Optimal

Important Techniques！
Graphics Deformation
Texture Warping
As-Rigid-As-Possible Shape Interpolation!
(SIGGRAPH 2000)

A Simple Construction [1]
Additional O(n2) Steiner Points

High Quality Com. Triangulations[2]
Calculate minimum-link
Create link-paths (Costly act!)

The Problems
Can this be fast? (Real-time perform?)
How to get better result? (Regular triangles and better shape)

Our Algorithm
1) Create Compatible Polygons
(Force Target Sub-Polygons to be Convex)
2) Triangulate Source Sub-Polygons
3) Pre – Optimize!
4) Smooth Surface Fitting
5) Combine the Pieces of Meshes

Performance —— Our Algorithm

Performance [1]

Performance [2]

Performance [1]

Performance —— Our Algorithm

A Lower Bound

Contrasts

The Future!

References
[1] Boris Aronov, Raimund Seidel, Diane Souvaine. On Compatible Triangulations of Simple Polygons. Computational Ceometry: Theory and Application, 3:27-35, 1993.
[2] Vitaly Surazhsky, Craig Gotsman. High Quality Compatible Triangulations. 11th International Meshing Roundtable, Ithaca, NY, September 2002, pages 183-192.
[3] Michael S. Floater. Parametrization and smooth approximation of surface triangulations. Elsevier Science B. V. 1997.
[4] Vitaly Surazhsky, Craig Gotsman. Morphing Stick Figures Using Optimized Compatible Triangulations. Pacific Graphics 2001.
[5] Craig Gotsman, Vitaly Surazhsky. Guaranteed intersection-free polygon morphing. Computers & Graphics 2001.