A possible issue with kd-tree construction

[harrytodorov]

Dear Mr. Pharr,

While reading through, reimplementing and testing the algorithm for the kd-tree construction, I think, I've encountered a small issue, which doesn't manifest itself visually, but rather leads to a slight memory overhead (higher number of nodes created).

It's in the way bound edges are sorted here when two bound edges have an overlapping split position: then a BoundEdge with a Start type would come before a BoundEdge with End type.

Let me clarify it upon a simple example (here is a render):

Given: 5 equilateral triangles (tri0..tri4), which lie on the same plane next to each other, with the property that when one look at two neighbouring triangles: the vertex down right of the triangle on the left would have the same position as the vertex down left of the right triangle.

This would lead to every pair of neighbouring triangles to have two BoundEdges between them: one of type Start and one of type End, when using the sort you've provided, the 10 bound edges will be sorted like this (tri0.. represent the leftmost and tri4.. the rightmost triangle along the axis):

• tri0BoundEdgeStart
• tri1BoundEdgeStart
• tri0BoundEdgeEnd
• tri2BoundEdgeStart
• tri1BoundEdgeEnd
• tri3BoundEdgeStart
• tri2BoundEdgeEnd
• tri4BoundEdgeStart
• tri3BoundEdgeEnd
• tri4BoundEdgeEnd

When one has set the maximum number of primitives per leaf node to be 1, at the root node of the scene SAH would compute the best split position between tri1 and tri2 (tri1BoundEdgeEnd).

The issue comes, when classifying which triangles would be put in the left (below) child node and which in the right (above) child node: below and above. The algorithm puts (tri0, tri1, tri2) in the below child node and (tri2, tri3, tri4) in the above child node, when actually the optimal solution for the case would be to have:

• below child node having (tri0, tri1)
• above child node having (tri2, tri3, tri4)

Although the case above is rather trivial and this additional primitive in the below child node would not cause much trouble for the renderer, I've tested my guess on a larger model (the Ajax bust model with ca. 500K triangles, render here) and here are some statistical information I've gathered for the construction and traversal of the rendered scene using the sort as described in PBR (768x768 pixels with 32 samples per pixel and a normal integrator):

Construction: KdTreeConstrcutionStatistics[
  nodes = 2672837 (1336418 interiors, 1336419 leafs)
  avg number of primitives per leaf = 2.887413
  maximum number of primitives per leaf = 182
  minimum tree depth = 2
  maximum tree depth = 32
  tree size using KdNode (1 node 8 B) = 20.3921 MiB
  primitives list's array size = 14.0909 MiB
  overall kd-tree size = 34.4830 MiB
]
Traversal: KdTreeTraversalStatistics[
  rays = 18874368
  rays hitting the kd-tree = 10046066 (53.23% of all rays)
  rays tested against a primitive = 4903210 (25.98% of all rays,
                                    48.81% of rays hitting the kd-tree)
  rays hitting a primitve = 4758071 (47.36% of rays hitting the kd-tree,
                            97.04% of rays tested against a primitve)
  ray-primitive intersections = 98573006
  maximum number of intersected primitives for a ray = 500
  avg number of intersected primitives per ray = 20.10
  traversed nodes = 450115619 (81.56% interior, 18.44% leaf)
  avg number traversed nodes per ray = 44.81 (36.54 interior, 8.26 leaf)
]

When one modifies the sorting such that when two BoundEdges have the same split position to place bound edge of type End before bound edges of type Start by changing line from:

                      return (int)e0.type < (int)e1.type;

to

                      return (int)e0.type > (int)e1.type;

one gets following statistical information for the same scene:

Construction: KdTreeConstrcutionStatistics[
  nodes = 2430203 (1215101 interiors, 1215102 leafs)
  avg number of primitives per leaf = 2.124240
  maximum number of primitives per leaf = 172
  minimum tree depth = 2
  maximum tree depth = 32
  tree size using KdNode (1 node 8 B) = 18.5410 MiB
  primitives list's array size = 9.2062 MiB
  overall kd-tree size = 27.7472 MiB
]
Traversal: KdTreeTraversalStatistics[
  rays = 18874368
  rays hitting the kd-tree = 10046066 (53.23% of all rays)
  rays tested against a primitive = 4897997 (25.95% of all rays,
                                    48.76% of rays hitting the kd-tree)
  rays hitting a primitve = 4758071 (47.36% of rays hitting the kd-tree,
                            97.14% of rays tested against a primitve)
  ray-primitive intersections = 79348699
  maximum number of intersected primitives for a ray = 345
  avg number of intersected primitives per ray = 16.20
  traversed nodes = 448274713 (81.59% interior, 18.41% leaf)
  avg number traversed nodes per ray = 44.62 (36.41 interior, 8.22 leaf)
]

One can see, there is a rather significant impact on the quality of the construction, number of nodes created for the tree (Construction -> KdTreeConstrcutionStatistics -> nodes) is around 10% less, which also slightly affects the performance of the traversal afterwards (Traversal -> KdTreeTraversalStatistics -> avg number of intersected primitives per ray).

Sadly, I cannot provide you with the two scenes mentioned above in pbrt format, because I don't have them, but would be glad to provide any additional feedback, if needed!

Thank you for the time taken to read this rather lengthy explanation!

Best regards, Haralambi

[harrytodorov]

I'm sorry for this report. Recently, I was able to test my statement through and because of it and it is false.