Maillage de surfaces implicites

Application à des objets C.S.G

Projet réalisé par Laurent MEUNIER (promo 96)

Description du projet.

En imagerie tridimensionnelle, on distingue généralement deux manières de définir le modèle 3D d'un objet : la définition polygonale, qui réduit l'objet à un ensemble fini de facettes, et la définition implicite, où l'objet est un domaine de l'espace définit par une fonction mathématique (par exemple "x²+y²+z²-1<0" pour la boule unité"). Chaque méthode est associée à un procédé d'affichage particulier. Les modèles implicites sont usuellement rendus par la technique du lancé de rayon, qui donne des images de bonne qualité mais est très coûteuse en temps de calcul par rapport à l'affichage de facettes.

De plus, dans de nombreux domaines (simulation physique, imagerie médicale…), les données sont disponibles sous forme du champ scalaire (échantillonné ou défini par une équation). Le problème de la visualisation de ces données se ramène alors à celui de surfaces implicites. Pour cumuler les avantages des ces deux définitions (rapidité d'affichage pour les modèles polygonaux, compacité et exactitude pour les modèles implicites), il peut être intéressant de créer des algorithmes permettant de passer de l'une à l'autre. L'objet de mon projet est le passage d'une définition implicite vers un modèle polygonal, par une opération appelée maillage.

J'ai choisi de donner une orientation plus personnelle à ce projet, en m'intéressant plus particulièrement aux objets dits C.S.G (géométrie solide constructive), c'est à dire obtenus par unions, intersections et soustractions de volumes élémentaires appelés primitives (p.e. la sphère, le plan, le cône, le cylindre sont des primitives). En effet, les fonctions implicites sont particulièrement bien adaptées à ce type d'objet: les primitives ont des équations très simples, et les opérations booléennes (union, intersection…) sur les objets se traduisent très simplement en terme de fonctions implicites. En particulier, il semble possible d'obtenir un méthode de maillage rapide pour des objets C.S.G complexes.

Je me suis donc fixé comme objectif de concevoir en C++ un exécutable capable d'interpréter un fichier de définition d'objet C.S.G et de produire en sortie la description polygonale au format GEOMVIEW (standard UNIX) de l'objet correspondant.

Description des algorithmes utilisés.

Le principe de cette méthode de maillage est de diviser l'espace en un nombre fini de cellules cubiques bien choisies, en ne gardant parmi elles que celles qui rencontrent la surface de l'objet. On fait l'hypothèse qu'à l'échelle de chaque cellule, la surface de l'objet est à peu près plane, ce qui permet à partir de quelques points échantillonnés de créer un polygone approximant la surface dans la cellule considérée.

Figure 1: Le pas de la grille détermine la finesse du maillage.

L'ensemble de ces cellules peut être structuré en un arbre hiérarchique tridimensionnel communément appelé octree. Cette structure permet de définir une subdivision adaptive de l'espace, i.e une subdivision plus ou moins fine selon la zone dans laquelle on se trouve. En construisant un octree adapté à la fonction implicite sur laquelle on travaille, c'est à dire plus fin lorsque la courbure de la fonction est forte , on obtient un maillage raffiné des zones comportant des détails, plus grossier des zones planes.

Voici les différente étapes de l'exécution du programme:

(1) Lecture du fichier de définition et construction de la fonction implicite sous forme d'un arbre.
(2) Détermination d'un octree adapté à la surface (par propagation d'une cellule de taille variable le long de la surface).
(3) Echantillonage des sommets du maillage (les intersections des arêtes de l'octree avec la surface).
(4) Calcul des arêtes principales du maillage.
(5) Création des polygones s'appuyant sur ces arêtes et triangulation.
(6) Enregistrement du maillage obtenu au format geomview.

Cependant, la qualité visuelle du maillage obtenu est cependant décevante: en effet, les arête vives de l'objet - dues aux intersections entre primitives – sont presque toutes déformées et biseautées (car elle n'appartiennent à aucune facette de l'octree). J'ai donc ajouté une étape qui permet de récupérer le tracé de ces arêtes en divisant convenablement tous les triangles à cheval sur plusieurs primitives.

Figure 2: visualisation du maillage avant récupération des arêtes vives

Figure 3: visualisation du maillage après récupération des arêtes vives

Résultats obtenus et améliorations possibles.

Voici un script de définition et quelques images de maillages obtenus avec cet algorithme.

EXEMPLE DE SCRIPT (correspondant aux deux premières images):

#définitions des objets

PLAN 1 0 0 -1 0 0 INTER
PLAN -1 0 0 1 0 0 INTER
PLAN 0 1 0 0 -1 0 INTER
PLAN 0 -1 0 0 1 0 INTER
PLAN 0 0 1 0 0 -1 INTER
PLAN 0 0 -1 0 0 1 INTER
DEF cube

CYL -1 0 0 1 0 0 0.4
CYL 0 -1 0 0 1 0 0.4 SUNION 2 0.1
CYL 0 0 -1 0 0 1 0.4 SUNION 2 0.1
DEF croix

croix COL 1 0 0
croix SCAL 0.7 0.7 0.7 COL 0 0 1 SUB
cube SCAL 1.5 0.7 0.7 COL 1 1 0 INTER
DEF objet

#lancement du maillage
PARAM 0.1 0.6 1024 #(pas minimal, pas maximal, dimension maximale de la racine)
objet
MESH tuyaux.geom

Les critères de qualité que l’on peut appliquer au maillage d’une surface implicite sont la rapidité, la robustesse (traitement des cas particuliers), le respect de la topologie du volume initial, le rapport de la qualité de l’approximation polygonale sur le nombre de polygones produits.

La procédure critique en terme de rapidité d’exécution est l’évaluation de la fonction implicite. J’ai essayé de limiter au maximum le nombre d’appels de cette procédure au cours d’un maillage. On pourrait encore améliorer considérablement la vitesse de l’évaluation elle-même en introduisant des " bounding boxes " permettant de ne calculer que les parties utiles de l’arbre de fonctions.
Le problème de la topologie est volontairement pris en compte de manière un peu simpliste dans mon programme, car généralement les volumes C.S.G n’introduisent pas d’ambiguïtés topologiques.
La robustesse par contre demanderais encore un peu de travail. Il arrive en effet qu’une facette disparaisse, et des problèmes se posent lorsque plusieurs surfaces sont accolées.
Enfin le rapport qualité/taille des données est grandement amélioré lorsque l’on utilise une grille adaptive (l’octree) au lieu d’une grille régulière, mais je pense que l’on est encore loin de la solution optimale. Ceci étant dû notamment à la contrainte imposée sur la forme des cellules (cubiques de taille 2ⁿ). Des solutions du type migration de points donneraient je pense de meilleur résultats, mais imposeraient des temps de calcul supérieurs.

Retour à la liste des projets réalisés