Denthor/Asphyxia’s VGA trainers: Hidden face removal

This trainer is on 3D hidden face removal and face sorting. I was going to add shading, but that can wait until a later trainer. For convenience I will build on the 3D code from Part 8. The maths for face removal is a bit tricky, but just think back to your old high school trigonometry classes.

DENTHOR, coder for ...
_____   _____   ____   __   __  ___  ___ ___  ___  __   _____
/  _  \ /  ___> |  _ \ |  |_|  | \  \/  / \  \/  / |  | /  _  \
|  _  | \___  \ |  __/ |   _   |  \    /   >    <  |  | |  _  |
\_/ \_/ <_____/ |__|   |__| |__|   |__|   /__/\__\ |__| \_/ \_/
smith9@batis.bis.und.ac.za
The great South African Demo Team! Contact us for info/code exchange!

Grant Smith, alias Denthor of Asphyxia, wrote up several articles on the creation of demo effects in the 90s. I reproduce them here, as they offer so much insight into the demo scene of the time.

These articles apply some formatting to Denthor's original ASCII files, plus a few typo fixes.

Face Sorting

There are many ways to sort faces in a 3D object. For now, I will show you just about the easiest one of the lot.

Say you have two polygons….

                ------P1

           ------------------P2

                   Eye

As you can see, P1 has to be drawn before P2. The easiest way to do this is as follows:

On startup, find the midpoint of each of the polys, through the easy equations:

x = (P2.1.x + P2.2.x + P2.3.x + p2.4.x)/4
y = (P2.1.y + P2.2.y + P2.3.y + p2.4.y)/4
z = (P2.1.z + P2.2.z + P2.3.z + p2.4.z)/4

NOTE: For a triangle you would obviously only use three points and divide by three.

Anyway, now you have the X,Y,Z of the midpoint of the polygon. You can then rotate this point with the others. When it is time to draw, you can compare the resulting Z of the midpoint, sort all of the Z items, and then draw them from back to front.

In the sample program I use a simple bubble sort… basically, I check the first two values against each other, and swap them if the first is bigger than the second. I continue doing this to all the numbers until I run through the entire list without swapping once. Bubble sorts are standard computer science topics… perhaps borrow a text book to find out more about them and other (better) sorting methods.

The above isn’t perfect, but it should work 90% of the time. But it still means that when you are drawing a cube, you have to draw all 6 sides every frame, even though only three or so are visible. That is where hidden face removal comes in…

Hidden Face Removal

Pick up something square. A stiffy disk will do fine. Face it towards you, and number all the corners from one to four in a clockwise direction.

                1 +-------------+ 2
                  |             |
                  |             |
                  |             |
                  |             |
                4 +-------------+ 3

Now rotate the stiffy disk on all three axes, making sure that you can still see the front of the disk. You will notice that whenever you can see the front of the disk, the four points are still in alphabetical order. Now rotate it so that you can see the back of the stiffy. Your points will now be:

                2 +-------------+ 1
                  |             |
                  |             |
                  |             |
                  |             |
                3 +-------------+ 4

The points are now anti-clockwise! This means, in its simplest form, that if you define all your polygon points in a clockwise order, when drawing you ignore the polys that are anticlockwise. (Obviously when you define the 3D object, you define the polygons facing away from you in an anticlockwise order.)

To find out whether a poly’s points are clockwise or not, we need to find its normal. Here is where things start getting fun.

In school, you are told that a normal is perpendicular to the plane. In ASCII:

                      | Normal
                      |
                      |
        --------------------------- Polygon

As you can see, the normal is at 90 degrees to the surface of the poly. We must extend this to three dimensions for our polygons. You’ll have to trust me on that, I can’t draw it in ASCII :)

To find a normal, you only need three points from your poly (ABC):

A(x0,y0,z0), B(X1,Y1,Z1), C(X2,Y2,Z2)

then the vector normal = AB^AC = (Xn,Yn,Zn) with

Xn=(y1-y0)(z0-z2)-(z1-z0)(y0-y2)
Yn=(z1-z0)(x0-x2)-(x1-x0)(z0-z2)
Zn=(x1-x0)(y0-y2)-(y1-y0)(x0-x2)

We are interested in the Z normal, so we will use the function:

normal:=(x1-x0)(y0-y2)-(y1-y0)(x0-x2);

The result is something of a sine wave when you rotate the poly in three dimensions. A negative value means that the poly is facing you, a positive value means that it is pointing away.

The above means that with a mere two MULs you can discount an entire poly and not draw it. This method is perfect for “closed” objects such as cubes etc.

I am anything but a maths teacher, so go borrow someone’s math book to find out more about surface normals. Trust me, there is a lot more written about them than you think.

An extension of calculating your normal is finding out about light-sourcing your polygons. Watch for more information in one of the next few trainers.

A combination of the above two routines should work quite nicely in creating 3d objects with little or no overlapping.