Graphics Reference
In-Depth Information
in a balanced tree. The median cut is just one possible strategy. Going back to the list
of desired properties given earlier, other possible partition strategies are:
●
Minimize the sum of the volumes (or surface areas) of the child volumes.
The proba-
bility of an intersection between a bounding volume and either of the two child
volumes can be expected to be proportional to their volume. Thus, minimiz-
ing the sum of the volumes effectively minimizes the likelihood of intersection.
For a ray query, the probability of a ray striking a bounding volume is instead
proportional to the bounding volume's surface area.
●
Minimize the maximum volume (surface area) of the child volumes.
Whereas the
previous strategy can result in one volume much larger than the other, this
approach attempts to make the volumes more equal in size by making the larger
volume as small as possible. This results in a more balanced query, improving
worst-case behavior.
●
Minimize the volume (surface area) of the intersection of the child volumes.
This
strategy helps decrease the probability of both children being overlapped and
traversed into. Depending on the bounding volume used, the intersection can
be complex to construct and even to approximate.
●
Maximize the separation of child volumes.
Separating children, even when
not overlapping, can further decrease the likelihood of both children being
traversed into.
●
Divide primitives equally between the child volumes.
This strategy is the median-
cut algorithm mentioned at the start of the section. Its strength lies in giving
the most balanced hierarchy possible.
●
Combinations of the previous strategies.
Partitioning stops and a node is considered a leaf when some particular stop
criterion is reached. Common stop criteria are:
●
The node contains just a single primitive, or less than some
k
primitives.
●
The volume of the bounding volume has fallen below a set cut-off limit.
●
The depth of the node has reached a predefined cut-off depth.
Partitioning can also fail early, before a stop criterion triggers, for instance when:
●
All primitives fall on one side of the split plane.
●
One or both child volumes end up with as many (or nearly as many) primitives as the
parent volume.
Both child volumes are (almost) as large as the parent volume.
●
