Graphics Reference
In-Depth Information
points are good candidates for this approach because their subdivisions have associ-
ated control nets. In [LanR80] the idea is to subdivide the surfaces enough so that the
individual pieces are essentially flat (see also [Clar79] and [LCWB80]). One then finds
the intersection of the approximating planar patches to get a polygonal approxima-
tion to the actual intersection. Because the surfaces satisfy the convex hull property,
one can use bounding boxes to make the algorithm more efficient. This is the analog
of the recursive subdivision for curve intersections in Sections 13.3.1 and 13.3.4.
One problem associated to recursive subdivision is the amount of data that could
be generated potentially. The way to mitigate this problem is by not doing the subdi-
vision down to a certain level blindly. One should keep subdividing an object only at
those places where there is a possibility of it intersecting the other object. The typical
way that such an adaptive approach is carried out is by using some sort of bounding
box approach. Min-max boxes, which are obtained from the minimum and maximum
values of the coordinates of the points of an object, are common choices because they
are so simple. Other bounding objects are slabs (see Section 6.2), convex hulls in the
case of Bézier or B-spline surfaces, or “fat” planes ([Carl82]) for Bézier surfaces. If
the bounding objects do not intersect, then the objects will not intersect. Checking for
intersections of the bounding objects is much easier than checking for intersections
between the objects themselves. One subdivides the objects only at those places where
the bounding boxes intersect. This approach implies that one has a termination cri-
terion. The usual such is based on a flatness test. There are many ways to check for
flatness, but one simple one is to use the normal vectors. The normal vectors will not
change much over regions that are close to flat. Of course, no matter how simplified
a test one uses, this will still take some extra time and so the more one can avoid
having to use such tests, the better. One might be able to say in advance how much
subdivision is needed.
The algorithm in [HEFS85] is an example of a recursive subdivision algorithm for
C
1
parametric surfaces. It proceeds in four steps: subdivision, intersection, sorting,
and refinement. The subdivision is done in stages. First, the surfaces are subdivided
until the subpatches satisfy an initial flatness and edge linearity criterion. A stack of
possibly intersecting pairs of subpatches is created. The test for intersection here is
based on whether associated “oriented” bounding boxes (bounding boxes that roughly
line up with their patches) intersect. The leftover subpatches are successively subdi-
vided further to higher flatness tolerances. A tree data structure is used to maintain
the data generated. When subpatches are flat enough, they are approximated by two
triangles and the intersections of these triangles are used as approximations to the
intersection of the patches. This produces a collection of segments that the sorting
phase must then combine to get the polygonal curve segments that become the
approximation of the intersection curves of the surfaces. Since the algorithm is based
on adaptive subdivision there may be gaps between adjacent triangles, but the algo-
rithm checks for this and redefines subpieces appropriately to prevent the problem
from occurring. Finally, the triangle intersections are only approximations, therefore
a refinement step iteratively tries to find points closer to the surfaces. We described a
slightly improved version of this refinement in the Barnhill-Kersey algorithm in
Section 13.5.2. An algorithm similar to the one in [HEFS85] is described in [FiMM86].
There bounding boxes are defined using derivative bounds.
On a related topic, [Nasr87] discusses finding intersections of recursive subdivi-
sion surfaces.
