Polyhedral models

For a 3D world, , 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 . 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 is a convex polyhedron, as shown in Figure 3.3. A solid representation can be constructed from the vertices. Each face of 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

(3.7) |

in which are constants.

Once again, can be constructed, except now and

(3.8) |

Let be the number of faces. For each face of , a

(3.9) |

It is important to choose so that it takes on negative values inside of the polyhedron. In the case of a polygonal model, it was possible to consistently define 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, , , (they must not be collinear) in counterclockwise order on the boundary of the face. Let denote the vector from to , and let denote the vector from to . The cross product always yields a vector that points out of the polyhedron and is normal to the face. Recall that the vector is parallel to the normal to the plane. If its components are chosen as , , and , then 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 can be defined in a similar manner, in this case yielding TRUE if , and FALSE otherwise.

Steven M LaValle 2012-04-20