Sample Pamper Series - Part 3: 3D-Polygons and Lines

• Download source code - 13.3 KB

Introduction

This is the third part in the Sample Pamper series, and this time, we will turn to those of you who want to know about creating a surface for your 3D objects. In this case, we will focus on polygon surfaces, z-buffer, light and reflection, and drawing a 3D-line. The focus will not lie on cute encapsulations within code objects. We are going to focus on this in the fourth and the final part of this series when we are going to create a game out of what we have learnt this far.

This article will describe…

• Requirement
• The example
• The J.E. Bresenham line algorithm
• The algorithm with the z axis
• The 3D polygon
• The Z buffer
• Points of interest
• History
• References - for further reading
• Disclaimer

Requirement

You will need Visual Studio .NET installed to be able to run and try the source code for this article.

Back to top?

The example

This example will paint some polygons, like the ones in the picture, and rotate them. It will also display the light and reflection with two lines, this to more visually describe to you how the light will fall and reflect against the surface (if you want to read more about light and reflections, you can read: Part 1: 3D-Light, Flat-shading, and Rotations, and Part 2: 3D-Light Reflections of the Sample Pamper series). The light vector will follow the mouse pointer so that you easily change it and see the new effect. To paint a surface like this one in the picture, you will need to know the corners points, these corners are the ones creating the surface. You should then place polygons between these points to build the surface. The polygons should also be kept as small as possible, which we can do by adding points to the mesh (Polygon mesh) so that we can add several smaller polygons to it, and it would end up looking something like this:

But, how many points should we have then? It depends on many things, and one of them is how near the object is in the Z-order; the further away, the less number of points is needed, and contrary. But in our case, it will not be considered because it will be too much to handle in this article, so we will stick with some points for the surface in every case. But, how do we draw a polygon that will know every point in the z order so that we will know if a point is behind another? The polygon we drew in articles one and two was the one built in within the Graphics library, and this one can only handle x and y coordinates; we need the z coordinate to make it happen also. We must consider drawing a new one, handling x, y, and z coordinates by our selves.

The J.E. Bresenham line algorithm

A polygon is based on several lines, and to draw a line, we can use the line formula as this famous one:

p = pStart + t * L

where p is the point in the line segment and pStart is the starting point from where the segment is supposed to be drawn. The t goes from 0 to 1, and L is the length of the segment.

But, this line formula has its flaws, and will display cracks in the surface in some angles, if being used for this purpose. To solve this problem, you will need something that will follow the pixels on the screen much better, and I will therefore introduce the Bresenham line algorithm to you as it is made for plotters (Bresenham). This line will be rasterized so that it can't jump pixels like the line formula could.

private void SpeedLine2D(int x, int y, int xx, int yy)
{
 int dx = (xx-x);
 int dy = (yy-y);
        
 //Direction pointer.

 int step_x = 0;
 int step_y = 0;

 //Moving right step +1 else -1

 if(dx>=0)
  step_x = 1;
 else
 {
  step_x = -1;
  dx = -dx;
 }
 if(dy>=0)
  step_y = 1;
 else
 {
  step_y = -1;
  dy = -dy;
 }
            
 //You need this to make the err_term work.
 //Because we are using integers we must multiply with 2

 int dx2 = dx*2; //delta X * 2 instead of 0.5

 int dy2 = dy*2; //delta Y * 2 ..


 //Set err_term to height*2 and decrement by the segment width.
 //example. 2-10 =-8

 err_termXY = dy2 - dx;

  //Step x direction by one until the end of width.

  for(int i=0;i<=dx;i++)
  {
   //Paint the pixel
   //Example..

   bm.SetPixel(x,y,color);

   //Adjust error_term
   //and step down or up by one in the y path.
   //This if it's time to do so.

   if(err_termXY>=0)
   {
    err_termXY -= dx2; //err minus the width*2;

    y += step_y; //Step down or up by one.
   }
   err_termXY += dy2; //Add err_term by the height * 2;

   x += step_x; //step right or left

  }
 }
}

This function above is only displaying the part when x is dominating; you'll need the part when it's y dominating too, but you can see what it does here.

Back to top?

The algorithm with the z axis

But still, what about the z axis we where talking about? We must implement this to the algorithm too, and then it could look something like the following:

private void SpeedLine3D(int x, int y, int z, int xx, int yy, int zz)
{
 int dx = (xx-x);
 int dy = (yy-y);
 int dz = (zz-z);
         
 //Direction pointer.

 int step_x = 0;
 int step_y = 0;
 int step_z = 0;

 //Moving right step +1 else -1

 if(dx>=0)
  step_x = 1;
 else
 {
  step_x = -1;
  dx = -dx;
 }
 if(dy>=0)
  step_y = 1;
 else
 {
  step_y = -1;
  dy = -dy;
 }
 if(dz>=0)
  step_z = 1;
 else
 {
  step_z = -1;
  dz = -dz;
 }
            
 //You need this to make the err_term work.
 //Because we are using integers we must multiply with 2

 int dx2 = dx*2; //delta X * 2 instead of 0.5
 int dy2 = dy*2; //delta Y * 2 ..
 int dz2 = dz*2; //delta Z * 2 ..

 int err_termXY = 0; //Zero it
 int err_termXZ = 0; //Zero it

 //If width is greater than height
 //we are going to adjust the height movment after the x steps.

 if(dx>=dy&&dx>=dz)
 {
  //Set err_term to height*2 and decrement by the segment width.
  //example. 2-10 =-8

  err_termXY = dy2 - dx;
  err_termXZ = dz2 - dx;

  //Step x direction by one until the end of width.

  for(int i=0;i<=dx;i++)
  {
   //Paint the pixel
   //Example..

   bm.SetPixel(x,y,color);

   //Adjust error_term
   //and step down or up by one in the y path.
   //This if it's time to do so.

   if(err_termXY>=0)
   {
    err_termXY -= dx2; //err minus the width*2;

    y += step_y; //Step down or up by one.

   }
   if(err_termXZ>=0)
   {
    err_termXZ -= dx2; //err minus the width*2;

    z += step_z; //Step in or out by one.

   }
   err_termXY += dy2; //Add err_term by the height * 2;

   err_termXZ += dz2; //Add err_term by the depth * 2;


   //This will happen all the time.

   x += step_x; //step right or left

  }
 }
 else if(dy>dx&&dy>dz)//Height is leading the position.

 {
  //Set err_term to width*2 and decrement by the delta y.

  err_termXY = dx2 - dy;
  err_termXZ = dz2 - dy;

  //Step y direction by one until the end of height.

  for(int i=0;i<=dy;i++)
  {            
   //Paint one pixel

   bm.SetPixel(x,y,color);

   //Adjust error_term
   //and step left or right by one in the x path.
   //This if it's time to do so.

   if(err_termXY>=0)
   {
     err_termXY -= dy2; //err minus the height*2;

     x += step_x; //Step right or left by one.

   }
   if(err_termXZ>=0)
   {
    err_termXZ -= dy2; //err minus the height*2;

    z += step_z; //Step depth in or out by one.

   }
   err_termXY += dx2; //Add err_term by the width * 2;

   err_termXZ += dz2; //Add err_term by the depth * 2;

 
   //This will happen all the time.

   y += step_y; //step up or down.

  }
 }
 else if(dz>dx&&dz>dy)//Depth is leading the position.

 {
  //Set err_term to width*2 and decrement by the delta z.

  err_termXY = dx2 - dz;
  err_termXZ = dy2 - dz;

  //Step z direction by one until the end of depth.

  for(int i=0;i<=dz;i++)
  {
   //Paint one pixel

   bm.SetPixel(x,y,color);

   //Adjust error_term

   //and step up or down by one in the y path.

   //This if it's time to do so.

   if(err_termXY>=0)
   {
    err_termXY -= dz2; //err minus the depth*2;

    y += step_y; //Step up or down by one.

   }
   if(err_termXZ>=0)
   {
    err_termXZ -= dz2; //err minus the depth*2;

    x += step_x; //Step right or left by one.

   }
   err_termXY += dy2; //Add err_term by the height * 2;

   err_termXZ += dx2; //Add err_term by the width * 2;


   z += step_z; //step in or out.

  }
 }
}

Back to top?

The 3D polygon

Now that we have our new way of painting a 3D line, we can go on with the polygon. The best way of filling a polygon is to draw a horizontal line from the points in the left side line segment to the right side line segment of the polygon. What we need is to use the algorithm we made based on the Bresenham algorithm to first calculate every single unique y point, and that unique y positions the x coordinate in LS1, LS2, and LS3, and then we draw lines from left to right between these points.

We are going to fill these line segment points into an array first and then paint horizontal lines from this information. To manage this, I've developed the line algorithm a bit so that it handles three lines with x, y, and z in one single loop.

  private void CalculatePolygon(uint[][] zbuffer, Poinx3D p1,
  Poinx3D p2, Poinx3D p3, double intencity, int red, int green, int blue)
  {
   ArrayList aR1 = new ArrayList();
   ArrayList aR2 = new ArrayList();
   ArrayList aR3 = new ArrayList();

   //Calculate the rest

   //       p1

   //       /|

   //   LS1/ |LS3

   //   p2/  |

   //      \ |

   //    LS2\|p3  


   int LS1x = p2.X-p1.X;
   int LS1y = p2.Y-p1.Y;
   int LS1z = p2.Z-p1.Z;
   int LS2x = p3.X-p2.X;
   int LS2y = p3.Y-p2.Y;
   int LS2z = p3.Z-p2.Z;
   int LS3x = p3.X-p1.X;
   int LS3y = p3.Y-p1.Y;
   int LS3z = p3.Z-p1.Z;

   //Make directions.

   if(LS1x>=0)
    step_LS1x = 1;
   else
   {
    step_LS1x = -1;
    LS1x = -LS1x;
   }
   if(LS1z>=0)
    step_LS1z = 1;
   else
   {
    step_LS1z = -1;
    LS1z = -LS1z;
   }
   if(LS2x>=0)
    step_LS2x = 1;
   else
   {
    step_LS2x = -1;
    LS2x = -LS2x;
   }
   if(LS2z>=0)
    step_LS2z = 1;
   else
   {
    step_LS2z = -1;
    LS2z = -LS2z;
   }
   if(LS3x>=0)
    step_LS3x = 1;
   else
   {
    step_LS3x = -1;
    LS3x = -LS3x;
   }
   if(LS3z>=0)
    step_LS3z = 1;
   else
   {
    step_LS3z = -1;
    LS3z = -LS3z;
   }
   //Never divide with integers,

   //Better double it up by 2.

   //For the error term.

   int L2S1x = LS1x*2;
   int L2S1y = LS1y*2;
   int L2S1z = LS1z*2;
   int L2S2x = LS2x*2;
   int L2S2y = LS2y*2;
   int L2S2z = LS2z*2;
   int L2S3x = LS3x*2;
   int L2S3y = LS3y*2;
   int L2S3z = LS3z*2;

   //Init error terms for the three lines

   //If linesegment 3 is x dominate?

   if(LS3x>=LS3y&&LS3x>=LS3z)
   {
    //Init err term for x,y and z.

    //From the LS3x value.

    err_LS3x = L2S3x-LS3x;
    err_LS3y = L2S3y-LS3x;
    err_LS3z = L2S3z-LS3x;
   }
   else if(LS3y>LS3x&&LS3y>LS3z)
   {
    //Else it's y dominate.

    //Init err term for x,y and z.

    err_LS3x = L2S3x-LS3y;
    err_LS3y = L2S3y-LS3y;
    err_LS3z = L2S3z-LS3y;
   }
   else //Z dominant movement.

   {
    err_LS3x = L2S3x-LS3z;
    err_LS3y = L2S3y-LS3z;
    err_LS3z = L2S3z-LS3z;
   }

   //Same for all of the rest..

   if(LS2x>=LS2y&&LS2x>=LS2z)
   {
    err_LS2x = L2S2x-LS2x;
    err_LS2y = L2S2y-LS2x;
    err_LS2z = L2S2z-LS2x;
   }
   else if(LS2y>LS2x&&LS2y>LS2z)
   {
    err_LS2x = L2S2x-LS2y;
    err_LS2y = L2S2y-LS2y;
    err_LS2z = L2S2z-LS2y;
   }
   else //Z dominant movement.

   {
    err_LS2x = L2S2x-LS2z;
    err_LS2y = L2S2y-LS2z;
    err_LS2z = L2S2z-LS2z;
   }

   if(LS1x>=LS1y&&LS1x>=LS1z)
   {
    err_LS1x = L2S1x-LS1x;
    err_LS1y = L2S1y-LS1x;
    err_LS1z = L2S1z-LS1x;
   }
   else if(LS1y>LS1x&&LS1y>LS1z)
   {
    err_LS1x = L2S1x-LS1y;
    err_LS1y = L2S1y-LS1y;
    err_LS1z = L2S1z-LS1y;
   }
   else //Z dominant movement.

   {
    err_LS1x = L2S1x-LS1z;
    err_LS1y = L2S1y-LS1z;
    err_LS1z = L2S1z-LS1z;
   }

   for(int i=0;i<(storXY>storZ?storXY:storZ);i++)
   {
    //Line segment 1 --------------------


    //If segment 1 is x dominate,

    //and it's time to step up or down?

    if(err_LS1y>=0&&i<=LS1x&&LS1x>=LS1y
    &&LS1x>=LS1z)
    {
     //First store the old point.

     Poinx3D pp1 = new Poinx3D();
     pp1.X = x1+p1.X;
     pp1.Y = y1+p1.Y;
     pp1.Z = z1+p1.Z;
     aR1.Add(pp1);

     //Give a new row and continue.

     err_LS1y -= L2S1x; //We take away L2S1x from the err term.

     y1 += step_LS1y; //Step up or down.

    }
    //We also need to find next x step.

    //If segment 1 is still x dominate,

    //and it's time to step left or right?

    if(err_LS1x>=0&&i<=LS1x&&LS1x>=LS1y
    &&LS1x>=LS1z)
    {
     err_LS1x -= L2S1x; //Still the same, x dominate.

     x1 += step_LS1x; //Left or right?

    }
    //And now we want the next z in the x dominate.

    if(err_LS1z>=0&&LS1x>=LS1y&&LS1x
    >=LS1z&&(z1>=0?z1:-z1)<LS1z)
    {
     err_LS1z -= L2S1x; //Still x dominate.

     z1 += step_LS1z; //In or out?

    }
    //Now same thing for the y dominate.

    //If segment 1 is y dominate,

    //and it's time to step right or left?

    if(err_LS1x>=0&&i<LS1y&&LS1y>LS1x
    &&LS1y>LS1z)
    {
     err_LS1x -= L2S1y;
     x1 += step_LS1x;
    }
    //And we also need the next y step

    //in the y dominate movement (LS1y>LS1x).

    //Time to move up or down?

    if(err_LS1y>=0&&i<=LS1y&&LS1y
    >LS1x&&LS1y>LS1z)
    {
     Poinx3D pp1 = new Poinx3D();
     pp1.X = x1+p1.X;
     pp1.Y = y1+p1.Y;
     pp1.Z = z1+p1.Z;
     aR1.Add(pp1);

     err_LS1y -= L2S1y;
     y1 += step_LS1y;
    }
    //And in the y dominate, the z step.

    if(err_LS1z>=0&&LS1y>LS1x&&
    LS1y>LS1z&&(z1>=0?z1:-z1)<LS1z)
    {
     err_LS1z -= L2S1y;
     z1 += step_LS1z;
    }
    //If segment 1 is z dominate,

    //and it's time to step up or down?

    if(err_LS1y>=0&&i<=LS1z&&LS1z>
    LS1x&&LS1z>=LS1y)
    {
     Poinx3D pp1;
     pp1.X = x1+p1.X;
     pp1.Y = y1+p1.Y;
     pp1.Z = z1+p1.Z;
     aR1.Add(pp1);

     err_LS1y -= L2S1z;
     y1 += step_LS1y;
    }
    //We also need to find next x step.

    //If segment 1 is still z dominate,

    //and it's time to step left or right?

    if(err_LS1x>=0&&i<=LS1z&&LS1z>LS1x
    &&LS1z>=LS1y)
    {
     err_LS1x -= L2S1z;
     x1 += step_LS1x;
    }
    //And now we want the next z in the z dominate.

    if(err_LS1z>=0&&LS1z>LS1x&&LS1z>=
    LS1y&&(z1>=0?z1:-z1)<LS1z)
    {
     err_LS1z -= L2S1z;
     z1 += step_LS1z;
    }
    
    //Line segment 2 ----------------
    //Same for line 2..
    //Line segment 3 ---------------
    //And.. line 3
    //------------------------


    //Now add error terms..
    err_LS1x += L2S1x;
    err_LS1y += L2S1y;
    err_LS1z += L2S1z;
    err_LS2x += L2S2x;
    err_LS2y += L2S2y;
    err_LS2z += L2S2z;
    err_LS3x += L2S3x;
    err_LS3y += L2S3y;
    err_LS3z += L2S3z;
   }
   //Paint the polygon.

   PolyPainter(zbuffer, aR1, aR2, aR3, intencity, red, green, blue);
}

In this algorithm, you can see that we are using three arrays, and yes, they are of the ArrayList type, which is not the fastest way to go. We are only adding the last point from the line segment once for every new row, so that we will end up having one unique point per y row, and we are doing this with LS1, LS2, and LS3.

Now, when this is done, we can start to paint horizontal lines between these stored points, as you can see in the following picture:

To realize this in code, you'll get the following code snippet:

private void HorizontalLine3D(uint[][] zbuffer, Poinx3D p1,
     Poinx3D p2, double intencity, int red, int green, int blue)
{
 //Delta lengths

 int dx = (p2.X-p1.X);
 int dz = (p2.Z-p1.Z);
            
 //Direction pointers.

 int step_x = 0;
 int step_z = 0;

 //Moving right step +1 else -1

 if(dx>=0)
  step_x = 1;
 else
 {
  step_x = -1;
  dx = -dx;
 }
 if(dz>=0)
  step_z = 1;
 else
 {
  step_z = -1;
  dz = -dz;
 }
            
 int dx2 = dx*2; //delta X * 2 instead of 0.5

 int dz2 = dz*2; //delta Z * 2 ..

 int err_termXZ = 0;
        
 //Unified things.

 int uni1D = 0, uni2D2 = 0;
 int inc11 = 0, inc12 = 0, inc2 = 0;
 int step1D2 = 0, step2D = 0;
 int loopTo = 0, direction = 0;

 if(dx>=dz)
 {
  err_termXZ = dz2 - dx;
  direction = 0;
  loopTo = dx;
  uni1D = dx2;
  inc11 = p1.Y;
  step1D2 = step_z;
  inc12 = p1.Z;
  uni2D2 = dz2;
  inc2 = p1.X;
  step2D = step_x;
 }
 else if(dz>dx)
 {
  err_termXZ = dx2 - dz;
  direction = 2;
  loopTo = dz;
  uni1D = dz2;
  inc11 = p1.Y;
  inc12 = p1.X;
  step1D2 = step_x;
  uni2D2 = dx2;
  inc2 = p1.Z;
  step2D = step_z;
 }
            
 for(int i=0;i<=loopTo;i++)
 {
  Color cl = Color.FromArgb(red,green,blue);
  if(direction==0)
  {
   if(inc12>zbuffer[inc2][inc11])
   { 
     //Paint pixel based on intensity

     bm.SetPixel(inc2,inc11,cl);

     //Add point to the z buffer.

     zbuffer[inc2][inc11] = Convert.ToUInt32(inc12);
   }
  }
  if(direction==2)
  {
   if(inc2>zbuffer[inc12][inc11])
   {
    bm.SetPixel(inc12,inc11,cl);
    zbuffer[inc12][inc11]=Convert.ToUInt32(inc2);
   }
  }
  //Adjust error_term

  //This if it's time to do so.

  if(err_termXZ>=0)
  {
   err_termXZ -= uni1D;
   inc12 += step1D2;
  }
  err_termXZ += uni2D2;
  inc2 += step2D;
 }
}

This function will paint a horizontal line from one line segment to another, so we have released it from the y part because it's not needed here. The int parameters to this function will be the points as we have stored in our three line segment arrays.

Back to top?

The Z buffer

In the previous code snippets, you can see that we are using a Z-buffer to prevent pixels behind others to be painted. The z buffer is just a screen buffer that has the highest z order of a x, y point stored, to compare this with a new coordinate to see if it is in front or behind the stored one. If the new coordinate is behind the stored one, it will not be shown, and if it's in front, it will be painted, and this new z position will be stored in the buffer instead.

Back to top?

Points of interest

There is one sample to play around with in C#. And, this articles code is only made for learning, so don't expect to see something in a nice package. Made it this way to be simple to follow. But, I've realized that it's not easy anyway because of the size of this project. The next article Part 4 in this series will present a 2/3D-game called SpaceBox made from the knowledge we have got this far.

Back to top?

History

• Version 1.0, uploaded 27 September, 2007 - One version included for the article, for C#.
• Version *, changed 10 October, 2007 - Made some changes to the article.

Back to top?

References

Links

• Sample Pamper Part 1: 3D-Light, flat-shading, and rotations
• Sample Pamper Part 2: 3D-Reflection Vectors
• Sample Pamper Part 4: 2/3D-Game
• Jack E. Bresenham
• The Bresenham Line-Drawing Algorithm
• Anti-Aliased Line Drawing
• Simple Ray Tracing in C# Part IV (Anti-Aliasing), by Andalmeida

Back to top?

Disclaimer

This software is provided 'as-is' without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software. Permission is granted to anyone to use this software for learning purpose only. And, never could you claim that it is yours.