Octree Building Problem

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