Graphics Reference
In-Depth Information
(a)
(b)
Figure 14.15.
Shimada and Gossard bubble meshing (Modeling and Applications, Third
ACM Symposium, May 1995, p. 416, © 1995 ACM, Inc. (Reprinted by permission).
A quite different algorithm for generating two- and three-dimensional triangular
meshes for surfaces and solids that also applies to trimmed surfaces is described by
Shimada and Gossard in [ShiG95]. The algorithm, called
bubble meshing
by the
authors, consists of two steps. First, one defines a packing of bubbles or spheres with
centers on the object. To minimize the gaps and overlaps, one makes an initial guess
for the placement based on a hierarchical spatial subdivision. Proximity-based repul-
sive and attractive forces associated to the bubbles are defined and a physically based
dynamic simulation searches for a force-balanced solution that involves adding and
deleting bubbles depending on an overlap ratio.
After one has a packing, a constrained Delaunay triangulation or tetrahedrization
is used to select the best tessellation. Figure 14.15(a) shows an initial
random
place-
ment of bubbles
without
the use of a hierarchical subdivision and one can see that
the induced triangulation has undesirable properties. Figure 14.15(b) shows the final
bubbles and triangulation after the relaxation process. One motivation for the algo-
rithm is that the centers of a tightly packed set of bubbles mimics the structure of a
well-shaped Voronoi diagram, so that the number of poorly shaped triangles or tetra-
hedra is greatly reduced. The problem with the algorithm is that it is complex and the
relaxation method is computationally expensive. It also applied only to a single patch
and did not address the problem of cracks between patches.
Another adaptive trimming algorithm for a parametric surface p(u,v) is described
by Vigo and Brunet in [VigB95]. Its focus was also on stereolithography applications.
First, let
p
1
,
p
2
, and
p
3
be any three points in the domain of p(u,v). Let a(u,v) be the
standard linear map from the triangle
p
1
p
2
p
3
to the triangle p(
p
1
)p(
p
2
)p(
p
3
).
Definition.
The triangle
p
1
p
2
p
3
is said to be
admissible
with respect to a tolerance e if
(
)
-
(
)
£
puv
,
a
uv
,
e
for all (u,v) Œ
p
1
p
2
p
3
. A triangulation of a region in the domain of p(u,v) is said to be
an
admissible triangulation
if all of its triangles are admissible.
To test for admissibility Vigo and Brunet defined a function R(
p
) based on bounds
involving the second derivative of p(u,v) such that the following was true.
Admissibility Criterion.
A triangle in the domain of p(u,v) is admissible if and only
if |
pq
|£max (R(
p
),R(
q
)) for each of its edges
pq
.
