c++ - 在 C++ 中使用单元格列表/瓦片/网格进行碰撞检测的最佳数据结构

Question

我是 C++ 的新手，基于这个问题:Collision detection of huge number of circles我想实现单元格列表，这里也有描述:https://en.wikipedia.org/wiki/Cell_lists从碰撞检测算法中获得更好的性能。围绕这个主题可能有很多不同的算法，但我想关注这个。

现在我正在计算二维区域上 n 个大小相同的球体之间的碰撞。我将该区域划分为形成网格的单元格。网格是表示单元格位置的二维数组，3 是一个 vector ，用于存储当前位于该网格单元格中的球体数量。

std::array<std::array<std::vector<int>, cols>, rows> grid;

我可以通过计算得到每个球在网格中的位置:

row = x/cell_width;
col = y/cell_height;

然后我可以将该球编号添加到相应的单元格中:

grid[row][col].push_back(ball);

然后我检查每个网格单元格中是否有球。如果是，我将所有来自实际单元格和周围单元格的球连接起来形成一个 vector (gridballs)并粗暴检查该组中的碰撞。

for( int i = 1; i <rows; i = i + 1 ){
        for( int j = 1; j <cols; j = j + 1 ){
            if (grid[i][j].size()!=0){ 
                gridballs=grid[i][j];
                int nextx[]={1,1,0,-1,-1,-1,0,1}; 
                int nexty[]={0,1,1,1,0,-1,-1,-1};
                for( int k = 1; k <8; k = k + 1 ){
                    if (grid[i+nextx[k]][j+nexty[k]].size()!=0){   
                        gridballs.insert(gridballs.end(), grid[i+nextx[k]][j+nexty[k]].begin(), grid[i+nextx[k]][j+nexty[k]].end());
                    }
                }
         collisioncheck (gridballs);
        }
    }
}

执行此操作时出现以下问题:

有什么结构比在二维数组中使用 vector 更好？网格中的所有内容总是会发生变化，我想不断添加和重置 vector 会占用大量时间吗？

每次总是包括周围的单元格，我多次检查大量的单元格不会降低很多性能吗？有解决办法还是我错过了什么？

什么是确保我不会对一对球体进行两次测试的有效方法？

非常感谢您的帮助!

Answer 1

首先，你的循环写得很糟糕。而不是:

            gridballs=grid[i][j];
            int nextx[]={1,1,0,-1,-1,-1,0,1}; 
            int nexty[]={0,1,1,1,0,-1,-1,-1};
            for( int k = 1; k <8; k = k + 1 ){
                if (grid[i+nextx[k]][j+nexty[k]].size()!=0){   
                    gridballs.insert(gridballs.end(), grid[i+nextx[k]][j+nexty[k]].begin(), grid[i+nextx[k]][j+nexty[k]].end());
                }
            }

尝试:

balls.clear();
for (int dx=-1; dx<=1; dx++)
    for (int dy=-1; dy<=1; dy++) {
        const std::vector<int>& cell = grid[i+dx][j+dy];
        balls.insert(balls.end(), cell.begin(), cell.end());
    }

其次，使用++i和++j(或i++和j++)代替i = i + 1 和 j = j + 1。

至于你的问题，一个好的碰撞检测结构是quadtree(2d)或octree(3d)。像这样的东西:

class Quadtree {
public:
    Quadtree(const vector<int>& vBalls, Quadtree* parent=NULL);
    int size() const {return nBalls;}
    bool empty() const {return nBalls == 0;}
    bool IsInside(double x, double y, double r) const; // is the ball completely inside the square?
    bool IsOutside(double x, double y, double r) const; // is the ball completely outside the square?
    // ... other member functions
private:
    double xMin, yMin, xMax, yMax; // all balls must be within this square
    vector<int> vBigBalls; // balls which occupy more than one sub-square
    vector<Quadtree> vSubsquares; // 4 subsquares
    int nBalls; // total number of balls in the square and subsquares
    Quadtree* parent; // not sure if you need this
}