在没有新运算符的情况下细分四叉树

Question

在我见过的每个四叉树实现中，细分方法总是使用 new 运算符来创建子单元格。

有办法避免吗？因为我每帧都重新创建四叉树以便轻松更新它，但是每帧使用 new 和 delete 大约 200 ~ 300 次会降低我的性能。

这是我的实现：

void UQuadtree::subdivide(Quad * Node)
{
    float HalfExtent = Node->Extent/2;
    FVector2D Center = Node->Center;

    Node->NW = new Quad(FVector2D(Center.X + HalfExtent, Center.Y - HalfExtent), HalfExtent);
    Node->NE = new Quad(FVector2D(Center.X + HalfExtent, Center.Y + HalfExtent), HalfExtent);
    Node->SW = new Quad(FVector2D(Center.X - HalfExtent, Center.Y - HalfExtent), HalfExtent);
    Node->SE = new Quad(FVector2D(Center.X - HalfExtent, Center.Y + HalfExtent), HalfExtent);
}

bool UQuadtree::insert(FVector2D* point, Quad * Node)
{
    if (!ConstructBox2D(Node->Center, Node->Extent).IsInside(*point)) 
    {
        return false;
    }
    if (Node->Points.Num() < Capacity) {
        Node->Points.Add(point);

        return true;
    }
    if (Node->NW == nullptr) {
        subdivide(Node);
    }
    if (insert(point, Node->NW)) { return true; }
    if (insert(point, Node->NE)) { return true; }
    if (insert(point, Node->SW)) { return true; }
    if (insert(point, Node->SE)) { return true; }

    return false;
}

在使用 clear() 函数删除整棵树之后，我对每帧要添加到四叉树的每个点（大约 1000 个）都执行此操作。

void UQuadtree::clear() {

    if (root->NW != nullptr) {
        delete root->NW;
        root->NW = nullptr;
        delete root->NE;
        root->NE = nullptr;
        delete root->SW;
        root->SW = nullptr;
        delete root->SE;
        root->SE = nullptr;
    }
}

（顺便说一句，我在 UE4 中实现了它）。

Answer 1

我想演示一个非常简单的内存池。（在我的评论中，我为此推荐了一个向量列表，这就是我想在下面详细说明的内容。）

首先，我做了一些约束，用来简化概念：

节点提供默认构造函数。
不需要就地构建节点。
节点连续创建并一次性全部释放。

所以，我从 template class PoolT:

开始

#include <iomanip>
#include <iostream>
#include <vector>
#include <list>

template <typename ELEMENT, size_t N = 16>
class PoolT {
  private:
    typedef std::list<std::vector<ELEMENT> > Data;
    Data _data;
    typename Data::iterator _iterEnd;
    size_t _n;
    size_t _size, _capacity;

  public:
    PoolT():
      _data(), _iterEnd(_data.end()), _n(N),
      _size(0), _capacity(0)
    {
      std::cout << "  PoolT<ELEMENT>::PoolT()\n";
    }
    ~PoolT() = default;

    PoolT(const PoolT&) = delete;
    PoolT& operator=(const PoolT&) = delete;

    ELEMENT& getNew()
    {
      if (_n >= N && _iterEnd != _data.end()) {
        _n = 0; ++_iterEnd;
        std::cout << "  PoolT<ELEMENT>::getNew(): switching to next chunk.\n";
      }
      if (_iterEnd == _data.end()) {
        std::cout << "  PoolT<ELEMENT>::getNew(): Chunks exhausted. Allocating new chunk of size " << N << ".\n";
        _iterEnd = _data.insert(_iterEnd, std::vector<ELEMENT>(N));
        _capacity += N;
        _n = 0;
      }
      std::cout << "  PoolT<ELEMENT>::getNew(): returning ELEMENT " << _n << " of current chunk.\n";
      return (*_iterEnd)[++_size, _n++];
    }

    void reset()
    {
      _size = _n = 0; _iterEnd = _data.begin();
    }

    size_t size() const { return _size; }
    size_t capacity() const { return _capacity; }
};

块实现为 std::vector<ELEMENT>，块列表只是 std::list<std::vector<ELEMENT>>。

ELEMENT& getNew()是从池中请求新元素的函数。

如果当前块用完，则切换到下一个块。

如果它是最后一个块，则分配一个新块并将其添加到列表中。

之后，从块中返回下一个元素。

请注意，我禁用了 PoolT 的复制构造函数和复制赋值运算符。我认为复制内存池没有任何意义。因此，如果它是意外完成的（例如，当打算通过引用将其作为参数传递给函数时忘记插入 &），这将导致编译器错误。

对于元素，我制作了一个 struct Node 类似于 OPs 四叉树节点的一部分：

struct Node {
  Node *pNW, *pNE, *pSW, *pSE;

  Node(): pNW(nullptr), pNE(nullptr), pSW(nullptr), pSE(nullptr) { }
  ~Node() = default;

  Node(const Node&) = delete;
  Node& operator=(const Node&) = delete;

  void clear()
  {
    pNW = pNE = pSW = pSE = nullptr;
  }
};

返回的ELEMENT可能以前用过。因此，之后应该将其重置为初始状态。为简单起见，我只是创建了一个函数 Node::clear() 将实例重置为初始状态。

我也禁用了Node的复制构造函数和复制赋值运算符。在我的示例中，Node 个实例通过指针相互引用。因此，重新分配他们的存储空间将产生致命的后果。（这会使节点指针悬空。）内存池 PoolT 是在考虑到这一点的情况下构建的。（对于 std::vector 中的意外重新分配，至少需要其中之一（复制构造函数或赋值运算符）。因此，在这种情况下我会遇到编译器错误。）

Node的内存池：

typedef PoolT<Node> NodePool;

还有一个小测试套件，用于展示实际操作：

Node* fill(NodePool &nodePool, int depth)
{
  Node *pNode = &nodePool.getNew();
  pNode->clear();
  if (--depth > 0) {
    pNode->pNW = fill(nodePool, depth);
    pNode->pNE = fill(nodePool, depth);
    pNode->pSW = fill(nodePool, depth);
    pNode->pSE = fill(nodePool, depth);
  }
  return pNode;
}

void print(std::ostream &out, const Node *pNode, int depth = 0)
{
  out << (const void*)pNode << '\n';
  if (!pNode) return;
  ++depth;
  if (pNode->pNW) {
    out << std::setw(2 * depth) << "" << "pNW: "; print(out, pNode->pNW, depth);
  }
  if (pNode->pNE) {
    out << std::setw(2 * depth) << "" << "pNE: "; print(out, pNode->pNE, depth);
  }
  if (pNode->pSW) {
    out << std::setw(2 * depth) << "" << "pSW: "; print(out, pNode->pSW, depth);
  }
  if (pNode->pSE) {
    out << std::setw(2 * depth) << "" << "pSE: "; print(out, pNode->pSE, depth);
  }
}

#define DEBUG(...) std::cout << #__VA_ARGS__ << ";\n"; __VA_ARGS__

int main()
{
  DEBUG(NodePool nodePool);
  std::cout
    << "nodePool.capacity(): " << nodePool.capacity() << ", "
    << "nodePool.size(): " << nodePool.size() << '\n';
  DEBUG(Node *pRoot = nullptr);
  DEBUG(pRoot = fill(nodePool, 2));
  DEBUG(std::cout << "pRoot: "; print(std::cout, pRoot));
  std::cout
    << "nodePool.capacity(): " << nodePool.capacity() << ", "
    << "nodePool.size(): " << nodePool.size() << '\n';
  DEBUG(pRoot = nullptr);
  DEBUG(nodePool.reset());
  std::cout
    << "nodePool.capacity(): " << nodePool.capacity() << ", "
    << "nodePool.size(): " << nodePool.size() << '\n';
  DEBUG(pRoot = fill(nodePool, 3));
  DEBUG(std::cout << "pRoot: "; print(std::cout, pRoot));
  std::cout
    << "nodePool.capacity(): " << nodePool.capacity() << ", "
    << "nodePool.size(): " << nodePool.size() << '\n';
  return 0;
}

编译和测试：

NodePool nodePool;
  PoolT<ELEMENT>::PoolT()
nodePool.capacity(): 0, nodePool.size(): 0
Node *pRoot = nullptr;
pRoot = fill(nodePool, 2);
  PoolT<ELEMENT>::getNew(): Chunks exhausted. Allocating new chunk of size 16.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 0 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 1 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 2 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 3 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 4 of current chunk.
std::cout << "pRoot: "; print(std::cout, pRoot);
pRoot: 0xcb4c30
  pNW: 0xcb4c50
  pNE: 0xcb4c70
  pSW: 0xcb4c90
  pSE: 0xcb4cb0
nodePool.capacity(): 16, nodePool.size(): 5
pRoot = nullptr;
nodePool.reset();
nodePool.capacity(): 16, nodePool.size(): 0
pRoot = fill(nodePool, 3);
  PoolT<ELEMENT>::getNew(): returning ELEMENT 0 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 1 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 2 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 3 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 4 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 5 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 6 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 7 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 8 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 9 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 10 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 11 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 12 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 13 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 14 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 15 of current chunk.
  PoolT<ELEMENT>::getNew(): switching to next chunk.
  PoolT<ELEMENT>::getNew(): Chunks exhausted. Allocating new chunk of size 16.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 0 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 1 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 2 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 3 of current chunk.
  PoolT<ELEMENT>::getNew(): returning ELEMENT 4 of current chunk.
std::cout << "pRoot: "; print(std::cout, pRoot);
pRoot: 0xcb4c30
  pNW: 0xcb4c50
    pNW: 0xcb4c70
    pNE: 0xcb4c90
    pSW: 0xcb4cb0
    pSE: 0xcb4cd0
  pNE: 0xcb4cf0
    pNW: 0xcb4d10
    pNE: 0xcb4d30
    pSW: 0xcb4d50
    pSE: 0xcb4d70
  pSW: 0xcb4d90
    pNW: 0xcb4db0
    pNE: 0xcb4dd0
    pSW: 0xcb4df0
    pSE: 0xcb4e10
  pSE: 0xcb4e70
    pNW: 0xcb4e90
    pNE: 0xcb4eb0
    pSW: 0xcb4ed0
    pSE: 0xcb4ef0
nodePool.capacity(): 32, nodePool.size(): 21

Live Demo on coliru

我使用了相当小的 N = 16 作为默认块大小。我这样做是为了显示大块的耗尽，而不必过多地放大样本大小。对于“生产性”使用，我当然会推荐更高的值。

当然，有很多潜力可以使它更复杂，获得重载 new 和 delete 等 C++ 功能，就地构造（例如 std::vector::emplace()) 或其他令人兴奋的事情。

在没有新运算符的情况下细分四叉树

Subdivide Quadtree without the new operator

c++

memory-management

quadtree