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

Frédéric Cazals 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 : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00510092
Contributor : Team Evasion <>
Submitted on : Tuesday, August 17, 2010 - 3:14:41 PM
Last modification on : Wednesday, April 11, 2018 - 1:53:53 AM
Long-term archiving on : Thursday, November 18, 2010 - 3:05:19 AM

Files

SoCG97.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00510092, version 1

Collections

INRIA | UGA | IMAG

Citation

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. ⟨inria-00510092⟩

Share

Metrics

Record views

201

Files downloads

418