Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Refolding Planar Polygons

View Current Project Information

Hayley Nicole Iben, Erik Demaine1 and James O'Brien

Apple Computer, Intel, Sony, UC MICRO, GAANN Fellowship, National Science Foundation, Pixar Animation Studios, Autodesk and Alfred P. Sloan Foundation

This project describes an algorithm for generating a guaranteed-intersection-free interpolation sequence between any pair of compatible polygons. Our algorithm 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. We present the details of our algorithm in [1-3].

Figure 1
Figure 1: An intersection-free interpolation sequence generated using our algorithm. For this example, all edge lengths were held constant, the linear interpolation of vertex positions was used for the direction heuristic, and the total computation time was 1.6 minutes on a 3.06 GHz Pentium IV computer with 1 GB of memory.

Figure 2
Figure 2: This example interpolates between two configurations of interlocked teeth. The top row shows the result computed with the edge lengths constrained to change monotonically and required 5.0 minutes of computation. The bottom row shows the result computed with unconstrained edge lengths and required 1.8 minutes of computation.

Figure 3
Figure 3: As an experiment, we relaxed the requirement that steps of our algorithm never increase energy. The top row was computed with constrained edge lengths, requiring 4.1 minutes of computation. The bottom row has unconstrained edge lengths, requiring 2.0 minutes of computation. The leaf and plane outlines were provided by Marc Alexa.

H. N. Iben, J. F. O'Brien, and E. D. Demaine, "Refolding Planar Polygons," Proc. Symp. Computational Geometry, Sedona, AZ, June 5-7, 2006, pp. 71-79.
H. N. Iben, "Refolding Planar Polygons," Master's Report, UC Berkeley, May 2005.
H. N. Iben, J. F. O'Brien, and E. D. Demaine, "Refolding Planar Polygons," ACM SIGGRAPH, Los Angeles, CA, August 2004 (technical sketch).