Dynamic triangulation of variational implicit surfaces using incremental Delaunay tetrahedralization

ABSTRACT

In this paper, we present a novel method to triangulate variational implicit surfaces. The core of the algorithm is an incremental Delaunay tetrahedralization of the constraint points defining the surface; it can be refined over time by adding new points around the surface as needed. Each tetrahedron that crosses the surface can then be triangulated to locally approximate the surface. This method allows getting several meshes of the same shape at different resolutions, which can be updated dynamically when adding new constraint points. This level-of-detail property makes variational surfaces more appealing for applications such as interactive modeling.

REFERENCES

• 1: Akkouche, S., and Galin, E. 2001. Adaptive implicit surface polygonization using marching triangles. Computer Graphic Forum 20, 2, 67-80.
• 2: James F. Blinn, A Generalization of Algebraic Surface Drawing, ACM Transactions on Graphics (TOG), v.1 n.3, p.235-256, July 1982 [doi>10.1145/357306.357310]
• 3: Jules Bloomenthal , Ken Shoemake, Convolution surfaces, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.251-256, July 1991
• 4: Jules Bloomenthal , Brian Wyvill, Interactive techniques for implicit modeling, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.109-116, Mar. 1990
• 5: Jules Bloomenthal , Brian Wyvill, Introduction to Implicit Surfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 6: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1]
• 7: Jules Bloomenthal, An implicit surface polygonizer, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 8: Boissonnat, J.-D., Devillers, O., and Teillaud, M. 1990. A dynamic construction of higher-order Voronoi diagrams and its randomized analysis. Tech. Rep. 1207, INRIA.
• 9: Crespin, B., Guitton, P., and Schlick, C. 1998. Efficient and accurate tessellation of implicit sweeps. In Proc. of CSG'98 (Set-theoretic Solid Modelling Techniques and Applications), I. Geometers, Ed., 49-63.
• 10: Desbrun, M., Tsingos, N., and Gascuel, M.-P. 1995. Adaptive sampling of implicit surfaces for interactive modeling and animation. In Implicit Surfaces'95 Proceedings, Eurographics, 171-185.
• 11: Duchon, J. 1977. Spline minimizing rotation-invariant seminorms in sobolev spaces. In Constructive Theory of Functions of Several Variables, W. Schempp and K. Zeller, Eds., vol. 571, 85-100.
• 12: Mark Hall , Joe Warren, Adaptive Polygonalization of Implicitly Defined Surfaces, IEEE Computer Graphics and Applications, v.10 n.6, p.33-42, November 1990 [doi>10.1109/38.62694]
• 13: Hartmann, E. 1998. A marching method for the triangulation of surfaces. The Visual Computer 14, 3, 95-108.
• 14: Hilton, A., Stoddart, A., Illingworth, J., and Windeatt, T. 1996. Marching triangles: Range image fusion for complex object modeling. In International Conference on Image Processing.
• 15: Tasso Karkanis , A. James Stewart, Curvature-Dependent Triangulation of Implicit Surfaces, IEEE Computer Graphics and Applications, v.21 n.2, p.60-69, March 2001 [doi>10.1109/38.909016]
• 16: 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
• 17: Bryan S. Morse , Terry S. Yoo , David T. Chen , Penny Rheingans , K. R. Subramanian, Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions, Proceedings of the International Conference on Shape Modeling & Applications, p.89, May 07-11, 2001
• 18: Paul Ning , Jules Bloomenthal, An Evaluation of Implicit Surface Tilers, IEEE Computer Graphics and Applications, v.13 n.6, p.33-41, November 1993 [doi>10.1109/38.252552]
• 19: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 20: Rodrian, H.-C., and Moock, H. 1996. Dynamic triangulation of animated skeleton-based implicit surfaces. In Implicit Surfaces'96 Proceedings, Eurographics, 37-52.
• 21: Shewchuk, J. R., 1999. Lecture notes on delaunay mesh generation (available on citeseer.nj.nec.com/shewchuk99lecture.html).
• 22: Shu, R., Zhou, C., and Kankanhalli, M. 1995. Adaptive marching cubes. The Visual Computer 11, 4, 202-217.
• 23: Richard Szeliski , David Tonnesen, Surface modeling with oriented particle systems, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.185-194, July 1992
• 24: Turk, G., and O'Brien, J. F. 1999. Variational implicit surfaces. Tech. Rep. GIT-GVU-99-15, Georgia Institute of Technology.
• 25: Greg Turk , Huong Quynh Dinh , James F. O'Brien , Gary Yngve, Implicit Surfaces that Interpolate, Proceedings of the International Conference on Shape Modeling & Applications, p.62, May 07-11, 2001
• 26: van Overveld, C., and Wyvill, B. 1993. Shrinkwrap: an adaptive algorithm for polygonizing and implicit surface. Tech. rep., University of Calgary.
• 27: Luiz Velho , Luiz Henrique de Figueiredo , Jonas Gomes, A unified approach for hierarchical adaptive tesselation of surfaces, ACM Transactions on Graphics (TOG), v.18 n.4, p.329-360, Oct. 1999 [doi>10.1145/337680.337717]
• 28: 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]
• 29: Wu, S.-T., and de Gomensoro Malheiros, M. 1999. On improving the search for critical points of implicit functions. In Implicit Surfaces.
• 30: Wyvill, G., McPheeters, C., and Wyvill, B. 1986. Data structure for soft objects. The Visual Computer 2, 4, 227-234.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

Keywords:
geometric modelling, iso-surface extraction