of 26
Discrete Differential-Geometry Operators
for Triangulated 2-Manifolds
Mark Meyer
1
,MathieuDesbrun
1
,
2
, Peter Schr ̈
oder
1
, and Alan H. Barr
1
1
Caltech
2
USC
Summary.
This paper proposes a unified and consistent set of flexible tools to
approximate important geometric attributes, including normal vectors and cur-
vatures on arbitrary triangle meshes. We p
resent a consistent derivation of these
first and second order differential properties using
averaging Voronoi cells
and the
mixed Finite-Element/Finite-Volume method, and compare them to existing for-
mulations. Building upon previous work in discrete geometry, these operators are
closely related to the continuous case, guaranteeing an appropriate extension from
the continuous to the discrete setting: they respect most intrinsic properties of the
continuous differential operators. We show that these estimates are optimal in ac-
curacy under mild smoothness conditions, and demonstrate their numerical quality.
We also present applications of these operators, such as mesh smoothing, enhance-
ment, and quality checking, and show results of denoising in higher dimensions,
such as for tensor images.
1 Introduction
Despite extensive use of triangle meshes in Computer Graphics, there is no
consensus on the most appropriate way to estimate simple geometric at-
tributes such as normal vectors and curvatures on discrete surfaces. Many
surface-oriented applications require an approximation of the first and sec-
ond order properties with as much accu
racy as possible. This could be done
by polynomial reconstruction and analytical evaluation, but this often intro-
duces overshooting or unexpected surface behavior between sample points.
The triangle mesh is therefore often the only “reliable” approximation of the
continuous surface at ha
nd. Unfortunately, since meshes are piecewise linear
surfaces, the notion of continuous normal vectors or curvatures is non trivial.
It is fundamental to guarantee accuracy in the treatment of discrete sur-
faces in many applications. For example, robust curvature estimates are im-
portant in the context of mesh simplification to guarantee optimal triangu-
lations [HG99]. Even if the quadric error defined in [GH97] measures the
Gaussian curvature on an infinitely subdivided mesh, the approximation be-
comes rapidly unreliable for sparse sampling. In surface modeling, a number
of other techniques are designed to create very smooth surfaces from coarse
meshes, and use discrete curvature approximations to measure the quality of
2
Mark Meyer, Mathieu Desbrun, Peter Schr ̈
oder, and Alan H. Barr
the current approximation (for example, see [MS92]). Accurate curvature nor-
mals are also essential to the problem of surface denoising [DMSB99, GSS99]
where good estimates of mean curvatures and normals are the key to undis-
torted smoothing. More generally, discrete operators satisfying appropriate
discrete versions of continuous properties would guarantee reliable numerical
behavior for many applications using meshes.
1.1 Previous work
Several expressions for different surface properties have been designed. For
instance, we often see the normal vect
or at a vertex defined as a (sometimes
weighted) average of the normals of the adjacent faces of a mesh. Th ̈
urmer
and W ̈
uthrich [TW98] use the incident angle of each face at a vertex as the
weights, since they claim the normal vector should only be defined very lo-
cally, independent of the shape or length of the adjacent faces. However, this
normal remains consistent only if the faces are subdivided linearly, introduc-
ing vertices which are not on a smooth su
rface. Max [Max99] derived weights
by assuming that the surface locally approximates a sphere. These weights
are therefore exact if the object is a (even irregular) tessellation of a sphere.
However, it is unclear how this approximation behaves on more complex
meshes, since no error bounds are defined. Additionally, many meshes have
local sampling adapted to local flatness, contradicting the main property of
this approach. Even for a property as fundamental as the surface normal, we
can see that several (often contradictory) formulæ exist.
Taubin proposed the most complete derivation of surface properties, lead-
ing to a discrete approximation of the cu
rvature tensors for polyhedral sur-
faces [Tau95]. Similarly, Hamann [Ham93] proposed a simple way of determin-
ing the principle curvatures and their a
ssociated directions
by a least-squares
paraboloid fitting of the adjacent vertices, though the difficult task of select-
ing an appropriate tangent plane was left to the user. Our paper is closely
related to these works since we also derive all first and second order prop-
erties for triangulated surfaces. How
ever, many of the previous approaches
do not preserve important differential geometry properties (invariants) on
C
0
surfaces such as polyhedral meshes.
In order to preserve fundamental invariants, we have followed a path ini-
tiated by Federer, Fu, Polthier, and Morvan to name a few [Fu93, PP93,
PS98, Mor01, TM02]. This series of work proposed simple expressions for
the total curvatures, as well as the Dirichlet energy for triangle meshes, and
derived discrete methods to compute min
imal surfaces or geodesics. We refer
the reader to the overview compiled by M
orvan [Mor01]. Note also the tight
connection with the “Mimetic Discretiza
tions” used in computational physics
by Shashkov, Hyman, and Steinberg [HS97, HSS97]. Although it shares a lot
of similarities with all these approaches, our work offers a different, unified
derivation that ensures accuracy and tight error bounds, leading to simple
formulæ that are straightforward to implement.