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.
- · Projet Isa / Inria Lorraine
- Sylvain Lazard, CR2 Inria (géométrie algorithmique)
- Sylvain Petitjean, CR1 CNRS (vision artificielle, infographie)
- Hazel Everett, professeur univ. de Nancy 2 (géométrie algorithmique)
- Nicolas Holzschuch, CR2 Inria (infographie)
- · Projet iMAGIS / Inria Rhône-Alpes
- George Drettakis, CR1 Inria (infographie)
- · Projet Prisme / Inria Sophia Antipolis
- Olivier Devillers, CR1 Inria (géométrie algorithmique)
- Frédéric Cazals, CR2 Inria (géométrie algorithmique, infographie)
- · Équipe GéCoal / ENS Ulm
- Michel Pocchiola, maître de conférences (géométrie algorithmique)
- Xavier Goaoc, stagiaire de DEA, sous réserve (géométrie algorithmique)
- · Collaborateurs extérieurs
- Claude Puech, professeur univ. Joseph Fourier - Grenoble I (géométrie
algorithmique, infographie)
- Mark de Berg, professeur univ. d'Utrecht (géométrie algorithmique)
- Frédéric Durand, postdoc au MIT (infographie)
- Gert Vegter, professeur univ. de Groningue (géométrie algorithmique)
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