“Mesh optimization” by Hoppe, DeRose, Duchamp, McDonald Jr. and Stuetzle

We present a method for solving the following problem: Given a set
of data points scattered in three dimensions and an initial triangular
mesh M0, produce a mesh M, of the same topological type as M0,
that fits the data well and has a small number of vertices. Our approach is to minimize an energy function that explicitly models the
competing desires of conciseness of representation and fidelity to
the data. We show that mesh optimization can be effectively used
in at least two applications: surface reconstruction from unorganized points, and mesh simplification (the reduction of the number
of vertices in an initially dense mesh of triangles).

1. Ruud M. Bolle and Baba C. Vemuri. On three-dimensional surface reconstruction methods. IEEE PAMI, 13(1): 1-13, January 1991.
2. T. DeRose, H. Hoppe, T. Duchamp, J. McDonald, and W. Stuetzle. Fitting of surfaces to scattered data. SPIE, 1830:212-220, 1992.
3. Gene Golub and Charles Van Loan. Matrix Computations. John Hopkins University Press, 2nd edition, 1989.
4. Ardeshir Goshtasby. Surface reconstruction from scattered measurements. SPIE, 1830:247-256, 1992.
5. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstruction from unorganized points. Computer Graphics (SIGGRAPH ’92 Proceedings), 26(2):71-78, July 1992.
6. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. TR 93-01-01, Dept. of Computer Science and Engineering, University of Washington, January 1993.
7. J.L. Mallet. Discrete smooth interpolation in geometric modeling. CAD, 24(4):178-191, April 1992.
8. Samuel Matin and Philip Smith. Parametric approximation of data using ODR splines. GMR 7057, General Motors Research Laboratories, May 1990.
9. J.V. Miller, D.E. Breen, W.E. Lorensen, R.M. O’Bara, and M.J. Wozny. Geometrically deformed models: A method for extracting closed geometric models from volume data. Computer Graphics (SIGGRAPH ’91 Proceedings), 25(4):217-226, July 1991.
10. William Schroeder, Jonathan Zarge, and William Lorensen. Decimation of triangle meshes. Computer Graphics (SIGGRAPH ’92 Proceedings), 26(2):65-70, July 1992.
11. R. B. Schudy and D. H. Ballard. Model detection of cardiac chambers in ultrasound images. Technical Report 12, Computer Science Department, University of Rochester, 1978.
12. R.B. Schudy and D. H. Ballard. Towards an anatomical model of heart motion as seen in 4-d cardiac ultrasound data. In Proceedings of the 6th Conference on Computer Applications in Radiology and Computer- Aided Analysis of Radiological Images, 1979.
13. Stan Sclaroff and Alex Pentland. Generalized implicit functions for computer graphics. Computer Graphics (SIGGRAPH ’91 Proceedings), 25(4):247-250, July 1991.
14. E.H. Spanier. Algebraic Topology. McGraw-Hill, New York, 1966.
15. Greg Turk. Re-filing polygonal surfaces. Computer Graphics (SIG- GRAPH ’92 Proceedings), 26(2):55-64, July 1992.
16. G. Wyvill, C. McPheeters, and B. Wyvill. Data structures for soft objects. The Visual Computer, 2(4):227-234, August 1986.