adruab.net Deep internal/external searching… for… stuff

Complete Trees

Complete trees are cool. Best part is the closed form for parent/child indices. I had to rederive these equations for a complete quad tree today. It didn't take as long as I was expecting. Here they are if you care...

parent(i) = (i - 1) / 4

child_j of i = (i * 4) + j + 1

It turns out a level of a specific depth has a closed form too. The numbers are 0b, 1b, 101b, 10101b and so on.

level 0 start = 0

level n > 0 start = ((1 << ((n - 1) * 2 + 1)) - 1) & 0x5555555

Essentially this gives you multiples of 4. 1,2,3,4 map to 2^1, 2^3, 2^5, 2^7. Subtracting 1 gives you 1b, 111b, 11111b, 1111111b. Then anding with 0x55555555 should give you the 101010101 pattern.

The main gotcha here is that access to a single group of siblings is swizzled from normal xy access. Once that's done though, you're golden.

And the engine goes…