Bounding Volume Hierarchies - Real-Time Collision Detection - page 237

Each node in the hierarchy should be of minimal volume. ●

● The sum of all bounding volumes should be minimal.

● Greater attention should be paid to nodes near the root of the hierarchy. Pruning a
node near the root of the tree removes more objects from further consideration
than removal of a deeper node would.

● The volume of overlap of sibling nodes should be minimal.

● The hierarchy should be balanced with respect to both its node structure and its
content. Balancing allows as much of the hierarchy as possible to be pruned
whenever a branch is not traversed into.

For real-time applications, games especially, an important addition to the previous
list is the requirement that the worst-case time for queries not be much worse than
the average-case query time. This requirement is particularly important for console
games, for which a fixed frame rate is usually required (typically 60 fps).
Additionally, it is desired that the hierarchy can be automatically generated without
user intervention. For real-time applications, most hierarchies are usually generated
in a preprocessing step and not at runtime. For games, excessive waiting for precom-
puted structures to build can have a detrimental impact on level construction and
design. Therefore, although precomputation makes the construction less time signif-
icant algorithms of quadratic complexity and above are still likely to be too slow even
for preprocessing use. If a hierarchy is constructed at runtime, building the hierarchy
should also pay for itself in that the time taken for construction should be less than
the time saved by using the hierarchy.
Finally, a very important factor often glossed over in treatments of collision detec-
tion is the total memory requirement for the data structures used to represent the
bounding volume hierarchy. For example, console games roughly allocate a tenth
of the available memory for collision data. Whereas the built-in memory for next-
generation console systems will increase for each generation, the ratio allocated for
collision detection data is likely to remain roughly constant because the memory
requirements for other systems (such as rendering, animation, and AI) also are likely
to grow proportionally. These memory constraints set hard limits on all considered
collision detection systems.

6.1.2 Cost Functions

Several people have come up with expressions to identify the various parts con-
tributing to the expected cost of bounding volume hierarchy queries. A cost formula
first presented in [Weghorst84] and adapted for bounding volume hierarchies by
[Gottschalk96] and subsequently refined in [Klosowski98] and [He99] is

T = N V C V + N P C P + N U C U + C O .