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

[Tom F. <tom...@ee...>]

After experience with Morton vs Hilbert in a bunch of areas (rasterization,
texture storage, vertex caching, etc), my gut feeling is that a Hilbert
curve very rarely gives a worse cache-traversal pattern than Morton. Note
the very precise statement! However, it can be a pain to implement (whereas
Morton is pretty trivial), and whether it's actually a significant *win*
depends a lot on a bazillion things. Fairly obviously for very sparse data,
there's no coherence to be extracted, and neither is significantly better
than completely random, in which case you should implement the simplest
thing possible (usually linear).

TomF.


> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...] On Behalf Of
> Darren Grant
> Sent: Thursday, June 05, 2008 2:03 PM
> To: Game Development Algorithms; 'Game Development Algorithms'
> Subject: Re: [Algorithms] Cache-oblivious layout (was: BSP tree, or
> what?)
> 
> 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
> 
> 
> -----------------------------------------------------------------------
> --
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://sourceforge.net/services/buy/index.php
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-
> list