Toby Opferman
http://www.opferman.net
toby@opferman.net


				2D Primatives

	In this section we introduce some code and we introduce some
more theory on 2D.  Then in the next section, we introduce 3D using the
2D primatives.


	Lines, Circles, Rectangles, Triangles, and pixels are all graphics
primatives.  Everything can be made up of these primatives, even 3D graphics.


	Let us start out with Lines.  A line in computer graphics is really
a line segment.  It has a start point, an end point and a slope.  Now,
we need a way to draw a line on the screen.  Well, if the line is horizontal,
that is from (X1, Y1) to (X2, Y2)  Y1 = Y2, we have a horizontal line.


We can determine the length of this line is X2 - X1 and draw it such that:

FOR X = X1 to X2
  PutPixel(X, Y1)
END FOR

In a general pesudo code.

If a line is Verticle, that is X1 = X2 for (X1, Y1) - (X2, Y2)  we can
draw it such that

FOR Y = Y1 to Y2
  PutPixel(X1, Y)
END FOR


Now, when we work with graphics, we are going to be dealing with linear
memory.  That is, Y is defined as Y*MaxX.  This is because in order
to get to the line we need, we have to Multiply Y by the length of the width
of the screen.  Then, we add X.

Let's say we have this screen:
8x5: (All screens mxn are indexed 0 to (m-1), 0 to (n-1))

  0  1  2  3  4  5  6  7 
0 
1
2
3
4

And let's say it's actualy a linear screen.  That is, the values to get
to a position are:


   0  1  2  3  4  5  6  7  
0  0  1  2  3  4  5  6  7  
1  8  9 10 11 12 13 14 15
2 16 17 18 19 20 21 22 23
3 24 25 26 27 28 29 30 31
4 32 33 34 35 36 37 38 39


Now, to get a location on the screen, you have "Screen".
You need to add 1 number to it go to go to the location.
That is, this matrix is just imaginary, arbitrary, we only like to picture
it as a matrix, really, it's just a straight buffer from 0 to 39.

If Y = 0 and X = 0 then Screen + Y + X = 0

Now, the max X is 8.  So,

Screen + Y*8 + X  = Location.  Let's see:

Y = 3, X = 4   Y*8 + X = (3)*8 + 4 = 24 + 4 = 28


Look back above or at this lower simplified graph.

   0  1  2  3  4  5  6  7  
0 
1 
2 
3             28
4 

That is the correct linear combination.  

8 = 2^3  So Y (Bit Shift Left 3)  is the same thing.  

Let us look at that way:

Y = 3, X = 4

Now, instead of multiplying 8, we will bitshift.

Y<<3 + X

3 in Binary = 00000011

Shift if left 3 places

00011000
2^4+2^3 = 16 + 8 = 24 
24 + X = 24 + 4 = 28

there's your answer.  Why show you this?  Well, graphics is usually very
computational and processor consuming.  Bit shifting is faster than multiplication
on a computer especially.  This tutorial is NOT going to teach you how to do this,
I am just showing you that it is your best interest to look at things in different
lights and learn certain optimizations.  If you don't know about binary, you should
learn.  There is a tutorial under DOX that has Base Conversions on it (Assembly
tutorial 1) that you should read.


Second thing I want to mention is a Double Buffer.  Video memory is slow
and plus you don't want to be drawing on it while someone is viewing it.
You want to have an offscreen linear buffer the same size as the screen.
That way, you can draw on that and just blast that to the screen all at once.
And it's faster, video memory is always being accessed by the video card.

Ok, back to drawing lines.  If we want to draw a diaginal line, it's a bit
of work, but a guy named Bresenham came up with an algorithm to draw lines.

To draw a line, you want to get the change in X and the change in Y.

Here is the theory behind the algorithm.

You have a line (X1, Y1) to (X2, Y2)
For our example we will use 

(10, 4) to (20, 10)

We get a Delta X and a Delta Y (Delta means change, so Change in Y and Change in X)

Delta X = 20 - 10 = 10
Delta Y = 10 - 4 = 6

The Delta X is greater than Delta Y so we will plot along the X axis.
That way, we have more room to adjust the error for Y's descent.

So, we want a loop from 0 to 10.

At first, we just plot at (10, 4), the starting point.

  10 11 12 13 14 15 16 17 18 19 20
4  *
5
6
7
8
9
10

Now, we have an error counter. Which we will start off at 0, but now every time
we plot we will add the change of the variable that is NOT being plotted against.
Hence, we are moving along the X acess.  What we want to do is divide up
Y so that it is evenly divided amonst the delta of X.

Error = Error + Delta Y

Error is now 6.

We now increment X1 by 1 (Positive since we are going in the positive direction)

X1 is now 11.

Second time thru the loop we are at
(11, 4)

We plot:

  10 11 12 13 14 15 16 17 18 19 20
4  *  *
5
6
7
8
9
10

We add the error
Error = Error + Delta Y
Error = 6 + 6 = 12

Now, Error > Delta X.

So, we need to do some adjusting of the line.
We want to subtract DeltaX FROM the error to reset it
to a correct error position.
Error = Error - Delta X
Error = 12 - 10 = 2
Error = 2

Now, we want to increment Y1 by it's direction (Which is Positive) so we
add 1.

Y1 = Y1 + 1

And again, we add 1 to X1.

Now, we have
(12, 5)
We plot

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *
6
7
8
9
10


We add the error
Error = Error + Delta Y
Error = 2 + 6 = 8

Error is less than Delta X

Add 1 to X1


Now we have
(13, 5)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6
7
8
9
10

We add the error
Error = Error + Delta Y
Error = 8 + 6 = 14

Now, Error > Delta X.

So, we need to do some adjusting of the line.

Error = Error - Delta X
Error = 14 - 10 = 4
Error = 4

Now, we want to increment Y1 by it's direction (Which is Positive) so we
add 1.

Y1 = Y1 + 1

And again, we add 1 to X1.


Now we have
(14, 6)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6              *
7
8
9
10


We add the error
Error = Error + Delta Y
Error = 4 + 6 = 10

Error is equal to Delta X

So, we need to do some adjusting of the line.

Error = Error - Delta X
Error = 10 - 10 = 0
Error = 0

Add 1 to Y1

Add 1 to X1


Now we have
(15, 7)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6              *
7                 *
8
9
10



We add the error
Error = Error + Delta Y
Error = 0 + 6 = 6

And again, we add 1 to X1.

Now we have
(16, 7)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6              *
7                 *  *
8
9
10



We add the error
Error = Error + Delta Y
Error = 6 + 6 = 12

Error is greater than Delta X
Error = Error - Delta X = 2
Y1 = Y1 + 1

Add 1 to X1


Now we have
(17, 8)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6              *
7                 *  *
8                       *
9
10

We add the error
Error = Error + Delta Y
Error = 2 + 6 = 8
+++

And again, we add 1 to X1.


Now we have
(18, 8)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6              *
7                 *  *
8                       *  *
9                          
10

We add the error
Error = Error + Delta Y
Error = 8 + 6 = 14

Error > Delta X 

Error = Error - Delta X = 4
Y1 = Y1 + 1


And again, we add 1 to X1.

Now we have
(19, 9)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6              *
7                 *  *
8                       *  *
9                             *
10



We add the error
Error = Error + Delta Y
Error = 4 + 6 = 10

Error = Delta X 
Error = Error - Delta X = 0
Y1 = Y1 + 1


And again, we add 1 to X1.

Now we have
(20, 10)

  10 11 12 13 14 15 16 17 18 19 20
4  *  *  
5        *  *
6              *
7                 *  *
8                       *  *
9                             *
10                               *


And now X = 10, so the loop is done and so is the line.

As you can see, it's a pretty good algorithm.


Here is the Pseudo Code:



Delta X = X2 - X1
Delta Y = Y2 - Y1

IF Delta X < 0 THEN
   Sign Delta X = -1
ELSE
   Sign Delta X = 1
END IF

IF Delta Y < 0 THEN
   Sign Delta Y = -1
ELSE
   Sign Delta Y = 1
END IF

Delta X = Sign Delta X * Delta X + 1
Delta Y = Sign Delta Y * Delta Y + 1

ERROR = 0

IF Delta X >= Delta Y THEN
   FOR X = 0 TO Delta X - 1
       Plot(X1, Y1)

       ERROR = ERROR + Delta Y

       IF ERROR >= Delta X THEN
          ERROR = ERROR - Delta X
          Y1 = Y1 + Sign Delta Y
       END IF
  
       X1 = X1 + Sign Delta X
   END FOR
ELSE
   FOR Y = 0 TO Delta Y - 1
       Plot(X1, Y1)

       ERROR = ERROR + Delta X

       IF ERROR >= Delta Y THEN
          ERROR = ERROR - Delta Y
          X1 = X1 + Sign Delta X
       END IF
  
       Y1 = Y1 + Sign Delta Y
   END FOR
END IF



The next thing you will want to learn is how to make a triangle.
Since any polygon is just a bunch of triangles formed together, you
get a fast triangle drawing function you can draw them all.


Now, obviously when I say draw a triangle I'm not talking just connecting
3 lines.  I am talking about drawing the real solid triangle.


You will laugh at this, but not only do we have to split polygons up into
triangles, but we have to split triangles up into triangles!

See, we want to be able to draw horizontal lines very easily.
So, we make that we have 2 types of triangles. Flat Top and Flat bottom.
If a triangle isn't one of those two, we make it one.

Exmaple:

Take this triangle:

|\
| \
|  \
|   \
|    \
|     \
|     /
|    /
|   /
|  /
| /    
|/



Divide it like so:
|\
| \
|  \
|   \
|    \
|_____\
|     /
|    /
|   /
|  /
| /    
|/



Now you have 2 seperate triangles:

|\
| \
|  \
|   \
|    \
|_____\



 _____
|     /
|    /
|   /
|  /
| /    
|/


A flat bottom and a flat top.


How do you split it? You just need 1 more point.

First thing, you want to sort the points.

You have 3 points.  (X1, Y1), (X2, Y2), (X3, Y3)


This is how you sort them:

IF Y1 > Y2 THEN
  Swap(Y1, Y2)
  Swap(X1, X2)
END IF

IF Y1 > Y3 THEN
  Swap(Y1, Y3)
  Swap(X1, X3)
END IF

IF Y2 > Y3 THEN
  Swap(Y2, Y3)
  Swap(X2, X3)
END IF


To test for a Flat Top Triangle:

IF Y1 = Y2 THEN
  FlatTop
END IF

To Test For A Flat Bottom Triangle:

IF Y2 = Y3 THEN
  FlatBottom
END IF

Also, Remeber:

IF Y1 = Y2 AND Y2 = Y3 THEN
  This is a line
END IF

IF X1 = X2 AND X2 = X3 THEN
  This is a line
END IF

Also, if Any 2 Vertexs are Equal, Then that is a line as well.


IF X1 = X2 AND Y1 = Y2 THEN
  This is a line
END IF

IF X2 = X3 AND Y3 = Y2 THEN
  This is a line
END IF

Y3 Cannot Equal Y1 unless Y2 Equals Y1 since you sorted them.



Now, you have them sorted, say you have these triangles:

(5, 10), (5, 15), (10, 15) Flat Bottom
(5, 10), (5, 10), (10, 15) Flat Top
(5, 8), (6, 12), (15, 15) Irregular

Well, on an irregular triangle, the middle point, (X2, Y2) has to create
the new point to split the triangle.

We will call this point (NewX, NewY)

For Obvious reasons, NewY = Y2.

We are splitting these Horizontally.  So, NewY will be the same as Y2.

Now, we need to computer NewX.

Here is our triangle:

   5  6  7  8  9 10 11 12 13 14 15
 8 *  
 9     
10  
11  
12    * 
13      
14     
15                                *

I can't put the lines in so you are going to have to imagine.

Now, you know that the NewX should be on line 12 and on the line between
X1 and X3.


   5  6  7  8  9 10 11 12 13 14 15
 8 *  
 9     
10  
11  
12    *         
13      
14     
15                                *

(5, 8), (6, 12), (15, 15) Irregular

(X3 - X1) = Delta X (10)
Now, you can divide 10 by 15.

(Delta X)/Y3

10/15 = 0.666666666666666666666666666666667

That is the change in X from X1 to X3

So, .6666 * Y2 = NewX

That's .6666 * 12 = 8

NewX = 8



   5  6  7  8  9 10 11 12 13 14 15
 8 *  
 9     
10  
11  
12    *     *    
13      
14     
15                                *



Now, the triangle is split.

Split Triangles are drawn like so:
FlatBottom (X1, Y1), (X2, Y2), (NewX, Y2)
FlatTop    (X2, Y2), (NewX, Y2), (X3, Y3)

Now, you want to draw a triangle with a flat bottom.

What we need to do is the same thing as the line algorithm did.


             (X1, Y1)


(X2, Y2)                    (NewX, Y2)


We start at (X1, Y1).  We plot a dot.  Now, we need to change the Length
of our drawing gradually so the  Right side will end up at (NewX, Y2).
AND, we also need to change the start position of our drawing so the Left side
ends up at (X2, Y2).

NewX and X2 in Ascending order.

IF X2 > NewX THEN
  Swap(X2, NewX)
END IF

Next, you want to find out Delta X2 and Delta NewX
Delta Y = (Y2 - Y1)
Delta X2 = (X1 - X2)/(Delta Y)
Delta NewX = (NewX - X1)/(Delta Y)

Just like the line.  We make it porportional.  We get the distance from X1 to X2 (And X1 to
NewX)  And we make it porportional. i.e., every New Y, it goes up a portion.  This is what
we need.  (Now, triangles NEED to work with floats.  But, the Line aglorithm I showed you
works fine with integers.)

(5, 8), (6, 12), (15, 15) Was our triangle.
We now have:

(5, 8), (6, 12), (8, 12) Flat Bottom
(6, 12), (8, 12), (15, 15) Flat Top

Delta Y = (12 - 8) = 4
Delta X2 = (6 - 5)/4 = 1/4 = .25
Delta NewX = (8 - 5)/4 = 3/4 = .75
Get an End X.
EndX = Delta NewX + X1 + .50 = .75 + 5.50 = 6.25
Add on .50 to round up.
Length = 1

Now, we start the loop.
Now, as you can see, if we every line do the following:

Plot(X1, Y1) Length 1

Y1 = Y1 + 1 = 9
X1 = X1 + Delta X2 = 5.25
Length = EndX - X1 = 6.25 - 5.25 = 1 (Add on 1 so you plot 2 pixels) +1 = 2
EndX = EndX + Delta NewX = 5.75 + .75 = 6.50


Next round:

Plot(X1, Y1) Length 2
These are rounded to integers so,
Plot(5, 9)

Y1 = Y1 + 1 = 10
X1 = X1 + Delta X2 = 5.25 + .25 = 5.50
Length = EndX - X1 = 6.50 - 5.50 = 1 (Add on 1 so you plot 2 pixels) + 1 = 2
EndX = EndX + Delta NewX = 6.50 + .75 = 7.25


Next Round:

Plot(6, 10) Length 2


Y1 = Y1 + 1 = 11
X1 = X1 + Delta X2 = 5.50 + .25 = 5.75
Length = EndX - X1 = 7.25 - 5.75 = 2 (Add on 1 so you plot 2 pixels) + 1 = 3
EndX = EndX + Delta NewX = 7.25 + .75 = 8


Next Round:

Plot(6, 11) Length 3

Y1 = Y1 + 1 = 12
X1 = X1 + Delta X2 = 5.75 + .25 = 6
Length = EndX - X1 = 8 - 6 = 2 (Add on 1 so you plot 2 pixels) + 1 = 3
EndX = EndX + Delta NewX = 8 + .75 = 8.75

Plot(6, 12) Length 3

And it looks like this:

   5  6  7  8  9 10 11 12 13 14 15
 8 *  
 9 *  *      
10    *  *  
11    *  *  *      
12    *  *  *    
13      
14     
15                                *


Here is pseudo code:

IF X2 > X3 THEN
  Swap(X2, X3)
END IF

Delta X = (X2 - X1)/(Y2 - Y1)
NewDelta = (X3 - X1)/(Y2 - Y1)
BegX = X1
EndX = NewDelta + X1 + .5
Length = 1
    
FOR Y = Y1 TO Y2
  Plot(BegX, Y, Length)
  BegX = BegX + Delta X
  Length = (EndX - BegX) + 1  
  EndX = EndX + NewDelta
END FOR



Seems simple enough.  But something is missing.  If you do run that, you do see that
some bigger triangles look ok and some triangles look a little messed up.  We need
to perfect this so the triangle will be more perfect.  Can you think of any ideas?
Sure, we can try the .5 to .75 with a little bit of difference, but not what we want.
These triangles are pretty rigid, see if you can figure out a way to make them more
accurate.

These triangles need to be pretty decent together because, we are supposed to
be able to fit triangles together to make polygons.  If they aren't working
propertly, you will see holes in them, pixels missing.  


The next would be to do the flat top triangles and as you figured it's pretty much
the same as the flat bottom triangles.

Well, we have A line from (X1, Y1) to (X2, Y2).

We want these to merge to (X3, Y3).


But, instead of wasting my time telling you how to do this, I will now go into another
method.



First thing first, like always, get deltas.  The change of X as Y changes by 1.
That is how we work things.  Just like I stated in the line drawing and in 
the flat top.  We want how much X changes as we change Y by 1 so we can
appropriately increment X.  Now, if it is not 1:1 (That is, Delta X = 1,
which means for every Y + 1 you have X + 1 (A perfect situation!)), we don't have
.5 of a pixel, so we must approximate and round.  That is why the .5 was added onto DeltaX
of the one above.  We need to figure out a good approximation.


But, I am not going to show you bottom triangle code.  Instead, we are going to step
up a bit and try to fix the problem.  I only made the crap code above for better
visualization.  What if we forget about creating a middle X.  What if we forget
about checking for bottom and top triangles?  Well, let's see this better Pseudo Code.


* First, like above, we sort.

IF Y1 > Y2 THEN
  Swap(Y1, Y2)
  Swap(X1, X2)
END IF

IF Y1 > Y3 THEN
  Swap(Y1, Y3)
  Swap(X1, X3)
END IF

IF Y2 > Y3 THEN
  Swap(Y2, Y3)
  Swap(X2, X3)
END IF

* And again, we need the deltas, but instead of splitting the triangle, let us
* get the deltas for each line.


Delta X1 = X2 - X1
Delta X2 = X3 - X2
Delta X3 = X3 - X1
Delta Y1 = Y2 - Y1
Delta Y2 = Y3 - Y2
Delta Y3 = Y3 - Y1

* Now, Let use create the Deltas to be used in the loops

IF Delta Y1 IS NOT 0 THEN
   D1 = Delta X1 / Delta Y1
ELSE
   D1 = 0
END IF

* Now, you can't divide by 0, so we need a check in.

IF Delta Y2 IS NOT 0 THEN
   D2 = Delta X2 / Delta Y2
ELSE
   D2 = 0
END IF

IF Delta Y3 IS NOT 0 THEN
   D3 = Delta X3 / Delta Y3
ELSE
   D3 = 0
END IF

* Now, we have the loops.  We want to loop to where we WOULD have split, then
* change how we create the lines and loop again.

* The Flat Bottom Triangle
FOR V = Y1 TO Y2

*  You start at X1 and you Add the current Y value subtracted by Y1.  Then you multiply
*  The change in X as Y approcahes the maximum. 
   
  PlotX1 =  X1 + (V - Y1)*D1;
  PlotX2 =  X1 + (V - Y1)*D3;  

  HorizontalLine(PlotX1, PlotX2, V) 
END FOR

* The Flat Top Triangle
FOR V = Y2 TO Y3

*  You start at X2 and you Add the current Y value subtracted by Y2.  Then you multiply
*  The change in X as Y approcahes the maximum. 

  PlotX1 =  X2 + (V - Y2)*D2;
  PlotX2 =  X1 + (V - Y1)*D3;  

  HorizonalLine(PlotX, V)
END FOR



NOTE: The parameters for this arbitrary Horizontal Line Function are:

HorizontalLine(X1, X2, Y)

If you don't FULLY understand this, it is ok.  With modern APIs you don't have to anyway.
And even with no APIs, you can just use the psuedo code I gave.  I made the first one,
with the shitty right side, in ten minutes for this tutorial.  But, the above version
I did not make myself, but it is a better version.  I leave optimizations up to you
now however.  The above works on the same principal as the one I came up with, but it
works better.

For primative 3D beginnings a circle function is not needed.  If you want to draw a circle,
A SIMPLE function would just be:

FOR THETHA = 0 TO 360
  PlotPixel(Radius*COS(THETA), Radius*SIN(THETA))
END FOR


(Notice in my examples I ignore a "color" parameter, these are arbitrary functions,
so they are omitted.)


There is a more optimized way to do a circle, with integers.  As you also could tell,
that will only plot 360 pixels.  If your circle has a radius that on a computer screen
would need > 360 pixels, you would see start to see spaces between the pixels of the circle.

This tutorial has served it's purpose and theory on drawing a circle is irrevevant and
is left up to your own research if you are interested.  Or, you could think of how to do
it on your own.

For the basics of 3D, A line drawing function and a triangle drawing function are definately
what you need.  You need to get really familar with the triangle function.  Since, not
only is it used to draw a solid surface, but texture mapping needs to be drawn in combination
with it, and so does lighting.  It's pretty much the most important primative.  Now, yes,
once you get to graphics APIs like DirectX and OpenGL you don't have to worry about it anymore
since most things are done for you.  This is behind the scenes tho, you should know how things
work so you have a better understanding even if you just use an API.  

Also remeber, these routines are NOT optimized, they are even just pseudo code.
Another important aspect of 3D and game programming alone is speed.  I would always
look for faster and better methods.