Geekly articles weekly

Cálculo 2D de colisão: Algoritmo de Gilbert-Johnson-Kirti

imagem

Eu iniciei o estudo dos processos de reconhecimento de colisões, e isso me levou ao algoritmo Gilbert-Johnson-Keerthi (GJK).

Todos os exemplos de código na postagem são escritos em TypeScript. Os exemplos usam as estruturas que eu criei que não são discutidas em detalhes no post. Eles são simples e podem ser visualizados no repositório GitHub:

  • Vector
  • IShape
  • Collision

Todo o código da postagem é armazenado no repositório do GitHub:

https://github.com/jthomperoo/gjk-ts-implementation

A postagem foi escrita com base neste artigo e o vídeo recomendado:


1. Introdução


GJK é um algoritmo projetado para determinar a interseção de duas formas convexas. É simples e implementado com a ajuda de uma “função auxiliar” generalizada que permite usar uma abordagem mais geral - da mesma forma, você pode processar polígonos e formas que consistem em curvas, por exemplo, elipses.

Informações Necessárias


Soma de Minkowski


GJK usa um conceito chamado soma de Minkowski. O SM é calculado somando todos os pontos de duas figuras. Por exemplo, pegue as duas figuras mostradas abaixo:


Figura A (verde):

UmBC
(0,1)(1, -1)(-1, -1)

Figura B (roxa):

DEF
(0, -1)(1,1)(-1,1)

Tomando os valores das figuras A e B, podemos calcular a soma de Minkowski:

A + D = (0,1) + (0,-1) = (0,0)

A + E = (0,1) + (1,1) = (1,2)

A + F = (0,1) + (-1,1) = (-1,2)

B + D = (1,-1) + (0,-1) = (1,-2)

B + E = (1,-1) + (1,1) = (2,0)

B + F = (1,-1) + (-1,1) = (0,0)

C + D = (-1,-1) + (0,-1) = (-1,-2)

C + E = (-1,-1) + (1,1) = (0,0)

C + F = (-1,-1) + (-1,1) = (-2,0)

Se pegarmos esses valores e fizermos um gráfico a partir deles, veremos qual figura será o resultado.

Soma de Minkowski para as figuras A e B:

Observe que o AD na tabela e no gráfico corresponde a A + D

Gráfico da soma de Minkowski da forma A e B

ADAeAFBdBEBfCDCECF
(0,0)(1,2)(-1,2)(1, -2)(2.0)(0,0)(-1, -2)(0,0)(-2,0)

Para entender melhor a soma de Minkowski, podemos imaginar que pegamos a figura A e a contornamos com o contorno de um B. A figura resultante será a soma de Minkowski.

Diferença de Minkowski


GJK usa uma variação da soma de Minkowski, na qual não A + B é obtido, mas A - B. Nas fontes que li, isso é chamado de "Diferença de Minkowski". A diferença de Minkowski tem uma propriedade interessante: se duas figuras se sobrepõem / se cruzam, a diferença de Minkowski resultante conterá a origem. E esta é a base do algoritmo GJK.

Tomando os valores das figuras A e B, podemos calcular a diferença de Minkowski:

A - D = (0,1) - (0,-1) = (0,2)

A - E = (0,1) - (1,1) = (-1,0)

A - F = (0,1) - (-1,1) = (1,0)

B - D = (1,-1) - (0,-1) = (-1,0)

B - E = (1,-1) - (1,1) = (0,-2)

B - F = (1,-1) - (-1,1) = (2,-2)

C - D = (-1,-1) - (0,-1) = (-1,0)

C - E = (-1,-1) - (1,1) = (-2,-2)

C - F = (-1,-1) - (-1,1) = (0,-2)

Se pegarmos esses valores e os colocarmos no gráfico, veremos a figura resultante.

Diferença de Minkowski para as figuras A e B:

Observe que o AD na tabela e no gráfico se refere a A - D

Gráfico da soma de Minkowski da forma A e B

ADAeAFBdBEBfCDCECF
(0,2)(-1,0)(1,0)(-1,0)(0, -2)(2, -2)(-1,0)(-2, -2)(0, -2)

Algoritmo


Com base nesses conceitos, o algoritmo GJK os otimiza. O cálculo da soma de Minkowski pode demorar muito, especialmente se você verificar a interseção de duas figuras que consistem em muitos pontos. Para evitar isso, o GJK usa dois conceitos principais: funções auxiliares e simplexes.

Funções auxiliares


As funções auxiliares são uma maneira de amostrar um ponto na extremidade da diferença de Minkowski sem construir a figura inteira. A função auxiliar obtém dois números comparados e a direção que precisa ser verificada. Então a função auxiliar recebe de cada figura um ponto mais distante de duas direções opostas. Usando esses dois pontos mais distantes, você pode calcular o ponto auxiliar na figura da diferença de Minkowski. Tomamos pontos de direções opostas porque obtemos um ponto da diferença de Minkowski, que nos dará a maior área, ou seja, haverá uma maior probabilidade de incluirmos a origem na figura. Como a diferença de Minkowski é o a - b , a presença do ponto da figura b amostrado na direção oposta nos dará um ponto auxiliar o mais distante possível nessa direção.

A implementação da função auxiliar é bastante simples:

 function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); }

Uma das vantagens do GJK é que o FarthestPointInDirection pode ser abstraído e aplicado a polígonos e curvas. Aqui está a implementação do FarthestPointInDirection para um polígono.

 class Polygon implements IShape { public points: Vector[]; ... public FarthestPointInDirection(direction: Vector): Vector { let farthestDistance = -Infinity; // If there are no points, just return point 0,0 let farthestPoint: Vector = new Vector(0,0); for (const point of this.points) { const distanceInDirection = point.Dot(direction); if (distanceInDirection > farthestDistance) { farthestPoint = point; farthestDistance = distanceInDirection; } } return farthestPoint; } }

Se você quiser ver como outras formas serão implementadas, confira o repositório Git desta postagem , que apresenta a implementação do Circle .

Aqui está como o ponto auxiliar na direção (1,0) será calculado para as figuras A e B:

  1. Tome o ponto mais distante da figura A; acaba sendo o ponto B (1, -1) . (Você pode calculá-lo, como o algoritmo mostrado acima, ou apenas vê-lo olhando para o gráfico).
  2. Tome o ponto mais distante da figura B; acaba sendo o ponto F (-1, 1) .
  3. Calcular B - F ; acaba sendo o ponto BF (2, -2) - será auxiliar .

Simplexes


Um simplex é uma amostra de pontos ao longo da figura da diferença de Minkowski. Simplexes podem conter até três pontos. GJK os usa, tentando construir um triângulo em torno da origem para determinar a ocorrência de uma colisão.

Construção simplex


Simplexes são construídos iterativamente adicionando pontos auxiliares em diferentes direções. Cada ponto auxiliar deve apontar para uma nova direção, para que possamos construir o mais rápido possível um simplex contendo um ponto de origem. A dificuldade está em escolher a direção na qual obter o próximo ponto auxiliar.

Detecção de colisão e seleção de direção


O algoritmo básico simplesmente cria um simplex com a ajuda de uma função auxiliar, tentando incluir um ponto de origem na figura. Podemos entender que não há colisão / interseção verificando se o ponto auxiliar calculado alcança a origem e, se não, a origem deve estar fora da diferença de Minkowski; portanto, podemos dizer que não há colisão / interseção.

 function Calculate(a: IShape, b: IShape): Collision | undefined { // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); }

Toda a complexidade e operação interna do algoritmo estão em simplex.CalculateDirection . Essa função determina se a origem está no simplex atual - nesse caso, retornará undefined ; caso contrário, ele retornará uma nova direção para obter um ponto auxiliar, que deve ser adicionado ao simplex.

 class Simplex { private points: Vector[]; ... CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } return undefined; } // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; } }

Você pode se perguntar: por que não verificamos o segmento BC? Porque podemos excluir incondicionalmente que a origem é ao longo de sua perpendicular. Como os pontos B e C já estão no simplex e não foram apenas adicionados, sabemos que foram verificados na iteração anterior. Eles podem ser verificados como parte de um triângulo ou como um segmento dos dois primeiros pontos em um simplex - isso não importa. Portanto, podemos ignorar com segurança a verificação do segmento BC.

Explicação detalhada


Temos muito código, e isso parece confuso. Abaixo, analisarei as etapas do algoritmo para as figuras A e B mostradas acima.

Pontos das figuras A e B:

UmBCDEF
(0,1)(1, -1)(-1, -1)(0, -1)(1,1)(-1,1)

  1. Preparação do algoritmo; tomamos (0,1) como a direção inicial.

     // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1);

  2. Temos o primeiro ponto auxiliar.

      // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert();

    Chegamos ao ponto mais distante do ponto A na direção (0,1) e do ponto B na direção (0,-1) .

    aFar: (0,1) ebFar: (0,-1)

    Use esses valores para obter o ponto auxiliar.

    Suporte: aFar-bFar = (0,2)

      function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); }

  3. Viramos a direção do próximo ponto auxiliar e iniciamos a iteração, calculando um novo ponto auxiliar.

    Suporte: (0,-3)

      // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction);
  4. Verifique se o ponto auxiliar atingiu a origem; caso contrário, não deve haver interseção. Se ela alcançou a origem, adicione o ponto ao simplex.

    Nesse caso, o ponto auxiliar atingiu a origem.

    direção: (0,-1)

    Suporte: (0,-3)

    supportPoint.Dot (direction): 3

      // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint);

  5. Nesse estágio, o simplex é um segmento, portanto, não pode conter um ponto de origem dentro; defina uma nova direção na qual procurar o ponto auxiliar.

      direction = simplex.CalculateDirection();

    1. Pegamos o último ponto adicionado ao simplex e determinamos a direção da origem; este será o recíproco deste ponto.

      a: (0,-3) ao: (0,3)

        CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) {
    2. Como o simplex é um segmento, não um triângulo, pegamos o segundo ponto do segmento e calculamos o segmento do simplex.

      b: (0,2) ab: (0,5)

        // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a);
    3. Calculamos a perpendicular a esse segmento e verificamos que ele é direcionado para a origem. Essa será a nova direção para o próximo ponto auxiliar.

      abPerp: (5, 0)

      abPerp.Dot (ao) 0

      abPerp: (-5, 0)

      Gráfico da linha ab e sua perpendicular

        // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp;
  6. Agora temos uma direção para procurar o próximo ponto auxiliar. Retornamos ao início do ciclo e não o saímos, porque enquanto temos uma direção e a interseção ainda não foi encontrada.

    direção: (-5, 0)

    Suporte: (-2,-2)

    supportPoint.Dot (direction): 10

    O ponto auxiliar atingiu a origem, portanto, não podemos dizer que não há interseção.

      while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; }
  7. Adicione um novo ponto auxiliar ao simplex, criando um triângulo. Esse triângulo pode conter a origem e, nesse caso, o simplex retornará undefined , e não uma nova direção para a pesquisa.

      // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection();

    1. Tome os pontos do simplex do triângulo.
      a: (-2,-2) b: (0,-3) c: (0,2) ao: (2,2)

        // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0];
    2. Pegue os segmentos ab e ac.

      ab: (2,-1) ac: (2,4)

        // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a);
    3. Calculamos a perpendicular ao segmento ab, direcionado a partir do simplex.

      abperp: (-1,-2)

        // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); }
    4. Determinamos se a origem está fora do simplex além de ab.

      abPerp.Dot (ao): -6

      A origem não está fora do simplex além de ab.

      Gráfico da linha ab e sua perpendicular

        if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; }
    5. Calculamos a perpendicular ao segmento ac direcionado a partir do simplex.

      acPerp: (-4,2)

        // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); }
    6. Determine se a origem está fora do simplex além de ac.

      acPerp.Dot (ao): -4

      A origem não está fora do simplex além de ab.

      Gráfico da linha ac e sua perpendicular

        // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; }
    7. Como AB e AC foram verificados nesta iteração, e sabemos que BC foi verificado na iteração anterior, o ponto de origem deve estar dentro do simplex, para que uma colisão / interseção seja detectada - informando sobre isso, a função retornará undefined .

      Linhas ab, ac e bc e perpendiculares relevantes
  8. Como uma colisão foi detectada, o loop é encerrado e as informações de Collision sobre a colisão entre as duas figuras são retornadas.

      direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b);

Conclusão


Espero que este artigo ajude você a entender o algoritmo GJK. O algoritmo dá uma resposta sim / não sobre a presença de um conflito entre as duas figuras. Um exemplo de trabalho com polígonos e círculos pode ser visualizado no repositório desta postagem . Você pode expandir esse código com algoritmos e técnicas adicionais, tentando obter a distância de penetração entre as duas figuras, a colisão normal e o ponto de contato. A publicação dyn4j possui links para bons recursos em vários algoritmos de reconhecimento de colisão / resposta; se você deseja expandir o GJK, deve estudá-los.

Source: https://habr.com/ru/post/pt472404/

More articles:


All Articles