Graphics Reference
In-Depth Information
of a regular map where the solution is a manifold is described in [AllS85], [AllG87],
and [AllG91]. One does need to get a start point for each component of the solution.
A Newton-Raphson-type method is used to do this. One then “marches” out from that
start point building a triangulation as one goes along.
Snyder ([Snyd92]) describes a marching type algorithm that uses interval analy-
sis and, because of that, is more robust than the one in [Bloo88]. Another interesting
algorithm that uses interval analysis to guarantee robustness is described by Stander
and Hart in [StaH97]. This algorithm is based on the handle decomposition of a man-
ifold defined by the nondegenerate critical points of a Morse function for it. See Sec-
tions 4.5, 4.6, 8.6, and 8.7 in [AgoM05] for a discussion of the general theory behind
this. One assumes that equation (14.16) defines a surface
S
that is the boundary of a
solid defined by f(x,y,z) ≥ 0 and that the function f(x,y,z), or a slight perturbation of
it, has only nondegenerate critical points. Assume further that the critical values of
the function lie in an interval (-c,c) for some c. Consider the contours
C
t
= f
-1
(t). As
t ranges from c down to 0, the sets
C
t
start with the empty set and end with
S
. In
between critical values the topology of the sets
C
t
does not change. As one passes a
critical value, the topology changes in a well-defined manner that is a very simple
special case of the surgery described in Section 8.7 in [AgoM04]. Stander and Hart
use interval analysis to find the critical points of f. They are just the zeros of the gra-
dient of f. They then incrementally polygonize the contours
C
t
moving from one crit-
ical value to the next. The polygonization of
S
that they get in the end is then
guaranteed to be topologically correct. They claim that their approach is faster than
the one in [Snyd92] and produces fewer small polygons.
Finally, one can again use algebraic geometry, either to try to find a parameteri-
zation or to get past singularities that are the places where algorithms tend to run
into difficulties.
14.6
Finding Contours
Problems dealing with contours come in different flavors. In this section we consider
the following:
The general contour problem:
Given a function f:
R
n
Æ
R
m
and a point
c
Œ
R
m
, find the
contour
X
= f
-1
(
c
). (Other terms for such a set
X
are
level curve
or
isoline
or
isosurface
with
isovalue
c
.)
Sometimes the subset
{
(
,f
()
)
}
pp pX
Œ
of the graph of f is called the contour rather than
X
, but this set would be easy to get
once one knows
X
, and so we prefer our formulation. It should be pointed out that
the contour finding problem is closely related to the problem of finding spaces that
are defined implicitly because finding f
-1
(
c
) is equivalent to finding the zeros of the
function g(
p
) = f(
p
) -
c
. The two problems are just two sides of the same coin. The
justification for discussing the problems separately is that they have different conno-
