Graphics Reference
In-Depth Information
for f around
p
. Assume that g(t) =
q
. Since g(t) lies in
S
1
, h(t) = f(g(t)) = 0. Therefore,
if one substitutes the series (13.18) into (13.19) all the coefficients of the resulting
power series in t must vanish. Setting the coefficients of t
i
, i = 1, 2,..., m, to zero
gives m equations in 3m unknowns g
j
(i)
(0), j = 1, 2, 3, and i = 1, 2,..., m. Applying
the same argument to the function g that defines the surface
S
2
gives another m equa-
tions. This underdetermined system of equations can be solved. By adding some addi-
tional geometric constraints dealing with the curvature and moving triad associated
to the space curve g(t), one can get a unique solution. The way that the additional con-
straints are chosen affects the parameterization g(t) of the intersection of the surfaces.
[BHLH88] and [Hoff89] also discuss how to choose the step d. One has to watch out
that one does not get outside the radius of convergence of g(t). This is not easy, but
one can give bounds for the maximum step size. In the case m = 3 these depend on
the second and third derivative of g.
Having gotten an approximation to the next point on the surface intersection, one
performs a Newton-Raphson iteration consisting of points
q
0
=
q
,
q
1
,
q
2
,..., to find
the point
p
i+1
that actually lies in that intersection with as much accuracy as desired.
One point to note is that what we just did for
R
3
easily extends to computing the inter-
section of n - 1 hypersurfaces in
R
n
.
Using higher-order approximations to curves takes computation time, which is
why many algorithms are satisfied with linear approximations and step in the tangent
direction. However, one must also decide on the step size. Intuitively, it makes a lot of
sense to base the decision on the osculating circle since it is the best circle approxi-
mation to the curve at the point. Both the Timmer and Barnhill-Kersey algorithms step
in the tangent direction and use the radius of the osculating circle to determine a step
size. Since everything is an approximation anyway, the only question is how accurately
we should compute the osculating circle and its radius r. Computing second derivatives
is usually not cheap. Timmer's algorithm did compute r exactly. The Barnhill-Kersey
algorithm used an approximation to the real r. Neither algorithm actually tried to
compute the osculating circle and only needed its radius. The algorithms in [CheO88]
and [Aste88], on the other hand, actually stepped along the circle. The first applied
to parametric surfaces and the second to implicit surfaces. The approximation in
[WuAn99] is better yet for parametrically defined surfaces. The authors define an
approximation to the osculating circle that can be computed efficiently and step in its
tangent direction (not along the tangent to the curve). The equation for their circle is
based on the current and previously computed curve point and tangent. Let
T
i
denote
the tangent to the intersection curve at point
p
i
. Let
C
be the point that is the intersec-
tion of the following three planes p
1
, p
2
and p
3
described in point-normal form:
plane p
1
:
point
p
i-1
, normal vector
T
i-1
plane p
2
:
point
p
i
, normal vector
T
i
plane p
3
:
point
p
i
, normal vector
T
i-1
¥
T
i
The point
C
is then assumed to be the center of the circle. The plane of the circle is
assumed to have normal vector
Cp
i-1
¥
Cp
i
. See Figure 13.18. Degenerate cases are
handled in the paper. One can show that this circle converges to the actual osculat-
ing circle as
p
i
approached
p
i-1
. The marching distance is again taken to be rDq, where
r = |
Cp
i
| and Dq is a predefined tolerance. It was found that this method leads to a
robust marching algorithm that
