CS-460/560, Wk13C
Spring, 1998
R. Eckert

SIMPLE HIDDEN SURFACE REMOVAL (BACK-FACE CULLING)

If we are modeling a fairly complex object with polygons, the number of
polygons may be quite large. For a solid object, many of the polygons are
really not visible because they are facing away from the observer.
Although all of the polygons may be drawn on the screen, a less complex
and more realistic image will be produced if only the visible polygons
(those facing toward the observer) are drawn. The simple technique of
back-face culling is employed to determine whether a polygon is visible or
not from the view point.

To use back-face culling, we define one side of each polygon to be the
visible side. (That side, of course, will be the side facing outward from
the object.) In defining each polygon in the polygons array we
systematically number its vertices in counter-clockwise fashion as seen
from the outside of the object. In part A of the following figure, for
example, we see a triangle whose vertices have been numbered 0, 1, and 2.



Following our convention, the side of the triangle we can see as we look
down at the Figure is the visible side, since 0,1,2 are in counter-
clockwise order for us. (If we were to look from behind the paper to see
the invisible side of the triangle, points 0, 1, and 2 would be in
clockwise order.)

In part B of the above figure, we have placed the triangle in a plane
nearly perpendicular to the line of sight of a viewer V in such a way that
the visible side is facing away from the observer. It is convenient to
define the following two vectors: N, the outward normal to the triangle
and V0, the vector from the observer to vertex 0. In the configuration of
the figure, N and V0 are nearly parallel (V0.N = 1), and the visible side
of triangle 012 cannot be seen by the viewer. If we rotate the triangle
about side 01 by 90 degrees, we get part C of the above figure. Now N and
V0 are perpendicular, and the triangle is just about to become visible
(V0.N = 0). At all other points between these two orientations, V0.N is
positive, and the triangle is invisible to the viewer. Continuing the
rotation about side 01, the triangle becomes visible to the viewer, and
after 90 degrees more, as shown in part D of the figure, N and V0 are
antiparallel (V0.N = -1). The triangle is now facing directly toward the
viewer and is visible. At all orientations between that of part C and that
of part D, the triangle is visible and V0.N is negative. Evidently the
criterion for invisibility is: If V0.N is positive, triangle 012 is
invisible.

                 V0 . N > 0,  for invisibility.

In the following figure we see triangle 012 placed in an arbitrary
position relative to viewer V.



From the figure, the outward normal N is the vector (cross) product of the
vector from vertex 0 to vertex 1 (01) and the vector from vertex 0 to
vertex 2 (02).

                 N = 01 X 02

So our criterion for invisibility is

                 V0 . (01 X 02) > 0

But using the rule for vector addition, we see that vector 01 is the
difference between V1 and V0:

                 01 = V1 - V0

and 02 the difference between V2 and V0:

                 02 = V2 - V0

Substituting, we get

                 V0 . [(V1 - V0) X (V2 - V0)] > 0,  for invisibility.

Expanding this,

  V0 . (V1 X V2) - V0 . (V1 X V0) - V0 . (V0 X V2) + V0 . (V0 X V0) > 0

The last term is zero, since the cross product of any vector with itself
is zero. For each of the middle two terms, the quantity inside the
parentheses is a vector perpendicular to V0. Therefore, when the dot
product of either of these two vectors is taken with V0, the result is
zero, since the dot product of two mutually perpendicular vectors is
always zero. So the criterion for invisibility becomes:

                 V0 . (V1 X V2) > 0

If we are using a right-handed coordinate system, the triple product can
be expressed as the following determinant.

                        | X0   Y0   Z0 |
   V0 . (V1 X V2)   =   | X1   Y1   Z1 |  (right-handed coordinate system)
                        | X2   Y2   Z2 |

where (X0,Y0,Z0), (X1,Y1,Z1), and (X2,Y2,Z2) are the viewing coordinates
(xv,yv,zv) of vertices 0, 1, and 2 of the triangle. Since our viewing
coordinate system is left-handed, the sign of the determinant must be
reversed. So finally, the criterion for invisibility becomes:

               | X0   Y0   Z0 |
               | X1   Y1   Z1 |  <  0,  for invisibility.
               | X2   Y2   Z2 |

Although the above analysis has been done for a triangle, the result
applies to any planar polygon as long as we substitute the viewing
coordinates of three consecutive vertices of the polygon into the
determinant. A visibility function that calculates and returns the value
of the determinant (positive means visible, negative invisible) may be
used to determine whether the polygon should be displayed or not. The
function must read the xv,yv,zv coordinates of three consecutive vertices
of the polygon from the view-points array in order to perform its task.