The Next Week: The book says the ordering of bvh_node children doesn't matter, but acts like it does

[DeltaPavonis]

In Section 3: Bounding Volume Hierarchies of "Ray Tracing: The Next Week", the first example given of a BVH (3.2) notes that the order of left and right children in a bvh_node does not matter (emphasis mine):

Note that the blue and red bounding volumes are contained in the purple one, but they might overlap, and they are not ordered — they are just both inside. So the tree shown on the right has no concept of ordering in the left and right children; they are simply inside.

However, in the subsequent code for splitting BVH volumes (3.9), a constraint seems to be imposed where the left child of a bvh_node always contains the objects which have axis value less than the right child. Specifically, in the code

        } else if (object_span == 2) {
            if (comparator(objects[start], objects[start+1])) {
                left = objects[start];
                right = objects[start+1];
            } else {
                left = objects[start+1];
                right = objects[start];
            }
        } else {

When the current objects list has only 2 objects, the given code always places the object with the lesser coordinate along the chosen axis in the left child. However, why can't we just always set left = objects[start]; and right = objects[start + 1];, saving a call to comparator? Doesn't the ordering of the left and right children not matter, as stated before? If it does, then why does the ordering matter now?

[hollasch]

Hmmm, well, you're right and you're wrong. Technically you can just arbitrarily divide the objects into two groups, and everything will still work. However, an arbitrary partition will yield bounding volumes that will likely overlap quite a bit. That's why in the next section it says that "… we need to make good divisions, rather than bad ones, …". But this needs to be reworded because we "make good divisions" in the interest of speed, as "bad" divisions will still yield functional results. So it looks like we need to clarify the text here.

But, the case with only two objects is special. With many objects, ordering them in one dimension will yield a tighter cluster, and thus smaller and minimally overlapping boxes for the two groups. With only two objects, though, you're absolutely correct — dividing is trivial, and the two boxes will be as small as can be. Order doesn't matter, as you point out. The code should be simplified exactly as you say.

[hollasch]

The code portion of this issue should be included in PR #1391.

The rewriting work I mention above will be included in a separate change.

[hollasch]

@DeltaPavonis — Nice catch, by the way!

[hollasch]

Done.