Using particles to sample and control implicit surfaces

ABSTRACT

We present a new particle-based approach to sampling and controlling implicit surfaces. A simple constraint locks a set of particles onto a surface while the particles and the surface move. We use the constraint to make surfaces follow particles, and to make particles follow surfaces. We implement control points for direct manipulation by specifying particle motions, then solving for surface motion that maintains the constraint. For sampling and rendering, we run the constraint in the order direction, creating floater particles that roam freely over the surface. Local repulsion is used to make floaters spread evenly across the surface. By varying the radius of repulsion adaptively, and fissioning or killing particles based on the local density, we can achieve good sampling distributions very rapidly, and maintain them even in the face of rapid and extreme deformations and changes in surface topology.

REFERENCES

• 1: Chandrajit Bajaj , Insung Ihm , Joe Warren, Higher-order interpolation and least-squares approximation using implicit algebraic surfaces, ACM Transactions on Graphics (TOG), v.12 n.4, p.327-347, Oct. 1993 [doi>10.1145/159730.159734]
• 2: D. Baraff, Analytical methods for dynamic simulation of non-penetrating rigid bodies, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.223-232, July 1989
• 3: David Baraff, Curved surfaces and coherence for non-penetrating rigid body simulation, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.19-28, Aug. 1990
• 4: David Baraff , Andrew Witkin, Dynamic simulation of non-penetrating flexible bodies, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.303-308, July 1992
• 5: Ronen Barzel , Alan H. Barr, A modeling system based on dynamic constraints, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.179-188, Aug. 1988
• 6: J. Baumgarte. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics, 1972.
• 7: Thaddeus Beier. Practical uses for implicit surfaces in an-imation. In Modeling, Visualizing, and Animating Implicit Surfaces (SIGGRAPH '93 Course Notes), pages 20.1-20.10. 1993.
• 8: 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]
• 9: 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]
• 10: Jules Bloomenthal, An implicit surface polygonizer, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 11: Jules Bloomenthal , Brian Wyvill, Interactive techniques for implicit modeling, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.109-116, Mar. 1990
• 12: 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
• 13: Phillip Gill, Walter Murray, and Margret Wright. Practical Optimization. Academic Press, New York, NY, 1981.
• 14: Michael Gleicher , Andrew Witkin, Through-the-lens camera control, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.331-340, July 1992
• 15: Herbert Goldstein. Classical Mechanics. Addision Wesley, Reading, MA, 1950.
• 16: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
• 17: David J. Jevans, Brian Wyvill, and Geoff Wyvill. Speeding up 3-D animation for simulation. In Proc. MAPCON IV (Multi and Array Processors), pages 94-100, Jan. 1988.
• 18: 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
• 19: Henry P. Moreton , Carlo H. Séquin, Functional optimization for fair surface design, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.167-176, July 1992
• 20: Shigeru Muraki, Volumetric shape description of range data using “Blobby Model”, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.227-235, July 1991
• 21: 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]
• 22: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.145-152, July 1987
• 23: W.H. Press, B.P. Flannery, S. A. Teukolsky, and W. T. Vetter-ling. Numerical Recipes in C. Cambridge University Press, Cambridge, England, 1988.
• 24: A. Ricci. A constructive geometry for computer graphics. Computer Journal, 16(2):157-160, May 1973.
• 25: T. Sederberg. Piecewise algebraic surface patches. Computer Aided Geometric Design, 2(1-3):53-60, 1985.
• 26: John M. Snyder, Generative modeling for computer graphics and CAD: symbolic shape design using interval analysis, Academic Press Professional, Inc., San Diego, CA, 1992
• 27: Richard Szeliski , David Tonnesen, Surface modeling with oriented particle systems, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.185-194, July 1992
• 28: Greg Turk, Generating textures on arbitrary surfaces using reaction-diffusion, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.289-298, July 1991
• 29: Greg Turk, Re-tiling polygonal surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.55-64, July 1992
• 30: William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992
• 31: Andrew Witkin , Michael Gleicher , William Welch, Interactive dynamics, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.11-21, Mar. 1990
• 32: Andrew Witkin , William Welch, Fast animation and control of nonrigid structures, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.243-252, September 1990, Dallas, TX, USA [doi>10.1145/97879.565650]
• 33: Brian Wyvill, Craig McPheeters, and Geoff Wyvill. Data struc-ture for soft objects. The Visual Computer, 2(4):227-234, 1986.

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

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

General Terms:
Algorithms, Design, Theory

Keywords:
adaptive sampling, constrained optimization, interaction, physically based modeling