开发碰撞检测用四叉树类引发栈溢出，无法定位问题原因

问题定位 #

1. 栈溢出的根本原因：无限递归分裂 #

• 代码没有设置最小分裂节点尺寸：当多个对象都位于四个子节点的交界区域，所有子节点都会把这些对象判定为属于自己的范围，每次分裂后每个子节点的对象数依然超过maxObjects阈值，触发无限递归分裂，哪怕只有几个对象也会直接爆栈。
• 插入逻辑存在冗余：如果一个对象同时被多个子节点包含，会被插入到所有符合条件的子节点中，进一步放大了子节点的对象计数，加速递归分裂的触发。

2. 内存线性增长的根本原因：严重内存泄漏 #

• 用new创建的Quadtree节点、Rectangle边界对象，都没有对应的delete操作：
  • Clear()方法仅清空了存储节点指针的nodes向量，没有释放每个节点指针指向的堆内存
  • 每个Quadtree实例的bounds指针对象在构造时new创建，析构时没有释放
  • 子节点分裂时创建的所有对象，在节点销毁时都没有回收，内存会随对象插入持续堆积。

3. 额外逻辑缺陷 #

• 碰撞对重复统计：跨节点的对象会在多个子节点中被重复检测，同一个碰撞对可能被多次添加到collidingObjects中。
• 删除逻辑冗余：删除对象时会遍历所有符合范围的子节点，哪怕对象只存在于某一个叶子节点中。

修复方案 #

栈溢出修复 #

1. 给Quadtree类添加minSize属性，分裂前先判断当前节点的宽高是否小于minSize，如果小于则不再分裂，直接把对象存在当前节点即可，从根源上阻断无限递归。
2. 调整插入逻辑：如果一个对象跨了超过2个子节点，就直接存在父节点中，不往下插入子节点，避免同一个对象被多节点重复存储。

内存泄漏修复 #

1. 给Quadtree添加析构函数，释放当前节点的bounds指针，同时遍历nodes释放所有子节点的内存：

Quadtree::~Quadtree()
{
    delete bounds;
    for (auto n : nodes) {
        delete n;
    }
    nodes.clear();
    objects.clear();
}

2. 调整Clear()方法，释放子节点内存后再清空向量：

void Quadtree::Clear()
{
    if (bIsSplit)
    {
        for (auto n : nodes)
        {
            n->Clear();
            delete n;
        }
        this->bIsSplit = false;
    }
    nodes.clear();
    objects.clear();
}

逻辑优化 #

• 碰撞检测可以拆分为两步：先检测当前节点存储的对象之间的碰撞，再检测当前节点对象和所有子节点对象的碰撞，避免重复统计。
• 删除对象时，找到对应的节点后直接返回，不需要遍历所有子节点。

内容的提问来源于stack exchange，提问作者Sam Hirsch