Interactive design of smooth objects with probabilistic point constraints

ABSTRACT

Point displacement constraints constitute an attractive technique for interactive design of smooth curves, surfaces, and volumes. The user defines an arbitrary number of “control points” on the object and specifies their desired spatial location, while the system computes the object's degrees of freedom so that the constraints are satisfied. A constraint-based interface gives a feeling of direct manipulation of the object. In this article we introduce soft constraints, constraints which do not have to be met exactly. The softness of each constraint serves as a nonisotropic, local shape parameter enabling the user to explore the space of objects conforming to the constraints. Additionally, there is a global shape parameter which determines the amount of similarity of the designed object to a rest shape, or equivalently, the rigidity of the rest shape. We present an algorithm termed probabilistic point constraints (PPC) for implementing soft constraints. The PPC algorithm views constraints as stochastic measurements of the state of a static system. The softness of a constraint is derived from the covariance of the “measurement.” The resulting system of probabilistic equations is solved using the Kalman filter, a powerful estimation tool in the theory of stochastic systems. We also describe a user interface using direct-manipulation devices for specifying and visualizing covariances in 2D and 3D. The algorithm is suitable for any object represented as a parametric blend of control points, including most spline representations. The covariance of a constraint provides a continuous transition from exact interpolation to controlled approximation of the constraint. The algorithm involves only linear operations and allows real-time interactive direct manipulation of curves and surfaces on current workstations.

REFERENCES

• 1: ANDERSSON, B.D.O., AND MOORE, ,J.B.1979. Opttmal Filtering.Prentice Hall,Englewood cliffs, N.,J.
• 2: BARTELS, R. AN{) B~:A'tvrY, C. 3. 1989. A technique for the direct manipulation of spline curves. In Graphics Interface '8,9, 33- 39,
• 3: BARTEI,S, R., B~:ATT~', ,J. ANI) BARSKY, B. 1988. An Introduction tcJ Splines/~or Use In Computer Graphics and Geometric Modelling. Morgan-Kaufmann, Pal() Alto, Calif.
• 4: BECHMANN, D. ANI) Dt;BRb;~TII, N. 1992 Animation through space and time based on a space defi~rmation model. Eur~)graphie.s" Workshop on Animation and Simulation.
• 5: Paul Borrel , Dominique Bechmann, Deformation of n-dimensional objects, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.351-369, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112564]
• 6: Paul Borrel , Ari Rappoport, Simple constrained deformations for geometric modeling and interactive design, ACM Transactions on Graphics (TOG), v.13 n.2, p.137-155, April 1994 [doi>10.1145/176579.176581]
• 7: BOULLION, T.L. AND ODELL, P.L. 1971. Generalized lnt,erse Matrices. Wiley, New York.
• 8: 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
• 9: CHENG F. ,XNI) BARSK',', B,A. 1991. Interproximation: Interpolation and approximation using cubic spline curves. Comput. Aided Des. 23, 10, 700706.
• 10: EMMO:RX~'K VAN, M. J. G. M., RAPt'()P()RT, A. ANI) R~~SSi(;NA~', J. 1993. Simplifying interactive design of solid models: A hypertext approach. Vis. Compttt. 9, 5, 239-254.
• 11: FANG, L. AND GOSSARD, D.C. 1992. Reconstruction of smooth parametric surfaces from unorganized data points. In Curves and Surfaces in Computer Vision and Graphics III, vol. 1830. SPIE, 226-236.
• 12: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 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: Barry Fowler, Geometric manipulation of tensor product surfaces, Proceedings of the 1992 symposium on Interactive 3D graphics, p.101-108, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147172]
• 15: Yaacov Hel-Or , Ari Rappoport , Michael Werman, Relaxed parametric design with probabilistic constraints, Proceedings on the second ACM symposium on Solid modeling and applications, p.261-270, May 19-21, 1993, Montreal, Quebec, Canada [doi>10.1145/164360.164437]
• 16: William M. Hsu , John F. Hughes , Henry Kaufman, Direct manipulation of free-form deformations, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.177-184, July 1992
• 17: KALLAY, M. 1993. Constrained optimization in surface design. In Modeling in Computer Graphics. Springer-Verlag, New York, 85-94.
• 18: KASS, M., WITKIN, A. AND TERZOPOULOS, D. 1988. Snakes: active contour models, intl. J. of Computer Vision. 321-331.
• 19: Dimitri Metaxas , Demetri Terzopoulos, Dynamic deformation of solid primitives with constraints, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.309-312, July 1992
• 20: 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
• 21: Gregory M. Nielson , Dan R. Olsen, Jr., Direct manipulation techniques for 3D objects using 2D locator devices, Proceedings of the 1986 workshop on Interactive 3D graphics, p.175-182, January 1987, Chapel Hill, North Carolina, United States [doi>10.1145/319120.319134]
• 22: PRESS, W. H., FLANNERY, B. P., TEUKOLSKY, S. A. AND VETTERLING, W.W. 1988. Numerical Recipes in C. Cambridge University Press, Cambridge, Mass.
• 23: RAPPOPORT, A. 1993. Direct manipulation devices for the design of geometric constraint networks. In Communicating with Virtual Worlds. Proceedings of Computer Graphics International '93. Springer, New York, 294-305.
• 24: SCHWEPPE, F.C. 1973. Uncertain Dynamic Systems. Prentice-Hall, Englewood Cliffs, N.J.
• 25: TERZOPOULOS, D., WITKIN, A. AND KASS, M. 1987. Symmetry seeking models and 3D object reconstruction. Int. J. Comput. Vis. 1, 3, 211-221.
• 26: William Welch , Andrew Witkin, Variational surface modeling, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.157-166, July 1992

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.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation; Least squares approximation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.4 Graphics Utilities
          Subjects: Graphics editors
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

General Terms:
Algorithms, Design

Keywords:
Kalman filter, interpolation, probabilistic point constraints, relaxed design, shape parameter, smooth objects, soft constraints, splines