Interpolation of Triangle Hierarchies

Axel Friedrich - Konrad Polthier - Markus Schmies


We consider interpolation between keyframe hierarchies. We impose a set of weak constraints that allows smooth interpolation between two keyframe hierarchies in an animation or, more generally, allows the interpolation in an n-parameter family of hierarchies. We use hierarchical triangulations obtained by the Rivara element bisection algorithm and impose a weak compatibility constraint on the set of root elements of all keyframe hierarchies. We show that the introduced constraints are rather weak.

The strength of our approach is that the interpolation works in the class of conforming triangulations and simplifies the task of finding the intermediate hierarchy, which is the union of the two (, or more,) keyframe hierarchies involved in the interpolation process. This allows for an efficient generation of the intermediate connectivity and additionally ensures that the intermediate hierarchy is again a conforming hierarchy satisfying the same constraints.

CR Categories:

 I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - Surface and object representations; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - Hierarchy and geometric transformations; I.3.6 [Computer Graphics]: Methodology and Techniques - Graphics data structures and data types I.3.7 [Computer Graphics]: Three-dimensional graphics and realism - animation


animation, shape interpolation, adaptive refinement, level-of-detail, multiresolutional representation

Full Preprint: Interpolation of Triangle Hierarchies (.pdf 216 KB)