Help me understand quadtree traversal!

[MutantJohn]

I'm currently reading "Simple and Efficient Traversal Methods for Quadtrees and Octrees" by Frisken and Perry.

I'm currently looking at their code and I dig the way they built their structure.

typedef struct _qtCell {

    unsigned int xLocCode;
    unsigned int yLocCode;
    unsigned int level;

    struct _qtCell *parent;
    struct _qtCell *children;

    void *data; //generic data pointer    
} qtCell;

#define QT_N_LEVELS 16 // Number of possible levels in the quadtree
#define QT_ROOT_LEVEL 15 // Level of root cell (QT_N_LEVELS - 1)
#define QT_MAX_VAL 32768.0f // For converting positions to locational codes

/* Macro to traverse a quadtree from a specified cell (typically the root cell) to a leaf cell by following the x and y locational codes, xLocCode and yLocCode. Upon entering, cell is the specified cell and nextLevel is one less than the level of the specified cell. Upon termination, cell is the leaf cell and nextLevel is one less than the level of the leaf cell. */

#define QT_TRAVERSE(cell, nextLevel, xLocCode, yLocCode) {

    while (cell->children) {

       unsigned int childBranchBit = 1 << nextLevel;
       unsigned int childIndex = ((xLocCode & childBranchBit) >> nextLevel) + ((yLocCode & childBranchBit) >> (--nextLevel));

       cell = &((cell->children)[childIndex]);
    }
}

I finally looked up what the bitwise AND operation but I'm still confused about this code. I get that childBranchBit is logically equivalent to some 2^n but the child index is what I'm totally stuck on.

So we compare xLocCode and childBranchBit and get the net bits they have in common and we right shift those bits by nextLevel. We then add this to yLocCode's and childBranchBit's common bits which are then right shifted by one less than x's common bits.

I'm imagining that the index of each child would go from 0 to 3. Does this code actually give me a number from 0 to 3 or am I thinking of this wrong?

Also, I don't get the last line. Is cell a pointer or the struct itself? Are we supposed to assume that we have qtCell cell or is it qtCell *cell?

I'm guessing it's the first but I'm just lost on all this bit math. T_T

[oogabooga]

Does this code actually give me a number from 0 to 3

Yes, that's right. It just puts a one or a zero into the lowest two bit locations, which makes a number from 0 to 3.

Is cell a pointer or the struct itself?

Since it's being dereferenced as a pointer in the first line and assigned an address in the last line, it must be a pointer.

[MutantJohn]

Lol thank you for your response. I actually copied the code and noticed that yeah, it was only affecting the first two bit locations as it went from 14 to 14 - 14 = 0 and 14 - 13 = 1 so it's bit 0 and bit 1 which are the first two. Very neat code, actually. If I need help actually building and navigating this tree then I'll be sure to come back.