2
I need to divide space into cells. Each cell should be approximately the size of the particle radius so that a particle does not occupy more than 4 cells as in the illustration below:
The r-ray particle can occupy up to 4 cells. Its own cell (where the center (x,y) of the particle is located) and 3 other neighboring cells.
Reason for optimization: With the current code, when I increase the amount of particles, the program becomes very slow and the collisions between them do not occur in a fluid way.
canvas.cpp
#include "canvas.h"
#include <QPainter>
canvas::canvas(QWidget *parent) :
QWidget(parent)
{
m_particulas.resize(50);
int n = m_particulas.size();
for(int i = 0 ; i<n ; ++i)
{
m_particulas[i].init();
}
startTimer(5);
}
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, 2, 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();
for(int i = 0 ; i<n ; ++i)
{
Particula &pi = m_particulas[i];
for(int j = 0 ; j < n ; ++j)
{
if (i == j) continue; //(MODO 2)
Particula &pj = m_particulas[j];
if (pi.testa_colisao(pj))
{
pi.calcula_colisao(pj);
}
}
}
update();
}
particle.cpp
#include "particula.h"
#include <stdlib.h> /* srand, rand */
#include <cmath>
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 dist2 = dx*dx + dy*dy;
double somaRaios = r() + p.r();
return dist2 <= somaRaios * somaRaios;
}
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);
do
{
andar();
p.andar();
} while (testa_colisao(p));
}
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
}
I don’t know if I got the question right: you don’t know how to check the collision using this concept of partitions, is that it? Ah, maybe you don’t need to split the space on that level. You’ve tried to split it into 4 or 16 large square areas?
– Luiz Vieira
I couldn’t see how your code works, it’s a little complex. I would do it using concepts of analytical geometry with the circle equation, since you have the radius, the center X and the center Y. Then you would see lines that are boring to the circumference, ignoring the tangent lines and those that are outside. Maybe by using point-to-line distance and comparing the radius with some things in the circumference equation, you get a very small, readable, fast code.
– Metalus
I want to do it in a way that it is no longer necessary to calculate the distance of a particle to all other particles, but only to those that are near. Thus avoiding slowness in collisions. The following image is an example: http://goo.gl/D1B5lV
– Marlon Paranhos
What is the order of magnitude we are talking about? How many particles do you want to use and how large is your mesh?
– Guilherme Bernal
Something around 5,000 particles with a radius between 5 and 10.
– Marlon Paranhos