Résumé : Les problèmes de visibilité sont centraux pour bien des applications en synthèse d'images. Les exemples les plus classiques sont le calcul de vue, les limites d'ombres, la visibilité mutuelle de paires de points, etc. Nous présentons tout d'abord une étude théorique des propriétés de visibilité tridimensionnelle dans l'espace des rayons lumineux. Nous regroupons les rayons qui voient le même objet, ce qui définit le complexe de visibilité 3D. Les frontières de ces groupes de rayons décrivent les événements visuels de la scène (limites d'ombres, apparition d'objets lors du déplacement d'un observateur, etc.). Nous simplifions le complexe de visibilité en un graphe de l'espace des droites que nous appelons le squelette de visibilité. Les événements visuels sont les arcs de ce graphe, et notre algorithme de construction évite le traitement complexe des ensembles 1D de droites correspondants. Nous calculons uniquement les extrémités (droites à 0 degré de liberté) de ces ensembles, et les événements visuels sont déduits topologiquement grâce à un catalogue d'adjacences. Notre implémentation montre que le squelette est plus robuste, plus général et plus efficace que les structures antérieures. Nous avons appliqué le squelette de visibilité à la simulation de l'éclairage, où il permet des calculs plus précis de manière plus rapide. Nous avons également développé un précalcul pour l'affichage de scènes très complexes. Nous calculons l'ensemble des objets potentiellement visibles depuis un volume de l'espace. Notre méthode est la première qui prend en compte l'occultation due à la conjonction de plusieurs bloqueurs dans ce contexte. Nos tests d'occultation sont effectués grâce à des projections étendues sur des plans, ce qui les rend simples, efficaces et robustes. Nous proposons enfin un vaste tour d'horizon des travaux sur la visibilité dans différents domaines.
Abstract: Visibility problems are central to many computer graphics applications. The most common examples include hidden-part removal for view computation, shadow boundaries, mutual visibility of pairs of points, etc. In this document, we first present a theoretical study of 3D visibility properties in the space of light rays. We group rays that see the same object; this defines the 3D visibility complex. The boundaries of these groups of rays correspond to the visual events of the scene (limits of shadows, disappearance of an object when the viewpoint is moved, etc.). We simplify this structure into a graph in line-space which we call the visibility skeleton. Visual events are the arcs of this graph, and our construction algorithm avoids the intricate treatment of the corresponding 1D sets of lines. We simply compute the extremities (lines with 0 degrees of freedom) of these sets, and we topologically deduce the visual events using a catalogue of adjacencies. Our implementation shows that the skeleton is more general, more efficient and more robust than previous techniques. Applied to lighting simulation, the visibility skeleton permits more accurate and more rapid simulations. We have also developed an occlusion culling preprocess for the display of very complex scenes. We compute the set of potentially visible objects with respect to a volumetric region. In this context, our method is the first which handles the cumulative occlusion due to multiple blockers. Our occlusion tests are performed in planes using extended projections, which makes them simple, efficient and robust. In the second part of the document, we present a vast survey of work related to visibility in various domains.
@PhdThesis{Fredo:99:PhD,
author = "Fr\'edo Durand",
title = "3D Visibility: analytical study and applications",
school = "Universit\'e Joseph Fourier, Grenoble I",
year = "1999",
month = "July",
note = "http://www-imagis.imag.fr"
}