Visualisation de surfaces implicites
Projet Réalisé par Nicolas de Mauroy (promo 96)
Description du projet
On peut définir une surface quelconque par une équation de
type f(x,y,z)=0. Le projet a pour but d'approcher cette surface par un
ensemble de polygones visualisables par exemple sous Geomview. Pour cela,
on divise l'espace en cubes élémentaires et on analyse le
cas échéant l'intersection du cube avec la surface. J'ai
choisi de réaliser un programme optimisé ne permettant d'analyser
que des fonctions suffisamment régulières. Ceci m'a ammené
à m'interroger sur les possibilités d'approcher, avec des
fonctions regulieres, les opérations basiques de la csg. Des résultats
intéressant ont été obtenus dans ce domaine.
Algorithmes utilisés
Diviser l'espace en un réseau de cubes revient à disposer
de N^3 cubes, ou N est la "finesse" du réseau. La structure naive
de stockage des valeurs de f sur chaque cube est en N^3. Comme on peut
etre amené à travailler, surtout pour des objects complexes
ou "allongés" avec une grande résolution, on sera vite limité
par la taille mémoire d'un objet en N^3. Il faut donc trouver une
autre structure qui ne stocke que les cubes nécessaires mais qui
permette également un accès rapide aux données, puisque
l'on sera amené à regarder, par exemple, les voisins d'un
cube. J'ai choisi une structure d'arbre à 8 branches. Chaque cube
est divisé en 8 sous cubes, chaque sous cube est divisé lui
même en 8 petits cubes et ainsi de suite jusqu'à obtenir la
finesse désirée. On ne mémorisera un cube, à
n'importe quel niveau que si il possède des sous cubes intéressants.
Le schéma suivant montre, en deux dimensions, la démarche
suivie. Les cubes colorés ne sont pas mémorisés.
Le projet commence par calculer, pour chaque petit cube, la valeur de
la fonction f. Il memorise la valeur de f sur le cube ( sur un octet )
si la fonction y change de valeur. L'algorithme récursif élimine
automatiquement de l'arbre les branches inintéressantes. Ensuite,
les zéros de la fonction sur les arêtes des petits cubes sont
calculés. Puis, en fonction de la valeur de f sur chaque petit cube,
les polygones sont créés. Comme ces polygones ne sont pas
forcément plans, on les décomposera en plusieurs triangles.
La plupart des fonctions utilisées par le programme sont récursives
ce qui permet au code d'être relativement compact. Le programme est
optimisé pour des fonctions non pathologiques ( c'est à dire
c1 ou c2 ).
Résultats obtenus
Le but initial du projet était d'obtenir des rendus rapides et si
possible de qualité d' "objects mous". L'image suivante montre qu'une
qualité acceptable ( légèrement inférieure
à du raytracing classique ) peut être obtenue rapidement.
L'affichage d'un tel object comprenant de l'ordre d'une centaine de milliers
de polygones se fait en quelques secondes, le calcul des polygones en environ
deux minutes.
Il a été également trouvé des fonctions
au calcul simple permettant d'approcher les volumes de base de la CSG,
et, dans une certaine mesure, de réaliser des opérations
dessus. Certains résultats intéressants sont montrés
ci dessous.
En utilisant des champs en 1/R^2, on obtient facilement des modèles
de champs de gravitation permettant, par exemple, de dessiner de
façon réaliste des mollécules ( ces objects sont souvent
appelés "blobs"). Par exemple, on aura obtenu ci dessus une représentation
de mollécule diatomique.
Ci dessous sont montrés des résultats obtenus pour représenter
approximativement un cube, un cylindre, et une différence de deux
sphères.
Problèmes rencontrés et solutions apportées
La principale difficulté du projet est de réaliser les fonctions
qui gèrent de façon efficace la structure spéciale
d'arbre à 8 branches. Ces fonctions sont récursives et de
débugage difficile. La programmation a été facilitée
en utilisant la structure d'espace vectoriel de {0,1} du cube unité.
Le programme utilisé est efficace, mais ne permet que l'utilisation
de fonctions régulières. De plus, pour obtenir un temps de
calcul raisonnable, il faut que la fonction soit relativement simple. J'ai
donc cherché des fonctions approchant les formes simples ( cube,
sphère, tore, cylindre ) et permettant les opérations de
la CSG, c'est à dire intersection, union, différence.
En utilisant des fonctions du type f(x)=1/(1+g(x)^16) avec g(x)<1 à
l'intérieur du volume et g(x)>1 à l'extérieur, on
obtient des surfaces tout à fait acceptables pour un temps de calcul
extrêmement raisonnable.
Retour à la liste des projets réalisés