Given a search radius 𝑅 (in this example set to 2), the nearest neighbor search of a 𝑐ℎ𝑢𝑛𝑘𝑖 of 𝑁
cluster representatives (green middle boxes) can be processed independently when including 2 × 𝑅 additional
representatives on the left and right side of the chunk (4 × 𝑅 total, orange and yellow boxes), which are small
parts of the end/beginning of the neighboring left/right chunk 𝑖-1 and 𝑖+1: if 𝐴 (green) determined 𝐵 (yellow) as
nearest neighbor, we need to make sure that the nearest neighbor of 𝐵 is 𝐴 as well to successfully merge them.
By Carsten Benthin, Radoslaw Drabinski, Lorenzo Tessari, and Addis Dittebrandt
Abstract
We propose a novel version of the GPU-oriented massively parallel locally-ordered clustering (PLOC) algorithm for constructing bounding volume hierarchies (BVHs). Our method focuses on removing the weaknesses of the original approach by simplifying and fusing different phases, while replacing most performance critical parts by novel and more efficient algorithms. This combination allows for outperforming the original approach by a factor of 1.9 − 2.3×.
Downloads:
PDF: PLOC++, Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction Revisited
Research Area: bounding volume hierarchy, ray tracing.
Published in High Performance Graphics 2022