Refolding planar polygons

ABSTRACT

This paper describes an algorithm for generating a guaranteed-intersection-free interpolation sequence between any pair of compatible polygons. Our algoithm builds on prior results from linkage unfolding, and if desired it can ensure that every edge length changes monotonically over the course of the interpolation sequence. The computational machinery that ensures against self-intersection is independent from a distance metric that determines the overall character of the interpolation sequence. This decoupled approach provides a powerful control mechanism for determining how the interpolation should appear, while still assuring against intersection and guaranteeing termination of the algorithm. Our algorithm also allows additional control by accommodating a set of algebraic constraints that can be weakly enforced throughout the interpolation sequence.

REFERENCES

• 1: Oswin Aichholzer , Erik D. Demaine , Jeff Erickson , Ferran Hurtado , Mark Overmars , Michael Soss , Godfried T. Toussaint, Reconfiguring convex polygons, Computational Geometry: Theory and Applications, v.20 n.1-2, p.85-95, October 2001 [doi>10.1016/S0925-7721(01)00037-2 ]
• 2: Marc Alexa , Daniel Cohen-Or , David Levin, As-rigid-as-possible shape interpolation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.157-164, July 2000 [doi>10.1145/344779.344859]
• 3: Kendall E. Atkinson. An introduction to numerical analysis. John Wiley & Sons Inc., New York, second edition, 1989.
• 4: J. Baumgarte. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics and Engineering, 1:1--16, 1972.
• 5: Jason H. Cantarella , Erik D. Demaine , Hayley N. Iben , James F. O'Brien, An energy-driven approach to linkage unfolding, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997840]
• 6: Eyal Carmel and Daniel Cohen-Or. Warp-guided object-space morphing. The Visual Computer, 13:465--478, 1997.
• 7: Daniel Cohen-Or , Amira Solomovic , David Levin, Three-dimensional distance field metamorphosis, ACM Transactions on Graphics (TOG), v.17 n.2, p.116-141, April 1998 [doi>10.1145/274363.274366]
• 8: Robert Connelly, Erik D. Demaine, and Günter Rote. Straightening polygonal arcs and convexifying polygonal cycles. Discrete & Computational Geometry, 30(2):205--239, September 2003.
• 9: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 10: Alon Efrat , Sariel Har-Peled , Leonidas J. Guibas , T. M. Murali, Morphing between polylines, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.680-689, January 07-09, 2001, Washington, D.C., United States
• 11: Eli Goldstein and Craig Gotsman. Polygon morphing using a multiresolution representation. In Proceedings of Graphics Interface, pages 247--254, 1995.
• 12: Craig Gotsman and Vitaly Surazhsky. Guaranteed intersection-free polygon morphing. Computers and Graphics, 25(1):67--75, 2001.
• 13: Leonidas Guibas , John Hershberger, Morphing simple polygons, Proceedings of the tenth annual symposium on Computational geometry, p.267-276, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177987]
• 14: Taosong He , Sidney Wang , Arie Kaufman, Wavelet-based volume morphing, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
• 15: John F. Hughes, Scheduled Fourier volume morphing, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.43-46, July 1992
• 16: Anil Kaul and Jarek Rossignac. Solid-interpolating deformations: Construction and animation of PIPs. In Proceedings of Eurographics '91, pages 493--505, 1991.
• 17: W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. Numerical Recipes in C. Cambridge University Press, second edition, 1994.
• 18: 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]
• 19: 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
• 20: 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 ]
• 21: I. Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.443, November 12-14, 2000
• 22: Controllable morphing of compatible planar triangulations, ACM Transactions on Graphics (TOG), v.20 n.4, p.203-231, October 2001 [doi>10.1145/502783.502784]
• 23: Vitaly Surazhsky and Craig Gotsman. Intrinsic morphing of compatible triangulations. International Journal of Shape Modeling, 9(2):191--201, 2003.
• 24: Greg Turk , James F. O'Brien, Shape transformation using variational implicit functions, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.335-342, July 1999 [doi>10.1145/311535.311580]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms

Keywords:
morphing, polygon interpolation, refolding, shape transformation