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).