I've been getting quite a few requests lately from people wanting to know some of the more basic techniques in graphics programming, so I'll start with perhaps one of the more common requests, Texture Mapping.
The basic idea of texture mapping is to map a texture, be it an image, or procedurally generated, onto the surface of a triangle/polygon, to make that surface look better without the need for geometric transformations. There are a number of techniques that fall under this matter. However, to limit the discussion, this will concentrate on linear (affine) mapping, as this forms the basis of a number of other techniques. Information on further types can be found on other websites/books, such as Mark Feldmans homepage (Win95GPE).
Firstly, to understand texture mapping, you must know how to fill a triangle. I'll limit the disussion to triangles, as they are both the easiest and fastest to map, and are easy to understand.
To fill a triangle, we basically need two steps:
Vertex 1
/ \
/ \
/ \
/*************\ Scan line Y
/ \
/ \
Vertex 2------------------------\ <-- Middle of triangle
______ \
______ \
______ \
______ \
______ \
____\ Vertex 3
So, to fill the triangle, we would have to first fill the set of scanlines
above the centre of the triangle:
For y = y1 to y2 do
FillScanLine(left[y], right[y], colour)
End For
And then from the middle line to vertex 3:
For y = y2 to y3 do
FillScanLine(left[y], right[y], colour)
End For
Now, you're probably wondering where the left[y] and right[y] come from. Well, they're not arrays (I just written it so to indicate for every scan line we will have a left and right X). They are interpolated as we scan along. The following code should illustrate what I mean (for top half of triangle):
TopX = v1.x
LeftX = TopX
RightX = TopX
DeltaLeftX = (MiddleLeftX - TopX) / (MiddleY - TopY)
DeltaRightX = (MiddleRightX - TopX) / (MiddleY - TopY)
or perhaps more efficiently:
Reciprocal = 1.0 / (MiddleY - TopY)
DeltaLeftX = (MiddleLeftX - TopX) * Reciprocal
DeltaRightX = (MiddleRightX - TopX) * Reciprocal
Then in your loop:
For y = y1 to y2 do
FillScanLine(LeftX, RightX, Colour)
LeftX += DeltaLeftX
RightX += DeltaRightX
End For
So, we interpolate the start and end of the edges, and then fill inbetween
them. Now, the same thing is done for the bottom half of the triangle.
But -- the key is, we have to recalculate *either* DeltaLeftX, *or*
DeltaRightX. We decide this by checking if the "point" on the middle of the
triangle points to the left or the right:
/ \ t = 0
/ \
/ \
/ \
/ \
/ \
Point ------------------------\ t = 0.5 (arbitrary figure: doesn't always
______ \ occur at 0.5!)
______ \
______ \
______ \
______ \
____\ t = 1
Here, the "Point" is on the left, so DeltaLeftX must be recalculated.
However, it could just have easily been on the right, in which case
DeltaRightX would need to be recalculated. So what must you do? You must
calculate the width of the middle scanline of the triangle, and depending
on its sign, you must set some kind of flag to either recalculate
either DeltaLeftX, or DeltaRightX. But how to calculate it? Simple. We need
to obtain a value 't' which indicates how far along the line on the *opposite*
side of the "Point" that the break occurs, as shown on the diagram. We then
need to obtain a value for X on that side. By then performing a subtraction,
we can calculate what side it is on:
TopX, TopY = co-ords of top and bottom vertices in triangle
BotX, BotY = co-ords of top and bottom vertices in triangle
MidX, MidY = co-ords of "Point" of the triangle
0 <= t <= 1 : Point where the opposite scan line is broken.
Dx = BotX - TopX
1
Dy = BotY - TopY
1
Dy = MidY - TopY (portion of opposite side in top half)
2
Dy
2
t = ---
Dy
1
t = (MidY - TopY) / (BotY - TopY)
So we now have a value telling us the point along the opposite edge.
If we recall that the equation of a ray is:
Point = Origin + t*Direction
We can use a 2D ray to calculate the X position
Point2.X = TopX + t*(BotX - TopX)
And now he have the right and left points on the centre scanline. However,
there is a problem: we do not yet know *which* is the right, and *which*
is the left. We must perform a subtraction to tell us this, or a comparison.
Width = Point2.X - MidX
If Width > 0 Then // Point2.x was > MidX, ie on the right side
SetFlag RecalculateDeltaLeftX
Else If Width < 0 // Point2.x was < MidX, ie point2.x was the left side
SetFlag RecalculateDeltaRightX
Else
Degenerate triangle; abort!
End If
You should now have the information you need to make a simplistic triangle
filler. However, its not optimal; it'll run slowly. I'll explain in the
next section how to get it running better.
Now, you may be wondering about all this flag setting, breaking the triangle into two halves and so on. Doesn't sound too efficient does it? Well, no, but thats not the real way it should be implemented. I've been explaining things in a purely *logical* fashion, not code wise. Its important to avoid discussing issues of code when explaining an algorithm. Now I'll deal with how it should really be implemented.
Firstly, the main point is that we do *NOT* have two seperate loops. We have *one* loop, and at the end, we decrement two heights: one for the left hand side, the other for the right. If one height runs out, ie <= 0, then we check to see if we have more work to do: if not, we then exit. The following pseudo code should help illustrate:
Loop {
Width = RightX - LeftX
If Width > 0 Then
FillScanLine(LeftX, RightX, Colour)
End If
Decrement LeftHeight
If LeftHeight <= 0 Then // out of "edge"
If Point Of Triangle On Left Side
Recalculate DeltaLeftX
Else
Return // hit bottom of triangle
End If
Else
LeftX += DeltaLeftX
End If
Decrement RightHeight
If RightHeight <= 0 Then // out of "edge"
If Point Of Triangle On Right Side
Recalculate DeltaRightX
Else
Return // hit bottom of triangle
End If
Else
RightX += DeltaRightX
End If
}
This will ensure we can code the filler as one loop, rather than the
pair of loops previously. Now, you will often *not* see this algorithm
implemented in this manner. Many coders prefer to use two tables and two
indices to work out whats going on with respect to the inner 'If' statement
above (If Point Of Triangle...). Its often coded as:
(Just the if statement)
Decrement LeftHeight
If LeftHeight <= 0 Then // out of "edge"
Decrement LeftIndex
If LeftIndex < 1 Then // dropped off bottom of table
Return
Else // find new delta (now function call)
If RecalculateDeltaLeftX(LeftIndex - 1, LeftIndex) <= 0 Then
Return
End If
End If
Else
LeftX += DeltaLeftX // simply interpolate
End If
Further to this, we need a similar statement for the right section of
triangle. Also, we will need a table and an index for the left and right
side of triangle respectively:
Vertex Pointer LeftArray[3] Vertex Pointer RightArray[3] Array Index LeftIndex Array Index RightIndexWe will also need to fill and set these tables and indices correctly, according to what side of the triangle the point is on. That decision is based on the width of the largest scan line. If you recall, a positive width meant that the "Point" of the triangle was on the left; negative width meant it was to the right. This gives rise to the following code:
(For the purposes of this pseudo-code, arrays are 1-based)
VertexPtr1, VertexPtr2, VertexPtr3 are 3 vertex pointers, sorted top->bottom,
used for quick lookup of data.
If Width > 0 Then // Point is to the left...
RightIndex = 2 // only one edge to the right
LeftIndex = 3 // two edges to the left
LeftArray[1] = VertexPtr1
LeftArray[2] = VertexPtr2
LeftArray[3] = VertexPtr3
RightArray[1] = VertexPtr1
RightArray[2] = VertexPtr3 // will only use 2 entries
(Calculate initial deltas, etc)
Else If Width < 0 Then // reverse situation
LeftIndex = 2 // only one edge to the left
RightIndex = 3 // two edges to the right
RightArray[1] = VertexPtr1
RightArray[2] = VertexPtr2
RightArray[3] = VertexPtr3
LeftArray[1] = VertexPtr1
LeftArray[2] = VertexPtr3
(Calculate initial deltas, etc)
Else
Degenerate triangle; reject
End If
That *almost* completes the basic skeleton of the code. One last detail:
The calculation of the initial deltas. You may think that could just be done
with a call to a function "CalculateLeftDelta" etc. However there is a
special case involved. Triangles with flat bottoms/tops. If this occurs,
you have to decrement the array index, calculate the delta *again*, and
check for zero. Two zeros in a row indicate a degenerate triangle. Code may
look like:
(For first branch of above if statement (Width > 0))
...
If CalculateRightDelta(RightIndex - 1, RightIndex) <= 0 Then
Return // error occured, major side of triangle is flat
End If
If CalculateLeftDelta(LeftIndex - 1, LeftIndex) <= 0 Then
Decrement LeftIndex
If CalculateLeftIndex(LeftIndex - 1, LeftIndex) <= 0 Then
Degenerate triangle; reject
Return
End If
End If
That should be enough information; you'll need to do the coding yourself,
but this should prove sufficient for coding a flat-colour filler. Obviously
you'll need to reverse the above code for the opposite case in the 'If'
statement.
Now the serious begins; how to map a texture onto that triangle. In all honesty, it really is pretty simple; however the maths involved can become a little involved.
Firstly, we need to interpolate u,v. U and V are our texture co-ordinates, such that:
1 <= u <= TextureWidth 1 <= v <= TextureHeightAssuming that a 1-based array is used. Interpolating U, V is done in the same fashion for the LeftX and RightX, except we only interpolate for *ONE* side of the triangle. The reason for this is that we only need a starting point; we move along the texture by adding DeltaU to U and DeltaV to V. We don't need to know a pair of [U,V], as we are not filling between them. Also for a triangle DeltaU and DeltaV are *constant*, which again simplifies our task. More on that later. Also we need to add code to our CalculateLeftDelta to calculate our deltas along the edge.
In summary, our task is to:
The calculation for the constant deltas is fairly simple: its linked to the one we used someway above to calculate the other x value for the centre scan line. The basic calculation is:
da = (a*(a3 - a1) + (a1 - a2)) / widthI used the value 'a' simply to emphasize that this calculation is not unique to texture co-ordinates: it can be used for other values, such as colour, specular colour, and so on (but please not angle!). What the calculation basically does is find the step between the values of 'a' for the widest scan line, then divide it, to give an interpolation delta. For texturing, we would write:
du = (u*(u3 - u1) + (u1 - u2)) / width dv = (v*(v3 - v1) + (v1 - v2)) / width Or if we wanted to be a little more stylish: Recip = 1.0 / width du = (u*(u3 - u1) + (u1 - u2)) * Recip dv = (v*(v3 - v1) + (v1 - v2)) * Recip Or if we really want to be clever: Recip = RecipTable[Width] du = (u*(u3 - u1) + (u1 - u2)) * Recip dv = (v*(v3 - v1) + (v1 - v2)) * RecipThese values du, dv will then be used for interpolation across the scan line.
Right now your brain is probably cooked with all of this. So, lets now put all this code together, to give us a framework for a texture mapper. I'll write in pseudo code, and then you can implement it in your favourite language. Good luck!
Vertex Pointer LeftArray[3]
Vertex Pointer RightArray[3]
Real DeltaLeftX, DeltaRightX, DeltaLeftU, DeltaLeft V
Real LeftX, RightX, LeftU, LeftV
Integer leftheight, rightheight
// This function calculates our deltas for interpolating along the left
// edge. On error, it returns zero. On success, it returns the height of the
// section, and updates the global variables accordingly
Integer Function CalculateLeftDelta(Integer index1, Integer index2)
Begin
Vertex Pointer Vertex1 = LeftArray[index1]
Vertex Pointer Vertex2 = LeftArray[index2]
Integer Height
Real recip
// Get height of this section. If its an illegal value, return 0
// On catching the value zero, the function will then adjust its
// variables, and attempt a recalculation
Height = Vertex2.y - Vertex1.y
If Height == 0 Then
Return 0
End If
// RecipTable holds values of 1.0 / x for a series of integers
// Size of table is not defined; you will decide that based on the
// size of your screen, as only values that are within those limits
// will be used
recip = RecipTable[Height]
DeltaLeftX = (Vertex2.x - Vertex1.x) * Recip
DeltaLeftU = (Vertex2.u - Vertex1.u) * Recip
DeltaLeftV = (Vertex2.v - Vertex1.v) * Recip
// Initial values; these will then be interpolated
LeftX = Vertex1.x
LeftU = Vertex1.u
LeftV = Vertex1.v
leftheight = Height
Return Height
End
// This function calculates our deltas for interpolating along the right
// edge. On error, it returns zero. On success, it returns the height of the
// section, and updates the global variables accordingly
Integer Function CalculateRightDelta(Integer index1, Integer index2)
Begin
Vertex Pointer Vertex1 = RightArray[index1]
Vertex Pointer Vertex2 = RightArray[index2]
Integer Height
Real recip
// Get height of this section. If its an illegal value, return 0
// On catching the value zero, the function will then adjust its
// variables, and attempt a recalculation
Height = Vertex2.y - Vertex1.y
If Height == 0 Then
Return 0
End If
recip = RecipTable[Height]
DeltaRightX = (Vertex2.x - Vertex1.x) * Recip
// Initial values; these will then be interpolated
RightX = Vertex1.x
RightHeight = Height
Return Height
End
// This is the main function for performing the texture mapping. It accepts
// an array of vertices, and a texture. It will then paint a textured
// triangle onto the screen.
Void Function TextureTriangle(Vertex Pointer vertarray[3], Texture texture)
Begin
Vertex Pointer vert1, vert2, vert3, verttemp
Integer TopY, MidY, BotY, cury
Integer height, widest, x, x1, x2, width
Integer leftindex, rightindex
Colour colour
Real t, deltau, deltav recip, curu, curv
// Get the pointers to the 3 vertices
vert1 = vertarray[1]
vert2 = vertarray[2]
vert3 = vertarray[3]
// Now sort them based on ascending Y
If vert1.y > vert2.y Then
Swap(vert1, vert2)
End If
If vert1.y > vert3.y Then
Swap(vert1, vert3)
End If
If vert2.y > vert3.y Then
Swap(vert2, vert3)
End If
// Calculate the value of t, described above, and the widest width
t = (MidY - TopY) / (BotY - TopY)
widest = (vert1.x + t*(vert3.x - vert1.x)) - vert2.x
If widest > 0 Then
rightindex = 2
leftindex = 3
LeftArray[1] = vert1
LeftArray[2] = vert2
LeftArray[3] = vert3
RightArray[1] = vert1
RightArray[2] = vert3
If CalculateRightDelta(rightindex - 1, rightindex) <= 0 Then
Return
End If
If CalculateLeftDelta(leftindex - 1, leftindex) <= 0 Then
Decrement leftindex
if(CalculateLeftDelta(leftindex - 1, leftindex) <= 0 Then
Return
End If
End If
Else If widest < 0 Then
leftindex = 2
rightindex = 3
RightArray[1] = vert1
RightArray[2] = vert2
RightArray[3] = vert3
LeftArray[1] = vert1
LeftArray[2] = vert3
If CalculateLeftDelta(leftindex - 1, leftindex) <= 0 Then
Return
End If
If CalculateRightDelta(rightindex - 1, rightindex) <= 0 Then
Decrement rightindex
if(CalculateRightDelta(rightindex - 1, rightindex) <= 0 Then
Return
End If
End If
Else
Return
End If
// Now we must calculate our constant texture deltas.
recip = RecipTable[widest]
deltau = (vert1.u + t*(vert3.u - vert1.u)) - vert2.u)*recip
deltav = (vert1.v + t*(vert3.v - vert1.v)) - vert2.v)*recip
cury = vert1.y
InfiniteLoop
Begin
x1 = LeftX
x2 = RightX
width = x2 - x1
If width > 0 Then
curu = LeftU
curv = LeftV
For x = x1 to x2 do
colour = Texture[curv][curv]
PutPixel(x, cury, colour)
curu += deltau
curv += deltav
End For
End If
cury++
Decrement LeftHeight
If LeftHeight <= 0 Then
Decrement LeftIndex
If LeftIndex < 1 Then
Return
Else
If CalculateLeftDelta(LeftIndex - 1, LeftIndex) <= 0 Then
Return
End If
End If
Else
LeftX += DeltaLeftX
LeftU += DeltaLeftU
LeftV += DeltaLeftV
End If
Decrement RightHeight
If RightHeight <= 0 Then
Decrement RightIndex
If RightIndex < 1 Then
Return
Else
If CalculateRightDelta(RightIndex - 1, RightIndex) <= 0 Then
Return
End If
End If
Else
RightX += DeltaRightX
End If
End
End