Graphics Reference
In-Depth Information
(a
)
D
P
(b)
Figure 14.17.
Tessellating surfaces via locally isometric approximations (Cho, W.P., et
al. “Approximate Development of Trimmed Patches for Surface Tessellation,” CAD,
30
(14), December 1998, 1077-1087.).
to a local isometry. Of course, this has to be done in a way that does not involve exces-
sive computations. Starting with a rectangular grid of points on the surface, the
authors construct a mapping from this grid to a grid G in the plane that is approxi-
mately a local isometry in the sense that edges adjacent to a vertex should be mapped
to edges in the plane of approximately the same length. In Figure 14.17(a) we see an
original surface, then a grid on that surface, and finally the grid G in the plane. Cho
et al. define a global error function and use a minimization argument to accomplish
this. Next, they define a one-to-one and onto linear map a from the region
D
defined
by G to the rectangular domain of p(u,v). The map j(u,v) = p(a(u,v)) will be a para-
meterization of the surface with domain
D
. See Figure 14.17(b). A nice triangulation
of
D
or the trimmed regions in
D
will then map to a reasonably nice triangulation of
S
by j(u,v).
Most algorithms that triangulate trimmed surfaces obtain the triangulation by
triangulating the region bounded by the trimming curves in parameter space. This
means that the trimmed surface problem has as part of it a problem that is interest-
ing on its own, namely, the
triangulation problem
for such planar regions. This is a
well-known problem in computational geometry and Section 17.6 discusses algo-
rithms for triangulating planar polygons without holes and their complexity. On the
other hand, since we are interested in the rendering of trimmed surfaces, we do not
necessarily need triangles. We shall now describe an implementation of a relatively
simple algorithm that solves the following general problem.
Trapezoidation problem:
Given a closed planar region bounded by k closed polygonal
curves, k ≥ 1, decompose it into a collection of trapezoids.
Of course, once a region has been divided into trapezoids, it is obviously easy to get
a triangulation, so that we will also have solved the corresponding triangulation
