Statistical optimization of octree searches. (English) Zbl 1162.68737
Summary: This work emerged from the following observation: usual search procedures for octrees start from the root to retrieve the data stored at the leaves. But as the leaves are the farthest nodes to the root, why start from the root? With usual octree representations, there is no other way to access a leaf. However, hashed octrees allow direct access to any node, given its position in space and its depth in the octree. Search procedures take the position as an input, but the depth remains unknown. This work proposes to estimate the depth of an arbitrary node through a statistical optimization of the average cost of search procedures. As the highest costs of these algorithms are obtained when starting from the root, this method improves on both the memory footprint by the use of hashed octrees, and execution time through the proposed optimization.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68P05 | Data structures |
References:
| [1] | Boubekeur, Volume-Surface Trees, Computer Graphics Forum 25 (3) pp 399– (2006) |
| [2] | [BWK02] Botsch M. , Wiratanaya A. , Kobbelt L. : Efficient high quality rendering of point sampled geometry. In Eurographics Workshop on Rendering (2002), pp. 53-64. |
| [3] | Dachsbacher, SIGGRAPH pp 657– (2003) |
| [4] | Gargantini, Linear octrees for fast processing of three-dimensional objects, Computer Graphics and Image Processing 4 (20) pp 365– (1982) |
| [5] | Gumerov, Data Structures, Optimal Choice of Parameters, and Complexity Results for Generalized Multilevel Fast Multipole Methods in d Dimensions (2003) |
| [6] | Glassner, Space subdivision for fast ray tracing, Computer Graphics & Applications 4 (10) pp 15– (1984) · doi:10.1109/MCG.1984.6429331 |
| [7] | Morton, A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing (1966) |
| [8] | Samet, Applications of Spatial Data Structures (1989) |
| [9] | Schrack, Finding neighbours of equal size in linear quadtrees and octrees in constant time, Computer Vision, Graphics and Image Processing 55 (3) pp 221– (1992) · Zbl 0780.68017 |
| [10] | Stocco, Communications, Computers and Signal Processing pp 426– (1995) |
| [11] | Schaefer, Adaptive vertex clustering using octrees, Geom. Design and Computing pp 491– (2003) |
| [12] | Warren, Supercomputing pp 12– (1993) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
