 THE OUTLAW TRIAD DEMOSERIES 
 PART X 
Written by : Vulture/OT
Code in : Pascal
Topic : Face sorting
 Introduction 
Welcome to the Outlaw Triad demoseries! In these series we will be
talking about programming demoeffects in either pascal or assembler.
Theory behind the effects shall be discussed while a full sourcecode
is also provided.
The tenth release in the Outlaw Triad Demo Series! We will be talking
about face sorting in 3d objects. Face sorting will enable you to
determine in which order polygons in 3d objects should be drawn on
the screen. It's an essential part of coding 3d graphics. Enjoy!
 Theory 
We will be building a basic 3d engine this time using polygons to
create closed 3d objects. I will asume you know the basics of 3d
graphics coding, that is, how to rotate 3d points and how to
calculate 2d screen coЩrdinates.
The most important thing in 3d engines at this point is how to draw
the 3d object on the screen. Rotating the 3d object and calculating
2d coordinates shouldn't be real problems. However, drawing the
object correctly on the screen might cause significant troubles.
Polygons in 3d objects are to be drawn in a specific order, that is,
those polygons which are way deep in space have to be drawn first.
The polygons which are closer to the origin (closer to the eye) have
to be drawn last. Like this:
 Poly 1 (small z)
 
 
 Poly 2 (large z)
 
 
 
 
 
 

Hmm, it ain't very much 3d but with a little imagination you can see
that poly 1 has to be drawn first since it's drawn partially behind
poly 2. It's located deeper in space than the second poly.
If you draw poly 2 first and then poly 1, poly 2 will be partially
overwritten by poly 1 and that's not what we want. To be short, you
have to draw your polys from back to front, so that the nearest polys
(the ones close to the eye) overwrite the futher polys.
This is also known as "the painter's algorithm".
This is where face sorting comes in! Face sorting means finding out
in which order the polygons must be drawn on the screen. In our case,
we'll use the most simple method around and that's sorting the
polygons on their average z value! Let's take a look at this in
detail...
A polygon is made up by a number of 3dpoints. And each 3dpoint
consists of x,y,z values. If we add the z values from all 3dpoints
of a polygon and divide the resulting value by the number of
3dpoints, we've calculated the average z value of that polygon,
that is, how deep the polygon is in space.
Remember to do this AFTER you have rotated the 3dpoint! (note: in
the code, I did not divide the resulting value as it is not really
necessary)
We calculate the average z value for all the polygons in the 3d
object and store those values in a seperate list. Now we keep two
lists. One for all the average z values and one for the exact drawing
order of the polygons.
At start of each frame, the orderlist looks like:
1 2 3 4 5 6 7 8 9 etc etc...
So, each polygon got his own number. Ok, now we sort the polygons on
their z values, that is, we sort the average z values list.
For example: compare the first two values. If the first value
(average z of poly 1) is greater than the second value, swap them.
Repeat this until you've got an average z list in which the values
go from small to large. In the sourcecode, I used a bubblesort
routine to do this. These bubblesort routines work most of the time
but there are better algorithmes to sort values in a list. I mean,
try to use the provided bubblesort routine to sort, like, 400 values
each frame.
Bad idea... Just so you know... :) (hint: use a quicksort routine
instead)
Anyway, when you swap values in the average z value list, you must
also swap the corresponding values in the order list! So, if you swap
the first two values in the z value list, you must also swap the
first two values in the polygon orderlist. Ok, after you sorted the
average z value list, the final polygon orderlist could then look
something like:
3 5 6 4 2 8 1 9 7 etc etc...
At this time you've created a list in which the exact drawing order
of the polygons is saved! In our case we have to draw polygon 3
first, then 5, then 6, then 4 etc. Polygon 3 has the smallest
average z which means it lies far deep in space so it has to be
drawn first. There! Quite simple, eh? :)
Of course, as said before, you will have to reset the orderlist at
start of each frame to its original state (1,2,3,4 etc).
Ok, that's practically all there is to it. Simply sort all polygons
on their average z value and draw them from back to front. You can
also implement code to determine the facenormal. With this, we can
entirely skip drawing polygons which would not be visible on the
screen when the entire object has been drawn. This makes the engine
a lot faster. Also, you can go and do lightshading using facenormals.
Hmm... something for a future trainer.
The example source is a basic 3d system. It was the first 3d engine
I coded using this method so it's not that hot and needs a lot of
improvements. It should be enough to get started, though, as it shows
how a basic 3d engine works. We will be working on this 3d system in
future trainers. What about implementing glenzing and various kinds
of shading. Watch out for more docs from OT. Anyway, hope this helped
you a bit futher in 3d graphics coding.
If it has, greet Outlaw Triad in your productions. We like that...
:)
This is all for now. Happy coding!
Vulture/Outlaw Triad
 Distro Sites 
Call our distribution sites! All our releases are available at:
BlueNose World HQ +31 (0)345619401
The Force Distrosite +31 (0)365346967
Bugs'R'Us Distrosite +31 (0)252686092 More distros wanted!
The 7 Angels Distrosite +31 (0)715148377 (preferably outside
ShockWave South African HQ +27 (011)8886345 of the Netherlands)
Society HQ United States HQ +1 (518)4656721
ACe World Brazilian HQ +55 (21)2598847
Also check the major FTP/WWW sites for Outlaw Triad productions.
 Contact 
Want to contact Outlaw Triad for some reason? You can reach us at our
distrosites in Holland. Or if you have email access, mail us:
Vulture (coder/pr) comma400@tem.nhl.nl
Our internet homepage:
http://www.tem.nhl.nl/~comma400/vulture.html
These internet adresses should be valid at least till june 1997.

Quote: To do nothing is exhausting because you can't take breaks.
