 THE OUTLAW TRIAD DEMOSERIES 
 PART IX 
Written by : Inopia/OT
Code in : Pascal
Topic : Polygons
 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.
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 Xaxis, instead of the
Yaxis 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 Yvalues. 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
Yvalues..), 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.
AB
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=(BA)/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=(5010)/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 Xvalue 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 (TOPBOT), and two shorter
ones (TOPMID), and (MIDBOT). 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
Xvalues 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,
(BA)/C) values, we shall graciously call EBR and EBL. EBLeft and
EBRight. The first one we do is TOPMID:
EBL=(MID.XTOP.X)/(MID.YTOP.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.YTOP.Y!
The other one is (TOPQ). But we don't know QX! Well, Q is on
(TOPBOT), so we can use BOT in stead of Q:
EBR=(BOT.XTOP.X)/(BOT.YTOP.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
(MIDBOT), and (QBOT). Since QBOT is the same side as TOPBOT,
we can still use the EBR, calculated before. But EBL has to be
recalculated.
EBL=(BOT.XMID.X)/(BOT.YMID.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.YMID.Y and
MID.YBOT.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 email 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!
