CS 248 Marc Levoy Introduction to Computer Graphics Spring, 1995 Stanford University Back-face culling for project #3 First, I need to correct an error in a previous lecture. In the transformation lectures, I stated that the matrix Q, which equals M inverse transpose and is used to transform normals, cannot be found if M contains a perspective transformation, because that transformation is not invertible. This is true of the perspective matrix derived in your textbook (eqn. 6.3, p. 254). It is not true, however, of the perspective matrix derived in class and stated but not derived in your textbook (eqn 6.48, p. 275). It is also not true of the SGI perspective matrix. The latter two matrices *are* invertible. With this correction said, there are (at least) three ways to perform back-face culling for project #3. First, some definitions and symbols: (I'll be handing out several sets of notes like this to help you along with project #4, and all of them will follow this symbology.) Rx(thetax) = X-rotation matrix Ry(thetay) = Y-rotation matrix Rz(thetaz) = Z-rotation matrix T(dx,dy,dz) = translation matrix persp = transpose of SGI persp matrix from Haeberli & Akeley M1 o M2 = composition of any matrices M1 and M2 (implemented by premultiplication, i.e. M2 M1) M^ = M-hat for any matrix M M(-1) = inverse of M for any matrix M P = a point in world space E = world space coordinates of the viewer eyepoint X . Y = dot product of any two vectors X and Y world space = the coordinate system given to you by Composer eye space = world space rotated and translated for viewing, but w/o any perspective mapping screen space = world space rotated, translated, and perspective mapped, a.k.a. clipping space In the pseudocode that follows, I assume that all coordinates are 4-vectors and that all matrices are 4x4. In the section entitled "Reducing the dimensionality", I suggest how to improve on this. So here are three ways to perform back-face culling: 1. In screen space using a matrix Q as follows: For each view of the scene: Compute the compound viewing transformation matrix with perspective: M <-- Rx(thetax) o Ry(thetay) o Rz(thetaz) o T(Tx,Ty,Tz-d1) o persp o S(1,1,-1/2) o T(0,0,-1/2) Compute Q as derived in class: Q = M(-1) transpose For each triangle in the scene: Transform the world triangle normal vector N by Q to put it into screen space, then dot this with the viewing vector (a vector pointing from the triangle to the viewer): (Q N) . ([0 0 1 0] transpose) where [0 0 1 0] transpose is the viewing vector in screen space, looking from the scene towards the origin along the positive Z-axis If the sign of this dot product is positive, the polygon is front-facing, else it is back-facing and should be discarded. Note that Composer gives you per-vertex normals, not triangle normals. The normals for the three vertices of a triangle may not agree; this sounds strange, but you'll see next week that this is useful for shading. Therefore, you should compute your own normal for each triangle, being careful with its orientation. The problem with this formulation is that it requires inverting M, which is possible (as stated in my correction at top), but is nevertheless a lengthy calculation. Fortunately, there is an alternative: 2. In eye space, as follows: For each view of the scene: Compute a compound viewing matrix but without the perspective: M^ <-- Rx(thetax) o Ry(thetay) o Rz(thetaz) o T(Tx,Ty,Tz-d1) Compute the world space location of the viewer: E <-- M^(-1) ([0 0 0 1] transpose) where [0 0 0 1] transpose is the eye space location of the viewer, at the origin. (Note the difference between a viewer location and a viewing vector.) For each triangle in the scene: Compute the vector from any vertex P of the triangle to E and dot this vector with the world space normal vector N for the triangle, i.e.: (E - P) . N If the sign of this dot product is positive, the polygon is front-facing, else it is back-facing and should be discarded. 3. In screen space without a matrix Q, as follows: For each view of the scene: Compute the compound viewing transformation matrix M with perspective as described above under method 1. For each triangle in the scene: 1. Transform the triangle to screen space using matrix M. 2. Compute its normal in screen space as a cross product of the transformed edges as shown in class. For the purposes of culling, you don't need to normalize the length of this vector. 3. Dot this normal with the screen space viewing vector [0 0 1 0] transpose as defined above under method 1. If the sign of this dot product is positive, the polygon is front-facing, else it is back-facing and should be discarded. I suggest method #2 or #3. Method #2 requires computing an inverse, but computing the inverse of M^ is much easier than computing the inverse of M. Specifically, you can simply concatenate together the inverse of each constituent transformation, concatenating them in the reverse of the usual order. The inverses of of the constituent rotations and translations are trivial; we went over them in class. Method #3 requires computing a cross product, but is conceptually simple and very efficient. Note that in order to compute the dot product with this particular vector, you only need to compute the Z-component of the normal. Note on reducing the dimensionality of the matrices and vectors: If you study where zeros fall in matrices M^ and Q, you will realize that M^ can be a 3x4, Q^ can be a 3x3, and that N and the eye location and viewing vector can be 3-vectors.