A survey of spatial deformation from a user-centered perspective

ABSTRACT

The spatial deformation methods are a family of modeling and animation techniques for indirectly reshaping an object by warping the surrounding space, with results that are similar to molding a highly malleable substance. They have the virtue of being computationally efficient (and hence interactive) and applicable to a variety of object representations.

In this article we survey the state of the art in spatial deformation. Since manipulating ambient space directly is infeasible, deformations are controlled by tools of varying dimension—points, curves, surfaces and volumes—and it is on this basis that we classify them. Unlike previous surveys that concentrate on providing a single underlying mathematical formalism, we use the user-centered criteria of versatility, ease of use, efficiency and correctness to compare techniques.

REFERENCES

• 1: Alexis Angelidis , Marie-Paule Cani , Geoff Wyvill , Scott King, Swirling-Sweepers: Constant-Volume Modeling, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.10-15, October 06-08, 2004
• 2: Sweepers: Swept User-Defined Tools for Modeling by Deformation, Proceedings of the Shape Modeling International 2004, p.63-73, June 07-09, 2004 [doi>10.1109/SMI.2004.62]
• 3: Alexis Angelidis , Geoff Wyvill , Marie-Paule Cani, Sweepers: swept deformation defined by gesture, Graphical Models, v.68 n.1, p.2-14, January 2006 [doi>10.1016/j.gmod.2005.08.002]
• 4: Aubert, F. and Bechmann, D. 1997a. Animation by deformation of space-time objects. Proceedings of the Computer Graphics Forum 16, 3, 57--66.
• 5: Aubert, F. and Bechmann, D. 1997b. Volume preserving space deformation. Comput. Graph. 21, 5, 625--639.
• 6: Alan H. Barr, Global and local deformations of solid primitives, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.21-30, July 1984
• 7: Bechmann, D. 1994. Space deformation models survey. Comput. Graph. 18, 4, 571--586.
• 8: Bechmann, D. 1998. Multidimensional free-form deformation tools. In Proceedings of EUROGRAPHICS'. State of the Art Reports (STARs).
• 9: Bechmann, D., Bertrand, Y., and Thery, S. 1996. Continuous free-form deformation. In Proceedings of Computer Networks and ISDN Systems (Compugraphics'96). 157--171.
• 10: Bechmann, D. and Dubreuil, N. 1993. Animation through space and time based on a space deformation model. J. Visualis. Comput. Animat. 4, 3, 165--184.
• 11: Bechmann, D. and Dubreuil, N. 1995. Order controlled free-form animation. J. Visualis. Comput. Animat. 5, 1, 11--32.
• 12: Dominique Bechmann , Mehdi Elkouhen, Animating with the "Multidimensional deformation tool", Proceedings of the Eurographic workshop on Computer animation and simulation, p.29-35, September 02-03, 2001, Manchester, UK
• 13: Bechmann, D. and Gerber, D. 2003. Arbitrary shaped deformations with dogme. Vis. Comput. 19, 2-3, 175--186.
• 14: Bezier, P. 1972. Numerical Control: Mathematics and Applications. Wiley.
• 15: Carole Blanc , Pascal Guitton , Christophe Schlick, A methodology for description of geometrical deformations, Proceedings of the second Pacific conference on Fundamentals of computer graphics, p.49-62, January 1995, Beijing, China
• 16: Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984 [doi>10.1145/357346.357349]
• 17: Borrel, P. and Bechmann, D. 1991. Deformation of n-dimensional objects. Int. J. Computat. Geom. Appl. 1, 4, 427--453.
• 18: 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]
• 19: Botsch, M. and Kobbelt, L. 2005. Real-time shape editing using radial basis functions. Comput. Graph. Forum 24, 3, 611--621.
• 20: Boullion, T. L. and Odell, P. L. 1971. Generalized Inverse Matrix. Wiley Interscience, New York.
• 21: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, Interactive skeleton-driven dynamic deformations, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 22: Catmull, E. and Clark, J. 1978. Recursively generated b-spline surfaces on arbitrary topological meshes. Comput.-Aid. Des. 10, 6, 350--355.
• 23: 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
• 24: Yu-Kuang Chang , Alyn P. Rockwood, A generalized de Casteljau approach to 3D free-form deformation, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.257-260, July 1994 [doi>10.1145/192161.192220]
• 25: Comninos, P. 1989. Fast bends or fast free-form deformation of polyhedral data. In Computer Graphics. Blenheim Online Publications, Middlesex, UK, 225--242.
• 26: Sabine Coquillart, Extended free-form deformation: a sculpturing tool for 3D geometric modeling, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.187-196, Aug. 1990
• 27: Sabine Coquillart , Pierre Jancéne, Animated free-form deformation: an interactive animation technique, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.23-26, July 1991
• 28: Crespin, B. 1999. Implicit free-form deformations. In Implicit Surfaces. 17--23.
• 29: Davis, O. R. and Burton, R. P. 1991. Free-form deformation as an interactive modeling tool. J. Imag. Tech. 17, 4, 181--187.
• 30: Philippe Decaudin, Geometric deformation by merging a 3D-object with a simple shape, Proceedings of the conference on Graphics interface '96, p.55-60, May 1996, Toronto, Ontario, Canada
• 31: Petros Faloutsos , Michiel van de Panne , Demetri Terzopoulos, Dynamic Free-Form Deformations for Animation Synthesis, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.201-214, July 1997 [doi>10.1109/2945.620488]
• 32: G. Farin, Surfaces over Dirichlet Tessellations, Computer Aided Geometric Design, v.7 n.1-4, p.281-292, Jun. 1990 [doi>10.1016/0167-8396(90)90036-Q]
• 33: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 34: Feng, J., Ma, L., and Peng, Q. 1996. A new free-form deformation through the control of parametric surfaces. Comput. Graph. 20, 4, 531--539.
• 35: Feng, J., Shao, J., Jin, X., Peng, Q., and Forrest, R. 2005. Multuresolution free-form deformations with subdivision surfaces of arbitrary topology. Vis. Comput. 22, 1, 28--42.
• 36: James Gain , Patrick Marais, Warp Sculpting, IEEE Transactions on Visualization and Computer Graphics, v.11 n.2, p.217-227, March 2005 [doi>10.1109/TVCG.2005.36]
• 37: Gain, J. E. 2000. Enhancing spatial deformation for virtual sculpting. Ph.D. thesis, University of Cambridge.
• 38: Gain, J. E. and Dodgson, N. 1999a. Adaptive refinement and decimation under free-form deformation. In Proceedings of Eurographics, 7--18.
• 39: James Gain , Neil Dodgson, Enhancing the efficiency and versatility of directly manipulated free-form deformation, ACM SIGGRAPH 99 Conference abstracts and applications, p.240, August 08-13, 1999, Los Angeles, California, United States [doi>10.1145/311625.312132]
• 40: James E. Gain , Neil A. Dodgson, Preventing Self-Intersection under Free-Form Deformation, IEEE Transactions on Visualization and Computer Graphics, v.7 n.4, p.289-298, October 2001 [doi>10.1109/2945.965344]
• 41: Greissmair, J. and Purgathofer, W. 1989. Deformation of solids with trivariate B-Splines. Comput. Graph. Forum, 137--148.
• 42: Greville, T. 1960. Some applications of the pseudo-inverse of a matrix. SIAM Revue II, 15--22.
• 43: Guillet, S. and Léon, J.-C. 1998. Parametrically deformed free-form surfaces as part of a variational model. Comput.-Aid. Des. 30, 8, 621--630.
• 44: Gentaro Hirota , Renee Maheshwari , Ming C. Lin, Fast volume-preserving free form deformation using multi-level optimization, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.234-245, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304036]
• 45: 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
• 46: Hu, S.-M., Zhang, H., Tai, C.-L., and Sun, J.-G. 2001. Direct manipulation of ffd : efficient explicit solutions and decomposible multiple point constraints. Vis. Comput. 17, 370--379.
• 47: Xiaogang Jin , Y. F. Li, Three-dimensional deformation using directional polar coordinates, Journal of Graphics Tools, v.5 n.2, p.15-24, Dec. 2000
• 48: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 49: Kalra, P., Mangili, A., Magnenat Thalmann, N., and Thalmann, D. 1992. Simulation of facial muscle actions based on rational free form deformations. Comput. Graph. Forum 11, 3, 59--69.
• 50: Ladislav Kavan , Steven Collins , Jiří Žára , Carol O'Sullivan, Skinning with dual quaternions, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington [doi>10.1145/1230100.1230107]
• 51: Kil, Y. J., Renzulli, P. A., Kreylos, O., Hamann, B., Monno, G., and Staadt, O. G. 2006. 3d warp brush modeling. Comput. Graph. 30, 4, 610--618.
• 52: F Klok, Two moving coordinate frames for sweeping along a 3D trajectory, Computer Aided Geometric Design, v.3 n.3, p.217-229, Nov. 1986 [doi>10.1016/0167-8396(86)90039-7]
• 53: Kazuya G. Kobayashi , Katsutoshi Ootsubo, t-FFD: free-form deformation by using triangular mesh, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781641]
• 54: Henry J. Lamousin , Warren N. Waggenspack Jr., NURBS-Based Free-Form Deformations, IEEE Computer Graphics and Applications, v.14 n.6, p.59-65, November 1994 [doi>10.1109/38.329096]
• 55: Lazarus, F., Coquillart, S., and Jancène, P. 1994. Axial deformations : an interactive deformation technique. Comput.- Aid. Des. 26, 8, 607--613.
• 56: Seung-Yong Lee , Kyung-Yong Chwa , Sung Yong Shin, Image metamorphosis using snakes and free-form deformations, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.439-448, September 1995 [doi>10.1145/218380.218501]
• 57: Ignacio Llamas , Byungmoon Kim , Joshua Gargus , Jarek Rossignac , Chris D. Shaw, Twister: a space-warp operator for the two-handed editing of 3D shapes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 58: Ignacio Llamas , Alexander Powell , Jarek Rossignac , Chris D. Shaw, Bender: a virtual ribbon for deforming 3D shapes in biomedical and styling applications, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.89-99, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060255]
• 59: MacCracken, R. and Joy, K. I. 1996. Free-form deformations with lattices of arbitrary topology. Comput. Graph., 181--188.
• 60: David Mason , Geoff Wyvill, Blendeforming: Ray Traceable Localized Foldover-Free Space Deformation, Proceedings of the International Conference on Computer Graphics, p.183, July 03-06, 2001
• 61: Bruce Merry , Patrick Marais , James Gain, Animation space: A truly linear framework for character animation, ACM Transactions on Graphics (TOG), v.25 n.4, p.1400-1423, October 2006 [doi>10.1145/1183287.1183294]
• 62: Mikita, M. 1996. 3d free-form deformation: basic and extented algorithms. In Proceedings of the 12th Spring Conference on Computer Graphics. 183--191.
• 63: Tim Milliron , Robert J. Jensen , Ronen Barzel , Adam Finkelstein, A framework for geometric warps and deformations, ACM Transactions on Graphics (TOG), v.21 n.1, p.20-51, January 2002 [doi>10.1145/504789.504791]
• 64: Moccozet, L. 1996. Hand modeling and animation for virtual humans. Ph.D. thesis, Université de Genève.
• 65: Laurent Moccozet , Nadia Magnenat Thalmann, Dirichlet Free-Form Deformations and their Application to Hand Simulation, Proceedings of the Computer Animation, p.93, June 04-07, 1997
• 66: Alex Mohr , Michael Gleicher, Building efficient, accurate character skins from examples, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 67: Andrew Nealen , Takeo Igarashi , Olga Sorkine , Marc Alexa, FiberMesh: designing freeform surfaces with 3D curves, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 68: Nimscheck, U. 1995. Rendering for free-form deformations. Ph.D. thesis, University of Cambridge.
• 69: Y. Ono , B-Y Chen , T. Nishita , J. Feng, Free-Form Deformation with Automatically Generated Multiresolution Lattices, Proceedings of the First International Symposium on Cyber Worlds (CW'02), p.0472, November 06-08, 2002
• 70: Scott R Parry, Free-form deformation in a constructive solid geometry modeling system, Brigham Young University, Provo, UT, 1986
• 71: Qunsheng Peng , Xiaogang Jin , Jieqing Feng, Arc-Length-Based Axial Deformation and Length Preserved Animation, Proceedings of the Computer Animation, p.86, June 04-07, 1997
• 72: Jean-Philipe Pernot , Stephane Guillet , Jean-Claude Léon , Franca Giannini , Chiara Eva Catalano , Bianca Falcidieno, A Shape Deformation Tool to Model Character Lines in the Early Design Phases, Proceedings of the Shape Modeling International 2002 (SMI'02), p.165, May 17-22, 2002
• 73: Raffin, R., Neveu, M., and Jaar, F. 2000. Curvilinear displacement of free-form-based deformation. Vis. Comput. 16, 38--46.
• 74: Ari Rappoport , Alla Sheffer , Michel Bercovier, Volume-preserving free-form solid, Proceedings of the third ACM symposium on Solid modeling and applications, p.361-372, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218086]
• 75: Rossignac, J. 1994. Introduction to the special issue on interactive sculpting. ACM Trans. Graph. 13, 2.
• 76: Ruprecht, D., Nagel, R., and Muller, H. 1995. Spatial free-form deformation with scattered data interpolation methods. Comput. Graph. 19, 63--72.
• 77: Sagi Schein , Gershon Elber, Discontinuous Free Form Deformations, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.227-236, October 06-08, 2004
• 78: B. Shneiderman, Direct Manipulation: A Step Beyond Programming Languages, Computer, v.16 n.8, p.57-69, August 1983 [doi>10.1109/MC.1983.1654471]
• 79: Thomas W. Sederberg , Jianmin Zheng , Almaz Bakenov , Ahmad Nasri, T-splines and T-NURCCs, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 80: 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
• 81: Karan Singh , Eugene Fiume, Wires: a geometric deformation technique, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.405-414, July 1998 [doi>10.1145/280814.280946]
• 82: Singh, K. and Kokkevis, E. 2000. Skinning characters using surface-oriented free-form deformations. In Proceedings of Graphies Interface. 35--42.
• 83: Peter-Pike J. Sloan , Charles F. Rose, III , Michael F. Cohen, Shape by example, Proceedings of the 2001 symposium on Interactive 3D graphics, p.135-143, March 2001 [doi>10.1145/364338.364382]
• 84: Wenhao Song , Xunnian Yang, Free-form deformation with weighted T-spline, The Visual Computer: International Journal of Computer Graphics, v.21 n.3, p.139-151, April 2005 [doi>10.1007/s00371-004-0277-8]
• 85: Wolfram von Funck , Holger Theisel , Hans-Peter Seidel, Vector field based shape deformations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 86: Wolfram von Funck , Holger Theisel , Hans-Peter Seidel, Explicit Control of Vector Field Based Shape Deformations, Proceedings of the 15th Pacific Conference on Computer Graphics and Applications, p.291-300, October 29-November 02, 2007 [doi>10.1109/PG.2007.22]
• 87: Xiaohuan Corina Wang , Cary Phillips, Multi-weight enveloping: least-squares approximation techniques for skin animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545283]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Human Factors, Performance

Keywords:
Free-form deformation, spatial deformation, warping