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.