On travaille sur deux modèles A et B, simplement connexes, c'est à dire ne comportant pas de "trous". Pour simplifier nous utilisons en fait des objets étoilés : on peut pour chacun d'entre eux trouver un centre qui voit toutes les faces.
Le principe de l'interpolation est de créer une topologie commune aux deux modèles à partir des maillages initiaux triangulés, en passant par leur projection sur la sphère unité. Les deux modèles ayant alors le même nombre de points et la même triangulation, on peut trouver un homéomorphisme point par point entre les deux.
On peut alors faire une animation passant d'un modèle à un autre :
Algorithmes utilisés
La première étape est la lecture des modèles, la création des structures. Chaque modèle est centré, ce qui permet alors de projeter le maillage de chaque modèle sur la sphère unité : pA et pB.
se projette en
La fusion des deux maillages se fait sur la sphère unité. On parcourt les arcs du modèle pA et on note les intersections éventuelles avec les arcs du modèle pB. A l'issue de cette étape on possède tous les points du maillage commun : ceux de pA, ceux de pB, et les intersections pA/pB.
Par construction ces nouveaux points se trouvent sur un segment de pA et un de pB. On les ordonne topologiquement sur chacun de ces segments.
Avec toutes ces informations on peut alors trianguler le maillage commun, grâce à un parcours des segments des deux modèles, en avançant point par point. Cette étape de fusion est la plus délicate car de nombreux cas sont présents. Elle est simplifiée par le fait que les modèles initiaux sont triangulés, on sait donc que les polygones de la structure commune sont au plus des hexagones.
La dernière étape est la projection du maillage combiné sur les modèles A et B intiaux.
Résultats obtenus
Le plus simple est quand même de montrer des images et des animations...
Cliquer sur les images pour voir les animations gif
Le plus simple : l'octaèdre qui se transforme en cube.......
Très visuel : l'étoile et le ballon de foot.......
Intéressant : deux isocaèdres creux et pointus.......
Pourquoi pas : une bouteille de vin et une "étoile" tridimensionnelle.....
On prend les mêmes : la bouteille et l'isocaèdre pointu.....
Dernier petit plaisir : une haltère et un coeur.....
Problèmes rencontrés et solutions
Le principal problème rencontré est celui des cas dégénérés lors de la fusion des maillages. En effet lors de la superposition des deux maillages, si un point tombe sur un segment ou même sur un point de l'autre modèle l'algorithme échoue. Ces cas dégénérés ont une probabilité 0 d'arriver dans la nature, mais avec les modèles faits à la main... c'est une autre histoire! Même l'octaèdre et le cube étaient dégénérés à cause de leur trop parfaite régularité.
La solution trouvée a été de rajouter un bruit aléatoire lors du chargement des modèles, de l'ordre de 10^-3. Ainsi cela ne se voit pas à l'affichage. Le programme est plus robuste, on peut interpoler le coeur (200 points) avec lui même sans problème.
Cependant alors que théoriquement cette fusion ne devrait rien changer au modèle, on a désormais près de 3000 points ! Autant dire que beaucoup sont "inutiles" !
Une conséquence de cela est l'apparition de triangles minuscules près des intersections. Cela peut causer des problèmes d'arrondi au niveau des calculs du processeur. La solution choisie a été de travailler en double, ainsi aucun problème de ce genre n'a été rencontré.
se projette en
