M.Sc Thesis

M.Sc StudentKatz Sagi
SubjectPolyhedral Surface Decomposition and Applications
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROFESSOR EMERITUS Ran Ginosar
PROF. Ayellet Tal


Cutting up a complex object into simpler sub-objects is a fundamental problem in various disciplines. In image processing, images are segmented while in computational geometry, solid polyhedra are decomposed. In recent years, in computer graphics, polyhedral surfaces are decomposed into sets of simpler sub-surfaces that are easier to handle and manipulate. The major problem, however, is how to decompose an object.

In this thesis we propose a new hierarchical surface decomposition algorithm and use it in three applications. The idea behind the algorithm is to separate the decomposition into two stages. In the first stage the patches which  encircle the main parts of the input object are found. In the second  stage the final cuts between the patches are found.

The algorithm proposed has a few benefits over previous algorithms. First, while previous algorithms produce ``flat'' decompositions, our algorithm produces hierarchical ones. As a consequence, should the number of components be refined, the whole decomposition does not have to be calculated from scratch.  oreover, components which belong to a refined decomposition are contained in components of a coarser decomposition, which is usually a desired property.

A Second benefit of the algorithm proposed is in the way boundaries between components are handled. Previously, the focus has been on generating either meaningful components or components which comply with certain geometric properties. The boundaries between the components, however, were a by-product of the process. As a result, the boundaries were often too jagged or too straight in a way that did not always fit the model. The current algorithm aims at avoiding jagginess, by specifically handling the boundaries. Finally, the algorithm avoids over-segmentation and decomposes the objects into meaningful components.

We demonstrate the use of our algorithm in three applications. The first application is skeleton articulation which is a novel application for a surface decomposition algorithm. This skeleton is used to control non-rigid animations in real-time. The second application is finding a correspondence for metamorphosis. Given two objects, they are first decomposed using our decomposition algorithm. A correspondence between the parts of the two objects is established, maintaining the boundaries between the components. Finally, our algorithm is used in the creation of 3D puzzles, which is also a novel application.