[dahart]

What does Z-ordering mean in this context?

I definitely want to avoid swap at all costs and find things that are designed to tile & stream instead. The difference between GraphicsMagick resizing an image by streaming and ImageMagick resizing an image that hits swap is orders of magnitude - seconds versus hours.

[phkahler]

>> What does Z-ordering mean in this context?

You divide the image into quarters and store each quarter as a continuous block of memory. Do this recursively.

Normally we'd index into the pixel data using pixel[x,y]. You can get Z-ordering by using pixel[interleave(x,y)] where the function interleave(x,y) interleaves the bits of the two parameters.

This works fantastically well when the image is a square power of two, and gets terrible when it's one pixel high and really wide. I think a combination of using square tiles where each one is Z-ordered is probably a useful combination.

For my ray tracer I use a single counter to scan all the pixels in an image. I feed the counter into a "deinterleave" function to split it into an X and Y coordinate before shooting a ray. That way the image is rendered in Z-order. That means better cache behavior from ray to ray and resulted in a 7-9 percent speedup from just this one thing.

Once you have data coherence, swapping is not a big deal either in applications where you're zoomed in.

[tripzilch]

> You can get Z-ordering by using pixel[interleave(x,y)] where the function interleave(x,y) interleaves the bits of the two parameters.

That is pretty cool (also the raytracing application), but most surprising to me, is I remember the interleave operator from reading the INTERCAL[0] docs ... I never even considered the function could actually be applied to something useful :-)

[0] one of the early esoteric programming languages, designed to be "most unlike any other language". It also features a "COME FROM" statement (because GOTO is considered harmful), which iirc also actually has a parallel in some modern programming paradigm.