Graphics Reference
In-Depth Information
Figure 13.2.
Bounding rectangles for curve segments without characteristic points.
The easiest way to get a bounding box is to use the minimum and maximum values
of the coordinates of the control points. It is faster to compute the intersection of a
line with such a bounding box than with the control polygon. The subdivision
approach generalizes to nonplanar curves.
Another recursive subdivision algorithm is a “characteristic point”-based sub-
division algorithm described in [KopM83]. A characteristic point is basically one
where the first or second derivative of a component function vanishes. Such points
were computed using interval analysis for accuracy. We describe the planar case.
Given a curve, one determines all the points that have horizontal or vertical tangent
lines. These points, along with the endpoints of the curve, divide the curve into seg-
ments. The rectangle that has diagonal defined by the two endpoints of a curve
segment then contains that segment. See Figure 13.2. The collection of these rectan-
gles becomes the bounding boxes for the curve. If our ray intersects any of these rec-
tangles, then we divide the corresponding curve segment in half and compute the new
bounding rectangles. We keep doing this until the remaining bounding rectangles are
small enough. The only disadvantage of this algorithm is that one has to find the places
on the curve with horizontal and vertical tangents. For low-degree curves it is shown
in [SedP86] that the method is actually faster than the Bézier subdivision approach,
although the latter is more stable.
13.3.2
Curve-Curve Intersections
Finding the intersection of two polygonal curves reduces to finding the intersection
of a segment with a curve and finally to finding the intersection of two segments. The
last problem has already been dealt with in Section 6.5.
To find the intersection of a parameterized and a polygonal curve reduces to
finding the intersection of a segment with a smooth curve. We can use a straightfor-
ward modification of the ray-curve algorithm described in Section 13.3.1.
To intersect two smooth curves one could of course replace those curves by poly-
gonal approximations and a use polygonal intersection algorithm. The main problem
is determining whether the approximations are good enough so that no intersections
are missed. In a variation of the subdivision approach described in [LanR80], Turner
([Turn88]) actually replaced the curve with two approximations that contained the
curve between them. As an example, consider the planar Bézier curve shown in Figure
13.3. The convex hull of the four control points is bounded by two curves C 1 and C 2 ,
Search WWH ::




Custom Search