We present an algorithm for constructing kd-trees on GPUs. This algorithm achieves real-
time performance by exploiting the GPU's streaming architecture at all stages of kd-tree
construction. Unlike previous parallel kd-tree algorithms, our method builds tree nodes
completely in BFS (breadth-first search) order. We also develop a special strategy for large
nodes at upper tree levels so as to further exploit the fine-grained parallelism of GPUs. For
these nodes, we parallelize the computation over all geometric primitives instead of nodes at …

Described is a technology for constructing kd-trees on GPUs, in a manner that is Sufficiently
fast to achieve real-time per formance by exploiting GPU-based parallelism during the kd-
tree construction. Tree nodes are built in breadth-first search order, eg, to use a thread for
each node at each level. For large nodes at upper tree levels, computations are paral lelized
over geometric primitives (instead of nodes). To this end, large nodes are split into child
nodes by cutting offempty space based until an empty space ratio is achieved, and there …