Controllable morphing of compatible planar triangulations

Vitaly Surazhsky, Craig Gotsman

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

Two planar triangulations with a correspondence between the pain of vertex sets are compatible (isomorphic) if they are topologically equivalent. This work describes method for morphing compatible planar triangulations with identical convex boundaries in a manner that guarantees compatibility throughout the morph. These methods are based on a fundamental representation of a planar triangulation as a matrix that unambiguously describes the triangulation. Morphing the triangulations corresponds to interpolations between these matrices. We show that this basic approach can be extended to obtain better control over the morph, resulting in valid morphs with various natural properties. Two schemes, which generate the linear trajectory morph if it is valid, or a morph with trajectories close to linear otherwise, are presented. An efficient method for verification of validity of the linear trajectory morph between two triangulations is proposed. We also demonstrate how to obtain a morph with a natural evolution of triangle areas and how to find a smooth morph through a given intermediate triangulation.

Original languageEnglish (US)
Pages (from-to)203-231
Number of pages29
JournalACM Transactions on Graphics
Volume20
Issue number4
DOIs
StatePublished - Oct 1 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design

Keywords

  • Algorithms
  • Compatible triangulations
  • Controllable Morphing
  • Geometric algorithms, languages, and systems
  • I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - Curve, surface, solid, and object representations

Fingerprint

Dive into the research topics of 'Controllable morphing of compatible planar triangulations'. Together they form a unique fingerprint.

Cite this