Graphics Reference
In-Depth Information
// Separate bits of 32-bit value by one, giving 64-bit value
uint64 t = Part1By1_64BitOutput(xy);
// Interleave the top bits (y) with the bottom bits (x)
return (uint32)((t >> 31) + (t & 0x0ffffffff));
}
In general, for the 2D case just presented, handling n -bit inputs would require
4 n -bit numbers being available in the intermediate calculations.
7.3.6 Loose Octrees
Consider again the problem of objects becoming stuck high up in a dynamic octree due
to straddling of the partitioning planes. An effective way of dealing with this problem
is to expand the node volumes by some amount to make them partially overlapping
(Figure 7.13). The resulting relaxed octrees have been dubbed loose octrees [Ulrich00].
The loose nodes are commonly extended by half the side width in all six directions
(but may be extended by any amount). This effectively makes their volume eight times
larger.
Assuming spherical objects, the objects are propagated into the child node in which
the sphere center is contained. Only when the sphere extends outside the loose cell
would it remain at the current level.
With these larger nodes, objects now descend deeper into the tree, giving the parti-
tioning more discriminatory power. Unfortunately positioned but otherwise pairwise
distant objects that previously became stuck high up in the tree are less likely to
have to be tested against other objects. Another benefit of the loose nodes is that the
(a)
(b)
Figure 7.13 (a) The cross section of a regular octree, shown as a quadtree. (b) Expanding the
nodes of the octree, here by half the node width in all directions, turns the tree into a loose
octree. (The loose nodes are offset and shown in different shades of gray to better show their
boundaries. The original octree nodes are shown as dashed lines.)
Search WWH ::




Custom Search