Hidden Surface Removal
Fifth part of The 3D Coding Blackhole tutorial series
- 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
- Required time increase faster
- Hard to implement (especially overlapping tests)
- Unable to sort correctly complex scenes
BinarySpacePartitioning trees
- Extremely fast
- Hard to implement
- Can only sort static polygons
- Need stored trees
Z-Buffering
- Required time increasing linearly with the number of polygons
- Faster than the Painter's above 5000 polygons
- Able to render any scene perfectly, even logically incorrect ones
- Extremely easy to implement
- Straightforward
- Requires a lot of memory
- 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 computations 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; c<MEMORYSIZE; c++)
zbuffer[c]=-32767;And now come more maths. How do you find the z coordinate? We only have them for the defined vertices, not for EVERY point of the polygon. Actually, what you need is to do is the inverse of projection. And our projection equations were:
and
where u is the x coordinate on the screen, minus XOrigin, and v is the y coordinate on the screen, minus YOrigin. The plane equation is:
And once we've isolated x and y we get:
and
If we replace the variables in the plane equation, it becomes:
and we can extract the z component:
So to find what we're looking for:
But since we would need to execute all this divides for each pixel, it's much faster to compute the 1/z value instead:
So at the beginning of a run of pixels:
And for each pixels, it increments of:
What will the code look like?
#define FIXMUL (1<<20)
int offset=y*MODEINFO.XResolution+x1;
int i=x1-Origin.x, j=y-Origin.y;
float z_,dz_;
ZBUFTYPE z,dz;
//Initialize 1/z value (z: 1/z)
dz_=((A/(float)Focal_Distance)/-D);
z_=((dz_*i)+( (B*j/(float)Focal_Distance) + C) /-D);
dz=dz_*FIXMUL;
z=z_*FIXMUL;Then for each pixel, we simply do a:
if(z>ZBuffer[offset])
{
zbuffer[offset]=z;
SCREENBUFFER[offset]=color;
}
z+=dz;And we got it!
Copyright © 1996-1998 Jerome St-Louis
