Three-dimensional distance field metamorphosis

ABSTRACT

Given two or more objects of general topology, intermediate objects are constructed by a distance field metamorphosis. In the presented method the interpolation of the distance field is guided by a warp function controlled by a set of corresponding anchor points. Some rules for defining a smooth least-distorting warp function are given. To reduce the distortion of the intermediate shapes, the warp function is decomposed into a rigid rotational part and an elastic part. The distance field interpolation method is modified so that the interpolation is done in correlation with the warp function. The method provides the animator with a technique that can be used to create a set of models forming a smooth transition between pairs of a given sequence of keyframe models. The advantage of the new approach is that it is capable of morphing between objects having a different topological genus where no correspondence between the geometric primitives of the models needs to be established. The desired correspondence is defined by an animator in terms of a relatively small number of anchor points

REFERENCES

• 1: ARAD, N. AND REISFELD, D. 1995. Image warping using few anchor points and radial functions. Comput. Graph. Forum 14 1, 35-46.
• 2: K. S. Arun , T. S. Huang , S. D. Blostein, Least-squares fitting of two 3-D point sets, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.5, p.698-700, Sept. 1987 [doi>10.1109/TPAMI.1987.4767965]
• 3: Gill Barequet , Micha Sharir, Piecewise-linear interpolation between polygonal slices, Proceedings of the tenth annual symposium on Computational geometry, p.93-102, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177562]
• 4: Thaddeus Beier , Shawn Neely, Feature-based image metamorphosis, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.35-42, July 1992
• 5: Gunilla Borgefors, Distance transformations in digital images, Computer Vision, Graphics, and Image Processing, v.34 n.3, p.344-371, June 1986 [doi>10.1016/S0734-189X(86)80047-0]
• 6: CARMEL, E. AND COHEN-OR, D. 1997. Warp-guided object-space morphing. Visual Comput. (to appear).
• 7: 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]
• 8: Daniel Cohen-Or , David Levin , Amira Solomovici, Contour blending using warp-guided distance field interpolation, Proceedings of the 7th conference on Visualization '96, p.165-ff., October 28-29, 1996, San Francisco, California, United States
• 9: Douglas DeCarlo , Jean Gallier, Topological evolution of surfaces, Proceedings of the conference on Graphics interface '96, p.194-203, May 1996, Toronto, Ontario, Canada
• 10: 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
• 11: DYN, N. 1987. Interpolation and approximation by radial and related functions. In Approximation Theory VI, L. L. Schumaker, C. K. Chui and J. D. Ward, Eds., 211-234.
• 12: GOLDSTEIN, E. AND GOTSMAN, C. 1995. Polygon morphing using a multiresolution representation. In Proceedings of Graphics Interface '95, 247-254.
• 13: Taosong He , Sidney Wang , Arie Kaufman, Wavelet-based volume morphing, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
• 14: Gabor T. Herman , Jingsheng Zheng , Carolyn A. Bucholtz, Shape-Based Interpolation, IEEE Computer Graphics and Applications, v.12 n.3, p.69-79, May 1992 [doi>10.1109/38.135915]
• 15: John F. Hughes, Scheduled Fourier volume morphing, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.43-46, July 1992
• 16: T. Kanai , H. Suzuki , F. Kimura, 3D geometric metamorphosis based on harmonic map, Proceedings of the 5th Pacific Conference on Computer Graphics and Applications, p.97, October 13-16, 1997
• 17: KAUL, A. AND ROSSIGNAC, J. 1991. Solid-interpolation deformations: Construction and animation of pips. In Proceedings of EUROGRAPHICS'91 (Sept.), 493-505.
• 18: James R. Kent , Wayne E. Carlson , Richard E. Parent, Shape transformation for polyhedral objects, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.47-54, July 1992
• 19: LAZARUS, F. AND VERROUST, A. 1994. Feature-based shape transformation for polyhedral objects. In Proceedings of the Fifth Eurographics Workshop on Animation and Simulation.
• 20: 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]
• 21: Apostolos Lerios , Chase D. Garfinkle , Marc Levoy, Feature-based volume metamorphosis, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.449-456, September 1995 [doi>10.1145/218380.218502]
• 22: LEVIN, D. 1986. Multidimensional reconstruction by set-valued approximation. IMA J. Numer. Anal. 6, 173-184.
• 23: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 24: PARENT, R. E. 1992. Shape transformation by boundary representation interpolation: A recursive approach to establishing face correspondences. J. Visualization Comput. Animation 3, 219-239.
• 25: Bradley A. Payne , Arthur W. Toga, Distance Field Manipulation of Surface Models, IEEE Computer Graphics and Applications, v.12 n.1, p.65-71, January 1992 [doi>10.1109/38.135885]
• 26: Detlef Ruprecht , Heinrich Müller, Image Warping with Scattered Data Interpolation, IEEE Computer Graphics and Applications, v.15 n.2, p.37-43, March 1995 [doi>10.1109/38.365004]
• 27: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 28: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 29: Thomas W. Sederberg , Eugene Greenwood, A physically based approach to 2–D shape blending, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.25-34, July 1992
• 30: 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]
• 31: Michal Shapira , Ari Rappoport, Shape Blending Using the Star-Skeleton Representation, IEEE Computer Graphics and Applications, v.15 n.2, p.44-50, March 1995 [doi>10.1109/38.365005]
• 32: Ken Shoemake, Animating rotation with quaternion curves, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.245-254, Jul. 1985
• 33: SUN, Y. M., WANG, W., AND CHIN, F. Y. L. 1995. Interpolating polyhedral models using intrinsic shape parameters. In Proceedings of the Third Pacific Conference on Computer Graphics and Applications, Pacific Graphics '95, S.Y. Shin and T. L. Kunii, Eds. World Scientific, River Edge, NJ, 133-147.
• 34: Thomas J. True , John F. Hughes, Volume warping, Proceedings of the 3rd conference on Visualization '92, October 19-23, 1992, Boston, Massachusetts
• 35: George Wolberg, Digital Image Warping, IEEE Computer Society Press, Los Alamitos, CA, 1994

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms

Keywords:
computer animation, interpolation, morphing, radial basis function, shape-blending, warping