Abstract
[Japanese | Thesis | Researches in Minoh Lab | Minoh Lab]


Elimination of Local Self-intersection on Three-dimensional Metamorphosis between patch-models


In this report, we propose a method for eliminating local self-intersection on three-dimensional metamorphosis between patch-models. A patch-model represents a three-dimensional shape of an object and consists of vertices, edges, and faces. Metamorphosis is the procedure to describe continuous transformation by creating a series of intermediate models between two models. Our ultimate goal is to describe a real shape transformation of an object, such as growth of human embryo, by using metamorphosis.

Any methods of metamorphosis between two patch-models consist of the following two steps. The first step is to establish a correspondence between the vertices of two patch-models. The second step is to generate the trajectories between the correspondent vertices, which is referred to interpolation problem. A simple method, such as linear interpolation, gives a solution for the interpolation problem. Even though we have precise correspondence of vertices between two models, the trajectories of vertex generated by a simple method may differ from real trajectories.

A self-intersection on the metamorphosis between two patch-models is a problems caused by the difference between metamorphosis and real transformation. The self-intersection is the phenomenon that the surface of an intermediate model intersects with itself. When a model represents a real object, the self-intersection of the model has to be eliminated. When we describe a shape transformation of an object in real world by metamorphosis, all intermediate models should be self-intersection-free. In recent years, many algorithms have been proposed about the metamorphosis, but no algorithm has been proposed yet to guarantee the metamorphosis self-intersection-free for three-dimensional models.

If the correspondence problem has solved correctly, the self-intersection is caused by the difference between real trajectories and ones that generated in the metamorphosis. Self-intersections are classified into two groups by this difference. One is caused by a method for interpolation problem. The other is caused by real transformation that is too complex to be estimated. Our goal is to eliminate self-intersections caused by an inappropriate interpolation. But it is difficult to classify all self-intersections into two groups.

The method of self-intersection detection used here for a patch-model is based on the conventional methods of intersection detection between two models. Any self-intersection can be detected by checking all pairs of faces in one patch-model. The position of self-intersections on three-dimensional metamorphosis can be detected with the trajectories of vertices. A collision can be detected from the relationship among 4 vertices. If a set of 4 vertices leads the collision and one of the 4 vertices is directly connected to the other 3 vertices, we call it "Local self-intersection". We try to eliminate a local self-intersection by modifying the trajectory.

To evaluate our method, we applied it to the patch-models of human embryo, showing the effectiveness of our method. We also discussed the relationship between the results and the classification of self-intersection in metamorphosis.


Go back to Thesis Page