Polyhedral models

For a 3D world, ${\cal W}= {\mathbb{R}}^3$, and the previous concepts can be nicely generalized from the 2D case by replacing polygons with polyhedra and replacing half-plane primitives with half-space primitives. A boundary representation can be defined in terms of three features: vertices, edges, and faces. Every face is a ``flat'' polygon embedded in ${\mathbb{R}}^3$. Every edge forms a boundary between two faces. Every vertex forms a boundary between three or more edges.

Several data structures have been proposed that allow one to conveniently ``walk'' around the polyhedral features. For example, the doubly connected edge list [264] data structure contains three types of records: faces, half-edges, and vertices. Intuitively, a half-edge is a directed edge. Each vertex record holds the point coordinates and a pointer to an arbitrary half-edge that touches the vertex. Each face record contains a pointer to an arbitrary half-edge on its boundary. Each face is bounded by a circular list of half-edges. There is a pair of directed half-edge records for each edge of the polyhedon. Each half-edge is shown as an arrow in Figure 3.3b. Each half-edge record contains pointers to five other records: 1) the vertex from which the half-edge originates; 2) the ``twin'' half-edge, which bounds the neighboring face, and has the opposite direction; 3) the face that is bounded by the half-edge; 4) the next element in the circular list of edges that bound the face; and 5) the previous element in the circular list of edges that bound the face. Once all of these records have been defined, one can conveniently traverse the structure of the polyhedron.

Now consider a solid representation of a polyhedron. Suppose that ${\cal O}$ is a convex polyhedron, as shown in Figure 3.3. A solid representation can be constructed from the vertices. Each face of ${\cal O}$ has at least three vertices along its boundary. Assuming these vertices are not collinear, an equation of the plane that passes through them can be determined of the form

$$a x + b y + c z + d = 0,$$ (3.7)

in which $a,b,c,d \in {\mathbb{R}}$ are constants.

Figure 3.3: (a) A polyhedron can be described in terms of faces, edges, and vertices. (b) The edges of each face can be stored in a circular list that is traversed in counterclockwise order with respect to the outward normal vector of the face.

Once again, $f$ can be constructed, except now $f: {\mathbb{R}}^3 \rightarrow {\mathbb{R}}$ and

$$f(x,y,z) = a x + b y + c z + d .$$ (3.8)

Let $m$ be the number of faces. For each face of ${\cal O}$, a half-space $H_i$ is defined as a subset of ${\cal W}$:

$$H_i = \{ (x,y,z) \in {\cal W}\;\vert\; f_i(x,y,z) \leq 0 \} .$$ (3.9)

It is important to choose $f_i$ so that it takes on negative values inside of the polyhedron. In the case of a polygonal model, it was possible to consistently define $f_i$ by proceeding in counterclockwise order around the boundary. In the case of a polyhedron, the half-edge data structure can be used to obtain for each face the list of edges that form its boundary in counterclockwise order. Figure 3.3b shows the edge ordering for each face. For every edge, the arrows point in opposite directions, as required by the half-edge data structure. The equation for each face can be consistently determined as follows. Choose three consecutive vertices, $p_1$, $p_2$, $p_3$ (they must not be collinear) in counterclockwise order on the boundary of the face. Let $v_{12}$ denote the vector from $p_1$ to $p_2$, and let $v_{23}$ denote the vector from $p_2$ to $p_3$. The cross product $v = v_{12} \times v_{23}$ always yields a vector that points out of the polyhedron and is normal to the face. Recall that the vector $[a \;\; b \;\; c]$ is parallel to the normal to the plane. If its components are chosen as $a = v[1]$, $b = v[2]$, and $c = v[3]$, then $f(x,y,z) \leq 0$ for all points in the half-space that contains the polyhedron.

As in the case of a polygonal model, a convex polyhedron can be defined as the intersection of a finite number of half-spaces, one for each face. A nonconvex polyhedron can be defined as the union of a finite number of convex polyhedra. The predicate $\phi (x,y,z)$ can be defined in a similar manner, in this case yielding TRUE if $(x,y,z) \in {\cal O}$, and FALSE otherwise.