uvre
- Limites et contraintes du modèle
- Extensions possibles
- Elargissement des domaines d'application
- Organisation du projet
Rapport de projet
Carine NGUYEN - Bruno FISCHEL - Vincent THOREL - Pierre-Jean TURPEAU - Frédéric VIDIL
15 juin 2001
Dans ce document, nous abordons le travail réalisé sur un outil de conversion d'objets représentés en 3D classique vers une représentation en surfels. Cette représentation est à la base de nouvelles techniques de rendu permettant, entre autre, d'obtenir différents niveaux de détails tout en minimisant l'espace nécessaire pour le stockage des objets. Un objet classiquement représenté par un ensemble de polygones est alors modélisé par un nuage de points. On étudie donc ici les techniques possibles de surfelisation d'un objet et on s'interesse tout particulièrement à celle basée sur le principe du lancé de rayons, en étudiant et réutilisant le moteur offer par PovRay.
uvre
Jusqu'à présent, la méthode la plus classique pour représenter des objets 3D sur un ordinateur est l'utilisation de maillages polygonaux. Un maillage polygonal est un assemblage de plusieurs polygones reliés les uns aux autres, afin d'approximer une surface. Aujourd'hui les objets 3D utilisés sont composés de milliers, voir de millions de polygones et ce modèle a ses limites. Ainsi, lorsqu'un objet complexe est vu de loin, il arrive très souvent que des polygones qui le compose soient réduits à de simples points [3].
De ce fait, dans bon nombre de cas, il en résulte une consommation inutile des ressources, aussi bien processeur que mémoire, dès que la taille des polygones est inférieure à un pixel.
Pour résoudre ce problème, des travaux récents proposent d'utiliser
des points plutôt que des polygones pour développer une représentation
des objets 3D adaptée à un rendu efficace [7]. Ce modèle se
base principalement sur une primitive [6] appelée surfel
. C'est un élément discret de surface 3D constitué de
trois attributs (une position dans un espace à trois dimensions, une
orientation et une couleur) et obtenu à partir de l'échantillonage
d'un objet 3D selon plusieurs techniques possibles.
Typiquement, ce modèle s'adapte surtout à des applications utilisant
des objets complexes composés d'un très grand nombre de polygones,
pour les jeux par exemple. En effet, les techniques de visualisation
proposées permettent de gérer le niveau de détail du rendu, et
ainsi de maîtriser complètement les ressources utilisées [2]
[5] [1].
L'objectif de ce projet est donc de réaliser un logiciel permettant de
convertir une représentation d'un objet 3D en une représentation
utilisant les surfels selon un taux d'échantillonnage
donné. Nous avions deux axes de travail possibles pour parvenir à ce
résultat. D'une part nous pouvons échantilloner les objets selon la
méthode du lancé de rayon, les objets sont alors représentés sous
formes de constructions géométriques (CSG). D'autre part nous pouvons
échantilloner des objets représentés par un assemblage de polygones,
il faut alors traiter les polygones un à un.
Afin de répondre aux attentes du client, qui souhaitait avant tout un
outil efficace, susceptible de fonctionner dans un environnement UNIX
et facilement maintenable, nous avons choisi de nous concentrer sur la
méthode du lancé de rayon, bénéficiant ainsi d'outils et de techniques
déjà bien maîtrisés [4]. Ensuite, nous pourrons éventuellement
nous pencher sur le problème des polygones et de l'optimisation de la
conversion afin de résoudre le problème lié aux grappes de surfels.
La réalisation de ce projet nécessite les materiels et logiciels suivant:
Les personnes susceptibles d'intervenir en cours de réalisation du
projet sont:
Les phases de l'étude préalable sont les suivantes:
Certaines phases du projet peuvent se réaliser de manière concurrente. Notamment la documentation du projet se réalise tout au long des phases de conception et de réalisation. De plus, une réunion sur l'avancement du projet a lieu chaque semaine. Elle regroupe l'équipe projet et le client.
Livrables papier :
Surfels
Livrables logiciels :
L'objectif est de convertir des objets géométriques en objets composés de surfels. L'intérêt du stockage des objets au format surfels est le gain mémoire pour les objets complexes ne comportant pas de surfaces planes.
Le diagramme de flots (figure 2.1) met en évidence les différents modules et étapes nécessaires à la réalisation du convertisseur.
L'architecture générale du convertisseur sera principalement basée sur
les fonctionnalités de PovRay. On tentera ainsi de réaliser une
bibliothèque regroupant les services nécessaires à la conversion. La
réutilisation du code de PovRay permet un gain de temps indéniable car
on dispose d'un modèle déjà existant pour la représentation des objets
et d'outils puissant pour effectuer tous les calculs dont nous
pourrions avoir besoin.
Notre modèle des données est basé sur celui de PovRay en ce qui
concerne l'architecture interne (gestion des objets en mémoire,
etc...). Notre programme se contentera d'appeler les fonctions de
calcul de PovRay afin d'effectuer la conversion de l'objet en surfels.
La première contrainte de conception est l'utilisation presque obligatoire des sources du logiciel PovRay. En effet, la plupart des fonctions nécessaire à notre convertisseur ont précédemment été implémentées dans ce logiciel. De plus, une implémentation personnelle ne serait pas codable dans les temps impartis pour cette étude.
La décision d'utiliser PovRay implique que les objets 3D doivent être
décrit à partir de primitives géométriques au format ``.POV''. Dans
un premier temps, cela peut être considéré comme étant une contrainte
forte dans la mesure où la plupart des objets sont définis dans bien
d'autres formats tels que DFX, 3DS ou LWO. Or il apparaît que PovRay
contient une primitive facette, ce qui induit la possibilité
de convertir les formats ``polygonaux'' classiques vers le format
POV.
Le logiciel devra pouvoir s'utiliser soit seul (en mode ligne
de commande avec des options diverses) soit en tant que
bibliothèque inclus dans un autre logiciel. Une interface
permettra donc d'effectuer des appels aux fonctionnalités
diverses du programme.
En ce qui concerne la structure du fichier de sortie, le client nous a
proposé un modèle simple qu'il utilise avec ses propres
visualisateurs. Le fichier de sortie sera au format texte, et trois
lignes seront nécessaires pour décrire chaque surfel de l'objet. La
première ligne contiendra les coordonnées 3D du surfel, la seconde
ligne contiendra les coordonnées 3D de la normale et enfin la
troisième ligne contiendra les couleurs RVB du surfel. Nous
n'utiliserons que des réels.
Dans cette sections nous aborderons 3 types de besoins non fonctionnelles:
La première contrainte non fonctionnelle serait l'étude du logiciel PovRay. Ses fonctions n'étant absolument pas documentées, on ne peut que supposer leur fonctionnement en s'aidant du nom de celles-ci. Ce besoin est non fonctionnel dans la mesure ou on ne pourra garantir le bon fonctionnement du logiciel de conversion que si les fonctions utilisées font ce à quoi l'on s'attend.
La seconde contrainte non fonctionnelle concerne
l'algorithme employé pour la génération d'objets en surfels:
on part de l'objet en 3D géométrique, puis on échantionne sur
chaque axe X, Y et Z selon un pas prédéterminé, si un rayon
rencontre la surface d'un objet, on crée alors un surfel. Le
problème concerne la répartition des surfels, ils ne sont pas
uniformément répartis sur la surface de l'objet. Il serait
intéressant de trouver un algorithme qui soit capable
d'éliminer certains surfels (voir d'en ajouter) afin d'obtenir
une répartition des surfels uniforme.
La dernière contrainte est l'utilisation du projet
dans d'autres produits qui voudront mettre en place une
conversion en temps réel d'objets de polygones 
Surfels avec des contraintes de vitesse. Ici nous somme
tributaires de l'utilisation du code source de PovRay - ce qui
limite notre vitesse de conversion. De plus l'utilisation des
surfels n'est intéressante que si la conversion offre un gain
d'espace mémoire intéressant, ce qui n'est pas toujours le
cas. Donc il faudra mettre en uvre des méthodes d'analyse
permettant de simplifier la représentation des objets en
surfels pour que leur utilisation mémoire soit intéressante.
Le développement du logiciel est basé sur l'API de PovRay et se fera intégralement en langage C. De ce fait, il ne devrait pas y avoir de plateforme cible type et ainsi toute architecture supportée par PovRay devrait être supportée par notre convertisseur. Le code sera principalement écrit et testé sur des terminaux X sous SunOS et sur des PC sous Linux.
La longueur de ce projet sera modulée en grande
partie par le temps que prendra l'analyse des fonctionnalités
de PovRay. Le risque le plus important de ce projet est la
réutilisation du code source de PovRay. En effet, en
l'absence de documentation sur son organisation, beaucoup trop
de temps peut être consacré à l'analyse et à la compréhension
du fonctionnement des méthodes de PovRay. Et il semble qu'il
n'y ai pas de parade possible compte tenue du temps dont nous
disposons.
Les priorités de ce projet sont les suivantes:
Nous verrons dans ce chapitre nos réflexions préliminaires sur le sujet du projet. Cette étude présentera également les documents de travail qui ont été à la base du développement du logiciel et de son architecture.
Pour réaliser ce que souhaitait le client, à savoir convertir un objet représenté en 3D classique en une représentation sous forme de surfels, nous devions choisir quel serait le format d'entré du convertisseur (la grammaire du fichier de description des objets 3D). Ce choix conditionne bien évidemment les techniques à utiliser pour effectuer la conversion. Nous avons ciblé deux possibilités.
La représentation en maillages polygonaux (figure 3.1) est le modèle le plus utilisé par les nombreux modeleurs du marché pour stocker les objets en mémoire. Un objet est alors un ensemble de polygones collés les uns aux autres afin de constituer une surface ``linéaire''.
Il s'agit typiquement de formats assez répandus tels que les fichiers
3D Studio (3DS) et LightWave (LWO). Bien que séduisante
car très répandue, l'utilisation de cette représentation comporte
malgré tout plusieurs défauts.
Le premier est que ces formats de fichiers sont dans la plupart des
cas privés et aucune description officielle publique des grammaires
n'est disponible sur le réseau. Même si de nombreuses spécifications
non officielles sont accessibles, on ne peut s'en satisfaire car
forcement incomplètes et ne bénéficiant pas nécessairement de mises à
jour régulières.
De plus, dans le cas de 3D Studio, il peut arriver que les
objets créés utilisent des textures fournies avec le modeleur. Or,
une des exigences du client est que toutes les caractéristiques des
objets soient conservées, ce qui signifie que l'on doit tenir compte
des textures appliquées aux objets pour calculer la couleur des
surfels. Dans ce cas, toute conversion d'un fichier 3DS impose la
présence sur la machine des textures du modeleur, et donc l'achat
d'une licence qui coûte relativement chère si on ne souhaite faire que
des conversions.
La représentation CSG (Constructive Solid Geometry) est une représentation plus formelle des objets basée sur des opérations simples que l'on applique à des primitives géométriques. Ces opérations peuvent être l'union, l'intersection, la soustraction sur des objets élémentaires tels que le cube, la sphere, le plan ou le cylindre (figure 3.2).
En réalité cette représentation n'a pas d'avantages en soit, mais elle est la base d'un logiciel bien connu de lancé de rayon (figure 3.3) appelé PovRay. Il permet de générer des images et des animations de scènes 3D grâce à la technique du lancé de rayons dont nous verrons tout l'interêt dans la section 3.2.2.
Afin de justifier le choix du format et du type de fichier d'entré du convertisseur, nous avons procédé à une première étude des techniques possibles permettant d'échantillonner des objets 3D.
Elle dérive du principe de l'application d'une texture sur un polygone 2D (mapping). En fait, cette technique s'applique plutôt dans le cadre d'un système purement polygonal. En général, dans un système à maillages polygonaux, chaque polygone est composé de trois points, chaque point à une coordonnée dans un espace à 3 dimensions et une coordonnée dans une texture.
En fait, il suffit d'interpoler les coordonnées 
du
polygone dans la texture le long de ses arêtes dans l'espace à 3
dimensions (figure 3.4). Puis on interpole
``horizontalement'' ces coordonnées qui nous permettent de récupérer
la couleur dans la texture lorsqu'on échantillonne un surfel. Cette
opération doit être répétée pour chaque polygone de l'objet.
L'échantillonnage d'un objet ne se réduit pas seulement à l'échantillonnage des polygones qui le constituent. Basée sur le principe du système de scanner 3D laser (système d'acquisition de données 3D à partir d'objets rééls), une autre technique, utilisant le principe du lancé de rayon est à notre disposition.
Cette technique consiste à lancé des rayons dans la direction d'un
objet et de calculer les intersections du rayon avec cet objet. Chaque
intersection représente donc un surfel dont on doit pouvoir calculer
la couleur et l'orientation. On obtient ainsi un nuage de points qui
est la modélisation en surfels de l'objet. Afin d'assurer que les
surfels ne sont pas trop éloignés, on lance les rayons dans trois
directions différentes. Ainsi, la distance maximale entre deux surfels
est inférieure à 
(diagonale d'un cube de côté un).
Le mécanisme de prise de vues multiples est de toute façon nécessaire
afin de garantir que l'on ne génère pas que les surfels visibles à
partir d'une position donnée de caméra.
Pour le développement de notre programme nous avons choisi de réutiliser l'architecture de PovRay. Se baser sur un tel outil pour développer notre convertisseur comporte de nombreux avantages. Tout d'abord, PovRay est un logiciel gratuit, assez répandu, robuste, performant et fréquement utilisé pour le rendu d'images construites avec des modeleurs conventionnels. Ensuite, les sources sont disponibles et librement utilisables dans le cadre de projets éducatifs. On dispose ainsi d'un système facilement maintenable, écrit en C, donc relativement portable (PovRay fonctionne sous Windows, Macintosh, Unix/Linus/SunOs, Amiga). De plus, cela nous permet de réutiliser le code au sein d'une bibliothèque de fonctions PovRay que nous aurons à mettre au point.
Grâce à cette bibliothèque de fonctions, nous bénéficions d'éléments
essentiels à notre convertisseur et déjà mis au point au sein de
PovRay. Ces différents modules sont :
On peut bien évidemment considérer le format spécifique de PovRay
comme une limitation à l'utilisation du logiciel, mais cela n'est pas
un réél problème dans la mesure où la grammaire possède une primitive
facette et la perspective da conversion des modèles polygonaux
classiques vers le format PovRay devient possible.
L'analyse du code source de PovRay est une partie non négligeable du projet. Cette section est donc principalement dédiée à cette analyse; mais elle est aussi un guide de référence des fonctions de PovRay utilisées dans le projet. L'objectif n'est pas la compréhension complète des sources de PovRay : nous voulons simplement réutiliser le maximum de code sans avoir à comprendre toutes les subtilités des algorithmes et des structures secondaires.
Voici, donné en vrac, les premières constatations que nous pouvons faire sur l'architecture de PovRay:
Le principal constat, c'est l'absence de documentation dans le
code source (ni même sur le Web): si nous n'avons aucune
documentation, nous ne pouvons connaître les objectifs des
fonctions que par leur nom et par des tests successifs.
Rappelons notre objectif initial concernant PovRay:
Il faut déterminer les modules qui implémentent ces méthodes et les structures employées.
La première méthode qui nous en apprend le plus sur le fonctionnement de PovRay est la fonction Trace() du fichier render.c. Celle ci montre en effet comment parcourir tout les objets d'une scène, comment calculer les intersections avec ces mêmes objets et quelles sont leur couleur et leur normale. C'est donc cette fonction qui va nous guider tout au long de cette étude:
![\includegraphics[width=.5\linewidth,angle=0]{yoda.eps}](img2.png)
![\includegraphics[width=.3\linewidth,angle=0]{surfel.eps}](img3.png)
![\includegraphics[width=1\linewidth,angle=0]{sample.eps}](img4.png)
![\includegraphics[width=.40\linewidth,angle=0]{flow.eps}](img6.png)
![\includegraphics[width=.5\linewidth,angle=0]{maillages.eps}](img8.png)
![\includegraphics[width=.8\linewidth,angle=0]{ex-csg.eps}](img9.png)
![\includegraphics[width=.8\linewidth,angle=0]{raytracing.eps}](img10.png)
![\includegraphics[width=.9\linewidth,angle=0]{mapping.eps}](img11.png)
![\includegraphics[width=.7\linewidth,angle=0]{rays.eps}](img13.png)
![\includegraphics[width=.6\linewidth,angle=0]{surfelization.eps}](img15.png)
for (Object = Frame.Objects; Object != NULL;
Object = Object -> Sibling)
{
if (Intersection(&New_Intersection, Object, Ray))
{
if(New_Intersection.Depth < Best_Intersection.Depth)
{
Best_Intersection = New_Intersection;
Intersection_Found = TRUE;
}
}
}
On voit aussi apparaître quelques lignes plus bas l'appel à la fonction suivante:
Determine_Apparent_Colour(&Best_Intersection, Colour, Ray, Weight);
Le principal problème de cette fonction est que les
paramètres des fonctions sont des paramètres d'entrée/sortie.
On peut quand même apprendre quelques informations
intéressantes: la normale est calulée dans le corps de cette
fonction et peut être extraite de la façon suivante:
Best_Intersection->INormal.
Concernant le parcours des objets de la scène, nous avons tout ce qu'il nous faut, la représentation interne des objets ne nous interesse pas puisque nous interagissons avec ceux-ci que par le biais des fonctions de PovRay.
Dans le module render.c on trouve la fonction intersection(). Elle retourne la première intersection d'un rayon avec un objet. Ce n'est pas exactement ce que nous cherchons puisque nous voulons toutes les intersections. Nous avons alors recherché l'implémentation de intersection() (elle se trouve dans object.h). Et enfin nous trouvons la fonction qui nous intéresse:
All_Intersections(OBJECT *, RAY *, ISTACK *);
Comme nous le verrons dans un prochain paragraphe, ISTACK * est une pile d'intersections entre un rayon et un objet.
frame.h contient toutes les structures de données nécessaire à la description d'une scène PovRay. Dans ce module, on découvre qu'il existe une fonction Inside_Object() qui nous sera utile pour la suite. Cette fonction permet de déterminer l'orientation des normales aux surfaces à un point d'intersection (rayon/objet). En effet, si la normale est orienté vers l'intérieur de l'objet, alors cette fonction retourne TRUE:
int Inside(VECTOR IPoint, OBJECT *Vector);
Le client veut que les normales des surfels pointent vers l'exterieur des objets. Cette fonction nous sera donc très utile si nous rencontrons des problèmes d'orientation des normales (ce qui à été le cas).
PovRay stocke ses principaux objets (avec CSG inclus) dans une variable globale aux modules nomée Frame. On peut parcourir ces objets de la façon la plus simple: il s'agit d'une liste chaînée :
for (Object = Frame.Objects; Object != NULL;
Object = Object -> Sibling)
{
/* Ici on applique nos analyses sur ``Object'' */
}
All_Intersections(OBJECT *, RAY *, ISTACK *);
Cette méthode calcule toutes les intersections entre un rayon et un objet et place le résultat sur une pile d'intersections ISTACK *. Si des intersections ont effectivement été trouvées, elle retourne TRUE sinon elle retourne FALSE.
Plutôt que de décrire chaque fonction, voici un exemple d'utilisation trouvé dans PovRay (objects.c: Intersection()):
ISTACK *Is;
Is = open_istack ();
if (All_Intersections (Object, Ray, Is))
{
while ((Local = pop_entry(Is)) != NULL)
{
/*
Ici on inclus le code qui traite l'intersection
``Local'' à ``Object''
*/
}
close_istack (Is);
}
Les fonctions open_istack() et close_istack() sont les fonctions d'initialisation et de libération d'une pile d'intersections. Nous avons remarqué que PoV possédait son propre module de gestion mémoire afin d'optimiser les allocations et libérations de blocs mémoire. Il n'est donc pas nécessaire de se préoccuper du fonctionnement exacte du système. Il nous suffit d'utiliser les structures de données de PoV.
Pour chaque intersection objet/rayon, on determine la normale orientée vers l'exterieur de l'objet ainsi que la couleur RGBFT du point d'intersection. Ces deux informations sont délivrées par l'intermédiaire de la fonction suivante:
Determine_Apparent_Colour(&Intersection, Colour, Ray, Weight);
Avant d'appeler cette fonction, il faut determiner une intersection et un rayon. Après l'appel à cette fonction, Colour est un vecteur décrivant la couleur au format RGBFT. La normale étant un champ de la structure INTERSECTION, on peut y accéder ainsi : (INTERSECTION *)->INormal.
Cette partie montre les modèles et diagrammes utilisés pour la conception du surfelizer. Les contraintes de développement imposent l'utilisation du langage C pour l'implémentation. Les diagrammes suivant servent à décrire la structure du projet:
diagramme des composants : Modélisation la structure modulaire du projet.
diagramme entité-relations : Structures de données employées et relations de dépendances.
Nous utilisons les abstractions du langage de modélisation graphique UML pour cette description.
Le but de ce diagramme est de représenter graphiquement les modules du surfelizer et leurs responsabilités.
options : Ce module est chargé de la gestion des options d'initialisation du surfelizer. Les fonctions de ce module vont, en fonction des paramètres lu sur la ligne de commande, appeler les fonctions spécifiques nécessaires de la librairie de fonction de PovRay.
interrupts : Ce module est chargé de la gestion des signaux.
pov_interface : C'est le module de base. Ses fonctions sont des redéfinitions des fonctions de la librairie de PovRay pour les adapter à notre projet.
pov_tools : Fonctions annexes, utilisées par le module pov_interface.
main : Implémente la fonction principale main qui fait appel aux fonctions des interfaces décrites précédemment.
Ce diagramme doit permettre d'avoir une vue plus précise des structures données utilisées par PovRay, et donc par notre surfelizer, pour représenter les objets, la scène et les rayons. Cette vue n'est que partielle; seules les structures directement manipulées par notre surfelizer sont montrées. De plus, par souçi de lisibilité, seuls les champs les plus importants des structures ont été représentés.
OBJECT : Propriétés physiques des objets (opacité, couleur, etc ...cf. champs Interior); relations entres objets (par exemple, placement relatif les uns par rapport aux autres) et boîte englobante.
INTERSECTION : Elle est propre à un objet (Objet). Elle nous renseigne sur la position spatiale de l'intersection, la distance de ce point par rapport au point d'observation, la normale à l'objet en ce point ainsi que sa couleur; c'est cette information que récupère le surfelizer.
RAY : Rayon partant d'un point donné (Initial) dans une direction déterminée (Direction).
uvre
Comme nous avons pris la décision de baser notre convertisseur sur PoV, il a fallu dans un premier étudier le code source de ce logiciel afin de repérer parmi toutes ses fonctionnalités celles susceptibles de nous aider dans notre travail.
Ce sont ces fonctions qui vont permettre de déterminer la position des surfels dans l'espace ainsi que leur vecteur directeur (correspondant à la normale de la surface se trouvant dans le voisinage du surfel).
Ce sont ces fonctions qui vont permettre de déterminer la couleur des surfels.
Cette étude préalable nous a permis de fixer le squelette de notre convertisseur et de spécifier une première ébauche d'interface de la librairie des fonctions de PoV.
Voici de manière informelle la liste des fonctions que nous y avons défini:
Il s'agît ici des manipulations de base (instanciation, initialisation, affectation, ...) qui n'ont rien de compliqué en elles-même mais qu'il était indispensable de définir clairement afin de rendre le code lisible et facile à maintenir.
Pour s'en convaincre, il suffit de regarder de près un objet intersection tel qu'il est défini par PoV. À notre niveau, les seules informations qui nous intéressent dans une intersection sont:
, 
et 
),
Or en réalité, pour chaque intersection PoV ne mémorise pas moins d'une dizaine d'attributs tels que la distance du point d'intersection à l'oeil de la caméra, un pointeur sur l'objet ``intersecté'' ainsi que de nombreux autres champs non documentés.
Il n'était pas du tout raisonnable d'initiliaser ``à la main'' tous ces champs. Cela aurait pollué le code et l'aurait rendu peu clair. Cela aurait aussi entraîné de nombreuses duplications de parties du code, ce qui d'un point de vue génie logiciel est très mauvais.
Il s'agît plus exactement d'une interface, car les fonctions développées dans ce module correspondent aux principales actions sémantiques de PoV qui nous intéressent.
Ces fonctions de haut niveau correspondent aux différentes méthodes de surfélisation que nous avons imaginées, qui sont:
Les fonctions du programme ont donc été regroupées en unités logiques, dont voici la liste:
Les méthodes de PoV ne sont jamais appelées directement. Le rôle de l'interface que nous avons spécifiée est de fournir toutes les fonctions nécessaires à la surfélisation.
En s'appuyant uniquement sur cette interface pour implémenter les autres modules, on s'assure donc la possibilité de mettre à jour facilement notre convertisseur au fil des évolutions de PoV.
De plus, le fait que les objets rendus puissent être définis par CSG induit que la structure utilisée pour mémoriser la scène soit arborescente. On a donc un arbre dont les feuilles sont des éléments atomiques (cube, sphère, tore, ...) et dont chaque sommet interne correspond à une opération de CSG (union, intersection, différence). Tous les sommets contiennent aussi une boîte englobante. Ainsi, ces boîtes englobantes sont imbriquées les unes dans les autres, à la manière de poupées russes (voir figure 6.1).
Cette organisation permet de réduire de manière drastique les temps de calcul pour peu que l'arbre de la scène ne soit pas dégénéré.
Or la représentation des objets par les surfels étant une alternative à leur représentation par les polygones, les recherches en cours sont plutôt axées sur la comparaison entre les deux représentations. Par conséquent, notre convertisseur devait être capable de surféliser des objets modélisés uniquement à l'aide de triangles. Et les fichiers PoV qui décrivent de tels objets sont rarement écrits directement; ils sont plutôt produits en convertissant des fichiers 3DS, DXF ou LightWave.
Ces conversions permettent d'obtenir des fichiers au format PoV qui contiennent généralement une liste de triangles, comme le montre la figure 6.2.
Pour de tels fichiers, l'optimisation faite avec les boîtes englobantes imbriquées est totalement inefficace. En effet, pour chaque rayon lancé, les tests d'intersection sont faits systématiquement avec les boîtes englobantes de tous les triangles de la scène.
Il est clair que passer en revue tous les objets de la scène à chaque lancer de rayon n'est pas du tout raisonnable, mais ce problème est dû à la manière même dont PoV a été conçu.
Si cette méthode permet d'assurer que toutes les zones des objets seront bien atteintes par les rayons, elle ne permet pas par contre d'assurer une répartition homogène des surfels. En fait, la méthode consiste à passer trois ``couches'' de surfels sur chaque objet, d'où la création d'un nombre bien trop important de surfels.
De plus, l'expérience montre que selon l'orientation de la surface surfélisée, on voit apparaître localement des groupes de trois surfels très rapprochés.
L'arborescence est parcourue en profondeur d'abord. Lorsqu'on atteint une feuille, on est sur un objet atomique. Si ce n'est pas un triangle, on l'ignore. Sinon on définit un nouveau repère (à deux dimensions) dont l'origine est placée sur le barycentre du triangle et dont les vecteurs sont dans le plan du triangle.
Ainsi, par changement de base on peut déterminer les coordonnées 2D des trois sommets du triangle. Une fois ce calcul effectué, on obtient le rectangle englobant du triangle. Il suffit alors de lancer des rayons passant perpendiculairement dans ce rectangle sur le triangle en cours de surfélisation (et surtout pas sur l'ensemble de la scène).
| entrée | : | - |
| sortie | : | - |
| descriptif | : | Initialisation du parcours en profondeur. |
| entrée | : | - |
| sortie | : | OBJECT * (éventuellement NULL) |
| descriptif | : | Récupération de l'objet suivant (parcours en profondeur). |
| entrée | : | OBJECT * ( NULL) |
| sortie | : | bool |
| descriptif | : | Teste si l'objet donné est un triangle. |
Pour chaque triangle 
défini par les sommets 
, 
et 
, les opérations
suivantes sont effectuées:
, le barycentre de .
, le vecteur normal de .
et 
, les vecteurs de base du plan du triangle.
est déterminé par deux points du plan (nous avons choisi
et car PoV intervertit parfois les sommets et lors du
chargement des scènes pour des raisons d'optimisation).
est déterminé par produit vectoriel de avec .
, et dans
le repère
.
et 
, les limites du rectangle englobant 
.
sur en respectant l'espacement
spécifié dans les paramètres passés en ligne de commande.
C'est un problème difficile à résoudre qui s'apparente à la celui de la répartition des surfels dans le cadre d'une scène décrite en CSG. Pour résoudre ce problème, on aurait pû utiliser la méthode suivante:
C'est le principe de l'algorithme que nous avons initialement imaginé, mais il apparaissait d'emblée compliqué à spécifier en détail à cause d'un problème en particulier: celui du marquage des surfaces déjà surfélisées afin d'éviter le retour par récursivité dans des régions déjà étudiées de l'espace, sans quoi la terminaison du programme n'est pas assurée.
Et surtout cette méthode n'est pas totalement satisfaisante elle non plus car dans certains cas les surfels qu'elle génère peuvent être très mal répartis, en particulier si la surface étudiée est très irrégulière (voir figure 6.3).
Il s'avère donc que le problème de la répartition homogène des surfels est un problème difficile dans le cas général. Nous l'avons cependant résolu dans le cadre des objets modélisés uniquement à l'aide de facettes triangulaires. C'était l'essentiel car la théorie des surfels est potentiellement une alternative à la représentation polygonale classique des objets. Notre convertisseur est un outil qui doit aider à la comparaison de ces deux représentations. De ce point de vue là, il remplit parfaitement sa tâche.
Le but qui nous nous étions fixé, à savoir la réalisation d'un outil de surfelisation permettant la conversion d'un modèle géométrique en sa représentation par surfels a été pleinement atteint. La rasterisation des objets est basé sur la méthode du lancé de rayons et notamment sur le moteur de PovRay. L'échantillonnage peut être fait par prise de vues multiples si l'objet est en CSG pure, ou par rasterisation des triangles si l'objet n'est constitué que de facettes.
Bien que cette solution soit pleinement satisfaisante en ce qui concerne le genie logiciel (réutilisation de code) et les fonctionnalités et besoins exprimés par le client, il existe des limites et contraintes dans le choix de notre architecture.
Une première limite est liée à la surfelisation des objets CSG. Il apparaît que la répartition des surfels sur la surface n'est pas harmonieuse. L'aspect technique de cette mauvaise répartition est expliquée dans la section , mais nous pouvons tenter de donner une solution à partir des différentes lectures [2] et [6]. Cette solution est appelée le ``collecteur de surfels''. Pour cela, on stocke le résultat de la surfelisation dans une grille 3D (donc une matrice) contenant l'objet, si il arrive que deux point-échantillons tombent dans la même cellule lors de la surfelisation, le ``collecteur de surfels'' gère cette collision et peut génèrer un surfel médian. La solution exacte est un peu plus complexe puisque les surfels n'existent que sur la surface des objets, la matrice étant alors extrêment creuse l'utilisation de techniques de représentation permettant de minimiser le gaspillage de mémoire devient nécessaire, et le collecteur joue alors le rôle de quantificateur.
Un autre point faible de notre tavail est l'utilisation d'un algorithme purement logiciel de rasterisation des objets. Dans [2] une technique utilisant au maximum le hardware est proposée. Son principe est basé sur l'utilisation d'un Z-buffer matériel pour obtenir les informations dont on a besoin. En couplant l'utilisation du Z-Buffer matériel avec la projection orthogonal OpenGL et l'association de couleurs, on peut obtenir successivement le material buffer, le depth buffer et enfin l'orientation buffer donnant respectivement la couleur, la position et l'orientation nécessaire pour modéliser un surfel.
Enfin, nous avons choisi de nous concentrer exclusivement sur PovRay pour réaliser la conversion. Nous aurions pu également traiter le cas des descriptions purement polygonales des modeleurs commerciaux. Mais il aurait fallu gérer plusieurs grammaires n'ayant pas forcément les même spécifications et dont les formats ne sont pas publiques. Il s'agit là d'un travail de conversion de format, distinct du notre et qui fait d'ailleurs l'objet d'un autre projet de cette année.
Le client ne souhaitait pas de format de sortie particulièrement évolué, le fichier contenant le résultat de la surfelisation est un simple fichier texte avec trois lignes par surfel. La première indiquant la position du surfel, la seconde indiquant l'orientation du surfel et enfin la dernière indiquant la couleur du surfel.
Afin de minimiser la taille du fichier sur le disque, il serait interressant de mettre au point un système de stockage binaire qui serait en correllation avec le niveau d'échantillonnage choisi par l'utilisateur. Il y aurait alors plusieurs niveau de stockage.
Basse qualité :
Soit au total 48 bits.
Haute qualité :
Soit au total 64 bits.
La surfelisation est une technique récente qui n'est pas encore couramment utilisée. Elle pourrait par exemple être utilisée pour l'imagerie médicale, la CAO, et d'autres applications où il est nécessaire de visualiser des objets, de les analyser, ou même de les manipuler.
Elle présente un grand intérêt pour les applications en temps réel. Si les surfels sont hiérarchisés, cela permettrait de régler le ``niveau de détails'', c'est-à-dire de sélectionner des surfels en assurant un compromis: on en choisit suffisamment pour une bonne qualité de l'image, mais pas trop car le temps de calcul doit rester raisonnable.
Il ne faut pas considérer les surfels comme une solution visant à remplacer les représentations polygonales. On peut imaginer une structure hiérarchique mixte mélangeant polygones et surfels. Il faut pour cela avoir un système de remplissage des trous utilisant le hardware des cartes graphiques actuelles (voir [2]).
L'organisation du groupe est sans aucun doute une des parties essentielles du bon déroulement d'un projet. Nous présentons ici la hiérarchie de groupe et les méthode de travail que nous avons utilisées.
Le groupe est donc constitué de cinq étudiants en informatique de l'ENSEIRB. Nous avons décidé de ne pas attribuer dès le départ des rôles prédéfinis dans la mesure ou nous n'avions aucune réelle expérience quand à la gestion d'un projet d'une durée supérieure à trois semaines. Les rôles se sont définis d'eux même au fur et à mesure du développement du programme, et, bien que n'ayant pas suivi les préceptes de M. SHERMAN distillés sur LearningSpace, deux sous-équipes se sont implicitement formées : rhino et tigre/éléphant. Cela étant dit, globalement chacun a contribué aux différentes phases du projet à savoir : la rédaction des documents, la veille technologique, la définition de l'architecture, la mise en place des normes et conventions, l'intégration des tests, etc ...
A titre d'information, nous donnons ici un tableau récapitulatif de la répartition des tâches au sein du groupe. Il faut préciser que la faible modularité du projet et l'interdépendance des composants le constituant ne nous ont pas permis d'assurer à chacun une charge de travail équitable en terme de temps (mais pas nécessairement en terme d'importance). La liste suivante donne donc la répartition nominative, mais pas forcément exhaustive, des tâches.
| Bruno FISCHEL | Analyse de l'API de PovRay, réalisation des |
|---|---|
| diagrammes et modèles de la documentation | |
| Carine NGUYEN | Analyse de l'API de PovRay, |
| Correction des différents documents. | |
| Vincent THOREL | Analyse de l'API de PovRay, |
| réalisation des bancs de test. | |
| Pierre-Jean TURPEAU | Veille technologique, |
| réalisation de la phase de conception. | |
| Frédéric VIDIL | Implémentation des modules, |
| mise au point des bancs de test. |
M. Ireneusz TOBOR, du LaBRI, travaille en ce moment sur une thèse liée de très près au principe des surfels et notamment sur des algorithmes et techniques pour le remplissage des trous. Notre outil lui permettra de compléter sa collection d'objets surfelisés, support majeur de son travail.
Réunions internes : Elles concernent l'avancement du projet et le respect de la qualité. Ces réunions ont surtout eu lieu durant la première partie du projet lors de la définition des besoins (brain storming). A partir de la conception de l'architecture, elles ont fait place à de nombreuses réunions de travail sur le terrain.
Réunions externes : Après l'attribution du sujet, de nombreuses réunions ont eu lieu avec le client I. TOBOR. Une première fois afin de nous expliquer plus précisemment le travail attendu, une seconde fois afin de décider des orientations exactes du travail en vue de la rédaction du cahier des charges puis quasiment toutes les semaines afin de lui faire part des avancées du projet.
Interne à l'équipe : Elle se réduit à l'envois de mails qui servent notamment à fixer les réunions et à valider les documents que le groupe est amené à produire.
Externe à l'équipe : Peu après l'attribution du sujet, nous avons mis en place plusieurs pages internet depuis lesquels on peu accéder aux études préliminaires de PovRay7.1, à l'ètat du code7.2, au cahier des charges7.3 et autres documents/liens provenant de la veille technologique.
Les termes techniques suivant sont récurrents au projet:
Un surfel (contraction de "surface element") est un point de l'espace produit par l'échantillonnage d'une surface.
Il possède les attributs suivants:
Conversion d'un modèle géométrique en sa représentation par surfels par un processus de rasterisation (ou échantillonnage) 3D d'un objet.
La CSG est une méthode de construction d'objets 3D par assemblage. Les 3 opérateurs de base de la CSG sont l'union, l'intersection et la différence. Chaque opérateur agit sur deux objets et produit un nouvel objet. En combinant les niveaux multiples des opérateurs de CSG, des objets complexes peuvent être produits à partir des objets primitifs simples (sphère, cube, cylindre).
Le lancé de rayon est une méthode qui permet de synthétiser des images réalistes sur un ordinateur. Les algorithmes basés sur la technique du lancer de rayons partent de la description mathématique d'une scène (cette description pouvant être faite en utilisant la CSG par exemple). Le logiciel simule mathématiquement la trajectoire prise par les rayons lumineux en tenant compte des phénomènes de réflexion, de réfraction, etc...
Afin d'illustrer le travail réalisé, nous proposons ici un exemple de surfelisation avec les deux techniques que nous avons implémenté. L'objet utilisé est un astéroïde composé de 12796 facettes.
![\includegraphics[width=.2\linewidth]{toutatis-pov.eps}](img39.png)
![\includegraphics[width=.2\linewidth]{toutatis-dot-3w.eps}](img40.png)
![\includegraphics[width=.2\linewidth]{toutatis-bold-3w.eps}](img41.png)
|
![\includegraphics[width=.2\linewidth]{toutatis-dot-tri.eps}](img42.png)
![\includegraphics[width=.2\linewidth]{toutatis-bold-tri.eps}](img43.png)
|
On remarque que dans le cas d'un objet à facettes la méthode adaptée aux triangles permet une meilleures répartition des surfels sur la surface de l'objet. La différence est remarquable visuellement lorsqu'on utilise une technique brutale de remplissage des trous (chaque surfel est rendu par un gros sprite), la qualité d'image est nettement plus fine pour un nombre de surfels généré presque trois fois moins important.
![\includegraphics[width=.7\linewidth,angle=0]{architecture-composants.eps}](img16.png)
![\includegraphics[width=.75\linewidth,angle=0]{entite-relation.eps}](img17.png)
![\includegraphics[width=.6\linewidth,angle=0]{csg.eps}](img21.png)
![\includegraphics[width=.6\linewidth,angle=0]{triangles.eps}](img22.png)
![\includegraphics[width=.6\linewidth,angle=0]{irregularites.eps}](img38.png)