Hidden Surface Removal Algorithms

When drawing a 3D object, we need to draw only "visible" to viewer faces. There are a variety of algorithms to do that with different strong points.

Backface Culling

A simple way to remove hidden surfaces for convex bodies is to put away all "backfacing" polygons, as they are not seen by the viewer (see Fig.1). A polygon is "backfacing" if its normal N is facing away from the viewing direction V, i.e. if (NV) = cos(α) > 0.
convex
Interactive polyhedra applet. Drag the mouse to rotate objects. Look at Interactive polyhedra and Semiconductor microstructures for more examples.

For the non-perspective projection we can direct V along e.g. the Z axis, therefore
    (NV) = (Nez ) = cos(α) = Nz .
The value cos(α) = Nz is used also to determine brightness of the face in the "headlight" mode.

The backface culling algorithm has a HUGE speed advantage if we can use it since the test is cheap and we expect at least half the polygons will be discarded. If objects are not convex, one need to do more work. Usually it is performed in conjunction with a more complete hidden surface algorithm.

See also The Portal Technique for Real-time 3D Engines mainly useful for indoor engines.

Painter's Algorithm (Z-Sorting)

Draw polygons as an oil painter might: the farthest one first. This algorithm is used e.g. in James Gosling's "MoleculeViewer" Java 1.1 applet.
To draw stellated polyhedron the combinations of the backface culling and z-sorting is used in this applet. The non-convex body is broken into convex rays. Then these convex parts are z-sorted with respect of there center of mass positions and are ploted the farthest one first.

Interactive fractal polyhedra are obtained by recursive z-sorted translations.

Grid ordering

gridperspective We draw an array of objects (i, j) successively so, that zi, j grows when i or j are changed. From Fig.2 it follows, that in this case an object cannot be covered by a new more distant in z object.

Fig.2a shows, that unfortunately this trick doesn't work for the perspective projection, therefore IMHO one need use z-sorting in this case.

Grid ordering and backface culling are used in 3D Fractal Mountains applets.
rotations

Comments to the 3D controls. Rotations

Two rotations are used in all 3D applets. The first rotation on an angle φ around the Y axis and the second one on an angle θ around X axis
    R = M r ,
where the matrix M is
matrix

Zooming

It is evident, that for two successive zoomings the total scaling factor is
    Scale1+2 = Scale1 * Scale2 .
For Scalei = exp(c Δxi ) where c is a constant and Δxi is mouse displacement we get
    Scale1 * Scale2 = exp(c Δx1 ) * exp(c Δx2 ) = exp[c (Δx1 + Δx2 )] = Scale1+2 .
E-notes     free sources
updated 10 Oct 2001