Graphics Reference
In-Depth Information
(a)
P
3
rule
(b)
R
3
rule
(c)
V
3
rule
Figure 14.29.
Three triangulations by reflections.
Figure 14.30.
The P
3
reflection rule applied to a basic R
3
triangle.
angulation along with a labeling of the vertices of this triangulation. For example,
applying the P
3
reflection rule to a basic R
3
triangle in Figure 14.29(b) produces the
triangulation shown in Figure 14.30. Here is what is recommended by [DLTW90]: The
P
3
triangulation seems to be the best geometrically for the contour-finding algorithm.
Start off with the triangle
v
0
v
1
v
2
centered at the origin, where
1
6
1
6
1
2
Ê
Ë
ˆ
¯
=
Ê
Ë
ˆ
¯
=
(
)
v
00
,,
v
=
2
, ,
0
and
v
,
.
0
1
2
Scale this triangle to the appropriate size and then translate it so that our start point
becomes its barycenter. Now start the iterative algorithm described above. If one
wants to find several components of the contour and we want all of them to use the
same triangulation, then things get a little trickier. See [DLTW90].
With our choice of triangulation one can simplify the termination test, which
checks for loops. This can be done by expressing points with respect to the basis
v
1
and
v
2
. For example, the coordinates of the barycenters of all simplices will then have
the form (1/3)k, where k is an integer unique to the simplex. Checking whether a
contour has terminated in a loop therefore amounts to simply checking if two integer
vectors are equal. The authors of [DLTW90] suggest that it is possible to avoid some
round-off errors if other computations are also done in that basis. Of course, the con-
version from Euclidean coordinates to the coordinates with respect to that basis costs
a little time.
Finally, we need to say something about the limitations of the algorithm just
described. First of all, we only dealt with the nondegenerate case. There are two degen-
erate cases that must be handled in special ways. The first is where the derivative of
