 |
Morphing refers to the process of transforming one shape (the source) into another
(the target). Morphing is widely used in computer graphics, animation, and modeling.
In planar graph morphing we would like to transform a given source graph to another
pre-specified target graph. A smooth transformation of one graph into another can be
useful for numerous problems from graph drawing. In particular, when dealing with
dynamic graphs and graphs that change through time, it is crucial to preserve the
mental map of the user. Thus, it is important to minimize the changes to the drawing
and to create a smooth transition between consecutive drawings. Another important
goal is to avoid creating any intersections throughout the morph. We designed and
implemented an algorithm that can morph between drawings with straight-line segments,
bends and it relies on a combination of techniques to achieve smooth transformations:
rigid morphing, compatible triangulations, as well as morphing based on interpolation
of the convex representations of the graphs.
For example given the two layouts on the left(top-left is the source, bottom-right drawn opaquely is the target layout) we are interested in finding a smooth sequence of layouts starting from the source ending with the target layout. We want each intermediate layout in the sequence contain no edge-crossings. Our algorithm has 4 main parts:
|
1 Dept. of Computer Science
University of Arizona
{cesim,kobourov}@cs.arizona.edu
2 Dept. of Electrical and Comp. Eng.
University of Arizona
tech@email.arizona.edu