Quad Trees

[starboarder2001]

This isn't really the right forum...but I didn't know were else to post it. I am using opengl for this though :P .

my first question:

Ok I decided to give it a try. I have a terrain map 128by128. I divided it down until there are 256 polygons in each node. I got a average of 20-50fps increase so i know it is doing its job. Right now I am using a linked list to hold the nodes. Is what I wanted to know is..What is the best way to store the nodes...have a linked list or a array? it seems to work fine but I just wondered what the "correct" or the most popular way was?

my second question:

I have never used linked lists before so i just wanted to make shure i have a ok understanding of what they are...and how to use them. :blush:

//example -I know that this wouldnt run i am not going to allocate memory...i am to lasy to do it for the example so just ignore that :)

struct LIST{
int data;
LIST *list;
};

int num = NULL;

void SetList(LIST *list){ //create a list of 10 and set data to num
num++;
list->data = num;
if(num < 10){
SetList(list);
}

}

my third question:

I dont know if it is a bug or what but when i divide it until each node has 64 polygons it probably takes about 10 seconds to build the tree. If I devide it down to 256 it works fine it only takes a few seconds. I know it will be hard to answere becuase you cant see my code...but i just wondered if it is normal to take that long to build the tree of that size?

[UnknownStranger]

Why don't you just implement it the way it is called? B)

edit: About Q3...splitting down to a level of 64 Polygons might not be very efficient; it should usually be much faster to just draw that bunch of a few hundred polys and don't waste cpu power or memory on splitting it down that much...

[starboarder2001]

http://www.vision-software.org/treeexample.JPG

Well you edited your post to word it a little different...but basicly says the same thing. :)

Here is kind of what i am doing..

-check the children of parent to see if they are in the viewing frustrum
-"parent->c1" was the only child in viewing frustrum so check its children
-"parent->c1->c2" was the only child in the viewing frustrum so render node

basicly i just work down the tree...if a node is not in the viewing frustrum i do not check its children.

although this is just a small example of how i did it...you can see that it seems to be a tree. each node holds 4 child nodes. When you edited it did you mean do it the way i am doing it now?? or is there another way...help me out :blush: .

my structure would be something like this.
struct NODE{
DATA *data;
NODE *child[4];
};

edit: About Q3...splitting down to a level of 64 Polygons might not be very efficient; it should usually be much faster to just draw that bunch of a few hundred polys and don't waste cpu power or memory on splitting it down that much...

Ok..thanks :)

[UnknownStranger]

struct NODE{
DATA *data;
NODE *child[4];
};


Yep, that's a nice quad tree node structure; that's how it's ment to be ;)


EDIT: 100th post :)

[DrunkenCoder]

for a nearly fully populated tree of for one where speed is of outmost importance I would suggesting putting it into one contigous memory block, much as you would with a "flat" binary tree.