Graphics Reference
In-Depth Information
π
B
A
C
Figure 12.23 A good heuristic is to resolve two or more concave edges with a single cut.
Here the cutting plane π passes through the concave edges A and B , leaving just one concave
edge C (going into the drawing).
A more feasible approach to convex decomposition is to recursively split the poly-
hedron in two with a cutting plane through one or more concave edges. In that such
a split reduces the number of concave edges by one, the procedure will eventually
terminate, returning a set of convex pieces (which lack concave edges).
If the goal is to produce as few convex pieces as possible, a good rule is to attempt
to resolve as many concave edges as possible with the same cut. This means that fewer
cuts are needed, generally resulting in fewer pieces overall. Figure 12.23 illustrates a
cut resolving two concave edges.
Where only one concave edge can be resolved, one degree of freedom remains
to determine the cutting plane fully: the angle of rotation about the concave edge.
In these cases, two reasonable options are to either find some other (convex) edge
with which to form a cutting plane or to select the cutting plane to be the supporting
plane of one of the faces incident to the concave edge. Both alternatives are illus-
trated in Figure 12.24. The former option is not always available because there may
not be an edge that forms a plane with the concave edge. It also requires search for the
second edge. The latter option requires no search and can always be performed. How-
ever, cutting planes that are aligned or nearly aligned with polygon faces are sources
of robustness problems, similar to the line-plane intersection problem described in
Section 11.3.2.
Splitting a nonconvex polyhedron by a plane can result in many pieces, not just
two. The decomposition procedure is recursively called with each piece. To limit the
number of pieces generated, not the entire of the polyhedron should be split to the
cutting plane. Consider Figure 12.25, which illustrates the problem. Here, the cutting
plane has been selected to cut off the part labeled A from the rest of the polyhedron.
However, if the cut is applied globally across the polyhedron part B will also be
cut off.
Search WWH ::




Custom Search