Real-time KD-tree construction on graphics hardware

By Kun Zhou, Qiming Hou, Rui Wang, Baining Guo. ACM SIGGRAPH Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia, 2008

620 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/85dc52a012e92922b152df015191bac7ed3c11d3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

A quantitative study of irregular programs on GPUs (2012, methodology): “Many irregular GPU implementations have been published, including single-source shortest paths (SSSP) and all-pairs shortest paths algorithms [20], breadth-first search (BFS) codes [14], [20], [34], algorithms for constructing kdtrees [48], Boruvka’s minimum spanning tree algorithm [45], the MPM alg”
FAST-LIO2: Fast Direct LiDAR-Inertial Odometry (2021, methodology): “Though hardware-based methods to re-build k-d trees have been thoroughly investigated in 3D graphic applications [46]–[49], the proposed methods rely heavily on the computational sources which are usually limited on onboard computers for robotic applications.”
OptiX: a general purpose ray tracing engine (2010, methodology): “Second, a single acceleration structure build code can usually be parallelized (see e.g. [Shevtsov et al. 2007], [Zhou et al. 2008], [Lauterbach et al. 66:6 • S. Parker et al.”
GPU-based out-of-core many-lights rendering (2013, positive): “Recently, many GPU-based or GPU-friendly global illumination algorithms and systems [Zhou et al. 2008; Wang et al. 2009; Parker et al. 2010; Hachisuka et al. 2008; Kaplanyan and Dachsbacher 2013] have been presented to utilize the parallel computational power.”
PointRend: Image Segmentation As Rendering (2019, background): “Ray-tracing renderers often use oversampling [52], a technique that samples some points more densely than the output grid to avoid aliasing effects.”
Design and implementation of a parallel priority queue on many-core architectures (2012, methodology): “A number of tree-based data structures, such as R-tree [9], KDtree [10]–[12], Octree [13]–[19], decision tree [20], [21], and bounding volume hierarchy [22] have been ported to GPGPUs.”
Fast GPU-based locality sensitive hashing for k-nearest neighbor computation (2011, background): “The associative operator includes +, max, min, etc. Segmented-reduction performs reduction operation on elements with the same segmentation index [44].”