Isotopic implicit surface meshing

ABSTRACT

This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. Then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. This is the first algorithm achieving this goal in a provably correct way.

REFERENCES

• 1: A. A. Agrachev , D. Pallaschke , S. Scholtes, On Morse Theory for Piecewise Smooth Functions, Journal of Dynamical and Control Systems, v.3 n.4, p.449-469, October 1997 [doi>10.1023/A:1021810206861]
• 2: Th. Banchoff, Critical points and curvature for embedded polyhedra, J. Diff. Geom 1 (1967) 245--256.
• 3: Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
• 4: Jules Bloomenthal , Brian Wyvill, Introduction to Implicit Surfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 5: F. Chazal and D. Cohen-Steiner, A condition for isotopic approximation, submitted. Available at : ftp://ftp-sop. inria. fr/prisme/dcohen/Papers/isotopie. ps
• 6: David P. Dobkin , Allan R. Wilks , Silvio V. F. Levy , William P. Thurston, Contour tracing by piecewise linear approximations, ACM Transactions on Graphics (TOG), v.9 n.4, p.389-423, Oct. 1990 [doi>10.1145/88560.88575]
• 7: A. Dold, Lectures on algebraic topology, Springer 1972.
• 8: Herbert Edelsbrunner , John Harer , Afra Zomorodian, Hierarchical morse complexes for piecewise linear 2-manifolds, Proceedings of the seventeenth annual symposium on Computational geometry, p.70-79, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378626]
• 9: H. Edelsbrunner, Surface reconstruction by wrapping finite point sets in space, Ricky Pollack and Eli Goodman Festschrift, ed. B. Aronov, S. Basu, J. Pach and M. Sharir, Springer-Verlag, to appear.
• 10: M. Goresky and R. MacPherson, Stratified Morse Theory, Springer Verlag, 1988.
• 11: D. Gottlieb and G. Samaranayake, The index of discontinuous vector fields, New-York Journal of Mathematics, 1, pp 130--148, 1995.
• 12: A. Hatcher, Algebraic topology, Cambridge University Press, 2002. http://www. math. cornell. edu/ hatcher.
• 13: M. Hirsch, Differential Topology, Springer Verlag, 1976.
• 14: Adriano Lopes , Ken Brodlie, Improving the Robustness and Accuracy of the Marching Cubes Algorithm for Isosurfacing, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.16-29, January 2003 [doi>10.1109/TVCG.2003.1175094]
• 15: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 16: J. Milnor, Morse theory, Ann. of Math. studies 51, Princeton University Press, Princeton N. J. 1963.
• 17: Barton T. Stander , John C. Hart, Guaranteeing the topology of an implicit surface polygonization for interactive modeling, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.279-286, August 1997 [doi>10.1145/258734.258868]
• 18: C. P. Rourke and B. J. Sanderson, Introduction to Piecewise-Linear Topology, Springer-Verlag, 1982.
• 19: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 20: A. Sard, The measure of the critical values of differentiable maps, Bull. Amer. Math. Soc. 48 (1942), 883--890.
• 21: J. R. Shewchuk, What Is a Good Linear Finite Element? Interpolation, Conditioning, Anisotropy, and Quality Measures, in preparation.
• 22: John M. Snyder, Interval analysis for computer graphics, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.121-130, July 1992
• 23: L. Velho , L. H. de Figueiredo , J. Anthony Gomes, Implicit Objects in Computer Graphics, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 24: Luiz Velho, Simple and efficient polygonization of implicit surfaces, Journal of Graphics Tools, v.1 n.2, p.5-24, February 1996

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

General Terms:
Algorithms, Theory

Keywords:
computational topology, meshing, morse theory