Graphics Reference
In-Depth Information
for(inti=0;i<8;i++) {
// See if the ith child exist
if (pTree->hasChildK & (1 << i)) {
// Compute new Morton key for the child
int key = (pTree-
>
key << 3) + i;
// Using key, look child up in hash table and recursively visit subtree
Node *pChild = HashTableLookup(gHashTable, key);
VisitLinearOctree(pChild);
}
}
}
A hashed octree similar to this is described in [Warren93].
7.3.5
Computing the Morton Key
Given three integer values representing the
x
,
y
, and
z
coordinates of an octree leaf,
the corresponding Morton key can be computed by the following function.
// Takes three 10-bit numbers and bit-interleaves them into one number
uint32 Morton3(uint32 x, uint32 y, uint32 z)
{
// z--z--z--z--z--z--z--z--z--z-- : Part1By2(z) << 2
// -y--y--y--y--y--y--y--y--y--y- : Part1By2(y) << 1
// --x--x--x--x--x--x--x--x--x--x : Part1By2(x)
// zyxzyxzyxzyxzyxzyxzyxzyxzyxzyx : Final result
return (Part1By2(z)
<<
2) + (Part1By2(y) << 1) + Part1By2(x);
}
The support function
Part1By2()
splits up the bits of each coordinate value,
inserting two zero bits between each original data bit. Interleaving the intermedi-
ate results is then done by shifting and adding the bits. The function
Part1By2()
can
be implemented as:
// Separates low 10 bits of input by two bits
uint32 Part1By2(uint32 n)
{
// n = ----------------------9876543210 : Bits initially
// n = ------98----------------76543210 : After (1)
// n = ------98--------7654--------3210 : After (2)
