Maintaining deforming surface meshes

ABSTRACT

We present a method to maintain a mesh approximating a deforming surface, which is specified by a dense set of sample points. We identify a reasonable motion model for which a provably good surface mesh can be maintained. Our algorithm determines the appropriate times at which the mesh is updated to maintain a good approximation. The updates use simple primitives, and no costly computation such as line-surface intersection is necessary. Point insertions and deletions are allowed at the updates. Each update takes time linear in the size of the current sample set plus the new sample points inserted. We also construct examples for which, under the same model, no other algorithm makes asymptotically fewer changes to the mesh than our algorithm.

REFERENCES

• 1: Pankaj K. Agarwal , Yusu Wang , Hai Yu, A 2D kinetic triangulation with near-quadratic topological changes, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997847]
• 2: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22 (1999), 481--504.
• 3: N. Amenta and T. K. Dey. Normal variation with adaptive feature size. A note as an erratum to Lemma 2 in {2}.
• 4: N. Amenta, S. Choi, T. K. Dey and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. Appl. 12 (2002), 125--141.
• 5: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 6: Jean-Daniel Boissonnat , Steve Oudot, Provably good sampling and meshing of surfaces, Graphical Models, v.67 n.5, p.405-451, September 2005 [doi>10.1016/j.gmod.2005.01.004]
• 7: Ho-Lun Cheng , Tamal K. Dey , Herbert Edelsbrunner , John Sullivan, Dynamic skin triangulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.47-56, January 07-09, 2001, Washington, D.C., United States
• 8: S.-W. Cheng and T. K. Dey. Delaunay flipping of dense surface triangulations. Manuscript, 2007. Available from authors' web-pages.
• 9: Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Tathagata Ray, Sampling and meshing a surface with guaranteed topology and geometry, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997861]
• 10: Tamal K. Dey, Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
• 11: Stefan Funke , Edgar A. Ramos, Smooth-surface reconstruction in near-linear time, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 06-08, 2002, San Francisco, California
• 12: James Glimm , John W. Grove , X. L. Li , D. C. Tan, Robust Computational Algorithms for Dynamic Interface Tracking in Three Dimensions, SIAM Journal on Scientific Computing, v.21 n.6, p.2240-2256, Dec 1999 [doi>10.1137/S1064827598340500]
• 13: Leonidas J. Guibas, Kinetic data structures: a state of the art report, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.191-209, August 1998, Houston, Texas, United States
• 14: S. Pandya, B. Z. Gao, and N. H. C. Hwang. Bioprosthetic heart valve leaflet deformation monitored by double pulse stereo photogrammetry. Proc. First Joint BMES/EMBS Conference, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory