“Shape transformation using variational implicit functions” by Turk and O’Brien

Traditionally, shape transformation using implicit functions is performed in two distinct steps: 1) creating two implicit functions, and 2) interpolating between these two functions. We present a new shape transformation method that combines these two tasks into a single step. We create a transformation between two N-dimensional objects by casting this as a scattered data interpolation problem in N +1 dimensions. For the case of 2D shapes, we place all of our data constraints within two planes, one for each shape. These planes are placed parallel to one another in 3D. Zero-valued constraints specify the locations of shape boundaries and positive-valued constraints are placed along the normal direction in towards the center of the shape. We then invoke a variational interpolation technique (the 3D generalization of thin-plate interpolation), and this yields a single implicit function in 3D. Intermediate shapes are simply the zero-valued contours of 2D slices through this 3D function. Shape transformation between 3D shapes can be performed similarly by solving a 4D interpolation problem. To our knowledge, ours is the first shape transformation method to unify the tasks of implicit function creation and interpolation. The transformations produced by this method appear smooth and natural, even between objects of differing topologies. If desired, one or more additional shapes may be introduced that influence the intermediate shapes in a sequence. Our method can also reconstruct surfaces from multiple slices that are not restricted to being parallel to one another.

1. Barequet, Gill, Daniel Shapiro and Ayellet Tal, “History Consideration in Reconstructing Polyhedral Surfaces from Parallel Slices,” Proceedings of Visualization ’96, San Francisco, California, Oct. 27 – Nov. 1, 1996, pp. 149-156.
2. Barr, Alan H., “Global and Local Deformations of Solid Primitives,” Computer Graphics, Vol. 18, No. 3 (SIGGRAPH 84), pp. 21-30.
3. Beier, Thaddeus and Shawn Neely, “Feature-Based Image Metamorphosis,” Computer Graphics, Vol. 26, No. 2 (SIGGRAPH 92), July 1992, pp. 35-42.
4. Bloomenthal, Jules, “An Implicit Surface Polygonizer,” in Graphics Gems IV, edited by Paul S. Heckbert, Academic Press, 1994, pp. 324- 349.
5. Bookstein, Fred L., “Principal Warps: Thin Plate Splines and the Decomposition of Deformations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, No. 6, June 1989, pp. 567-585.
6. Celniker, George and Dave Gossard, “Deformable Curve and Surface Finite-Elements for Free-Form Shape Design,” Computer Graphics, Vol. 25, No. 4 (SIGGRAPH 91), July 1991, pp. 257-266.
7. Cohen-Or, Daniel, David Levin and Amira Solomovici, “Three Dimensional Distance Field Metamorphosis,” ACM Transactions on Graphics, 1997.
8. Duchon, Jean, “Splines Minimizing Rotation-Invariant Semi-Norms in Sobolev Spaces,” in Constructive Theory of Functions of Several Variables, Lecture Notes in Mathematics, edited by A. Dolb and B. Eckmann, Springer-Verlag, 1977, pp. 85-100.
9. Duncan, Jody, “A Once and Future War,” Cinefex, No. 47 (entire issue devoted to the film Terminator 2), August 1991, pp. 4-59.
10. Fuchs, H., Z. M. Kedem and S. P. Uselton, “Optimal Surface Reconstruction from Planar Contours,” Communications of the ACM,Vol. 20, No. 10, October 1977, pp. 693-702.
11. Golub, Gene H. and Charles F. Ban Loan, Matrix Computations, John Hopkins University Press, 1996.
12. Gregory, Arthur, Andrei State, Ming C. Lin, Dinesh Manocha, Mark A. Livingston, “Feature-based Surface Decomposition for Correspondence and Morphing between Polyhedra”, Proceedings of Computer Animation, Philadelphia, PA., 1998.
13. He, Taosong, Sidney Wang and Arie Kaufman, “Wavelet- Based Volume Morphing,” Proceedings of Visualization ’94, Washington, D. C., edited by Daniel Bergeron and Arie Kaufman, October 17-21, 1994, pp. 85-92.
14. Herman, Gabor T., Jingsheng Zheng and Carolyn A. Bucholtz, “Shape-Based Interpolation,” IEEE Computer Graphics and Applications, Vol. 12, No. 3 (May 1992), pp. 69-79.
15. Hugues, John F., “Scheduled Fourier Volume Morphing,” Computer Graphics, Vol. 26, No. 2 (SIGGRAPH 92), July 1992, pp. 43-46.
16. Kaul, Anil and Jarek Rossignac, “Solid- Interpolating Deformations: Construction and animation of PIPs,” Proceedings of Eurographics ’91, Vienna, Austria, 2-6 Sept. 1991, pp. 493-505.
17. Kent, James R., Wayne E. Carlson and Richard E. Parent, “Shape Transformation for Polyhedral Objects,” Computer Graphics, Vol. 26, No. 2 (SIGGRAPH 92), July 1992, pp. 47-54.
18. Lerios, Apostolos, Chase Garfinkle and Marc Levoy, “Feature-Based Volume Metamorphosis,” Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH 95), pp. 449-456.
19. Levin, David, “Multidimensional Reconstruction by Set-valued Approximation,” IMA J. Numerical Analysis, Vol. 6, 1986, pp. 173-184.
20. Litwinowicz, Peter and Lance Williams, “Animating Images with Drawings,” Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH 94), pp. 409-412.
21. Lorenson, William and Harvey E. Cline, “Marching Cubes: A High Resolution 3-D Surface Construction Algorithm,” Computer Graphics, Vol. 21, No. 4 (SIGGRAPH 87), July 1987, pp. 163-169.
22. Meyers, David and Shelley Skinner, “Surfaces From Contours: The Correspondence and Branching Problems,” Proceedings of Graphics Interface ’91, Calgary, Alberta, 3-7 June 1991, pp. 246-254.
23. Payne, Bradley A. and Arthur W. Toga, “Distance Field Manipulation of Surface Models,” IEEE Computer Graphics and Applications,Vol. 12, No. 1, January 1992, pp. 65-71.
24. Rossignac, Jarek and Anil Kaul, “AGRELs and BIPs: Metamorphosis as a Bezier Curve in the Space of Polyhedra,” Proceedings of Eurographics ’94, Oslo, Norway, Sept. 12-16, 1994, pp. 179-184.
25. Sederberg, Thomas W. and Eugene Greenwood, “A Physically Based Approach to 2-D Shape Blending,” Computer Graphics, Vol. 26, No. 2 (SIGGRAPH 92), July 1992, pp. 25-34.
26. Sederberg, Thomas W. and Scott R. Parry, “Free-Form Deformations of Solid Geometric Models,” Computer Graphics, Vol. 20, No. 4 (SIGGRAPH 86), pp. 151-160.
27. Turk, Greg and James F. O’Brien, “Variational Implicit Surfaces,” Tech Report GIT-GVU-99-15, Georgia Institute of Technology, May 1999, 9 pages.
28. Wolberg, George, Digital Image Warping, IEEE Computer Society Press, Los Alamitos, California 1990.