Graphics Reference
In-Depth Information
(1) exactly via equations or parameterizations (for example, this is possible for
quadric intersections),
(2) as a polygonal curve that matches the intersection to some tolerance,
(3) as a spline (usually of a low degree) that uses an appropriate number of points
on the intersection as control points, or
(4) procedurally (for example, determine a fixed number of points on the inter-
section and compute the intersection to the desired accuracy on demand by
a marching method).
The polygonal curve approach seems to be the most popular.
13.2
Convex Set Intersections
This section describes a simple algorithm for testing whether two convex linear poly-
hedra intersect. The result is based on the fact, proved in Section 17.5, that disjoint
convex sets can be separated by a hyperplane and that there is a straightforward algo-
rithm for determining whether such a hyperplane exists or not.
See [Edel87] for a linear programming approach to the intersection and separat-
ing hyperplane problem. The solutions there result in much more complex programs
and may not be that much faster if m is relatively small.
Algorithm 13.2.1 is an abstract program for a function AreDisjoint that determines
whether two convex hulls are disjoint. First, a function SpaceProjectionType is called
that implements Theorem 17.5.1 directly and determines if the sets are linearly
separable. If the sets are separated by a plane
P
, then this still allows the possibility
that they intersect in that plane. Therefore, Theorem 17.5.1 has to be applied again
to the intersections of the sets with this plane. This is accomplished by the function
PlanarProjectionType. If two sets are separated in a plane this allows one final possi-
bility that they may intersect on the separating line and so we check for that with a
final call to function LinearProjectionType.
13.2.1 Theorem.
Algorithm 13.2.1 for whether the convex hulls of two sets
X
and
Y
with s and t points, respectively, are disjoint is an O(m
4
) algorithm, where m =
s + t.
Proof.
The algorithm is implemented by the function AreDisjoint. The work done
in AreDisjoint is dominated by the call to SpaceProjectionType. The loop in this func-
tion is executed m(m - 1)(m - 2) times and involves O(m) operations.
Finally, it should be noted that it is possible to make the algorithm more efficient
by decreasing the size of the loop in the SpaceProjectionType procedure. For example,
for each point picked in the outer i loop of the procedure one only needs to look at
vertices that lie in the “silhouette” of the polygons as seen from that point. Of course,
any gain in efficiency of the algorithms is at the expense of much more complicated
code.
