Problema de detecção de colisão de linhas circulares

11

Atualmente, estou desenvolvendo um clone de desagregação e encontrei um obstáculo ao obter a detecção de colisão entre uma bola (círculo) e um tijolo (polígono convexo) funcionando corretamente. Estou usando um teste de detecção de colisão Circle-Line, em que cada linha representa e aresta no tijolo de polígono convexo.

Na maioria das vezes, o teste de linhas circulares funciona corretamente e os pontos de colisão são resolvidos corretamente.

Detecção de colisão funcionando corretamente.

No entanto, ocasionalmente, meu código de detecção de colisão retorna falso devido a um discriminante negativo quando a bola está realmente cruzando o tijolo.

Falha na detecção de colisão.

Estou ciente da ineficiência com esse método e estou usando caixas delimitadoras alinhadas ao eixo para reduzir o número de tijolos testados. Minha principal preocupação é se há algum erro matemático no meu código abaixo.

/* 
 * from and to are points at the start and end of the convex polygons edge.
 * This function is called for every edge in the convex polygon until a
 * collision is detected. 
 */

bool circleLineCollision(Vec2f from, Vec2f to)
{
    Vec2f lFrom, lTo, lLine;
    Vec2f line, normal;
    Vec2f intersectPt1, intersectPt2;
    float a, b, c, disc, sqrt_disc, u, v, nn, vn;
    bool one = false, two = false;

    // set line vectors
    lFrom = from - ball.circle.centre;      // localised
    lTo = to - ball.circle.centre;          // localised
    lLine = lFrom - lTo;                    // localised
    line = from - to;

    // calculate a, b & c values
    a = lLine.dot(lLine);
    b = 2 * (lLine.dot(lFrom));
    c = (lFrom.dot(lFrom)) - (ball.circle.radius * ball.circle.radius);

    // discriminant
    disc = (b * b) - (4 * a * c);

    if (disc < 0.0f)
    {
        // no intersections
        return false;
    }
    else if (disc == 0.0f)
    {
        // one intersection
        u = -b / (2 * a);

        intersectPt1 = from + (lLine.scale(u));
        one = pointOnLine(intersectPt1, from, to);

        if (!one)
            return false;
        return true;
    }
    else
    {
        // two intersections
        sqrt_disc = sqrt(disc);
        u = (-b + sqrt_disc) / (2 * a);
        v = (-b - sqrt_disc) / (2 * a);
        intersectPt1 = from + (lLine.scale(u));
        intersectPt2 = from + (lLine.scale(v));

        one = pointOnLine(intersectPt1, from, to);
        two = pointOnLine(intersectPt2, from, to);

        if (!one && !two)
            return false;
        return true;
    }
}

bool pointOnLine(Vec2f p, Vec2f from, Vec2f to)
{
    if (p.x >= min(from.x, to.x) && p.x <= max(from.x, to.x) && 
        p.y >= min(from.y, to.y) && p.y <= max(from.y, to.y))
        return true;
    return false;
}
jazzdawg
fonte
Não consigo encontrar nenhuma diferença entre lLine e linha ...
FxIII 10/10
O teste pointOnLine pode ser simplificado e realizado antes do cálculo do ponto real.
FxIII 10/10
como sqrt_disc é calculado?
FxIII 10/10
Desculpe FxIII Eu devo ter ficado um pouco confuso quando localizava meus vetores. Não percebi que os vetores seriam iguais quando subtraídos um do outro. Eu estava limpando meu código um pouco antes de postar e esqueci de colocar sqrt_disc = sqrt(disc);novamente. Muito obrigado por sua resposta abaixo, isso me ajudou muito.
jazzdawg

Respostas:

20

O segmento que vai de A a B pode ser calculado como

P (t) = A + D · t onde D é B - A e t varia de 0 a 1

Agora o círculo está centralizado na origem (mova A e B, se necessário, para colocar o centro na origem) e possui raio r .

Você tem uma interseção se, para alguns t, obtiver que P tem o mesmo comprimento de r ou, equivalentemente, que o comprimento de P ao quadrado seja equivalente a

O comprimento ao quadrado de um vetor é obtido fazendo o produto pontual de um vetor por si mesmo (isso é tão verdadeiro que, se alguém encontrar uma operação adequada para o produto pontual, ele pode definir um novo e consistente conceito de comprimento)

P · P = ( A + D · t) · ( A + D · t) =

Um · Uma + 2 Uma · D t + D · D

Queremos descobrir para qual t temos P · P = r², então acabamos perguntando a nós mesmos quando

Um · Uma + 2 Uma · D t + D · D t² = R

ou quando

D · D t² + 2 Uma · D t + A · Um -r² = 0

esta é a famosa equação quadrática

em² + bt + c = 0

com

a = D · D ; b = 2 A · D ec = A · A -r²

Temos que verificar se o determinante b² - 4ac é positivo e, portanto, encontramos 2 valores de t que nos dão os pontos de interseção P (t).

t deve estar entre 0 e 1, caso contrário, encontramos soluções que ficam na linha que passa por A e B, mas que estão antes de A ou depois de B

[EDITAR]

Como outras perguntas podem encontrar alguma ajuda para essa resposta, decidi tentar simplificar o raciocínio nesta edição usando algumas imagens. condição inicial Esta é a condição inicial. Agora concentre-se no segmento A_B

Segmento que vai de A a B

D é o vetor que move A para B, portanto, se t está entre 0 e 1, D · t é uma "fração adequada" de D, de modo que o ponto A + D · t fica no segmento A_B : os pontos marrons aparecem quando t é entre 0 e 1 e o verde escuro é quando t> 1.

Agora podemos simplificar as coisas se movermos o centro do círculo para a Origem. Isso sempre pode ser feito porque é uma simples mudança de sistema de coordenadas que preserva geometria, ângulos, interseção, medidas etc.

círculo movendo-se para o centro

Agora, temos uma maneira simples de calcular o comprimento de P quando t varia e dizer para qual t P cruza os limites do círculo.

Exemplos

Como você vê, P ' tem comprimento maior que r enquanto P " é menor que r. Como os comprimentos do vetor er são números positivos, a relação de ordem de ser maior ou menor que o que é preservado é que calculamos a relação entre os comprimentos ao quadrado e ao raio ao quadrado P * 1 e P * 2 são o ponto que torna o | P | ² igual a r²

Como mencionado na seção de pré-edição, chegamos a uma equação quadrática em que t é nossa variável. Como é sabido, os valores da solução de t variam do caso em que t é um par de números complexos - isso significa que não há interseção; o caso em que t são duas soluções iguais - isso significa que há uma interseção; o caso em que existem duas soluções distintas - isso significa que existem duas interseções.

O Discriminante é usado para discriminar a condição anterior e um teste de validade é realizado em t para verificar se existe uma interseção válida, mas fora do nosso segmento - ou seja, a solução t deve ser real e entre 0 e 1 para ser considerada uma interseção adequada que cai. no segmento A_B

FxIII
fonte
3
Este é o algoritmo certo para usar. Uma descrição realmente boa de como funciona pode ser encontrada em Real Time Rendering Third Edition , páginas 787 a 791. Se você pode encontrá-lo em uma biblioteca, vale a pena dar uma olhada.
precisa
4
Com o 8º voto positivo para esta resposta, atingi 2k pontos de reputação. Aprecio muito a confiança que você depositou em mim. Isso é tanto um reconhecimento dos meus esforços quanto um estímulo para continuar fazendo o meu melhor na produção da resposta da mais alta qualidade possível. Obrigado
FxIII
Espere, isso representa os dois casos de canto corretamente? Por exemplo, um círculo pode cruzar o plano definido pela linha fora de t0 <= t <= t1, mas atinge os pontos finais do segmento de linha um pouco mais tarde. Você precisa verificar a distância mínima entre os pontos finais da linha e o caminho dos círculos. Se essa distância for menor que o raio do círculo, a linha foi atingida.
precisa
@DarcyRayner, você está falando sério quando ambos os pontos estão dentro da área do círculo?
FxIII 16/10