Detecção de colisão de ponto-triângulo em 3D

Question

Como faço para corrigir flutuante erro ponto na simulação física seguinte:

• Ponto original (x, y, z),
• ponto desejado (x 'y', z ') depois que as forças são aplicadas.
• Dois triângulos (A, B, C) e (B, C, D), que borda share BC

Eu estou usando este método para detecção de colisão:

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

O problema que estou tendo é que às vezes a ponto de cair na área cinzenta de matemática de ponto flutuante onde é tão perto da linha BC que não colidem com qualquer triângulo, embora tecnicamente ele sempre deve colidir com um ou o outro uma vez que partilham uma vantagem. Quando isso acontece, o ponto passa bem entre os dois triângulos de compartilhamento de borda. Eu marquei uma linha do código com (!) , porque eu acredito que é onde eu deveria estar fazendo uma mudança.

Uma idéia que funciona em situações muito limitadas é pular a testes de borda. Efectivamente transformar os triângulos em aviões. Isso só funciona quando os meus malhas são cascos convexos, mas eu pretendo criar formas convexas.

Eu estou usando especificamente os normais produtos de ponto e triângulo para todos os meus testes de frente para trás.

Answer 1

Este é um problema inevitável quando se fotografa um único raio contra alguns geometria com arestas e vértices. É incrível como física simulações parecem buscar a menor das imprecisões numéricos!

Algumas das explicações e soluções propostas por outros entrevistados não vai funcionar. Em particular:

• imprecisão numérica realmente pode causar um raio "cair através da abertura". O problema é que cruzam o raio com o plano ABC (obtendo o ponto P, digamos) antes de testar contra a linha BC. Então nós cruzam o raio com BCD plano (ficando o ponto Q, digamos) antes de testar contra a linha BC. P e Q são ambos representados pela aproximação mais próximo do ponto flutuante; não há nenhuma razão para esperar que estes se encontram exatamente nos planos que eles são supostamente para mentir sobre, e assim qualquer possibilidade de que você pode ter ambos P para a esquerda do BC e Q à direita do BC.

• Usando menos-que-ou-igual teste não vai ajudar; é imprecisão na interseção do raio e do avião que é o problema.

• Raízes quadradas não são o problema; você pode fazer todos os cálculos necessários usando produtos de ponto e divisão de ponto flutuante.

Aqui estão algumas soluções genuínas:

• Para malhas convexas, você pode apenas prova contra todos os aviões e ignorar as arestas e vértices, como você diz (evitando assim a questão inteiramente).

• não se cruzam o raio com cada triângulo, por sua vez. Em vez disso, use o escalar triplo produto. (Este método faz com que a mesma sequência exacta de cálculos para o raio e o BC borda quando se considera cada triângulo, assegurando que qualquer inexactidão numérica é pelo menos consistente entre os dois triângulos.)

• Para malhas não convexos, dar as arestas e vértices alguma largura. Isto é, colocar uma pequena esfera em cada vértice na malha, e colocar um cilindro fino ao longo de cada borda da malha. Intersect o raio com estas esferas e cilindros, bem como com os triângulos. Estas figuras geométricas adicionais parar o raio que passa através de arestas e vértices da malha.

Deixe-me recomendo fortemente o livro Real-Time Detecção de Colisão por Christer Ericson. Há uma discussão sobre este problema exato em páginas 446-448, e uma explicação da abordagem produto triplo escalar a interseção um raio com um triângulo em páginas 184-188.

Answer 2

Parece que você não está incluindo testar se é na borda (você está escrevendo "Dentro do triângulo bordas"). Tente alterar o código para "menor ou igual" (dentro ou sobreposição).

Answer 3

Acho que é pouco provável que o seu raio cairia exatamente entre os triângulos de forma que o ponto flutuante de precisão entraria em vigor. Você está absolutamente positivo que este é realmente o problema?

De qualquer forma, uma possível solução é em vez de atirar apenas um raio de disparar três que são muito próximos uns dos outros. Se um cai exatamente no meio que um pelo menos um dos outros dois é garantido para cair em um triângulo.

Isto irá pelo menos permitir que você teste se o problema é realmente o erro de ponto flutuante ou algo mais provável.

Answer 4

@Statement: Eu estou na verdade já está usando uma "maior ou igual a" comparação no meu código, obrigado pela sugestão. +1

Minha solução atual é adicionar uma quantidade cotovelada pequena à prova de ponta. Basicamente, quando cada triângulo é testado, os seus bordos são empurrados para fora por uma muito pequena quantidade para neutralizar o erro no ponto flutuante. Mais ou menos como testar se o resultado de um cálculo de ponto flutuante é inferior a 0,01 em vez de testar a igualdade com zero.

Será esta uma solução razoável?

Answer 5

Se você estiver fazendo medições de distância, atente para raízes quadradas. Eles têm o mau hábito de jogar fora metade de sua precisão. Se você empilha alguns desses cálculos, você pode entrar em apuros rápido. Aqui é uma função de distância que tenho usado.

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

Desde a última operação não é uma raiz quadrada, você não perde a precisão mais.

Eu descobri isso em um projeto que eu estava trabalhando. Depois de estudá-lo e descobrir o que ele fez eu rastreou o programador que eu pensei que era responsável para parabenizá-lo, mas ele não tinha idéia do que eu estava falando.