“Implicit fairing of irregular meshes using diffusion and curvature flow” by Desbrun, Meyer, Schröder and Barr

In this paper, we develop methods to rapidly remove rough features from irregularly triangulated data intended to portray a smooth surface. The main task is to remove undesirable noise and uneven edges while retaining desirable geometric features. The problem arises mainly when creating high-fidelity computer graphics objects using imperfectly-measured data from the real world. Our approach contains three novel features: an implicit integration method to achieve efficiency, stability, and large time-steps; a scale-dependent Laplacian operator to improve the diffusion process; and finally, a robust curvature flow operator that achieves a smoothing of the shape itself, distinct from any parameterization. Additional features of the algorithm include automatic exact volume preservation, and hard and soft constraints on the positions of the points in the mesh. We compare our method to previous operators and related algorithms, and prove that our curvature and Laplacian operators have several mathematically-desirable qualities that improve the appearance of the resulting surface. In consequence, the user can easily select the appropriate operator according to the desired type of fairing. Finally, we provide a series of examples to graphically and numerically demonstrate the quality of our results.

1. Alan H. Barr. The Einstein Summation Notation: Introduction and Extensions. In SIGGRAPH 89 Course notes #30 on Topics in Physically-Based Modeling, pages J1-J12, 1989.
2. David Baraff and Andrew Witkin. Large Steps in Cloth Simulation. In SIGGRAPH 98 Conference P~vceedings, pages 43-54, July 1998.
3. Brian Curless and Marc Levoy. A Volumetric Method for Building Complex Models from Range Images. In SIGGRAPH 96 Conference P~vceedings, pages 303-312, 1996.
4. Tom Duchamp, Andrew Certain, Tony DeRose, and Wemer Stuetzle. Hierarchical computation of PL harmonic embeddings. Technical report, University of Washington, July 1997.
5. Mathieu Desbrun and Marie-Paule Cani-Gascuel. Active Implicit Surlace for Computer Animation. In Graphics Intelface (GI’98) P1vceedings, pages 143-150, Vancouver, Canada, 1998.
6. Bengt Fomberg. Generation of Finite Difference Formulas on Arbitrarily Spaced Grids. Math. Comput., 51:699-706, 1988.
7. Koji Fujiwara. Eigenvalues of Laplacians on a closed riemannian manifold and its nets. In P~vceedings of AMS 123, pages 2585-2594, 1995.
8. Igor Guskov, Wim Sweldens, and Peter Schr6der. Multiresolution Signal Processing for Meshes. In SIGGRAPH 99 Conference P1vceedings, 1999
9. Leif Kobbelt, Swen Campagna, Jens Vorsatz, and Hans-Peter Seidel. Interactive Multi-Resolution Modeling on Arbitrary Meshes. In SIGGRAPH 98 Conference P~vceedings, pages 105-114, July 1998.
10. Leif Kobbelt. Discrete Fairing. In P1vceedings of the Seventh IMA Conference on the Mathematics of Smfaces ’97, pages 101-131, 1997.
11. S. Lien and J. Kajiya. A Symbolic Method for Calculating the Integral Properties of Arbitrary Nonconvex Polyhedra. IEEE CG&A, 4(9), October 1984.
12. Roger B. Milne. An Adaptive Level-Set Method. PhD Thesis, University of California, Berkeley, December 1995.
13. Ulrich Pinkall and Konrad Polthier. Computing Discrete Minimal Surfaces and Their Conjugates. Experimental Mathematics, 2(1):15-36, 1993.
14. William Press, Saul Teukolsky, William Vetterling, and Brian Flannery. Numerical Recipes in C, second edition. Cambridge University Press, New York, USA, 1992.
15. James A. Sethian. Level-Set Methods: Evolving Intelfaces in Geometry, Fluid Dynamics, Computer Vision, and Material Science. Cambridge Monographs on Applied and Computational Mathematics, 1996.
16. Gabriel Taubin. A Signal Processing Approach to Fair Surface Design. In SIGGRAPH 95 Conference P1vceedings, pages 351-358, August 1995.
17. Demetri Terzopoulos. The Computation of Visible-Surface Representations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(4), July 1988.
18. Willian Welch and Andrew Witkin. Free-tbrm shape design using triangulated surfaces. In SIGGRAPH 94 Conference Proceedings, pages 247-256, July 1994.