Jump to content
  • Advertisement
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

Recommended Posts



Here are some code snippet


It's just going perfectic, and stack overflowing.



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:      - + - + - + - +

        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;

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

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

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


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

                    // 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)
            } else {
                // We are at an interior node. Insert recursively into the
                // appropriate child octant
                int octant = getOctantContainingPoint(point->getPosition());

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

for (int i = 0; i < verts.size(); i += 3)
        Vec3 newPos(verts[i], verts[i+1], verts[i+2]);
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)));
Edited by lucky6969b

Share this post

Link to post
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 this post

Link to post
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 this post

Link to post
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 this post

Link to post
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.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!