Triangle fillers

Flat triangle

Flat triangle

Drawing triangle (or in general convex polygon, but as I said we will use only triangles) is very simple. The basic idea of the line triangle drawing algorithm is as follows.

For each scanline (horizontal line on the screen), find the points of intersection with the edges of the triangle. Then, draw a horizontal line between intersections. Do this for all scanlines and you are done.
But how can we find these points quickly?? Using linear interpolation!

We have 3 vertices and we want to find coordinates of all points belonging to segments determined by these vertices.
Assume we have segment given by points: (xa,ya) and (xb,yb). Our task is to find points: (xc,ya+1), (xd,ya+2), ... , (xm,yb-1), (xn,yb).
Notice that xa changes to xb in (yb-ya) steps.
We also have: xa=xa+0*(xb-xa)/(yb-ya),
xb=xa+(yb-ya)*(xb-xa)/(yb-ya) and, in general, xi=xa+(yi-ya)*delta, where delta=(xb-xa)/(yb-ya).

The general function for linear interpolation is:
f(X) = A + X*((B-A)/steps) where we slide from A to B in steps steps


Here is pseudocode for a triangle filling algorithm.

  • the coordinates of vertices are (A.x,A.y), (B.x,B.y), (C.x,C.y); we assume that A.y<=B.y<=C.y (you should sort them first)
  • dx1,dx2,dx3 are deltas used in interpolation
  • horizline draws horizontal segment with coordinates (S.x,Y), (E.x,Y)
  • S.x, E.x are left and right x-coordinates of the segment we have to draw
  • S=A means that S.x=A.x; S.y=A.y;
*** begin triangle filler ***

	if (B.y-A.y > 0) dx1=(B.x-A.x)/(B.y-A.y) else dx1=0;
	if (C.y-A.y > 0) dx2=(C.x-A.x)/(C.y-A.y) else dx2=0;
	if (C.y-B.y > 0) dx3=(C.x-B.x)/(C.y-B.y) else dx3=0;

	S=E=A;
	if(dx1 > dx2) {
		for(;S.y<=B.y;S.y++,E.y++,S.x+=dx2,E.x+=dx1)
			horizline(S.x,E.x,S.y,color);
		E=B;
		for(;S.y<=C.y;S.y++,E.y++,S.x+=dx2,E.x+=dx3)
			horizline(S.x,E.x,S.y,color);
	} else {
		for(;S.y<=B.y;S.y++,E.y++,S.x+=dx1,E.x+=dx2)
			horizline(S.x,E.x,S.y,color);
		S=B;
		for(;S.y<=C.y;S.y++,E.y++,S.x+=dx3,E.x+=dx2)
			horizline(S.x,E.x,S.y,color);
	}

*** end triangle filler ***

I ought to explain what is the comparision dx1 > dx2 for. It's optimization trick: in the horizline routine, we don't need to compare the x's (S.x is always less than or equal to E.x).

Trick

Gouraud triangle

Gouraud triangle

The idea of gouraud and flat triangle is nearly the same. Gouraud takes only three parameters more (the color value of each of the vertices), and the routine just interpolates among them drawing a beautiful, shaded triangle.
You can use 256-colors mode, in which vertices' colors are simply indices to palette or hi-color mode (recommended).

Flat triangle interpolated only one value (x in connection with y), 256 colors gouraud needs three (x related to y, color related to y, and color related to x), hi-color gouraud needs seven (x related to y, red,green,blue component of color related to y, and color related to x (also three components))

Drawing a gouraud triangle, we add only two parts to the flat triangle routine. The horizline routine gets a bit more complicated due to the interpolation of the color value related to x but the main routine itself remains nearly the same.


I'll give you a full gouraud routine because good pseudocode is better than the best description :-)

  • the coordinates of vertices are (A.x,A.y), (B.x,B.y), (C.x,C.y) we assume that A.y<=B.y<=C.y (you should sort them first)
  • vertex A has color (A.r,A.g,A.b), B (B.r,B.g,B.b), C (C.r,C.g,C.b), where X.r is color's red component, X.g is color's green component and X.b is color's blue component
  • dx1,dx2,dx3 are deltas used in interpolation of x-coordinate
  • dr1,dr2,dr3, dg1,dg2,dg3, db1,db2,db3 are deltas used in interpolation of color's components
  • putpixel(P) plots a pixel with coordinates (P.x,P.y) and color (P.r,P.g,P.b)
  • S=A means that S.x=A.x; S.y=A.y; S.r=A.r; S.g=A.g; S.b=A.b;
*** begin gouraud triangle filler ***

	if (B.y-A.y > 0) {
		dx1=(B.x-A.x)/(B.y-A.y);
		dr1=(B.r-A.r)/(B.y-A.y);
		dg1=(B.g-A.g)/(B.y-A.y);
		db1=(B.b-A.b)/(B.y-A.y);
	} else 
		dx1=dr1=dg1=db1=0;

	if (C.y-A.y > 0) {
		dx2=(C.x-A.x)/(C.y-A.y);
		dr2=(C.r-A.r)/(C.y-A.y);
		dg2=(C.g-A.g)/(C.y-A.y);
		db2=(C.b-A.b)/(C.y-A.y);
	} else 
		dx2=dr2=dg2=db2=0;

	if (C.y-B.y > 0) {
		dx3=(C.x-B.x)/(C.y-B.y);
		dr3=(C.r-B.r)/(C.y-B.y);
		dg3=(C.g-B.g)/(C.y-B.y);
		db3=(C.b-B.b)/(C.y-B.y);
	} else 
		dx3=dr3=dg3=db3=0;

	S=E=A;
	if(dx1 > dx2) {
		for(;S.y<=B.y;S.y++,E.y++) {
			if(E.x-S.x > 0) {
				dr=(E.r-S.r)/(E.x-S.x);
				dg=(E.g-S.g)/(E.x-S.x);
				db=(E.b-S.b)/(E.x-S.x);
			} else 
				dr=dg=db=0;
			P=S;
			for(;P.x < E.x;P.x++) {
				putpixel(P);
				P.r+=dr; P.g+=dg; P.b+=db;
			}
			S.x+=dx2; S.r+=dr2; S.g+=dg2; S.b+=db2;
			E.x+=dx1; E.r+=dr1; E.g+=dg1; E.b+=db1;
		}

		E=B;
		for(;S.y<=C.y;S.y++,E.y++) {
			if(E.x-S.x > 0) {
				dr=(E.r-S.r)/(E.x-S.x);
				dg=(E.g-S.g)/(E.x-S.x);
				db=(E.b-S.b)/(E.x-S.x);
			} else 
				dr=dg=db=0;
			P=S;
			for(;P.x < E.x;P.x++) {
				putpixel(P);
				P.r+=dr; P.g+=dg; P.b+=db;
			}
			S.x+=dx2; S.r+=dr2; S.g+=dg2; S.b+=db2;
			E.x+=dx3; E.r+=dr3; E.g+=dg3; E.b+=db3;
		}
	} else {
		for(;S.y<=B.y;S.y++,E.y++) {
			if(E.x-S.x > 0) {
				dr=(E.r-S.r)/(E.x-S.x);
				dg=(E.g-S.g)/(E.x-S.x);
				db=(E.b-S.b)/(E.x-S.x);
			} else 
				dr=dg=db=0;

			P=S;
			for(;P.x < E.x;P.x++) {
				putpixel(P);
				P.r+=dr; P.g+=dg; P.b+=db;
			}
			S.x+=dx1; S.r+=dr1; S.g+=dg1; S.b+=db1;
			E.x+=dx2; E.r+=dr2; E.g+=dg2; E.b+=db2;
		}

		S=B;
		for(;S.y<=C.y;S.y++,E.y++) {
			if(E.x-S.x > 0) {
				dr=(E.r-S.r)/(E.x-S.x);
				dg=(E.g-S.g)/(E.x-S.x);
				db=(E.b-S.b)/(E.x-S.x);
			} else 
				dr=dg=db=0;

			P=S;
			for(;P.x < E.x;P.x++) {
				putpixel(P);
				P.r+=dr; P.g+=dg; P.b+=db;
			}
			S.x+=dx3; S.r+=dr3; S.g+=dg3; S.b+=db3;
			E.x+=dx2; E.r+=dr2; E.g+=dg2; E.b+=db2;
		}
	}

*** end gouraud triangle filler ***

I hope you are familiar with idea of interpolation now, because I'm not going to give you another pseudocodes. You should do something by yourself, too, don't you think? :)

Texture triangle

Texture mapped triangle

I'll show you the idea of linear (or 'classical') texture mapping (without perspective correction). Linear mapping works pretty well (read: fast) in some scenes, but perspective correction is in some way needed in most 3D systems.

Anyway: Again we're using the idea of interpolation: now we'll code a texture triangle filler. And again the idea is perfectly the same, only two more values to interpolate, that is five values total. In texture mapping, we interpolate x, u, and v related to y, and u and v related to x (u and v are coordinates in the 2D bitmap space). The situation is maybe easier to understand by looking at the following picture:

Texture mapping

The left triangle is the triangle which is drawn onto the screen. There's a single scanline (one call to the horizline routine) pointed out as an example. The triangle on the right is the same triangle in the bitmap space, and there's the same scanline drawn from another point of view into it, too. So we need just to interpolate, interpolate, and once more interpolate in a texture filler - an easy job if you've understood the idea of a gouraud filler.

An optimization trick: the color deltas in gouraud and (u,v) coordinate deltas in texture remain constant, so we need to calculate them only once per polygon. Let's take the u delta in linear texturing as an example. Assume, that dx2<=dx3 (we are using the same symbols like in flat and gouraud filler). As we know, we need to interpolate S.u to E.u in the horizline routine in (S.x-E.x) steps. We are in the need of a u delta (du) which would be the same for the whole polygon. So instead of calculating in each scanline this:
du = (E.u-S.u) / (E.x-S.x),
we do like this in the setup part of the polygon routine:
We know that
S.x = A.x + (B.y-A.y)*dx1,
S.u = A.u+(B.y-A.y)*du1,
E.x = B.x = A.x+(B.y-A.y)*dx2,
E.u = B.u = A.u+(B.y-A.y)*du2,

WHEN y=B.y (when y is the y-coordinate of the second vertex).

When we place the values of the variables S.u,E.u,S.x and E.x (above) to the u delta statement,
du = (E.u-S.u) / (E.x-S.x),
we get the following statement as a result:



       [A.u+(B.y-A.y)*du2] - [A.u+(B.y-A.y)*du1]
  du = -----------------------------------------
       [A.x+(B.y-A.y)*dx2] - [A.x+(B.y-A.y)*dx1]

           (B.y-A.y)*(A.u-A.u+du2-du1)
<=>   du = ---------------------------
           (B.y-A.y)*(A.x-A.x+dx2-dx1)

           du2-du1
<=>   du = -------
           dx2-dx1

                    outerUdelta2-outerUdelta1
<=>   innerUdelta = -------------------------
                    outerXdelta2-outerXdelta1

Nice! But what if dx2 = dx1? This of course means that the polygon is just one line, so du doesn't need any specific value; zero does the job very well.

Note! I find it hard to get good results using fixed point math because of inadequate precision (if you don't know what fixed point math is, forget about this note :-)

Environment mapping

Envmapped triangle

As I said in 'shading' part, the way demos do environment mapping is very simple. Take the X and Y components of your pseudo-normal vectors (perpendicular to verices), and use them to index your texture map!. Very simple indeed. Your formulae would be:
U = N.x*128 + 127
V = N.y*128 + 127
(assuming 256x256 texture maps).
Or in general
U = N.x * (width / 2) + (width / 2) - 1
V = N.y * (height / 2) + (height / 2) - 1

Texturing + Shading

Gouraud+Texture Envmapping+Texture

Using texturing and shading at the same time is quite straightforward to implement: the basic idea being that we just interpolate the values of both texture and shade and blend them in a suitable ratio (alpha-blending).