Introduction

3D Programming Demos and Tutorials

Filling in
by Simon Brown

This tutorial
Now we are going to cover how to take a set of three screen coordinates (x, y)'s and draw a solid flat-shaded triangle. This process varies depending on your programming environment. I'm going to cover the maths behind drawing filled triangles and leave the implementation to you. You won't be able to do anything with the maths unless you can plot pixels yourself, which varies depending on your target platform and programming language.

Horizontal lines
The easiest way to draw 2D triangles is to draw a series of horizontal lines to fill up the space occupied by the triangle as shown in Figure 2.1 below.

Figure 2.1 - Drawing a triangle using horizontal lines.

Types of triangles
Once you've put your 3D triangle through the 3D to 2D transformation, and got three screen (x, y) coordinates, you will have one of three types of triangle - flat-topped, flat-bottomed, or general triangles (which means neither the top nor bottom is flat). Figure 2.2 shows the three types of triangle.

Figure 2.2 - The three triangle types

Ok, so you can see above that two of the triangle types have flat horizontal edges. To draw a general triangle we split it in half horizontally to make one flat-topped and one flat-bottomed triangle. This means every triangle we draw has a flat horizontal edge and a point at the top or bottom.

Taking the Flat-topped triangle above as an example, basically, we start drawing at the point (x_3, y_3) and work out the gradient (change in x) of each the two outer edges as we decrease y (go upwards, in other words). So we will have a loop from y_3 to y_2. The reason that we use y_3 to y_2 and not y_3 to y_1 is that it also works for the flat-topped half of a general triangle, as you can see from Figure 2.2.

So the change in x value of the two edges per line are worked out like this-

change in left edge per y = ( x_1 - x_3 ) / ( y_3 - y_2 )
change in right edge per y = ( x_2 - x_3 ) / ( y_3 - y_2 )

This is nothing more than simple linear interpolation. So we just have to keep track of the two x values of either edge of the line as we decrease y. We then feed the y value and the x values of the two ends of the line to a horizontal line drawing function (which we'll cover later).

Ok, next?
The first thing we need to do is to sort the three sets of coordinates in y order. This is fairly trivial.

float temp_x; // temporary variables, should be same type as x_1, x_2 etc.
float temp_y;

// Sort so y_1 is closest to the top of the screen, followed by y_2 and y_3

if ( y_2 < y_1 ) // Make sure point 2 is below (on screen) point 1
{

   temp_x = x_2;
   temp_y = y_2;
   x_2 = x_1;
   y_2 = y_1;
   x_1 = temp_x;
   y_1 = temp_y;
}

if ( y_3 < y_1 )   // Make sure point 3 is below (on screen) point 1
{

   temp_x = x_3;
   temp_y = y_3;
   x_3 = x_1;
   y_3 = y_1;
   x_1 = temp_x;
   y_1 = temp_y;
}

if ( y_3 < y_2 )   // Make sure point 3 is below (on screen) point 2
{

   temp_x = x_3;
   temp_y = y_3;
   x_3 = x_2;
   y_3 = y_2;
   x_2 = temp_x;
   y_2 = temp_y;
}

I didn't really have to show you that right? So now we've got our three (x, y)'s in ascending y order.

Horizontally splitting a "general" triangle
A general triangle must be split in half horizontally. This is a simple process. What we have to do is work out the x coordinate of the fourth point (x_4, y_2), shown in Figure 2.3 which is the only coordinate we haven't got if we are to make this triangle into one flat-topped and one flat-bottomed triangle. We already know the y value at this point, since it's the same as y_2.

Figure 2.3 - Splitting a "general" triangle in two horizontally.

So we now need to work out the x coordinate x_4 (shown above). We work out the ratio of the top height (from y_1 to y_2) divided by the total height (from y_1 to y_3). This tells us how far as a percentage the fourth point is along the edge it falls on. Since x_1 is always the top point and x_3 is always the bottom point (since we have sorted the three points by height), we know that x_3 to x_1 is the longest side, and the side which (x_4, y_2) must fall on.

So if we know the percentage along the line where x_4 falls and the x values at either end (x_3 and x_1) of the line then working out x_4 is straight forward. x_3 - x_1 gives us the length of the edge in x only, so multiply this by ratio will tell us how far along x_4 is (but not the actual coordinate) which we add to x_1 to give us the coordinate of x_4. Which looks like this in code-

float ratio = float ( y_2 - y_1 ) / float ( y_3 - y_1 ); // top height divided by total height

x_4 = ( ( x_3 - x_1 ) * ratio ) + x_1;

So there we go. That's all the preparation that's needed. We now have all the info we need to start drawing triangles. The process for drawing a flat-topped and flat-bottomed triangle is slightly different, so you will need two functions. For every triangle you call both the flat-topped and flat-bottomed triangle drawing functions, and the functions will work out for themselves whether they should be drawing anything. So if you've got only a flat-topped triangle, then when you call the flat-bottomed triangle function, it will work out that you are asking it to draw a zero height triangle and it will return without doing anything. You could equally well put this decision making prior to calling either function, and avoid a few function calls per frame, there's really no difference in speed, but there's less maths for me to explain when it's written this way.

This whole process is in no way 'set-in-stone', almost every software 3D engine you find will perform the same process but in a slightly different way.

Flat-Topped Triangle
As I described earlier, a flat-topped triangle involves a simple loop from y_3 to y_2. The starting x values for the end of the first horizontal line to be drawn are simply both x_3. We work out the gradient of both edges and then set the loop going.

// Draws a Flat-topped Triangle

void Draw_FT_Triangle ( void )
{

   float dx_left       = 0;   // left gradient
   float dx_right      = 0;   // right gradient
   float current_left = 0;   // current left hand position
   float current_right = 0;   // current right hand position

   float height = y_3 - y_2;   // height of triangle

   if ( height < 0.5 && height > -0.5 ) return; // do not draw a zero height triangle

   dx_left = ( x_4 - x_3 ) / height;
   dx_right = ( x_2 - x_3 ) / height;

   current_left = current_right = x_3; // both edges start at x_3

   for ( int i = y_3; i >= y_2; y-- ) // go from bottom to top
   {

if ( i > -1 && i < 480 ) // Only draw line if on screen vertically
{

         Draw_Line ( current_left, current_right, i );
      }

      current_left += dx_left;
      current_right += dx_right;

}
}

As you can see, we keep track of the current x values of either edges of the line in the variables current_left and current_right, which, of course, must be floating point variables. We store the change in these variables per line (the gradient) in dx_left and dx_right. We return if we get a zero height triangle. Also we only draw a line if it is on the screen vertically, although these values change depending on your screen resolution. Since we use x_4 instead of x_1 to work out the first gradient we automatically take account of the fact that we may be drawing half of a general triangle. If we are not drawing half of a general triangle, then x_4 turns out identical to x_1 anyway, so the code works for both circumstances.

Flat-Bottomed Triangle
Drawing a flat-bottomed triangle is very similar. This time we will be looping from y_1 to y_2, so we are drawing from the top down this time. We are still drawing starting at the point and proceeding to the flat edge. Again by using y_1 to y_2 we take account of the fact that this may be either a flat-bottomed triangle, or the flat-bottomed half of a general triangle. Here's the code

// Draws a Flat-bottomed triangle

void Draw_FB_Triangle ( void )
{

   float dx_left       = 0; // left gradient
   float dx_right      = 0; // right gradient
   float current_left = 0; // current left hand position
   float current_right = 0; // current right hand position

   float height = y_2 - y_1; // height of triangle

   if ( height < 0.5 && height > -0.5 ) return; // do not draw a zero height triangle

   dx_left = ( x_4 - x_1 ) / height;
   dx_right = ( x_2 - x_1 ) / height;

   current_left = current_right = x_1; // both edges start at x_1

   for ( int i = y_1; i <= y_2; i++ ) // go from top to bottom
   {

if ( i > -1 && y < 480 ) // Only draw line if it's on the screen vertically
{

         Draw_Line ( current_left, current_right, i );
      }

      current_left += dx_left;
      current_right += dx_right;

   }
}

And that's how we draw a flat-bottomed triangle. This time we use x_4 instead of x_3 for the first gradient, again so our function will cope with being sent a flat-bottomed triangle, or the flat-bottomed half of a general triangle. It's also worth mentioning that although I've named my variables with left and right, this doesn't mean than left always refers to the left hand edge. For flat shaded triangles it doesn't matter which edge is which, the values are automatically swapped round if current_left happens to be greater than current_right when they are passed to the horizontal line drawing function. I've done it this way again to simplify the code.

Drawing a Line
Ok, this is probably the easiest bit, drawing a horizontal line. As you can see from the previous code, the line drawing function is passed the left hand edge position, the right hand edge position and the y value (called i in the previous code).

// This function draws a horizontal line

void Draw_Line ( int left, int right, int y )
{

   if ( !( left < 0 && right < 0 ) && !( left > 639 && right > 639 ) ) // line is visible
   {

      if ( left > right ) // make sure we are drawing left to right on the screen
      {
         int temp_x = left;
         left = right;
         right = temp_x;
      }

      if ( left < 0 ) // if left edge is off screen move it to left-hand edge of screen
         left = 0;

      if ( right > 639 ) // same for right edge of line
         right = 639;

for ( int x_position = left; x_position <= right; x_position++ )
{

Plot ( x_position, y, colour );

}
}
}

And that's all there is to it. The only thing we have had to do here is make sure the line is on the screen horizontally and then make sure that left is actually the left hand of the two x values. Then we loop through the pixels in the line.

Implementation
As for how you implement Plot in your particular engine, it will depend on your target environment. In DOS and DirectDraw, you will have a pointer to the top-left pixel of your back-buffer and an offset to this pointer, which represents the current drawing position. So to draw a horizontal line you just keep incrementing the offset (the offset size must match the pixel size - 16 bit/32 bit etc) and setting the pixel colour. You will also need to know how much to increment the offset per y line as well, sometimes called the pitch. Say you are working in 16-bit colour, then the pitch is basically the difference between one point and the same point of the next y line in quantities of 16-bit's. Then to draw a horizontal line you would do-

offset = left + y * pitch;

for ( int x_position = left; x_position <= right; x_position++ )
{

*(video_buffer + offset) = colour;
offset++;

}

In DOS programming, the pitch will just be the screen width, since VGA memory is linear. In DirectDraw the pitch is not equal to the screen width. Instead it is the lPitch member of a DDSURFACEDESC2 struct, which is given in bytes, so divide by 2 for a 16-bit back-buffer. To plot pixels in DirectDraw you have to lock your back-buffer, and then you can request your video_buffer pointer and pitch form DirectDraw. If you don't know how to do that then chances are you don't know how to initialize DirectDraw anyway, so refer to the DirectX SDK under DirectDraw and Surfaces.

Note - although DirectX 8 doesn't have DirectDraw anymore, and it's 2D capabilities are limited, the capabilities needed for software 3D are still there, although the implementation has changed a little.

Conclusion
So, we now know the basics of taking some 3D points defined as (x, y, z)'s, transforming them into 2D screen coordinates, and then drawing a filled in triangle from these screen coordinates. You may have noticed that this engine will only work for objects that are straight ahead on the z-axis at the moment. This is deliberate and this is how the majority of 3D engines work. In the next tutorial I'm going to show you how to rotate and move your objects and the camera.