Graphics Reference
In-Depth Information
Figure 14.13.
Differences between the algorithms in Rockwood, A., et al. “Real-Time
Rendering of Trimmed Surfaces,” SIGGRAPH 89,
23
(3), July 1989, 107-117. By permis-
sion of the publisher, ACM and Luken, William L., “Tessellation of Trimmed NURB Sur-
faces,” CAGD,
13
(2), March 1996, 163-177.
some new complexities. However, there was no need for computing maxima and
minima of curves or uv-monotone regions, as was the case in [RoHD89].
Sheng and Hirsh ([SheH92]) describe an algorithm for triangulating trimming
surfaces that are grids of polynomial patches. The intended application was in stere-
olithography where one wanted to generate a “solid hard copy” directly from a three-
dimensional CAD model. There the machines that carry this out need a very accurate
triangulation. First, the trimming curves in parameter space were approximated by
polygonal curves and merged to produce planar polygons with possibly holes. These
polygons were triangulated using a special Delaunay triangulation algorithm and then
this triangulation was refined until the edges of the triangles satisfied allowed toler-
ances. Cracks were avoided not only between patches of a single surface but also
between surfaces. To avoid cracks between different surfaces one first determined the
matching common boundaries (the distance between the boundaries must be suffi-
ciently small) and then used a merging process to combine the two sets of vertices
into one. One disadvantage with the approach is that the size of the triangles is deter-
mined by a global flatness bound for each patch that depends on the second deriva-
tive of the parameterization and is not adaptive, so that potentially a very large
number of triangles are generated. The triangles one gets may also not have a desir-
able shape. A similar algorithm was described by Piegl and Richard in [PieR95].
Although it also used a global, but different, bound on the edge length of the trian-
gles to ensure that the triangulation was within a user-specified tolerance, it had a
special way to select the vertices of the triangles giving the triangles a more even size.
Many algorithms assume that surfaces are C
2
. The Piegl and Tiller algorithm in
[PieT98] only assumes a C
0
parameterization p(u,v) for a surface. Given a trimming
tolerance e
c
and a triangulation tolerance e
s
, the algorithm outputs polygonal trim-
ming curves and a triangulated trimmed surface. The polygonal approximation for
each trimming curve g(t) in the domain of p(u,v) is within a tolerance of e
c
of the trim-
ming curve p(g(t)). The triangulated surface is within a tolerance of e
s
of the surface
p(u,v). First, the trimming curves, which do not have to be closed curves, are linked
together into lists that correspond to closed curves and are marked as being either
inner or outer loops. Then they are polygonized. If g(t) is a trimming curve, its domain
