Bucket-like space partitioning data structures with applications to ray-tracing
Frédéric Cazals, Claude P. Puech · 1997
Data structures baaed on uniform subdivisions of the space ---&o 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 neighbors 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 performzmces 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 rage of probability densities, recursive bucketlike 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 investigates hierarchical recursive and non recursive data structures for ray-tracing.First, we show that precisely analyzing 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 dktributions, recursive grids are very good at handling such distributions.Third, we present several 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 previously best known solution.