6
\$\begingroup\$

I am creating a game with destructive terrain. Before I used a flat array to store the blocks, in chunks of 32^3.

As I am aiming for detail and long view distance I would of course need some sort of LOD. Therefore I decided to use a octree instead. Memory usage is significantly less than the flat array, but accessing nodes takes much longer. (Specifically for checking neighbors when generating meshes)

Octree.h is the head parent. Each chunk contains one Octree.

Octree.h

#pragma once

#include "OctreeNode.h"
#include "ToolBox.h"

using namespace kaarez::toolBox;

namespace kaarez {
    namespace world {
        namespace chunk {

            class Octree {
            public:
                Octree(int size, int value);
                ~Octree();

                int getValue(Int_position position);
                void insert(Int_position position, int size, int value);

                bool isSolid();


                OctreeNode *m_children[8]{};
            private:
                int m_size = 0;

                int m_value;


            };

        }
    }
}

Octree.cpp

#include "Octree.h"

namespace kaarez {
    namespace world {
        namespace chunk {

            Octree::Octree(int size, int value) {
                m_size = size;
                m_value = value;

            }


            int Octree::getValue(Int_position position) {
                if (isSolid()) {
                    return m_value;
                }

                //Get index
                int index = 0;
                //X
                if (position.x >= m_size / 2) {
                    index++;
                }

                //Y
                if (position.y >= m_size / 2) {
                    index += 2;
                }

                //Z
                if (position.z >= m_size / 2) {
                    index += 4;
                }

                return m_children[index]->getValue(SmallPosition(position.x, position.y, position.z));
            }

            void Octree::insert(Int_position position, int size, int value) {
                if (m_size <= size) {
                    m_value = value;
                    return;
                }

                if (isSolid() && m_value == value) {
                    return;
                }

                if (isSolid()) {
                    for (int X = 0; X < 2; X++) {
                        for (int Y = 0; Y < 2; Y++) {
                            for (int Z = 0; Z < 2; Z++) {
                                int index = 0;
                                int x = m_size / 2;
                                int y = m_size / 2;
                                int z = m_size / 2;

                                //X
                                if (X == 1) {
                                    x += (m_size / 2) * .5;
                                    index++;
                                }
                                else {
                                    x += (m_size / 2) * -.5;
                                }

                                //Y
                                if (Y == 1) {
                                    y += (m_size / 2) * .5;
                                    index += 2;
                                }
                                else {
                                    y += (m_size / 2) * -.5;
                                }

                                //Z
                                if (Z == 1) {
                                    z += (m_size / 2) * .5;
                                    index += 4;
                                }
                                else {
                                    z += (m_size / 2) * -.5;
                                }

                                m_children[index] = new OctreeNode(SmallPosition(x, y, z), m_size / 2, m_value, nullptr);
                            }
                        }
                    }
                }

                //Get index
                int index = 0;
                //X
                if (position.x >= m_size / 2) {
                    index++;
                }

                //Y
                if (position.y >= m_size / 2) {
                    index += 2;
                }

                //Z
                if (position.z >= m_size / 2) {
                    index += 4;
                }

                m_children[index]->insert(SmallPosition(position.x, position.y, position.z), size, value);

            }

            bool Octree::isSolid() {
                if (m_children[0] == nullptr) {
                    return true;
                }

                return false;
            }


            Octree::~Octree() {

            }


        }
    }
}

OctreeNode.h

#pragma once

#include "ToolBox.h"

using namespace kaarez::toolBox;


namespace kaarez {
    namespace world {
        namespace chunk {

            class OctreeNode {
            public:
                OctreeNode(SmallPosition position, int size, int value, OctreeNode* parent);
                ~OctreeNode();

                int getValue(SmallPosition position);
                bool insert(SmallPosition position, int size, int value);

                bool isSolid();
                OctreeNode* m_children[8]{};

                int m_size;
                SmallPosition m_position;
                int m_value;
            private:
                OctreeNode* m_parent;


                bool compress(SmallPosition position, int value);

            };


        }
    }
}

OctreeNode.cpp

#include "OctreeNode.h"

namespace kaarez {
    namespace world {
        namespace chunk {

            OctreeNode::OctreeNode(SmallPosition position, int size, int value, OctreeNode* parent) : m_position(position), m_parent(parent) {
                m_value = value;
                m_size = size;

            }



            int OctreeNode::getValue(SmallPosition position) {
                if (isSolid()) {
                    return m_value;
                }

                //Get index
                int index = 0;
                //X
                if (position.x >= m_position.x) {
                    index++;
                }

                //Y
                if (position.y >= m_position.y) {
                    index += 2;
                }

                //Z
                if (position.z >= m_position.z) {
                    index += 4;
                }

                return m_children[index]->getValue(position);
            }



            bool OctreeNode::insert(SmallPosition position, int size, int value) {
                if (m_size <= size) {
                    m_value = value;
                    return true;
                }

                if (isSolid() && m_value == value) {
                    return true;
                }

                if (compress(position, value)) {
                    return true;
                }

                if (isSolid()) {
                    bool tryCompress = true;

                    for (int X = 0; X < 2; X++) {
                        for (int Y = 0; Y < 2; Y++) {
                            for (int Z = 0; Z < 2; Z++) {
                                int index = 0;
                                int x = m_position.x;
                                int y = m_position.y;
                                int z = m_position.z;

                                //X
                                if (X == 1) {
                                    x += (m_size / 2) * .5;
                                    index++;
                                }
                                else {
                                    x += (m_size / 2) * -.5;
                                }

                                //Y
                                if (Y == 1) {
                                    y += (m_size / 2) * .5;
                                    index += 2;
                                }
                                else {
                                    y += (m_size / 2) * -.5;
                                }

                                //Z
                                if (Z == 1) {
                                    z += (m_size / 2) * .5;
                                    index += 4;
                                }
                                else {
                                    z += (m_size / 2) * -.5;
                                }

                                m_children[index] = new OctreeNode(SmallPosition(x, y, z), m_size / 2, m_value, this);
                            }
                        }
                    }
                }

                //Get index
                int index = 0;
                //X
                if (position.x >= m_position.x) {
                    index++;
                }

                //Y
                if (position.y >= m_position.y) {
                    index += 2;
                }

                //Z
                if (position.z >= m_position.z) {
                    index += 4;
                }

                if (m_children[index]->insert(position, size, value)) {
                    bool compression = true;
                    for (int i = 0; i < 8; i++) {
                        if (!m_children[i]->isSolid()) {
                            compression = false;
                        }

                        if (value != m_children[i]->m_value) {
                            compression = false;
                        }
                    }

                    if (compression) {
                        for (int i = 0; i < 8; i++) {
                            delete m_children[i];
                            m_children[i] = nullptr;
                        }

                        m_value = value;
                        return true;
                    }

                    return false;
                }


                return false;
            }



            bool OctreeNode::compress(SmallPosition position, int value) {
                //Compress if all childs are solid and same value
                if (!isSolid()) {
                    //Get index
                    int index = 0;
                    //X
                    if (position.x >= m_position.x) {
                        index++;
                    }

                    //Y
                    if (position.y >= m_position.y) {
                        index += 2;
                    }

                    //Z
                    if (position.z >= m_position.z) {
                        index += 4;
                    }


                    bool compression = true;
                    for (int i = 0; i < 8; i++) {
                        if (!m_children[i]->isSolid()) {
                            compression = false;
                        }

                        if (i != index) {
                            if (value != m_children[i]->m_value) {
                                compression = false;
                            }
                        }

                    }

                    if (compression) {
                        for (int i = 0; i < 8; i++) {
                            delete m_children[i];
                            m_children[i] = nullptr;
                        }

                        m_value = value;

                        return true;
                    }

                }

                return false;

            }



            bool OctreeNode::isSolid() {
                if (m_children[0] == nullptr) {
                    return true;
                }

                return false;
            }



            OctreeNode::~OctreeNode() {
                if (isSolid()) {
                    for (int i = 0; i < 8; i++) {
                        delete m_children[i];
                        m_children[i] = nullptr;
                    }
                }
            }


        }
    }
}

What improvements could I make? Is there any way to make it more efficient or less memory consuming?

\$\endgroup\$
4
\$\begingroup\$

This code has a lot of duplication:

  • Octree is almost the same as OctreeNode. Probably you want Octree to contain just one, not eight OctreeNodes, and delegate operations to it.
  • There is a function begging for factoring out - indexFromPosition. I can see the same snippet occuring five times in the code!
  • This code:

                for (int X = 0; X < 2; X++) {
                    for (int Y = 0; Y < 2; Y++) {
                        for (int Z = 0; Z < 2; Z++) {
                            int index = 0;
                            int x = m_position.x;
                            int y = m_position.y;
                            int z = m_position.z;
    
                            //X
                            if (X == 1) {
                                x += (m_size / 2) * .5;
                                index++;
                            }
                            else {
                                x += (m_size / 2) * -.5;
                            }
    
                            //Y
                            if (Y == 1) {
                                y += (m_size / 2) * .5;
                                index += 2;
                            }
                            else {
                                y += (m_size / 2) * -.5;
                            }
    
                            //Z
                            if (Z == 1) {
                                z += (m_size / 2) * .5;
                                index += 4;
                            }
                            else {
                                z += (m_size / 2) * -.5;
                            }
    
                            m_children[index] = new OctreeNode(SmallPosition(x, y, z), m_size / 2, m_value, this);
                        }
                    }
                }
    

    Can become something like:

                  int shift = (m_size / 2) * .5;
                  int shifts[] =  { shift, -shift };
                  for ( int x_shift : shifts ) { // I use C++11 range for, but you can still iterate X over [0, 1] indicies and x_shift = shifts[X];
                      for ( int y_shift : shifts ) {
                          for ( int z_shift : shifts ) {
                              SmallPosition new_position = m_position;
                              new_position.x += x_shift;
                              new_position.y += y_shift;
                              new_position.z += z_shift;
                              int index = indexFromPosition(new_position); // Remember we factored this function out?
                              // I'm not happy about new operator here, but we'll deal with it later. 
                              m_children[index] = new OctreeNode(new_position, m_size / 2, m_value, this);  
                          }
                      }
                  }
    

    We elimimated most of duplication and made code more consize.


Make m_children a std::vector. This will spare you unneeded code in destructors (and Octree destructor is already leaking nodes). On top of that you will gain a little bit of efficiency: - std::vector implementations tend to be of size of 3-4 pointers, while array is of size of 8 pointers. - When inserting new node, current code calls new (and hence memory allocation) eight times. With std::vector you should just call reserve(8) which would result in one allocation.

And just to be clear. I am speaking of std::vector<OctreeNode>, not std::vector<OctreeNode*>.

In general, prefer containers and smart pointers to manual memory management with new and delete.

Last thing I want to talk about is m_parent member. There is no actual use of it. Probably it could be helpful for some traversing algorithms, but in this case there should be public interface to access it. Until you figure it out, i recommend eliminate this member from the code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.