Graphics Reference
In-Depth Information
Figure 13.1.
A ray-curve intersection
problem.
find the world coordinates of their points involves a transformation in any case.
Adding a rigid motion costs only one matrix multiplication per object (not one per
point).
If p(u) = (p 1 (u),p 2 (u)), then finding the point where the y-axis pierces the curve is
equivalent to solving the equation
() =
pu
0
1
along with the constraint p 2 (u) ≥ 0. See Figure 13.1. The equation can be solved using
a Newton-Raphson method. To apply this method we need a starting guess at a solu-
tion. One way to get one is to subdivide the domain of p(u) into small segments with
endpoints u i and then approximate the curve by the polygonal curve defined by the
points p(u i ). If we find a segment pierced by the ray, then any one of its endpoints can
be used as an initial guess for the Newton-Raphson iteration. Two situations that cause
problems with this approach are zero derivatives and places where the iteration gen-
erates parameter points that leave the interval which is the domain of the function
p(u).
Recursive Subdivision Methods. The first approach of this type, described in
[LanR80], can be used to find ray-curve or line-curve intersections in the case of curves
like Bézier and B-spline curves, which satisfy the variation diminishing property,
namely, that a hyperplane meets the curve in no more points than it meets the control
polygon of the curve. Because of that property one can use the following algorithm
to find the intersection of a line and the curve p(u):
(1) If the line does not intersect the control polygon, then the line will not inter-
sect the curve and we quit.
(2) Otherwise, subdivide the curve into two parts, compute the control polygon
for these two subcurves, and repeat step (1) for each of them. One continues
this process until the curves are small enough so that we can use an endpoint
as an approximation to the intersection.
A better algorithm replaces (1) by
(1) If the line does not intersect a bounding box containing the control polygon,
then the line will not intersect the curve and we quit.
Search WWH ::




Custom Search