טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentYakersberg Evgeny
SubjectMorphing between Geometric Shapes using a Straight-Skeleton-
Based Interpolation
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet


Abstract

In this thesis we design and implement a 2-dimensional morphing technique between polygonal shapes, based on a 3-dimensional surface interpolation between them. A shape may consist of several non-intersecting contours (each one is a simple polygon), possibly nested within each other. A major challenge of this problem is morphing between shapes having different geometries and topologies. Our approach involves surface reconstruction (or interpolation) between the source and target shapes, and then extraction of intermediate slices. This is accomplished by slicing the solid object bounded from below and above by the original shapes embedded in parallel planes, and by the interpolated surface between the two planes. Using a dense-enough series of intermediate planes, the resulting sequence of slices can be used for visualizing the morphing between the original shapes. Our approach is naturally extended to the general case of n parallel polygonal shapes, for n>2.


The solid objects constructed by the interpolation often have irregular boundaries and sharp dihedral angles between faces. This is not always suitable for the reconstructed object, and it often creates disappointing artifacts in the morphing process. We propose a subdivision smoothing scheme, which is adopted from a spline subdivision scheme. In order to make this scheme operate on a set of 2D parallel cross-sections, we define the straight skeleton average, and base the subdivision scheme on this average.