体素八叉树

Question

我正在创建一个具有破坏性地形的游戏。在使用平面数组存储块之前，以32^3块为单位。

由于我的目标是细节和长远的视野距离，我当然需要一些LOD。因此，我决定用八叉树代替。内存使用量明显低于平面数组，但访问节点所需时间要长得多。(特别是用于生成网格时检查邻居)

他是孩子的家长。每个块包含一个八叉树。

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


        }
    }
}

我还能做什么改进呢？有没有办法让它更有效率或者更少的内存消耗？

Answer 1

这段代码有很多重复：

• Octree与OctreeNode几乎相同。您可能希望Octree只包含一个，而不是八个OctreeNodes，并将操作委托给它。
• 有一个函数请求分解- indexFromPosition。我可以在代码中看到相同的片段发生五次！
• 这个代码: for (int X= 0；x< 2；X++) { for (int Y= 0；Y< 2；Y++) { for (int Z= 0；z< 2；Z++) { int指数= 0；int x= m_position.x；int y= m_position.y；整数= m_position.z；//X if (X == 1) {x += (m_size / 2) * .5；index++；}{x += (m_size / 2) * -.5；} //Y if (Y == 1) {y += (m_size / 2) * .5；索引+= 2；}{y += (m_size / 2) * -.5；}/Z if (Z == 1) {z += (m_size / 2) * .5；索引+= 4；{z += (m_size / 2) * -.5；} m_children索引 =新OctreeNode(SmallPosition(x，y，z)，m_size / 2，m_value，this)；}}可以变成类似于: int shift = (m_size / 2) * .5；int shifts[] ={ shift，-shift }；for ( int x_shift :shift){ // i使用C++11范围，但仍然可以在0，1指示符上迭代X，x_shift =shiftX；( 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)；//还记得吗? //我对这里的新操作符并不满意，但我们稍后会处理它。m_children索引 =新的OctreeNode(new_position，m_size / 2，m_value，this)}我们消除了大部分重复，使代码更加考虑。

让m_children成为std::vector。这将节省析构函数中不必要的代码(而且Octree析构函数已经泄漏节点)。在此基础上，您将获得一些效率：- std::vector实现的大小通常为3-4个指针，而数组的大小为8个指针。-当插入新节点时，当前代码8次调用new (因此也是内存分配)。使用std::vector，您应该只调用reserve(8)，这将导致一个分配。

我只想说清楚。我说的是std::vector<OctreeNode>，而不是std::vector<OctreeNode*>。

通常，与使用new和delete的手动内存管理相比，更喜欢容器和智能指针。

我最不想谈的就是m_parent会员。它没有实际的用途。它可能对一些遍历算法有帮助，但在这种情况下，应该有公共接口来访问它。在您找出答案之前，我建议将此成员从代码中删除。