如何优化四叉树递归查询函数，提升粒子模拟运行速度？

我正在学习C++，用熟悉的Java思路开发基于四叉树的粒子集群模拟系统，目的是通过四叉树低成本查询区域内的粒子。目前功能正常，但四叉树查询区域粒子的速度极慢——5000次调用耗时约1秒，5000个粒子跑起来只能到1FPS，完全无法接受。

我试过把vector换成数组，也测试了函数各部分的执行时间，想排查是不是有不必要的对象复制这类新手错误。下面是完整可复现代码：

main.cpp #

#include <string>
#include <iostream>
#include <random>
#include <chrono>
#include <thread>
#include <cmath>

#include "Particle.h"
#include "Quadtree.h"

// Clock
using namespace std::chrono;
using namespace std::this_thread;

// Global constants
const int SCREEN_WIDTH = 640;
const int SCREEN_HEIGHT = 480;
const int desiredFPS = 30;
const int frameTimeMS = int(1000 / (double)desiredFPS);
const int numberOfParticles = 5000;

// Random number generation
std::random_device dev;
std::mt19937 rng(dev());
std::uniform_real_distribution<> dist(0, 1);

Particle particles[numberOfParticles];
Quadtree quadtree = Quadtree(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);

int main(int argc, char* args[])
{
    for (int i = 0; i < numberOfParticles; i++)
    {
        particles[i] = Particle(dist(rng) * SCREEN_WIDTH, dist(rng) * SCREEN_HEIGHT);
    }

    // Clock for making all frames equally long and achieving the desired framerate when possible
    auto lapStartTime = system_clock::now();

    // Main loop
    for (int i = 0; i < 1; i++)
    {
        // Insert the particles into the quadtree
        quadtree = Quadtree(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);
        for (int i = 0; i < numberOfParticles; i++)
        {
            quadtree.insert(&particles[i]);
        }

        double neighbourhoodRadius = 40;
        for (int i = 0; i < numberOfParticles; i++)
        {
            // THIS IS THE PART THAT IS SLOW
            std::vector<Particle*> neighbours = quadtree.getCircle(
                particles[i].x,
                particles[i].y,
                neighbourhoodRadius
            );
        }

        // Update clocks
        auto nextFrameTime = lapStartTime + milliseconds(frameTimeMS);
        sleep_until(nextFrameTime);
        lapStartTime = nextFrameTime;
    }
    return 0;
}

Quadtree.h #

#pragma once

#include <vector>
#include "Particle.h"
#include "Rect.h"

class Quadtree
{
public:
    const static int capacity = 10; // Capacity of any section
    Quadtree(double px, double py, double width, double height);
    Quadtree(Rect r);
    bool insert(Particle* p); // Add a particle to the tree
    std::vector<Particle*> getCircle(double px, double py, double r);
    int numberOfItems(); // Total amount in the quadtree
private:
    std::vector<Particle*> particles; // Particles stored by this section
    std::vector<Quadtree> sections; // Branches (only if split)
    Rect area; // Region occupied by the quadtree
    bool isSplit() { return sections.size() > 0; }
    void split(); // Split the quadtree into 4 branches
};

Quadtree.cpp #

#include <iostream>
#include "Quadtree.h"

Quadtree::Quadtree(double px, double py, double width, double height)
{
    area = Rect(px, py, width, height);
    sections = {};
    particles = {};
}

Quadtree::Quadtree(Rect r)
{
    area = r;
    sections = {};
    particles = {};
}

bool Quadtree::insert(Particle* p)
{
    if (area.intersectPoint(p->x, p->y))
    {
        if (!isSplit() && particles.size() < capacity)
        {
            particles.push_back(p);
        }
        else
        {
            if (!isSplit()) // Capacity is reached and tree is not split yet
            {
                split();
            }

            // That this is a reference is very important!
            // Otherwise a copy of the tree will be modified
            for (Quadtree& s : sections)
            {
                if (s.insert(p))
                {
                    return true;
                }
            }
        }

        return true;
    }
    else
    {
        return false;
    }
}

std::vector<Particle*> Quadtree::getCircle(double px, double py, double r)
{
    std::vector<Particle*> selection = {};
    if (!isSplit())
    {
        // Add all particles from this section that lie within the circle
        for (Particle* p : particles)
        {
            double a = px - p->x;
            double b = py - p->y;
            if (a * a + b * b <= r * r)
            {
                selection.push_back(p);
            }
        }
    }
    else
    {
        // The section is split so add all the particles from the
        // branches together
        for (Quadtree& s : sections)
        {
            // Check if the branch and the circle even have any intersection
            if (s.area.intersectRect(Rect(px - r, py - r, 2 * r, 2 * r)))
            {
                // Get the particles from the branch and add them to selection
                std::vector<Particle*> branchSelection = s.getCircle(px, py, r);
                selection.insert(selection.end(), branchSelection.begin(), branchSelection.end());
            }
        }
    }
    return selection;
}

void Quadtree::split()
{
    sections.push_back(Quadtree(area.getSection(2, 2, 0, 0)));
    sections.push_back(Quadtree(area.getSection(2, 2, 0, 1)));
    sections.push_back(Quadtree(area.getSection(2, 2, 1, 0)));
    sections.push_back(Quadtree(area.getSection(2, 2, 1, 1)));

    std::vector<Particle*> oldParticles{ particles };
    particles.clear();

    for (Particle* p : oldParticles)
    {
        bool success = insert(p);
    }
}

int Quadtree::numberOfItems()
{
    if (!isSplit())
    {
        return particles.size();
    }
    else
    {
        int result = 0;
        for (Quadtree& q : sections)
        {
            result += q.numberOfItems();
        }
        return result;
    }
}

Particle.h #

#pragma once

class Particle {
public:
    double x;
    double y;
    Particle(double px, double py) : x(px), y(py) {}
    Particle() = default;
};

Rect.h #

#pragma once

class Rect
{
public:
    double x;
    double y;
    double w;
    double h;
    Rect(double px, double py, double width, double height);
    Rect() : x(0), y(0), w(0), h(0) {}
    bool intersectPoint(double px, double py);
    bool intersectRect(Rect r);
    Rect getSection(int rows, int cols, int ix, int iy);
};

Rect.cpp #

#include "Rect.h"

Rect::Rect(double px, double py, double width, double height)
{
    x = px;
    y = py;
    w = width;
    h = height;
}

bool Rect::intersectPoint(double px, double py)
{
    return px >= x && px < x + w && py >= y && py < y + h;
}

bool Rect::intersectRect(Rect r)
{
    return x + w >= r.x && y + h >= r.y && x <= r.x + r.w && y <= r.y + r.w;
}

Rect Rect::getSection(int cols, int rows, int ix, int iy)
{
    return Rect(x + ix * w / cols, y + iy * h / rows, w / cols, h / rows);
}

1. 最严重的性能杀手：getCircle的vector频繁复制与分配 #

当前getCircle每次调用都会创建新的vector，递归调用时还要把分支的vector内容插入到当前vector，这会导致大量的内存分配、复制操作，5000次调用下来开销极大。

解决方法： 改成通过引用传递输出vector，避免每次创建新容器：

// 修改Quadtree.h中的函数声明
void getCircle(double px, double py, double r, std::vector<Particle*>& out);

// 修改Quadtree.cpp中的实现
void Quadtree::getCircle(double px, double py, double r, std::vector<Particle*>& out)
{
    if (!isSplit())
    {
        for (Particle* p : particles)
        {
            double a = px - p->x;
            double b = py - p->y;
            if (a * a + b * b <= r * r)
            {
                out.push_back(p);
            }
        }
    }
    else
    {
        Rect circleBounds(px - r, py - r, 2 * r, 2 * r);
        for (Quadtree& s : sections)
        {
            if (s.area.intersectRect(circleBounds))
            {
                s.getCircle(px, py, r, out);
            }
        }
    }
}

// main.cpp中调用时提前复用一个vector
std::vector<Particle*> neighbours;
for (int i = 0; i < numberOfParticles; i++)
{
    neighbours.clear(); // 清空而非重新创建
    quadtree.getCircle(particles[i].x, particles[i].y, neighbourhoodRadius, neighbours);
    // 处理neighbours...
}

2. Rect类的intersectRect函数存在bug #

当前intersectRect的最后一个条件是y <= r.y + r.w，这里应该是y + h <= r.y + r.h，错误的判断会导致不必要的分支查询，增加无效的递归调用。

修复代码：

bool Rect::intersectRect(Rect r)
{
    return x + w >= r.x && y + h >= r.y && x <= r.x + r.w && y + h <= r.y + r.h;
}

3. 避免临时Rect对象的重复创建 #

在getCircle中每次判断分支是否相交时，都会创建Rect(px - r, py - r, 2 * r, 2 * r)，可以提前创建一次，避免重复构造。

4. 四叉树的sections改用指针而非值存储 #

当前std::vector<Quadtree> sections存储的是四叉树对象，复制和销毁时都会有额外开销，改用std::vector<std::unique_ptr<Quadtree>> sections可以减少对象复制的成本，尤其是split的时候。

修改示例：

// Quadtree.h中的private成员
std::vector<std::unique_ptr<Quadtree>> sections;

// split函数实现
void Quadtree::split()
{
    sections.emplace_back(std::make_unique<Quadtree>(area.getSection(2, 2, 0, 0)));
    sections.emplace_back(std::make_unique<Quadtree>(area.getSection(2, 2, 0, 1)));
    sections.emplace_back(std::make_unique<Quadtree>(area.getSection(2, 2, 1, 0)));
    sections.emplace_back(std::make_unique<Quadtree>(area.getSection(2, 2, 1, 1)));

    std::vector<Particle*> oldParticles{ particles };
    particles.clear();

    for (Particle* p : oldParticles)
    {
        bool success = insert(p);
    }
}

// insert和getCircle中的遍历改成
for (auto& s : sections)
{
    if (s->insert(p)) { return true; }
}

5. 减少main中的四叉树赋值开销 #

当前quadtree = Quadtree(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);会先创建临时对象，再赋值给全局的quadtree，改成直接调用clear重置（需要给Quadtree加clear方法），或者直接构造新对象替换：

// 替换main中的赋值为：
quadtree = Quadtree{}; // 利用默认构造，或者加clear方法
// 或者：
quadtree.~Quadtree();
new (&quadtree) Quadtree(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT);

或者更好的方式是把quadtree声明在main函数内，每次循环重新构造，避免全局对象的赋值开销。

内容的提问来源于stack exchange，提问作者Fractal Salamander