Twinned meshes for dynamic triangulation of implicit surfaces

ABSTRACT

We introduce a new approach to mesh an animated implicit surface for rendering. Our contribution is a method which solves stability issues of implicit triangulation, in the scope of real-time rendering. This method is robust, moreover it provides interactive and quality rendering of animated or manipulated implicit surfaces.

This approach is based on a double triangulation of the surface, a mechanical one and a geometric one. In the first triangulation, the vertices are the nodes of a simplified mechanical finite element model. The aim of this model is to uniformly and dynamically sample the surface. It is robust, efficient and prevents the inversion of triangles. The second triangulation is dynamically created from the first one at each frame. It is used for rendering and provides details in regions of high curvature. We demonstrate this technique with skeleton-based and volumetric animated surfaces.

REFERENCES

• 1: Ricardo S. Avila , Lisa M. Sobierajski, A haptic interaction method for volume visualization, Proceedings of the 7th conference on Visualization '96, p.197-ff., October 28-29, 1996, San Francisco, California, United States
• 2: Randolph E. Bank, Andrew H. Sherman, and Alan Weiser. Refinement Algorithms and Data Structures for Regular Local Mesh Refinement. 1983.
• 3: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 4: Adam W. Bargteil , Tolga G. Goktekin , James F. O'brien , John A. Strain, A semi-Lagrangian contouring method for fluid simulation, ACM Transactions on Graphics (TOG), v.25 n.1, p.19-38, January 2006 [doi>10.1145/1122501.1122503]
• 5: F. Bornemann and R. Erdmann, B. and Kornhuber. Adaptive multilevel-methods in three space dimensions. Intl. J. for Numer. Meth. in Eng., 1993.
• 6: Antoine Bouthors and Fabrice Neyret. Modeling clouds shape. In E. Galin M. Alexa, editor, Eurographics (short papers), august 2004.
• 7: Marie-Paule Cani. Implicit representations in computer animation: a compared study. In Proceedings EUROGRAPHICS Workshop on Implicit Surfaces'99, 1999.
• 8: Patricia Crossno , Edward Angel, Isosurface extraction using particle systems, Proceedings of the 8th conference on Visualization '97, p.495-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 9: Patricia Crossno , Edward Angel, Spiraling edge: fast surface reconstruction from partially organized sample points, Proceedings of the conference on Visualization '99: celebrating ten years, p.317-324, October 1999, San Francisco, California, United States
• 10: Bruno Rodrigues de Araujo , Joaquim Armando Pires Jorge, Curvature Dependent Polygonization of Implicit Surfaces, Proceedings of the Computer Graphics and Image Processing, XVII Brazilian Symposium on (SIBGRAPI'04), p.266-273, October 17-20, 2004
• 11: Luiz Henrique de Figueiredo , Jonas de Miranda Gomes , Demetri Terzopoulos , Luiz Velho, Physically-based methods for polygonization of implicit surfaces, Proceedings of the conference on Graphics interface '92, p.250-257, September 1992, Vancouver, British Columbia, Canada
• 12: Tamal K. Dey, Herbert Edelsbrunner, Sumanta Guha, and Dmitry V. Nekhayev. Topology preserving edge contraction. Publications de l' Institut Mathematique (Beograd), 1999.
• 13: Eric Ferley, Marie-Paule Cani, and Jean-Dominique Gascuel. Practical volumetric sculpting. The Visual Computer, 2000.
• 14: Markus Hadwiger, Christian Sigg, Henning Scharsach, Khatja Bühler, and Markus Gross. Real-time ray-casting and advanced shading of discrete isosurfaces. Computer Graphics Forum, 2005.
• 15: John C. Hart, Antoinne Durr, and Douglas Harsh. Critical points of polynomial metaballs. In Proceedings of Implicit Surfaces '98, pages 69--76, June 1998.
• 16: Chien.-Chang Ho, Fu-Che Wu, Bing-Yu Chen, Yung-Yu Chuang, and Ming Ouhyoung. Cubical marching squares: Adaptive feature preserving surface extraction from volume data. Computer Graphics Forum, 24(3):537--546, September 2005.
• 17: G. Irving , J. Teran , R. Fedkiw, Invertible finite elements for robust simulation of large deformation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028541]
• 18: Xiangmin Jiao, Andrew Colombi, Xinlai Ni, and John C. Hart. Anisotropic mesh adaptation for evolving triangulated surfaces. In Meshing Roundtable, pages 173--190, 2006.
• 19: Takashi Kanai , Yutaka Ohtake , Hiroaki Kawata , Kiwamu Kase, GPU-based rendering of sparse low-degree implicit surfaces, Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia, November 29-December 02, 2006, Kuala Lumpur, Malaysia [doi>10.1145/1174429.1174455]
• 20: Florian Levet , Xavier Granier , Christophe Schlick, Fast Sampling of Implicit Surfaces by Particle Systems, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006 (SMI'06), p.39, June 14-16, 2006 [doi>10.1109/SMI.2006.13]
• 21: Florian Levet, Julien Hadim, Patrick Reuter, and Christophe Schlick. Anisotropic sampling for differential point rendering of implicit surfaces. In Proceedings of the Winter School of Computer Graphics'05, 2005.
• 22: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 23: Lee Markosian , Jonathan M. Cohen , Thomas Crulli , John Hughes, Skin: a constructive approach to modeling free-form shapes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.393-400, July 1999 [doi>10.1145/311535.311595]
• 24: John Willard Milnor. Topology from the Differentiable Viewpoint. University Press of Virginia, 1965.
• 25: Matthias Müller , Julie Dorsey , Leonard McMillan , Robert Jagnow , Barbara Cutler, Stable real-time deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545269]
• 26: M. Nesme, Y. Payan, and F. Faure. Efficient, physically plausible finite elements. In Eurographics (short papers), 2005.
• 27: Yutaka Ohtake, Alexander Belyaev, and Alexander Pasko. Dynamic mesh optimization for polygonized implicit surfaces with sharp features. The Visual Computer, 19(2):115--126, 2003.
• 28: Hans-Christian Rodrian and Hardy Moock. Dynamic triangulation of animated skeleton-based implicit surfaces. In Proceedings of the EUROGRAPHICS Workshop on Implicit Surfaces'96, 1996.
• 29: 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]
• 30: Andrew P. Witkin , Paul S. Heckbert, Using particles to sample and control implicit surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.269-277, July 1994 [doi>10.1145/192161.192227]
• 31: Brian Wyvill, Craig McPheeters, and Geoff Wyvill. Data structure for soft objects. The Visual Computer, 2(4):227--234, 1986.

INDEX TERMS

Keywords:
implicit surfaces, real-time, triangulation