Eurographics Symposium on Geometry Processing (2003)L. Kobbelt, P. Schröder, H. Hoppe (Editors)Estimating Differential QuantitiesUsing Polynomial Fitting of Osculating JetsF. Cazals†, and M. Pouget‡AbstractThis paper addresses the pointwise estimation of differential properties of a smooth manifold S —a curve in theplane or a surface in 3D— assuming a point cloud sampled over S is provided. The method consists of fittingthe local representation of the manifold using a jet, by either interpolating or approximating. A jet is a truncatedTaylor expansion, and the incentive for using jets is that they encode all local geometric quantities —such asnormal or curvatures.On the way to using jets, the question of estimating differential properties is recasted into the more general frame-work of multivariate interpolation/approximation, a well-studied problem in numerical analysis. On a theoreticalperspective, we prove several convergence results when the samples get denser. For curves and surfaces, theseresults involve asymptotic estimates with convergence rates depending upon the degree of the jet used. For theparticular case of curves, an error bound is also derived. To the best of our knowledge, these results are amongthe first ones providing accurate estimates for differential quantities of order three and more. On the algorithmicside, we solve the interpolation/approximation problem using Vandermonde systems. Experimental results for sur-faces of R3are reported. These experiments illustrate the asymptotic convergence results, but also the robustnessof the methods on general Computer Graphics models.Keywords. Meshes, Point Clouds, Differential Geometry,Interpolation, Approximation.1. Introduction1.1. Estimating differential quantitiesSeveral applications from Computer Vision, ComputerGraphics, Computer Aided Design or Computational Ge-ometry requires estimating local differential quantities. Ex-ample such applications are surface segmentation, surfacesmoothing / denoising, surface reconstruction, shape design.In any case, the input consists of a point cloud or a mesh.Most of the time, estimating first and second order differ-ential quantities, that is the tangent plane and curvature-related quantities, is sufficient. However, applications in-volving shape analysis16, 26require estimating third orderdifferential quantities.†INRIA Sophia-Antipolis, 2004 route des Lucioles, F-06902Sophia-Antipolis; [email protected]‡INRIA Sophia-Antipolis, 2004 route des Lucioles, F-06902Sophia-Antipolis; [email protected] first to third order differential quantities, a wealth ofdifferent estimators can be found in the vast literature ofapplied geometry24. Most of these are adaptations to thediscrete setting of smooth differential geometry results. Forexample, several definitions of normals, principal directionsand curvatures over a mesh can be found in32, 9. Ridges ofpolyhedral surfaces as well as cuspidal edges of the focalsets are computed in33. Geodesics and discrete versions ofthe Gauss-Bonnet theorem are considered in25.A striking fact about estimation of second order differ-ential quantities —using conics and quadrics—- is that theclassification of Euclidean conics/quadrics is never men-tioned. Another prominent feature is that few contributionsaddress the question of the accuracy of these estimates orthat of their convergence when the mesh or the sample pointsget denser. The question of convergence is one prime impor-tance since estimates do not always asymptotically behaveas one would expect. For example, it is proved in4that theangular defect of triangulations does not in general provideinformation on the Gauss curvature of the underlying smoothsurface.The following are provably good approximation results.c The Eurographics Association 2003.177Cazals and Pouget / Estimating Differential QuantitiesUsing Polynomial Fitting of Osculating JetsIn1, an error bound is proved on the normal estimate to asmooth surface sampled according to a criterion involvingthe skeleton. The surface area of a mesh and its normal vec-tor field versus those of a smooth surface are considered in23. Asymptotic estimates for the normal and the Gauss cur-vature of a sampled surface for several methods are givenin22. In particular, a degree two interpolation is analyzed.Based upon the normal cycle and restricted Delaunay trian-gulations, an estimate for the second fundamental form of asurface is developed in8.Deriving provably good differential operators is the goalpursued in this paper. To motivate our guideline and beforepresenting our contributions, we raise the following ques-tion. Second order differential properties for plane curves arealmost always investigated using the osculating circle, whileprincipal curvatures of surfaces are almost always computedusing osculating paraboloids. Why not osculating parabolasfor curves and osculating ellipsoids or hyperboloids for sur-faces? Before answering this question and to clarify the pre-sentation, we recall some fundamentals.1.2. Curves and surfaces, height functions and jetsIt is well known10, 31that any regular embedded smoothcurve or surface can be locally written as the graph of a uni-variate or bivariate function with respect to any z directionthat does not belong to the tangent space. We shall call sucha function a height function. Taking an order n Taylor expan-sion of the height function over a curve yields:f (x) = JB,n(x) + O(xn+1), (1)withJB,n(x) = B0+ B1x + B2x2+ B3x3+ ... + Bnxn. (2)Similarly for a surface:f (x,y) = JB,n(x,y) + O(||(x,y)||n+1), (3)withJB,n(x,y) =n∑k=1HB,k(x,y), HB,k(x,y) =k∑j=0Bk−j, jxk−jyj.(4)Borrowing to the jargon of singularity theory5, the trun-cated Taylor expansion JB,n(x) or JB,n(x,y) is called a de-gree n jet, or n-jet. Since the differential properties of a n-jet matches those of its defining curve/surface up to ordern, the jet is said to have a n order contact with its definingcurve or surface. This also accounts for the term osculatingjet —although osculating was initially meant for 2-jets. Thedegree n-jet of a curve involves n + 1 terms. For a surface,since there are i+1 monomials of degree i, the n-jet involvesNn= 1 + 2 + ··· + (n + 1) = (n + 1)(n + 2)/2 terms. Noticethat when z direction used is aligned with the normal vec-tor to the curve/surface, one has B1= 0 or B10= B01= 0.The osculating n-jet encloses differential properties of thecurve/surface up to order n, that is any