Colisão bola a bola - detecção e manuseio

266

Com a ajuda da comunidade Stack Overflow, escrevi um simulador de física bastante básico, mas divertido.

texto alternativo

Você clica e arrasta o mouse para lançar uma bola. Ele vai ricochetear e eventualmente parar no "chão".

Meu próximo grande recurso que quero adicionar é colisão bola a bola. O movimento da bola é dividido em machado e vetor de velocidade y. Tenho gravidade (pequena redução do vetor y a cada passo), tenho atrito (pequena redução dos dois vetores a cada colisão com uma parede). As bolas se movem honestamente de uma maneira surpreendentemente realista.

Eu acho que minha pergunta tem duas partes:

  1. Qual é o melhor método para detectar colisão de bola em bola?
    Eu só tenho um loop O (n ^ 2) que itera sobre cada bola e verifica todas as outras bolas para ver se o raio se sobrepõe?
  2. Que equações eu uso para lidar com a bola em colisões? Física 101
    Como isso afeta as duas bolas na velocidade dos vetores x / y? Qual é a direção resultante em que as duas bolas seguem? Como aplico isso a cada bola?

texto alternativo

Lidar com a detecção de colisão das "paredes" e as alterações vetoriais resultantes foi fácil, mas vejo mais complicações com colisões bola-bola. Com paredes, eu simplesmente tive que pegar o negativo do vetor x ou y apropriado e ele seguiria na direção correta. Com bolas, não acho que seja assim.

Alguns esclarecimentos rápidos: por simplicidade, estou bem com uma colisão perfeitamente elástica no momento, também todas as minhas bolas têm a mesma massa agora, mas posso mudar isso no futuro.


Edit: Recursos que achei úteis

Física da 2d Ball com vetores: Colisões bidimensionais sem trigonometria.pdf
Exemplo de detecção de colisão da 2d Ball: Adicionando detecção de colisão


Sucesso!

Tenho a detecção e resposta de colisão de bola funcionando muito bem!

Código relevante:

Detecção de colisão:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

Isso verificará colisões entre todas as bolas, mas ignorará verificações redundantes (se você precisar verificar se a bola 1 colide com a bola 2, não será necessário verificar se a bola 2 colide com a bola 1. Além disso, ignora a verificação de colisões consigo mesma )

Então, na minha classe de bola, tenho meus métodos colliding () e resolveCollision ():

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

Código Fonte: Fonte completa para o colisor de bola em bola.

Se alguém tiver alguma sugestão de como melhorar este simulador básico de física, avise-me! Uma coisa que ainda tenho que acrescentar é o momento angular, para que as bolas rolem mais realisticamente. Alguma outra sugestão? Deixe um comentário!

mmcdole
fonte
16
Eu não acho que esse algoritmo é bom o suficiente, porque se suas bolas estão se movendo muito rápido (ex: mais rápido, então 2 raio * por frame, uma bola pode passar por outra bola sem quaisquer colisões.
Benji Mizrahi
@Simulcal, você pode fazer o upload do seu código-fonte novamente (todos os links filedropper.com parecem estar quebrados). Além disso, você poderia colocar o arquivo pdf que você tem de [geocities.com/vobarian/2dcollisions/2dcollisions.pdf] como GeoCities foi desligada recentemente
bguiz
1
Aqui está um link para a última versão do BallBounce em que trabalhei: dl.dropbox.com/u/638285/ballbounce.rar
mmcdole
@ Para todos os que contribuíram: Você pode lançar alguma luz para transformar esse mecanismo em 3D. Como esse ótimo mecanismo também pode funcionar no Java3D.
static void main
2
A linha Vector2d impulse = mtd.multiply(i);deve ser * o vetor mtd normalizado. Algo como:Vector2d impulse = mtd.normalize().multiply(i);
klenwell

Respostas:

117

Para detectar se duas bolas colidem, basta verificar se a distância entre seus centros é inferior a duas vezes o raio. Para fazer uma colisão perfeitamente elástica entre as esferas, você só precisa se preocupar com o componente da velocidade que está na direção da colisão. O outro componente (tangente à colisão) permanecerá o mesmo para as duas esferas. Você pode obter os componentes da colisão criando um vetor unitário apontando na direção de uma bola para a outra e, em seguida, levando o produto escalar com os vetores de velocidade das bolas. Você pode então conectar esses componentes a uma equação de colisão 1D perfeitamente elástica.

A Wikipedia tem uma boa resumo de todo o processo . Para bolas de qualquer massa, as novas velocidades podem ser calculadas usando as equações (onde v1 e v2 são as velocidades após a colisão e u1, u2 são anteriores):

v_ {1} = \ frac {u_ {1} (m_ {1} -m_ {2}) + 2m_ {2} u_ {2}} {m_ {1} + m_ {2}}

v_ {2} = \ frac {u_ {2} (m_ {2} -m_ {1}) + 2m_ {1} u_ {1}} {m_ {1} + m_ {2}}

Se as bolas tiverem a mesma massa, as velocidades são simplesmente alteradas. Aqui está um código que escrevi que faz algo semelhante:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

Quanto à eficiência, Ryan Fox está certo, considere dividir a região em seções e, em seguida, fazer a detecção de colisões em cada seção. Lembre-se de que as bolas podem colidir com outras bolas nos limites de uma seção, portanto, isso pode tornar seu código muito mais complicado. A eficiência provavelmente não será importante até que você tenha várias centenas de bolas. Para pontos de bônus, você pode executar cada seção em um núcleo diferente ou dividir o processamento de colisões em cada seção.

Jay Conrod
fonte
2
Digamos que as massas das duas bolas não sejam iguais. Como isso afeta o vetor entre as bolas?
Mmdole
3
Já faz um tempo desde a série 12, mas acho que eles obtêm uma proporção do momento correspondente à proporção das massas.
Ryan Fox
6
@ Jay, apenas para salientar .. que uma imagem de equação que você adicionou é para uma colisão unidimensional, não bidimensional.
mmcdole 6/12/08
@simucal. não é verdade ... u e v são vetores nessa equação. Ou seja, eles têm componentes x, y (e z).
Andrew Rollings
2
@ Simucal, você está certo, eles são para o caso unidimensional. Para mais dimensões, basta usar os componentes da velocidade que estão alinhados com a colisão (aci, bci no código). Os outros componentes são ortogonais à colisão e não mudam, portanto você não precisa se preocupar com eles.
Jay Conrod 06/12/08
48

Bem, anos atrás, eu fiz o programa como você apresentou aqui.
Há um problema oculto (ou muitos, depende do ponto de vista):

  • Se a velocidade da bola for muito alta, você poderá perder a colisão.

E também, quase em 100% dos casos, suas novas velocidades estarão erradas. Bem não velocidades , mas posições . Você precisa calcular novas velocidades com precisão no lugar correto. Caso contrário, você apenas muda as bolas com uma pequena quantia de "erro", disponível na etapa discreta anterior.

A solução é óbvia: você precisa dividir o timestep para que primeiro mude para o local correto, depois colida e depois mude pelo resto do tempo.

avp
fonte
Se mudar de posição timeframelength*speed/2, as posições serão estatisticamente fixas.
Nakilon
@ Nakilon: não, isso ajuda apenas em alguns casos, mas geralmente é possível perder a colisão. E a probabilidade de perder a colisão aumenta com o tamanho do comprimento do intervalo de tempo. A propósito, parece que Aleph demonstrou a solução correta (embora eu apenas a tenha consultado).
avp
1
@ Avp, eu não era sobre Se a velocidade da bola é muito alta, você pode perder a colisão. , mas suas novas posições estarão erradas . Por causa da colisão estar sendo detectada um pouco mais tarde, do que realmente colidiram, se subtrairtimeframelength*speed/2 dessa posição, a precisão aumentará duas vezes.
Nakilon
20

Você deve usar o particionamento de espaço para resolver esse problema.

Leia sobre particionamento de espaço binário e quadríceps

grepsedawk
fonte
4
Em vez de particionar espaço, um algoritmo de varredura e remoção não funcionaria melhor? as bolas estão se movendo rapidamente, portanto, qualquer particionamento precisará ser atualizado com frequência, incorrendo em sobrecarga. Uma varredura e remoção pode encontrar todos os pares de colisão em O (n log n), sem nenhuma estrutura de dados transitória. Aqui está um bom tutorial para o básico
HugoRune
13

Como um esclarecimento à sugestão de Ryan Fox de dividir a tela em regiões e apenas verificar colisões dentro de regiões ...

por exemplo, divida a área de jogo em uma grade de quadrados (que arbitrariamente dirá que são de 1 unidade de comprimento por lado) e verifique se há colisões em cada quadrado da grade.

Essa é absolutamente a solução correta. O único problema com ele (como outro pôster apontou) é que colisões entre fronteiras são um problema.

A solução para isso é sobrepor uma segunda grade em um deslocamento vertical e horizontal de 0,5 unidade à primeira.

Então, quaisquer colisões que ultrapassem os limites da primeira grade (e, portanto, não sejam detectadas) estarão dentro dos quadrados da segunda grade. Contanto que você acompanhe as colisões que já tratou (como é provável que haja alguma sobreposição), não precisa se preocupar em lidar com casos extremos. Todas as colisões estarão dentro de um quadrado de grade em uma das grades.

Andrew Rollings
fonte
1 para uma solução mais exacta, e para contrariar a unidade covarde-por downvoter
Steven A. Lowe
1
essa é uma boa ideia. Eu fiz isso uma vez e verifiquei a célula atual e todas as células vizinhas, mas seu método é mais eficiente. Outra maneira em que pensei é verificar a célula atual e, em seguida, verificar se ela se cruza com os limites das células atuais e, se for o caso, verificar objetos nessa célula vizinha.
LoveMeSomeCode 27/07/2009
10

Uma boa maneira de reduzir o número de verificações de colisão é dividir a tela em seções diferentes. Você só compara cada bola com as bolas na mesma seção.

Ryan Fox
fonte
5
Correção: você precisa verificar colisões com as mesmas seções adjacentes AND
rint
7

Uma coisa que eu vejo aqui para otimizar.

Embora eu concorde que as bolas batem quando a distância é a soma de seus raios, nunca se deve calcular essa distância! Em vez disso, calcule o quadrado e trabalhe dessa maneira. Não há razão para essa operação cara de raiz quadrada.

Além disso, depois de encontrar uma colisão, você deve continuar a avaliar as colisões até que não restem mais. O problema é que o primeiro pode causar outros que precisam ser resolvidos antes que você obtenha uma imagem precisa. Considere o que acontece se a bola bater na bola na borda? A segunda bola atinge a borda e imediatamente se recupera na primeira bola. Se você bater em uma pilha de bolas no canto, poderá ter algumas colisões que precisam ser resolvidas antes que você possa repetir o próximo ciclo.

Quanto ao O (n ^ 2), tudo o que você pode fazer é minimizar o custo de rejeitar aqueles que perdem:

1) Uma bola que não está se movendo não pode acertar nada. Se houver um número razoável de bolas espalhadas pelo chão, isso pode economizar muitos testes. (Observe que você ainda deve verificar se algo atingiu a bola estacionária.)

2) Algo que pode valer a pena: Divida a tela em várias zonas, mas as linhas devem ficar confusas - as bolas na borda de uma zona são listadas como estando em todas as zonas relevantes (podem ser 4). Eu usaria uma grade 4x4, armazenar as zonas como bits. Se um AND das zonas de duas esferas retornar zero, final do teste.

3) Como eu mencionei, não faça a raiz quadrada.

Loren Pechtel
fonte
Obrigado pelas informações na ponta da raiz quadrada. Não sabia sobre sua natureza cara quando comparado à praça.
mmcdole 6/12/08
Outra otimização seria encontrar bolas que não estão nem perto de outras bolas. Isso funcionaria de maneira confiável apenas se as velocidades das bolas estivessem restritas.
Brad Gilbert
1
Não concordo em procurar bolas isoladas. Isso é tão caro quanto detectar a colisão. Para melhorar as coisas, você precisa de algo menor que O (n) para a bola em questão.
Loren Pechtel 07/12/08
7

Encontrei uma excelente página com informações sobre detecção e resposta de colisões em 2D.

http://www.metanetsoftware.com/technique.html

Eles tentam explicar como isso é feito do ponto de vista acadêmico. Eles começam com a simples detecção de colisão de objeto a objeto e passam para a resposta de colisão e como aumentá-la.

Editar: Link atualizado

Markus Jarderot
fonte
3

Você tem duas maneiras fáceis de fazer isso. Jay cobriu a maneira exata de checar a partir do centro da bola.

A maneira mais fácil é usar uma caixa delimitadora retangular, defina o tamanho da sua caixa como 80% do tamanho da bola e você simulará a colisão muito bem.

Adicione um método à sua aula de bola:

public Rectangle getBoundingRect()
{
   int ballHeight = (int)Ball.Height * 0.80f;
   int ballWidth = (int)Ball.Width * 0.80f;
   int x = Ball.X - ballWidth / 2;
   int y = Ball.Y - ballHeight / 2;

   return new Rectangle(x,y,ballHeight,ballWidth);
}

Então, no seu loop:

// Checks every ball against every other ball. 
// For best results, split it into quadrants like Ryan suggested. 
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
    Rectangle r1 = balls[i].getBoundingRect();

    for (int k = 0; k < balls.count; k++)
    {

        if (balls[i] != balls[k])
        {
            Rectangle r2 = balls[k].getBoundingRect();

            if (r1.Intersects(r2))
            {
                 // balls[i] collided with balls[k]
            }
        }
    }
}
FlySwat
fonte
1
Isso faria as bolas se chocarem 20% em colisões horizontais e verticais. Também pode usar caixas delimitadoras circulares, pois a diferença de eficiência é insignificante. Além disso, (x-width)/2deveria ser x-width/2.
Markus Jarderot 06/12/08
Boa chamada no erro de precedência. Você verá que a maioria dos jogos 2D usa caixas delimitadoras retangulares em formas não retangulares porque é rápida, e o usuário quase nunca nota.
FlySwat
Você pode fazer uma caixa delimitadora retangular; se houver um acerto, marque a caixa delimitadora circular.
Brad Gilbert
1
@ Jonathan Holland, seu loop interno deve ser para (int k = i + 1; ...) Isso eliminará todas as verificações redundantes. (ou seja, checando com colisão de si mesmo e checando bola de colisão1 com bola2 e depois bola2 com bola1).
mmcdole 6/12/08
4
Na verdade, uma caixa delimitadora quadrada é provável que seja pior em termos de performance do que uma caixa delimitadora circular (supondo que você tenha otimizado a raiz quadrada de distância)
Ponkadoodle
3

Eu vejo isso sugerido aqui e ali, mas você também pode fazer um cálculo mais rápido primeiro, como comparar as caixas delimitadoras para sobreposição e, em seguida, fazer uma sobreposição baseada em raio se esse primeiro teste passar.

A matemática da adição / diferença é muito mais rápida para uma caixa delimitadora do que todos os triggers para o raio e, na maioria das vezes, o teste da caixa delimitadora descartará a possibilidade de uma colisão. Mas se você testar novamente com trigonometria, está obtendo os resultados precisos que está buscando.

Sim, são dois testes, mas será mais rápido no geral.

Jason Kleban
fonte
6
Você não precisa de trigonometria. bool is_overlapping(int x1, int y1, int r1, int x2, int y2, int r2) { return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<(r1+r2)*(r1+r2); }
Ponkadoodle 06/07/10
3

Esta KineticModelé uma implementação da abordagem citada em Java.

rots trashgod
fonte
2

Eu implementei esse código em JavaScript usando o elemento HTML Canvas, e ele produziu simulações maravilhosas a 60 quadros por segundo. Comecei a simulação com uma coleção de uma dúzia de bolas em posições e velocidades aleatórias. Descobri que, em velocidades mais altas, uma colisão de relance entre uma bola pequena e uma muito maior fazia com que a bola pequena aparecesse STICK até a borda da bola maior e se movia cerca de 90 graus ao redor da bola maior antes de se separar. (Gostaria de saber se mais alguém observou esse comportamento.)

Alguns registros dos cálculos mostraram que a Distância Mínima de Conversão nesses casos não era grande o suficiente para impedir que as mesmas bolas colidissem na etapa seguinte. Fiz algumas experiências e descobri que poderia resolver esse problema escalando o MTD com base nas velocidades relativas:

dot_velocity = ball_1.velocity.dot(ball_2.velocity);
mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle));
mtd.multplyScalar(mtd_factor);

Eu verifiquei que antes e depois dessa correção, a energia cinética total era conservada para cada colisão. O valor de 0,5 no mtd_factor era aproximadamente o valor mínimo encontrado para sempre fazer com que as bolas se separassem após uma colisão.

Embora essa correção introduza uma pequena quantidade de erro na física exata do sistema, a desvantagem é que agora bolas muito rápidas podem ser simuladas em um navegador sem diminuir o tamanho da etapa de tempo.

Stefan Musarra
fonte
1
sin (..) não é uma função barato
PaulHK