Graphics Reference
In-Depth Information
It is of course possible to combine this representation with previous methods. For
instance, storing a tri-node tree in preorder traversal order with parent-relative offsets
instead of child pointers would reduce the memory used for links to a minimum.
A related technique is discussed in [Intel99], in which instead of a single sphere
bounding volume the union of three spheres is used as the bounding volume, as
three spheres fit nicely within a cache line.
6.6.5 Tree Node and Primitive Ordering
When, say, a simultaneous traversal is used four recursive calls are generated in
the node-node part of the traversal algorithm. As the algorithm was presented in
Section 6.3.3, the order in which these four calls were issued was completely deter-
mined by the relative ordering of the nodes within the two trees. If the current
query is for testing rather than finding collision, or if distance pruning is used to
cull away branches of the hierarchies, it is desired to find intersections as early as
possible.
One possibility would be to attempt to figure out at runtime the best order in which
to issue the recursive calls. This is not necessarily easy, as nothing is known about
the structure further down the hierarchies at this point. A more feasible alternative
(with no runtime overhead) is to rearrange the children of a parent node heuristically
during construction, so that the child more likely to lead to an early intersection
comes first. Following [Haines91a], a few possible ways to order the nodes (for not
necessarily binary trees) include:
Arrange children so that leaves come before nodes. If the collision status is deter-
mined at the primitive level, as all primitives are contained in the leaves, by
having the leaves come before nonleaf nodes primitives are tested as early as
possible.
Put the smallest subtrees first. By considering the nodes as roots of hierarchy
subtrees, the same argument applies. By having nodes with fewer descendants
first, leaves should be reached earlier.
Sort children by their hits-to-tests ratio. Based on actual usage, rearrange the
hierarchy so that nodes actually involved in positive collision queries come first
and those never or rarely involved come last.
Sort children from near to far along predominant query direction. If tests are coming
predominantly from a specific direction, such as from above for a hierarchy
representing ground, it makes sense to sort children so that those corresponding
to higher ground come first.
The same ordering principle applies to the primitives stored within a leaf, of
course. When the leaf contains more than one primitive, the primitives can be sorted
Search WWH ::




Custom Search