Graphics Reference
In-Depth Information
tations. In one case we are looking for a slice of a given object and in the other, the
zero set of a function is the entire object of interest.
An entirely different context for contour problems is where we are simply given
some discrete data and we are asked to find contour lines or surfaces for this data.
Specifically, we would want a structured definition of the line (an ordered list of
points) or surface (its edge and facet structure), not simply a random list of its points.
This problem can be thought of as a kind of special case of the contour problem stated
above by thinking of the data as consisting of sampled points for the zero set of a
function which we do not know. We ran into the problem earlier in Chapter 10 when
we discussed volume rendering and the marching cube algorithm. We shall not discuss
the discrete contour problem any further here. The interested reader is referred to
[Sabi85] and [Dowd85]. [HosL93] also has quite a few references. A related problem
is fitting curves and surfaces to discrete data that has also been studied extensively.
We now return to the contour-finding problem as we have stated it and the case
m = 1. If n = 3, then we would expect f
-1
(c) to be a surface. If n = 2, then we expect
to get a curve. This is the case we consider in this section and “finding the contour”
will mean finding a polygonal approximation for the curve. We restate the problem
for this case as
Given a real-valued function of two variables f(x,y) defined on some domain
D
in
R
2
and
a real number c, find a polygonal approximation to
X
= f
-1
(c).
In general one would expect the set
X
to consist of components which are curves,
but without some extra conditions on the function f(x,y), it could be pretty much any-
thing. For example, if
(
)
=+
2
2
fxy
,
x
y
,
then c = 1, 0, or -1 produces an
X
that is the unit circle, the single point (0,0), or the
empty set, respectively. A more degenerate case is the constant function f(x,y) = c, in
which case
X
is all of
D
. One well-known condition that guarantees that
X does
consist of nice curves is that f is a continuously differentiable function whose deriv-
ative has rank 1 on
X
. This condition is not one that one can always assume in prac-
tice however, and so any algorithm that finds contours has to be able to handle some
degenerate cases.
Contour finding algorithms typically consist of two steps:
Step 1:
One has to find starting points, that is, one has to find one point on each
component of the contour.
Step 2:
Given a starting point in a component, one then has to trace out the rest of
that component.
Step 1 is the problem of finding solutions to or zeros of equations about which
much is known. See Section 4.7 in [AgoM05]. We say no more about it here and con-
centrate instead on Step 2.
Assuming that one has found one point
p
0
of a component
C
of
X
, two basic
approaches to finding the rest of it are:
