Depuis la nuit des temps l'homme a cherché à représenter ce qu'il voyait, cela démara avec les peintures sur les grottes préhistoriques, et cela se poursuit actuellement avec les images de synthèse. Actuellement l'image de synthèse révolutionne la façon de représenter les choses.
En animation, il devient possible de réaliser des univers très réalistes avec des effets de caméras très complexes à réaliser avec les techniques traditionnelles d'animation. En architecture et en conception, il est possible de se faire une idée très précise de l'éclairage d'une habitation où de la forme d'un objet avant même de l'avoir réellement fabriqué.
Toutefois l'image de synthése nécéssite de constantes mises à jour technologiques, dûes à l'avancée extrémement rapide de la recherche dans ce domaine. En effet actuellement les algorithmes classiques comme le scanline, ou le raytracing sont en perte de vitesse, voir complètement dépassés par rapport à des méthodes comme la radiosité, qui permet une illumination globale, car elle prend mieux en compte les caractéristiques physique de la lumière.
Le logiciel que nous allons réaliser est destiné à rendre des scènes 3D complexes de manière réaliste. Surtout destiné à illuminer des scènes d'intérieurs, il devrait permettre d'obtenir des images de haute qualité rapidement grâce à un support du réseau, qui permettra de distribuer les tâches efficacement entre plusieurs machines.

II ) Origine et nature du projet

1.Nature du projet

Il s'agit de realiser un programme de rendu de scenes 3d produisant des images photorealistes pouvant fonctionner sur un petit cluster
d'ordinateurs personnels.
Le rendu d'images photorealistes a longtemps ete le monopole de logiciels proprietaires a des prix exorbitans, notamment en raison du temps de calcul extrement important necessaire. La societe Pixar [1] en a fait sa specialite. La puissance de calcul des ordinateurs grands public permet aujourd'hui d'obtenir des images de tres grande qualite en des temps de calcul raisonnable. Mais il existe peu de logiciels abordables par un graphiste independant ou une petite PME pour produire ces images : a notre connaissance, il n'existe quasiment que le POV (Persistence Of Vision [2]) qui, gratuit, permet d'obtenir des images capables de concurencer des logiciels professionels a plus de 30 000 FF. Nous avons pour objectif de proposer une autre alternative, prenant en compte les nouveautes technologiques que POV, trop vieux, n'implemente que par le biais d'ajouts bricolés alors qu'elles devraient se situer a sa base pour etre reellenent efficaces.

2.Ray-Tracing

POV utilise pour effectuer son rendu, l'algorithme du Ray-tracing. Cet algorithme permet de rendre avec un realisme etonnant les refractions (par exemple lors du rendu d'un verre d'eau) et reflections (lors du rendu d'un mirroir), mais il est incapable de gerer une illumination globale, c'est a dire de prendre en compte le fait qu'un mur rouge renvoie un peu de lumiere rouge sur un sol blanc.

3.Radiosité

En reponse a ce probleme limitant tous les logiciels bases sur algorithme de ray-tracing, un nouvel algorithme a ete propose : l'algorithme de radiosité. Cet algorithme qui, lui, permet la gestion d'une illimination globale, a cependant un gros defaut : il est incapable de gerer les refractions et le reflections. Il apparait alors evident que la solution ideale serait d'utiliser la complementarite de ces deux algorithmes et de les combiner. C'est ce que nous allons essayer de faire.

4.Calcul parallele reparti sur reseau

Cependant, ces deux algorithmes etant chacuns tres couteux en temps de calcul, les utiliser tous deux amenera inevitablement a des temps de calcul extremement important. D'ou l'idee de repartir le calcul sur plusieurs ordinateurs. En effet, beaucoup de graphistes independants ou de petites PME disposent de quelques ordinateurs de la generation precedant l'actuelle, trop lents pour etre utilises par des graphistes, mais qui utilises tous ensembles peuvent representer une solution d'une puissance de calcul considerable. Dans l'enventualite ou ils ne possederaient deja aucun ordinateurs de ce type, leur achat d'occasion est negligeable compare a l'achat d'une station reprensentant la meme puissance de calcul. Notre logiciel devra donc etre capable de repartir ses calculs sur plusieurs ordinateurs, ceux-ci etant sur un reseau a bas debit (un reseau Ethernet 10 Mb), via le protocole TCP/IP.

5.Interface Graphique

Dans un soucis de facilite d'utilisation, il devra aussi etre dote d'une interface graphique, les graphistes etant rarement des adeptes de la ligne de commande. Cependant, cette interface devra etre independante du logiciel de rendu, afin de lui permettre d'etre utilise sur une machine distante via la ligne de commande.

6.Previsualisation

Toujours dans un soucis d'ergonomie, et afin d'eviter les mauvaises surprises apres plusieurs heures de calcul, notre logiciel devra etre capable d'effectuer une previsualisation rapide de la scene a rendre.

7.Format de fichier de scene 3d a rendre

Notre logiciel s'appuyera sur le format POV, celui-ci etant largement implemente par les modeleurs.

On peut donc resumer ce que doit etre capable de faire notre logiciel de rendu:
-Combiner les algorithmes de radiosite et de ray-tracing.
-Etre capable de repartir les calculs sur plusieurs ordinateurs personnels.
-Etre capable de previsulaliser rapidement la scene.
-Etre dote d'une interface graphique optionnelle.
-Etre capable d'utiliser les fichiers POV.

III ) Objet de l'etude

1.Buts et interets :

Un moteur de rendu calcule images en trois dimensions puis les affiche sur un ecran. Ce projet mettra donc en oeuvre de nombreuses technique applicables a l'ensemble des logiciels faisant appel a la 3d (jeux videos, modeleurs, visulasation scienfique...), notamment au niveau de l'organisation des donnees (nous utiliserons un octree), de la gestion des cameras, des transformation, des lumieres ... Ce projet nous permettra donc d'acquerir ou de consolider nos connaissance dans l'ecriture de logiciels 3d.
Il utilise ensuite en general l'un des deux principaux algorithmes de rendu actuellement utilises dans le rendu d'images de synthese, il nous permettra donc d'avoir une experience dans ce domaine, en nous permettant d'implementer ces algorithmes, de mener des experiences dessus , et donc de pouvoir apprecier leurs qualites et leurs complexite respective.
Ces algorithme devront s'executer en paralelle sur plusieurs ordinateurs. Ce projet nous permettra donc d'explorer les difficultes de parallelisation des algorithmes, de repartition des taches entre les differents ordinateurs.
Cette application paralelle devra s'appuyer sur une couche reseau permettant de faire communiquerle serveur et ses clients. Implementer cette couche devrait nous permettre d'avoir une experience dans l'ecriture

2.Plateforme de developpement:

Notre projet devant etre executable et compilable a l'ecole, le choix de deux plateformes de developpement s'offrait a nous. Le choix que nous avons fait n'est pas arbitraire et cela pour plusieurs raisons. Tout d'abord le systeme Unix va nous permettre de lancer des processus sur plusieurs machines sans la contrainte d'etre physiquement sur ces machines. En effet, les outils comme 'rlogin' ou 'ssh' vont nous autoriser a prendre le controle de la machine et utiliser ses ressources disponibles pour nos differents calculs.

3.Language :

Deux choix etaient possible pour la realisation de ce projet : le C et le C++.
L'avantage du C sur le C++ souvent avance est la plus forte portabilite du C par rapport au C++. La conception d'une application C est, de plus, souvent consideree comme plus simple, car ne mettant pas en jeu tous les principes de la programation orientee objet. Enfin, le C est souvent considere comme plus rapide, car plus proche du fonctionnement de la machine.
Cependant, nos experiences ont d'abord montre qu'un programme C++ ne posait pas plus de difficulte de compilation qu'un programme ecrit en C lors d'un changement de plateforme (a condition bien sur de ne pas s'aventurer sur des plateformes trop vielles). L'argument de la portabilite etait a prendre en compte il y a une dizaine d'annee, alors que les compilateurs C++ etaient a peine finalises, souvent differents, et peu matures. Aujourd'hui, le C++ s'avere donc autant portable que le C.
La programmation oriente objet que permet le C++ peut certes accroitre la complexite de conception, mais elle apporte de nombreux avantages. [....]
Quant au probleme de rapidite, nos experiences ont montres que cette perte de rapidite n'etait pas perceptibles mais que , par contre, la clarte du code objet permet un developpement et un debugging beaucoup plus rapide.
Le c++ sortant vainqueur de tous les arguments que nous avons pu lui opposer, nous l'avons donc choisi pour notre projet.

4.Algorithmes:

a)Raytracing et parallelisation

L'algorithne de raytracing consiste en une procedure recursive assez simple : pour chaque pixel de l'ecran, on lance un rayon partant de la camera et passant par ce pixel, puis on cherche le point d'intersection le plus proche entre ce rayon et l'ensemble des objets de la scene. Lors de cette intersection et en application des lois de Snell-Descartes concernant la refraction et la reflexion, un rayon refracte et un rayon reflechi, la procedure est ensuite relancee sur ces deux rayons, jusqu'a ce que l'energie du rayon considere soit negligeable. La couleur du pixel de depart resulte de la combinaison de la couleur de la texture correspondant au point d'intersection, des valeurs renvoyes par la meme procedure concernant les rayons refractes et reflechis, et de l'influences des lumieres sur ce point.
Le calcul de la couleur de chaque pixel s'avere donc independant, l'algorithme peut donc etre efficacement effectue en parallele, par exemple chaque ordinateur calculant la valeur de la couleur pour un pixel de l'ecran.
Cet algorithme gere donc les refractions et reflexions, mais ne prend pas en compte l'influence des surfaces sur les autres.
Une description complete de cet algorithme peut etre trouvee dans [17].

b)Radiosite progressive et parallelisation

L'algorithme de radiosite essaye d'approcher au maximum le modele physique de la lumiere. Dans ce modele, un mur rouge renvoie de la lumiere rouge sur toutes les autres surfaces, par exemple. L'algorithme de radiosite commence par diviser chaque surface en petits carres (evidemment, leur taille et donc leur nombre influe directement sur la vitesse de rendu et la qualite de l'image), puis calcule l'influence de chacun de ces carres (en general appeles patches) sur tous les autres. On est donc ramene a calculer les solutions d'un systeme lineaire ayant pour inconnues la nouvelle couleur de chacun des carres. Le nombre de ces patches pouvant etre enorme, nous emploieront une variante de cet algorithme, appelle "radiosite progressive". Cet algorithme commence par selectionner le patche possedant la plus grande energie, et calcule son influence sur tous les autres, puis il selectionne le deuxieme et recommence. On a donc rapidement une idee de la scene finale, et surtout on evite de stocker toutes les valeurs et de resoudre un enrme systeme lineaire.
Comme il est suggeré dans [7], nous nous demanderons a chacun des clients de calculer le "form factor" correspondant a un patche.
La radiosite propose donc une solution tres realiste, mais ne prend pas en compte les reflexions et refractions. Une description detaillee de cet la radiosite progressive peut etre trouvee dans [10]

c)Notre algorithme

Souhaitant profiter des avantages de ces deux algorithmes, nous proposons un algorithme les utilisant tous deux.
Nous commencons par appliquer l'algorithme de radiosite a toute la scene et appliquons le resultat obtenus aux textures (on combine donc le resultat de l'influence des autres patches sur le patche considere avec partie de la texture correspondant a ce patch).
Puis on applique l'algorithme de raytracing a cette scene, en tenant compte des nouvelles textures. Puisque ces textures tiennent deja compte de la lumiere (l'algorithme de radiosite les ayant deja prises en compte), cette version du raytracing ne devra pas considerer les lumieres, ce qui l'accelerera legerement.

4.Bibliotheques

a)previsualisation

Ayant choisit de developper notre projet sous unix, deux choix etaient possible pour obtenir une previsualisation rapide de la scene : ecrire une versions simplifiée du rendu, ou utiliser OpenGL. La rapidite developpement d'une application OpenGL permettant l'affichage non optimise d'objets textures, la disponibilite d'OpenGL sur la majorite des plateformes actuelles, et la possibilite d'une acceleration hardware sur certains systeme nous a pousse a choisir d'utiliser OpenGL pour effectuer la previsualisation de la scene.

b)Interface graphique:

Pour faciliter l'acces et l'administration de notre calculateur, nous avons decide de creer une interface qui fera apparaitre la previsualisation OpenGL. Le language GTK semble etre un bon choix pour ses performances et sa simplicite. C'est un langage sous licence libre

5.Format de fichier:

POV est un raytracer bien connu, qui remporta et remporte encore un succés énorme grâce à ses capacités de rendu et aux nombreuses possibilités qu'il offrait à ses utilisateur. La particularité de POV est que la seule interface qu'il propose aux utilisateurs est son format de fichiers, qui est un script où chaque point de la scéne est décrit, ce qui permet au raytracer de rendre la scéne de façon très précise. Le succés de POV peut donc aussi s'expliquer par la puissance de son language de description de scéne.
Le projet tel qu'il était considéré au départ devait utiliser le format RIB (Renderman), qui est le format le plus en vogue dans le monde de l'infographie professionnel. Il fût abandonné en raison de sa trop grande complexité par rapport au temps et aux compétence dont nous disposions.
Le format de POV perd certe un peu en puissance par rapport au format RIB, mais il gagne beaucoup en popularité et surtout en simplicité tant pour nous developpeur, que pour l'utilisateur. En outre de nombreux modeleurs sont disponible pour ce format de fichier.
Un autre point intéressant du language est qu'il posséde un language de programmation, intégré, ce qui permet de réaliser des choses assez complexes sans pour autant devoir taper des lignes et des lignes. De plus POV intégre un module de radiosité, ce qui fait qu'il existe dans le language de POV des paramétrages spécifiques à la radiosité, ce qui permettra à l'utilisateur d'avoir un meilleur contrôle sur le processus d'illuminantion globale.

6.Organisation et programmes utilisés

CVS est un logiciel d'aide au développement de logiciels. Il permet entre autre de gérer les versions et d'enregistrer l'historique du développement d'un produit. CVS permet aussi le développement de produits en équipe en gérant les accès concurrents des fichiers. En utilisant CVS, on peut enregistrer l'historique des fichiers source. Par exemple, des anomalies s'introduisent parfois lorsque le logiciel est modifié, et l'anomalie peut être détectée longtemps après d'autres modifications. Avec CVS, on peut facilement rechercher les vieilles versions pour voir les changements qui ont causé l'anomalie. Aussi, on pourrait enregistrer chaque version de chaque fichier créé. Cependant cela gaspillerai une énorme quantité d'espace disque. CVS mémorise toutes les versions dans un fichier intelligent et enregistre seulement les différences entre les versions. CVS permet de travailler aussi en groupe sur un même projet. Il est difficile de recouvrir des changements en groupe de travail à moins de faire extrêmement attention. Quelques éditeurs, comme Emacs, essayent de s'assurer que le même fichier n'est jamais modifié par deux personnes en même temps. Malheureusement, si quelqu'un utilise un autre éditeur, la sauvegarde ne fonctionnera pas. CVS résout ce problème en isolant les programmeurs. Chaque programmeur travail dans son propre répertoire, et CVS fusionne le travail.
Notre serveur CVS vient d'etre créé sur sourceforge [15] (projet : http://www.sourceforge.net/projects/zrcube/ , serveur cvs : cvs.zrcube.sourceforge.net ). Ce serveur est un des plus grand regroupement de programmeurs indépendants qui developpent des projets tres divers. Chacun peut suivre les evolutions des differentes versions du projet. Ce serveur integre plusieurs fonctionnalités telles que ftp, CVS , mailling list ... Ce sont les raisons pour lesquelles nous avons choisi de developper notre projet sur sourceforge.

Nous utiliserons autoconf et automake afin d'obtenir une gestion automatique des dependances mais surtout de permettre a notre programme d'etre configuré differemment en fonction du systeme sur lequel il est compile.
Nous avons ecrit une "charte de code" que chacun des developpeurs devra suivre afin d'obtenir une coherence dans le code source ecrit. Cette charte est disponible en annexe.
Nous utiliserons le compilateur egcs pour compiler notre projet.

2.8/License et prix de vente

Notre logiciel sera disponible sous license GPL. Un exemplaire de la license peut etre trouve sur www.gnu.org/

IV ) Decoupage du projet

Nous avons essaye de bien subdiviser le travail afin de pouvoir faire le plus de choses en meme temps, donc reduire les interdependances qui peuvent causer des problemes de conception.
Par exemple le loader POV et la couche reseau peuvent etre developpe en meme temps car l'un n'a pas besoin de l'autre.
Voici un schema simple de dependances, dans le temps.

Les fleches en pointilles represent une dependance indirecte. C'est a dire que lorsque nous allons coder les parties ray-tracing et radiosite, nous seront conscients que tout devra fonctionner en utilisant la couche reseau, donc la structure du code en tiendra compte, meme si l'integration ne sera pas faite immediatement, pour des raisons d'organisations.

Echeancier

Janvier	Groupe: Documentation intensive, developpement des classes de base et mise en place du CVS.
Fevrier	Guillaume, Henri: Developpement du loader POV et d'un previewer. J-b, Edouard: Developpement de la couche reseau.
Mars	Guillaume, Henri: Developpement du loader POV et d'un previewer. J-b, Edouard: Developpement de la couche reseau.
Avril	Guillaume, Edouard: Developpement de la partie Ray-Tracing. J-b, Henri: Developpement de la partie Radiosite.
Mai	Guillaume, Edouard: Developpement de la partie Ray-Tracing. J-b, Henri: Developpement de la partie Radiosite.
Juin	Guillaume, Henri: Integration du reseau avec chaque partie individuelle (ray-tracing, radiosite). J-b, Edouard: Combinaison du ray-tracing avec la radiosite. Edouard: Interface GTK

Nous allons commencer pendant les vacances de Noel, donc l'echeancier risque d'etre decale legerement, mais nous l'avons ecrit en reflechissant bien a la quantite de travail requise pour chaque partie, avec des marges de precaution.

Annexe

Bibliographie et Sources principales d'inspiration

[1] http://www.pixar.com

[2] http://www.povray.org

[3] Specification du format RenderMan : http://www.pixar.com/products/renderman/toolkit/Toolkit/rispec31.pdf

[4] Interactive Ray Tracing on a Virtual Shared-Memory Parallel (M.J. Keates and R.J. Hubbold) http://www.cs.man.ac.uk/aig/staff/roger/pubs/CGF-KRT.ps.Z

[5] A ray Tracing Framework for Global Illumination System (Peter Shirley, Kelvin Sung, William Brown) ftp://ftp.cs.indiana.edu/pub/shirley/gi91.ps.Z

[6] Partitionning and Parallel Radiosity (S. Merzouk, C. Winkler and J.C. Paul)ftp://ftp.loria.fr/pub/loria/isa/Merzouk/merzoukWP95.ps.gz

[7] Parallel Radiosity on a Cluster of Workstation (Libor Sindlar, Josef Pelikan) : http://sun3.ms.mff.cuni.cz/thesis/sindlar/sindlar.ps.gz

[8] Rendering Large Scenes Using Parallell Ray Tracing (Erik Reinhard and Frederik W. Jansen) : http://www.cs.utah.edu/~reinhard/papers/1996-reinhard-2.pdf

[9] A Rapid Hierachical Radiosity Algorithm (Pat Hanrahan and David Salzman) Computer Graphics (SIGGRAPH '91 Proceedings), 1991.

[10] Radiosity in English (Paul Nettle) : http://www.gamedev.net/reference/articles/article652.asp

[11] Dynamic Data Managemement For Parallel Ray Tracing (Boris Farizon and Alon Itail) http://www.cs.technion.ac.il/%7Eitai/publications/ray-tracing.ps

[12] RenderMan FAQ : http://www.landfield.com/faqs/graphics/renderman-faq/

[13] OpenGL Programming Guide, third Edition (Mason Woo, Jackie Neider, Tom Davis, Dave Shreiner), ed. Addison Wesley

[14] Images d'exemple comparant radiosite et raytracing: http://www.cg.tuwien.ac.at/research/rendering/rays-radio/

[15] Radiosity Solution: http://euklid.mi.uni-koeln.de/c/mirror/www.cs.curtin.edu.au/units/cg351-551/notes/restricted/lect13f1.html

[16] www.sourceforge.net

[17] The Basics of Raytracing : http://members.nbci.com/_XMCM/3dcoding/tom_h/raytrace.htm