Interactive Update of Global Illumination Using A Line-Space Hierarchy

George Drettakis 1, * François X. Sillion 1
* Auteur correspondant
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Graphisme, Vision et Robotique, Inria Grenoble - Rhône-Alpes
Abstract : In this paper we describe a unified data-structure, the 3D Visibility Complex which encodes the visibility information of a 3D scene of polygons and smooth convex objects. This datastructure is a partition of the maximal free segments and is based on the characterization of the topological changes of visibility along critical line sets. We show that the size k of the complex is (n) and O(n4) and we give an output sensitive algorithm to build it in time O((n3 + k) log n). This theoretical work has already been used to define a practical data-structure, the Visibility Skeleton described in a companion paper. Interactively manipulating the geometry of complex, globally illuminated scenes has to date proven an elusive goal. Previous attempts have failed to provide interactive updates of global illumination and have not been able to offer well-adapted algorithms controlling the frame rate. The need for such interactive updates of global illumination is becoming increasingly important as the field of application of radiosity algorithms widens. To address this need, we present a novel algorithm which provides interactive update rates of global illumination for complex scenes with moving objects. In the contact of clustering for hierarchical radiosity, we introduce the idea of an implicit line-space hierarchy. This hierarchy is realized by augmenting the links between hierarchical elements (clusters or surfaces) with shafts, representing the set of lines passing through the two linked elements. We show how line-space traversal allows rapid identification of modified links, and simultaneous cleanup of subdivision no longer required after a geometry move, by identifying the modified paths in the scene hierarchy. The implementation of our new algorithm allows interactive updates of illumination after object motion for scenes containing several thousand polygons, including global illumination effects. Finally, the line-space hierarchy traversal provides a natural control mechanism allowing the regulation of the tradeoff between image quality and frame rate.
Type de document :
Communication dans un congrès
ACM SIGGRAPH 97, 1997, Los Angeles, United States. 1997
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
Contributeur : Team Evasion <>
Soumis le : jeudi 19 août 2010 - 14:23:37
Dernière modification le : jeudi 11 janvier 2018 - 06:20:04
Document(s) archivé(s) le : mardi 23 octobre 2012 - 12:32:21


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00510100, version 1




George Drettakis, François X. Sillion. Interactive Update of Global Illumination Using A Line-Space Hierarchy. ACM SIGGRAPH 97, 1997, Los Angeles, United States. 1997. 〈inria-00510100〉



Consultations de la notice


Téléchargements de fichiers