The 3D Visibility Complex: a unified data-structure for global visibility of scenes of polygons and smooth objects

Frédo Durand George Drettakis 1, * Claude Puech 1
* Corresponding author
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 3DVisibility 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00510106
Contributor : Team Evasion <>
Submitted on : Tuesday, August 17, 2010 - 3:15:22 PM
Last modification on : Wednesday, April 11, 2018 - 1:51:59 AM
Long-term archiving on : Thursday, November 18, 2010 - 3:06:20 AM

Files

cccg97.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00510106, version 1

Collections

INRIA | UGA | IMAG

Citation

Frédo Durand, George Drettakis, Claude Puech. The 3D Visibility Complex: a unified data-structure for global visibility of scenes of polygons and smooth objects. 9th Canadian Conference on Computational Geometry (CCCG97), Aug 1997, Kingston, Canada. ⟨inria-00510106⟩

Share

Metrics

Record views

107

Files downloads

106