Free-form shape design using triangulated surfaces

ABSTRACT

We present an approach to modeling with truly mutable yet completely controllable free-form surfaces of arbitrary topology. Surfaces may be pinned down at points and along curves, cut up and smoothly welded back together, and faired and reshaped in the large. This style of control is formulated as a constrained shape optimization, with minimization of squared principal curvatures yielding graceful shapes that are free of the parameterization worries accompanying many patch-based approaches. Triangulated point sets are used to approximate these smooth variational surfaces, bridging the gap between patch-based and particle-based representations. Automatic refinement, mesh smoothing, and re-triangulation maintain a good computational mesh as the surface shape evolves, and give sample points and surface features much of the freedom to slide around in the surface that oriented particles enjoy. The resulting surface triangulations are constructed and maintained in real time.

REFERENCES

• 1: Timothy Barth. Higher order solution of the euler equations on unstructured grids using quadratic reconstruction. In 28th Aerospace Sciences Meeting. AIAA-90-0013, 1990.
• 2: Marshall Bern and David Eppstein. Mesh generation and opti-mal triangulation. Technical Report CSL-92-1, XEROX Palo Alto Research Center, March 1992.
• 3: D.L. Bonner, M.J. Jakiela, M. Watanabe, and N. Kishi. Pseu-doedge: nonintersected parametric quilt modeling of multiply connected objects. Computer Aided Design, 25(7):438-452, July 1993.
• 4: George Celniker , Dave Gossard, Deformable curve and surface finite-elements for free-form shape design, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.257-266, July 1991
• 5: George Celniker , Will Welch, Linear constraints for deformable non-uniform B-spline surfaces, Proceedings of the 1992 symposium on Interactive 3D graphics, p.165-170, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147191]
• 6: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 7: R. Courant and D. Hilbert. Methods of Mathematical Physics, volume volume I. Wiley, 1937.
• 8: M. Eppstein. On the influence of parameterization in paramet-ric interpolation. SIAM J. Numer. Anal., 13:261-268, 1976.
• 9: G. Farin, Curves and surfaces for computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1990
• 10: Helaman Ferguson , Alyn Rockwood , Jordan Cox, Topological design of sculptured surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.149-156, July 1992
• 11: D. A. Field. Laplacian smoothing and delaunay triangulations. Comm. Appl. Numer. Methods, 4:709-712, 1984.
• 12: G. Forsythe and W. Wasow. Finite Difference Methods for Partial Differential Equations, chapter 19, pages 179-182. John Wiley and Sons, 1960.
• 13: Richard Franke and Gregory Nielson. Scattered data inter-polation and applications: a tutorial and survey. In Hans Ha-gen and Dieter Roller, editors, Geometric Modeling. Springer-Verlag, 1991.
• 14: Gene Golub and Charles Van Loan. Matrix Computations. Johns Hopkins University Press, 1989.
• 15: Victor Guillemin and Alan Pollack. Differential Topology. Prentice-Hall, 1974.
• 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: Geertjan Huiskamp, Difference formulas for the surface Laplacian on a triangulated surface, Journal of Computational Physics, v.95 n.2, p.477-496, Aug. 1991 [doi>10.1016/0021-9991(91)90286-T]
• 18: Michael Kallay. Constrained optimization in surface design. In Modeling in Computer Graphics. Springer Verlag, 1993.
• 19: Michael Kass, Andrew Witkin, and Dimetri Terzopoulos. Snakes: Active contour models. International Journal Com-puter Vision, 1(4), 1987.
• 20: N. J. Lott , D. I. Pullin, Method for fairing B-spline surfaces, Computer-Aided Design, v.20 n.10, p.597-604, December 1988 [doi>10.1016/0010-4485(88)90206-0]
• 21: Steve Mann, Charles Loop, Michael Lounsbery, D. Meyers, J. Painter, Tony Derose, and K. Sloan. A survey of parametric scattered data fitting using triangular interpolants. In Curve and Surface Modeling. SIAM.
• 22: 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
• 23: Henry Packard Moreton, Minimum curvature variation curves, networks, and surfaces for fair free-form shape design, University of California at Berkeley, Berkeley, CA, 1992
• 24: Gregory Nielson. A transfinite, visually continuous, triangu-lar interpolant. In Gerald Farin, editor, Geometric Modelling, pages 235-246. SIAM, 1987.
• 25: Barrett O'Neill. Elementary Differential Geometry. Academic Press, 1966.
• 26: J~ org Peters. Smooth interpolation of a mesh of curves. Con-structive Approximation, 7:221-246, 1991.
• 27: J. C. Platt, Constraint methods for neural networks and computer graphics, California Institute of Technology, Pasadena, CA, 1990
• 28: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.145-152, July 1987
• 29: M. M. Rai and D. A. Anderson. Application of adaptive grids to fluid-flow problems with asymptotic solutions. AIAA J., 20:496-502, 1982.
• 30: D.G. Schweikert. An interpolation curve using a spline in ten-sion. Journal of Math and Phys., 45:312-317, 1966.
• 31: Thomas W. Sederberg , Eugene Greenwood, A physically based approach to 2–D shape blending, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.25-34, July 1992
• 32: Michael Spivak. A Comprehensive Introduction to Differential Geometry. Publish or Perish, Inc., 1979.
• 33: Gilbert Strang. Introduction to Applied Mathematics. Wellesley-Cambridge Press, 1986.
• 34: Richard Szeliski , David Tonnesen, Surface modeling with oriented particle systems, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.185-194, July 1992
• 35: D. Terzopoulos. Multi-level reconstruction of visual surfaces. MIT Artificial Intelligence Memo Number 671, April 1981.
• 36: Joe F. Thompson , Z. U.A. Warsi , C. Wayne Mastin, Numerical grid generation: foundations and applications, Elsevier North-Holland, Inc., New York, NY, 1985
• 37: Joe F. Thompson. A survey of dynamically-adaptive grids in the numerical solution of partial differential equations. Ap-plied Numerical Mathematics, 1:3-27, 1985.
• 38: Greg Turk, Generating textures on arbitrary surfaces using reaction-diffusion, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.289-298, July 1991
• 39: Greg Turk, Re-tiling polygonal surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.55-64, July 1992
• 40: William Welch. Free-Form shape design using triangulated surfaces. PhD thesis, Carnegie Mellon University, (in prepa-ration) 1994.
• 41: William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992
• 42: 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]

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

General Terms:
Design, Theory

Keywords:
Delaunay triangulation, adaptive meshing, fair surface design, functional minimization, polygonal models