Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Quadtree generator for BMP sprites
Index -> Programming, C++ -> C++ Submissions
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Insectoid




PostPosted: Sun May 12, 2013 1:06 pm   Post subject: Quadtree generator for BMP sprites

This program takes a bitmap image as input, generates a quadtree mesh outlining the input, draws the mesh onto the image and outputs the image to output.bmp. I finally got around to looking for a decent bitmap library to use for this project, and found EasyBMP, which is awesome and exactly suited for my needs (after some very small modifications).

This works by iterating over the pixels in the image and calculating the percentage of colored pixels to total pixels (I've set the 'invisible color' to white for now. It ignores alpha values atm but that can easily be changed later). If the percentage is greater than 80% or equal to 0%, the image is considered 'full' or 'empty', and no sub-division takes place. Otherwise, it divides the image into quarters and repeats the process until the quarter is full/empty, or it has recursed 8 times. Once it has generated the tree, the program draws the outline of every division and sub-division except the empty ones, and saves the new image as output.bmp.

If I get around to it, I'll fix this up so that it's more modular (account for Alpha values, adjustable invisible color, variable depth and min/max coverage, etc). I also plan on adding a function that outputs the tree data to a file that can be loaded by another program for collision detection (or whatever you might use it for). From there, I suppose I'll have to build a demo to show it working. But for now, this is what I've got.

Compile with 'c++ collision.cpp easybmp.cpp'.



ex_output.bmp
 Description:
 Filesize:  4.92 KB
 Viewed:  22260 Time(s)

ex_output.bmp



output.bmp
 Description:
 Filesize:  247.97 KB
 Viewed:  551 Time(s)

output.bmp



robot_output.bmp
 Description:
 Filesize:  576.05 KB
 Viewed:  645 Time(s)

robot_output.bmp



Quadtree.zip
 Description:

Download
 Filename:  Quadtree.zip
 Filesize:  299.15 KB
 Downloaded:  588 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
mirhagk




PostPosted: Sun May 12, 2013 1:53 pm   Post subject: RE:Quadtree generator for BMP sprites

Interesting project, I absolutely love quadtrees, they are so easy to work with, yet can be ridiculously more efficient.

Just out of curiousity, what are your plans with this, is it just a random, just cuz project, or do you have some use for it?


Rant:
If only minecraft had developers half as capable as some of the people on here.... The majority of maps are filled with either dirt, stone or air, and regions that aren't are clumped together. It is like literally the most optimal scenario for quadtree (well rather octree) storage.
Insectoid




PostPosted: Sun May 12, 2013 2:00 pm   Post subject: RE:Quadtree generator for BMP sprites

Collision detection has always been a massive pet peeve of mine. I'm tired of using single rectangles and ovals to represent complex objects. I want this to simplify the process. Just plug in your sprite image and it spits out the quadtree. Problem solved.
Insectoid




PostPosted: Sun May 12, 2013 7:03 pm   Post subject: RE:Quadtree generator for BMP sprites

This is the most fun I've ever had playing with one of my own programs! It's turned out way more interesting than I anticipated!

Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.
Posted Image, might have been reduced in size. Click Image to view fullscreen.

Unfortunately, EasyBMP doesn't support bitmaps with negative heights, and all my editing applications format just happen to format bitmaps with negative heights, so I can't use any of my own images. Oh well.
linuxp




PostPosted: Sun May 12, 2013 10:10 pm   Post subject: Re: RE:Quadtree generator for BMP sprites

mirhagk @ Sun May 12, 2013 1:53 pm wrote:
If only minecraft had developers half as capable as some of the people on here.... The majority of maps are filled with either dirt, stone or air, and regions that aren't are clumped together. It is like literally the most optimal scenario for quadtree (well rather octree) storage.


I don't think octree or quadtree is good for minecraft "game". They are probably very great for minecraft static map rendering but not the game. When there are tons of redstones, water, mobs updating, random access speed and iteration speed become very critical. In my opinion, best way to handle this is straight up store blocks as array. Updating each chunk requires only 16*16*256=65536 access which is a very small number. But if there are some huge redstone structures with large amount of redstones need to update, random access efficiency of oct/quadtree is a big issue.
Also, networking is another problem. I'm not sure if there is any efficient technique to stream octree between server and client. (single player minecraft is just an integrated server)
Very Happy
Insectoid




PostPosted: Mon May 13, 2013 2:24 pm   Post subject: Re: Quadtree generator for BMP sprites

I did a little more work on it. Running collision.cpp will now save the tree to a file. Running inputQuadTree.cpp will load the file and draw the tree to the screen.

Improvements:

-The tree now starts at 100% accuracy, and becomes slightly less accurate the deeper you go. Previously, it would have big chunks that were maybe 85% full that didn't split, and tiny chunks that were super-accurate right next to it, which was pretty funny and wrong. It is now far more accurate for a lower max tree depth.
-Initially I just wrote a bunch of 1's and 0's to a text file to save the tree (code deleted so nobody can see my shame). This led to ridiculous 80MB files with over a million one-character lines. The program now writes less data, and it groups all the 1's and 0's into bytes so the files are as low as 200 bytes (they may be significantly larger depending on your filesystem).
-inputQuadTree.cpp was created. It loads the tree and draws it to the screen. If you specify an image when you call it (ie ./inputQuadTree image.bmp) it will draw it to that image. Make sure the picture dimensions are at least as big as the original one though, or bad things will happen.
-inputQuadTree.cpp now trims the tree during loading. Any nodes that are non-collidable are deleted from the tree. No uncollidable node has collidable children, so they can simply be removed. This reduces the total RAM required by variable amounts depending on the source image. Some get massive improvement and some don't improve all that much. I may move this job to the generator once I figure out how to store a trimmed tree without potentially doubling the size of the file.
-runtime & RAM usage for large inputs has been significantly reduced. Previously, large inputs could require several GB of RAM (I ended up 5GB deep in swap memory once before I terminated the script) and run for several minutes. The same inputs now execute almost instantly and with minimal memory requirements. Loading a tree into inputQuadTree now requires as little as 4KB of RAM (though a lot more space is used to store the image data).


Bugs:
-Trimming north-west nodes causes a segfault. I don't know why. All the other nodes trim just fine, and they're all treated identically in code.

If you want to play with it, compile the generator with c++ collision.cpp EasyBMP.cpp -o generate. Compile the loader with c++ inputQuadTree.cpp EasyBMP.cpp -o load (this is probably different for non-GCC compilers). run the generator with the path to your image file as an argument. It will output an image to output.bmp. Run the loader by itself. If you pass the loader an image, it will try to draw the tree to that image. It outputs the new image to output2.bmp.



EasyBMP_test.zip
 Description:

Download
 Filename:  EasyBMP_test.zip
 Filesize:  467.29 KB
 Downloaded:  463 Time(s)

DemonWasp




PostPosted: Mon May 13, 2013 5:43 pm   Post subject: RE:Quadtree generator for BMP sprites

I compiled your code on g++ (after fixing a syntax error, see below) and uncommented the call to trim() and the recursive call for nw->trim(), and I didn't get any segfault. I can't see any difference between the output, but it sure did generate a lot of calls to the destructor.

In inputQuadTree.cpp, QuadTree::readFromFile(ifstream*), this:
code:
&(char)bitpack
should be
code:
(char*)&bitpack
Insectoid




PostPosted: Mon May 13, 2013 6:14 pm   Post subject: RE:Quadtree generator for BMP sprites

That syntax error is just a warning on my compiler (gcc 4.2.1) but the warning does state that it will be an error in future versions, which I guess did indeed happen.

Interesting about the segfault. It isn't happening on my end anymore either. I don't remember fixing it. It just didn't work. I don't like it when bugs fix themselves...
Sponsor
Sponsor
Sponsor
sponsor
Zren




PostPosted: Mon May 13, 2013 7:39 pm   Post subject: Re: RE:Quadtree generator for BMP sprites

mirhagk @ Sun May 12, 2013 1:53 pm wrote:
Rant:
If only minecraft had developers half as capable as some of the people on here.... The majority of maps are filled with either dirt, stone or air, and regions that aren't are clumped together. It is like literally the most optimal scenario for quadtree (well rather octree) storage.


There was a guy on r/gamedev a while ago who decided to try making a Minecraft clone. He had the same idea (with octrees). I think he decided not to use them because rebuilding the tree on every edit/build/destroy gave bad performance. Of course you could probably use them for the saved unloaded chunks. Minecraft might already be doing that as I remember them changing to the Anvil storage format, which supposedly had some form of compression.


linuxp @ Sun May 12, 2013 10:10 pm wrote:
mirhagk @ Sun May 12, 2013 1:53 pm wrote:
If only minecraft had developers half as capable as some of the people on here.... The majority of maps are filled with either dirt, stone or air, and regions that aren't are clumped together. It is like literally the most optimal scenario for quadtree (well rather octree) storage.


I don't think octree or quadtree is good for minecraft "game". They are probably very great for minecraft static map rendering but not the game. When there are tons of redstones, water, mobs updating, random access speed and iteration speed become very critical. In my opinion, best way to handle this is straight up store blocks as array. Updating each chunk requires only 16*16*256=65536 access which is a very small number. But if there are some huge redstone structures with large amount of redstones need to update, random access efficiency of oct/quadtree is a big issue.
Also, networking is another problem. I'm not sure if there is any efficient technique to stream octree between server and client. (single player minecraft is just an integrated server)
Very Happy


Ah, totally forgot about everything updating during each tick, that definitely would make things much slower on the live version.
Insectoid




PostPosted: Mon May 13, 2013 8:18 pm   Post subject: RE:Quadtree generator for BMP sprites

I'm working on a consolidation algorithm now, which combines adjacent squares with compatible dimensions, but it keeps segfaulting. Again. I'm gonna post the code here because last time I did, the problem went away and I figure maybe it will work again.
c++:
#include <cmath>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include "EasyBMP.h"

using namespace std;

class QuadTree {
        private:
                char collidable;
                int offsetX, offsetY, depth;
               
                QuadTree *nw, *sw, *ne, *se, *parent;
                QuadTree* readFromFile (char* _in);
                QuadTree* readFromFile(ifstream* in);
                void drawBoundary(BMP* data, RGBApixel color); //draws the boundary around the node
                void mergeNorth();
                void mergeSouth();
        public:
                int sizeX, sizeY;
                static RGBApixel black;
                static RGBApixel red;
               
                QuadTree(char* ifile);
                QuadTree(ifstream *ifile);
                QuadTree(int offsetX, int offsetY, int sizeX, int sizeY, int depth, unsigned char* bitpack, ifstream* in, QuadTree* parent);
                ~QuadTree();
                bool hasChildren();
                bool trim();
                void merge(int depth);
                void drawBoundaries(BMP* data); //recursively draws all non-empty nodes 
};

QuadTree::QuadTree (char* ifile){
        offsetX = offsetY = depth = 0;
        nw = sw = ne = se = NULL;
        readFromFile(ifile);
        trim();
        merge(0);
}

QuadTree::QuadTree (int offsetX, int offsetY, int sizeX, int sizeY, int depth, unsigned char* bitpack, ifstream* in, QuadTree *parent){
        this->offsetX = offsetX;
        this->offsetY = offsetY;
        this->sizeX = sizeX;
        this->sizeY = sizeY;
        this->depth = depth;
        this->parent = parent;
        unsigned char b = 255;
        b &= *bitpack;
        b >>= 7;
        *bitpack <<= 1;
        this->collidable = b;
        b = 255;
        b &= *bitpack;
        b >>= 7;
        *bitpack <<= 1;
        //cout << depth << endl;
        //cout << (unsigned int)collidable << " " << (unsigned int)b << endl;
        if (b) readFromFile(in);       
}

QuadTree::~QuadTree(){
        if (nw != NULL) delete (nw);
        if (ne != NULL) delete (ne);
        if (sw != NULL) delete (sw);
        if (se != NULL) delete (se);
}

QuadTree* QuadTree::readFromFile(char* _in){
        char hasChildren;
        ifstream in;
        in.open (_in);
        in >> sizeX;
        in >> sizeY;
        in >> collidable;
        in >> hasChildren;
        collidable -= 48;
        hasChildren -= 48;
        //cout << "collidable: " << (int) collidable << " hasChildren: " << (int)hasChildren << endl;
        if (hasChildren) readFromFile (&in);
        in.close();
        return this;
}

QuadTree* QuadTree::readFromFile(ifstream* in){
        unsigned char bitpack;
        in->read ((char*) &bitpack, 1);
        //cout << hex << setfill('0') << setw(2) << (int) bitpack << dec << endl;
        nw = new QuadTree (offsetX, offsetY, int (floor (sizeX/2.0)), int(floor (sizeY/2.0)), depth+1, &bitpack, in, this);
        ne = new QuadTree (offsetX + int(floor(sizeX/2.0)), offsetY, int(ceil(sizeX/2.0)), int(floor(sizeY/2.0)),depth+1, &bitpack, in, this);
        sw = new QuadTree (offsetX, offsetY + int(floor(sizeY/2.0)), int(floor(sizeX/2.0)), int(ceil(sizeY/2.0)), depth +1, &bitpack, in, this);
        se = new QuadTree (offsetX + int(floor(sizeX/2.0)), offsetY + int(floor(sizeY/2.0)), int(ceil(sizeX/2.0)), int(ceil(sizeY/2.0)), depth+1, &bitpack, in, this);
        return this;
}

void QuadTree::drawBoundary(BMP* data, RGBApixel color){
        //draw horizontal lines
        for (int x = 0; x < sizeX; x++){
                data->SetPixel (x+offsetX, offsetY+sizeY, color); //bottom
                data->SetPixel (x+offsetX, offsetY, color); //top
        }
       
        //draw vertical lines
        for (int y = 0; y < sizeY; y++){
                data->SetPixel (offsetX+sizeX, y+offsetY, color); //right
                data->SetPixel (offsetX, y+offsetY, color); //left
        }
}
       
void QuadTree::drawBoundaries(BMP* data){
                if (collidable && !hasChildren()) drawBoundary(data, red);
                //else drawBoundary(data, black);
                if (nw != NULL) nw -> drawBoundaries(data);
                if (sw != NULL) sw -> drawBoundaries(data);
                if (ne != NULL) ne -> drawBoundaries(data);
                if (se != NULL) se -> drawBoundaries(data);
}

bool QuadTree::hasChildren(){
        return ((nw != NULL) || (sw != NULL) || (ne != NULL) || (se != NULL));
}

bool QuadTree::trim(){
        if (ne != NULL && ne->trim()) {delete (ne);ne = NULL;}
        if (sw != NULL && sw->trim()) {delete (sw);sw = NULL;}
        if (se != NULL && se->trim()) {delete (se);se = NULL;}
        if (nw != NULL && nw->trim()) {delete (nw);nw = NULL;}
        if (!collidable) return 1;
        return 0;
}

void QuadTree::mergeNorth(){
        if (nw != NULL && ne != NULL && !nw->hasChildren() && !ne->hasChildren() && nw->sizeY == ne->sizeY){
                printf ("North Merge!\n");
                nw->sizeX += ne->sizeX;
                delete(ne);
        }
        else {
                printf ("No North Merge! Going deeper...!\n");
                if (nw != NULL) nw->merge(depth+1);
                if (ne != NULL) ne->merge(depth+1);
        }
}
void QuadTree::mergeSouth(){
        if (sw != NULL && se != NULL && !sw->hasChildren() && !se->hasChildren() && sw->sizeY == se->sizeY){
                printf ("South Merge!\n");
                sw->sizeX += se->sizeX;
                delete(se);
        }
        else {
                printf ("No South Merge! Going deeper...!\n");
                if (sw != NULL) sw->merge(depth+1);
                if (se != NULL) se->merge(depth+1);
        }
}

void QuadTree::merge(int depth){
        printf ("Depth = %d\n", depth);
        if (hasChildren()) {
                printf ("Has Children!\n");
                mergeNorth();
                mergeSouth();
        }
        else printf ("Leaf!\n");
                //if (ne != NULL) ne->merge();
                //if (sw != NULL) sw->merge();
                //if (se != NULL) se->merge();
}       

RGBApixel QuadTree::black = {0,0,0,0};
RGBApixel QuadTree::red = {0, 0, 255, 0};

#define SIZE 1
int main(int argc, char* argv[]){
        BMP image;
        QuadTree* a[SIZE];
        for (int i = 0; i < SIZE; i++) a[i] = new QuadTree("foo.tree");
        int foo;
        //scanf ("%d", &foo);
        if (argc >= 2) image.ReadFromFile (argv[1]);
        image.SetSize (a[0]->sizeX+1, a[0]->sizeY+1);
       
        a[0]->drawBoundaries (&image);
        image.WriteToFile ("output_2.bmp");
}
mirhagk




PostPosted: Mon May 13, 2013 8:56 pm   Post subject: RE:Quadtree generator for BMP sprites

Man I'm going to have to get deep into quad trees again, I'm curious about all of this.

For the redstone thing, I could imagine there might be a workaround, and I'd be curious whether navigating the tree is worse than having more memory used.

As for networking, shouldn't it be possible to be much faster? Start sending the parent nodes, and then go to deeper and deeper depths, so the client starts out with a rough approximate and then it gets more and more detailed. You could probably even focus it to send deeper nodes closer first, so you'd get high detailed close, and low detail far

@Insectoid

That's actually a good idea with the collision detection. Per pixel is extremely costly, and I hate when 2D images use box collision detection. Have you done any comparisons for speed about how much faster this is than per-pixel?
Insectoid




PostPosted: Tue May 14, 2013 4:34 am   Post subject: RE:Quadtree generator for BMP sprites

Well, per-pixel is at least O(n) and potentially O(n^2). Quadtrees are O(log N) or something and at worst, O(depth^2).
Insectoid




PostPosted: Tue May 14, 2013 12:33 pm   Post subject: RE:Quadtree generator for BMP sprites

I worked on it a bit more, and fixed the merge() algorithm. It works, but unfortunately it segfaults if you try to create more than one instance of the tree. merge() will only merge children of the same node, so I've started work on a deepMerge() function, which will merge the children of adjacent parents. For the purpose of collision detection, this is more difficult. For example, if I merge() nw and ne, I can simply add their widths together and assign that to nw, and set ne to NULL. This causes no problems with collision detection, because they share the same parent and even a collision happened with ne, it will simply be detected by nw instead.

However, if I deepMerge() ne and nw, they do not share the same parent. Using the same strategy as with merge(), if ne collides but nw's parent does not, the collision will not be detected. I tried assigned ne=nw in my code, which would solve the problem, however if nw is subsequently merged with another node, then nw will point to the new node and the node nw was pointing at will be deleted, but ne is still pointed at that node, which no longer exists. For now I'm simply setting ne to NULL, which as I explained renders the tree useless for collision detection. If anyone knows of a way to solve this, I'd be happy to hear it.

Anyway, here's some pictures.

Raw tree:
Posted Image, might have been reduced in size. Click Image to view fullscreen.

Trimmed tree:
Posted Image, might have been reduced in size. Click Image to view fullscreen.

Merged tree:
Posted Image, might have been reduced in size. Click Image to view fullscreen.

Deeply merged tree:
Posted Image, might have been reduced in size. Click Image to view fullscreen.

As you can see from the last image, my deepMerge() algoritm isn't perfect and there's a lot of nodes that could have been merged. This is a side-effect of nullifying spare pointers. A lot of potential merges failed because one of the pointers was NULL instead of pointing to the node that took up that space.
Insectoid




PostPosted: Sun May 19, 2013 10:13 am   Post subject: RE:Quadtree generator for BMP sprites

I've run into a really strange issue inside inputQuadTree.cpp. It runs just fine when I load up a single tree, but if I load a second tree, it segfaults when I delete() a node (this happens inside trim(), merge() and deepMerge()). My destructor recursively deletes nodes in the tree. It checks for NULL pointers before trying to delete them, and sets them to NULL after deleting them. The only static variables I have are a couple of RGBApixels, which are structs holding pixel data for drawing to the screen, which have nothing to do with the destructor. The funny thing is that it only happens when I load more than one tree. Even if I assign the first to a pointer with new() and delete() it immediately after, then load a new one, it segfaults.
Display posts from previous:   
   Index -> Programming, C++ -> C++ Submissions
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 14 Posts ]
Jump to:   


Style:  
Search: