CS 248 Marc Levoy Introduction to Computer Graphics Spring, 1995 Stanford University Texture mapping computations for project #4 1. The texture mapping pipeline (a reiteration of the June 6 lecture) Here is a summary of the pipeline presented in Heckbert's MS thesis (handout #14). You do not need to implement all of this, so don't panic. In sections 3 and 4 of this handout, I present a streamlined pipeline that is suitable for your project. I use Heckbert's variable names throughout, but I retain our column vector notation; take care when comparing this handout to the online culling and shading tutorials and to the textbook. Definitions and symbols: [a b] [c d] = a 2x2 matrix (the best I can do in ASCII) [u v 1]T = [u v 1] transpose Heckbert's texture mapping pipeline, which is restricted to rendering textures mapped onto planar surfaces, is represented by a compound 3x3 matrix Mts that maps 2D texture coordinates [u v]T = [u v q]T, q=1, to 2D screen space coordinates [x y]T = [x' y' w]T. This matrix is: Mts = Mdropz Mws Mow Mto Maddz (Mts is a 3x3 matrix) where: Maddz = [1 0 0] [0 1 0] [0 0 0] [0 0 1] (4x3 matrix) Mto = parameterization of triangle (4x4 matrix) Mow = modeling transformation (4x4 matrix) Mws = viewing transformation (4x4 matrix) Mdropz = [1 0 0 0] [0 1 0 0] [0 0 0 1] (3x4 matrix) Here is a detailed description of each constituent matrix: Maddz = a 4x3 matrix that converts 2D texture coordinates [u v 1]T to 3D texture coordinates [u v 0 1]T by adding a depth = 0. Mto = a 4x4 matrix that places a texture on a planar surface by mapping 3D texture coordinates [u v 0 1]T to 3D object space coordinates [xo yo zo wo]T. This process is called parameterization of the surface. For a polygon defined to lie (before application of the modeling transformation) in the (xo,yo)-plane with one of its vertices at the origin, the matrix typically won't contain translations or rotations. On the other hand, since textures are typically hundreds of pixels across while triangle coordinates typically range over much smaller numbers, the matrix will almost surely include an (xo,yo)-scaling. Since most parameterizations are affine, the 4th row of Mto will typically contain [0 0 0 1]. Although you don't need to explicitly derive a matrix Mto for your project (see section 4 for what you should implement), you need to think about how to parameterize your surface. Mow = a 4x4 matrix that places a polygon in the scene by mapping 3D object space coordinates [xo yo zo wo]T to 3D world space coordinates [xw yw zw ww]T. (That's w sub w, not w squared.) This process is called modeling. For affine modeling transformations (the typical case), the 4th row of Mow will likely contain [0 0 0 1]. You don't have a modeling transformation matrix in your project because Composer traverses the modeling hierarchy for you, outputting all triangle vertices in world space coordinates. Mws = a 4x4 viewing matrix, typically including perspective, which maps 3D world space coordinates [xw yw zw ww]T to 3D screen space coordinates [x' y' z' w]T. This matrix is equivalent to the composite viewing transformation matrix in your project (matrix M in the culling and shading tutorials). (I called these coordinates [X Y Z W]T in the perspective lectures, in keeping with the textbook's notation.) Mdropz = a 3x4 matrix that drops depth from 3D screen space coordinates [x' y' z' w]T to yield 2D screen space coordinates [x' y' w]T. This is sometimes called clipping space. After clipping, homogenization produces pixel coordinates [x'/w y'/w]T = [x y]T. For simplicity, I omit any conversion to device (e.g. canvas) coordinates from this discussion. 2. Incremental image order texture mapping To incorporate texture mapping into the rasterization pipeline you are implementing in your project, you need to compute for each pixel in a triangle the corresponding position in the texture. This process is variously called image-order texture mapping, reverse texture mapping, or (in Heckbert) screen order scanning. If done in a naive fashion, it requires inverting the compound 3x3 matrix Mts defined above. Since Mts contains Mto and Mow, both of which are polygon-specific, this matrix inversion must be performed for each polygon. Its result is a 3x3 matrix Mst which takes 2D screen space coordinates [x y]T = [x' y' w]T, w=1, to 2D texture coordinates [u v]T = [u' v' q]T. To paraphrase Heckbert (p. 26), the procedure is: For each view of the scene: For each textured triangle: Compute Mts as described above For each pixel in triangle (using your scan converter): [u'' v'' q'']T <- [u'' v'' q'']T + [duq dvq dq]T [u v]T <- [u''/q'' v''/q'']T where [duq dvq dq]T = [Adx+Bdy+C Ddx+Edy+F Gdx+Hdy+I]T and A,B,C,D,E,F,G,H,I are as in eqn. 2.2 of Heckbert (p. 19). The calculation of A-I essentially inverts Mts to give Mst. 3. An important simplification We know that the key to perspective projection lies in dividing x and y by depth. We also know that this division by depth is implemented in the matrix formulation of perspective by setting the homogeneous coordinate equal to the depth. This is implemented in equation 6.48 on page 275 of your textbook by the -1 in the 4th row of the matrix. Since the effect of matrix Mst is to reverse the perspective mapping contained in matrix Mts, then a simple inverse relation ought to exist between the depth encoded in the w coordinate in [x' y' w]T and the q coordinate in [u' v' q]T. There is a simple relation (which I won't bother deriving here): q = 1/w !! This simple relation leads to a significant simplification of the texture mapping calculations. This simplification is not described in either the textbook or in Heckbert's chapter, but Heckbert uses it in a polygon scan converter published in Graphics Gems I, pp. 667-680. (If you don't know about the Graphics Gems series, it is a great source for oft-used simplifications, approximations, and hacks. There are four books so far in the series, edited by Andrew Glassner, James Arvo, David Kirk, and Paul Heckbert himself. The newest Gems also comes with machine-readable code for the algorithms in Gems I-IV. These books make an excellent addition to any graphics library.) 4. Implementing the simplified texture mapping pipeline You can take advantage of this simplification as follows. For each vertex in each triangle, store a pair of texture coordinates u and v. For lone triangles, the u and v you choose for each vertex establishes the texture space -> object space mapping. It thus replaces the matrix Mto. For meshes, how you establish this mapping depends on how you generate your mesh and on what sort of mapping you would like to see between your texture and the curved surface approximated by the mesh. Then, instead of using the algorithm outlined in sections 1 and 2 above, which requires building a compound mapping Mts for each triangle and inverting it to yield Mst, you should do the following: For each triangle in the scene: For each vertex in the triangle: Transform its world space coordinates by the compound viewing matrix M (see online shading tutorial) to produce screen space coordinates [x' y' z' w']T (using Heckbert's notation). Clip to the viewing frustum. If outside frustum, discard triangle Divide by w for use in your scan converter: x <-- x'/w y <-- y'/w z <-- z'/w (You have already implemented these last three steps in your project #3. I am simply restating them in Heckbert's notation.) Also divide the (untransformed) texture coordinates by w: u' <-- u/w v' <-- v/w Finally, create a homogeneous texture coordinate equal to 1/w: q <-- 1/w (By dividing u and v by w, texture coordinates undergo perspective distortion. This allows us to interpolate them in perspective. By setting q to 1/w, the later division of u'' and v'' by q'' undoes the perspective, giving us coordinates in texture space.) For each pixel in the triangle (using your scan converter): Interpolate u'', v'', and q'' from the u' 's, v' 's, and q 's at the vertices (rather than using Mst as in the expensive method): u'' <-- u'' + du v'' <-- v'' + dv q'' <-- q'' + dq Homogenize: u''' <-- u''/q'' v''' <-- v''/q'' Access the nearest texture sample at floor([u''' v''']T + 0.5).