Copyright Derek O'Reilly, Dundalk Institute of Technology (DkIT), Dundalk, Co. Louth, Ireland.
In order to render an image we need to be able find the colour at any surface point that is struck by a light ray. If the surface is only one colour, then this colour is used as the colour for all points on the surface. However, in the real world most surfaces are multicoloured. For example, a globe will have at least green land and blue sea, where each continent and larger island will be clearly recognisable.
In order to represent any detailed and specific multicoloured surface we use texture maps. A texture map is a two dimensional representation of a surface colouring. If we 'roll' the surface out until it becomes flat, we get its texture map.
A texture map can be mapped onto any 3D surface point coordinate (or in the case of a polygon, a 2D surface point coordinate).
A separate texture mapping algorithm will have to be developed for each surface type (such as spheres, fractals, and three or four vertex defined polygons) that is modelled.
There are two types of texture mapping that can be applied to polygons:
In parameterised texture mapping the whole of the texture map is mapped onto the surface of the polygon. The surface of the texture map is stretched so as to fit onto the polygon. This is shown in the diagram below.
In explicit texture mapping only a part of the texture map is mapped onto the surface of the polygon. Each vertex of the polygon is explicitly assigned a coordinate in the texture map.
Explicit texture mapping is particularly useful if we are using polygons to approximate another surface. For example, if we are using polygons to approximate a globe, then we can map the globe's texture map (i.e. the map of the world) so that different parts of the texture map are mapped onto the various polygons that are being used to approximate the globe. Explicit texture mapping is shown in the diagram below.
We shall now develop a texture mapping algorithm that fits into the scan line hidden surface and rendering algorithm.
The same scanline polygon texture mapping algorithm will work for both paramiterised and explicit texture mapping.
Each vertex of a polygon is assigned an x,y coordinate from the texture map.
For paramiterised texture mapping the four vertices of the polygon are assigned the four corner coordinates of the texture map.
For explicit texture mapping the four vertices are assigned coordinates within the texture map that give the desired texture map.
Once each of the four vertices is assigned a texture map coordinate, the same algorithm will work for both paramiterised and explicit texture mapping.
Given that we have assigned texture map coordinates to the two vertices that define a polygon edge, we can linearly interpolate between the two vertices' texture map coordinates to give the edge's other texture map coordinates.
If vertex V_{1} is assigned texture map coordinate T_{1} and vertex V_{2} is assigned T_{2}, then the number of interpolation steps that we need equals the number of scan lines between the two vertices (i.e. V_{2}yV_{1}y).
We need to map the length of the texture map edge evenly onto the V_{2}yV_{1}y steps. The length of the texture map edge is equal to the distance between its two defining points (T_{1} and T_{2}). We calculate the texture map edge's x and the y lengths independently. The length of the texture map edge in the x direction is T_{2}xT_{1}x and the length of the texture map in the y direction is T_{2}yT_{1}y.
The linear interpolation of the texture map's x coordinate as we move down one scan line is:
T_{x+1} 
= T_{x} + (T_{2}xT_{1}x) / (V_{2}yV_{1}y) 
= T_{x} + edgeStepSizeX 
where:
· T_{x} is the texture map x coordinate that maps onto the polygon's edge at the current scanline.
· T_{x+1} is the texture map x coordinate that maps onto the polygon's edge at the NEXT scanline.
· V_{1}y and V_{2}y are the polygon edge's two vertex y coordinates.
· T_{1}x and T_{2}x are the two texture map x coordinates that map onto V_{1}x and V_{2}x respectively.
NOTE: edgeStepSizeX need only be calculated once for a given polygon edge as the edge is being added to the AET.
Using the above formula, we can calculate the next edge texture map x coordinate given that we know the current edge texture map x coordinate.
We keep each polygon's edge texture map coordinate in the AET and we add the edgeStepSizeX to it each time we move down a scanline.
Similarly
T_{y1} 
= T_{y} + (T_{2}yT_{1}y) / (V_{2}yV_{1}y) 
= T_{y} + edgeStepSizeY 
As a result of the linear interpolation along the edge of the polygon we always know the texture map's x and y coordinates for the two polygon edges that are on the current scanline.
We also know (from the AET) the two polygon edge x coordinates. These two x coordinates are used to calculate the distance between the two polygon edges. The distance between the two edges represents the number of pixels that must be coloured in. This is shown in the diagram below.
We can interpolate between the two edges texture map coordinates to fill in the pixels on the scan line.
The formula used to calculate the successive texture map x coordinates as we move across the scan line is:
T_{x+1} 
= T_{x} + (T_{2}xT_{1}x) / (E_{2}xE_{1}x) 
= T_{x} + scanlineStepSizeX 
where:
· T_{x} is the current texture map coordinate (which maps onto the current x coordinate along the scanline).
· T_{x+1} is the next texture map coordinate (which will be mapped onto the next x coordinate along the scanline).
· E_{1}x and E_{2}x are the two polygon edge x coordinates (taken from the AET).
· T_{1}x and T_{2}x are the two texture map x coordinates that map onto E_{1}x and E_{2}x respectively. These two values are got from the linear interpolation along the polygon's respective edges (as described in the last section).
NOTE: scanlineStepSizeX need only be calculated once for a given polygon and it can then be used continually as a scanline progresses across the polygon.
Similarly
T_{y+1} 
= T_{y} + (T_{2}yT_{1}y) / (E_{2}xE_{1}x) 
= T_{y} + scanlineStepSizeY 
In the above diagram, we can assume that the four vertices of the polygon were assigned to the four corner points of a texture map of width 60 and height 20:
The polygon vertices are assigned to the texture map corner coordinates as follows:
V_{1} is assigned 
T_{1}(0,0) 
V_{2} 
T_{2}(0,20) 
V_{3} 
T_{3}(60,20) 
V_{4} 
T_{4}(60,0) 
Q1) For each of the four edges, by how much does the texture map's coordinate change at each new scanline? (i.e. find edgeStepSizeX and edgeStepSizeY for each of the four edges).
Q2) What coordinates of the texture map will be displayed along the polygon edge V_{4}V_{3}?
Q3) What coordinates of the texture map will be displayed on scanline y=15?
ANSWER Q1)
The equivalent texture map coordinate along any edge of the polygon can be got by linear interpolation between the two vertex's equivalent texture map coordinates.
The edge V_{4}V_{3} maps across the top of the texture map from the coordinates 60,0 to 60,20
edgeStepSizeX 
= (T_{3}xT_{4}x) / (V_{3}yV_{4}y) 
= (6060) / (2010) 

= 0 
edgeStepSizeY 
= (T_{3}yT_{4}y) / (V_{3}yV_{4}y) 
= (200) / (2010) 

= 2 
The x and y stepSize for each of the other three edges are calculated similarly:
Edge V_{4}V_{1}
edgeStepSizeX 
= (0  60) / (1310) 
= 20 
edgeStepSizeY 
= (00) / (1310) 
= 0 
Edge V_{1}V_{2}
edgeStepSizeX 
= (00) / (3013) 
= 0 
edgeStepSizeY 
= (200) / (3013) 
= 1.17647 
Edge V_{3}V_{2}
edgeStepSizeX 
= (060) / (3020) 
= 6 
edgeStepSizeY 
= (3030) / (3020) 
= 0 
ANSWER Q2) What coordinates of the texture map will be displayed along the polygon edge V_{4}V_{3}?
We use the linear interpolation along a polygon's edge formula to calculate the texture map's coordinates at each position along the polygon's edge. The formula is:
T_{x+1} = T_{x} + edgeStepSizeX
T_{y+1} = T_{y} + edgeStepSizeY
We know:
· from "Q1)" that:
edgeStepSizeX = 0
edgeStepSizeY = 2
· V_{4} was assigned texture map coordinate T_{4}(60,0).
This means:
· the first T_{x} value will be 60;
· the first T_{y} value will be 0.
The table below shows the texture map coordinates that map onto the polygon edge V_{4}V_{3}.
Scanline 
Texture Map Coordinates 

Y 
X 
Y 
10 
60 
0 
11 
60 
2 
12 
60 
4 
13 
60 
6 
14 
60 
8 
15 
60 
10 
16 
60 
12 
17 
60 
15 
18 
60 
16 
19 
60 
18 
20 
60 
20 
ANSWER Q3) What coordinates of the texture map will be displayed on scanline y=15?
Scanline y=15 is shown in the above diagram. It cuts through edges V_{4}V_{3} and V_{1}V_{2}.
In a program, the two polygon edge x coordinates and the two texture map edge coordinates that they map onto would be contained in the AET.
They are:
E_{43}x 
= 11 
Rounded from 10.5 
E_{12}x 
= 26 
Rounded from 26.17647 
T_{43}x 
= 60 

T_{43}y 
= 10 

T_{12}x 
= 0 

T_{12}y 
= 2 
Rounded from 2.3529 
where:
· E_{43}x is the x coordinate along the edge V_{4}V_{3} that lies on the scanline y=15.
· E_{12}x is the x coordinate along the edge V_{1}V_{2} that lies on the scanline y=15.
E_{43}x = 11 and E_{12}x = 26 means that between the two polygon edges, the scanline y=15 passes through the pixels whose x coordinates are 11 to 26 inclusive.
All the pixels between the two polygon edges on the scanline y=15 will have the same y coordinate (y=15).
Calculation of the scanline step size
ScanlineStepSizeX 
= (T_{12}xT_{43}x) / (E_{12}xE_{43}x) 
= (0  60) / (26  11) 

= 60 / 15 

= 4 
scanlineStepSizeY 
= (T_{12}yT_{43}y) / (E_{12}xE_{43}x) 
= (2  10) / (2611) 

= 8 / 15 

= 0.53333 
The table below shows the texture map coordinates that map onto the polygon between the edges V_{4}V_{3} and V_{1}V_{2} along the scanline y=15.
Scanline 
Texture Map Coordinates 

X 
X 
Y (Actual) 
Y (Rounded) 
11 
60 
10.00 
10 
12 
56 
9.466 
9 
13 
52 
8.933 
9 
14 
48 
8.4 
8 
15 
44 
7.866 
8 
16 
40 
7.3333 
7 
17 
36 
6.8 
7 
18 
32 
6.266 
6 
19 
28 
5.7 
6 
20 
24 
5.2 
5 
21 
20 
4.666 
5 
22 
16 
4.133 
4 
23 
12 
3.6 
4 
24 
8 
3.066 
3 
25 
4 
2.533 
3 
26 
0 
2 
2 
We can apply the algorithm described above to perform explicit texture mapping for polygons with ANY number of edges.
However, for paramiterised texture mapping, we need to customise the algorithm depending on the number of edges the polygon contains.
A simple solution for performing paramiterised texture mapping on a three edge polygon is to pass to the texture mapping algorithm a four edged version of the polygon. This is done by assigning an extra vertex that coincides with one of the polygon's existing vertices. The fourth edge will be zero in length.
The vertex chosen to be doubled up will affect how the texture map maps onto the polygon.
In the diagram below, the polygon vertex that maps onto the texture map's top left corner has been doubled up.
In the diagram below, the polygon vertex that maps onto the texture map's bottom right corner has been doubled up.
Copyright Derek O' Reilly, Dundalk Institute of Technology (DkIT), Dundalk, Co. Louth, Ireland.