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

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

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.


> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...] On Behalf Of
> Jeff Russell
> Sent: Friday, June 06, 2008 12:03 PM
> To: duc...@ll...; Game Development Algorithms
> Subject: Re: [Algorithms] Cache-oblivious layout (was: BSP tree, or
> what?)
> 
> All very interesting,
> 
> Does anyone have a link or example of how to quickly do a morton or
> hilbert lookup?
> 
> -Jeff
> 
> On Fri, Jun 6, 2008 at 12:40 PM, Mark Duchaineau <duc...@ll...>
> wrote:
> > My colleagues Sung-Eui Yoon and Peter Lindstrom did a very
> > thorough study of various cache-efficiency metrics for
> > a variety of space-filling variants in a paper
> > "Mesh Layouts for Block-Based Caches" from IEEE Vis 2006,
> > pdf here:
> >
> > http://www.cc.gatech.edu/~lindstro/papers/blockcache/paper.pdf
> >
> > Looks like some special variants on Hilbert and a block
> > interpretation of Sierpinski do very well, depending on the
> > way you define efficiency (will vary by application requirements
> > a bit, in other words).
> >
> > Cheers,
> >
> > --Mark D.
> >
> > Daniel Vollmer wrote:
> >> On Jun 6, 2008, at 01:07 , Tom Forsyth wrote:
> >>
> >>
> >>>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.
> >>
> >>
> >> I'd agree with Tom's gut impression. :)
> >>
> >> For a wavelet image compression algorithm (shameless plug:
> http://www.maven.de/code/wavelet/)
> >>   I went with Morton / Z first, and then later on went ahead and
> >> implemented a Hilbert curve variant. The Hilbert curve gave
> slightly,
> >> but consistently better results (i.e. smaller images) which means it
> >> extracted locality better than the other space-filling curves, and
> as
> >> I stored the curve in a table anyhow the computational cost was
> >> irrelevant. Of course, there were also cases where the Morton curve
> >> fared better, but they were very much in the minority (and from and
> >> Information Theory viewpoint they *have* to exist).
> >> The above-linked code has a nice, self-contained 2D Hilbert Curve
> >> generation (which gets optimized to a simple loop due to tail-
> >> recursion), which is quite easy to extend to 3D (as was done in the
> >> paper referenced in the source).
> >>
> >>
> >>       Daniel.
> >>
> >> --------------------------------------------------------------------
> -----
> >> 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
> >>
> >
> > ---------------------------------------------------------------------
> ----
> > 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
> >
> 
> -----------------------------------------------------------------------
> --
> 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