The hierarchy cut code can accelerate the ray trace speed. We compare the
performance of our reordering technique with NoSort method and Two_Point
reordering technique in Breakfast scene. The figure is rendered in 1920x1080
resolution with two shadow rays per bounce with eight samples per pixel. The
block chart of secondary ray trace speed acceleration ratio shows that our
method achieves better acceleration effect than Two_Point method. The
following three small figures show the bounding boxes used in our method from
three observation positions. Our method uses these bounding boxes, rather than
the spatial information, to encode the ray.

# Faster Ray Tracing through Hierarchy Cut Code

WeiLai Xiang10000-0002-0222-9904, FengQi Liu1, Dan Li1111$\dagger$
Corresponding author<EMAIL_ADDRESS>ZaoNan Tan1, PengZhan Xu2, MeiZhi
Liu2 and Qilong Kou2
1 School of Computer Science and Technology, Huazhong University of Science
and Technology, Wuhan, China 2 Tencent Technology (Shenzhen) Co., Ltd.
Shenzhen, China

###### Abstract

We propose a novel ray reordering technique to accelerate the ray tracing
process by encoding and sorting rays prior to traversal. Instead of spatial
coordinates, our method encodes rays according to the cuts of the hierarchical
acceleration structure, which is called the hierarchy cut code. This approach
can better adapt to the acceleration structure and obtain a more reliable
encoding result. We also propose a compression scheme to decrease the sorting
overhead by a shorter sorting key. In addition, based on the phenomenon of
boundary drift, we theoretically explain the reason why existing reordering
methods cannot achieve better performance by using longer sorting keys. The
experiment demonstrates that our method can accelerate secondary ray tracing
by up to 1.81 times, outperforming the existing methods. Such result proves
the effectiveness of hierarchy cut code, and indicate that the reordering
technique can achieve greater performance improvement, which worth further
research.

<ccs2012> <concept>
<concept_id>10010147.10010371.10010372.10010374</concept_id>
<concept_desc>Computing methodologies Ray tracing</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>

[500]Computing methodologies Ray tracing

###### keywords:

Ray Tracing, Ray Reordering, Ray Encoding

##  1 Introduction

Path tracing is an expensive rendering method that achieves global
illumination for synthesizing realistic images by recursive ray-casting. It is
keyed by three steps: computing the intersection result between the rays and
the scene, shading the ray hits, and generating new rays according to the
intersection result. As the number of reflections of rays increases, rays
might reach every corner of the scene, which is beneficial for realistic
rendering. However, due to the dispersion of rays, rays in the same parallel
unit will access completely different parts of the acceleration structure.
Even if each ray only accesses a small part of the acceleration structure, the
parallel unit still needs to access almost the whole acceleration structure in
that case. This will bring huge bandwidth consumption, resulting in the
reduction of parallel efficiency.

One solution to this problem is the ray reordering technique. Reordering
technique sorts the rays prior to the tracing process to reduce the dispersion
of rays obtained by each parallel unit during tracing. To achieve this
reordering process, rays need to be encoded as sorting key. Existing ray
encoding methods will encode the rays by their origins and directions [AK10,
CMJ15, RCP17] or origins and terminate points [MBK*10]. At present, there are
two important problems to be solved in these reordering techniques. One is
that the overhead is relatively high, especially for ray sorting. The other is
that these reordering techniques have encountered some performance bottleneck.
Their performance cannot benefit from longer encoding keys. Longer codes can
get more precise ray encoding, but cannot improve the performance. This
phenomenon has not been fully explained theoretically.

Our main contribution is to put forward the directions that can overcome the
large overhead issue and performance bottleneck. We review the relationship
between rays and acceleration structure and analyze the relationship between
ray spatial coherence and tracing efficiency. Based on this, we explain the
tehoretical reasons that limit the existing reordering technology and prove
the existence of a more efficient ray order through experiments. Finally, we
propose a novel ray encoding method called hierarchy cut code to break this
limitation. This code utilize a cut of acceleration structure to encode rays.
In this way, hierarchy cut code can avoid the boundary drift and obtain better
results. Such cut can be found by a priority queue search using hierarchically
accumulated density as priority. Comparative experiments with other methods
prove that our encoding method can perform better in most scenes. Besides, we
propose a compression scheme that can effectively reduce the overhead. Figure
Faster Ray Tracing through Hierarchy Cut Code shows the secondary ray trace
speed comparison of our reordering technique with NoSort method and Two_Point
reordering technique. It can be seen that our method achieves significant
speedup. The main contributions of this work include:

  * •

A novel encoding method based on a cut of acceleration structure to achieve
better performance than existing reordering techniques.

  * •

An explanation of performance defects to existing reordering techniques.
Especially to explain why they cannot benefit from longer sorting keys.

  * •

A compression scheme which can reduce the overhead by shortening the sorting
key.

##  2 Related Work

One major time-consuming step in path tracing is to compute the intersection
between rays and objects in the scene. Researchers have long been using
parallel computing to speed up this process. Representative works include the
packet ray trace of Gunther et al. [GPSS07] and the ray stream trace of Tsakok
[Tsa09]. However, ordinary parallel schemes will encounter the problem of low
parallel rates. To solve this problem, Aila and Laine [AL09] analyze the
bottleneck of the existing ray trace scheme and put forward three improvement
schemes: replacing the terminated rays, utilizing work queues, and designing
wide trees. Following these works, Aila and Karras [AK10] propose a fast
rendering framework by making better use of the treelet structure. Wald
[Wal11] takes the idea of terminated rays replacing strategy and comes up with
active thread compaction, which improves the GPU path tracing efficiency.
Antwerpen [Ant11] uses a similar method to speed up the Monte Carlo light
transport. The small kernel rendering framework put forward by Laine et al.
[LKA13] seem to solve the terminated ray replacement completely. This
framework splits the intersecting and shading into different kernels. This
approach minimizes the number of registers used by each core, and guarantees
that terminated ray will not occupy any thread. In this way, the maximum
number of threads can execute in parallel.

In addition to parallel computing, a hierarchical acceleration structure is
also used to speed up the tracing process. Bounding volume hierarchy (BVH) is
a frequently used structure. Goldsmith and Salmon [GS87] propose a framework
for constructing BVH structure. Later, MacDonlad and S.Booth [MB90] utilize
the surface area heuristic (SAH) to build optimized BVH. Recently Lin et al.
[LVY*20] propose the dual-split tree. This acceleration structure can reduce
the ray-plane intersection tests. However, optimizing the bounding box
partition cannot essentially solve the divergence of BVH parallel traversal.
The reason for this divergence is the fact that rays will follow the divergent
path of BVH traversal, which increases the total global memory access load.
Meister et al. [MOB*21] summarize a series of BVH methods, some methods are
working to solve this problem. A wider tree might be one solution to such
problem. Ylitie et al. [YKL17] have proved that efficient incoherent ray
traversal can be achieved by a compressed wide BVH, which be named as CWBVH.
The effectiveness of wide trees proves that reducing memory consumption of the
hierarchy is one direction to obtain higher performance. Analogously, Pharr et
al. [PKGH97] divide the scene into cells and compute the intersection between
rays and cells, thus reducing the scene switch from disk to memory when the
scene is extremely large. Navratil et al. [NFLM07] extend this idea and
propose to split both geometries and rays. Besides, Hendrich et al. [HPMB19]
propose a ray classification scheme mapping rays to interior nodes deeper in
the tree, skipping nodes in top levels. This method can reduce the number of
traversal steps.

Increasing the coherence of rays can also improve divergent traversal path
problems. Consciously generating coherent ray sets is one implementation.
Szirmay-Kalos and Purgathofer [SP99] propose the global ray bundle tracing,
and Nimier-David et al. [NVZJ19] implement coherent MCMC sampling. They both
generate highly coherent workloads to achieve fast intersect computation. A
common drawback of these methods is that they require special rendering
pipeline.

Without changing ray generation rules, it’s still possible to generate a
coherent workload. Reordering technique achieves this goal by encoding and
sorting the rays. Havran and Bittner [HB01] propose Longest Common Traversal
Sequences (LCTS) to exploit coherence in ray shooting with BSP trees. Gunther
et al. [GPSS07] force the SIMD structure to work on such workload, and Boulos
et al. [BWB08] explicitly reorder the rays into coherent ray packets. Despite
the ray reordering technique introducing extra work, Meister et al. [MBGB20]
prove that ray reordering can significantly accelerate the ray trace speed in
modern GPU architecture. Other rendering stages can also benefit from the
coherent workload. Eisenacher et al. [ENSB13] sort termination points to
improve shading performance. Moon et al. [MBK*10] sort rays using an estimated
termination point to achieve cache coherent memory access for out-of-core
rendering. Costa et al. [CMJ15] propose a ray sorting approach based on ray
direction for ambient occlusion.

Another way to take advantage of a coherent workload is the breadth-first
packet traversal. Garanzha and Loop [GL10] use this method to reduce
divergence in computation. Such breadth-first packet traversal uses a hash-
based method which is inspired by Arvo and Kirk’s 5D ray tracing [AK87].
Reshetov et al. [RSH05] propose a method that groups the rays into frusta to
reduce the total number of intersection tests. Torres et al. [TMG11] split the
BVH into a forest of disjoint subtrees based on their cut. This method can be
regarded as breadth-first packet traversal in treelet. Breadth-first packet
traversal can accelerate the primary ray and deterministic ray tracing but is
not applicable to path tracing, where the frusta will become too large and
intersect most of the scene.

##  3 Coherence in Ray Tracing

In this section, we describe a precise definition of coherence in ray tracing.
There are two kinds of coherence to be aware of: traversal path coherence and
ray spatial coherence, which will be explained in Section 3.1. The word "Path"
in the text refers to the traversal path of rays in the BVH. In Section 3.2,
we point out that existing reordering techniques suffer from encoding bias
between code boundary and node boundary. This phenomenon is called boundary
drift. We propose prefix path encoding method based on traversal paths in
Section 3.3. This method proves that the reordering technique still has great
potential for improvement.

###  3.1 Ray spatial Coherence and Traversal Path Coherence

Under the assumption that the scene only contains triangle object, the tracing
process can be regarded as computing the intersection of rays and triangles.
In most ray tracing systems, this process is accelerated by bounding volume
hierarchy (BVH). By applying this structure, rays only need to do the
intersection tests with a small set of triangles and some BVH nodes rather
than whole triangle set. The BVH nodes accessed by one ray constitute its
traversal path. Since different rays will have different traversal path, every
parallel unit (such as warp in NVIDIA GPU) needs to fetch many decentralized
nodes in one intersecting test. This will consume a lot of bandwidth. And the
parallel rate of this kind of computation will also be pretty low.

Traversal path coherence is directly related to the divergence mentioned
above, which means the way in which the traversal paths of rays overlap each
other. Rays of higher traversal path coherence have higher tracing efficiency
because less computation divergence will occur during parallel computation and
fewer nodes will be fetched in total. This concept is shown in Figure 1. The
treelike structure represents the first three layers of a BVH. Arrows of three
colors represent the BVH traversal path of three rays. Orange and blue arrows
have very similar traversal paths, which means their corresponding rays have a
high traversal path coherence. On the contrary, orange and red arrows have
very different traversal paths, which means their corresponding rays have very
low traversal path coherence.

Measurement of traversal path coherence is challenging as traversal paths
cannot be known prior to intersection test. Instead, ray spatial coherence can
be measured and used easily. This concept means that the rays are close to
each other in world space, having similar origins and directions. Rays of
similar origins and directions are more likely to intersect with the same BVH
nodes and have similar access patterns. In other words, rays of high ray
spatial coherence are likely to have high traversal path coherence. Similar
conclusions have been put forward by Moon et al. [MBK*10]. Direct comparison
of rays requires comparison of at least 6 floating point numbers, which is too
performance intensive. Ray spatial coherence is often measured by comparing
the encoded rays. Different encoding methods will result in different ray
spatial coherence measurement. Encoding method should ensure the consistency
of ray spatial coherence and traversal path coherence.

Figure 1: The BVH traversal paths for rays of high traversal path coherence
(orange and blue arrows) or low traversal path coherence (orange and red
arrows).

###  3.2 Boundary Drift in General Reordering Techniques

As we mentioned earlier, conventional reordering techniques are based on ray
spatial coherence. They encode the rays and sort them according to their
spatial coordinates to create the ray set with high ray spatial coherence.
Morton code is a frequently chosen encoding method. Every encoding method has
their code boundaries. Each point (or ray if the encoding method is encoding
the ray) in the same code boundary will have the same code under the
corresponding encoding method. For example, Figure 2 shows the code boundary
of 4 bits 2D Morton code. The dotted line is drawn to demonstrate the Z-curve.
The 4 bits 2D Morton code divides the space in a grid with sixteen cells and
the points in each cell will have the same code. For example, three orange
points in the upper right corner will all be encoded as 0101. The blue point
will be encoded as 0111 and the green point will be encoded as 1000.
Therefore, sixteen black solid grids are the code boundary of this code.

Figure 2: Code boundary for 4 bits 2D Morton code. Points in the same grid
will have the same code. For example, three orange points in the upper left
grid have the same Morton code 0101.

Boundary drift refers to the phenomenon that the code boundary is different
from the boundary of the BVH node. This will result in different intersection
results between rays of the same code and BVH nodes. As Figure 3 (a) shows,
black boundaries are morton code boundaries, and red boundaries are BVH node
boundaries. Points in the same BVH node boundary (P0 and P1) will correspond
to different codes since they fall in different code boundaries. Conversely,
points in different BVH node boundaries (P1 and P2) will correspond to the
same codes. The word "drift" comes from the intuitive view that the code
boundary is drifting from the BVH boundary in Figure 3 (a). Boundary drift
causes the ray spatial coherence measured by the encoding method to be
inconsistent with the traversal path coherence. Due to boundary drift, high
ray spatial coherence does not necessarily guarantee high traversal path
coherence. It is the primary reason why the reordering techniques failed to
achieve the best effect in some situation.

Direction encoding has a similar problem, as shown in Figure 3 (b). The red
boundaries are BVH node boundaries and the black boundaries are the code
boundaries of Spherical Coordinates code, which is a common direction encoding
method. Because the method is encoding the direction, the code boundary is no
longer a box, but a cone. Rays R1 and R2 intersect the same BVH boundary, but
R1 and R0 have the same Spherical Coordinates code.

(a) Boundary drift in Morton code

(b) Boundary drift in Spherical Coordinates code

Figure 3: Bounding drift in (a): Morton code, (b): Spherical Coordinates code.
The red boxes are BVH nodes’ boundaries, and the black boundaries are the code
boundary. The code boundaries for Morton code are boxes. The code boundaries
for Spherical Coordinates code are cones. This example shows that rays in the
same code boundary can intersect different BVH nodes, which causes boundary
drift.

In some cases, boundary drift can have a particularly significant impact. For
example, complex small objects placed in a large scene. In this case, the hit
points on that object will be encoded with a few bits, which results in
extremely serious performance degradation (even worse than not optimized).

###  3.3 Prefix Path Code

If the encoding overhead is not considered, directly encoding the full BVH
traversal path can avoid the boundary drift and obtain the best traversal path
coherence. The practical optimization value of this method is limited because
of its large overhead. Nevertheless, this method can still be used as a
reasonable upper bound of performance.

The complete traversal path is generally long, and it takes a lot of bits to
encode. In order to make this encoding method feasible, and gain a better
comparison between other encoding methods, it is necessary to limit such
encoding to a certain length. To achieve this goal, we can halt the traversal
after enough bits have been set. The proposed encoding method is called prefix
path code because it directly encodes the ray by its traversal path prefix.
Figure 4 illustrates this encoding method. Every intersect results in the
traversal path (orange arrows) are being recorded and form the prefix path
code. Each bit is set to 1 if the corresponding node intersection result is
true. Otherwise, the bit is set to 0. For example, the results of the first
four intersections of rays in Figure 4 are true, true, false and false. So its
4 bits prefix code is 1100. This prefix path code can represent the
corresponding hierarchy traversal path after forcing the rays to traverse the
BVH in the same order.

Figure 4: Example of prefix path code. Orange arrows are the traversal path.
Prefix path code will record every intersection result. One for intersected
and zero for not intersected. The corresponding prefix path code of the
example path is 1100.

Prefix path code achieves the best performance in most scenes compared with
any other reordering techniques of same bit length. This result supports our
conjecture that traversal path coherence does have a huge correlation with
tracing efficiency, and proves that there is still room for performance
improvement in the current ray reordering techniques. Removing the boundary
drift from encoding method can boost reordering techniques’ practicability.
Nevertheless, the overhead of prefix path code is almost the same as actual
intersection test. Such huge overhead makes it unsuitable for application as
an optimization scheme.

##  4 Reorder the Rays with Hierarchy Cut Code

This section proposes a novel encoding method named hierarchy cut code to
solve the boundary drift issue. Such encoding method uses a cut of BVH as the
encoding basis. A proper BVH cut divides the space into several blocks
according to BVH structure. Encoding the rays based on such division can
increase the traversal path coherence without introducing bounding drift. In
Section 4.1, we will show the hierarchy cut encoding method encodes the rays
based on BVH cut. In Section 4.2, we will describe how to determine such BVH
cut. Section 4.3 will explain the spatial meaning of this code, which is
helpful to understand how this encoding method works. In Section 4.4 we put
forward an effective hierarchy cut code enhancement method called multi-level
hierarchy cut code. This method uses two levels cut nodes, and achieves
competitive result with less encoding bits.

###  4.1 Defining Hierarchy Cut Code

Eliminating boundary drift is the primary goal of improving encoding method.
To achieve this goal without introducing a huge overhead, we choose a cut of
BVH to represent the whole BVH. Instead of encoding the rays based on their
traversal path, this method encodes the rays as their intersection results
with the chosen cut. This intersection result of cut nodes can implicitly mark
the traversal path. We name this code as hierarchy cut code (HCC). Figure 5
shows how this code relates with traversal path coherence. If one ray
intersects one cut node, it will traverse the corresponding subtree. Rays that
traverse the same subtree will have a high chance to overlapping traversal
path. The more identical the subtree sequence of two rays accesses, the more
likely they have overlapping traversal paths. Therefore, traversal path
coherence can be measured by bit difference between hierarchy cut codes. The
more two rays access the same cut nodes, the more traversal path coherence
they have.

(a) BVH cut example.

(b) Three example rays traverse this BVH.

Figure 5: Example shows how hierarchy cut code is related with traversal path
coherence. (a) An example cut (colored in orange) for a BVH. It has three cut
nodes and three corresponding subtrees. (b) Three example rays traverse this
BVH. Ray1 and Ray2 access the same cut node, so they shall traverse the same
corresponding subtree. While Ray3 does not access that cut node. Ray1 and Ray2
have more traversal path coherence than Ray1 and Ray3, because Ray1 and Ray2
have longer path overlap.

Hierarchy cut code only needs to calculate the intersection results of rays
and fixed cut nodes. The pseudo code of encoding process is described in
Algorithm 1. Unlike prefix path code, the encoding process does not traverse
the BVH. The cut nodes are shared between all the rays so that they can be
fetched into a shared memory before the ray intersection test (Line 1). This
processing avoids frequent nodes fetching. For every ray, compute their
intersection result of each cut node and record the result as hierarchy cut
code (Lines 5 and 6).

Algorithm 1 The process of hierarchy cut encoding

1:copy cut nodes from global memory into shared memory;

2:while have ray to encode do

3: Fetch $Ray$ from global ray queue;

4: for all $CutNode$ in cut nodes do

5: Compute intersection between $CutNode$ and $Ray$;

6: Set corresponding bits in HCC;

###  4.2 Determining Cut Nodes

The cut nodes are static in the whole process. One efficient way to determine
these cut nodes is breadth-first search. Figure 6 shows the searching process.
The breadth-first searching process starts with a priority queue that contains
the root of the node tree, as Figure 6 (b) shows. The searching process will
remove the queue head node and add its child nodes into the queue until it
finds enough nodes. All nodes still in the queue will be regraded as cut nodes
when the searching process is end. Generally the cut nodes will not be leaf
nodes. We expect the cut nodes to be internal nodes, so their corresponding
subtrees can represent traversal path. Only in some extremely unbalanced BVH,
a leaf node can be chosen as cut node. Figure 6 (d) shows such case. The leaf
nodes will be treated as special cases. Since these nodes cannot be divided,
they will be treated as cut nodes and no longer participate in the searching
process. This measure can make sure the searching process will not fail down
when encounter leaf nodes. The pseudo code of searching process is described
in Algorithm 2.

(a) An example BVH.

(b) Cut node search starts from root node.

(c) Breadth-first search to determine cut nodes.

(d) Special case when encount leaf node.

Figure 6: Demonstration of how to determine cut nodes. (a) This is an
unbalanced BVH. It has one leaf node in top level. (b) The search starts from
the root node of BVH. The blue node is in the search queue. (c) The search
goes in breadth-first order. Four nodes are in the search queue at this
moment, one leaf node and three top nodes. (d) Stop searching when enough cut
nodes are found. Seven cut nodes (colored in orange) are found in this case.
We treat the leaf node as cut node and no longer search this branch. Algorithm
2 Compute the cut nodes

1:Clear the $CutNodeList$;

2:Set $MaxQueueSize$ to required length;

3:Copy the root node into $PriorityQueue$;

4:while len($PriorityQueue$) < $MaxQueueSize$ do

5: Pop $Node$ from $PriorityQueue$;

6: if $Node$ is leaf then

7: Add $Node$ into $CutNodeList$;

8: $MaxQueueSize$ -= 1

9: else

10: Push the child of $Node$ into $PriorityQueue$;

11:Add all $Node$ in $PriorityQueue$ into $CutNodeList$;

The priority of nodes is a topic worth studying. To generate a uniform cut, we
measure and accumulate the density of mesh hierarchically. The measurement we
choose is to define the density of leaf nodes as the number of leaf node
triangles, and the density of non leaf nodes as the sum of the density of
their children plus it’s surface area. We named this priority function
hierarchically accumulated density (HAD). By applying this HAD, we can
automatically allocate more bits in areas with dense meshes. The following
Formula 1 shows the detailed definition of HAD. TC is the number of triangles
associated with the leaf node. SA is the surface area of node n. The
subscripts left and right represent the children of node n. The $\lambda$ is a
hyperparameter, which is used to balance the weight of internal nodes and leaf
nodes. We set it to 0.125 in experiments.

$HAD_{n}=\begin{cases}TC_{n}*SA_{n}&\mbox{n is leaf node}\\\
HAD_{left}+HAD_{right}+\lambda*SA_{n}&\mbox{n is internal node}\end{cases}$
(1)

###  4.3 Code Boundary of Hierarchy Cut Code

Although the hierarchy cut code does not seem to contain spatial information
of ray as morton code do, the intersection of rays and cut nodes can mark rays
in world space. As Figure 7 shows, sixteen grids are the cut nodes’
boundaries. When rays are encoded by hierarchy cut code, their intersection
results with these anchors are recorded as hierarchy cut code. Their
corresponding codes are: Ray1-1100010001000000, Ray2-1100010001000000,
Ray3-0000000000101110, Ray4-0001001100100110. Ray1 and Ray2 have the same
hierarchy cut code, while Ray3 and Ray4 have totally different hierarchy cut
code. The code boundary of hierarchy cut code is the combination of cut node
boundaries. For example, four colored grids in Figure 7 are the code boundary
of hierarchy cut code. Such code boundary is a frustum like area, as the blue
dotted line outlined. The code boundary is not completely a frustum, and the
outline is only used to highlight its shape. It can be seen that the outline
actually contains some areas without color, which is not in the code boundary.
Unlike the code boundary of spatial encoding methods, the code boundary of
hierarchy cut code requires rays to pass through the boundary of each cut node
that constitutes it. Rays crossing the same cut nodes will fall in the same
code boundary. When reordering the rays according to our hierarchy cut code,
we are actually collecting the rays that fall in the same code boundary, and
feed them into one trace warp. The similarity between code boundaries can be
measured by bit difference of hierarchy cut code. To create coherence
workload, rays that be are assigned to the same warp shall be fetched from the
same code boundary or several similar code boundaries.

Figure 7: Demonstration of how hierarchy cut code encodes rays’ spatial
information. The sixteen cells of the grid are the cut nodes’ boundaries. Four
rays are encoded by sixteen cut nodes. Ray1 and Ray2 are close to each other.
Ray3 and Ray4 have reverse direction and close origin. Four colored cells form
the code boundary of hierarchy cut code 1100010001000000 (outlined by blue
dotted line). Ray1 and Ray2 fall in this code boundary, so they have the same
hierarchy cut code.

One interesting part is about the ray direction. If two rays cross the same
cut nodes, they will have exactly the same hierarchy cut code. Such code
duplication seems to seriously affect tracing performance. However, the
hierarchy cut code can have good performance without ray direction explicit
encoding. Hierarchy cut code can implicitly represent ray direction in most
cases. As Ray3 and Ray4 in Figure 7 shows, if the ray’s origin is in the
scene, reversing its direction will make that ray access totally different cut
nodes. Only when two rays that have reverse start and end points on the scene
boundary, their corresponding hierarchy cut code will be duplicated. Besides,
adding direction information to the code will increase the risk of boundary
drift. Experiments on this phenomenon are included in the appendix.

The other puzzling part of hierarchy cut code is why the sorting method is
still valid. Hierarchy cut codes do not have partial order, the difference
between codes are measured by their bit difference. Sorting hierarchy cut
codes as they are decimal numbers can cause disorder, which means that the
precursor or the successor of some cut nodes have high bit difference like
1000 and 0111. The experiment shows that our encoding method is so rough that
most warps processing the rays have same hierarchy cut code. If the rays in
the warp have the same code, the order of code does not matter. Because it is
the traversal path coherence inside the warps that ultimately affects the
tracing efficiency.

###  4.4 Multi-Level Hierarchy Cut Code

One drawback for our hierarchy cut code is the insufficient space division.
The 32-bit hierarchy cut code have 32 cut nodes, which means it divides the
space into 32 blocks in total. On the other hand, ordinary encoding methods
with 32 bits (16 bits for origin and 16 bits for direction) can have 32*32*64
blocks. In order to divide the space into finer blocks, multi-level hierarchy
cut code utilize multi-level cut nodes. For example, multi-level cut nodes
with two-level structure uses two level cut nodes: top level and low level.
Top level cut nodes divide the BVH, and low level cut nodes divide the subtree
of corresponding top level cut node. When encoding a given ray, we record the
intersection results of that ray with all top level cut nodes. Then we select
one top level cut node as representative top level cut node, and record the
intersection results of corresponding low level cut nodes of the
representative top level cut node. In this way, we can divide the space with
finer granularity by utlizing more low level cut nodes than bit length. Figure
8 shows that this encoding method can form a finer space division.

Figure 8: Demonstration of how multi-level hierarchy cut code encodes rays.
Ray1 intersects four top level cut nodes (orange cells). Select top level cut
node 3 as the representative top level cut node, Ray1 intersects four
corresponding low level cut nodes (blue grids). So Ray1 can be encoded as
0101110001101100. The first 8 bits are the intersection results with top level
cut nodes, and the last 8 bits are the intersection results with corresponding
low level cut nodes. In this way, we can have at most 64 low level cut nodes
with 16 bits, which means the space is divided into finer blocks than using 16
bits hierarchy cut code.

To apply multi-level hierarchy cut code with two-level structure, there are
two problems to be solved: generating two levels cut nodes, and determining
representative top level cut node. The two level cut nodes generation uses the
similar breadth-first searching method (Algorithm 3). We will abandon the top
level node that does not have enough subtree when generating two level cut
nodes, as shown in line 6 of Algorithm 3. This measure can avoid empty low
level node. We apply the searching process to BVH and every subtrees of top
level cut nodes to generate cut nodes. Representative top level cut node is
determined by the intersection results of that ray with all top level cut
nodes. We select the top level cut node with the highest HAD value to be the
representative top level cut node. In practice, we can sort the top level cut
nodes according to their HAD values before send them into the GPU memory.
After that, the representative top level cut node is simply the first
intersected top level cut node. This method can minimize the extra overhead in
the encoding process.

Algorithm 3 Compute the cut nodes for multi-level hierarchy cut code

1:Clear the $CutNodeList$;

2:Set $MaxQueueSize$ to required length;

3:Copy the root node into $PriorityQueue$;

4:while len($PriorityQueue$) < $MaxQueueSize$ do

5: Pop $Node$ from $PriorityQueue$;

6: if $Node$ has lagre enough subtree then

7: Push the child of $Node$ into $PriorityQueue$;

8:Add all $Node$ in $PriorityQueue$ into $CutNodeList$;

Figure 9: The overview of sorting key occupied by chosen encoding methods. The
figure shows bits of a 32-bit key occupied by encoding origin (o),
direction(d), estimated termination point(t), or the codes introduced earlier.

Multi-level hierarchy cut code is essentially a compression scheme rather than
an improved method. For example, the 16 bits multi-level hierarchy cut code in
Figure 8 can be considered as a compression form of 64 bits hierarchy cut
code. Two reasons make this multi-level hierarchy cut encoding method do not
perform as well as expected when the encoding length is sufficient. First
reason is that the premature discard of other top level cut nodes’ information
will also make multi-level hierarchy cut code bear huge risks. If the
representative top level cut node we choose is not good enough, the
performance of multi-level hierarchy cut code will also decline sharply. This
is also the reason why we do not design Multi-level hierarchy cut code with
more levels. Other reason is that finer code boundary can increase the
encoding accuracy, but it does not always improve the tracing performance. In
Section 6.6, we will further explain why simply increasing the encoding
accuracy (e.g. using longer sort keys) cannot always improve the tracing
efficiency.

##  5 Implementation

To compare the performance of our technology with existing methods, we select
four representative methods: Origin, Reis, Aila_Compact, and Two_Point. These
methods have been introduced by Meister et al. [MBGB20]. The Two_Point method
method has several ways to estimate the termination points. We choose the
fixed-length estimation method, which set the ray length to 0.25 of the
largest extent of the scene bounding box. Other termination points estimation
methods depend on the records from last frame, so they are not suitable for
comparison. These methods will be compared with 3 proposed methods: hierarchy
cut code (HCC), multi-level hierarchy cut code (MLHCC) and prefix path code
(PPC). Besides, we design a regular grid encoding to compare with the
hierarchy cut code. The difference between hierarchy cut code and regular grid
encoding is that the BVH cut is replaced by the grids which divide the space
evenly. By comparing the performance of this two encoding methods, we can
emphasize the effect of avoiding boundary drift. An overview of all
aforementioned ray encoding methods is shown in Figure 9.

Figure 10: Overall render pipeline diagram.

(a) Breakfast scene.

(b) Cut node boundaries in Breakfast scene.

(c) Salle de Bain scene.

(d) Cut node boundaries in Salle de Bain scene.

(e) Livingroom scene.

(f) Cut node boundaries in Livingroom scene.

(g) Sibenik scene.

(h) Cut node boundaries in Sibenik scene.

(i) Vokselia scene.

(j) Cut node boundaries in Vokselia scene.

Figure 11: Cut node boundaries (orange wireframe boxes) of hierarchy cut code
in five scenes.

We implement our ray reordering technique in CUDA C. The path tracer uses next
event estimation with two shadow rays per bounce with eight samples per pixel.
The overall pipeline is shown in Figure 10, which follows the small kernel
framework proposed by Laine et al. [LKA13]. We add a key compute kernel and a
ray sort kernel before the trace kernel to implement ray reordering technique.
The ray sorting kernel is achieved by the Thrust library, which only sorts the
index of rays. The trace kernel will fetch the rays according to these
indices.

##  6 Results

Table 1: Light source setting table. | Light Index | Relative Radius
---|---|---
Breakfast | 0 | 8.30%
| 1-2 | 1.60%
Salle de Bain | 0 | 1.10%
Livingroom | 0 | 5%
Sibenik | 0 | 7.50%
| 1-2 | 2.50%
| 3-12 | 0.50%
Vokselia | 0 | 12%

The performance is evaluated in five scenes of various complexity. Thanks to
McGuire [McG17] and Bitterli [Bit16] for providing the necessary models. Their
light sources only include sky light and spherical light sources. The number
and the relative radius are shown in Table 1. The first column of the table
represents the index of the corresponding light source in the scene, and the
second column represents the relative radius of that light source, which is
the radius percentage in terms of the largest extent of scene. Some scenes in
the table use sphere light sources of different radii. For example, Breakfast
scene has two types of spherical light sources. The radius of the large light
source (light 0) accounts for 8.3% of the largest extent of the scene, while
the radius of the two small light sources (light 1 and light 2) accounts for
1.6%. We use this simple light source setting to perform experiments without
increasing the complexity of the original scenes. The measurements are
performed on GeForce RTX 3060 GPU with an image resolution of 1920 x 1080. And
the execute code is compiled in CUDA 10.0. All recorded data are averages. We
run each scene three times and count the data of 100 frames each time to
collect the average running time and the number of rays.

###  6.1 Hyperparameters Selection

The experiment of ray reordering involves the selection of two
hyperparameters. One is the $\lambda$ that be used to calculate the HAD value.
The other is the average distance used to estimate termination point of
Two_Point method. This part will show the reasons for the selection of these
hyperparameters. To select the appropriate hyperparameters, we have carried
out experiments in many scenes and plot their relative trace speed in Figure
12 and Figure 13. The relative trace speed is defined as the trace speed in
certen hyperparameters divide by the trace speed in the hyperparameters we
choose ($\lambda$ = 0.125, average distance = 0.25).

Figure 12: The trace performance of hierarchy cut code with different
$\lambda$ value.

The hyperparameter $\lambda$ will affect the weight of internal node surface
area when calculating the HAD value. We choose some parameter values unevenly
between 0.1-1 and plot the trace speed in Figure 12. Experiments have proved
that $\lambda$ value of 0.125 is appropriate. Although for some scenes, this
is not an optimal choice. In order to avoid the unfairness of the performance
test caused by the over-adaptation scenes by hyperparameter selection, we does
not use the best hyperparameter each scene. The result also shows that not
every different $\lambda$ value will greatly affect the trace speed. This is
because the $\lambda$ affects the trace speed by affecting the selection of
cut nodes. The breadth-first based search order determines that the upper
nodes will be searched sooner or later. Changes in lambda values sometimes
only affect one or two cut nodes. Therefore, the variation of $\lambda$ in 0.1
to 1 will not have a significant impact on trace speed.

Figure 13: The trace performance of Two_Point method with different average distance. Table 2: Secondary ray trace speed comparison of our methods and test methods. The trace speed is measured in million rays per second (MRay/s). The numbers in parentheses represent the acceleration ratio of the method. Scene | Breakfast | Salle de Bain | Livingroom | Sibenik | Vokselia
---|---|---|---|---|---
#Triangles | 1347K | 1231K | 580K | 75K | 1876K
|  |  |  |  |
NoSort | 37.4 (1.00) | 206.1 (1.00) | 189.4 (1.00) | 154.7 (1.00) | 64.2 (1.00)
HCC (Ours) | 67.6 (1.81) | 284.9 (1.38) | 277.1 (1.46) | 208.1 (1.35) | 71.7 (1.12)
MLHCC (32bits) | 65.1 (1.74) | 280.2 (1.36) | 277.8 (1.47) | 218.5 (1.41) | 74.4 (1.16)
MLHCC (16bits) | 58.4 (1.56) | 254.0 (1.23) | 250.6 (1.32) | 207.6 (1.34) | 73.2 (1.14)
Regular Grid | 51.4 (1.37) | 247.1 (1.19) | 243.3 (1.28) | 188.7 (1.22) | 70.7 (1.10)
Two_Point | 56.8 (1.52) | 274.2 (1.33) | 272.1 (1.44) | 217.9 (1.41) | 75.5 (1.18)
Aila_Compact | 55.6 (1.48) | 268.0 (1.30) | 258.2 (1.36) | 208.9 (1.35) | 75.5 (1.18)
Reis | 49.7 (1.33) | 242.4 (1.18) | 224.8 (1.19) | 183.2 (1.18) | 74.3 (1.16)
Origin | 46.1 (1.23) | 233.0 (1.13) | 208.3 (1.10) | 165.4 (1.07) | 74.8 (1.17)
PPC | 68.3 (1.82) | 342.0 (1.66) | 348.5 (1.84) | 278.0 (1.80) | 87.1 (1.36)

The average distance will affect the termination point estimation for
Two_Point method. Meister et al.’ work used the value 0.25 to perform the
test. We choose some parameter values unevenly between 0.1-1 and plot the
trace speed in Figure 13. The experiment shows that 0.25 is an appropriate
choice. Although the average distance is used to estimate the termination
point, we believe it acts more like the mixed weight of origin and direction.
The greater the average distance, the greater the influene of direction on
estimated termination point. Therefore, the coding will contain more direction
information.

###  6.2 Ray Tracing Performance Overall

Table 2 shows a summary of the secondary ray trace performance. The bold data
represents the best performance in the corresponding scene. The highest
secondary ray speedup of various encoding methods are: Origin 1.23x, Reis
1.33x, Alia_Compact 1.48x, Two_Point 1.52x, HCC 1.81x, MLHCC 1.56x, PPC 1.84x.
All these methods achieve the highest speedup in Breakfast scene except prefix
path code. Prefix path code method gives us a soft upper bound of performance
that can be achieved by increasing traversal path coherence.

In two scenes our hierarchy cut code does not reach the best performance with
32-bit length. In order to analyze this phenomenon, we provide cut node
boundaries of hierarchy cut code in Figure 11. In Breakfast, Salle de Bain and
Livingroom scenes, the cut nodes match the details in the scene, which are the
most complex part in the scenes. Spending more bits on such details can
effectively encode the ray. In Sibenik scene, our method does not find such
details. The Sibenik scene is a scene similar to an empty box. The scene is
relatively spacious as a whole, with details concentrated on the wall at the
edge of the scene. Therefore, the cut node can only roughly represent the
boundary of the scene, but not the internal space. This will cause that most
of the rays can only pass through 3-4 cut nodes, thus further aggravating the
problem of insufficient cut nodes.

The experiment on Vokselia scene exposes that the reordering techniques have
trouble dealing with the large scale scene. All the reordering technique falls
in this scene (achieve only 1.1 speed up). The reason why our method fails in
this scene is that there are too many details contained in one code boundary.
For example, the forest in this scene is present in only one cut node, which
cannot help to determine whether a ray can pass this forest. Ordinary methods
fail beacuse of similar reasons. For the encoding method applicable to the
whole scene, the large-scale scene is a challenge. It can be predicted that
the reordering technique will suffer similar performance degradation when the
scene is divided into several areas, like a big house with many rooms. In
these cases, the existing encoding methods inevitably waste bits on space that
ray will not access at all. In this case, one should divide the scene into
different regions according to the viewport and encoding rays in different
regions separately.

The speedup improvement achieved by hierarchy cut code comes from avoiding the
boundary drift, rather than the advantage of using the intersection result of
bounding box and ray to encode the ray. The fifth row of the Table 2 shows the
trace speed using regular grid encoding. As mentioned in section 5, regular
grid encoding is basically the same as that of hierarchy cut code except that
it does not use BVH cut. From the data in the Table 2, regular grid encoding
has no advantages in performance compared with hierarchy cut code or Two_Point
method because it uses regular grid as the coding boundary, which will face
the boundary drift problem. This confirms the necessity of eliminating
boundary drift.

Multi-level hierarchy cut code can achieve acceptable performance in most
scene with only 16 bits. Such result proves that multi-level hierarchy cut
code is very efficient when using code with short bit length. By using a
shorter sorting key, multi-level hierarchy cut code can reduce encoding and
sorting overhead. However, 32-bit multi-level hierarchy cut code does not
achieve better result than hierarchy cut code in most scenes. Only in Sibenik
and Vokselia scenes, multi-level hierarchy cut code performs better than
hierarchy cut code. The 32-bit multi-level hierarchy cut code is essentially a
compressed version of the 256-bit hierarchy cut code. Multi-level hierarchy
cut code will abandon many information about top level cut nodes, as the last
paragraph of Section 4.4 analyzes. Such information loss may cause the coding
after compression to become less effective. On the other hand, using longer
sort keys does not always get better result. The experiment in section 6.6
will further explore this problem.

Figure 14: The reflection ray trace performance in Breakfast scene for subsequent bounces. Table 3: Primary shadow ray trace comparison of our methods and test methods. The trace speed is measured in million rays per second (MRay/s). The numbers in parentheses represent the acceleration ratio of the method. Scene | Breakfast | Salle de Bain | Livingroom | Sibenik | Vokselia
---|---|---|---|---|---
#Triangles | 1347K | 1231K | 580K | 75K | 1876K
NoSort | 152.4 (1.00) | 700.7 (1.00) | 425.6 (1.00) | 163.5 (1.00) | 501.3 (1.00)
HCC (Ours) | 230.6 (1.51) | 850.8 (1.21) | 522.9 (1.23) | 253.6 (1.55) | 537.5 (1.07)
MLHCC (32bits) | 238.5 (1.56) | 821.0 (1.17) | 507.9 (1.19) | 234.6 (1.44) | 521.1 (1.04)
MLHCC (16bits) | 206.1 (1.35) | 795.2 (1.13) | 499.3 (1.17) | 245.7 (1.50) | 520.4 (1.04)
Regular Grid | 156.4 (1.03) | 688.9 (0.98) | 419.8 (0.99) | 201.9 (1.29) | 491.6(0.98)
Two_Point | 257.1 (1.69) | 975.4 (1.39) | 561.0 (1.32) | 314.5 (1.92) | 521.7 (1.04)
Aila_Compact | 275.7 (1.81) | 1032.1 (1.47) | 580.0 (1.36) | 324.1 (1.98) | 632.0 (1.26)
Reis | 276.6 (1.81) | 1048.4 (1.50) | 577.1 (1.36) | 268.2 (1.64) | 664.5 (1.33)
Origin | 245.6 (1.61) | 1090.9 (1.56) | 527.9 (1.24) | 204.8 (1.25) | 747.0 (1.49)
PPC | 287.8 (1.89) | 1208.9 (1.73) | 682.1 (1.60) | 323.0 (1.98) | 820.7 (1.64)

Reordering technique can accelerate arbitrary reflection rays, not just
secondary ray. Figure 14 shows the example of the influence of reordering on
different bounces of reflection on breakfast scene. In each reflection, the
reordering technique has achieved a certain acceleration effect. However the
speed of ray tracing will still decrease as the reflection bounces increase
even if the reordering technology is applied. With the random reflection of
rays in the scene, they will inevitably become more and more scattered in the
scene.

###  6.3 Shadow Ray Acceleration

The reordering method can also accelerate the tracing efficiency of shadow
rays, as shown in Table 3. We test the primary shadow ray trace performance.
When accelerating shadow rays, our method is far less efficient than ordinary
reordering techniques. While Two_Point method achieves 1.92x speedup in the
Sibenik scene, the hierarchy cut code only achieves 1.55x speedup in the
Sibenik scene. This result is related to the characteristics of shadow rays.
Because shadow rays will directly point to the light source, most shadow rays
will point to nearby locations. Especially when there is only one small light
source in the scene. Since shadow rays always point to the light source,
encoding the ray’s direction or end point can be more effective in that
situation. Hierarchy cut code can achieve relatively good speedup effect in
Breakfast and Sibenik scene. As the lighting settings in Table 1, this two
scenes have multiple light sources applied, so the shadow rays will not point
to single location.

(a) Breakfast scene in limited viewport.

(b) Salle de Bain scene in limited viewport.

(c) Livingroom scene in limited viewport.

(d) Sibenik scene in limited viewport.

Figure 15: Four scenes rendered in limited viewport. The speedup ratio of
hierarchy cut code in these scenes are: (a) 1.81 in Breakfast, (b) 1.42 in
Salle de Bain, (c) 1.49 in Livingroom, (d) 1.49 in Sibenik.

###  6.4 Performance in Limited Viewport

The experiment of shadow ray acceleration proves that the distribution of ray
will affect the acceleration effect of hierarchy cut code. Limited viewport,
which means only a small part of scene is on the screen, will also affect the
ray distribution. The ray will hit the same small area in the scene, and then
reflect into the whole area. Figure 15 shows the rendering images with limited
viewport. The performance of the our method will not be greatly affected from
this perspective. Hierarchy cut code achieves a competitive speedup ratio in
such limited viewport (1.81 in Breakfast, 1.42 in Sall de Bain, 1.49 in
Livingroom, 1.49 in Sibenik). This result proves that the hierarchy cut code
has sufficient robustness to cope with the impact of limited viewport. The
performance of other methods in limited viewport is placed in the appendix.

###  6.5 Overhead of Reordering Techniques

Evaluating the overhead is an important part of evaluating reordering
techniques performance. This is also the main reason why we abandoned the
prefix path code as a feasible reordering technique. Table 4 shows the
overhead of each method in Breakfast scene. Reis, Aila_Compact and Two_Point
have the same overhead, so we only display the overhead of Two_Point method.
The percentage column is the ratio of total overhead (encode overhead plus
sort overhead) to tracing time. Result shows that our hierarchy cut code has
the similar overhead as ordinary methods. Meanwhile, multi-level hierarchy cut
code (16 bits) has less sort and encode overhead because it uses a shorter
sorting key. This shows the feasibility of using compression coding to reduce
overhead. Multi-level hierarchy cut code (32 bits) has larger encode overhead
compared to hierarchy cut code with the same sorting key length, because it
does multi-level encoding.

Under our experiment setup, the acceleration effect of reordering method can
payoff its overhead. However, this overhead still needs to be further reduced,
so that the reordering method is worth using in the faster tracing core.
Compression schemes such as multi-level hierarchy cut code can become an
option, because it can shorten the encoding length while retaining the
acceleration effect, thus reducing the overhead.

Table 4: Overhead of reordering techniques in Breakfast scene. |  Encode (ms) |  Sort (ms) |  Sum (ms) | Percentage
---|---|---|---|---
HCC (Ours) | 4.51 | 9.35 | 13.86 | 5.66%
MLHCC (16bits) | 3.36 | 5.47 | 8.83 | 3.19%
MLHCC (32bits) | 5.76 | 9.38 | 15.14 | 5.63%
Two_Point | 2.73 | 9.44 | 12.17 | 4.24%
PPC | 24.93 | 9.41 | 34.34 | 13.06%

###  6.6 Reordering Techniques with Longer Sorting Keys

Table 5 shows the secondary ray tracing performance in Sibenik scene using
sorting keys of different bit length. Origin, Reis, Aila_Compact and Two_Point
have the same pattern when using different length of sorting keys, so we only
display the pattern of Two_Point method. Our methods (PPC, HCC, MLHCC) can
benefit from longer sorting keys, while ordinary methods cannot.

Table 5: The trace speed (MRays/s) with different sorting key bit length in Sibenik scene. | 16bits | 32bits | 64bits
---|---|---|---
HCC (Ours) | 187.2 | 208.1 | 222.0
MLHCC | 207.6 | 218.5 | 240.9
Two_Point | 193.5 | 217.9 | 220.5
PPC | 213.9 | 274.7 | 293.7

Longer sorting keys can make ray encoding more accurate. It can make the ray
coding have a finer coding boundary, so it is easier to distinguish rays by
different codes. But in fact, it is the traversal path coherence inside the
warps that ultimately affects the tracing efficiency. How the rays in the same
warp are arranged will not affect the tracing efficiency. If a finer encoding
cannot change the ray arranged, it will not help to the tracing speedup.

A finer coding will not change the order of rays which already have different
code. For example, if two rays are encoded as 1 and 2. The order of this two
rays will not change when they get a finer coding with longer sorting key,
like 1.x and 2.y (x and y represent any decimal number). Only when the rays in
multiple warps have the same code, in other words, the encoding is very rough,
the longer sort key will change the ray order and improve the tracing
efficiency.

Table 6: Average number of codes with different sorting key bit length in Sibenik scene. | 16bits | 32bits | 64bits
---|---|---|---
HCC (Ours) | 1.02 | 1.17 | 1.73
MLHCC | 1.06 | 1.52 | 2.87
Two_Point | 1.88 | 13.94 | 13.94
PPC | 1.05 | 4.33 | 18.02

To further confirm this analysis, we count the average number of codes (ANC).
The average number of codes refers to how many different codes will be
obtained in one warp on average if rays are encoded by certain encoding
method. The result is shown in Table 6. We can see that the Two_Point method
has a much larger average number of codes than other methods in 32 bits
sorting key. Average number of codes reflects the sufficiency of encoding.
Only when the ANC is small enough can the encoding method benefit from the
longer sorting key.

From Table 6, we can see all these methods have small ANC when using 16 bits
sorting key. At this time, their encoding is insufficient. Using longer
sorting keys can improve tracing efficiency. However, the Two_Point method
already has a relatively large ANC value using 32 bits sorting key. This means
that the ray has been fully encoded, and increasing sorting keys’ length has
little effect on tracing efficiency. This is why Two_Point method using 64
bits sorting key does not achieve significant performance improvement compared
with 32 bits version. As we mentioned in Section 3.2, Two_Point method suffers
from boundary drift. Therefore, when the encoding is sufficient, its tracing
efficiency is worse than hierarchy cut code. The other three types of methods
have small ANC values using 32 bits sorting key, so they can still benefit
from longer sorting keys.

In conclusion, increasing the encoding accuracy cannot always improve the
tracing efficiency. When encoding method has a high ANC value, the encoding is
already sufficient. Using longer sorting key cannot further boost the
performance in that case. Therefore, increasing the coding accuracy is not a
universal solution. An essential improvement direction is to ensure the
consistency of traversal path coherence and ray spatial coherence measured by
encoding method.

###  6.7 Discussion

####  6.7.1 Application in Faster Tracing Kernels

The reordering method needs a higher speedup and smaller overhead to be
applied in faster tracking core. Meister et al.’ work found that the large
overhead makes the reordering techniques only achieve low speedup (even
negative speedup) on RTX platform. In this paper, two feasible ways to reduce
the overhead are proposed. One is to use some compression scheme, such as
MLHCC. The other solution should be combined with our analysis in Section 6.6.
Since the arrangement of rays will not affect the tracing efficiency, sorting
the rays in same warp seems unnecessary. Taking measures to eliminate these
unnecessary work can increase the sorting speed. For example, we can skip the
last few bits encoding and end bucket sorting early. Or we can try to use some
heuristic methods to sacrifice the accuracy of sorting in exchange for faster
sorting speed. Hardware acceleration scheme may also be an option.

Because the process to encode hierarchy cut code needs to access the
acceleration structure, it cannot be applied to RTX core by existing
framework. We do not carry out our experiments on the RTX core. However, our
work addresses two key problems found in Meister et al.’ work for reordering
techniques, which are the large overhead and bit bottleneck. Therefore,
although our work can not give the final answer (or solution) to that one-
million dollars question if ray reordering preprocessing step pays off in
current RTX platform, our work does contribute to answering that. If the
reordering method can really speed up the tracing process, it can be expected
to achieve better implementation efficiency through hardware implementation.

####  6.7.2 Better Encoding Method

For reordering technology, a better encoding scheme is not equivalent to a
more accurate encoding scheme. The analysis in Section 6.6 shows that simply
increasing the sorting key length does not guarantee improved tracing
performance. Only when the encoding is still insufficient, such as our
hierarchy cut code, longer sorting keys can improve the tracing performance.
Besides longer sorting key, finding a better cut nodes searching method or
compression method can also help solve this problem. Combining our encoding
method with traditional encoding method may be a way to solve the problem of
insufficient encoding and boundary drift at the same time. Although this seems
to increase the encoding time.

####  6.7.3 Adapting Large Scene

Experiments show that the existing reordering techniques cannot achieve good
acceleration result in large scale scenes. In the large scale scenes, each ray
can only use a small part of the code. Most of the codes will be wasted
because they are used to express parts that the ray will never access. In
order to solve this problem, we need to apply some scene partitioning methods
to ensure that the encoding bits will not be wasted in the place that the
current perspective will not see at all.

##  7 Conclusion

In this parer, we present hierarchy cut code in solving the negative impact of
bounding drift on ray reordering technique. By encoding the rays based on a
BVH cut, we avoid the performance drawback caused by bounding drift.
Hierarchically accumulated density enables code to automatically adapt to
areas with dense meshes. For which our method obtains better tracing
performance and higher robustness. Besides, multi-level hierarchy cut code
reaches the similar performance with half sorting key length. In addition, we
analyze and address the issue that ordinary reordering techniques cannot
benefit from longer sorting keys. These results prove that a more versatile
reordering effect can be obtained by directly targeting the accelerated
structure encoding regardless of the spatial position. This should be an
important guidance for the further reordering technique development.

##  8 Acknowledgments

This work was supported by National Key R&D Program of China (No:
2021YFF0500302) and National Natural Science Fund of China (No: 61502185). We
would like to thank Benedikt Bitterli and Morgan McGuire for providing the
test scenes.

## References

  * [AK10] Timo Aila and Tero Karras  “Architecture Considerations for Tracing Incoherent Rays”  In _Proceedings of the Conference on High Performance Graphics 2010_ The Eurographics Association, 2010, pp. 113–122  DOI: 10.2312/EGGH/HPG10/113-122
  * [AK87] James Arvo and David Kirk  “Fast ray tracing by ray classification”  In _ACM SIGGRAPH Computer Graphics_ 21.4, 1987, pp. 55–64  DOI: 10.1145/37402.37409
  * [AL09] Timo Aila and Samuli Laine  “Understanding the efficiency of ray traversal on GPUs”  In _Proceedings of the Conference on High Performance Graphics 2009_ , 2009, pp. 145–149  DOI: 10.1145/1572769.1572792
  * [Ant11] Dietger van Antwerpen  “Improving SIMD efficiency for parallel Monte Carlo light transport on the GPU”  In _HPG ’11: Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics_ , 2011, pp. 41–50  DOI: 10.1145/2018323.2018330
  * [Bit16] Benedikt Bitterli  “Rendering resources” https://benedikt-bitterli.me/resources/, 2016
  * [BWB08] Solomon Boulos, Ingo Wald and Carsten Benthin  “Adaptive ray packet reordering”  In _2008 IEEE Symposium on Interactive Ray Tracing_ , 2008, pp. 131–138  DOI: 10.1109/RT.2008.4634633
  * [CMJ15] Vasco Costa, J. Madeiras Pereira and Joaquim A. Jorge  “Accelerating Occlusion Rendering on a GPU via Ray Classification”  In _International journal of creative interfaces and computer graphics_ 6.2, 2015, pp. 1–17  DOI: 10.4018/IJCICG.2015070101
  * [ENSB13] Christian Eisenacher, Gregory Nichols, Andrew Selle and Brent Burley  “Sorted Deferred Shading for Production Path Tracing”  In _Computer Graphics Forum_ 32.4, 2013, pp. 125–132  DOI: 10.1111/cgf.12158
  * [GL10] Kirill Garanzha and Charles Loop  “Fast Ray Sorting and Breadth-First Packet Traversal for GPU Ray Tracing”  In _Computer Graphics Forum_ 29.2, 2010, pp. 289–298  DOI: 10.1111/j.1467-8659.2009.01598.x
  * [GPSS07] Johannes Gunther, Stefan Popov, Hans-Peter Seidel and Philipp Slusallek  “Realtime Ray Tracing on GPU with BVH-based Packet Traversal”  In _2007 IEEE Symposium on Interactive Ray Tracing_ , 2007, pp. 113–118  DOI: 10.1109/RT.2007.4342598
  * [GS87] Jeffrey Goldsmith and John Salmon  “Automatic Creation of Object Hierarchies for Ray Tracing”  In _IEEE Computer Graphics and Applications_ 7.5, 1987, pp. 14–20  DOI: 10.1109/MCG.1987.276983
  * [HB01] V. Havran and J. Bittner  “LCTS: Ray Shooting using Longest Common Traversal Sequences”  In _Computer Graphics Forum_ 19.3, 2001, pp. 59–70  DOI: 10.1111/1467-8659.00398
  * [HPMB19] J. Hendrich, A. Pospisil, D. Meister and J. Bittner  “Ray Classification for Accelerated BVH Traversal”  In _Computer Graphics Forum: Journal of the European Association for Computer Graphics_ 38.4, 2019, pp. 49–56  DOI: 10.1111/cgf.13769
  * [LKA13] Samuli Laine, Tero Karras and Timo Aila  “Megakernels considered harmful: wavefront path tracing on GPUs”  In _HPG ’13: Proceedings of the 5th High-Performance Graphics Conference_ , 2013, pp. 137–143  DOI: 10.1145/2492045.2492060
  * [LVY*20] Daqi Lin et al.  “Hardware-Accelerated Dual-Split Trees”  In _Proceedings of the ACM on Computer Graphics and Interactive Techniques_ 3.2 ACM, 2020  DOI: 10.1145/3406185
  * [MB90] J.David MacDonald and Kellogg S. Booth  “Heuristics for ray tracing using space subdivision”  In _The Visual Computer volume 6_ , 1990, pp. 153–166  DOI: 10.1007/BF01911006
  * [MBGB20] Daniel Meister, Jakub Boksansky, Michael Guthe and Jiri Bittner  “On Ray Reordering Techniques for Faster GPU Ray Tracing”  In _I3D ’20: Symposium on Interactive 3D Graphics and Games_ , 2020, pp. Article No.13  DOI: 10.1145/3384382.3384534
  * [MBK*10] Bochang Moon et al.  “Cache-oblivious ray reordering”  In _ACM Transactions on Graphics_ 29.3, 2010, pp. Article No.28  DOI: 10.1145/1805964.1805972
  * [McG17] Morgan McGuire  “Computer Graphics Archive”, 2017  URL: https://casual-effects.com/data
  * [MOB*21] Daniel Meister et al.  “A Survey on Bounding Volume Hierarchies for Ray Tracing”  In _Computer Graphics Forum_ 40.2, 2021, pp. 683–712  DOI: 10.1111/cgf.142662
  * [NFLM07] Paul Arthur Navratil, Donald S. Fussell, Calvin Lin and William R. Mark  “Dynamic Ray Scheduling to Improve Ray Coherence and Bandwidth Utilization”  In _2007 IEEE Symposium on Interactive Ray Tracing_ , 2007, pp. 95–104  DOI: 10.1109/RT.2007.4342596
  * [NVZJ19] Merlin Nimier-David, Delio Vicini, Tizian Zeltner and Wenzel Jakob  “Mitsuba 2: a retargetable forward and inverse renderer”  In _ACM Transactions on Graphics_ 38.6, 2019, pp. Article No.203  DOI: 10.1145/3355089.3356498
  * [PKGH97] Matt Pharr, Craig Kolb, Reid Gershbein and Pat Hanrahan  “Rendering complex scenes with memory-coherent ray tracing”  In _SIGGRAPH ’97: Proceedings of the 24th annual conference on Computer graphics and interactive techniques_ , 1997, pp. 101–108  DOI: 10.1145/258734.258791
  * [RCP17] Nuno T. Reis, Vasco S. Costa and J.. Pereire  “Coherent Ray-Space Hierarchy via Ray Hashing and Sorting”  In _Proceedings of the 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2017)_ , 2017, pp. 195–202  DOI: 10.5220/0006098001950202
  * [RSH05] Alexander Reshetov, Alexei Soupikov and Jim Hurley  “Multi-level ray tracing algorithm”  In _ACM Transactions on Graphics_ 24.3, 2005, pp. 1176–1185  DOI: 10.1145/1073204.1073329
  * [SP99] Laszlo Szirmay-Kalos and Werner Purgathofer  “Global Ray-bundle Tracing with Infinite Number of Rays”  In _Computers & Graphics_ 23.2, 1999, pp. 193–202  DOI: 10.1016/S0097-8493(99)00029-1
  * [TMG11] R. Torres, P.. Mart´ın and A. Gavilanes  “Traversing a BVH Cut to Exploit Ray Coherence”  In _Grapp - International Conference on Computer Graphics Theory and Applications_ , 2011, pp. 140–150
  * [Tsa09] John A. Tsakok  “Faster incoherent rays: Multi-BVH ray stream tracing”  In _Proceedings of the Conference on High Performance Graphics 2009_ , 2009, pp. 151–158  DOI: 10.1145/1572769.1572793
  * [Wal11] Ingo Wald  “Active thread compaction for GPU path tracing”  In _HPG ’11: Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics_ , 2011, pp. 51–58  DOI: 10.1145/2018323.2018331
  * [YKL17] Henri Ylitie, Tero Karras and Samuli Laine  “Efficient incoherent ray traversal on GPUs through compressed wide BVHs”  In _HPG ’17: Proceedings of High Performance Graphics_ , 2017, pp. Alticle No.4  DOI: 10.1145/3105762.3105773

##  Appendix A Hierarchy Cut Code with Direction Encoding

Encoding the direction information into hierarchy cut code will not improve
the performance. From Table 7, we can see that the hierarchy cut code with
direction information (HCC_DIR) performance even worse than 31 bit version.
That is because the direction information introduces boundary drift to the
code.

Table 7: The trace speed of hierarchy cut code with direction information. | Trace Speed (MRays/s)
---|---
| HCC | HCC_DIR | HCC_31bit
Breakfast | 67.6 | 60.6 | 65.3
Salle de Bain | 284.9 | 278.8 | 284.1
Livingroom | 277.1 | 263.1 | 275.9
Sibenik | 208.1 | 203 | 203.5
Vokselia | 71.7 | 71.4 | 71.1

##  Appendix B Performance Overall in Limited Viewport

Table 8 shows the performance overall in limited viewport. By comparing Table
8 and Table 2, it is proved that the limited viewport will not affect the
acceleration performance.

Table 8: Secondary ray trace speed comparison of our methods and test methods in limited vierport. The trace speed is measured in million rays per second (MRay/s). The numbers in parentheses represent the acceleration ratio of the method. Scene | breakfast | bathroom | livingroom | Sik
---|---|---|---|---
|  |  |  |
NoSort | 41.1(1.00) | 170.7(1.00) | 132.5(1.00) | 125.2(1.00)
HCC(Ours) | 74.4(1.81) | 241.3(1.41) | 197.5(1.49) | 186.9(1.49)
MLHCC32 | 77.9(1.90) | 235.1(1.38) | 188.3(1.42) | 194.9(1.56)
MLHCC16 | 73.1(1.78) | 220.6(1.29) | 165.4(1.25) | 183.9(1.47)
RG | 62.4(1.52) | 217.1(1.27) | 178.5(1.35) | 166.4(1.33)
TP | 63.8(1.55) | 243.4(1.43) | 202.8(1.53) | 199.9(1.60)
Aila | 61.2(1.49) | 236.7(1.39) | 193.3(1.46) | 188.6(1.51)
Reis | 52.9(1.29) | 217.8(1.28) | 169.4(1.28) | 161.8(1.29)
Origin | 44.7(1.09) | 204.6(1.20) | 148.0(1.12) | 133.8(1.07)
PPC | 83.8(2.04) | 281.0(1.65) | 249.0(1.88) | 236.1(1.88)