Graphics Reference
In-Depth Information
(3) They get tricky to implement near terminating points.
(4) They have problems at singular points.
What differentiates the various marching algorithms is how these problems are
addressed. We finish this section with a discussion of these points.
When it comes to picking start points, we have seen how the Timmer and
Barnhill-Kersey algorithms do it. For more on the subject we refer the reader to
[AbdY97]. That paper discusses two general methods for picking start points along
with an analysis and comparison.
The question of step direction and size really has to do with finding a good approx-
imation to the next point on the curve. Obviously, the better these guesses are, the
faster the Newton-Raphson method converges to the solution. Most of the time, the
guesses are based on linear approximations to the solution. For example, a starting
guess for the next point is often chosen from the points along the tangent line at the
current point of an intersection curve. This is often only a crude guess. A higher-order
approximation to the solution set would lead to quicker convergence of the Newton-
Raphson method. [Stoy92] suggests using a second-order approximation, that is,
parabolas. In that way one was also able to control the deviation of the actual inter-
section curve from its polygonal approximation.
We shall sketch the mathematics involved in getting higher order approximations.
The details can be found in [BHLH88] and [Hoff89]. Consider the implicit/implicit
case where the two surfaces
S
1
and
S
2
in
R
3
are defined by equations
(
)
= 0
(
)
= 0
fxyz
,,
and
(13.17)
gxyz
,,
.
As usual our object is to define a sequence of points
p
0
,
p
1
,
p
2
,..., so that the polyg-
onal curve they define approximates the intersection of
S
1
and
S
2
. We need to describe
how we get the first point and then how we get from one point to the next.
Assume that we are given a point
p
=
p
i
that lies on the intersection of
S
1
and
S
2
and we want to get the next point
p
i+1
. Assume further that the gradients —f(
p
) and
—g(
p
) are not zero and that the surfaces intersect transversally at
p
. If any of these
conditions are not satisfied, the approach that will be described here will probably
fail and an algebraic geometry approach would be appropriate if f and g are polyno-
mials. The general assumption we make here is that the intersection of
S
1
and
S
2
can
be defined by an analytic function of the form
1
()
()
=+ +
2
i
()
g
t
aa a
t
t
+
...,
where
a
=
g
0
,
(13.18)
0
1
2
i
i
!
defined in the neighborhood of the origin with g(0) =
p
. We use the first m terms of
this power series to approximate g(t). The case m = 1 corresponds to the usual linear
approximation and so of interest here is the case m > 1, specifically when m = 2 or 3.
To accomplish the goal, we need to solve for the
a
i
, i = 0, 1,..., m.
Let
q
=
p
+ d and let d = (d
1
,d
2
,d
3
). Consider the Taylor expansion
•
ijk
++
1
∂
∂∂∂
f
xyz
Â
Â
j
i
k
()
=
()
f
q
a
dd d
,
a
=
p
(13.19)
ijk
ijk
123
ijk
!! !
i
j
k
d
=
0
ijkd
++ =
