Copy Link
Add to Bookmark
Report

Hidden Surface Removal

DrWatson's profile picture
Published in 
atari
 · 2 months ago

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:

u = f \cdot \frac {x}{z}

and

v = f \cdot \frac{y}{z}

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:

A_x + B_y + C_z + D = 0

And once we've isolated x and y we get:

x = \frac{uz}{f}

and

y = \frac{vz}{f}

If we replace the variables in the plane equation, it becomes:

A \cdot \left(\frac {uz}{f}\right) + B \cdot \left(\frac {vz}{f}\right) + C_z = -D

and we can extract the z component:

z \cdot A(\frac{u}{f}) + B(\frac{v}{f} + C) = -D

So to find what we're looking for:

z = - \frac {D}{A(\frac{u}{f}) + B (\frac {v}{f}) + C}

But since we would need to execute all this divides for each pixel, it's much faster to compute the 1/z value instead:

\frac {1}{z} = -\frac{(A(\frac{u}{f}) + B(\frac{v}{f}) +C)}{\frac {D_1}{z}} = -(\frac{A}{ (fD)})u - (\frac{B}{(fD)})v - \frac{C}{D}

So at the beginning of a run of pixels:

\frac {1 }{z} = - \frac {A}{fD} \cdot u_1 - \frac {B}{fD} \cdot v - \frac {C}{D}

And for each pixels, it increments of:

- \frac {A}{fD}

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

← previous
next →
loading
sending ...
New to Neperos ? Sign Up for free
download Neperos from Google Play

Latest Articles

Recent comments

Neperos cookies
This website uses cookies to store your preferences and improve the service. Cookies authorization will allow me and / or my partners to process personal data such as browsing behaviour.

By pressing OK you agree to the Terms of Service and acknowledge the Privacy Policy

By pressing REJECT you will be able to continue to use Neperos (like read articles or write comments) but some important cookies will not be set. This may affect certain features and functions of the platform.
OK
REJECT