Introduction
Texture mapping is the process of mapping a 2D image, pattern or 'texture' onto a polygon or the surface of a 3D object. Using this process, you can 'dress' a 'naked' 3D object with textures, making this 3D object look like a piece of wood, stone, glass, etc. In this session, we will limit ourselves to mapping a simple bitmap (the texture) onto a trapezoid. This is an important operation in almost all 3D applications.
Before texture mapping a polygon, we will start by implementing polygon scan-conversion. The goal of scan-conversion is simply to determine which pixels should be coloured to fill a polygon. This is usually done by means of a scan line algorithm, hence the name. Scan conversion is a specific case of texture mapping since it simply involves mapping a texture that consists of a single color onto the polygon.
You can use the following skeleton code for this exercise session. You can use this bitmap as a test-texture.
Exercises
Exercise 1: Triangle Scan-conversion
The goal of this exercise is to colour a triangle defined by three vertices v0, v1 and v2. Assume that v0, v1 and v2 are ordered according to increasing y-coordinates (i.e. v0 defines the top vertex, v2 the bottom vertex). The algorithm fills the triangle by drawing an imaginary horizontal line across the screen and plotting all pixels on the line that intersect the triangle. The algorithm fills the entire triangle by moving this horizontal 'scan line' one pixel down at each step.
The only difficulty in this algorithm is finding the 2 intersection points between the scan line and the triangle. Determining these points by calculating at each step the intersection between the scan line and each of the triangle's edges would be inefficient. A more efficient algorithm consists of using the DDA technique we learned during the first exercise session. Start from a vertex and trace the edges of the triangle by drawing a line from that vertex to the other vertices.
In most cases, you will need to "switch directions" at v1 while tracing one of the edges of the triangle. To summarise, implement your scan-line algorithm as follows: using a horizontal scan-line, descend from v0 up to v1 and colour each pixel in between the intersection points with the long edge and the first short edge. Subsequently, descend from v1 up to v2, this time colouring all pixels in between the long edge and the second short edge.
Make sure that your algorithm works for all cases: triangles where a.y == b.y, where b.y == c.y, where v2 lies to the left of v1 and where v2 lies to the right of v1.
Exercise 2: Resizing a Bitmap
Before mapping a bitmap onto a trapezoid, consider the special case of mapping it onto a rectangle. Mapping a bitmap (itself a rectangle) onto another rectangle can be seen as resizing the bitmap. Your resize algorithm takes as its arguments the bitmap and the two opposite corners of the target rectangle in which it needs to be mapped. Loop over your target rectangle and for each position (i,j), try to determine which pixel to select from your original bitmap. When looping over the rectangle, make use of the DDA technique we have seen in the first session!
Exercise 3: Wolfenstein 3D Texture mapping
In Wolfenstein 3D, all walls are trapezoids. This means that at least two sides of each wall are always parallel. Loop over the target trapezoid and try to determine based on the position (i,j) in the trapezoid which pixel to select from your original bitmap. Hint: use a vertical scan-line that sweeps from the left to the right. Then interpolate/extrapolate the pixels from the bitmap onto the scan-line.
Exercise 4 (Optional): Quake Texture mapping
Try to develop an algorithm to texture-map a bitmap into an arbitrary 4-sided polygon. Hint: you can decompose your polygon into trapezoids and then apply your algorithm from exercise 3.
