Hidden Surface Removal

Hidden Surface Removal

Fifth part of The 3D Coding Blackhole tutorial series

Home at http://3Dblackhole.base.org

NOTE: Some part of functions and some members of structures are not
explained here, but we'll discuss them in other tutorials of the series.
They're usually displayed in totality for the sake of similarity between
the different tutorials and with the complete 3D engine.
---------------------------------------------------------------------------

   * The Dilemna
   * Backfaces removal
   * Z-Buffering

The Dilemna

The heart of a 3D engine is its HSR system... So you must think twice about
which one to chose... I'll point right now the pros and cons of the most
popular ones:

Painter's algorithm

        o Required time increase faster
        o Hard to implement (especially overlapping tests)
        o Unable to sort correctly complex scenes

BinarySpacePartitioning trees

        o Extremely fast
        o Hard to implement
        o Can only sort static polygons
        o Need stored trees

Z-Buffering

        o Required time increasing linearly with the number of polygons
        o Faster than the Painter's above 5000 polygons
        o Able to render any scene perfectly, even logically incorrect ones
        o Extremely easy to implement
        o Straightforward
        o Requires a lot of memory
        o Usually slow

My own choice is Z-Buffering. I will only talk about it, so if you want
some reference for the other algorithms, take a look at my list in the last
chapters.

Backfaces removal

In addition to these methods, we can easily remove back facing polygons to
save a lot of computing time. We will start by defining some useful
function to compute our plane and normals and all that stuff. Later, we
will add texture and shading computaions to this function. These numbers
will be kept in global variables:

float A,B,C,D;
BOOL backface;

And our function's beginning will look like this. We start by extracting
every coordinate in float variables:

void ENG3D_SetPlane(Polygon_t *Polygon,Object_t *Object)
{
   float x1=Vert(0).Aligned.x;
   float x2=Vert(1).Aligned.x;
   float x3=Vert(2).Aligned.x;
   float y1=Vert(0).Aligned.y;
   float y2=Vert(1).Aligned.y;
   float y3=Vert(2).Aligned.y;
   float z1=Vert(0).Aligned.z;
   float z2=Vert(1).Aligned.z;
   float z3=Vert(2).Aligned.z;

Then we compute every member of the plane equation:

   A=y1*(z2-z3)+y2*(z3-z1)+y3*(z1-z2);
   B=z1*(x2-x3)+z2*(x3-x1)+z3*(x1-x2);
   C=x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2);
   D=-x1*(y2*z3-y3*z2)-x2*(y3*z1-y1*z3)-x3*(y1*z2-y2*z1);

Then we check if it's facing us or not:

   backface=D<0;
}

Z-Buffering

Z-Buffering consists in keeping the z coordinate of every point we put on
the screen in a huge array, and when we come to put another at the same
place, we check if it is closer to the viewer or if it behind. We only draw
it in the first case. As you can see, the only thing we have to do is to
compute the z value for every point. But first of all, we declare a global
array and allocate space for it (MEMORYSIZE is the product of the vertical
and horizontal resolutions):

typedef long ZBUFTYPE;
ZBUFTYPE *zbuffer;
zbuffer=(ZBUFTYPE *)malloc(sizeof(ZBUFTYPE)*MEMORYSIZE);

We use a long as the z-buffer type, because we're gonna use fixed points.
And you must not forget to set every z coordinate to the farthest value
possible:

   int c;
   for(c=0; cZBuffer[offset])
   {
      zbuffer[offset]=z;
      SCREENBUFFER[offset]=color;
   }
   z+=dz;

And we got it!
---------------------------------------------------------------------------
E-mail me at jerstlouis@videotron.ca
Back to Jerome St-Louis's Homepage
Back to The 3D Coding BlackHole

                                                  Last Updated: 08-24-1997
Discuss this article in the forums
Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)
See Also:
Miscellaneous