GPU Octrees and Optimized Search Daniel Madeira Anselmo Montenegro

Octree structures are widely used in graphic applications to accel-erate the computation of geometric proximity relations. This data strucutre is fundamental for game engine architectures for a correct scene management and culling process. With the increasing power of graphics hardware, processing tasks are progressively ported of to those architectures. However, octrees are essentially hierarchical structures, and octree searches mainly sequential processes, which is not suited for GPU implementation. On one side, several strate-gies have been proposed for GPU octree data structure, most of them use hierarchical searches. On the other side, recent works introduced optimized searches which avoid hierarchical traversals. In this work, we propose a GPU octree that allows for those opti-mized searches, which uses the GPU streaming to search for large of points at once. Moreover, we propose a parallelization of those optimized search to speed up the single point search. Finally, the proposed structure takes advantage of the recent graph-ics hardware architectures to improve the GPU octree data struc-ture