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).]

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).]