Majeure "Algèbre, Informatique et Applications" Enseignement d'Approfondissement"

Projet Réalisé par Xiaolong Kong (promo 97)

1   Description

This project realized an algorithm efficient for the polyhedral models. Given two objects, the algorithm generates two new models who are formed by
triangles. Every new model has the same shape as the original one, both of them contain all topological informations of two given models, which allow
translation from one to another be easy. The algorithm used bases on two articles.[1][2] [3]
 
 

2   Algorithm

The principle problem of this project consists how to build two new models. We will limit problem in convex and star-shaped objects in order to simplify
discuss.

Firstly we project the two original objects onto a sphere, note their projected coordinates. Then we will calculate their intersection points and determin
relative situation of their vertices, edges and try to add one of them to another little by little and recursively. We call this step correspondence process.

Once we finished the correspondence process, rested work is to interpolate two new models. Since they have the same number of vertices, edges and faces,
it's sufficient to do a linear interpolation.

Here, I give my suggestions or pseudocode of several critical points.

First problem we encounter is to calculate intersection point of one face and one edge, in fact most of running time is spent to do this. The article[1] and
article[2] of J. R. Kent and W. E. Carlson suggested to calculate determinant, in fact we'd better use Guass's method to resolve linear equations. (Also useful
for intersection of two edges.)

The difficulty of correspondence process lies on the determination of relative situations of two objects' vertices and use these informations to creat a new
model on the sphere. In article[2], authors didn't give details about how to do it, I will complish their algorithm with pseu-docode
 
 

Of cause, to make it work, it need do a lot of preparing work, especially we need construct a well-formed data structure[1] . Okay, it's the main idea of
correspondance process, but things are always complicated, we will talk about possible problems of this algorithm:-(
 
 

3   Results

Take a look, following figures give an example of running results of my program:
 

You can see a big size image of it.
 
 
 

4   Problems

Although the algorithm is theoritically parfect, in fact, we often encounter problems: Firstly, the algorithm do calculates exaustively, as we can see in the
figure, even the object is not very complex, they will be separated in to many new tiny faces. While we do calculations of intersection of vertice and face,
edge and edge, small numerical inaccuracies often generate errors, so the result depends on sensively initial model datas. Pour resolve this problem, perhaps
we can't use precedent recursive method -- it's difficult to add additional control conditions who ensure computation to be correct.

To enconomise running time, the algorithm use a data structure quite complex, we use lots of pointers, familiar with how to correctly allocate and manage
pointer is primarily important. Since there are many options concerning pointer, it's not easy -- very difficult to find errors.

The algorithm doesn't yet deal with the cases that projected point coincides with vertex of the other model or it lies on one edge of the other model, so when
the two objects have regular shape, we'd better do some translations or rotations before running merging process
 
 

5  Other informations

You can find a PDF format or PS format file of this page and find my source code here.
 

References

   [1]James R. Kent, Wayne E. Carlson and Richard E. Parent, Shape Transformation for Polyhedral Objects. Computer ames Graphics (July, 1992), pp.
      47-54.
   [2]James R. Kent, Richard E. Parent and Wayne E. Carlson, Establishing Correspondences by Topological Merging: A New Approach to 3-D Shape
      Transformation. Graphics Interface '91, pp. 271-278.
   [3]Ekoule, A., Peyrin, F. and Odet, C. A Triangulation Algorithm from Arbitrary Shaped Multiple Planar Contours. ACM Transactions onGraphics 10, 2
      (April, 1991), pp. 182-191.