Name
Abstract | ||
|---|---|---|
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 each level. Finally, in order to maintain kd-tree quality, we introduce novel schemes for fast evaluation of node split costs. As far as we know, ours is the first real-time kd-tree algorithm on the GPU. The kd-trees built by our algorithm are of comparable quality as those constructed by off-line CPU algorithms. In terms of speed, our algorithm is significantly faster than well-optimized single-core CPU algorithms and competitive with multi-core CPU algorithms. Our algorithm provides a general way for handling dynamic scenes on the GPU. We demonstrate the potential of our algorithm in applications involving dynamic scenes, including GPU ray tracing, interactive photon mapping, and point cloud modeling. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1457515.1409079 | ACM Trans. Graph. |
Keywords | Field | DocType |
kd-tree quality,previous parallel kd-tree algorithm,off-line cpu algorithm,comparable quality,real-time kd-tree algorithm,programable graphics hardware,real-time kd-tree construction,gpu ray,photon mapping,kd-tree,point cloud modeling,dynamic scene,cpu algorithm,ray tracing,kd-tree construction,multi-core cpu algorithm,graphics hardware,real time,kd tree,point cloud,breadth first search | Graphics hardware,Computer graphics (images),Computer science,CUDA,k-d tree,Parallel computing,Geometric primitive,Rendering (computer graphics),Photon mapping,Point cloud,Computation | Journal |
Volume | Issue | Citations |
27 | 5 | 208 |
PageRank | References | Authors |
9.54 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kun Zhou | 1 | 3690 | 159.79 |
| Qiming Hou | 2 | 529 | 23.72 |
| Rui Wang | 3 | 489 | 33.21 |
| Baining Guo | 4 | 3970 | 194.91 |