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.
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;
}
fonte
sqrt_disc = sqrt(disc);
novamente. Muito obrigado por sua resposta abaixo, isso me ajudou muito.Respostas:
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 r²
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 t²
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. Esta é a condição inicial. Agora concentre-se no segmento 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.
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.
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
fonte