- THE OUTLAW TRIAD DEMO-SERIES -

----------------------- PART IX ------------------------------------

                 Written by : Inopia/OT
                 Code in    : Pascal
                 Topic      : Polygons

            

---------------------- 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.
 This time we discuss polygons. The way I'm going to describe is not
 the only one. But who cares, the only difference between this and
 other routines, is that some scan over the X-axis, instead of the
 Y-axis as we do. You can use polygons to create filled 3d objects,
 like seen in many demos. And when you understand these basics, you
 can expand the code to texture mapping, gourad shading and a lot
 more! Ok, let's get started with some serious explaining.

------------------------- Theory -----------------------------------

 We will discuss how to draw filled triangles. Hmm, you may find
 yourself wondering, why the hell triangles? If not, skip this.
 Otherwise, triangles have some very special abilities. First of all,
 any other geometrical shape can be formed with multiple triangles.
 A square can be represented by two triangles for example (just like
 those stupid tangram puzzles). And second, in a triangle, step values
 are the same everywhere. You will see this later on (if you get that
 far anyhow, cos I'm not very good at this stuff :-) ).
 Furthermore, it's pretty standard! When your 3d engine is up to
 multiple faced objects, you can load in 3DS files as they work with
 triangles too.

 THE BASICS
 ----------

 A polygon can be drawn on a (virtual) screen by drawing horizontal
 lines.

             -
            ---
           -----
          -------
         ---------
        -----------
       ----------
      --------
     ------
    ----
   --
  -

 Yeah well, it doesn't really look like a poly, but hey,
 it's textmode... :-)
 Anyhow, we will need to sort the coordinates on Y values. The
 coordinates are called P1, P2, and P3. They are 2D coordinates and
 can be referred to as P1.X,P1.Y,P2.X,P2.Y etc..

            P1
           / \
          /   \
         /     \
        /       \
       /         \
      /        /  P3
     /      /
    /    /
   /  /
  //
 P2

 So, we should sort this stuff on Y-values. It's needed to find the
 longest side and all that, so it's really crucial. Pay attention.
 There are only 3 coordinates, so the sorting is simple
 (another reason to use triangles!).
 We are going to put P1, P2, and P3 into TOP, MID, and BOT which are
 2d points too.

 -Find out wich of P1.Y and P2.Y is the smallest (remember, we are
  looking for coordinates who are high on the screen, so with low
  Y-values..), and put that one in TOP. The other on in BOT.
 -Now find out where to put the P3. There are three possibilities:
   -P3.Y>TOP.Y and P3.Y<BOT.Y.
    This means you can put it in between: MID=P3.
   -P3.Y<TOP.Y. It's the smallest! Since TOP isn't anymore,
    you put it in MID.
    TOP=MID. Now put the P3 in top. TOP=P3.
   -P3.Y>BOT.Y. It's the biggest, so you can safely store it in BOT.
    But put BOT in MID first: MID=BOT. BOT=P3

 Well, this sorting routine should be about the largest part of your
 routine, since a flat poly involves nothing more than a bit of
 interpolating.

 INTERPOLATING?
 --------------

 Interpolating is a way of getting from A to B in C steps.

   A------------------B

  10km               50km

 Just like those neat math books you had years ago. Well,
 town A is 10km, and city B is 50km. So they're 40km apart. But you're
 in town A, and your girlfriend is in city B. So you want to get over
 there PRONTO! You don't want to spend more time sitting in your rusty
 old car than about 25 minutes.
 So C=25.

  Delta=(B-A)/C

 Delta, also called stepvalue, is the distance in km you should travel
 every minute to get to your girlfriend in time. Delta is the greek
 letter EB.

  EB=(50-10)/25
  EB=40/25
  EB=1.6

 So you should travel 1.6km every minute to get there in time. That's

  1.6*60=96km/hr

 But your rusty little car gets a flat tire and you don't make it...
 <hehe>
 What did we learn here? Well, we can now interpolate! We can get
 from one X-value to another one in any amount of steps, like from
 the TOP.X to the MID.X. This is quite important.

 BACK TO THE BASICS
 ------------------

 Ok. Let's grab the triangle again..

            TOP
           / \
          /   \
         /     \
        /       \
       /         \
      /        /  MID
     /      /
    /    /
   /  /
  //
 BOT


 As you can see, there's one long side (TOP-BOT), and two shorter
 ones (TOP-MID), and (MID-BOT). Now we are going to make two loops
 by cutting the long side in two:

            TOP           -
           / \             |
          /   \            | Loop1
         /     \           |
        /       \          |
       /         \         |
     Q*        /  MID     -
     /      /              |
    /    /                 | Loop2
   /  /                    |
  //                       |
 BOT                      -

 We have inserted point Q in here just to clearify things, you really
 don't need to know it's coordinates (you can find out if you would
 want to).
 With the stuff we've just learned, we can start interpolating the
 X-values needed for the horizontal lines. Make a loop from TOP.Y to
 MID.Y.
 This is LOOP1:

  FOR NR=TOP.Y TO MID.Y DO
  NEXT NR

 Now we must start to interpolate. Firstly we get two EB (Delta,
 (B-A)/C) values, we shall graciously call EBR and EBL. EBLeft and
 EBRight. The first one we do is TOP-MID:

  EBL=(MID.X-TOP.X)/(MID.Y-TOP.Y)

 This makes perfect sense, just check out the "picture". We have to
 "travel" from TOP.X to MID.X. The distance (C) is from TOP.Y to
 MID.Y. So, MID.Y-TOP.Y!
 The other one is (TOP-Q). But we don't know QX! Well, Q is on
 (TOP-BOT), so we can use BOT in stead of Q:

  EBR=(BOT.X-TOP.X)/(BOT.Y-TOP.Y)

 Now we can start interpolating:

  RPOS=TOP.X
  LPOS=TOP.X
  FOR NR=TOP.Y TO MID.Y DO
    HLINE(RPOS,LPOS,NR,COLOR)
    RPOS=RPOS+EBR
    LPOS=LPOS+EBL
  NEXT NR

 HLINE is ofcourse the routine wich draws the horizontal lines.
 COLOR is the color the poly should become, hence the name.
 Now we have drawn half the poly. That's not enough for real coders
 like you, so we shall get on with the second part. This is ofcourse
 the same routine, with other values. We must now interpolate
 (MID-BOT), and (Q-BOT). Since Q-BOT is the same side as TOP-BOT,
 we can still use the EBR, calculated before. But EBL has to be
 recalculated.

  EBL=(BOT.X-MID.X)/(BOT.Y-MID.Y)

  And now we go and draw the second part of the triangle like this:

  LPOS=MID.X
  FOR NR=MID.Y+1 TO BOT.Y DO
    HLINE(RPOS,LPOS,NR,COLOR)
    RPOS=RPOS+EBR
    LPOS=LPOS+EBL
  NEXT NR

 RPOS shouldn't be changed, for the previous loop should have left it
 exactly at QX. Also, since your loops are TOP.Y-MID.Y and
 MID.Y-BOT.Y, you're doing MID.Y twice. So that's why the second loop
 should start at MIDY+1.

 HORIZONTAL LINES
 ----------------

 Yeah well, this should be quite obvious. Just plot a row of pixels:

  FOR I=X1 TO X2 DO
    PUTPIXEL(I,Yline,Color)
  NEXT I

 Convert this to a fast inline assembler routine to gain speed.
 Shouldn't be too hard if you know assembler.

 Ok, I believe this is about all. You should be able to create
 flatpolys now. If I'm up to it, I'll release a sequal, explaining
 how to upgrade these flatpolys to gouraud and texture,
 and eventually PHONG, but I'm too tired right now.
 You can always contact me for futher talk.

   Later,

       -Inopia/Outlaw Triad-

-------------------------- 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
   Inopia    (coder)      inopia@horizon.nl

 Our internet homepage:

   http://www.tem.nhl.nl/~comma400/vulture.html

 These internet adresses should be valid at least till june 1997.

----------------------------------------------------------------------

               Quote: Welcome to the future! She just started!