- 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
- Inicialização: define-se um vetor de direção arbitrário
d e encontra-se o primeiro ponto p.
- Encontrar ponto: calcula-se o produto escalar de
d e p; se for positivo, continua, se for negativo, termina.
- Adicionar novo ponto: a partir de
p, encontra-se um novo ponto na direção da origem.
- Simplificação: com base nos dois primeiros pontos, adiciona-se um novo ponto para simplificar.
- Verificar se contém a origem: verifica-se se a forma simplificada contém a origem.
- 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.
1 comentários
Comentários do Hacker News
Algoritmo GJK: Nos anos 1990, passei um ano tentando entender o algoritmo GJK. Ele é útil para detecção de colisão e para encontrar os pontos mais próximos. A ideia básica é fácil de entender. Você começa com dois sólidos convexos e escolhe pontos aleatórios, tentando melhorar a distância entre cada par de pontos. Escolhe os pontos mais próximos e repete. Quando os pontos mais próximos deixam de ser vértices, entra em cena o conceito de "simplex". Trata-se de analisar vários casos. Em motores físicos, surgem problemas quando objetos acabam se acomodando em contato face a face. Em teoria, é uma solução elegante, mas na prática é um problema difícil de análise numérica. Ainda assim, provavelmente é a abordagem mais rápida. No caso geral, é O(log N), e O(1) quando está perto da posição anterior. O falecido professor Stephen Cameron, de Oxford, fez muita pesquisa para implementar o GJK corretamente. No fim dos anos 1990, usei GJK no sistema comercial de ragdoll 3D "Falling Bodies".
Escrevendo uma explicação do GJK: Como não consegui encontrar uma explicação intuitiva do algoritmo de detecção de colisão GJK, resolvi escrever uma eu mesmo. Se alguém souber como deixá-la mais clara e eficiente, peço que avise. Como é uma explicação matemática feita por um estudante do ensino médio, convém lê-la com um nível adequado de ceticismo.
Vídeo sobre o algoritmo GJK: Compartilho um link para uma apresentação em vídeo sobre o mesmo algoritmo. Link do vídeo
Elogio ao artigo: Excelente artigo. Muito claro e interessante.
Comparação com otimização convexa: Outra forma de verificar a interseção entre dois conjuntos convexos é resolver um problema de otimização convexa que minimiza a norma da diferença entre dois pontos. Se o valor ótimo for 0, os conjuntos se intersectam. Gostaria de ver uma comparação entre o algoritmo GJK e essa abordagem por otimização convexa. Não tenho certeza de qual é melhor.
Elogio ao artigo e ressalva: Excelente artigo. Só que a primeira imagem mostra a interseção de formas não convexas, enquanto só mais tarde fica claro que o algoritmo funciona apenas para formas convexas.
Primeiro contato com o algoritmo GJK: É a primeira vez que ouço falar do algoritmo GJK.
Post de blog relacionado: Escrevi um post de blog relacionado à geometria de Minkowski. Link do blog
Site pessoal: Inesperadamente isso está recebendo atenção, então menciono que meu site pessoal está cheio de piadas. Se quiser entrar em contato, avise em uma resposta.
Uso da função Minkowski: Eu vinha usando a função Minkowski no openSCAD e fico feliz em finalmente entender o que ela realmente é.
Elogio ao algoritmo: É um algoritmo fantástico.