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.