טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentPekerman Diana
SubjectOptimization of the Metamorphosis Process between Freeform
Curves
DepartmentDepartment of Applied Mathematics
Supervisor Professor Gershon Elber


Abstract

Metamorphosis, also known as morphing, is the continuous deformation of one shape into another. 2D and 3D metamorphosis of objects has gained popularity in computer animations, as seen in the film and television industry, due to its strong visual appeal. This research focuses on three problems related to metamorphosis: the similarity between two freeform curves, a monotone length-preserving metamorphosis of freeform curves, and global self-intersection detection and elimination in metamorphosis of freeforms.


We start by presenting an algorithm to answer the following fundamental question: ''Given two arbitrary (piecewise) polynomial curves, are they the same?'' This basic question in CAGD is answered by reducing the two curves into canonical irreducible forms. This reduction is conducted by reversing the processes of knot refinement, degree raising, and composition. Once in their irreducible forms, the two curves are compared and their shared domains, if any, are identified. The ability to answer this fundamental curve-identity question is not only crucial in metamorphosis applications, but is also expected to be a boon for numerous other applications.


Having presented our first algorithm, we consider two planar freeform curves in the same/parallel planes. The easiest approach to the metamorphosis of two planar curves is a simple convex combination between them. Unfortunately, this approach usually fails to create an intuitive and visually pleasing effect due to the shrinkage of the intermediate curves. We present a monotone-length-preserving (MLP) metamorphosis algorithm that creates a more satisfactory in-between motion of the intermediate curves. This algorithm constructs tangents to the intermediate curves, finds an approximation surface to the constructed tangents, and then integrates the approximation surface with boundary conditions to achieve a monotone length-preserving metamorphosis. We show that under certain considerations the metamorphosis is locally self-intersection-free.


Finally, we present an algorithm for global self-intersection detection and elimination in metamorphosis of freeform curves. We use a surface bi-normal line criterion to detect antipodal points on loop intersections, which is done by solving a system of five multivariate polynomial constraints, one of which is an inequality. Then, we gradually flip the location of the antipodal points by setting a set of constraints, until the resulting metamorphosis is globally self-intersection-free.