I have a problem understanding this algorithm, labeled "Algorithm 1" from this paper.
It says:

If at leaf, check for intersection with contained triangles.

What am I missing? As far as I know, the kd-tree nodes only hold one value and pointers to left and right children. Do you know any reference kd-tree structures for me to investigate? At insert, I calculate middlepoints for each axis and based on that, I place one triangle for each node.

CodePudding user response：

In case of GPU Ray Tracing, KD-Trees are used as acceleration structures. We group geometry into larger chunks to cull ray misses early. However, it might happen, that the tree gets too deep at certain nodes. To avoid this, we can limit the height of the tree. This is why we might end up with more geometry in a leaf.

Note, that Algorithm 3 also mentions this case.

The exit step
24: Intersect ray with contained geometry

Clarifying "too deep":
When a branch goes much deeper than it's neighbours, the threads diverge, causing performance degradation .

More on the topic here: Nvidia RTX best practices

CodePudding user response：

Storing only one triangle per node is probably sub-optimal. Generally, it is faster to iterate through a moderately sized bucket of objects than to navigate the same sized binary tree.

Also, there is no guarantee that you will be able to sort out all your triangles such that your k-D tree has one per node. Hierarchical bounding volumes (where, unlike k-D trees, sibling volumes may overlap) should be more flexible in this respect, but they are also conventionally used with buckets of target objects, rather than one object per node.