
                     - THE OUTLAW TRIAD DEMO-SERIES -

 PART XIV 

                         Written by : Vulture/OT
                         Code in    : Pascal
                         Topic      : Hidden face removal

 Introduction 

 Welcome to the Outlaw Triad demo-series! In these series we will be talking
 about programming demo-effects in either pascal or assembler. Theory behind
 the effects shall be discussed while a full sourcecode is also provided.
 Another one on 3d! This time we will implement code to perform hidden face
 removal. With this, you can skip drawing faces which would not be visible
 on the screen when the entire object has been draw. So if coded correctly,
 this method will speed up your engine quite a bit. And 3d engines are never
 fast enough, right? Enjoy!

 Theory 

 - HIDDEN FACE REMOVAL -

 Well, it's time to do some optimizing. Sofar, we've made a rather nice 3d
 engine which is able to perform some cool effects but of course, we want it
 to be faster. Hmm, we can do that by using more assembler code or by looking
 at the program and trying to code it more efficiently. We're going to use the
 latter, that is, we are going to implement code to perform socalled hidden
 face removal. Now, what's that?

 Well, that's an easy one (did I say that before? :-)). For example, a cube
 consist of six sides. Sofar, when drawing a cube, we actually painted all
 six sides. But only three of them are visible from whatever side you are
 looking at the object (if you rotate on all three axis, otherwise even less
 sides are visible!). So why draw polygons which are not visible? That's not
 necessary at all! Here's where hidden face removal comes in. It involves
 methods to determine if the side you are about to draw is visible or not.

 Ok, question is how hidden face removal works. Well, as usual, there are
 several ways to determine if a face should or should not be drawn on the
 screen. I will show you a basic one which is good enough for objects with
 little or no overlapping of polygons. Here we go...

 To put it simply, it's a matter of clockwise versus anti clockwise. We need
 to setup the objects polygons so that the 3d points of visible polygons are
 in a clockwise order. The 3d points of non-visible polygons have to be setup
 in an anti clockwise order (remember, you do this when DEFINING the object!).
 Now, when drawing, you only draw those polygons from which the 3d points are
 clockwise. And if they are anti clockwise, don't draw the poly. Examine this:

                          1Ŀ2
                                              
                                              
                                              
                                              
                                              
                                              
                                              
                                              
                          43

 This is the front (visible side) of a polygon, ok? The 3d points are ordered
 in a clockwise direction. Now if you rotate it so you can see the back of the
 polygon, the 3d points will be ordered like this:

                          2Ŀ1
                                              
                                              
                                              
                                              
                                              
                                              
                                              
                                              
                          34

 They are ordered in an anti clockwise direction! Obviously, when you rotate
 this polygon again so that the points are in a clockwise direction again, you
 will see the front of the polygon again. So remember:

                              clockwise = front
                           anti clockwise = back

 Where the front of the polygon is visible (of course). Well, this means that
 we only have to find out if the polygon points are in a clockwise direction
 after rotation of the polygon. And, like said before, if they are clockwise,
 we draw the polygon. Otherwise we don't!

 Now how do we code something like this? Ok, to check if the 3d points are in
 a clockwise direction, we need to find the normal of the polygon. The normal
 of a polygon is at 90 degrees to the surface of the polygon. Like this:

                                      Normal
                                     
                                     
                                     
                    Polygon surface

 (note: you should imagine this polygon in 3d, of course)

 Remember we talked about normals in the previous trainer on lightsourcing?
 Read that doc for more info on normals. Anyway, we are working in 3d so the
 normal consist of x,y,z points also. Now we need three (not four) 3d points
 from the polygon to find the normal. The normal can be found like this:

                      Xn=(y2-y1)*(z1-z3)-(z2-z1)*(y1-y3)
                      Yn=(z2-z1)*(x1-x3)-(x2-x1)*(z1-z3)
                      Zn=(x2-x1)*(y1-y3)-(y2-y1)*(x1-x3)

 Don't ask me to explain how these formulas work cos I don't understand them
 either. My math really sux! I just know they work and that's enough... :-)
 If you want to know more about normals, go read any mathbook. There should
 be something in it about normals and stuff like that. And again, read the
 previous trainer for more info.
 Anyway, we don't even need to calculate the entire normal vector, that is,
 all three (x,y,z) components. We only need the Z (depth) component so our
 normal is determined by:

                  Normal := (x2-x1)*(y1-y3)-(y2-y1)*(x1-x3);

 Now when we rotate the polygon on all three axis, the polygon is visible when
 the normal is a positive value. The polygon isn't visible when the normal is
 a negative value. Thus, if the normal is positive, the polygons 3d points are
 clockwise. Otherwise they are anti clockwise. And that's all there is to it!
 Just remember:

          - Setup 3d points of visible polygons in a clockwise direction
          - Setup 3d points of nonvisible polygons anti clockwise
          - Now rotate object polygons
          - Determine Z normal of polygon
          - If Z normal > 0, draw polygon

 If you implement this correctly, your engine will be a LOT faster. See the
 example source for the result. Compare this with the previous trainers to
 see the difference in speed! The source is simply the previous trainer on
 light sourcing with these particular Z normal calculations added to it.

 Hint: In a previous trainer (#12), we calculated the entire face normal in
 order to find the color of a polygon. Now, using that facenormal, you take
 the z-component. If it's BELOW zero, don't draw the polygon. That's all.
 Saves you a couple of calculations too. So why don't you try to implement
 that method instead? Shouldn't be too hard...

 For questions, chatting or for suggestions for future trainers, mail me.
 If you spot inaccuracies, please mail me at once so I can correct anything
 wrong in these textfiles! Don't hesitate to contact me (or any other member
 of OT) cos we're always in for a chat... :-)

 That's all for now. Happy coding!

     -Vulture/Outlaw Triad-

 Distro Sites 

 All our releases are available at these fine boards:

  BlueNose      World HQ          +31 (0)345-619401
  The Force     Distrosite        +31 (0)36-5346967
  Bugs'R'Us     Distrosite        +31 (0)252-686092
  The 7 Angels  Distrosite        +31 (0)715-148377    More distros wanted!
  ShockWave     South African HQ  +27 (011)888-6345    (preferably outside
  Society HQ    United States HQ  +1  (518)465-6721     of the Netherlands)
  ACe World     Brazilian HQ      +55 (21)-259-8847
  Corps Elite   Canadian HQ      +403 (ITS)-PRIVATE
  Dark Genesis  Canadian Distro   +1  (250)561-2850

 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 e-mail 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: Anybody can win, unless there happens to be a second entry