With every new generation of graphics processing units (GPUs), offloading ray-tracing algorithms to GPUs becomes more feasible. Software-hardware solutions for ray-tracing focus on implementing its basic components, such as building and traversing bounding volume hierarchies (BVH). However, global illumination algorithms, such as photon mapping method, depend on another kind of acceleration structure, namely k-d trees. In this work, we adapt state-ofthe-art GPU-based BVH-building algorithm of treelet restructuring to k-d trees. By evaluating the performance of the resulting k-d tree, we show that treelet optimisation heuristic suitable for BVHs of triangles is inadequate for k-d trees of points.
Over the last three decades, physically correct rendering became a ubiquitous method
of data visualization in scientific, educational, industrial design and digital
entertainment fields [
In this paper we discuss recent advancements in acceleration structures – building algorithms used to facilitate physically-correct rendering with GPUs. We apply a method of building an acceleration structure for ray-tracing for GPUs originally used with Bounding Volume Hierarchies (BVHs) to k-d trees.
The paper is organised as follows. In the rest of the "Introduction" section we describe the necessary preliminaries, such as definitions of acceleration structures and * Publication is supported by RFBR grant № 18-08-01484. heuristics, as well as specifics of GPU programming. In the “Related Works” section we review the development of GPU-based acceleration structures construction and traversal methods over the years. In the "Methods" section, we describe the choice of the original BVH-building method and the changes that were necessary to adapt it to k-d trees. Also, we describe the choice of test scenes and experimental setup. In the "Results" section, we compare the performance of our method to state-of-the-art top-down methods for building k-d trees on CPU and to the corresponding BVH-building method. In the "Discussion" section, we analyse the problems we encountered while adapting the method and propose the directions for further research. 1.1
Photon mapping is a robust method for solving the rendering equation [
To perform the photons gathering in the third stage of the photon mapping algorithm, it is essential to organise the photons into an acceleration structure, such as the k-d tree or a Bounding Volume Hierarchy.
K-d tree. K-d tree is a binary tree that partitions the scene volume into smaller
volumes by assigning an axis-aligned split plane for one of the scene's k dimensions at
each internal node [
Bounding volumes hierarchy. Another important acceleration structure used in
rendering is the bounding volumes hierarchy (BVH) [
Top down vs bottom-up building. When building a tree-like acceleration structure, there are two primary strategies. Splitting the whole space according to some heuristic, then proceeding to apply the same heuristic to the resulting subspaces is called topdown approach. Combining the smallest elements of the set (e.g. photons or triangles) into gradually bigger units, effectively building the tree from its leaves is called bottomup approach.
Constructing K-d Tree on GPU through Treelet Restructuring 3
Top-down methods are known to produce the most effective acceleration structures
[
Over the years, several bottom-up methods were suggested by researchers. The basic
method was coined in by Lauterbach et al. in [
The next generation of bottom-up methods uses LBVH as a starting point, then
building up to optimize it by e.g. changing the internal nodes [
It is important to note that top-down methods, while producing more efficient acceleration structures, tend to be much more computationally intensive than bottom-up methods, therefore requiring choosing a trade-off between the structure’s quality and building time. This makes finding a fitting trade-off a critical part of building a realtime rendering system. 1.3
Beside the actual tree construction method, the most important thing in an
accelerationstructure-building algorithm is the heuristic that selects the splitting point. It is
important to note that the actual effectiveness of the acceleration structure is highly
scenedependent [
Surface Area Heuristic. The idea of the Surface Area Heuristic is to optimize for a general case of rays traversing the scene at random angles. At each splitting the heuristic minimizes the summary surface area of the resulting bounding volumes in any given subtree. 1.4
Modern GPUs are SIMT [
These quirks of GPU architecture result in the following rules of efficient GPU
programming [
Modern GPUs have recently received support of hardware acceleration for some
raytracing operations, such as BVH tree traversal. Unfortunately, the underlying hardware
instructions remain undocumented [
Being an "embarrassingly parallel" problem, ray-tracing is well suited to GPU architecture. However, following the rules mentioned above for such stages of a ray-tracing algorithm as building and traversal of acceleration structures is non-trivial.
Firstly, top-down methods for constructing BVHs and kd-trees are bottlenecked by
the low parallelism during the beginning of the build process. Researchers proposed
several ways to alleviate this problem, such as using trees and BVHs of higher arity or
using hybrid CPU/GPU algorithm [
Secondly, tree traversal can result in high branch divergence when, for example, a
single thread in a thread group proceeds into a deep branch of the tree when the other
threads in the same group have already terminated. The problem can be tackled both
from the side of traversal algorithm by modifying it to use "persistent threads"
technique [
Thirdly, while persistent threads method solves the problem of branch divergence, it
can result in scattered memory access. One way to solve this problem is to use prefix
scans, and regularly sort the threads based on locality [
Fourthly, GPU cache/on-chip memory proved to be too small to support stack-based
tree traversal methods, which motivated the development of stackless methods as an
alternative [
A detailed analysis of the problem can be found in [
One of the reasons ray-tracing became feasible on GPUs is the rapid development of
algorithms for building high-quality BVHs on massively parallel processors, such as
GPUs [
Constructing K-d Tree on GPU through Treelet Restructuring 5 the algorithm in Python programming language to facilitate rapid prototyping. As the Python prototype does not run on a GPU, we studied relative and hardware-independent performance metrics, such as the average number of traversed nodes and SAH cost. 3.1
The idea of TRBVH algorithm is to first build a lower-quality BVH by utilizing Morton
codes (the so-called Linear BVH) [
The LBVH is built in the following way. Coordinates of the primitives (e.g. a
photons or triangle centroids) are converted to 30-bit Morton codes. The resulting array is
sorted using Radix sort [
At the optimization stage, the algorithm starts to traverse the LBVH bottom-up,
selecting 7-nodes breadth-first subtrees (“treelets”) to optimize. For each treelet, the
algorithm compares all possible variants of organizing four of its leaves into a new
subtree, comparing the results by SAH. To avoid repeated SAH recalculations, the
algorithm employs methods of dynamic programming [
Every k-d tree can be interpreted as a BVH, but not every BVH can be interpreted as a k-d tree. BVH nodes' volumes can overlap, which is impossible for k-d tree nodes. Thus, converting the linear part of the TRBVH algorithm to produce k-d trees is straightforward because of Morton codes natively splitting the scene space into nonoverlapping volumes. However, converting the treelet optimisation part requires modifying the original SAH heuristic to avoid overlapping volumes. To achieve this, we assign ∞ heuristic cost to permutations that would result in overlapping child volumes. Also, TRBVH works with triangles, while the photon map consists of points (spheres), so we had to change the algorithm accordingly. 4.2
We tested the performance of the algorithm with Sibenik, Stanford Dragon and
Conference scenes [
Table 1 shows improvements in SAH cost and ray-tracing performance for k-d trees
built with our treelet-based method relative to k-d trees built with linear Morton codes
(LBVH). Usage of relative values allows us to compare results obtained by using our
Python-based emulation of a k-d tree GPU algorithm to the results reported by Karras
for BVHs in [
Table 1 indicates that treelet restructuring does not increase the quality of the resulting k-d tree tangibly. We can attribute this effect to the following. First, forbidding volume overlaps cuts off more than 80% of the search space. Second, SAH heuristic is known to be better suited to BVHs of triangles, not k-d trees of points. This can be clearly seen with the Conference scene: after applying treelet restructuring the SAH cost goes down for both k-d tree (our algorithm) and TRBVH. However, the traversal performance goes up only for the BVH case, while for the k-d tree it actually decreases. Thus, the direct translation of BVH-building methods to the domain of k-d trees is not feasible. This observation gives us clear direction for future research: voxelizers based on the idea of tree optimization should employ an alternative, more suitable heuristic.
Constructing K-d Tree on GPU through Treelet Restructuring 7