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

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);        
}

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

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.

static C_ComPtr<ID3DXMesh> m_pBoxMesh;

std::shared_ptr<Octree> children[8]