“Multiresolution mesh morphing” by Lee, Dobkin, Sweldens and Schroeder

We present a new method for user controlled morphing of two homeomorphic triangle meshes of arbitrary topology. In particular we focus on the problem of establishing a correspondence map between source and target meshes. Our method employs the MAPS algorithm to parameterize both meshes over simple base domains and an additional harmonic map bringing the latter into correspondence. To control the mapping the user specifies any number of feature pairs, which control the parameterizations produced by the MAPS algorithm. Additional controls are provided through a direct manipulation interface allowing the user to tune the mapping between the base domains. We give several examples of æsthetically pleasing morphs which can be created in this manner with little user input. Additionally we demonstrate examples of temporal and spatial control over the morph.

1. AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. Data Structures and Algorithms. Addison-Wesley, 1983.
2. BEIER, T., AND NEELY, S. Feature-based image metamorphosis. In Computer Graphics (SIGGRAPH ’92 Proceedings), 35-42, 1992.
3. BESL, P. J., AND MCKAY, N. D. A Method for Registration of 3-D Shapes. IEEE Trans. on Pattern Anal. and Machine intelligence 14, 2 (Feb. 1992), 239- 258.
4. BOYER, M., AND STEWART, N. F. Modeling spaces for toleranced objects, int. J. Robotics Research 10, 5 (1991), 570-582.
5. BROWN, P. J. C., AND FAIGLE, C. T. A Robust Efficient Algorithm for Point Location in Triangulations. Tech. rep., Cambridge University, February 1997.
6. EYAL CARMEL AND DANIEL COHEN-OR Warp-guided object-space morphing. The Visual Computer 13, 9-10 (1998), 46-478. ISSN 0178-2789.
7. CHEN, Y., AND MEDIONI, G. Object Modeling by Registration of Multiple Range Images. int. J. of image and Vision Computing 10, 3 (Apr. 1992), 145- 155.
8. DECARLO, D., AND GALLIER, J. Topological Evolution of Surfaces. In Graphics interface ’96, 194-203, May 1996.
9. DECAUDIN, P. Geometric Deformation by Merging a 3D-Object with a Simple Shape. In Graphics interface ’96, 55-60, May 1996.
10. DOBKIN, D., AND KIRKPATRICK, D. A Linear Algorithm for Determining the Separation of Convex Polyhedra. Journal of Algorithms 6 (1985), 381-392.
11. ECK, M., DEROSE, T., DUCHAMP, T., HOPPE, H., LOUNSBERY, M., AND STUETZLE, W. Multiresolution Analysis of Arbitrary Meshes. In Computer Graphics (SIGGRAPH ’95 Proceedings), 173-182, 1995.
12. FAUGERAS, O. D., AND HERBERT, M. The Representation, Recognition, and Locating of 3D Objects. The int. J. Robotics Research 5, 3 (1986), 27-49.
13. GOMES, J., DARSA, L., COSTA, B., AND VELHO, L. Warping and Morphing of Graphical Objects. Morgan Kaufmann, San Francisco, Calif., 1998.
14. GREGORY, A., STATE, A., LIN, M., MANOCHA, D., AND LIVINGSTON, M. Feature-based Surface Decomposition for Polyhedral Morphing. Tech. Rep. TR98-014, Department of Computer Science, University of North Carolina – Chapel Hill, Apr. 14 1998.
15. HE, T., WANG, S., AND KAUFMAN, A. Wavelet-Based Volume Morphing. In Proceedings of the Conference on Visualization, 85-92, Oct. 1994.
16. HUGHES, J. F. Scheduled Fourier volume morphing. In Computer Graphics (SIGGRAPH ’92 Proceedings), 43-46, 1992.
17. KANAI, T., SUZUKI, H., AND KIMURA, F. Three-dimensionalgeometric metamorphosis based on harmonic maps. The Visual Computer 14, 4 (1998), 166- 176.
18. KANAI, T., SUZUKI, H., AND KIMURA, F. Metamorphosis of Arbitrary Triangular Meshes with User-Specified Correspondence. IEEE Computer Graphics and Applications (to appear).
19. KAUL, A., AND ROSSIGNAC, J. Solid-Interpolating Deformations: Construction and Animation of PIPs. In Eurographics ‘91,493-505, Sept. 1991.
20. KENT, J. R., CARLSON, W. E., AND PARENT, R. E. Shape transformation for polyhedral objects. In Computer Graphics (SIGGRAPH ’92 Proceedings), 47-54, 1992.
21. LANTHIER, M., MAHESHWARI, A., AND SACK, J.-R. Approximating Weighted Shortest Paths on Polyhedral Surfaces. In 6th Annual Video Review of Computational Geometry, Proc. 13th ACM Symp. Computational Geometry, 485-486, 4-6 June 1997.
22. LAZARUS, F., AND VERROUST, A. Feature-based shape transformation for polyhedral objects. In The 5th Eurographics Workshop on Animation and Simulation, 1-14, 1994.
23. LAZARUS, F., AND VERROUST, A. Three-dimensional metamorphosis: a survey. The Visual Computer 14 (1998), 373-389.
24. LEE, A. W. F., SWELDENS, W., SCHR(3DER, P., COWSAR, L., AND DOBKIN, D. MAPS: Multiresolution Adaptive Parameterization of Surfaces. Computer Graphics (SIGGRAPH ’98 Proceedings) (1998), 95-104.
25. LEE, S., CHWA, K., SHIN, S. Y., AND WOLBERG, G. Image Metamorphosis Using Snakes and Free-Form Deformations. In Computer Graphics (SIGGRAPIt ’95 Proceedings), 439-448, 1995.
26. LERIOS, A., GARFINKLE, C. D., AND LEVOY, M. Feature-Based Volume Metamorphosis. In Computer Graphics (SIGGRAPH ’95 Proceedings), 449- 456, 1995.
27. PARENT, R. E. Shape transformation by boundary representation interpolation: a recursive approach to establishing face correspondences. The Journal of Visualization and Computer Animation 3, 4 (Oct.-Dec. 1992), 219-239.
28. PAYNE, B. A., AND TOGA, A. W. Distance field manipulation of surface models. IEEE Computer Graphics andApplications 12, 1 (Jan. 1992), 65-71.
29. SEDERBERG, T. W., GAG, P., WANG, G., AND MU, H. 2D Shape Blending: An Intrinsic Solution to the Vertex Path Problem. In Computer Graphics (SIGGRAPH ’93 Proceedings), vol. 27, 15-18, Aug. 1993.
30. SHAPIRA, M., AND RAPPOPORT, A. Shape Blending Using the Star-Skeleton Representation. IEEE Computer Graphics and Applications 15, 2 (1995), 44-50.
31. SHEWCHUK, J. U. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18, 3 (Oct. 1997), 305-363.
32. SPANIER, E. H. Algebraic Topology. McGraw-Hill, New York, 1966.
33. SUN, Y. M., WANG, W., AND CHIN, F. Y. L. Interpolating Polyhedral Models using Intrinsic Shape Parameters. In Pacific Graphics ’95, Aug. 1995.
34. TURK, G. Re-Tiling Polygon Surfaces. Computer Graphics (SIGGRAPH ’92 Proceedings) (1992), 55-64.
35. WHITAKER, R., AND BREEN, D. Level-Set Models for the Deformation of Solid Objects. In Proceedings of the Third international Workshop on implicit Surfaces, 19-35, June 1998.
36. WOLBERG, G. Digital image Warping. IEEE Computer Society Press, 1990. IEEE Computer Society Press Monograph.