Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives directly or using an index which is then sorted. What if we are not allowed to change the order of the primitives? More formally:

Let $P=\{p_1, p_2, ..., p_k\}$ be an ordered set of primitives. A BVH can be constructed by splitting the set of indices $I=\{1,2,...,k\}$ into two subsets $I_l$ and $I_r$ so that $I_l\cap I_r=\emptyset$ and $I_l \cup I_r=I$. $I_l$ and $I_r$ correspond to the indices of all primitives in the left and right child node of the root node. This procedure then repeats recursively for $I_l$ and $I_r$ and so on. Now add the additional constraint that $\forall i \in I_l \forall j \in I_r(i<j)$. This prevents rearranging and makes the problem quite interesting in my opinion.

The quality of the best achievable BVH without rearranging primitives depends heavily on the initial order of the primitives. Instead of choosing a spatial split position, for example using the surface area heuristic, we are restricted to choosing a split index instead. My guess is that this would make agglomerative clustering algorithms much more attractive, as only adjacent primitives can be clustered together, not arbitrary pairs of primitives.

Has this problem been studied in the literature before?


Just some pointers:

  • I remember seeing a paper about kd-trees being executed on a GPU, which I think implied them being presorted and then moved into GPU memory. Kd-Trees are not BVHs though.

  • Also, there are bulkloaded R-Trees (R-Trees are basically BVHs), such as the STR-R-Trees (sort-tile-recurse) which pre-sort primitives, but not necessarily with memory locality in mind, but that could easily be achieved.

  • Finally, there is the PH-Tree (disclaimer: I wrote the paper about it). It stores all geometric data for each node in a single byte-stream for this node (maximum memory locality), however, the parent and children of a node are not necessarily neighbors in memory (the actual implementation, e.g. V13, uses object pooling, so many nodes are likely to be close in memory, but that is not a given, let alone scientifically evaluated. Also, the PH-Tree is not a BVH, it is more like a quadtree. Also, the PH-Tree has come a long way since the original version, it now supports rectangles/boxes (the original paper only mentions points).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.