Optimize the collision between particles

Question

I need to optimize as much as possible the algorithm that makes the particles collide, is there anything that can be done to do that? And I also want to add a background image, it’s possible?

Follows code canvas.cpp:

canvas::canvas(QWidget *parent) :
QWidget(parent)
{
m_particulas.resize(20);

int n = m_particulas.size();
for(int i = 0 ; i<n ; ++i)
{
    m_particulas[i].init();
}

startTimer(10);
}

void canvas::paintEvent(QPaintEvent * event)
{
(void) event;

QPainter painter(this);
painter.setWindow(0,0,1000,1000);
painter.setRenderHint(QPainter::Antialiasing, true);
painter.setPen(QPen(Qt::black, 5, Qt::SolidLine, Qt::RoundCap));
painter.setBrush(QBrush(Qt::darkCyan, Qt::SolidPattern));

int n = m_particulas.size();
for(int i = 0 ; i<n ; ++i)
{
    double x = m_particulas[i].x();
    double y = m_particulas[i].y();
    double L = m_particulas[i].r();
    painter.drawEllipse(QPointF(x, y), L, L);
}
}

void canvas::timerEvent(QTimerEvent *event)
{
(void) event;

int n = m_particulas.size();

for(int i = 0 ; i<n ; ++i)
{
    m_particulas[i].andar();
    Particula &pi = m_particulas[i];

    for(int j = 0 ; j < n ; ++j)
    {
        if (i == j) continue;

        Particula &pj = m_particulas[j];

        if (pi.testa_colisao(pj))
        {
            pi.calcula_colisao(pj);
        }
    }
pi.andar();
}
update();
}

particulates.cpp:

Particula::Particula()
{

}

void Particula::init()
{
m_r = 20;

m_x = 900.0*rand()/RAND_MAX + 50;
m_y = 900.0*rand()/RAND_MAX + 50;

m_vx = 2.0 * rand()/RAND_MAX - 1;
m_vy = 2.0 * rand()/RAND_MAX - 1;

double norma = sqrt(m_vx*m_vx + m_vy*m_vy);
m_vx /= norma;
m_vy /= norma;

}

void Particula::normaliza(double &vx, double &vy)
{
double norma = sqrt(vx*vx + vy*vy);
if (norma > 0)
{
    vx /= norma;
    vy /= norma;
}
}

bool Particula::testa_colisao (Particula &p)
{
    double dx = x() - p.x();
    double dy = y() - p.y();
    double dist = sqrt(dx*dx + dy*dy);
    return dist <= r() + p.r();
}

void Particula::calcula_colisao(Particula &p)
{
    double vx = p.x() - x();
    double vy = p.y() - y();
    normaliza(vx,vy);

    p.m_vx += vx;
    p.m_vy += vy;
    normaliza(p.m_vx,p.m_vy);

    m_vx -= vx;
    m_vy -= vy;
    normaliza(m_vx, m_vy);

    while (testa_colisao(p))
    {
        andar();
        p.andar();
    }
}

double Particula::x() const
{
return m_x;
}

double Particula::y() const
{
return m_y;
}

double Particula::r() const
{
return m_r;
}

void Particula::andar()
{
m_x += m_vx;
m_y += m_vy;

if(m_x > 1000-m_r) m_vx *= -1; //inferior - multiplicado por -1 para inverter a direção...
if(m_y > 1000-m_r) m_vy *= -1; //direita
if(m_x < 0+m_r) m_vx *= -1; //esquerda
if(m_y < 0+m_r) m_vy *= -1; //superior
}

Answer 1

For a simple optimization that doesn’t require much change in code, I have three suggestions:

1. You are testing all the particles against all the other two times (i.e. i of [0,n] vs j of [0,n]). Test them only once:

   for(int i = 0 ; i<n ; ++i)
   {
       m_particulas[i].andar();
       Particula &pi = m_particulas[i];
   
       for(int j = i+1 ; j < n ; ++j)
       {
           //if (i == j) continue;
   
           Particula &pj = m_particulas[j];
   

   To make it possible, don’t make the particle walk afterward crash test. Instead, move all the particles first, then start the tests (P.S. why are you moving each particle twice?):

   // Primeiro move
   for (int i = 0 ; i < n ; i++ )
       m_particulas[i].andar();
   
   // Depois testa
   for(int i = 0 ; i<n ; ++i)
   {
       Particula &pi = m_particulas[i];
   
       for(int j = i+1 ; j < n ; ++j) ...
   

2. The calculation of the square root is much slower than multiplication. Square the equation of the whole distance so as to avoid this calculation:

   bool Particula::testa_colisao (Particula &p)
   {
       double dx = x() - p.x();
       double dy = y() - p.y();
       double dist2 = dx*dx + dy*dy;
       double somaRaios = r() + p.r()
       return dist2 <= somaRaios * somaRaios;
   }
   

3. In the calcula_colisao, make the particle walk at least once before testing again if there are collisions (because the first time it runs, it will always return true):

   ...
   normaliza(m_vx, m_vy);
   
   do
   {
       andar();
       p.andar();
   } while (testa_colisao(p));
   

This should avoid all unnecessary work on current code. Based on this, we can move on to more complex optimizations, which involve refactoring the program as a whole. That question on the Soen gives some promising suggestions:

1. Divide your space into smaller areas, and calculate separately for each of these areas. For example, if your scenario is a square of 100x100, create 9 squares of 40x40 (with some intersection between the squares, so that a particle very close to the boundary is tested against the adjacent square) and place each particle in one or more squares. Update this with every move (it should be fast, because it’s just a matter of comparing positions x and y - and if the number of sub-areas is large, you can do a binary search). When testing for collisions, consider only particles that are in the same square.

   • Bonus: this is a good candidate for parallelization - create a separate thread/process to handle each square. Just be careful for the overhead the management of competition does not negate the benefit, this technique is only worth it if the number of particles is quite large.

2. Instead of searching for collisions in each simulation frame, store in another data structure the distances between each particle pair divided by the sum of its velocities. This value corresponds to the minimum number of tables required for there’s a chance these particles collide. If at the time of the impact test this value is greater than or equal to 1, decrease it and do not take the test - because it will definitely return false. If smaller, test and update the collision prediction (which may have increased, decreased, or remained the same, depending on the directions of motion).

   • Note: if your tables do not have a fixed duration, adaptations may be necessary.

   Every time a particle collides with any other, its speed can increase. You could recalculate this entire prediction matrix [for this particle] whenever it happens, but I imagine it would be too costly. A reasonable approximation could simply be to reduce all values proportionately (e.g.: the speed increased from 2 for 3, divide all collision predictions into 1.5).

These techniques can be combined (i.e. divide your space into smaller areas, and make the forecast matrix for each sub-area), and there are other more sophisticated to consider. Just take care to weigh the advantages/disadvantages of each of them according to your particular case. Examples:

• If there are many particles in relation to space, so the collisions will be frequent and localized, the strategy 1 is more interesting and the 2 unnecessary; divide your space into several sub-areas, because it will be rare for a particle to move from one area to another.

• If there are few particles relative to space, and they move quite fast, strategy 1 is useless (because every time a particle will change from sub-area) and 2 is more interesting; keep the prediction matrix in order, so that you do not need to travel-I was all over when I tested each particle.

• Other particular cases will have different impacts on the best strategy.