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

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

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?

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!

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):

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.

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.

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

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

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.

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.

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.

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

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]
            }
        }
    }
}

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.

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

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.