![\includegraphics[width=1\linewidth,angle=0]{sample.eps}](img1.png)
|
Cahier des charges
Carine NGUYEN - Bruno FISCHEL - Vincent THOREL - Pierre-Jean TURPEAU - Frédéric VIDIL
13 avril 2001
La représentation des objets 3D par maillage polygonal a ses limites. Avec les modèles actuels on arrive à des milliers de polygones, il en résulte une consommation inutile des ressources processeur dès que la taille des polygones est inférieure à un pixel. Il éxiste des travaux récents proposant d'utiliser les points au lieu des polygones pour développer une représentation des objets en 3D adaptée à un rendu efficace. Ces points, appelés surfels (surface element - section 2.6) correspondent à l'échantillonage de surface avec un taux donné. Un surfel est donc un triplet (position, orientation, couleur), et un objet est un ensemble de surfels.
L'objectif de ce projet est de réaliser un logiciel permettant de
convertir une représentation géométrique 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.
Nous avons choisi de nous concentrer sur la méthode du lancé de rayon,
bénéficiant ainsi d'outils et de technique déjà bien maîtrisés.
Ensuite, nous pourrons éventuellement nous pencher sur le problème des
polygones et l'optimisation de la convertion.
Pour nous familiariser avec les concepts nous avons tout d'abord lu la présentation de notre client [7], puis nous avons glané quelques documentations sur le réseau [6], [3], [1], [2]. Enfin, pour tout ce qui concerne l'implémentation, nous utiliserons les sources d'un ray-tracer bien connu : PovRay [4].
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, chaque semaine est organisée une réunion sur l'avancement du projet regroupant l'équipe projet et le client.
Délivrables papier :
Surfels
Dé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) 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 convertion. 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 pour effectuer tous les calculs dont nous pourrons avoir
besoin.
Notre modèle des données se rapproche donc de 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 convertion 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és dans ce logiciel. De plus, une implémentation personnel ne serait pas codable dans les temps impartis pour cette étude.
Le choix d'utiliser PovRay implique que les objets 3D
doivent être décrit à partir de primitives géométriques au format
``.pov''. C'est une contrainte forte dans la mesure ou la plupart des
objets sont définis dans bien d'autres formats tels que .dfx .3ds
.obj.
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 logicielle. Une interface
permettra donc d'effectuer des appels aux fonctionnalités
diverses du programme.
En ce qui concerne la structure du fichier, 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 type des besoins non fonctionnelles:
La première contrainte non fonctionnel serait l'étude du logiciel PovRay - ses fonctions n'étant absolument pas documentés - le risque est d'utiliser une fonction dont le calcul résultant n'est pas toujours ce à quoi nous nous attendons. 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é font ce que nous pensons qu'elles font (oui, c'est compliqué).
La seconde contrainte non fonctionnel 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, si un rayon rencontre une surface
d'une objet, on créer alors un surfel. Le problème concerne la
répartition des surfels, ils ne sont pas uniformément répartis
quel que soit l'objet. Il serait intéressant de trouver un
algorithme qui soit capable d'éliminer certain surfels (voir
d'en ajouter) afin d'obtenir une répartition des surfels plus
harmonieuse.
La dernière contrainte sera l'utilisation du projet
dans d'autre produits qui voudront mettre en place une
conversion en temps réel d'objet de polygone 
Surfels avec des contraintes de vitesse. Ici nous somme
tributaire de l'utilisation du code source de PovRay - ce qui
limitera de toute manière 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 oeuvre des
méthodes d'analyse qui permettent de simplifier les objets en
surfels pour que leurs utilisations mémoires soient
intéressantes.
Le développement du logiciel est basé sur l'API de PovRay et se fera intégralement en langage C le plus ANSI possible. 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.
Concernant la compréhension du domaine, il n'a pas de connaissance suffisante concernant la théorie sur la 3D et la représentation des objets en 3D notamment sur le calcul des intersections entre une droite et un CSG (Constructive Solid Geometry) parmit les membre du groupe pour dévelloper des algorithmes fiable dans les temps impartis - donc les connaissance nécessaire à ce projet seront axés sur les points suivants: bonne connaissance du vocabulaire 3D, capacité à analyser le code C de PovRay, bonne organisation du travail (travailler avec les sources du projets et les sources de PovRay de façon claire et réutilisable est difficile).
La longueur de ce projet sera modulé 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:
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:
La CSG (Constructive Solid Geometry) 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 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 lancer 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éflection, de réfraction, etc...
![\includegraphics[width=.60\linewidth,angle=0]{flow.eps}](img3.png)