Graphics Reference
In-Depth Information
on these. But for the kinds of meshes encountered in everyday games, for instance,
the algorithm works well.
Sander et al. [SNB07] have improved on this algorithm, and we anticipate
further research in this area, in which geometry and efficient computations are
combined.
The geometric study of meshes is a growing field, known as
discrete differ-
ential geometry.
Because of its close relationship to smooth differential geom-
etry, you should start by becoming familiar with that material. A particularly
gentle introduction is O'Neill's book [O'N06]; Millman and Parker's
book [MP77] is a good follow-up. For discrete differential geometry, there are
tutorials available [MDSB03], and at least one textbook [BS08].
The situation in what we've called “mesh flattening” (and what has come to be
known as “parameterization of meshes”) is not as hopeless as our remarks might
suggest. There does not seem to be any single ideal approach to parameterization
yet, but there's been substantial progress beyond the simplest approaches [SPR06,
CPS11, SSP08].
The structure of a mesh and the structure of the underlying graph are closely
related. The graph Laplacian has been used to address problems like graph parti-
tioning and clustering; analogs have been used in mesh partitioning.
Ray-mesh intersection testing, since it's in the critical path for ray tracing,
has been much studied. And because of its relevance to animation, so has col-
lision detection for meshes. Many ideas can be shared between the two topics.
Haines and Moller [AMHH08] give a complete overview, with details on many
algorithms.
Mesh optimization has been widely studied, along with the relationship of
mesh “smoothing” operations to digital filter design [Tau95] and to mean curva-
ture flow [DMSB99, HPP05]. Methods that allow small connectivity alterations
were popularized in graphics by Witkin and Welch [WW94], and can frequently
be useful in adjusting meshes where some vertex degrees are so large or small that
it's impossible to have all adjacent triangles approximately equilateral.
Despite all the research on meshes, they may, in fact, turn out to not be the ulti-
mate shape representation model for graphics. For rendering, the discontinuity of
reflection (you can adjust an incoming ray an arbitrarily small amount and get an
arbitrarily large change in the reflected ray) is a serious problem, especially when
one is trying to prove claims about convergence. The way that surfaces “condense”
geometric information (like curvature) to low-dimensional subsets (vertices and
edges) is reminiscent of the abstraction of the point light source, which condenses
the light emitted from a small area into light emitted from a single point. Such an
abstraction is convenient for some simple forms of rendering, but in fact makes
others considerably more difficult. It's possible that mesh representations of sur-
faces will someday be regarded only as limiting cases for some other preferred
kind of representation in which geometry generically has at least
C
2
continuity.
Nonetheless, meshes are an active area of research. Pick up any SIGGRAPH
proceedings from 2000 to 2012 and you'll find at least a dozen papers that concen-
trate on meshes in some form, and we anticipate that this trend will continue for
some time. Read such papers once with an open mind, to get ideas, and again with
