Tesseral arithmetic/quadtree

Question

I did a project a while back on path finding with quadtrees and I would like to improve on its performance. It seems that using tesseral arithmetic to determine node adjacency (as per this page, courtesy of the Geography department of the University of British Columbia) would be much faster than the brute force method I'm using at the moment (I'm checking for shared edges, which works fine for a static quadtree but would be too much overhead if the map were changing).

I more or less understand what's said in the Adjacency Algorithm section, but I'm not really sure how to begin. I'm primarily interested in C#, but it'd be awesome if there's already some source floating around for working with tesseral arithmetic that I could look at, regardless of language. Otherwise, could anyone give me some pointers on dealing with the addition/subtraction carries?

Sylvie

I just thought of a much better way. Yes a bit late, I know. Should be a lot better than unzipping a rezipping, too. – Inseverable

Answer 1

I think, the easiest way to deal with tesseral arithmetic is to "bit-unzip" numbers, perform any number of arithmetical operations normally, and "bit-zip" them back when tesseral form is needed:

z = bit_zip(bit_unzip(x) + bit_unzip(y));

(This example works for unsigned only. For signed integers, unpack each number into two variables and do normal arithmetic on both parts separately).

You can find fast implementations for "bit-unzip" and "bit-zip" in "Matters Computational ", chapter 1.15 "Bit-wise zip".

Oration

I'm not sure I follow this; does interleaving the bits bypass the need to manually carry the digit? I've not had much experience with interleaving and the site I referenced only briefly mentioned it, so if this is the case, could you point me towards a primer on interleaving and its uses? – Sylvie

Yes, deintereaving the bits bypasses the need of manual carry because it transforms tesseral representation to the cartesian representation which allows normal arithmetic calculations. Bit interleaving is also used in polynomial arithmetic and in computer graphics (z-order). Possibly there are other uses. "Matters Computational" gives pretty good explanation for interleaving, its uses and implementations. This article adds a little bit more information. – Oration

And this article explains tesseral addressing and its relation to interleaving. – Oration

So, another question; do you know of a modification of one of the bit-shuffling algorithms that allows one to shuffle only a portion of a word? For example, with a third level node, the address would be 6 bits (of, say a 64 bit word). To shuffle only the lowest 6 bits...? – Sylvie

Edit: I looked at the source code provided in your Bit Permutations link, but it seems that subwords can only have lengths of 2^n bits. That's the most similar I've seen to what I'm looking for, though. – Sylvie

Probably I don't fully understand this last question... If you need only 6 bits, why not shuffle all 64 bits, but use only 6 of them? You can mask 6 bits out of others: z=bit_unzip(x&63). In this case, it is also possible to shuffle bits with simple array indexing: z=unzipTable[x&63]. – Oration

Sorry, I was a bit sleep deprived when I asked that, so I made a mess of it. Shuffling isn't really the issue; shuffling the entire word and then only concerning myself with the lower bits will work fine. What is a good way of comparing a specific number of bits in one word to another? For example, how would one differentiate between the level one address 0 and the level four address 0000? Is there a better way than keeping a level variable? – Sylvie

A good way of comparing a specific number of bits is a bitmask: address&((1<<numberOfBits)-1). Keeping a level variable is the simplest way to do it. Is there a better way or not - it depends on your application, I cannot know it. – Oration

Cool, I think I'm about ready to try this out. Thanks for your help! – Sylvie

Answer 2

Well, I don't know of any way to do this efficiently, but the usual "add with bitwise operations" algorithm suggests the following algorithm (not tested):

static int tesseral_add(int x, int y)
{
    int a, b;
    do
    {
        a = x & y;
        b = x ^ y;
        x = a << 2; // move carry up 2 places instead of the usual 1
        y = b;
    } while (b != 0);
    return b;
}

Which possibly loops quite a lot, if there are carry chains.

---

Actually, there's a much better way to do this.

Observe that for z = interleave(a, -1); w = interleave(b, 0);, adding z and w directly gives a partially correct result, because any carries are re-carried (all the "in-between" bits are 1). The only "problem" is that it destroys the y-coordinates.

So to add two tesseral numbers z = interleave(a, b); w = interleave(c, d);, there is a nice short way to do it:

int xsum = (z | 0xAAAAAAAA) + (w & 0x55555555);
int ysum = (z | 0x55555555) + (w & 0xAAAAAAAA);
int result = (xsum & 0x55555555) | (ysum & 0xAAAAAAAA);

Inseverable