# Stack overflow for some inputs on the Simple Octree Project

This topic is 798 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I got stack overflow error when I enter 140000 vertices into the octree area.

It's like it keeps on splitting to a very fine-grained octree until the stack cannot withstand.

https://github.com/brandonpelfrey/SimpleOctree

Thanks

Jack

##### Share on other sites
Your post is missing crucial information.

##### Share on other sites

Sorry,

Here are some code snippet

It's just going perfectic, and stack overflowing.

Update:

I am better off to skip this step and right over to Loose Octrees that is built from this on,

because I am not going to use this garbage anyways, I just use this code to learn octrees.

class Octree {
// Physical position/size. This implicitly defines the bounding
// box of this node
Vec3 origin;         //! The physical center of this node
Vec3 halfDimension;  //! Half the width/height/depth of this node
static CComPtr<ID3DXMesh> m_pBoxMesh;
D3DXCOLOR m_Color;

// The tree has up to eight children and can additionally store
// a point, though in many applications only, the leaves will store data.
std::shared_ptr<Octree> children[8]; //! Pointers to child octants

// TODO: Use Bounding Boxes instead of Points
std::shared_ptr<OctreePoint> data;   //! Data point to be stored at a node

/*
Children follow a predictable pattern to make accesses simple.
Here, - means less than 'origin' in that dimension, + means greater than.
child:    0 1 2 3 4 5 6 7
x:      - - - - + + + +
y:      - - + + - - + +
z:      - + - + - + - +
*/

public:
Octree(const Vec3& origin, const Vec3& halfDimension)
: origin(origin), halfDimension(halfDimension), data(NULL) {
// Initially, there are no children
for(int i=0; i<8; ++i)
children[i] = NULL;

if (!m_pBoxMesh)
D3DXCreateBox(d3d::m_pDevice, 1.0f, 1.0f, 1.0f, &m_pBoxMesh, NULL);

CMinMax<D3DXCOLOR> randColor(D3DXCOLOR(0.1, 0.1, 0.1, 0.3), D3DXCOLOR(0.9, 0.9, 0.9, 0.3));
m_Color = randColor.GetRandomNumber();
}

Octree(const Octree& copy)
{
this->origin = copy.origin;
this->halfDimension = copy.halfDimension;
this->data = copy.data;
this->m_Color = copy.m_Color;
}

D3DXVECTOR3 getSize()
{
return D3DXVECTOR3(halfDimension.x, halfDimension.y, halfDimension.z) * 2.0f;
}

D3DXVECTOR3 getPivot()
{
return D3DXVECTOR3(origin.x, origin.y, origin.z);
}

void Render()
{
// Render this octree
D3DXMATRIX world;
D3DXMatrixIdentity(&world);

D3DXVECTOR3 pos = getPivot();
D3DXVECTOR3 sca = getSize();

D3DXVECTOR3 newPos;
D3DXMatrixTransformation(&world, NULL, NULL, &sca, NULL, NULL, &pos);

SetColor(m_Color);

d3d::m_pDevice->SetTransform(D3DTS_WORLD, &world);

m_pBoxMesh->DrawSubset(0);
}

// Determine which octant of the tree would contain 'point'
int getOctantContainingPoint(const Vec3& point) const {
int oct = 0;
if(point.x >= origin.x) oct |= 4;
if(point.y >= origin.y) oct |= 2;
if(point.z >= origin.z) oct |= 1;
return oct;
}

bool isLeafNode() const {
// This is correct, but overkill. See below.
/*
for(int i=0; i<8; ++i)
if(children[i] != NULL)
return false;
return true;
*/

// We are a leaf iff we have no children. Since we either have none, or
// all eight, it is sufficient to just check the first.
return children[0] == NULL;
}

void insert(std::shared_ptr<OctreePoint> point) {
// If this node doesn't have a data point yet assigned
// and it is a leaf, then we're done!
if(isLeafNode()) {
if(data==NULL || (halfDimension.x <= 0 || halfDimension.y <= 0 || halfDimension.z <= 0))
{
data = point;
return;
}
else
{
// We're at a leaf, but there's already something here
// We will split this node so that it has 8 child octants
// and then insert the old data that was here, along with
// this new data point

// Save this data point that was here for a later re-insert
std::shared_ptr<OctreePoint> oldPoint = data;
data = NULL;

// Split the current node and create new empty trees for each
// child octant.
for(int i=0; i<8; ++i) {
// Compute new bounding box for this child
Vec3 newOrigin = origin;
newOrigin.x += halfDimension.x * (i&4 ? .5f : -.5f);
newOrigin.y += halfDimension.y * (i&2 ? .5f : -.5f);
newOrigin.z += halfDimension.z * (i&1 ? .5f : -.5f);
children[i].reset(new Octree(newOrigin, halfDimension*.5f));
g_Octrees.push_back(children[i]);
}

// Re-insert the old point, and insert this new point
// (We wouldn't need to insert from the root, because we already
// know it's guaranteed to be in this section of the tree)
children[getOctantContainingPoint(oldPoint->getPosition())]->insert(oldPoint);
children[getOctantContainingPoint(point->getPosition())]->insert(point);
}
} else {
// We are at an interior node. Insert recursively into the
// appropriate child octant
int octant = getOctantContainingPoint(point->getPosition());
children[octant]->insert(point);
}
}

// This is a really simple routine for querying the tree for points
// within a bounding box defined by min/max points (bmin, bmax)
// All results are pushed into 'results'
void getPointsInsideBox(const Vec3& bmin, const Vec3& bmax, std::vector<std::shared_ptr<OctreePoint>>& results) {
// If we're at a leaf node, just see if the current data point is inside
// the query bounding box
if(isLeafNode()) {
if(data!=NULL) {
const Vec3& p = data->getPosition();
if(p.x>bmax.x || p.y>bmax.y || p.z>bmax.z) return;
if(p.x<bmin.x || p.y<bmin.y || p.z<bmin.z) return;
results.push_back(data);
}
} else {
// We're at an interior node of the tree. We will check to see if
// the query bounding box lies outside the octants of this node.
for(int i=0; i<8; ++i) {
// Compute the min/max corners of this child octant
Vec3 cmax = children[i]->origin + children[i]->halfDimension;
Vec3 cmin = children[i]->origin - children[i]->halfDimension;

// If the query rectangle is outside the child's bounding box,
// then continue
if(cmax.x<bmin.x || cmax.y<bmin.y || cmax.z<bmin.z) continue;
if(cmin.x>bmax.x || cmin.y>bmax.y || cmin.z>bmax.z) continue;

// At this point, we've determined that this child is intersecting
// the query bounding box
children[i]->getPointsInsideBox(bmin,bmax,results);
}
}
}

};

for (int i = 0; i < verts.size(); i += 3)
{
Vec3 newPos(verts[i], verts[i+1], verts[i+2]);
points.push_back(newPos);
}

for (int i = 0; i<points.size(); ++i)
{
std::shared_ptr<OctreePoint> newPt(new OctreePoint(Vec3(points[i].x, points[i].y, points[i].z)));
m_octree->insert(newPt);
}

Edited by lucky6969b

##### Share on other sites

Have you looked at the backtrace when it crashes? Have you stepped through it with a debugger to see why (I assume) there is infinite recursion?

##### Share on other sites

How deep can be your octree ? You will commonly won't have a height above 7 or 8. From your code, it seems that once you have data on a leaf, you'll split it into 8 children (which will be leaves again).

##### Share on other sites

You are using recursion here. Recursion is typically the wrong answer for a problem in an imperative language. It consumes variable amount of stack, and stack is a precious resource. In windows it is typically 1MB. You can use a recursion if you are sure that it doesn't consume too much stack and it decreases the complexity of the code, but that's not true here. You can use a loop here quite easily.

Other problem that I don't see a stopping condition for the recursion (even if you redesign your code to use loops this is important) if it runs too long. If you try to insert two object at the same place in an Octree it will generate infinite number of children. (Even two objects very near can result a huge amount of levels.) So you must stop at a certain cube size or when it reaches at a certain level.

##### Share on other sites

static C_ComPtr<ID3DXMesh> m_pBoxMesh;

Why is this static? Why are you making your code non-reusable?

std::shared_ptr<Octree> children[8]

Why is this a shared pointer? Do you really intend for other objects to take shared ownership?

A bigger question, why is your tree size created dynamically? Quite often they are implemented as a fixed array right at creation. The contents of the individual nodes can have dynamic content, but having a nice stable array for the tree means you can have direct access to any node through a directly computed value. No need to walk the tree every time you need to access something.

And as others mentioned, the correct way to debug this is to attach your debugger and look at the stack trace. It will be immediately obvious where you forgot the test.

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013710
×