, décomposition adaptative un principe d'analyse qui prolonge les travaux antérieurs sur les optimisations par décomposition. En implantant fortement la notion d'adaptabilité nous définissons une méthode d'analyse différente aussi bien dans la manière d'analyser le contenu d'une scène que dans le choix des techniques d'optimisation à mettre en oeuwe, Conclasion ll0 Conclusion Nous avons proposé avec la méthode de Nous avons vu que la souplesse d'adaptation des algorithmes d'optimisation aux caractéristiques géométriques et optiques des objets permettait de simuler correctement des effets lumineux complexes tout en ayant une définition simple de la scène

, étude des rayons primaires et secondaires, par exemple une décomposition de type octree, nous avons préferé une decomposition qui puisse s'adapter simplement à ce que pouvait voir I'observateur. En realité, la décomposition adaptative sépare le traitement de ce qui est vu et de ce qui est éclairé. La décomposition associée aux difiërentes sources lumineuses est indépendante du point de vue, il n'est donc pas nécessaire de la recalculer, si, lors de la définition d'une animation, seul I'observateur est déplacé. Une decomposition spatiale ne permet pas une application sélective des différents t)?es de rayons. En effet on est obligé pour chacun des rayons primaires, secondaires et d'ombrage, de rechercher une intersection en effectuant la traversée de la structure. Par contre, I'utilisation des projections d'objets, Plutôt qu'une décomposition statique de I'espace

, utilisation d'une décomposition surfacique pour optimiser le calcul des rayons réfléchis ou réfractés. Cependant la méthode connaît des limiaes liees essentiellement à la geométrie des objets et au coefficient de réfraction des objets transparents. Le mixage de méthode d'optimisation a permis d'apporter une solution satisfaisante à ce problème en effectuant

, Conclusian La réalisation a permis de valider les concepts et le bilan chiffré a confirmé I

, résultats obtenus par rapport à une méthode plus conventionnelle de traitement des rayons Audelà des performances chronométriques, le point le plus important reste le faible taux de rayons calculés inutilement. C'est-àdire que nous avons été en mesure de cibler correctement les parties de I'image où se localisait I'information. L'application de I'algorithme

, de tracé de rayons ne s'est pas faite de manière aveugle, la conjonction d'une analyse "réfléchie" et adaptative de la scène ainsi que d'une application sélective d'algorithme

, Les applications futures dewont sans aucun doute integrer dans leur fonctionnalité la modularité et I'intéractivité. Nous avons partiellement incorporé ces deux notions en essayant de développer un outil souple et convivial

. La-modularité-doit, e de scène traite Il est difficilement concevable que les applications à venir ne soient pas en mesure de choisir I'algorithme le plus adapte à chaque étape de la réalisation d'une image de synthèse. Cette notion se retrouve dans la méthode de décomposition adaptative développee au LRIM. En effet, I'algorithme de visualisation choisit actuellement la méthode d'optimisation la mieux adaptee à I'objet en cours de traitement. Cette notion doit pouvoir facilement s'élargir à des

, interactivité doit permettre à I'opérateur d'agir simplement sur les paramètres de calcul de I'image par exemple le modèle d'éclairage ou le niveau de réalisme recherché. L'interface que nous avons créxie va dans ce sens en permettant à I'opérateur de choisir et de modifier de nombreux paramètres liés soit à la décomposition

, Le premier consistera à augmenter la notion d'adaptabilité. La prochaine version de SACADO integrera un modeleur hybride GSG AE-REP. Nous souhaiterions, après une analyse de la scène la plus automatique possible, que le module de visualisation choisisse les algorithmes les plus adaptes en fonction de caractéristiques fixees par l'opérateur comme les temps de réponse ou le degré de réalisme. Le second point, enfin, serait de porter la decomposition adaptative sur une machine à architecture parallèle

. Cependant-afin-d, entre processus il semble plus souhaitable que chaque proc?sseur ait une connaissance globale de la scene ou mieux une restriction du contenu à chaque sous-fenêtre. Les principes de décomposition et de propagation de faisceau semblent bien se prêter à une telle approche. lll Références b ibliogr ap h iq u es Lt2 Réferen ces bibliosraph iq ues Réfé r en ce s b ib I iog rap h i q u es Ouvrages de référence AN INTRODUCTION TO RAY TRACING par Glassner A, éditions Academie press Londres ALGORITHMES POAR L'INFOGRAPHIE par Rogers D.F. éditions Mac Graw Hill COMPWER GRAPHICS: hînciples and proctices par Foley J. Van Dam Feiner A. Hughes J. editions

L. Cfao and Y. Gardan,

L. , S. D. Image-par-peroche, B. Argence, J. Ghazanfarpour, D. Michelucci et al., editions Hermes Paris It3 Référ en c e s b ib liog ap h i q u e s 114

, Références bibliographiques

J. Amanatides, Ray tracing with cones, Compt. Graph, vol.8

A. Takaaki, Y. Mase-kenji, and . Suenaga, Pixel-selected ray tracing" IEEE Compt.Graph. & Appl. 14-22 juillet l99l [APP 68] APPEL ASome techniques for shading machine renderings of solids" AFIPS conf. proc, pp.32-3745, 1968.

, IARV, vol.87

J. Arvo and . Kirk-d, Fast ray tracing by ray classification" Compt. Graph. 2l(4) 55- 64 juilletA new algorithm of space tracing using a CSG model, pp.65-77, 1987.

, Bouatouch, Priol, Arnaldi "subdivision spatiale et modélisation CSG pour le lancé de rayon, pp.391-407, 1988.

V. Bronsvoort and J. Wijk, Two methods for improving the efficiency of ray casting in solid modelling, Computer-Aided Design, vol.16, issue.1, pp.51-55, 1984.
DOI : 10.1016/S0010-4485(84)80008-1

E. E. Catnul, A subdivision algorithm for computer display of curved surfacesA more flexible image generation environmentrr, Computer Graphics, vol.82, issue.163, p.9, 1974.

. Icle-s8l-cleary-j and G. Wyvill, Analyse of an algorithm for fast ray tracing using uniforme space subdivision" The Visual Compt, pp.65-83, 1988.

, ICOH, vol.85

M. Cohen and D. P. Greenberg, The hemi-cube : A radiosity solution for complex environement, Computer Graphics no, vol.19, p.314085, 1985.

M. Cohen, E. Chen, R. Wallace, and D. P. Greenberg, rrA progressive refinement approach to fast radiosity image generationf' Computer Graphics n, Aout, vol.22, pp.75-8488, 1988.

D. Cohen and A. Kaufinan, Yagel R. I'Discrete Ray Tracing" pages 19 à 28IEEE Computer Graphics & Applications septembre, 1992.

O. Deviller, C. Puech, and F. Sillion, Efliciency of space subdivision structure for ray tracing Rapport de recherche 88-2 laboratoire d'informatique de I'ENS 45 rue d

D. 90j-deviller and O. , The macro-région: an efficient space subdivision structure for ray tracing, Réfé r en ces b ih Ii ogroph iq u es, pp.27-39, 1990.

M. Dippe and J. Swensen, An adaptative subdivision algorithm and parallele architecture for realistic image synthesis, Compt Graph volEXC, vol.8, issue.37, pp.149-158, 1984.

T. Excoffier and E. Tosan, une méthode d'optimisation pour le tracer de rayons, pp.549-563, 1987.

, IFUJ, vol.851

K. Fujimura and T. L. Kunii, A hierarchical space indexing method" dans Kunii ed Compt. Graph.: Visual and art Poceeding of computer graphics tokyo'85 conference, pp.2-34, 1985.

A. Fujimoto, T. Tanaka, and K. Iwata, ARTS: Accelerated Ray-Tracing System, IEEE Computer Graphics and Applications, vol.6, issue.4, pp.16-26, 1986.
DOI : 10.1109/MCG.1986.276715

Y. Gardan, J. C. Paul, and R. Vivian, Amélioration du calcul des images de synthèse par une analyse de la scène

Y. Igar-9ll-gardan, Y. Lanuel, R. Vivian, and B. Gebhart, Une décomposition adaptative pour le tracé de rayons : méthode et résultats, 1961.

, IGER, vol.861

M. Gervautz, Three improvements of the ray tracing algorithm for CSG trees, Computers & Graphics, vol.10, issue.4, pp.333-339, 1986.
DOI : 10.1016/0097-8493(86)90023-3

, IGHA, vol.92

D. Ghazanfarpour, visualisation réaliste par lancer de pyramides et subdivision adaptative'r Micad, 1992.

A. S. Glassner, Space subdivision for fast ray tracing, IEEE Computer Graphics and Applications, vol.4, issue.10, pp.15-22, 1984.
DOI : 10.1109/MCG.1984.6429331

, IGRE, vol.861

D. P. Greenberg and E. A. Haines, The light buffer: a shadows testing accelerator, Compt. Graph. & Appl, vol.6, issue.9, pp.6-16, 1986.

C. Goral, K. Torrance, D. P. Greenberg, and B. Battaile, Modeling the interaction of light betwen diffuse surfaces, Computer Graphics Juillet, pp.9-12784, 1984.

P. S. Heckbert and P. Hanrahan, Beam tracing polygonat objects, Compt. Graph, vol.8, issue.3, pp.9-27, 1984.

, IFIEG, vol.87

G. Hegron, Dynamic management of 3D scenes, pp.529-542

I. 9u-jahami and G. , Pour un système de synthèse d'image souple et évolutifl'These de docteur de l'université de

F. W. Jansen, Data structures for ray tracing" dans data structure for raster graphics, proceeding workshop Eurographics seminars Springer verlag, pp.57-73, 1986.

, Réfërences b ib lîograp hiq ues UEV 891

D. Jevans and . Wryill8, 'rAdaptative voxel subdivision for ray tracing" Compt. Interface'89, pp.164-172

, IJOY, vol.86

K. I. Joy, Ray tracing parametric surface patches utilizing numerical techniques and ray coherence, pp.86279-285, 1986.

, IKAP, vol.86

M. R. Kaplan, Space tracing a constany time ray trâcer". State of the art in image Synthesis" (Siggraph '85 course note) vol I I juillet, KAJ, vol.82, p.85

J. T. Igjya, Ray tracing parametric patches, ACM computer graphics vol, vol.16

, No3 IKAY, vol.79

D. Kay and D. P. Greenberg, Transparencey for computer synthesized images Computer Graphics n" 13 vol2 pages 158-164 Août, p.79, 1979.

, IKAY, vol.86

T. Kay and T. Kajiya, Ray tracing complex scenes" Siggraph, pp.269-278, 1986.

L. T. Kunii and G. Et-wyvill, CSG and ray tracing using fonctional primitives" dans computer generated images Proceedings of graphics, pp.137-152, 1985.

I. Lanuel and Y. , Une méthode de lissage pour le tracé de rayons Laboratoire de recherche en informatique de Metz note interneGénération de séquences animées rendues par lancer de rayons

K. Nemoto, An adaptative subdivision by sliding boundary surfaces for fast ray tracing" Graphics interfaces, pp.43-48, 1986.

M. Ohta and M. Maekawa, Ray Coherence Theorem and Constant Time Ray Tracing Algorithm, Compt. Graph. (Proc of CG international, vol.87, pp.303-314, 1987.
DOI : 10.1007/978-4-431-68057-4_19

, PLIE, vol.88

C. Puech and O. Devillers, Une subdivision spatiale en deux étapes pour le tracé de rayon Rapport de recherche laboratoire d'informatique de I'ENS 45 rue d

, IROT, vol.821

S. D. Roth, Ray casting for modeling solids, Computer Graphics and Image Processing, vol.18, issue.2, pp.109-144
DOI : 10.1016/0146-664X(82)90169-1

M. Sahnoune, Contribution à I'intégration des surfaces gauches dans les modèles de solide" Thèse de I'université de Metz décembre 89

H. Samet, The quadtree and related hiérarchical data structure" Computing Surveys l6juin, pp.187-260, 1984.

, ISAM, vol.89

H. Samet, Neighbor finding in images represented by octree, CGVIP, vol.46, issue.84, pp.367-386

J. M. Sederberg and D. C. Anderson, Ray tracing for steiner patches, Compt. Graph, vol.8, issue.3, pp.159-164, 1984.

, Référen ce s b ib I i og raph iq u es Lt7 lsEw 861

, lTHr eOl lToR eOl wTV eU njrv eu fwv e3l

, lwHr sol lwHr 80l

M. A. Sweeney and R. H. Bartels, Ray Tracing Free-Form B-Spline Surfaces, IEEE Computer Graphics and Applications, vol.6, issue.2, pp.4-49
DOI : 10.1109/MCG.1986.276691

M. Shinya, . Takahashi-r, and S. Naito, Principtes and applications of pencil tracing, Compt Graph, vol.2, issue.4, pp.45-49

F. Sillion, simulation de l'éclairage pour la synthèse d'image : réalisme et interactivité, Thèse de doctorat en sciences, 1989.

J. M. Snyder and A. H. Barr, Ray tracing complex models containing surface tessellations, Siggraph, vol.87, pp.9-128

J. Thirion, P "nata structures based on binary representation for ray tracing, pp.90-53

E. Torres, rroptimisation of the binary space partition algorithme (BSp) for the sualisation of dynamic scene, pp.507-541

R. Vivian, Y. L. Gardan, U. F. De-metz, R. M. Du-saulcy-57000-metz-vivian, R. Gardan et al., Amélioration du calcul des images de synthèses par une analyse adaptative de la scène Rapport de recherche 9l(l)Décomposition adaptative: méthode et résultats, M. ile du S.aulcy 57000 Metz vivian R. Gardan Y. LanuelY. " optimisation du tracé de rayons, une approche originale et adaptative située entre le ray-tracing et le beam-tracing " MICAD 93

J. Wallace, M. Cohen, and D. P. Greenberg, A two-pass solution to the rendering equation: a synthesis of ray-tracing and radiosity methods Computer Graphics n, Juillet, pp.3-32082, 1987.

L. Ferwerda, J. Greenberg, and D. P. , Perceiving spatiat Rerationships in computer generated images, 1992.

J. E. Warnock, A hidden surface algorithm for computer generated halftone pictures" technical report UTAH university june, 1969.

K. Et-atherton and P. , Hidden surface removal using polygon area sorting" Proceeding of Siggraph, pp.7-214

H. Hooper, G. Et-greenberg, and D. P. , Improved computational methods for ray-tracing, ACM TOG, vol.3, pp.52-69, 1984.

S. Rubin, A 3-dimensional representation for fast rendering of complex scenes, Compt. Graph, vol.4, issue.3, pp.0-16
DOI : 10.1145/800250.807479

T. Witted, An improved illumination model for shaded display, Communications of the ACM, vol.23, issue.6, pp.343-349, 1980.
DOI : 10.1145/358876.358882

, Références b ib liogr a p h iq u e s IWIV 86

G. Wyvill, T. L. Kunii, and S. N. Shira, Space Division for Ray Tracing in CSG, IEEE Computer Graphics and Applications, vol.6, issue.4, pp.28-34, 1986.
DOI : 10.1109/MCG.1986.276717