c – 没有新运算符的Subdivide Quadtree

发布时间：2020-12-16 07:24:24 所属栏目：百科来源：网络整理

导读：在我见过的Quadtrees的每个实现中,细分方法总是使用new运算符来创建子单元格. 有没有办法避免这种情况？因为我每帧重新创建我的四叉树以便轻松更新它,但是每帧使用新的和删除大约200~300次会破坏我的表现. 这是我的实施： void UQuadtree::subdivide(Quad *

在我见过的Quadtrees的每个实现中,细分方法总是使用new运算符来创建子单元格.

有没有办法避免这种情况？
因为我每帧重新创建我的四叉树以便轻松更新它,但是每帧使用新的和删除大约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,HalfExtent);
    Node->SE = new Quad(FVector2D(Center.X - 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中实现了它).

解决方法

我想演示一个非常简单的内存池. (在我的评论中,我为此推荐了一个向量列表,这是我想在下面详述的内容.)

首先,我做了一些用于简化概念的约束：

>节点提供默认构造函数.
>不需要就地构建节点.
>连续创建节点并立即释放所有节点.

所以,我从模板类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()是从池中请求新ELEMENT的函数.

如果当前块耗尽,则执行到下一个块的切换.

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

然后,从块返回下一个元素.

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

对于元素,我创建了一个类似于OP四叉树节点部分的结构节点：

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,"
    << "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作为默认块大小.我这样做是为了显示块的耗尽,而不必过多地吹掉样品的大小.对于“高效”的使用,我当然会建议更高的价值.

当然,有很多潜力可以使这更复杂,获得C功能,如重载的新和删除,就地构造(例如在std::vector::emplace())或其他令人兴奋的事情.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!