Lancer de Faisceaux en Synthèse d'Images

On peut affirmer, sans grand risque de se tromper, que le XXIeme siecle sera, entre autres, celui des images virtuelles. Pour s'en convaincre, il suffit de regarder a quel point notre quotidien a change ces dernieres annees. La part consacree aux images de synthese ne fait que croitre. Prenons par exemple les bulletins meteorologiques televises qui sont presentes a l'aide d'animations 3D, les films utilisant massivement des effets speciaux informatiques, les publicites, ... Bien sur, toutes les industries sont aussi tres friandes d'images de synthese. Et demain, peut-etre nous deplacerons nous dans des mondes virtuels pour faire nos achats, aller au travail ou au cinema ... Il est clair que les images de synthese sont promises a un bel avenir mais on en "demandera toujours davantage", on cherchera a etre plus rapide, plus precis et plus realiste. Ce memoire s'inscrit dans cette evolution et presente nos recherches dans ce domaine. Avant de presenter la demarche suivie, il est necessaire d'aborder deux problemes, relatifs a la synthese d'images. Ces problemes seront le fil directeur de nos travaux. Le premier probleme est celui de l'aliassage. On regroupe dans ce terme trois phenomenes visuels qui nuisent au realisme des images. Le premier, et le plus connu, est le phenomene des marches d'escalier sur les contours des objets. On peut le traiter efficacement avec un lancer de rayons et un surechantillonnage adaptatif des pixels. Le deuxieme est le phenomene des moires sur les textures, il peut etre traite en utilisant des textures filtrees a priori en fonction de differents taux de compression. Enfin, le troisieme phenomene est la disparition des petits objets et des petites ombres. C'est un probleme complexe, qu'un lancer de rayons conventionnel ne peut resoudre efficacement. En effet, il est impossible d'assurer qu'aucun objet ne se glisse entre les rayons d'epaisseur infinitesimale lances. C'est, de plus, un probleme important puisqu'il produit des effets involontaires de scintillement de petits objets dans les animations. Notons que les difficultes rencontrees avec de petits objets se retrouvent dans d'autres domaines comme l'acoustique ou les telecommunications. On cherche a calculer dans ces disciplines, avec precision, la propagation des ondes dans des environnements particuliers, par exemple un theâtre dans le cas des ondes sonores, ou une ville lors de la determination de la visibilite entre deux antennes dediee a une liaison microondes point a point. Le deuxieme probleme est le temps de calculs necessaire pour obtenir une image de synthese realiste. Un algorithme tel que le tampon de profondeur ("z-buffer"), en general câble sur les stations graphiques, permet un calcul tres rapide des images et des animations. Malheureusement, des effets tels que la refraction, la penombre et l'eclairage diffus sont difficiles a realiser, voire impossible. Ces manques laissent aux images produites un aspect synthetique et irreel. Pour produire des images plus realistes, on peut utiliser des algorithmes de lancer de rayons et de calcul de radiosite. Le premier propose un tres grand nombre d'effets speciaux comme la reflexion, la refraction, la penombre, le flou de bouge, la profondeur de champs, ..., le deuxieme cree des eclairages diffus tres realistes. Malheureusement, ces effets, augmentant le realisme sont couteux en temps de calculs. On constate en fait que realisme et rapidite de calcul sont des criteres qui ne vont pas souvent ensemble et qu'il faut la plupart du temps choisir entre les deux. Notre travail de recherche a donc consiste a trouver et developper des solutions a ces deux problemes. Une premiere solution qui resout efficacement les problemes d'aliassage et en particulier la disparition des petits objets et des petites ombres, est le remplacement des rayons d'epaisseur infinitesimale du lancer de rayons par des rayons volumiques. On parle alors de lancer de faisceaux. Cette approche n'est pas nouvelle puisque [AMAN 84] remplace les rayons par des cones, [HECK 84] les remplace par un seul faisceau volumique et [GHAZ 92] les remplace par des pyramides. Ces propositions resolvent en principe les problemes d'aliassage mais ne permettent pas toujours des effets de reflexion ou de refraction realistes et sont limitees a certains types de scenes. Une approche fondee sur [GHAZ 92] resout tous les problemes d'aliassage, permet des effets de refraction et de penombre au moins aussi realiste qu'un lancer de rayons et peut etre utilisee pour des scenes non polygonales comme les scenes "CSG". Nous proposons, entre autres, dans ce memoire l'etude detaillee de l'algorithme de [GHAZ 92] et des optimisations et extensions apportees [HASE 96][GHAZ 98]. Une autre solution, pour resoudre les problemes d'aliassage, est de calculer exactement tous les contours visibles des objets a partir d'un point de vue. On parle alors d'algorithme de calcul de visibilite exacte. Pour cela, de maniere tres schematique, on projette tous les objets sur le plan de l'ecran et on les decoupe en fonction de leurs parties visibles depuis l'oeil. Cette approche est interessante parce qu'elle permet de faire abstraction de toutes definitions d'un ecran. On peut ainsi modifier la taille de l'image sans la recalculer entierement et sans perte d'informations. Nous proposons dans ce memoire un algorithme de calcul de visibilite exacte fonde sur le modele des cartes generalisees et sur un lancer de faisceaux. Le modele des cartes simplifie les differents decoupages entre polygones et autorise une representation des contours integrant les proprietes d'adjacence entre les aretes. Les faisceaux permettent de positionner tres precisement les objets les uns par rapport aux autres et optimisent le nombre d'objets a traiter. Notre solution tient de plus compte des effets d'ombres portees, de reflexion et approche les effets de refraction. Une solution pour diminuer les temps de calcul est de diminuer le nombre d'objets a traiter. Pour cela, il existe plusieurs approches comme les volumes englobants, les subdivisions spatiales regulieres ou adaptatives, les "BSP", ... Mais toutes ces solutions ont leurs limites, en particulier lorsque l'on travaille avec des scenes decrites avec plusieurs dizaines de milliers de polygones ou lors d'animation. Nous proposons une approche qui, plutot que de chercher les objets visibles, cherche ceux qui sont caches afin de les exclure des traitements. Ces objets sont en general situes derriere d'autres objets tres imposants qui rendent une partie de la scene non visible. Nous proposons donc des solutions pour trouver ces objets imposants et pour determiner rapidement les objets qu'ils cachent. Ce memoire se decompose en cinq chapitres. Dans le 1er chapitre, nous etudions les algorithmes fondes sur des variantes du lancer de rayons et les algorithmes qui utilisent, d'une maniere ou d'une autre, des faisceaux. Pour synthetiser la presentation, nous avons classe les differentes approches en quatre categories : * les algorithmes fondes sur des ensembles de rayons lances en meme temps ; * les algorithmes utilisant exclusivement des faisceaux ; * les algorithmes hybrides utilisant a la fois des rayons et des faisceaux ; * les algorithmes utilisant ponctuellement les faisceaux pour resoudre un probleme. Le 2ieme chapitre presente les resultats de l'analyse et de l'implementation de l'algorithme de "lancer de faisceaux pyramidaux" propose par [GHAZ 92] pour des scenes polygonales. Nous verrons que les problemes d'aliassage sont resolus mais que les temps de calculs restent importants. Une extension de cet algorithme aux scenes non polygonales ("CSG") est presentee. Le chapitre 3 reprend l'algorithme de "lancer de faisceaux pyramidaux" pour ameliorer ses performances. Plusieurs points de cet algorithme sont optimises pour finalement ameliorer tres sensiblement les temps de calculs. Une nouvelle extension permettant des effets de penombre avec des sources lumineuses volumiques est decrite. Le chapitre 4 propose un nouvel algorithme de visibilite. Il est fonde sur les "cartes generalisees" [LIEN 89c] et sur un lancer de faisceaux. Cet algorithme permet de produire une description de tous les contours des objets, des ombres, des reflexions et des refractions sur le plan image. La construction de ces contours est facilitee par le modele topologique utilise et en particulier par les proprietes d'adjacence dont on dispose. Le dernier chapitre presente une methode permettant de diminuer le nombre d'objets a traiter dans un algorithme de visibilite. Pour cela, des faisceaux sont lances a partir du point de vue sur des polygones imposants afin de determiner les objets de la scene manifestement caches. Cette approche est exploitee dans un algorithme de calcul de la radiosite.