Re: [Algorithms] Cache-oblivious layout (was: BSP tree, or what?)

[Mark D. <duc...@ll...>]

Typically the other space-fill curves are computed efficiently
as you traverse your hierarchy, i.e. simple arithmetic as
you move down different branches of a tree.  If you are
randomly accessing elements, then some caching and look-up
of the indices is usually used to speed this up.  This overhead
is okay if you have fairly large payloads at each hierarchy node,
but is a problem for really light-weight nodes.  For swizzles
on texture hardware, this is obviously a non-starter.

Cheers,

--Mark D.

Tom Forsyth wrote:
> Morton order is otherwise known as "Z-swizzle". You take the coordinates and
> interleave the bits. So if you have standard X and Y coordinates with bits
> x31,x30,x29,...,x2,x1,x0 and y31,y30,y29,...,y2,y1,y0 then the Morton
> coordinate is simply y31,x31,y30,x30,y29,x29,...,y2,x2,y1,x1,y0,x0. There's
> an obvious extension to higher dimensions.
> 
> http://en.wikipedia.org/wiki/Z-order_(curve)
> 
> There's also a bunch of different variations that don't interleave all the
> bits, just some of them, or interleave blocks of 2 or 4 bits at a time,
> rather than a fine 1:1 interleave (e.g.
> ...,y7,y6,y5,y4,x7,x6,x5,x4,y3,y2,y1,y0,x3,x2,x1,x0). They all trade lower
> computational cost for slightly lower efficiency - pretty easy to experiment
> with.
> 
> If I ever knew the trick to generating Hilbert ordering easily, I've
> forgotten it :-(
> 
> TomF.