Reduce kd-tree's nodes' bounding box sizes to their shapes' extents?

Question

I've implemented a ray tracer that uses kd-trees for acceleration. To help debug kd-tree construction, I also created a crude OpenGL view of the same scene that shows the axis-aligned bounding boxes (AABBs) for each node in the tree (along with the shapes in the scene), and allows the user to highlight a specific node in the tree.

Here is an example of a scene with a bunch of spheres, the tree's nodes' AABBs, and one node selected:

You can clearly see that the AABB for the highlighted node contains a lot of empty space. In general, this is because, during creation, at node split time, the parent's AABB is split into two by an axis-aligned plane at whatever location is found to be optimal, and each child gets one of the two resulting AABBs.

I added a step to the splitting procedure that, after the steps above, reduces the size of each child's AABB such that its min/max extents in all axes are reduced to the min/max AABB extents of its shapes. Note that the node's AABB is never expanded, so it's still possible to have shapes partially outside the node's AABB.

Here is the same node selected with reduction turned on:

I see a slight improvement in performance, since the probability of an arbitrary ray hitting a given node's AABB is now less, since the AABB is smaller.

My question is, is there any disadvantage to doing this?

Answer 1

No disadvantage that I can see but what you have is not a kd-tree if you have axis-aligned bounding boxes in every node.

A kd-tree only has a splitting plane in every node, so there is no AABB to shrink. The way to deal with empty space in them is to split the node further into an empty node and a smaller node with the same objects as its parent, when justified by whatever heuristic is used. It is just one more possible split to consider when picking how to split a node.