problem with quadTree & union

Question

hi!

i have the following quadtree-like structure, in which each cell can either be a inner node or a leaf. if it is a leaf, it can store a color. if it is a inner node, it stores pointers to four children (which can be either leaf or inner node):

class RenderBucketCell{
public:
    RenderBucketCell();
    RenderBucketCell(float R, float G, float B, float A, unsigned short X, unsigned short Y);
    ~RenderBucketCell();

    void split();

    void collapse();

    bool isLeaf;
    RenderBucketCell* neighbours[8];
    unsigned short x;
    unsigned short y;
    union{
     struct{
      float r;
      float g;
      float b;
      float a;
     };
     struct{
      RenderBucketCell* children[4];
     };
    };
};

if the cell is is an inner node, then it doesn't need to store a color. if it's a leaf, then it doesn't need to store pointers to children. therefore the color and the children shall share the same memory (union)

there is the function split() which transforms a leaf into a inner node and creates for children (leafs) with the same color the current cell has at the moment:

void RenderBucketCell::split(){
isLeaf=false;
float rt = r;//make backups of the values before setting the children (union)
float gt = g;
float bt = b;
float at = a;
unsigned short xt2 = x*2;
unsigned short yt2 = y*2;
children[0] = new RenderBucketCell(rt,gt,bt,at, xt2, yt2);
children[1] = new RenderBucketCell(rt,gt,bt,at, xt2+1, yt2);
children[2] = new RenderBucketCell(rt,gt,bt,at, xt2, yt2+1);
children[3] = new RenderBucketCell(rt,gt,bt,at, xt2+1, yt2+1);
}

now i'm debugging the function split(). i set a debug point on the line

children[0] = new RenderBucketCell(rt,gt,bt,at, xt2, yt2);

so now: the debugger stops at this line and i observe the membervalues. i do a procedurestep, such that the line gets executed (the instruction cursor is now on the next line). After the line has been executed, the pointervalue of children[0] is still the same! instead, the pointervalue of children[2] has changed (along with the float value b)

can someone explain me this behaviour?? what am i doing wrong?

Thanks!

Answer 1

This is more than likely a problem with using a union. children[2] is the first un-assigned memory location that the compiler has given to the union (assuming 4 byte floats and 8 byte pointers). I'm not sure why it's happening, but problems like this are one of the main reasons why unions aren't advisable structures.

Answer 2

I solved your problem (a node can have either pointers or data) by giving the node four unsigned long's. When the node is a child node, those unsigned longs are cast to floats. And when it's a parent node they store the address of the children.

However, you have to be absolutely sure you want to use this optimization, because it becomes a nightmare to debug.

Answer 3

the value of children[0] being the same isn't all that surprising, as the memory will probably be partitioned in a very similar manner each time you run the program, i.e. the value in memory at children[0] will still be there from the previous run, and "operator new" will probably just retrieve the memory that was used last time. That's my guess for what's happening there.

As for children[2], I'm not entirely sure. The only thing I can think of is something with the constructor.

Answer 4

You are using something that could be called an "anonymous struct" within your union. I don't believe these are part of the C++ standard, although I've read some compilers support them. In all cases, I would stay clear of these and use the following:

union{
        struct {
                float r;
                float g;
                float b;
                float a;
        } color;
        struct {
                RenderBucketCell* children[4];
        } subnode;
};

Your code is going to be slightly more verbose as you have to refer to renderBucketCell.color.r instead of renderBucketCell.r, but it could solve your problem.