Bucket-like space partitioning data structures with applications to ray-tracing

Frédéric Cazals 1, * Claude Puech 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 : Data structures based on uniform subdivisions of the space —also known as bucketing— have the nice properties that they can be walked through very easily and can provide neighborhood relations at low cost. For data sets which are uniformly scattered in 2D or 3D space, this makes the imple- mentation of algorithms such as ray tracing, nearest neigh- bors computation or Delaunay triangulation almost trivial. But should the processed data set admit dense clusters, the spatial partitioning does not result in data partitioning so that the performances are collapsing. Although it has been known for a long time in dimension one that recursive bucket-sort admits a linear complexity for a wide range of probability densities, recursive bucket- like data structures have not received any attention in the computational geometry community. It has been observed in computer graphics that these were the fastest to ray-trace, but the question of understanding why they are not just another space partitioning data structure but rather the only data structure that succeeds in capturing the probabilistic properties of data distribution remains open. This paper is a first step in this direction and investi- gates hierarchical recursive and non recursive data struc- tures for ray-tracing. First, we show that precisely analyz- ing an optimized ray-tracer is a difficult task due to the context sensitivity of the calls costs of the functions called most often. Second, we exhibit statistics showing that if uniform grids are definitely not the right data structure to use for non-uniform distributions, recursive grids are very good at handling such distributions. Third, we present sev- eral improvements of the Hierarchy of Uniform Grids data structure, which result for the best cases in running times improved by up to a factor three with reference to the pre- viously best known solution.
Type de document :
Communication dans un congrès
13th ACM Symposium on Computational Geometry, 1997, Nice, France. 1997
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

Contributeur : Team Evasion <>
Soumis le : mardi 17 août 2010 - 15:14:41
Dernière modification le : jeudi 11 janvier 2018 - 06:20:04
Document(s) archivé(s) le : jeudi 18 novembre 2010 - 03:05:19


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


  • HAL Id : inria-00510092, version 1




Frédéric Cazals, Claude Puech. Bucket-like space partitioning data structures with applications to ray-tracing. 13th ACM Symposium on Computational Geometry, 1997, Nice, France. 1997. 〈inria-00510092〉



Consultations de la notice


Téléchargements de fichiers