Graphics Reference
In-Depth Information
the
k
-DOP is recomputed from these vertices and transformed into world space by
the current orientation matrix. This is equivalent to the AABB method described in
Section 4.2.6.
The vertex set of the
k
-DOP in its initial orientation can be computed with the help
of a duality transformation mapping. Here the dual mapping of a plane
ax
=
1 is the point (
a
,
b
,
c
) and vice versa. Let the defining planes of the
k
-DOP be expressed
as plane equations. Then by computing the convex hull of the dual of these planes the
faces (edges and vertices) of the convex hull maps into the vertices (edges and faces)
of the intersection of the original planes when transformed back under the duality
mapping. For this duality procedure to work, the
k-
DOP must be translated to contain
the origin, if it is not already contained in the
k
-DOP
.
For volumes formed by the
intersection of halfspaces, a point in the volume interior can be obtained through
linear programming (see Section 9.4.1). Another, simpler, option is to compute an
interior point using the
method of alternating projection
(MAP). This method starts
with an arbitrary point in space. Looping over all halfspaces, in arbitrary order, the
point is updated by projecting it to the bounding hyperplane of the current halfspace
whenever it lies outside the halfspace. Guaranteed to converge, the loop over all
halfspaces is repeated until the point lies inside all halfspaces. If the starting point lies
outside the intersection volume, as is likely, the resulting point will lie on the boundary
of the intersection volume, and specifically on one of the bounding hyperplanes.
(If the point lies inside the volume, the point itself is returned by the method.) A point
interior to the volume is obtained by repeating the method of alternating projections
with different starting points until a second point, on a different bounding hyperplane,
is obtained. The interior point is then simply the midpoint of the two boundary points.
MAP may converge very slowly for certain inputs. However, for the volumes typically
used as bounding volumes, slow convergence is usually not a problem. For more
information on MAP, see [Deutsch01]. For more information on duality (or polarity)
transformations see, for example, [Preparata85], [O'Rourke98], or [Berg00].
A simpler way of computing the initial vertex set is to consider all combinations
of three non co-planar planes from the input set of
k
-DOP boundary planes. Each
such set of three planes intersects in a point (Section 5.4.5 describes how this point is
computed). After all intersection points have been computed, those that lie in front
of one or more of the
k
-DOP boundary planes are discarded. The remaining points
are then the vertices of the
k
-DOP.
k
-DOPs can also be realigned using methods based on linear programming, as
described in [Konecný97] and [Konecný98]. A more elaborate realignment strategy
is presented in [Fünfzig03]. Linear programming is described in Section 9.4.
+
by
+
cz
4.6.5
Approximate Convex Hull Intersection Tests
It is easy to test separation between two convex polygons (for example, using the
rotating calipers method mentioned in Section 4.4.4). Unfortunately, the problem
is not as simple for polytopes. Accurate methods for this problem are discussed in
