Graphics Reference
In-Depth Information
(1) One only needs to evaluate f at the vertices at most.
(2) Given the way that the tracing proceeds this means that we need at most as
many function evaluations as there are triangles.
The main part of the algorithm is iterative in nature. At each stage we assume
that we have just “entered” a new triangle from some point
p
i
on one of its edges
(f(
p
i
) = 0). If the initial point does not lie on an edge of a triangle, then we use inter-
polation to replace it with one that does. Therefore, assume
(1) the triangle we are entering has vertices
v
0
,
v
1
, and
v
2
,
(2)
p
i
lies in the interior of edge [
v
0
,
v
1
], and
(3) f(
v
1
) < 0 < f(
v
0
).
The contour will leave the triangle through an edge
e
that is determined as follows:
if f(
v
2
) > 0, then the contour leaves through
e
= [
v
1
,
v
2
], otherwise, f(
v
2
) < 0, and the
contour leaves through
e
= [
v
0
,
v
2
]. In either case, a simple linear interpolation of the
function values at the vertices finds us the new point
p
i+1
in the interior of the edge
through which the contour leaves the triangle (f(
p
i+1
) = 0). We now repeat these same
steps with the point
p
i+1
and the triangle adjacent to the current one along edge
e
.
The iteration finishes when we return to the starting triangle or if we leave the
domain
D
. In the first case we have found our component and it is a closed loop. In
the second case we again start with
p
0
but move in the opposite direction to find the
other “half” of the component that now is a curve with two ends.
There is one final aspect of this algorithm. It has to do with the efficient way that
the triangulation is dealt with in [DLTW90]. In particular, there is no need to somehow
precompute a global triangulation of the domain or the values of the function on its
vertices. All one needs to do is to be able to generate the triangulation “locally.” The
properties one wants are to be able to find vertices of adjacent triangles easily, all tri-
angles should have roughly the same size, and their dimensions should roughly be
the same in different directions (no “thin” triangles). There are triangulations, called
monohedral triangulations generated by reflections
, which satisfy these properties. The
name means that the simplices in the triangulation are all congruent and all the sim-
plices are generated from a fixed one by reflection about faces. There is a complete
classification of such triangulations. The paper [DLTW90] discusses them and also
gives further references. The three possible triangulations of this type in the plane are
shown in Figure 14.29(a-c). They are the so-called
Coxeter triangulations
of type
P
3
, R
3
, and V
3
, respectively. The P
3
and R
3
triangulations are actually just a two-
dimensional instance of a family of triangulations P
m
and R
m
, which exist in dimen-
sion m - 1. We shall only summarize the main conclusion relevant in the context of
the special contour finding algorithm being described here.
The reflection rule associated to finding the new vertex of a triangle adjacent to
an edge is simplest when using a triangulation of the P
3
type shown in Figure 14.29(a):
The P
3
reflection rule:
To reflect vertex
v
i
of a triangle about the opposite edge, replace
it by
v
i-1
+
v
i+1
-
v
i
, where indices are taken modulo 3.
This rule and the other reflection rules for the R
3
and V
3
triangulations can actually
be applied to
any
triangle and therefore produces an algorithm for generating a tri-
