Game Development Reference
F IGURE 12.5
Insertion hierarchy building in action.
Each algorithm has many variations. In particular, the exact criteria used to group
nodes together has a large effect on the quality of the tree. The bottom-up approach
generally searches for nearby objects to group; the top-down approach can use any
number of clustering techniques to split the set; and the insertion approach needs to
select which child would be best to recurse into at each level of the tree. The specifics
of the tradeoffs involved are complex, and to get the optimum results they require a
good deal of fine-tuning and experimentation.
Fortunately even a simple implementation will give us a reasonable-quality tree
and a good speed-up for the coarse collision detector. For our implementation I have