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.