But the situation changes when a partitioning scheme is introduced. Under partitioning, the bunny is first subdivided into left and right halves. When the time comes to intersect-test one of the inbound rays against the bunny, we no longer naïvely test the ray against each of the polygons in the bunny. Instead, we first test the inbound ray against the bounding box (in this case, a rectangular prism) that encloses the left half of the bunny. If the ray doesn’t intersect the bounding box, then it cannot intersect any of the polygons contained it. This enables us to exclude all of the polygons on the left-hand side of the bunny from further intersect testing.
But what if the ray does intersect the left-hand bounding box? In this case, we progressively partition the bunny at a finer granularity. We do this by dividing the left half of the bunny into left-top and left-bottom quarters (the left-top quarter-bunny volume is shaded red in the figure). Since we know the inbound ray intersects the left half bounding box, it must in turn intersect either the left-top quarter bounding box or the left-bottom quarter bounding box, but not both. Once again, this enables us to exclude all of the polygons within whichever box the ray does not intersect from further intersect testing.
Under ideal conditions, partitioning schemes enable us to reduce the complexity of the intersect test operation by half at each partitioning step. Indeed, if we are lucky enough to possess an object that has been perfectly partitioned all the way down to the granularity of individual polygons, we can intersect test that object in O(n) = log n time complexity per ray—a massive improvement over the linear time complexity of the naïve approach.
Unfortunately, the logarithmic time complexities described in the preceding section are almost impossible to achieve in practice. The chief reason for this is easily understandable: real 3D models can rarely be partitioned perfectly. For example, when the bunny model in the figure above is partitioned uniformly into quarters, the entire right-top quarter is empty. Because this quadrant is empty, a failed intersect test against it doesn’t exclude any polygons from further testing, and as a result, we gain no increase in performance from this partitioning step.
Under whichever partitioning scheme we use, some objects will partition better than others. And this disparity in partitioning performance has important consequences in parallelization, since disparities in partitioning performance equate directly to disparities in time and work. For example, consider two rays r1 and r2 fired into different parts of a 3D environment. Simple testing reveals that ray r1 may intersect object o1 and that ray r2 may intersect object o2, so we now need to perform detailed, polygon-level intersect testing. Let us say that both o1and o2 contain roughly the same number of polygons—about 15,000. But in spite of being of similar size, o1 and o2 react to partitioning very differently. Let’s say that object o1 partitions almost perfectly, whereas object o2 barely partitions at all. This leads us to a situation in which ray r2 may require almost 15,000 intersect tests—owing to the ineffectual partitioning of object o2—whereas ray r1 requires only log2 15,000 ≈ 14 intersect tests. So despite the objects hit by both rays being of similar size, intersect testing one ray requires a thousand times more work than does intersect testing the other.