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

[Darren G. <dg...@ke...>]

At 09:40 AM 6/5/2008, Marc B. Reynolds wrote:


> > In what order are the nodes stored this way?
>
>What I did in my test was to take the 3D coordinate of a node, convert it to
>a Hilbert index and used the (sorted) Hilbert-indices to layout the memory.
>There are probably MUCH better methods.
>
>Conceptually, you layout memory as a Hilbert curve walk of the space would
>'touch' the node in question. Well, actually there is no reason to restrict
>to Hilbert...let's say some space-filling curve. I'm thinking that, say a
>Morton curve might be better for dynamic trees.


Great experiment!

I would love to know if the z-order curve just works better across 
the board with the octrees.


Regards,
Darren