Restricted Delaunay Triangulations and Normal Cycle∗Da vid Cohen-Steiner†Jean-Marie Morvan‡ABSTRACTWe address the problem of curvature estimation from sampledsmooth surfaces. Building upon the theory of normal cycles,we derive a definition of the curvature tensor for polyhedralsurfaces. This definition consists in a very simple and newformula. When applied to a polyhedral approximation of asmooth surface, it yields an efficient and reliable curvature es-timation algorithm. Moreo ver, we bound the difference be-tween the estimated curvature and the one of the smooth sur-face in the case of restricted Delaunay triangulations.Categories and Subject DescriptorsF.2.2 [Analysis of algorithms and problem complexity]: [Ge-ometrical problems and computations, Computations on dis-crete structures]; G.2.3 [Discrete Mathematics]: ApplicationsGeneral TermsAlgorithms, TheoryKeywordscurvature, geometric measure theory, meshIntroductionIn many applications such as surface segmentation, anisotropicremeshing [21] or non-photorealistic rendering, a key step is∗Work partially supported by the IST Programme of the EUas a Shared-cost RTD (FET Open) Project under Contract NoIST-2000-26473 (ECG – Effective Computational Geometryfor Curves and Surfaces).†I.N.R.I.A., Sophia-Antipolis, France. E-mail:David.Cohen [email protected]‡I.N.R.I.A., Sophia-Antipolis, France. E-mail: [email protected] to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SoCG’03, June 8-10, 2003, San Diego, California, USA.Copyright 2003 ACM 1-58113-663-3/03/0006 ...$5.00.to estimate the curvature of a smooth surface knowing onlya polyhedral approximation of it. A lot of efforts have beendevoted to this problem, leading to several curvature estima-tors, see [17] for a survey. Popular methods include quadricfitting, where the estimated curvature is the one of the quadricthat best fits the sample points locally. Other methods typ-ically consider some definition of curvature that can be ex-tended to the polyhedral setting. An example is [18], where thecurv ature is estimated using a discrete analog of the Laplace-Beltrami operator. The main shortcomings of these approachesare the lack of analysis of the quality of the obtained estima-tors, and also the lack of sound theoretical foundations.In this paper, we use the theory of normal cycles from differ-ential geometry to define curvature tensors for a general classof surfaces, including smooth and polyhedral ones. More pre-cisely, we associate with each region a tensor which in thesmooth case is the average of the curvature tensor over thisregion. The curvature tensor of a polyhedral approximationof a smooth surface then provides an estimator of the one ofthe smooth surface. Our main result is a bound on the differ-ence between the estimated curvature and the actual one whenthe polyhedral approximation is chosen to be a Delaunay tri-angulation restricted to the surface. This case is important inpractice, in particular when the triangulation is obtained by aDelaunay-based surface reconstruction algorithm. Under a lo-cal uniformity condition on the sampling, this bound impliesthat our estimator converges linearly with respect to the sam-pling density. To the best of our knowledge, only weaker re-sults have been obtained in the past [19]. Our result can beviewed as a quantitative version of a theorem obtained by J.Fu[11] for gaussian and mean curvatures. This paper is organizedin four sections. We first introduce some notations and statethe theorem (section 1). Then we present the theory of normalcycles (section 2) and how they can be used to deal with curva-ture tensors (section 3), which is a contribution of this paper.The proof of the theorem, based on geometric measure theory,is sketched in section 4.1. STATEMENT OF THE THEOREMIn the sequel, we denote by M a surface in the three dimen-sional oriented euclidean space3. We assume for simplicitythat M is the boundary of some compact set V ⊂3.1.1 Curvature measuresLet us first recall some basic definitions and notations inthe case where M is smooth. A good reference for these is312[7]. The unit normal vector at a point p ∈ M pointing out-ward V will be refered t o as n(p). Note that M is therebyoriented. Given a vector v in the tangent plane TpM to Mat p, the derivati ve of n(p) in the direction v is orthogonal ton(p) as n(q) has unit length for any q ∈ M. The derivati veDpn of n at p thus defines an endomorphism of TpM, knownas the Weingarten endomorphism. The Weingarten endomor-phism can be shown to be symmetric ; the associated quadraticform is called the second fundamental form. Eigenvectors andeigenvalues of the Weingarten endomorphism are respectivelycalled principal directions and principal curvatures. Both prin-cipal curvatures can be recovered from the trace and determi-nant of Dpn, also called mean and gaussian curvature at p.Our result does not involve curvatures at a single point, butrather curvature measures, which we define here :DEFINIT ION 1. The gaussian curvature measure of M , φGV,is the function that associates with every (Borel) set B ⊂3the quantity :φGV(B)=B∩MG(p)dpwhere G(p) is the gaussian curvature of M at point p. Simi-larly, we define the mean curvature measure φHVby :φHV(B)=B∩MH(p)dpH(p) being the mean curvature of M at point p.Corresponding objects can be defined for triangulated sur-faces. Assume now that V is a polyhedron with vertex set Pand edge set E.DEFINIT ION 2. The discrete gaussian curvature measureof M, φGV, is the function that associates with every (Borel)set B ⊂3the quantity :φGV(B)=p∈B∩Pg(p) (1)where g(p) is the angle defect of M at point p, that is 2π minusthe sum of angles between consecutive edges incident on p.Similarly, we define the discrete mean curvature measure φHVby :φHV(B)=e∈Elength(e ∩ B)β(e) (2)|β(e)| being the angle between the normals to the triangles ofM incident on e. The sign of β(e) is chosen to be positive if eis convex and negative if it is concave.In section 2 we will see where these formulas come fromand why we use the same notation