Generating a Quadtree this way

D.V.D

Make a wish
Reaction score
73
Hey guys, Im working on generating a quadtree by using a bottom up traversal. The idea is that I first make all my leaf nodes, add in the color value of the image I want to store inside my quadtree, then I start making higher and higher levels by using the nodes before it as a basis to create the tree. If the 4 children making up a node have the same color, then they are deleted since the structure is supposed to be sparse. The thing I want to check to see is if this is how I should code my builder and if it doesn't leak a whole bunch.

The quadtree itself is simple, here is the class and its constructor:

Code:
    struct Quadtree
    {
        uint32_t average;
        uint16_t length_x;
        uint16_t length_y;
        uint8_t level;
        Quadtree * parent;
        Quadtree * children;
 
        Quadtree () {}
        Quadtree (Quadtree * children);
        ~Quadtree ();
    };
 
    Quadtree::Quadtree (Quadtree * _children)
    {
        children = new Quadtree [4];
        children = _children;
 
        level = children[0].level--;
 
        length_x = children[0].length_x << 1; // multiply by 2 (2*1)
        length_y = children[0].length_y << 1;
 
        if ( children[0].average == children[1].average && // If all children nodes are the same, delete them (sparse quadtree)
            children[1].average == children[2].average &&
            children[2].average == children[3].average )
        {
            average = children[0].average;
            delete[] children;
        }
        else
        {
            average = (children[0].average + children[1].average + children[2].average + children[3].average) >> 2; // divide by 4 (2*2)
        }
    }
 
    Quadtree::~Quadtree ()
    {
        delete[] children;
    }



Since a quadtree grows exponentially, I can always multiply my side lengths by 2 (left shit by 1) to get the next node above its side lengths. The if statement simply checks to see if all children are the same and the else simply gets the average color.

The part Im worried about is the building function. I made it as a normal function outside the class since I don't start from the root of the quadtree so I don't have the master class until the whole building process is done. Here's the code:

Code:
Quadtree* build (unsigned int * Image_Pixels)
    {
        uint8_t level = 15;
        uint32_t count = sizeof(*Image_Pixels);
        Quadtree * prev_nodes = new Quadtree [count];
 
        for ( uint32_t i = 0; i < count; i++ )
        {
            prev_nodes->average = Image_Pixels[i];
        }
 
        while (level < QT_N_LEVELS)
        {
            level --;
            count >> 1; // Divide by 2
            Quadtree * nodes = new Quadtree [count];
            count <<= 2;
 
            for ( uint32_t i, j = 0; j < count << 2; i++, j+=4 )
            {
                Quadtree * children = new Quadtree [4];
                children[0] = &prev_nodes[j];
                children[1] = &prev_nodes[j+1];
                children[2] = &prev_nodes[j+2];
                children[3] = &prev_nodes[j+3];
                nodes[i] = Quadtree (children);
            }
 
            if ( count == 1 )
            {
                return nodes;
            }
 
            prev_nodes = nodes;
 
        }
    }

The way its done is a pointer to a list of Quadtree nodes is generated. It begins with the leaf nodes which are outside of the loop. Each pixel is inserted into these leaf nodes and then when the loop runs, a new pointer to a list of Quadtrees is created. This one is one level higher and in the for loop, we merge together the nodes before it to generate the next node using the constructor above. The list to the leaf nodes (prev_nodes) is then set to the newly created level and the loop continues until we reach either level 0 (the root) or we only have one node left which is in any case, the root.

The Quadtree root would keep the pointers to the all these newly created node lists but would I leak significantly by approaching this problem this way? It seems viable since I transfer the addresses of the newly created nodes to the Quadtree structure itself so although the list of pointers to these nodes are gone, the Quadtree keeps its own pointers to that I don't leak. Would that be correct however, with how I wrote my program right now?

(BTW sorry for all the right/left shifts, just learned the bit operators so I want to use them as much as possible to get more used to their concept).
 

monoVertex

I'm back!
Reaction score
460
I can't see any leak. Make sure to clear everything up when the program closes, though.

Also, the ImagePixels you're passing as parameters, you're clearing up those, right?

Now, 3 things:
  • Why don't you consider your nodes with level 0 and increase the level as you go up? It's more logical that way and you can always compute the total size of the tree from the root this way. I have a quadtree in a terrain generation project as well and that's how I did it.
  • You have this division inside the while:
    Code:
    count >> 1; // Divide by 2
    Is it doing anything? You have to assign it to something. 2 lines down, you multiply the count.
  • Don't worry about using bit shifting, it's good and it's faster.
 

D.V.D

Make a wish
Reaction score
73
Okay, well ImagePixels will be a pointer to the pixels of a SDL surface so once the surface is cleared, the pointers data should be too. I assume the destructor will properly destroy the Quadtree structure.

I'm not sure, this is the first time someone told me to do it that way. I learned it the opposite way but usually I won't know how deep the tree should be so I guess that's why.

The division is important, although it should be by 4 instead of 2. The multiplication 2 lines down is wrong :/. The division is there so that once the list for the next set of nodes has to be created, since its one level higher, it should be 4 times smaller (hence divide it by 2). The multiplication in the for loop is also needed to get the 4 previous level nodes into one current level child.

Yeah that's what I figured, although I also thought the compiler would just do that for me but its their primarily to get my brain to recognize and understand the shifts and bit stuff.

On a side note, I'm not allowed to create a list in this fashion am I? I got everything to compile but it throws a exception on the line
nodes = Quadtree (children);
but I did also change the nodes structure to be a pointer to a array with a calloc function to allocate the data but with no success. And also, is there a major difference between calloc and new other than the fact that new requires the size of each element to be some data structure instead of a arbitrary number?
 

monoVertex

I'm back!
Reaction score
460
The division is important, although it should be by 4 instead of 2. The multiplication 2 lines down is wrong :/. The division is there so that once the list for the next set of nodes has to be created, since its one level higher, it should be 4 times smaller (hence divide it by 2). The multiplication in the for loop is also needed to get the 4 previous level nodes into one current level child.

My point was that you did not assign that division to anything, so that line does exactly nothing, while the multiplication was assigned.

On a side note, I'm not allowed to create a list in this fashion am I? I got everything to compile but it throws a exception on the line
nodes = Quadtree (children);

I think you should rather use arrays of pointers instead.

So do something along the lines:

Code:
Quadtree::Quadtree(Quadtree ** _children) {}

Code:
...
Quadtree ** children = (Quadtree**) malloc(sizeof(Quadtree*) * 4);
children[0] = &(prev_nodes[j]);
children[1] = &(prev_nodes[j+1]);
children[2] = &(prev_nodes[j+2]);
children[3] = &(prev_nodes[j+3]);
nodes[i] = Quadtree(children);
...

This ensures that you're always using the same memory for your Quadtrees. With your previous setup, you were creating new Quadtree memory chunks and then copied the addresses of your existent chunks into them.

I have to say, I am not very familiar with new and I am coming from a C background, so I tend to rely more on calloc and malloc, generally, and not use new with lists.

but I did also change the nodes structure to be a pointer to a array with a calloc function to allocate the data but with no success. And also, is there a major difference between calloc and new other than the fact that new requires the size of each element to be some data structure instead of a arbitrary number?

I don't know about new for lists, but calloc always initializes your chunk of memory to 0, as opposed to malloc, which gives random stuff in the memory chunk. That means that malloc is faster, but sometimes you need that 0 initialization.

PS: I have to say that you're a bit inconsistent in your coding style, which makes it hard to follow :p. You should try and code a bit more tidy and make sure that you're always consistent in your usage of pointers (*), addresses (&) and allocation with malloc / calloc / new.
 

D.V.D

Make a wish
Reaction score
73
Oh damn, completely didn't notice that one LOL thanks for pointing it out.

Oh wait, I was? I thought that when you create a pointer, all it is is just a string or a bunch of bits that reference some memory location. So if I created the pointers and initialized them to another pointer, than it would be the same as initializing a pointer whose string is the address of that memory location. And while typing this I realize I used the new function in the constructor. I would assume it is only creating excess memory because of that so I'm going to fix it right now.

Okay, ill give it a few searches, dynamic memory is the most confusing part about programming to me at the moment so I'm still trying to understand how stuff will actually execute with references and pointers.

I see, thanks for the info, in this case, I don't really care whats in the memory since I overwrite it with Quadtree nodes anyways so ill use malloc.

Yeah im still trying to figure this stuff out. I should probably set myself the standard of using malloc/calloc vs new. Also, would you mind showing me how my usage of pointers and references is inconsistent? I realize I should fix the way I code pointer related code but I'm not exactly sure how its properly done (I'm a self taught programmer and I'm still in first year university, we do pointers next year I think).
 

monoVertex

I'm back!
Reaction score
460
Actually, I think the main issue is that you were doing:

Code:
Quadtree * children = new Quadtree [4];

But new creates an element and gives you the pointer to it. So that becomes Quadtree** (ie, an array of pointers, or pointer to pointer), whereas you only had Quadtree* (ie an array of objects or a pointer).

Don't quote me on this though, I'm not exactly sure. This is from what I noticed about new's behaviour.
 

D.V.D

Make a wish
Reaction score
73
I actually just did a bunch of searches. New and delete are C++'s versions of malloc, calloc and what not. The difference is new is type safe and calls the constructor where as malloc doesn't have to. The benefit of malloc/calloc and what not is that you can resize them without creating a whole new set where as you can't resize with new and delete.
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
I'm tired and can't even comprehend half of what is said here, but you should try to avoid using new/delete (or malloc/free) where ever applicable.

Rather, try to use std::array<> for arrays of static size and std::vector<> for arrays of dynamic size. They can be resized, they clean up memory by themselves, they make easy-to-read code.
If you have to use so many * and &, you're either coding in C or you're doing it wrong :p
 

monoVertex

I'm back!
Reaction score
460
That's true as well and I take it as an advice for myself, too :D. I have to start thinking about C++ more in Java terms rather than in C terms.
 

D.V.D

Make a wish
Reaction score
73
I agree I should but I really want to get this whole thing working because every time I write a program with pointers, it usually leaks or crashes. Its my worst concept in programming so far so I really want it down even if I will change it to std::array and std::vector. Especially since I usually have a harder time with C++, my python code in university is going way easier than my hobby coding in C++ :(.

I changed up a bunch of the program but I have a very weird issue. I think my program double deletes but there's a bunch of bugs that don't seem to make much sense to me. For one, I changed prev_nodes and nodes to be double pointers so they are arrays of pointers. The thing that first doesn't make sense is this:

Code:
        uint8_t level = 15;
        uint32_t count = length;
        Quadtree ** prev_nodes = new Quadtree* [count];
   
        for ( uint32_t i = 0; i < count; i++ )
        {
            prev_nodes[i] = new Quadtree;
            prev_nodes[i]->level = level;
            std::cout << prev_nodes[i]->level << std::endl;
            prev_nodes[i]->average = Image_Pixels[i];
        }

The std::cout in this line always prints '*' rather than the actual level value. Why doesn't it change it? Is it sending the memory location with the value of level? It shouldn't do that since the value prev_nodes->level should be changing instead of any address.
 

monoVertex

I'm back!
Reaction score
460
Sorry, writing this in a rush, but are you using Visual Studio? Why don't you use the debug tools and debug the program step by step, with watches in place, instead of prints?

It's way easier to see the data inside your variables then.
 

D.V.D

Make a wish
Reaction score
73
Yeah I am, I went step by step countless times and I know where my program crashes, but this error is the first one to pop up. I set prev_nodes->level to a variable (I tried a constant number as well), but it doesn't actually register it the next line after when I print it with cout. It only shows a asterix sign all the times I tested it. For references its Visual Studio 2010.

EDIT: For reference, this is what visual studios debugger tells me the value is before and after setting it to level:

Before: prev_nodes->level 205 'Í' unsigned char
After: prev_nodes->level 15 '' unsigned char

The after one actually isnt capturing properly but its some really weird symbol o_O I can grab a photo if you guys need it, its actually not a asterix but a symbol with a hole inside it and lines coming out and going around it.
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
It probably does. the level variable is a uint8_t, which is the same as a unsigned char. If you print chars via cout you're not going to get the integral representation, but the corresponding ASCII letter. Many ASCII letters cannot be displayed in the console (they end up being weird symbols or just don't show up at all).
Try std::cout << (int) prev_nodes->level;
 

D.V.D

Make a wish
Reaction score
73
Did it and it worked, I actually fixed the error in a odd way. The program doesn't work as intended because the main loop is actually quite heavily flawed at the moment but ill fix that now that the error is gone.

The data I gave to the build function was just a 512x512 1D array of pixels all with the color (0,0,0) or black. That means when I called the constructor that takes a pointer to 4 children as a parameter, it would realize that all the color values of these children are the same and call delete[] on the children pointers. This keeps the data structure sparse with less repeating data but this is were the program would crash. I'm going to assume it didn't know how long the array is but I changed it to delete children[0], delete children[1] ... children[3].

Whats odd about this is the fact that the variable actually specifies a array of size 4 (Quadtree * children [4]) and I'm not sure if this is legal but I also tried delete[4] children which also crashed. Its odd because I thought it would know how many elements it should delete and not go past the 4th index. Maybe its because I'm copying it from another pointer which was only Quadtree ** _children = new Quadtree* [4]; Although I did pass it as a parameter of type Quadtree * _children [4] so I'm not exactly sure why delete[] didn't work. Ill try a straight up Quadtree * [4] instead of ** and see if it makes a difference. Here's the code if anyone wanted to see it (without debug messages):

Code:
    struct Quadtree
    {
        uint32_t average;
        uint16_t length_x;
        uint16_t length_y;
        uint8_t level;
 
        Quadtree * parent;
        Quadtree * children [4];
   
        Quadtree ();
        Quadtree (Quadtree * children [4]);
        ~Quadtree ();
   
    }
 
        Quadtree::Quadtree ()
    {
        parent = nullptr;
        children[0] = nullptr;
        children[1] = nullptr;
        children[2] = nullptr;
        children[3] = nullptr;
    }
 
    Quadtree::Quadtree (Quadtree * _parent, uint32_t _x, uint32_t _y)
    {
        Quadtree ();
        parent = _parent;
        level = parent->level++;
        length_x = _x;
        length_y = _y;
    }
 
    Quadtree::Quadtree (Quadtree * _children [4])
    {
        parent = nullptr;
        children[0] = _children[0]; // share same address
        children[1] = _children[1]; // share same address
        children[2] = _children[2]; // share same address
        children[3] = _children[3]; // share same address
 
        level = children[0]->level--;
        length_x = children[0]->length_x << 1; // multiply by 2 (2*1)
        length_y = children[0]->length_y << 1; // multiply by 2
 
        if ( children[0]->average == children[1]->average && // If all children nodes are the same, delete them (sparse quadtree)
            children[1]->average == children[2]->average &&
            children[2]->average == children[3]->average )
        {
            average = children[0]->average;
            delete children[0];
            delete children[1];
            delete children[2];
            delete children[3];
            children[0] = nullptr;
            children[1] = nullptr;
            children[2] = nullptr;
            children[3] = nullptr;
        }
        else
        {
            average = (children[0]->average + children[1]->average + children[2]->average + children[3]->average) >> 2; // divide by 4 (2*2)
            children[0]->parent = this;
            children[1]->parent = this;
            children[2]->parent = this;
            children[3]->parent = this;
        }
    }
 
    Quadtree::~Quadtree ()
    {
        parent = nullptr;
        if ( children[0] != nullptr )
        {
            delete children[0];
        }
        if ( children[1] != nullptr )
        {
            delete children[1];
        }
        if ( children[2] != nullptr )
        {
            delete children[2];
        }
        if ( children[3] != nullptr )
        {
            delete children[3];
        }
    }

Code:
    Quadtree* build (unsigned int * Image_Pixels, int length)
    {
        uint8_t level = 15;
        uint32_t count = length;
        Quadtree ** prev_nodes = new Quadtree* [count];
 
        for ( uint32_t i = 0; i < count; i++ )
        {
            prev_nodes[i] = new Quadtree;
            prev_nodes[i]->level = level;
            prev_nodes[i]->average = Image_Pixels[i];
        }
   
        while (level > 0)
        {
            level --;
            count >>= 2; // Divide by 4
            Quadtree ** nodes = new Quadtree* [count];
 
            for ( uint32_t i = 0, j = 0; j < count << 2; i++, j+=4 )
            {
                Quadtree ** children = new Quadtree* [4];
 
                children[0] = prev_nodes[j]; // share same address
                children[1] = prev_nodes[j+1]; // share same address
                children[2] = prev_nodes[j+2]; // share same address
                children[3] = prev_nodes[j+3]; // share same address
 
                nodes[i] = &Quadtree(children);
            }
 
            if ( count == 1 )
            {
                return nodes[0];
            }
 
            prev_nodes = nodes;
        }
    }
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
A few things:

Code:
Quadtree::Quadtree (Quadtree * _parent, uint32_t _x, uint32_t _y)
    {
        Quadtree ();
        ...
    }

This doesn't do what you think it does. I guess you want to call the default constructor for the object you are currently constructing. But what this actually does is create a temporary Quadtree object and immediately throw it away. It's basically the same as writing "Quadtree t = Quadtree();".

You either have to copy-paste the contents of the default constructor or - if you run C++11 - you can write:

Code:
Quadtree::Quadtree (Quadtree * _parent, uint32_t _x, uint32_t _y)
        : Quadtree() //Only C++11, properly calls the default constructor
    {
        ...
    }


Next, this isn't necessary:

Code:
if ( children[0] != nullptr )
        {
            delete children[0];
        }

Calling delete on a nullptr is fine (it's a no-operation). So you can just call "delete children[x]" without having to check first.

Code:
count >>= 2; // Divide by 4
...
j < count << 2

Please don't do this. I know that bit-shifting properly divides/multiplies by powers of two, but it makes the code much harder to read. It might even change the behavior of your expressions because bitshifts have a different precedence than multiplication/division.

Code:
(2 + 4 << 1) // this returns 12
(2 + 4 * 2) // this returns 10

Lastly, it doesn't make things faster. Every compiler worth it's salt will do this optimization by themselves. So just stick to the normal operators :)

Code:
Quadtree::~Quadtree ()
    {
        parent = nullptr; //<--
        ...
    }

This isn't necessary since we're inside the destructor. The member variables cannot be used after it's destruction anyway.

Code:
Quadtree ** prev_nodes = new Quadtree* [count];
...
Quadtree ** children = new Quadtree* [4];

I don't think you're ever deleting these arrays. You pass their content into the constructors of the Quadtrees (and they destructors should take care of deleting them), but you never actually call "delete prev_nodes" or "delete children". And that's why working with std::array<> and std::vector<> is probably a very good idea. You'll get confused and mess up delete'ing somewhere, especially if you pass parts of the arrays around. Everytime I have to use an X** variable, my alarm bells ring. If I already have to use pointers to pointers to variables then something is foul.

The algorithm in it's whole *looks* alright to me, but I can't verify it because I don't have a working compiler right now (and I've no idea how you're calling the code).
 

D.V.D

Make a wish
Reaction score
73
A few things:

Code:
Quadtree::Quadtree (Quadtree * _parent, uint32_t _x, uint32_t _y)
    {
        Quadtree ();
        ...
    }

This doesn't do what you think it does. I guess you want to call the default constructor for the object you are currently constructing. But what this actually does is create a temporary Quadtree object and immediately throw it away. It's basically the same as writing "Quadtree t = Quadtree();".

You either have to copy-paste the contents of the default constructor or - if you run C++11 - you can write:

Code:
Quadtree::Quadtree (Quadtree * _parent, uint32_t _x, uint32_t _y)
        : Quadtree() //Only C++11, properly calls the default constructor
    {
        ...
    }

Oh damn, okay ill change it. I don't think visual studio 2010 supports C++11 or at least not all of it so Ill just copy and paste for now.

Next, this isn't necessary:

Code:
if ( children[0] != nullptr )
        {
            delete children[0];
        }

Calling delete on a nullptr is fine (it's a no-operation). So you can just call "delete children[x]" without having to check first.

Oh yeah, I was doing a test of that before hand, completely missed it here thanks! :D

Code:
count >>= 2; // Divide by 4
...
j < count << 2

Please don't do this. I know that bit-shifting properly divides/multiplies by powers of two, but it makes the code much harder to read. It might even change the behavior of your expressions because bitshifts have a different precedence than multiplication/division.

Code:
(2 + 4 << 1) // this returns 12
(2 + 4 * 2) // this returns 10

Lastly, it doesn't make things faster. Every compiler worth it's salt will do this optimization by themselves. So just stick to the normal operators :)

I know, the only real reason your seeing them here is because I just learned all the shifts and its a matter of learning to see them and understand what they do. They'll definitely be removed after and put into better use (next step might be to do Morton code once this works completely as intended).

Code:
Quadtree::~Quadtree ()
    {
        parent = nullptr; //<--
        ...
    }

This isn't necessary since we're inside the destructor. The member variables cannot be used after it's destruction anyway.

Oh damn, I put that there because at the beginning I was not sure if calling delete on a children pointer was calling delete on the parent and then crashing my program. Turns out it wasn't so I should remove that (i tried a lot of stuff trying to fix the crash, some which might be pretty illogical looking back but I think I get the topic better now :) ).

Code:
Quadtree ** prev_nodes = new Quadtree* [count];
...
Quadtree ** children = new Quadtree* [4];

I don't think you're ever deleting these arrays. You pass their content into the constructors of the Quadtrees (and they destructors should take care of deleting them), but you never actually call "delete prev_nodes" or "delete children". And that's why working with std::array<> and std::vector<> is probably a very good idea. You'll get confused and mess up delete'ing somewhere, especially if you pass parts of the arrays around. Everytime I have to use an X** variable, my alarm bells ring. If I already have to use pointers to pointers to variables then something is foul.

The algorithm in it's whole *looks* alright to me, but I can't verify it because I don't have a working compiler right now (and I've no idea how you're calling the code).

Its not the delete in the destructor that broke the program, it was actually the delete called in the constructor inside the if statement. That was where the program was crashing and thats where I applied the changes in my post above. More specifically, its this code right here:

Code:
        if ( children[0]->average == children[1]->average && // If all children nodes are the same, delete them (sparse quadtree)
            children[1]->average == children[2]->average &&
            children[2]->average == children[3]->average )
        {
            average = children[0]->average;
            delete children[0];
            delete children[1];
            delete children[2];
            delete children[3];
            children[0] = nullptr;
            children[1] = nullptr;
            children[2] = nullptr;
            children[3] = nullptr;
        }

Before it was delete[] children which crashed the program where as calling delete on all of the children index's didn't crash.

The code runs, I just create a Quadtree in my main and call build on it and have some output stuff coming up but it doesn't actually work as its supposed to. For one, Im picking nodes in the build function's loop in a line instead of a box. It should be a 2 dimensional array or at the very least, I should be accessing the 1D array as a 2D array (since both are technically the same anyways, the 2d one has a bit of math in its index). I also don't have a proper if statement in the constructor which can in some cases provide invalid results for the quadtree but Ill get working on it once I get home.

It is pretty foul and I can see why but its a really cool topic anyways XD. Ill start adding std::array and vector (array for the children, vector for the build function). I still have to use single pointers anyways so this was a good crash to fix.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top