Best data structure for collision detection using cell lists / tiles /grids in C++

Question

I am new to c++ and based on this question: Collision detection of huge number of circles i want to implement cell lists, also described here: https://en.wikipedia.org/wiki/Cell_lists to get better performance out of an collision detection algorithm. There are probably a lot of different algorithm around this subject but i would like to focus on this one.

Right now i am computing the collision between n spheres with the same size on a 2D area. I divided the area into cells which form a grid. The grid is a 2D array for the cell position and the 3 is a vector to store the number of the spheres which are currently in that grid cell.

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

I can get the position of each ball in the grid by calculating:

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

I can then add that ball number to the corresponding cell:

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

Then i check for every grid cell if there are balls in it. If yes, i join all the balls from the actual and surrounding cells to form one vector (gridballs) and brute check for collisions in this group.

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);
        }
    }
}

}

Following questions came up while doing this:

What would be a better structure than using vectors in a 2D array? Everything in the grid is always subject to change and i suppose constantly adding and resetting vectors takes up a lot of time?

Dont i loose a lot of performance by checking a lot of cells several times by always including the surrounding cells each time? Is there a way around this or did i miss something?

What would be an efficient way to make sure that i dont test a pair of spheres twice?

Thank you very much for the help!

Answer 1

First, you loop is written horribly. Instead of:

            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());
                }
            }

Try:

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());
    }

Second, use ++i and ++j (or i++ and j++) instead of i = i + 1 and j = j + 1.

As for your question, a good structure for collision detection is quadtree (in 2d) or octree (in 3d). Something like:

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
}