Dynamic NURBS with geometric constraints for interactive sculpting

ABSTRACT

This article develops a dynamic generalization of the nonuniform rational B-spline (NURBS) model. NURBS have become a defacto standard in commercial modeling systems because of their power to represent free-form shapes as well as common analytic shapes. To date, however, they have been viewed as purely geometric primitives that require the user to manually adjust multiple control points and associated weights in order to design shapes. Dynamic NURBS, or D-NURBS, are physics-based models that incorporate mass distributions, internal deformation energies, and other physical quantities into the popular NURBS geometric substrate. Using D-NURBS, a modeler can interactively sculpt curves and surfaces and design complex shapes to required specifications not only in the traditional indirect fashion, by adjusting control points and weights, but also through direct physical manipulation, by applying simulated forces and local and global shape constraints. D-NURBS move and deform in a physically intuitive manner in response to the user's direct manipulations. Their dynamic behavior results from the numerical integration of a set of nonlinear differential equations that automatically evolve the control points and weights in response to the applied forces and constraints. To derive these equations, we employ Lagrangian mechanics and a finite-element-like discretization. Our approach supports the trimming of D-NURBS surfaces using D-NURBS curves. We demonstrate D-NURBS models and constraints in applications including the rounding of solids, optimal surface fitting to unstructured data, surface design from cross sections, and free-form deformation. We also introduce a new technique for 2D shape metamorphosis using constrained D-NURBS surfaces.

REFERENCES

• 1: B^UMGARTE, J. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Comput. Meth. Appl. Mech. Eng. 1, 1, 1-16.
• 2: M. I. G. Bloor , M. J. Wilson, Representing PDE surfaces in terms of B-splines, Computer-Aided Design, v.22 n.6, p.324-331, July/August 1990 [doi>10.1016/0010-4485(90)90083-O]
• 3: M. I. G. Bloor , M. J. Wilson, Using partial differential equations to generate free-form surfaces: 91787, Computer-Aided Design, v.22 n.4, p.202-212, May 1990 [doi>10.1016/0010-4485(90)90049-I]
• 4: Wolfgang Böhm , Gerald Farin , Jürgen Kahmann, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, v.1 n.1, p.1-60, July 1984 [doi>10.1016/0167-8396(84)90003-7]
• 5: 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
• 6: 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]
• 7: J. E. Chadwick , D. R. Haumann , R. E. Parent, Layered construction for deformable animated characters, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.243-252, July 1989
• 8: Shenchang Eric Chen , Richard E. Parent, Shape Averaging and it's Applications to Industrial Design, IEEE Computer Graphics and Applications, v.9 n.1, p.47-54, January 1989 [doi>10.1109/38.20333]
• 9: DE BOOR, C. 1972. On calculating with B-Splines. J. Approx. Theor. 6, 1, 50-62.
• 10: Gerald Farin, From Conics to NURBS: A Tutorial and Survey, IEEE Computer Graphics and Applications, v.12 n.5, p.78-86, September 1992 [doi>10.1109/38.156017]
• 11: G. Farin, Curves and surfaces for computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1990
• 12: G. Farin, Trends in curve and surface design, Computer-Aided Design, v.21 n.5, p.293-296, June 1989 [doi>10.1016/0010-4485(89)90035-3]
• 13: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.205-212, Aug. 1988
• 14: G(~SSiCK, B.R. 1967. Hamilton's Principle and Physical Systems. Academic Press, New York.
• 15: Hayrettin Kardestuncer , Douglas H. Norrie, Finite element handbook, McGraw-Hill, Inc., New York, NY, 1987
• 16: KAUL, A. AND ROSSI(;NAC, J. 1991. Solid interpolating deformations: Construction and animation of PIPs. In Proceedings of Eurographics '91, F.H. Post and W. Barth, Eds, North Holland, Amsterdam, 493 505.
• 17: Dimitri Metaxas , Demetri Terzopoulos, Dynamic deformation of solid primitives with constraints, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.309-312, July 1992
• 18: 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
• 19: A. Pentland , J. Williams, Good vibrations: model dynamics for graphics and animation, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.207-214, July 1989
• 20: Les Piegl, On NURBS: a Survey, IEEE Computer Graphics and Applications, v.11 n.1, p.55-71, January 1991 [doi>10.1109/38.67702]
• 21: L. Piegl, Modifying the shape of rational B-splines. part 1: curves, Computer-Aided Design, v.21 n.10, p.509-518, Oct. 1989
• 22: L. Piegl, Modifying the shape of rational B-splines. part2: surfaces, Computer-Aided Design, v.21 n.9, p.538-546, Nov. 1989 [doi>10.1016/0010-4485(89)90014-6]
• 23: L Piegl , W Tiller, Curve and surface constructions using rational B-splines, Computer-Aided Design, v.19 n.9, p.485-498, Nov. 1987 [doi>10.1016/0010-4485(87)90234-X]
• 24: John Platt, A generalization of dynamic constraints, CVGIP: Graphical Models and Image Processing, v.54 n.6, p.516-525, Nov. 1992 [doi>10.1016/1049-9652(92)90071-5]
• 25: John C. Platt , Alan H. Barr, Constraints methods for flexible models, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.279-288, Aug. 1988
• 26: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, New York, NY, 1986
• 27: SCHt!MAKER, L.L. 1976. Fitting surfaces to scattered data. In Approximation Theory H, G. G.
• 28: Lorentz, C. H. Chui, and L. L. Schumaker, Eds., Academic Press, New York, 203 267.
• 29: Thomas W. Sederberg , Peisheng Gao , Guojin Wang , Hong Mu, 2-D shape blending: an intrinsic solution to the vertex path problem, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.15-18, September 1993 [doi>10.1145/166117.166118]
• 30: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.151-160, Aug. 1986
• 31: SttlNA(;AWA, Y. AND KUNIL T.L. 1991. The differential model: A model for animating transformation of objects using differential information. In Modeling in Computer Graphics, T. L. Kunii, Ed. Springer-Verlag, Tokyo, 6 15.
• 32: STa~XN(;, G. 1986. Introduction to Applied Mathematics. Wellesley-Cambridge Press, Cambridge, Mass.
• 33: R. Szeliski , D. Terzopoulos, From splines to fractals, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.51-60, July 1989
• 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: Demetri Terzopoulos, Regularization of inverse visual problems involving discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.4, p.413-242, July 1986 [doi>10.1109/TPAMI.1986.4767807]
• 36: TERZOPOULOS, D. AND FLEISCHER, K. 1988. Deformable models. Vis. Comput. 4, 6, 306-331.
• 37: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.205-214, July 1987
• 38: Jeffrey A. Thingvold , Elaine Cohen, Physical modeling with B-spline surfaces for interactive design and animation, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.129-137, Mar. 1990
• 39: TILLER, W. 1983. Rational B-splines for curve and surface representation. IEEE Comput. Graph. Appl. 3, 6, 61-69.
• 40: Kenneth James Versprille, Computer-aided design applications of the rational b-spline approximation form., 1975
• 41: WAHSA, G. 1990. Spline Models for Observational Data. SIAM, Philadelphia, Pa.
• 42: William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992
• 43: ZIENKIEWlCZ, O.C. 1977. The Finite Element Method. 3rd ed. McGraw-Hill, London.

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.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Design, Theory

Keywords:
CAGD, NURBS, constraints, cross-sectional shape design, deformable models, dynamics, finite elements, free-form deformation, optimal curve and surface fitting, shape metamorphosis, solid rounding, trimming