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…

nodes [16384 kb, 99.97% capacity, depth, 200 enters, 0 exits]

Here is my method:

[ol]

[li]allocate hunk data[/li]

[li]load mesh[/li]

[li]check mesh for duplicate vertices (warn user), and duplicate faces (error)[/li]

[li]determine starting bounding box[/li]

[li]initialize tree structure[/li]

[li]apply recursive function[/li]

[li]delete everything[/li][/ol]

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)

", t->unique);

return;

}

if (t->vertices == 0)

{

printf("recurse - zero vertex count (node %d)

", t->unique);

return;

}

if (t->indices == 0)

{

printf("recurse - zero index count (node %d)

", t->unique);

return;

}

for (a=0;a<8;a++)

{

if (t->children[a] != NULL)

{

printf("recurse - child %d (’%d’) not null (node %d)

", 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

");

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
```

");

return;

}

if (!nw)

{

printf("findpolys - child null

");

return;

}

nw->indices = 0;

```
if (!indextemp)
{
printf("findpolys - no indextemp
```

");

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?!!

Please help

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

```
[img]http://www.opengl.org/discussion_boards/ubb/eek.gif[/img] Thanks [img]http://www.opengl.org/discussion_boards/ubb/eek.gif[/img]
```

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