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.