Skip to Main content Skip to Navigation
Conference papers

Filtering, Clustering and Hierarchy Construction: a New Solution for Ray Tracing Very Complex Environments

Frédéric Cazals 1, * George Drettakis 1, * Claude Puech 1
* Corresponding author
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Laboratoire d'informatique GRAphique, VIsion et Robotique de Grenoble, Inria Grenoble - Rhône-Alpes
Abstract : Data structures that handle very complex scenes (hundreds of thousands of objects) have in the past either been laboriously built by hand, or have required the determination of unintuitive parameter values by the user. It is often the case that an incorrect choice of these parameters can result in greedy memory requirements or severely degraded performance. As a remedy to this problem we propose a new data structure which is fully automatic since it does not require the user to determine any input parameters. The structure is built by first filtering the input objects by size, subsequently applying a clustering step to objects of the same size and finally building a hierarchy of uniform grids (HUG ). We then show that this data structure can be efficiently constructed. The implementation of the HUG shows that the new structure is stable since it's memory requirements grow linearly with the size of the scene, and that it presents a satisfactory compromise between memory usage and computational efficiency. A detailed comparison with previous data structures is also presented in the results.
Document type :
Conference papers
Complete list of metadata
Contributor : Team Evasion Connect in order to contact the contributor
Submitted on : Tuesday, August 17, 2010 - 3:18:37 PM
Last modification on : Monday, December 28, 2020 - 3:44:02 PM
Long-term archiving on: : Thursday, November 18, 2010 - 3:08:43 AM


Files produced by the author(s)


  • HAL Id : inria-00510127, version 1




Frédéric Cazals, George Drettakis, Claude Puech. Filtering, Clustering and Hierarchy Construction: a New Solution for Ray Tracing Very Complex Environments. Eurographics'95 (Computer Graphics Forum), 1995, Maastricht, Netherlands. ⟨inria-00510127⟩



Les métriques sont temporairement indisponibles