Actions de recherche coopérative de la Direction scientifique de l'Inria
2000--2001





Visibilité tridimensionnelle :
théorie et applications




I. Activités scientifiques envisagées

Contexte

Dans plusieurs domaines de l'informatique, la notion de visibilité joue un rôle fondamental. C'est le cas notamment en infographie, en chimie algorithmique (manipulation de configurations moléculaires), en robotique (pour la planification de trajectoires de robots mobiles), en informatique temps réel (pré-calculs de la visibilité et des occultations pour un affichage rapide, par exemple dans les jeux vidéo) et en vision artificielle (reconstruction d'objets). Le domaine d'application qui nous intéresse tout particulièrement est l'infographie. Dans ce domaine, le calcul des objets visibles depuis un point donné, les calculs d'ombre ou de pénombre sont des exemples de calculs de visibilité. Dans les algorithmes de radiosité, qui permettent d'effectuer des simulations lumineuses réalistes pour des environnements complexes, il est nécessaire de déterminer si deux points de la scène sont mutuellement visibles. Les calculs de visibilité peuvent être excessivement coûteux. Ainsi, en radiosité, il n'est pas rare qu'entre 50 et 70 % de la simulation soit passé à effectuer des requêtes de visibilité.

Les requêtes de ce type sont d'une nature intrinsèquement globale, au sens où des objets spatialement éloignés peuvent avoir des interactions très complexes et peu intuitives. C'est ce qui explique que, jusqu'à récemment, les chercheurs, pour résoudre les problèmes de visibilité auxquels ils ont été confrontés, ont développé des structures ad hoc permettant de répondre à des requêtes précises mais d'une portée limitée. Ces solutions, bien qu'en général satisfaisantes, manquent d'un cadre de travail approprié, mathématiquement bien défini et qui exploite les propriétés de la visibilité 3D.

Récemment, des travaux dans la communauté de géométrie algorithmique se sont attachés à comprendre la cohérence inhérente aux espaces de droites et de rayons lumineux qui sont au coeur des questions de visibilité. Ainsi, en deux dimensions, Pocchiola et Vegter [pocchiola96b] ont introduit le complexe de visibilité, une structure globale à partir de laquelle il est possible d'effectuer une grande variété de requêtes de visibilité différentes, et ceci avec une base mathématique solide. Durand et al. [durand99a, durand97a] se sont ensuite intéressés à plusieurs extensions du complexe de visibilité en trois dimensions, en appliquant les structures développées à un contexte de radiosité. En 2D, Cho et Forsyth [cho99a] ont utilisé le même complexe pour une illumination par lancer de rayons, exploitant ainsi la cohérence entre rayons voisins qui heurtent les mêmes objets.

Le complexe de visibilité, et autres structures connexes, est également intimement lié à une représentation développée dans le domaine de la vision artificielle : le graphe d'aspect [petitjean95b, rieger96a]. Cette représentation énumère l'ensemble des ``vues'' topologiquement distinctes d'un objet. Par ailleurs, le complexe de visibilité et le graphe d'aspect ont d'importants points communs avec une représentation issue de la reconstruction par intersection de volumes : l'enveloppe visuelle [laurentini94a, petitjean98a].

Objectifs

Constatant que les mêmes problèmes de visibilité se posent dans différents domaines, les participants à cette Action de recherche coopérative souhaitent rapprocher les communautés théoriques de celles qui sont plus appliquées dans le but de synthétiser l'ensemble des connaissances acquises. L'objectif est d'analyser les différentes méthodes connues et de préciser leurs caractéristiques et similarités afin de poursuivre l'établissement d'une base mathématique commune. À noter que deux des participants à ce projet sont déjà partie prenante de l'action Géométrica, mais ont ressenti le besoin de mettre en place un groupe de travail plus spécifiquement dédié aux questions de visibilité.

Sans que cela soit limitatif, nous proposons les thèmes de recherche suivant pour cette Action de recherche coopérative.

Visibilité 3D : aspects théoriques

Les aspects théoriques de la visibilité 3D ont été peu étudiés jusqu'à présent. C'est un domaine dont les fondements théoriques et mathématiques restent encore largement à établir. C'est en particulier vrai pour la construction de structures de visibilité globales, comme le complexe de visibilité. Les travaux de Durand et al. [durand99a, durand97a] ont amené un premier ensemble de réponses pour des primitives polygonales simples, mais même dans ce cas, il reste beaucoup à faire. Le meilleur algorithme connu de construction du complexe de visibilité, sensible à la sortie, a été décrit dans [durand97b]. Peut-on améliorer sa complexité ? L'approche utilisée est-elle optimale ? Se transpose-t-elle dans le cas d'autres primitives, par exemple des primitives courbes algébriques de faible degré ? Les calculs de visibilité dans un espace à trois dimensions peuvent être pensés en termes de droites plutôt qu'en termes de points. Les faces du complexe de visibilité correspondent à des droites ayant des contacts particuliers avec les objets considérés (contacts en 2, 3 voire 4 points). Les applications qui nous intéressent ici (radiosité, problèmes liés aux contours occultants d'un objet courbe en vision, ...) peuvent également être formulées simplement en termes de droites. Ainsi, en radiosité, le facteur de forme entre deux objets, dans le cas de fonctions de base constantes, est la densité (au sens de la géométrie intégrale) des droites coupant les deux objets [pellegrini95a]. Dans la pratique, cependant, ces problèmes sont généralement abordés en termes de points. Cela tient essentiellement à la structure plus compliquée des ensembles de droites, qui ont été moins étudiés. Une meilleure compréhension des espaces de droites est sans doute un point-clé du développement de structures de visibilité 3D efficaces. Il existe quelques travaux sur ces questions (citons notamment [pellegrini97a, berg98a]), mais qui laissent de nombreuses pistes de recherche ouvertes. Il n'y a pas, par exemple, de consensus sur les paramétrages des droites à adopter. Le paramétrage ``standard'' utilise les coordonnées de Plücker (représentant une droite de R3 par un point sur une surface de degré deux de R5). Mais on peut également représenter une droite de R3 par un point de R4. Et il existe encore d'autres paramétrages, moins connus et moins utilisés. Bien qu'étant mathématiquement équivalents, ces paramétrages n'ont pas nécessairement les mêmes propriétés algorithmiques, numériques ou probabilistes. Quels sont les avantages des uns par rapport aux autres ? Dans quels contextes s'appliquent-ils ? Est-il possible de dégager une représentation unifié des différents paramétrages ? Le besoin d'``encoder'' les droites incidentes à un objet est une caractéristique commune de nombreux problèmes en vision et en infographie. Par exemple, lorsque l'on cherche à simuler la distribution de la lumière dans un intérieur complexe de bâtiment, on doit considérer l'incidence des rayons lumineux d'un mur vers les autres murs. Typiquement, une droite peut se trouver découpée en plusieurs segments (par exemple, un par pièce traversée). Jusqu'à maintenant, les chercheurs ont résolu ce problème en créant plusieurs copies d'un même espace et en ``collant'' ces copies entre elles. Ainsi, dans le cas de deux pièces séparées par une porte, on peut avoir deux espaces de droites, chacun représentant les droites ayant des segments dans chacune des pièces ; ces espaces sont ensuite ``collés'' entre eux par une région qui représente les droites qui passent par l'embrasure de la porte (voir [durand96a]). La topologie de ces espaces peut être très complexe et représenter une réelle difficulté algorithmique.

Visibilité et objets courbes

Depuis plusieurs années, le projet Isa (Inria Lorraine) collabore avec une société canadienne, SGDL (pour Solid Geometry Design Logic), qui développe un noyau de modélisation volumique aux concepts très novateurs [rotge97a]. En particulier, ce modeleur a pour particularité d'utiliser comme primitive de base des surfaces algébriques de faible degré et plus spécifiquement les quadriques et les quartiques (degré 4). Les quadriques ont un bon pouvoir descriptif et une faible complexité qui en font une alternative intéressante aux primitives traditionnellement utilisées en CAO. On estime par exemple que 85 % des pièces mécaniques peuvent être «bien« décrites par des carreaux de quadriques naturelles (plans, cônes, sphères et cylindres) [nourse80a].

Pour SGDL, disposer d'un outil de visualisation efficace de scènes composées d'un assez grand nombre de quadriques serait un atout considérable. Il permettrait de valider un certain nombre de choix faits par la société dans le développement de son produit. L'outil de visualisation employé actuellement utilise des calculs de requêtes de visibilité de type lancer de rayons. Développer des algorithmes efficaces de lancer de rayons sur des objets courbes s'avère donc d'un intérêt pratique important.

Cet axe de recherche s'appuie sur quelques travaux déjà existants, portant notamment sur les sphères. Dans le cadre de la manipulation de configurations moléculaires, Halperin et Overmars [halperin94a] ont ainsi montré comment construire efficacement la carte de visibilité d'un ensemble de sphères. Pour leur part, Mohaban et Sharir [mohaban97a] se sont intéressés au problème du lancer de rayons. Ils ont ainsi étudié des algorithmes de lancer de rayons en ligne pour un ensemble de sphères. Curieusement, les complexités rapportées sont les mêmes pour les sphères que pour des plans, ce qui peut paraître surprenant et est en tout cas un résultat à creuser.

La construction de structures de visibilité globales (type complexe de visibilité) pour des scènes quadriques est également d'un intérêt considérable en radiosité. Jusqu'à aujourd'hui, la prise en compte de primitives courbes en radiosité passait par une discrétisation de la géométrie ou par d'autres types d'approximations permettant de ramener le problème au cas classique des facettes polygonales. Toutefois, des solutions se profilent autorisant l'illumination d'objets courbes sans ces approximations, ce qui a le double avantage d'augmenter le réalisme de la simulation et d'illuminer des scènes d'une plus grande complexité géométrique. Pour que ces solutions soient réellement utilisables en pratique, il convient de développer parallèlement des algorithmes de calcul de visibilité 3D globale sur des objets courbes.

Visibilité dynamique

En synthèse d'images par illumination globale, la possibilité de rendre les calculs dynamiques est un problème récurrent. La question est la suivante : étant donné un unique objet mobile dans une scène statique, comment calculer l'illumination globale de la scène sans avoir à effectuer l'ensemble des calculs pour chacune des positions de l'objet mobile ? Le peu de travaux dans ce domaine (citons tout de même [drettakis97a, forsyth94b, orti96b, shaw97a]) atteste de la difficulté du problème. Or, pour peu que l'objet mobile soit de petite taille par rapport à la scène, les informations de visibilité changent peu entre deux positions successives de l'objet. Si la structure utilisée est une structure de visibilité globale, comment identifier les zones où une modification est nécessaire ? Comment par exemple faire une mise-à-jour incrémentale d'un complexe de visibilité quand un objet est ajouté ou retranché ? Un problème connexe est celui du maintien de la cohérence d'une ``vue'' d'une scène ou de son graphe de visibilité pour un observateur mobile. Il est intimement lié à la notion de graphe d'aspects évoquée plus haut. En géométrie algorithmique, quelques chercheurs se sont penchés sur ce problème pour le cas des sphères [follert96a, lenhof95a].

Visibilité 3D : aspects pratiques

Les difficultés d'ordre algorithmique liées à l'utilisation de structures de visibilité globale et à leur implantation font également partie des préoccupations des membres du projet. Comme cela est fréquemment le cas en géométrie, la prise en compte des cas dégénérés dans les calculs de visibilité est bien plus fastidieuse que le traitement du cas général. Or si les travaux théoriques se sont souvent intéressés à des configurations ``génériques'', les scènes rencontrées en pratique, notamment en infographie, présentent de nombreuses dégénérescences. Ces cas particuliers n'influent que localement sur la structure de visibilité utilisée mais sont un fardeau pour la robustesse du logiciel. Ainsi que l'a bien montré Durand [durand99a], le traitement cohérent des dégénérescences est un problème difficile.

En matière de visibilité 3D, l'autre goulot d'étranglement concerne le passage à l'échelle. En effet, l'implantation du complexe de visibilité 3D réalisée par F. Durand n'est en mesure que de traiter des scènes de petite taille par rapport au standard des scènes rencontrées en synthèse d'images. Le point noir est l'occupation mémoire des structures calculées. Les solutions proposées pour remédier à ce problème sont variées et représentent un champ important d'investigation future : développement d'algorithmes de construction ``paresseuse'', utilisation d'approches multi-échelles, définition de modèles de scènes ``réalistes'' (et calculs de complexité relatifs à ces modèles), etc. Plus généralement, puisque la visibilité exacte peut être difficile à calculer, il est important de se pencher sur des requêtes approchées (cf. [chrysanthou98a]) et de définir un cadre mathématique approprié à ce type de requêtes.

Programme de travail

Les participants de l'action de recherche incitative se réuniront dans le cadre de mini-ateliers de travail d'une durée de deux jours, qui auront lieu tous les deux mois, éventuellement tous les trois mois.

Nous avons également la volonté d'organiser le plus tôt possible (avant la fin de l'automne 2000) un atelier d'une semaine regroupant un petit nombre chercheurs (environ une vingtaine) en infographie, géométrie algorithmique et vision artificielle, concernés par les problèmes de visibilité 3D. L'objectif fondamental de cet atelier sera de dégager des thèmes de recherche pertinents d'un point de vue applicatif tout en offrant des perspectives de recherche intéressantes d'un point de vue théorique. Les thèmes que nous avons identifiés plus haut serviront de base de travail et de discussion.

II. Identité des participants

Ce projet d'ARC regroupe des chercheurs de trois sites Inria, du CNRS et de deux universités françaises.



Références

[cho99a]
F. Cho and D. Forsyth. Interactive ray tracing with the visibility complex. Computers and Graphics, 1999. To appear in a special issue on Visibility - Techniques and Applications.

[chrysanthou98a]
Y. Chrysanthou, D. Cohen-Or, and D. Lischinski. Fast approximate quantitative visibility for complex scenes. In Proc. of Computer Graphics International, pages 220--229, 1998.

[berg98a]
M. de Berg, H. Everett, and L. Guibas. The union of moving polygonal pseudodiscs -- combinatorial bounds and applications. Computational Geometry: Theory and Applications, 11:69--82, 1998.

[drettakis97a]
G. Drettakis and F. Sillion. Interactive update of global illumination using a line-space hierarchy. Computer Graphics Proceedings, Annual Conference Series, 31:57--64, 1997. Proceedings of Siggraph'97.

[durand99a]
F. Durand. Visibilité tridimensionnelle : étude analytique et applications. PhD thesis, Université Joseph Fourier - Grenoble I, 1999.

[durand96a]
F. Durand, G. Drettakis, and C. Puech. The 3D visibility complex: a new approach to the problems of accurate visibility. In Xavier Pueyo and Peter Schröder, editors, Proceedings of the 7th Eurographics Workshop on Rendering, Porto, Portugal, pages 245--256, 1996.

[durand97b]
F. Durand, G. Drettakis, and C. Puech. The 3D visibility complex: a unified data-structure for global visibility of scenes of polygons and smooth objects. In Proceedings of 9th Cccg (Canadian Conference on Computational Geometry), Kingston, Canada, pages 153--158, 1997.

[durand97a]
F. Durand, G. Drettakis, and C. Puech. The visibility skeleton: a powerful and efficient multi-purpose global visibility tool. Computer Graphics Proceedings, Annual Conference Series, 31:89--100, 1997. Proceedings of Siggraph'97.

[follert96a]
F. Follert. Viewing a set of spheres while moving on a linear flightpath. In Proceedings of 8th Cccg (Canadian Conference on Computational Geometry), pages 137--142, 1996.

[forsyth94b]
D. Forsyth, C. Yang, and K. Teo. Efficient radiosity in dynamic environments. In Proc. of Fifth Eurographics Workshop on Rendering, Darmstadt, Germany, pages 313--323, 1994.

[halperin94a]
D. Halperin and M. H. Overmars. Spheres, molecules, and hidden surface removal. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 113--122, 1994.

[laurentini94a]
A. Laurentini. The visual hull concept for silhouette-based image understanding. Ieee Transactions on Pattern Analysis and Machine Intelligence, 16(2):150--162, February 1994.

[lenhof95a]
H.-P. Lenhof and M. Smid. Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity. Algorithmica, 13:301--312, 1995.

[mohaban97a]
S. Mohaban and Micha Sharir. Ray shooting amidst spheres in three dimensions and related problems. SIAM J. Comput., 26:654--674, 1997.

[nourse80a]
B. Nourse, D. Hakala, R. Hillyard, and P. Malraison. Natural quadrics in mechanical design. Autofact West, 1:363--378, 1980.

[orti96b]
R. Orti, S. Rivière, F. Durand, and C. Puech. Radiosity for dynamic scenes in flatland with the visibility complex. In Proc. of Eurographics, Poitiers, 1996.

[pellegrini95a]
M. Pellegrini. Monte Carlo approximation of form factors with error bounded a priori. In Proceedings of 11th Scg (Acm Annual Symposium on Computational Geometry), Vancouver, Canada, pages 287--296, 1995.

[pellegrini97a]
M. Pellegrini. Ray shooting and lines in space. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 32, pages 599--614. CRC Press LLC, Boca Raton, FL, 1997.

[petitjean95b]
S. Petitjean. The enumerative geometry of projective algebraic surfaces and the complexity of aspect graphs. International Journal of Computer Vision, 19(3):1--27, 1996.

[petitjean98a]
S. Petitjean. A computational geometric approach to visual hulls. International Journal of Computational Geometry and Applications, 8(4):407--436, 1998. Special issue on applied computational geometry, edited by Ming Lin and Dinesh Manocha.

[pocchiola96b]
M. Pocchiola and G. Vegter. The visibility complex. International Journal of Computational Geometry and Applications, 6(3):1--30, 1996. Proceedings of 9th Scg (Acm Annual Symposium on Computational Geometry).

[rieger96a]
J.H. Rieger. On the complexity and computation of view graphs of piecewise-smooth algebraic surfaces. Philosophical Transactions of the Royal Society of London, Series A, 354(1714):1899--1940, 1996.

[rotge97a]
J.-F. Rotgé. L'arithmétique des formes : une introduction à la logique de l'espace. PhD thesis, Faculté de l'Aménagement, université de Montréal, 1997.

[shaw97a]
Erin Shaw. Hierarchical radiosity for dynamic environments. Computer Graphics Forum, 16(2):107--118, June 1997.

Ce document a été traduit de LATEX par HEVEA.



Sylvain Lazard
Last modified: Thu Mar 13 18:31:00 MET 2003