PDA

View Full Version : Octree Building Problem



Fugit
08-31-2000, 12:41 AM
Hi,
I'm now trying to build my octree engine. But, I'm having some problems with (I think) my recursive function - it's never happy that my nodes are small enough. Here's a sample output from my octree builder:

note: i've allocated a quake-like "hunk" buffer so that i'm not constantly calling "new/delete" or "malloc/free". this is the 'data store' and 'indextemp'.



octree compiler

newoctree - allocating data store...ok
loading 'test level.srm'...
checking mesh...
check ok
====compiling octree====

determining bounding box...
min (-3.458333 , -9.744751 , -1.009767).
max (3.486111 , 12.933006 , 1.434562).
initializing tree structure...
creating indextemp...ok
applying recursive function...
1000 nodes [74 kb, 0.23% capacity, 184 depth, 192 enters, 8 exits]
2000 nodes [148 kb, 0.45% capacity, 384 depth, 200 enters, 0 exits]
3000 nodes [222 kb, 0.68% capacity, 584 depth, 200 enters, 0 exits]
4000 nodes [296 kb, 0.91% capacity, 784 depth, 200 enters, 0 exits]
5000 nodes [371 kb, 1.13% capacity, 984 depth, 200 enters, 0 exits]
6000 nodes [445 kb, 1.36% capacity, 1184 depth, 200 enters, 0 exits]
7000 nodes [519 kb, 1.59% capacity, 1384 depth, 200 enters, 0 exits]
8000 nodes [593 kb, 1.81% capacity, 1584 depth, 200 enters, 0 exits]
9000 nodes [667 kb, 2.04% capacity, 1784 depth, 200 enters, 0 exits]
10000 nodes [742 kb, 2.26% capacity, 1984 depth, 200 enters, 0 exits]
11000 nodes [816 kb, 2.49% capacity, 2184 depth, 200 enters, 0 exits]
12000 nodes [890 kb, 2.72% capacity, 2384 depth, 200 enters, 0 exits]

..etc.. until..

<lots of> nodes [16384 kb, 99.97% capacity, <big> depth, 200 enters, 0 exits]



Here is my method:


allocate hunk data

load mesh

check mesh for duplicate vertices (warn user), and duplicate faces (error)

determine starting bounding box

initialize tree structure

apply recursive function

delete everything


Obviously, the recursive function is where the problem is. Here's my Recurse() function:




void Recurse(octree *t)
{
// log("Recurse");

unsigned short a;
unsigned short b;

// check for errors....
depth++;
enters++;
if (!t)
{
printf("recurse - null parameter (node %d)\n", t->unique);
return;
}
if (t->vertices == 0)
{
printf("recurse - zero vertex count (node %d)\n", t->unique);
return;
}
if (t->indices == 0)
{
printf("recurse - zero index count (node %d)\n", t->unique);
return;
}
for (a=0;a<8;a++)
{
if (t->children[a] != NULL)
{
printf("recurse - child %d ('%d') not null (node %d)\n", a, t->children[a]->unique, t->unique);
return;
}
}

for (a=0;a<8;a++)
{
// allocate children
t->children[a] = NewOctree();
if (!t->children[a])
{
printf("recurse: out of memory\n");
return;
}
t->children[a]->parent = t;
for (b=0;b<8;b++)
{
t->children[a]->children[B] = NULL;
}

// calculate child bounding boxes
// create bounding boxes -
// last 3 parameters are x,y,z offset (0 or 1), determining location.
// this definitely works, creates 8 accurate bounding boxes - not a problem
BBox(t->children[a], t->boundingbox, (a & 1)?1:0, (a & 2)?1:0, (a & 4)?1:0);

// store reference data
t->children[a]->vertexdata = t->vertexdata;
t->children[a]->vertices = t->vertices;

// find which polygons lie within the bounding boxes
FindPolys(t, t->children[a]);
if (t->children[a]->indices == 0)
{
// no surfaces at all
t->children[a] = NULL;
}
else if (t->children[a]->indices <= 3)
{
// only one surface, ok - just exit
}
else
{
// too many surfaces, split into 8 bits and try them
Recurse(t->children[a]);
}
}
depth--;
exits++;
}


"Octree" type:



typedef struct octree
{
unsigned long unique; // unique id
float boundingbox[6]; // XYZ-min, XYZ-max
index *indexdata; // indices
vertex *vertexdata; // vertices
unsigned short vertices; // vertex count
unsigned short indices; // index count
octree *children[8]; // 8 cube subdivisions
octree *parent; // parent
} octree;


FindPolys function
void FindPolys(octree *ref, octree *nw)
{
// log("FindPolys");

unsigned short a;

if (!ref)
{
printf("findpolys - parent reference null\n");
return;
}
if (!nw)
{
printf("findpolys - child null\n");
return;
}
nw->indices = 0;

if (!indextemp)
{
printf("findpolys - no indextemp\n");
return;
}

for (a=0;a<ref->indices;a+=3)
{
if ( PointBBox(nw->boundingbox, &ref->vertexdata[ref->indexdata[a]]) &&
PointBBox(nw->boundingbox, &ref->vertexdata[ref->indexdata[a+1]]) &&
PointBBox(nw->boundingbox, &ref->vertexdata[ref->indexdata[a+2]]) )
{
indextemp[nw->indices++] = ref->indexdata[a];
indextemp[nw->indices++] = ref->indexdata[a+1];
indextemp[nw->indices++] = ref->indexdata[a+2];
}
}

nw->indexdata = new index[nw->indices];
memcpy(nw->indexdata, indextemp, nw->indices * sizeof(index));
}

What I think is wrong!!
All my FindPolys function does is supposedly find all the polygons which have all of their vertices contained within the bounding boxes. Now I'm almost sure this is the problem - there could be instances where a polygon intersects with a bounding box but all it's vertices aren't contained within it. Am I right? What can I do?!!
http://www.opengl.org/discussion_boards/ubb/frown.gif Please help http://www.opengl.org/discussion_boards/ubb/frown.gif

Oops, forgot to say - under the project settings i've set my stack size to 1 MEG (both settings) - if this helps at all...

http://www.opengl.org/discussion_boards/ubb/eek.gif Thanks http://www.opengl.org/discussion_boards/ubb/eek.gif

p.s. If you really want to help me, plz read all the bits of this post, there's a few details...

p.p.s. if you need any more function code, or the whole file posted, please say so!! thanks!!

===============


[This message has been edited by Fugit (edited 08-31-2000).]

Fugit
08-31-2000, 05:07 AM
http://www.opengl.org/discussion_boards/ubb/eek.gifWOOHOO! http://www.opengl.org/discussion_boards/ubb/eek.gif
Sorry guys, I fixed it, there was a problem loading the mesh :p

thanks for reading this tho http://www.opengl.org/discussion_boards/ubb/wink.gif

Fugit
08-31-2000, 05:11 AM
http://www.opengl.org/discussion_boards/ubb/eek.gifWOOHOO! http://www.opengl.org/discussion_boards/ubb/eek.gif
Sorry guys, I fixed it, there was a problem loading the mesh :p

thanks for reading this tho http://www.opengl.org/discussion_boards/ubb/wink.gif

Rob
08-31-2000, 09:51 AM
Glad that you found your bug, but you were still right in your statement that a poly can intersect a box without having any vertices inside of the box. Consider a cube with one corner poking slightly through the center of a triangle which has vertices all outside of the box. Or a very large triangle which the box sits completely inside of.
Checking for intersection between an arbitrary polygon and a bounding box is a lot more complex of a problem than one might initially think.

The Real-Time Rendering book illustrates a well thought out solution to the problem. Also, Graphics Gems IV (I think) has a few algorithms.

paolom
09-01-2000, 06:21 AM
can you report the full bibliography for the Real-Time Rendering book

Rob
09-01-2000, 11:00 AM
paolom-
Here's the website for that RTR book. You can probably find all the info you want here: http://www.acm.org/tog/resources/RTR/

[This message has been edited by Rob (edited 09-01-2000).]