Ph.D Thesis | |
Ph.D Student | Surazhsky Vitaly |
---|---|
Subject | Morphing Piecewise Linear Shapes Using Convex Representations |
Department | Department of Computer Science | Supervisor | PROF. Chaim Craig Gotsman |
Morphing, also known as metamorphosis, is the gradual transformation
of one shape into another. An algorithm to morph two simple polygons
with a correspondence between their vertices is presented.
The algorithm is the only solution to the polygon morphing problem
that analytically guarantees that the intermediate polygons are also
simple. This is achieved by reducing the problem to planar
triangulation morphing, for which morphing techniques, which preserve
triangle orientations have been developed.
To perform the reduction, it is necessary to compatibly triangulate
the interiors of the source and target polygons, and certain regions
exterior to the polygons. The basic algorithm is extended
to deal with not only simple polygons but any connected
straight-line plane graphs called `stick figures'.
Several algorithms to generate compatible triangulations of two polygons
are presented. One of the algorithm produces compatible triangulations
such that the number of additional (Steiner) vertices is close to optimal.
Being close to optimal in terms of the number of Steiner vertices, these
compatible triangulations are usually not of high quality, i.e., do not
have well-shaped triangles. The quality of these triangulations can be
increased by adding Steiner vertices in a compatible manner,
using several novel techniques for remeshing and mesh smoothing.
This allows to produce high-quality compatible triangulations with
a small number of triangles.
Such triangulations may be used for constructing sweeps,
suitable for finite element analysis, between two base polygons.
We also demonstrate how to exploit the developed techniques
for remeshing planar triangulations for 3D triangular meshes.
To be able to apply our 2D remeshing techniques to arbitrary genus 3D meshes,
we use a novel technique for constructing a dynamic patch-wise
parameterization. In addition, we show that mesh quality can be
improved further by improving the mesh regularity using a new simple
and efficient algorithm.