Graphics Reference
In-Depth Information
edge that would modify the topology of the discontinuity curves, depending on
the application. This penalty cost, if included, is the final term
E
disc
in the energy
formulation. This treatment of attributes is an instance of the Meaning principle:
the difference of discrete attributes in adjacent triangles gives a meaning to the
edge between them that guides the computation.
While Hoppe's approach to mesh simplification makes sense if you are starting
from a mesh, there are situations where radically different approaches make sense.
For instance, if you have a spline surface that you've triangulated at some resolu-
tion, and you want a simpler triangulation, it makes sense to go back to the spline-
tessellation procedure and invoke it with different parameters. Part of the evolving
landscape of GPU architectures is the development of
tessellation shaders,
or
small pieces of code, run on the GPU, that take some description of a shape and
produce from it a tessellation—a division into polygons—of the shape, with the
tessellation typically being governed by one or two parameters that determine the
density of triangles produced.
Mesh Repair, and Mesh Improvement
We will now illustrate some typical uses of meshes. The first is the marching cubes
algorithm, used to extract level-set surfaces from volumetric data. The next is an
approach to mesh repair—filling in holes and cracks, etc.—based on a variant of
marching cubes. The third is an algorithm for mesh “improvement,” in which the
interior structure of a mesh, primarily the shapes of the triangles, is improved
while keeping the overall mesh geometry unchanged.
So far we've discussed triangle meshes, reasoning that they're a dominant model-
ing technology. But what if you have a model presented in some other form, like
an implicit model? One standard form of implicit model is the uniformly sampled
grid of densities; imaging modalities like nuclear magnetic resonance often pro-
duce such data, where the number associated to each grid cell is proportional to
the amount of some material within that cell. An isosurface of this data can rep-
resent the boundary between tissue and air, or between soft tissue and bone, etc.
Extracting representations of such isosurfaces is one step in rendering them: We
can take the resultant polygonal mesh and hand it to a polygon-rendering pipeline.
The marching cubes algorithm presented in Section 24.6 does exactly this.
Marching cubes can be generalized in many ways. We'll discuss two of these
in the 2D case, the 3D case being exactly analogous. If we have data values at
the vertices of a square grid, linear interpolation allows us to estimate the loca-
tion of zeroes along each edge. The “marching squares” algorithm fills in these
estimated locations of zeroes on a cell's boundary with line segments in the inte-
rior of the cell; these line segments, taken together, constitute an estimate of the
