Graphics Reference
In-Depth Information
Figure 13.17.
A step constrained marching
method.
on the intersection curve and possible lack of convergence where the partials of f
vanish. Additionally, the step constraint must be chosen carefully. For example, for a
constraint of the type shown in equation (13.15), the step size d influences the result
and the value of d may change from point to point. We do not want to step to another
branch of the curve. We also have to check for the possibility that our solution takes
us outside the given (u,v)-domain. If the intersection curve is closed, then we also
want to be able to close our curve explicitly.
A fourth marching method approach tries to minimize a function that vanishes
on the set of interest. For example, if the intersection is defined by
(
)
=
fxyz
gxyz
,,
,,
0
0
(
)
=
and we use a step constraint
(
)
= 0
hxyz
,,
,
then we could try to minimize
2
2
2
.
Ff g h
=+ +
(13.16)
See, for example, [Powe72] or [PraG86].
We mention one last marching type approach. Here one uses vector fields and
differential equations, where intersection curves are solutions to the latter. See, for
example, [PhiO84], [Chen89], [MarM89], or [KrPW92].
At the heart of the typical marching method is the Newton-Raphson method. One
ends up with a discrete approximation to the solution. As one generates the points
one always starts with a guess for the next point and then uses the Newton-Raphson
method to successively refine that guess until we get a point that lies on the actual
solution set with desired accuracy. Let us recapitulate some of the common problems
marching methods have to contend with:
(1) They need starting points.
(2) The direction and step size has to be selected very carefully to avoid missing
entire pieces of the intersection or accidentally stepping from one component
to another.
