4. Hidden-surface removal for convex polyhedra

Let us consider a convex polyhedron $C$ and a projection of it on some viewplane.

If the projection is perspective, let $V_0$ be the viewpoint. In this case, we assume of course that $V_0$ is not a point of $C$.

If the projection is parallel (e.g., orthographic), let v be a vector giving the direction of the viewpoint. In the past, we have considered v and $-$v to be equivalent; now, though, we should not, because the question of which faces are hidden depends on the direction from which we are looking. See Figure .

Figure: Viewing setups

Observation. Because $C$ is convex, each face is (a) entirely visible, (b) entirely hidden, or (c) seen edgewise.

Here (c) means that the plane of the face contains $V_0$ or is parallel to v.

For a given face $P_0 P_1 \dots P_{k-1}$, here is a method for computing which among (a), (b), (c) holds. Let's assume that no three of these vertices are in a straight line and that no other vertices of the polyhedron are in the plane of this face.

Step 0. If the projection is perspective, let v $=$ $V_0 - P_0$. Thus whether the projection is perspective or parallel, we have a ``line-of-sight'' vector v that, if drawn at $P_0$, points away from the polyhedron.

Step 1. Find a normal N to the face. One way is simply to let N $=$ $(P_0 - P_1) \times (P_2 - P_1)$.

Step 2. Choose another vertex $Q$ of the polyhedron, not on the given face, and let w $=$ $Q - P_0$, a vector that definitely points inward. Check the sign of the dot product w$\cdot$   N. If w$\cdot$   N$> 0$, then N is an inward normal; define a new normal N$_{out}$ $=$ $-$N. If w$\cdot$   N$< 0$, then N is an outward normal already; let N$_{out}$ $=$ N.

Step 3. Check the dot product v$\cdot$   N$_{out}$.

(a) If v$\cdot$   N$_{out} > 0$, then the face is visible.

(b) If v$\cdot$   N$_{out} < 0$, then the face is hidden.

(c) If v$\cdot$   N$_{out} = 0$, then the face is seen edgewise.

Figure: Testing a face for visibility

Observe that the viewplane itself is irrelevant for this method (Figure ).

To make a picture of a convex polyhedron with hidden faces removed, simply plot the image of each visible face. If you have a pen plotter, for example, just compute the images of the vertices of visible faces and plot line segments between them corresponding to the edges of the those faces.

Remark. If three consecutive vertices of a face are allowed to be collinear, then Step 1 may fail, because the cross product may be the zero vector. In this case, either try different choices of three vertices until three are found that are not collinear, or else let $\overline P$ be the average of all the vertices of the face and let N $=$ $(P_0 - \overline P) \times (P_1 - \overline P)$. ( $\overline P$ will automatically be in the interior of the face.) Similarly, if two different faces are allowed to lie in one plane, then in Step 2, $Q$ may be in the plane of the given face and not tell you anything about N; in this case, instead let $Q$ be the average of all the vertices of the polyhedron (a point definitely not on the given face).