Intersection Algorithms - Computer Graphics and Geometric Modeling - page 549

intersection point q , one is left with another problem, namely, that of finding the
parameter u so that p(u) = q .

13.4 Special Surface Intersections

13.4.1 Ray-Surface Intersections

Problem 10.2.2.6 solved the ray-surface intersection problem for the faceted surface
case. Now assume that S is a parameterized surface with parameterization p(u,v) and
that X is a ray from a point p in a direction v . Let L be the line through p with direc-
tion vector v . Using a rigid motion we can transform this situation into one where p
is the origin and v is e 3 , so that L is the z-axis. Like in the ray-curve case, there is
little cost associated to assuming that this has been done.
If p(u,v) = (p 1 (u,v),p 2 (u,v),p 3 (u,v)), then finding the point where the z-axis pierces
S is equivalent to solving the equations

( ) = puv

puv

,
,

0
0

1

( ) =

2

along with the condition that p 3 (u,v) ≥ 0. These equations can be solved using a
Newton-Raphson method but one needs a starting guess at a solution. One way to get
one is to subdivide the u-v domain into small rectangles with corners (u i ,v j ) and then
approximate the surface by the grid of points p(u i ,v j ). If we find a quadrilateral pierced
by the ray, then any one of its corners can be used as an initial guess for the Newton-
Raphson iteration.
Again, like in all Newton-Raphson method approaches, one has to be ready to deal
with at least two problems. The first is that the partial derivatives of the functions
p 1 (u,v) and p 2 (u,v) may not be linearly independent at some points causing the usual
problems with a Newton-Raphson method. The other more complicated problem is
caused by the fact that we have a bounded domain and the iteration may want to
cross one of the boundary lines. When this happens one should check if the solution
does not in fact lie on the boundary by applying a Newton-Raphson iteration along
the boundary, which is a one-dimensional problem. There will be additional problems
at the corners of the patch. If at any time the solution seems to want to move back
inside the patch, revert to the two-dimensional search problem.

13.4.2 Curve-Surface Intersections

We only consider the case where both the curve and surface are smooth subsets of R 3
and are defined by parameterizations. Assuming that the curve is parameterized by
q(t) and the surface by p(u,v), we need to solve the equation

( ) = () - ( ) = 0 rtuv ,, qt puv , . (13.11)