Quad Trees

F699ebb187331fdf7f7875320e3e7e3e
0
starboarder2001 101 Jul 31, 2003 at 08:36

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?

4 Replies

Please log in or register to post a reply.

Baaecfb3a09127d5bc5045f89025e49e
0
UnknownStranger 101 Jul 31, 2003 at 08:47

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…

F699ebb187331fdf7f7875320e3e7e3e
0
starboarder2001 101 Jul 31, 2003 at 09:02

[img]http://www.vision-software.org/treeexample.JPG[/img]

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 :)

Baaecfb3a09127d5bc5045f89025e49e
0
UnknownStranger 101 Jul 31, 2003 at 10:01

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 :)

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 31, 2003 at 12:00

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.