Algoritmo GJK: como resolver algo simples de um jeito estranho e bonito

• O algoritmo GJK é uma forma de verificar se duas formas se sobrepõem
• Para verificar se a forma A e a forma B se sobrepõem, basta verificar se ao menos um ponto entre os pontos das duas formas coincide

Diferença de Minkowski

• Cria-se um novo conjunto subtraindo todos os pontos das duas formas.
• Se a origem estiver contida nesse novo conjunto, isso significa que as duas formas se sobrepõem.
• Isso é chamado de diferença de Minkowski.

Ideia básica do algoritmo

• Verifica-se se a diferença de Minkowski de A e B contém a origem.
• Se a diferença contiver a origem, as formas se sobrepõem.

Etapas do algoritmo

1. Inicialização: define-se um vetor de direção arbitrário d e encontra-se o primeiro ponto p.
2. Encontrar ponto: calcula-se o produto escalar de d e p; se for positivo, continua, se for negativo, termina.
3. Adicionar novo ponto: a partir de p, encontra-se um novo ponto na direção da origem.
4. Simplificação: com base nos dois primeiros pontos, adiciona-se um novo ponto para simplificar.
5. Verificar se contém a origem: verifica-se se a forma simplificada contém a origem.
6. Repetição: repete-se até conter a origem ou até encontrar uma evidência de que não a contém.

Opinião do GN⁺

• Ponto interessante: o algoritmo GJK é um bom exemplo de resolver um problema complexo com uma transformação matemática simples.
• Por que é útil: é muito usado em gráficos em tempo real, como em detecção de colisão.
• Visão crítica: a implementação do algoritmo pode ser complexa e exige entendimento preciso.
• Tecnologias relacionadas: entre outros algoritmos de detecção de colisão está o SAT (Separating Axis Theorem).
• Pontos a considerar: ao usar o algoritmo GJK, é preciso considerar a complexidade das formas e o custo computacional.

[GN⁺]

Comentários no Hacker News

• Passei quase um ano apanhando do GJK nos anos 1990
  Ele é útil para detecção de colisão 3D e também pode ser usado como algoritmo de ponto mais próximo. A ideia básica é fácil de entender. Dado dois sólidos convexos, você pega um ponto arbitrário em cada sólido, calcula a distância entre os dois pontos e então tenta melhorar essa distância movendo-se, a partir do ponto atual, ao longo de cada aresta, escolhendo o novo ponto mais próximo, repetindo o processo
  Mas, quando o ponto mais próximo deixa de ser um vértice, essa abordagem quebra, e é aí que entra o conceito de simplexo (simplex). As combinações de pontos mais próximos se dividem em vértice-vértice, vértice-aresta, vértice-face, aresta-aresta, aresta-face (sem solução única) e face-face (sem solução única), e o tratamento de simplexo, na prática, fica bem próximo de analisar esses casos
  Na prática, surgem muitos problemas. Em motores de física, objetos frequentemente se estabilizam em contato face-face, e um modelo de colisão de ponto único pode gerar oscilações ou movimentos incorretos. Além disso, quando a posição converge para contato face-face, o GJK passa a lidar com pequenas diferenças entre valores grandes, podendo perder completamente os dígitos significativos de ponto flutuante. As condições de término também podem causar loops infinitos
  Em teoria é elegante, mas na prática é um problema difícil de análise numérica. Ainda assim, provavelmente é a abordagem mais rápida para esse problema. No caso geral é O(log N) e, quando se está na situação mais próxima da posição anterior e se usa a última solução como ponto de partida, fica perto de O(1)
  O falecido professor Steven Cameron, de Oxford, trabalhou bastante para fazer o GJK funcionar corretamente, e no fim dos anos 1990 o GJK foi usado em "Falling Bodies", o primeiro sistema comercial de ragdoll 3D

  • Depois que você encontra o contato, quase sempre precisa fazer alguma coisa com ele, e para a maioria dos tratamentos úteis é preciso saber as informações reais de interpenetração
    Obter isso é numericamente ainda pior. Você começa pelo simplexo gerado pelo GJK e o expande para fora, fazendo triangulação no processo. Implementar isso com bom desempenho é praticamente um pesadelo completo
  • https://www.youtube.com/watch?v=5lHqEwk7YHs
    Fico curioso se a patente já expirou e se há planos de abrir o código. Seria historicamente significativo e um material interessante, no estilo de ler o código-fonte do Doom

• Não encontrei um texto que explicasse intuitivamente o algoritmo de detecção de colisão GJK, então passei a tarde organizando uma explicação eu mesmo
  Se houver formas de deixá-lo mais claro e eficiente, seria bom saber. Claro, espero que levem em conta que é um texto de um aluno do segundo ano do ensino médio explicando conteúdo matemático

  • O texto é muito claro. Se continuar fazendo esse tipo de trabalho, você parece ter talento suficiente para um dia escrever um ótimo livro didático
    Já está bom, mas para deixá-lo ainda mais completo talvez dê para acrescentar algumas coisas: uma breve explicação da complexidade de tempo no pior caso, uma seção separada sobre as condições de término e pseudocódigo ao longo da explicação
    O jeito de explicar pela perspectiva matemática, como está agora, funciona bem e vale manter. Mas, depois de cada etapa, adicionar um pequeno pseudocódigo definindo funções auxiliares como S(•) e mostrando até onde o algoritmo avançou poderia deixá-lo ainda melhor
    O texto sobre o modelo oculto da OpenAI também foi bom. O tempo gasto procurando o que mais uma pessoa que produziu algo impressionante fez quase sempre vale a pena
  • Falando como matemático, a pior crítica que eu faria é que, se fosse escrito para leitores de matemática, eu teria formulado algumas expressões de modo ligeiramente diferente
    O título deveria ser "as simply as possible". Eu não conhecia o algoritmo GJK, mas, se estivesse ensinando Cálculo III agora, tentaria encontrar uma forma de incluir esse conteúdo na aula. A explicação é boa a esse ponto
  • Fico me perguntando se esse algoritmo tem término garantido
    No exemplo do retângulo com cantos suavemente arredondados no fim do texto, não sei o que impede que ele apenas se aproxime cada vez mais da resposta sem nunca realmente alcançá-la. Claro, em computação real, sei que não há motivo para continuar depois de um limite prático de precisão
  • Os três conjuntos A, B, A-B na segunda figura são confusos
    No começo, entendi como se alguma transformação fosse aplicada a A e B para produzir a forma A-B. Depois de reler algumas vezes, parece que A-B não representa os dois conjuntos à esquerda, mas sim a interseção de outros A e B, e que o ponto importante é essa interseção sobrepor a origem, ou 0,0. Gostaria de saber se é isso mesmo

• Uma apresentação em vídeo sobre o mesmo algoritmo: https://www.youtube.com/watch?v=ajv46BSqcK4

  • Este também vale como referência: https://winter.dev/articles/gjk-algorithm
    No final há uma demonstração interativa mostrando a diferença de Minkowski

• O texto é muito claro e interessante
  Outra forma de verificar se dois conjuntos convexos se intersectam é resolver um problema de otimização convexa que minimiza a norma da diferença entre um ponto pertencente ao primeiro conjunto convexo e um ponto pertencente ao segundo conjunto convexo. Se o valor ótimo for 0, os dois conjuntos se intersectam
  Seria interessante comparar o algoritmo GJK com otimização convexa. Não tenho certeza de qual dos dois é mais vantajoso

  • Pergunta interessante. Se a interpenetração for suficientemente grande, parece que um método de pontos interiores poderia terminar rapidamente. Também daria para acrescentar condições inteligentes de término antecipado

• A primeira imagem mostra a interseção de uma forma não convexa, mas o fato de o algoritmo funcionar apenas com formas convexas só aparece bem mais adiante, o que pode ser um pouco enganoso

  • Está explicado que formas não convexas são tratadas dividindo-as em formas convexas

• Uso a função Minkowski no openSCAD há algum tempo, e é bom entender o que ela realmente é

• Como isso acabou recebendo bem mais atenção do que eu esperava, acho que preciso dizer que meu site pessoal é basicamente uma coleção sofisticada de piadas internas
  Se quiserem entrar em contato ou tiverem algo a tratar, podem me avisar respondendo aqui

  • Se tiver interesse em mentoria para projetos de pesquisa, pode me mandar e-mail: [e-mail]
  • O site é bom e você parece ser uma pessoa legal. Continue fazendo coisas legais

• Implementei o GJK quase 10 anos atrás com base na excelente explicação do Casey: https://www.youtube.com/watch?v=Qupqu1xe7Io

• Já escrevi um texto relacionado à geometria de Minkowski: https://nickp.svbtle.com/asteroid-intersections