Testing a ray against every object in a scene one at a time is O(n) per ray -- workable for a handful of objects, hopeless for the millions a real ray tracer needs. A BOUNDING VOLUME HIERARCHY (BVH) fixes this: a binary tree where every node stores an axis-aligned bounding box (AABB) enclosing everything beneath it. Tracing a ray means walking the tree and -- the entire point of the structure -- SKIPPING any subtree whose own bounding box the ray doesn't even hit, without looking at a single object inside it.

ray_intersects_aabb (the slab test) and small AABB helpers are given -- this exercise is about construction and traversal, not ray/box math.

Implement:

• build_bvh(objects, leaf_size=2) -- objects is a list of (object_id, bounds). If len(objects) <= leaf_size, return a leaf node (objects = every item given, bounds = their union). Otherwise: compute the bounding box of every object's CENTROID, find its longest axis, sort objects by centroid on that axis, split the sorted list at len // 2, recursively build each half, and return an interior node (bounds = union of the two children's bounds).
• intersect_bvh(node, origin, direction, counter=None) -- return the list of object_ids whose bounds the ray actually intersects. Test a node's own bounds first; if the ray misses, return immediately WITHOUT recursing into its children. At a leaf, test each individual object's bounds (not just the leaf's aggregate bounds).

Example

objects = [("a", (0,0,0, 1,1,1)), ("b", (5,5,5, 6,6,6)), ("c", (10,10,10, 11,11,11))]
root = build_bvh(objects, leaf_size=2)
intersect_bvh(root, origin=(-1,0.5,0.5), direction=(1,0,0))   # -> ["a"]

Constraints

• The split axis is recomputed at every node (it can differ between a node and its children).
• Every object appears in exactly one leaf.
• A subtree whose bounds the ray misses must contribute NO further ray_intersects_aabb calls beyond the single test on that subtree's own root -- this is what the test suite checks to confirm real pruning is happening, not a disguised linear scan.

Real-world grounding

• mmp/pbrt-v4's BVH aggregate builds exactly this kind of tree -- recursively splitting by the longest axis of the primitives' centroid bounds (its Middle and EqualCounts split methods; pbrt's default SAH split additionally weighs surface area, which this exercise's simpler equal-counts split leaves out): src/pbrt/cpu/aggregates.cpp (see BVHAggregate::buildRecursive, in particular the dim = centroidBounds.MaxDimension() axis choice and the SplitMethod:: EqualCounts branch).
• The pbrt book itself -- pbrt-v4 is literally its reference implementation -- covers this construction and the traversal pruning rule in depth: Physically Based Rendering, "Bounding Volume Hierarchies".

Real pbrt additionally offers a Surface Area Heuristic (SAH) split (a cost model that usually builds a better tree than a plain equal-counts median split) and an HLBVH mode for very large scenes -- this exercise implements the equal-counts variant, which is simpler but shares the exact same pruning payoff on traversal.