Graphics Reference
In-Depth Information
Timmer's Ordering Phase.
We have to take our list of curve segments and combine
them appropriately to get the complete curve. This is not totally trivial. Only the end-
points of the curve pieces are important. Basically, one starts with the first point uv
1
and the piece to which it belongs, then looks for another piece that has an endpoint
that matches the second endpoint of our piece, and continues in this manner. For the
example in Figure 13.10 we would get following connected pieces:
acdijk
bef
hmlg
,
--
-
--
, ,
, ,
,
,
,
, ,
This concludes our sketch of Timmer's algorithm. The problem with Timmer's
algorithm is that it does not always give the correct answer and it is not as efficient
as some more recent algorithms. Although more recent algorithms also fail at times,
they give the correct answers in many more cases. We shall describe one more march-
ing algorithm, namely, the one by Barnhill and Kersey ([BarK90]), although strictly
speaking this algorithm is a hybrid method since it includes elements of recursive sub-
division. Its primary goal was to be more general and more robust than previous such
algorithms while still being efficient.
The Barnhill-Kersey Hunting Phase.
The first step is to subdivide the rectangular
or triangular domain of each of the parameterizations in an adaptive way. A quadtree
data structure is used to represent a subdivision. Several types of subdivisions are per-
formed. First, there is a uniform subdivision of the domain down to a user specified
level for the quadtree. Then may come a further subdivision of those subpatches that
do not meet a flatness and edge linearity criterion based on the angles between
normals and tangents, respectively. For each subpatch we want the normals at the
vertices and at one interior point to be almost parallel. Equivalently, the angles
between them should be small. See Figure 13.13(a). In addition, for each edge of the
subpatch, if
T
and
T
ยข are the unit tangent vectors at the endpoints of that edge, then
Figure 13.13.
Flatness and edge linearity tests in the Barnhill-Kersey algorithm.
