Real-time particle isosurface extraction

ABSTRACT

Particle-based methods are commonly used for simulation of fluid, gelatinous, and gooey substances. Recently, there has been great interest in using these methods in interactive applications such as surgical simulation, surface modeling, and video games. While modern computers are easily capable of simulating thousands of particles in real time, in many cases, a surface must be generated over the particles in order to realistically render the output of such a simulation. This surface extraction step is often the bottleneck in such applications due to the high computational cost and/or large memory requirements of common surface extraction algorithms. We present a new approach for fast, high quality polygonization of isosurfaces that can be used to render surfaces in real-time over thousands of particles in an unbounded spatial domain using a small amount of working memory, and compare it to existing algorithms. Furthermore, we extend our approach to generate polygon faces in back-to-front rendering order for transparent surfaces. Finally, we demonstrate the effectiveness of this new technique with several interactive scenarios showing complex interaction between fluid entities and dynamic objects in a virtual environment.

REFERENCES

• 1: Adams B., Lenaerts T., Dutré P.: Particle splatting: Interactive rendering of particle-based simulation data. Technical Report CW 453, Katholieke Universiteit Leuven (2006).
• 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: 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]
• 4: Hilton A., Illingworth J.: Marching triangles: Delaunay implicit surface triangulation. Technical Report CVSSP 01, University of Surrey (1997).
• 5: 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
• 6: Matthias Müller , David Charypar , Markus Gross, Particle-based fluid simulation for interactive applications, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 7: M. Müller , R. Keiser , A. Nealen , M. Pauly , M. Gross , M. Alexa, Point based animation of elastic, plastic and melting objects, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028542]
• 8: Matthias Müller , Simon Schirm , Matthias Teschner, Interactive blood simulation for virtual surgery based on smoothed particle hydrodynamics, Technology and Health Care, v.12 n.1, p.25-31, February 2004
• 9: Matthias Müller , Simon Schirm , Matthias Teschner , Bruno Heidelberger , Markus Gross, Interaction of fluids with deformable solids: Research Articles, Computer Animation and Virtual Worlds, v.15 n.3-4, p.159-171, July 2004 [doi>10.1002/cav.v15:3/4]
• 10: William T. Reeves, Particle systems—a technique for modeling a class of fuzzy objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.359-375, July 1983
• 11: Karl Sims, Particle animation and rendering using data parallel computation, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.405-413, Aug. 1990
• 12: Richard Szeliski , David Tonnesen, Surface modeling with oriented particle systems, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.185-194, July 1992
• 13: Teschner M., Heidelberger B., Müller M., Pomerantes D., Gross M. H.: Optimized spatial hashing for collision detection of deformable objects. Vision, Modeling, and Visualization (2003), 47--54.
• 14: Triquet F., Meseure P., Chaillou C.: Fast polygonization of implicit surfaces. WSCG (Plzen, Czech Republic) 2 (2001), 283--290.
• 15: 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]
• 16: Wyvill B., McPheeters C., Wyvill G.: Animating soft objects. The Visual Computer 2, 4 (1986), 235--242.
• 17: Wyvill G., McPheeters C., Wyvill B.: Data structure for soft objects. The Visual Computer 2, 4 (1986), 227--234.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development