Graphics Reference
In-Depth Information
at least two reasons for using an adaptive tiler. One is that one would usually use less
space. The other is that, like in the parametric object case, we may want to get a better
approximation to the actual shape if its curvature varies substantially. See [Bloo97]
for a discussion of this topic and for references.
Finally, Velho et al. ([VeDG99]) describe a polygonization algorithm that works
for both implicit and parametric surfaces. The paper also provides an overview and
references for many of the previous polygonization algorithms. Their algorithm is an
adaptive one that creates a hierarchical mesh. The construction guarantees that there
will be no cracks. There are three steps:
Step 1:
Determine a rough triangulation of the surface.
Step 2:
Sample the edges of the triangulation to produce a hierarchical approxi-
mation to the corresponding edge on the surface.
Step 3:
Subdivide the triangles of the triangulation into smaller triangles based on
the number of vertices in their boundary edges.
The only requirement in Step 1 is that the triangulation is faithful to the topol-
ogy of the surface. For parametric surfaces this boils down to triangulating planar
domains. The examples in the paper show that for parameterizations with rectangu-
lar domains, simply dividing the rectangle into two triangles with the diagonal will
often be adequate. The algorithm however also works for trimmed surfaces. In the
case of implicit surfaces, any one of a number of uniform polygonization algorithms
can be used as long as the edges of the mesh lie in a tubular neighborhood of the
surface. One such algorithm that does this is the one in [StaH97]. We shall describe
it later in Section 14.5.2.
In Step 2 one makes a single pass over all the edges in the triangulation. To each
edge one associates a data structure that consists of its two endpoints, a binary tree,
and a real number that gives the maximum deviation of the edge from the surface.
The binary tree comes from recursively replacing an edge
e
= [
p
,
q
] with two new edges
e
R
= [
p
,
r
] and
e
L
= [
r
,
q
]. The nodes in the tree consists of a vector
v
from the mid-
point of
e
to
r
, the maximum of the deviations of the edges
e
R
and
e
L
from the surface,
and pointers to the tree nodes associated to
e
R
and
e
L
. See Figure 14.10. Ideally, to
get a nice balanced tree one would like
r
to be the midpoint of the curve correspon-
ding to the edge, but since this would be too complicated to compute exactly, an
approximation is used. In the end this produces an adaptive multi-resolution approx-
imation to the curve corresponding to the edge.
Step 3 is carried out in a way that depends solely on the edge structure obtained
from Step 2. First, the original edges of the triangulation are classified as simple or
complex, depending on whether Step 2 subdivided them or not. Then the way a tri-
angle gets subdivided depends on how many simple edges it has. The four cases are
shown in Figure 14.11. If all three edges are simple, we do not subdivide. Otherwise,
Figure 14.10.
Edge sampling in [VeDG99].
