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) |
Once again, can be constructed, except now and
(3.8) |
(3.9) |
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 2020-08-14