Tutorial de física de videogame - Parte II: Detecção de colisão para objetos sólidos

Esta é a Parte II de nossa série de três partes sobre física de videogame. Para o resto desta série, veja:

Parte I: Uma Introdução à Dinâmica do Corpo Rígido
Parte III: Simulação de corpo rígido restrito

Na Parte I desta série, exploramos os corpos rígidos e seus movimentos. Nessa discussão, no entanto, os objetos não interagiam uns com os outros. Sem algum trabalho adicional, os corpos rígidos simulados podem atravessar uns aos outros, ou “interpenetrar-se”, o que é indesejável na maioria dos casos.

Para simular de forma mais realista o comportamento de objetos sólidos, temos que verificar se eles colidem uns com os outros toda vez que se movem, e se isso acontecer, temos que fazer algo a respeito, como aplicar forças que mudam suas velocidades, então que eles se moverão na direção oposta. É aqui que entender a física das colisões é particularmente importante para os desenvolvedores de jogos.

Na Parte II, abordaremos a etapa de detecção de colisão, que consiste em encontrar pares de corpos que estão colidindo entre um número possivelmente grande de corpos espalhados por um mundo 2D ou 3D. Na próxima e última parte, falaremos mais sobre “resolver” essas colisões para eliminar interpenetrações.

Para uma revisão dos conceitos de álgebra linear mencionados neste artigo, você pode consultar o curso intensivo de álgebra linear na Parte I.

Física de colisão em videogames

No contexto de simulações de corpos rígidos, uma colisão ocorre quando as formas de dois corpos rígidos se cruzam ou quando a distância entre essas formas cai abaixo de uma pequena tolerância.

Se tivermos n corpos em nossa simulação, a complexidade computacional de detectar colisões com testes de pares é O ( n 2 ) , um número que faz os cientistas da computação se encolherem. O número de testes de pares aumenta quadraticamente com o número de corpos, e determinar se duas formas, em posições e orientações arbitrárias, estão colidindo já não é barato. Para otimizar o processo de detecção de colisões, geralmente o dividimos em duas fases: fase ampla e fase estreita .

A fase ampla é responsável por encontrar pares de corpos rígidos potencialmente colidindo, e excluir pares que certamente não colidem, de todo o conjunto de corpos que estão na simulação. Esta etapa deve ser capaz de dimensionar muito bem com o número de corpos rígidos para garantir que permaneçamos bem abaixo da complexidade de tempo O ( n 2 ) . Para conseguir isso, essa fase geralmente usa particionamento de espaço acoplado a volumes delimitadores que estabelecem um limite superior para colisão.

A fase estreita opera nos pares de corpos rígidos encontrados pela fase ampla que pode estar colidindo. É uma etapa de refinamento onde determinamos se as colisões estão realmente acontecendo, e para cada colisão encontrada, computamos os pontos de contato que serão usados ​​para resolver as colisões posteriormente.

Nas próximas seções falaremos sobre alguns algoritmos que podem ser usados ​​na fase ampla e na fase estreita.

Fase ampla

Na fase ampla da física de colisão para videogames, precisamos identificar quais pares de corpos rígidos podem estar colidindo. Esses corpos podem ter formas complexas como polígonos e poliedros, e o que podemos fazer para acelerar isso é usar uma forma mais simples para englobar o objeto. Se esses volumes delimitadores não se cruzam, as formas reais também não se cruzam. Se eles se cruzam, as formas reais podem se cruzar.

Alguns tipos populares de volumes delimitadores são caixas delimitadoras orientadas (OBB), círculos em 2D e esferas em 3D. Vejamos um dos volumes delimitadores mais simples: caixas delimitadoras alinhadas ao eixo (AABB) .

Os AABBs recebem muito amor dos programadores de física porque são simples e oferecem boas compensações. Um AABB bidimensional pode ser representado por uma estrutura como esta na linguagem C:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

O campo min representa a localização do canto inferior esquerdo da caixa e o campo max representa o canto superior direito.

Para testar se dois AABBs se cruzam, basta descobrir se suas projeções se cruzam em todos os eixos coordenados:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Este código tem a mesma lógica da função b2TestOverlap do motor Box2D (versão 2.3.0). Calcula a diferença entre o min e o max de ambos os AABBs, em ambos os eixos, em ambas as ordens. Se algum desses valores for maior que zero, os AABBs não se cruzam.

Mesmo que um teste de sobreposição AABB seja barato, não ajudará muito se ainda fizermos testes de pares para todos os pares possíveis, pois ainda temos a indesejável complexidade de tempo O ( n 2 ) . Para minimizar o número de testes de sobreposição do AABB, podemos usar algum tipo de particionamento de espaço , que funciona com os mesmos princípios dos índices de banco de dados que aceleram as consultas. (Bancos de dados geográficos, como PostGIS, na verdade usam estruturas de dados e algoritmos semelhantes para seus índices espaciais.) Nesse caso, porém, os AABBs estarão se movendo constantemente, então geralmente devemos recriar índices após cada etapa da simulação.

Existem muitos algoritmos de particionamento de espaço e estruturas de dados que podem ser usados ​​para isso, como grades uniformes, quadtrees em 2D, octrees em 3D e hashing espacial. Vamos dar uma olhada em dois algoritmos populares de particionamento espacial: classificação e varredura e hierarquias de volume delimitador (BVH).

O algoritmo de classificação e varredura

O método sort and sweep (também conhecido como sweep and prune ) é uma das escolhas favoritas entre os programadores de física para uso em simulação de corpo rígido. O motor Bullet Physics, por exemplo, tem uma implementação deste método na classe btAxisSweep3 .

A projeção de um AABB em um único eixo de coordenadas é essencialmente um intervalo [ b , e ] (ou seja, início e fim). Em nossa simulação, teremos muitos corpos rígidos e, portanto, muitos AABBs, e isso significa muitos intervalos. Queremos descobrir quais intervalos estão se interceptando.

No algoritmo de ordenação e varredura, inserimos todos os valores b e e em uma única lista e a ordenamos em ordem crescente por seus valores escalares. Em seguida, varremos ou percorremos a lista. Sempre que um valor b é encontrado, seu intervalo correspondente é armazenado em uma lista separada de intervalos ativos e sempre que um valor e é encontrado, seu intervalo correspondente é removido da lista de intervalos ativos. A qualquer momento, todos os intervalos ativos estão se cruzando. (Confira a tese de doutorado de David Baraff, p. 52 para detalhes. Sugiro usar esta ferramenta online para visualizar o arquivo postscript.) A lista de intervalos pode ser reutilizada em cada etapa da simulação, onde podemos reordenar com eficiência esta lista usando a ordenação por inserção, que é boa para ordenar listas quase ordenadas.

Em duas e três dimensões, executar a classificação e varredura, conforme descrito acima, em um único eixo de coordenadas reduzirá o número de testes de interseção AABB diretos que devem ser executados, mas o retorno pode ser melhor em um eixo de coordenadas do que em outro. Portanto, variações mais sofisticadas do algoritmo de classificação e varredura são implementadas. Em seu livro Real-Time Collision Detection (página 336), Christer Ericson apresenta uma variação eficiente onde ele armazena todos os AABBs em uma única matriz, e para cada execução da classificação e varredura, um eixo de coordenada é escolhido e a matriz é classificada por o valor min dos AABBs no eixo escolhido, usando quicksort. Em seguida, a matriz é atravessada e os testes de sobreposição AABB são realizados. Para determinar o próximo eixo que deve ser usado para ordenação, a variância do centro dos AABBs é calculada e o eixo com maior variância é escolhido para a próxima etapa.

Árvores de Volume Limitante Dinâmico

Outro método útil de particionamento espacial é a árvore de volume delimitadora dinâmica , também conhecida como Dbvt . Este é um tipo de hierarquia de volume delimitadora .

O Dbvt é uma árvore binária em que cada nó possui um AABB que limita todos os AABBs de seus filhos. Os AABBs dos próprios corpos rígidos estão localizados nos nós folha. Normalmente, um Dbvt é “consultado” fornecendo o AABB para o qual gostaríamos de detectar interseções. Essa operação é eficiente porque os filhos dos nós que não cruzam o AABB consultado não precisam ser testados quanto à sobreposição. Como tal, uma consulta de colisão AABB começa na raiz e continua recursivamente pela árvore apenas para nós AABB que fazem interseção com o AABB consultado. A árvore pode ser balanceada por meio de rotações de árvores, como em uma árvore AVL.

Box2D tem uma implementação sofisticada de Dbvt na classe b2DynamicTree . A classe b2BroadPhase é responsável por realizar a fase ampla e utiliza uma instância de b2DynamicTree para realizar consultas AABB.

Fase estreita

Após a fase ampla da física de colisão dos videogames, temos um conjunto de pares de corpos rígidos que estão potencialmente colidindo. Assim, para cada par, dada a forma, posição e orientação de ambos os corpos, precisamos descobrir se eles estão, de fato, colidindo; se eles estiverem se cruzando ou se sua distância estiver abaixo de um pequeno valor de tolerância. Também precisamos saber quais são os pontos de contato entre os corpos que colidem, pois isso é necessário para resolver as colisões posteriormente.

Formas convexas e côncavas

Como regra geral da física dos videogames, não é trivial determinar se duas formas arbitrárias estão se cruzando ou calcular a distância entre elas. No entanto, uma propriedade que é de importância crítica para determinar o quão duro é, é a convexidade da forma. As formas podem ser convexas ou côncavas e as formas côncavas são mais difíceis de trabalhar, por isso precisamos de algumas estratégias para lidar com elas.

Em uma forma convexa, um segmento de linha entre quaisquer dois pontos dentro da forma sempre cai completamente dentro da forma. No entanto, para uma forma côncava (ou “não convexa”), o mesmo não é verdade para todos os possíveis segmentos de linha conectando pontos na forma. Se você puder encontrar pelo menos um segmento de linha que esteja fora da forma, a forma é côncava.

Computacionalmente, é desejável que todas as formas sejam convexas em uma simulação, pois temos muitos algoritmos poderosos de teste de distância e interseção que trabalham com formas convexas. No entanto, nem todos os objetos serão convexos, e geralmente trabalhamos em torno deles de duas maneiras: casco convexo e decomposição convexa.

O casco convexo de uma forma é a menor forma convexa que a contém totalmente. Para um polígono côncavo em duas dimensões, seria como martelar um prego em cada vértice e enrolar um elástico em torno de todos os pregos. Para calcular o casco convexo para um polígono ou poliedro, ou mais geralmente, para um conjunto de pontos, um bom algoritmo a ser usado é o algoritmo quickhull , que possui uma complexidade de tempo média de O ( n log n ) .

Obviamente, se usarmos um casco convexo para representar um objeto côncavo, ele perderá suas propriedades côncavas. Comportamentos indesejáveis, como colisões “fantasmas”, podem se tornar aparentes, pois o objeto ainda terá uma representação gráfica côncava. Por exemplo, um carro geralmente tem uma forma côncava, e se usarmos um casco convexo para representá-lo fisicamente e depois colocarmos uma caixa nele, a caixa pode parecer estar flutuando no espaço acima.

Em geral, os cascos convexos costumam ser bons o suficiente para representar objetos côncavos, seja porque as colisões irreais não são muito perceptíveis, ou suas propriedades côncavas não são essenciais para o que está sendo simulado. Em alguns casos, porém, podemos querer que o objeto côncavo se comporte fisicamente como uma forma côncava. Por exemplo, se usarmos um casco convexo para representar fisicamente uma tigela, não poderemos colocar nada dentro dela. Os objetos irão flutuar em cima dele. Neste caso, podemos usar uma decomposição convexa da forma côncava.

Os algoritmos de decomposição convexa recebem uma forma côncava e retornam um conjunto de formas convexas cuja união é idêntica à forma côncava original. Algumas formas côncavas só podem ser representadas por um grande número de formas convexas, e elas podem se tornar proibitivamente caras para calcular e usar. No entanto, uma aproximação geralmente é boa o suficiente e, portanto, algoritmos como V-HACD produzem um pequeno conjunto de poliedros convexos a partir de um poliedro côncavo.

Em muitos casos de física de colisões, porém, a decomposição convexa pode ser feita à mão, por um artista. Isso elimina a necessidade de taxar o desempenho com algoritmos de decomposição. Como o desempenho é um dos aspectos mais importantes em simulações em tempo real, geralmente é uma boa ideia criar representações físicas muito simples para objetos gráficos complexos. A imagem abaixo mostra uma possível decomposição convexa de um carro 2D usando nove formas convexas.

Teste de Interseções - O Teorema do Eixo Separador

O teorema dos eixos de separação (SAT) afirma que duas formas convexas não se cruzam se e somente se existir pelo menos um eixo onde as projeções ortogonais das formas neste eixo não se cruzam.

Geralmente é visualmente mais intuitivo encontrar uma linha em 2D ou um plano em 3D que separa as duas formas, o que é efetivamente o mesmo princípio. Um vetor ortogonal à linha em 2D, ou o vetor normal do plano em 3D, pode ser usado como “eixo de separação”.

Os mecanismos de física de jogos têm várias classes diferentes de formas, como círculos (esferas em 3D), bordas (um único segmento de linha) e polígonos convexos (poliedros em 3D). Para cada par de tipo de forma, eles possuem um algoritmo específico de detecção de colisão. O mais simples deles é provavelmente o algoritmo círculo-círculo:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Embora o SAT se aplique a círculos, é muito mais simples verificar se a distância entre seus centros é menor que a soma de seus raios. Por esse motivo, o SAT é usado no algoritmo de detecção de colisão para pares específicos de classes de forma, como polígono convexo contra polígono convexo (ou poliedros em 3D).

Para qualquer par de formas, há um número infinito de eixos que podemos testar quanto à separação. Assim, determinar qual eixo testar primeiro é crucial para uma implementação eficiente do SAT. Felizmente, ao testar se um par de polígonos convexos colidem, podemos usar as normais das arestas como possíveis eixos de separação. O vetor normal n de uma aresta é perpendicular ao vetor da aresta e aponta para fora do polígono. Para cada aresta de cada polígono, só precisamos descobrir se todos os vértices do outro polígono estão na frente da aresta.

Se algum teste passar – ou seja, se, para qualquer aresta, todos os vértices do outro polígono estiverem à sua frente – então os polígonos não se cruzam. A álgebra linear fornece uma fórmula fácil para este teste: dada uma aresta na primeira forma com vértices a e b e um vértice v na outra forma, se ( v - a ) · n for maior que zero, então o vértice está na frente da borda.

Para poliedros, podemos usar as normais de face e também o produto vetorial de todas as combinações de arestas de cada forma. Isso soa como um monte de coisas para testar; no entanto, para acelerar as coisas, podemos armazenar em cache o último eixo de separação que usamos e tentar usá-lo novamente nas próximas etapas da simulação. Se o eixo de separação armazenado em cache não separar mais as formas, podemos procurar um novo eixo a partir de faces ou arestas adjacentes à face ou aresta anterior. Isso funciona porque os corpos geralmente não se movem ou giram muito entre as etapas.

Box2D usa SAT para testar se dois polígonos convexos estão se cruzando em seu algoritmo de detecção de colisão polígono-polígono em b2CollidePolygon.cpp.

Distância Computacional - O Algoritmo Gilbert-Johnson-Keerthi

Em muitos casos de física de colisões, queremos considerar objetos colidindo não apenas se estiverem realmente se cruzando, mas também se estiverem muito próximos um do outro, o que exige que conheçamos a distância entre eles. O algoritmo Gilbert-Johnson-Keerthi (GJK) calcula a distância entre duas formas convexas e também seus pontos mais próximos. É um algoritmo elegante que trabalha com uma representação implícita de formas convexas por meio de funções de suporte, somas de Minkowski e simplexes, conforme explicado abaixo.

Funções de suporte

Uma função de suporte s A ( d ) retorna um ponto no limite da forma A que tem a projeção mais alta no vetor d . Matematicamente, tem o maior produto escalar com d . Isso é chamado de ponto de suporte e essa operação também é conhecida como mapeamento de suporte . Geometricamente, este ponto é o ponto mais distante na forma na direção de d .

Encontrar um ponto de apoio em um polígono é relativamente fácil. Para um ponto de suporte para o vetor d , você só precisa percorrer seus vértices e encontrar aquele que tem o maior produto escalar com d , assim:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

No entanto, o verdadeiro poder de uma função de suporte é que facilita o trabalho com formas como cones, cilindros e elipses, entre outras. É bastante difícil calcular a distância entre essas formas diretamente e, sem um algoritmo como o GJK, você normalmente teria que discretizá-las em um polígono ou poliedro para tornar as coisas mais simples. No entanto, isso pode levar a mais problemas porque a superfície de um poliedro não é tão lisa quanto a superfície de, digamos, uma esfera, a menos que o poliedro seja muito detalhado, o que pode levar a um desempenho ruim durante a detecção de colisão. Outros efeitos colaterais indesejáveis ​​também podem aparecer; por exemplo, uma esfera “poliédrica” pode não rolar suavemente.

Para obter um ponto de apoio para uma esfera centrada na origem, basta normalizar d (ou seja, calcular d / || d || , que é um vetor de comprimento 1 (comprimento unitário) que ainda aponta na mesma direção de d ) e então multiplicamos pelo raio da esfera.

Confira o artigo de Gino van den Bergen para encontrar mais exemplos de funções de suporte para cilindros e cones, entre outras formas.

Nossos objetos serão, é claro, deslocados e rotacionados a partir da origem no espaço de simulação, então precisamos ser capazes de calcular pontos de suporte para uma forma transformada. Usamos uma transformação afim T ( x ) = R x + c para deslocar e girar nossos objetos, onde c é o vetor de deslocamento e R é a matriz de rotação . Essa transformação primeiro gira o objeto em torno da origem e depois o traduz. A função de suporte para uma forma transformada A é:

Somas Minkowski

A soma de Minkowski de duas formas A e B é definida como:

Isso significa que calculamos a soma de todos os pontos contidos em A e B . O resultado é como inflar A com B.

Da mesma forma, definimos a diferença de Minkowski como:

que também podemos escrever como a soma de Minkowski de A com -B :

Para A e B convexos, A⊕B também é convexo.

Uma propriedade útil da diferença de Minkowski é que se ela contém a origem do espaço, as formas se cruzam, como pode ser visto na imagem anterior. Por que é que? Porque se duas formas se cruzam, elas têm pelo menos um ponto em comum, que está no mesmo local no espaço, e sua diferença é o vetor zero, que na verdade é a origem.

Outra característica interessante da diferença de Minkowski é que se ela não contém a origem, a distância mínima entre a origem e a diferença de Minkowski é a distância entre as formas.

A distância entre duas formas é definida como:

Em outras palavras, a distância entre A e B é o comprimento do menor vetor que vai de A a B. Este vetor está contido em A⊖B e é o de menor comprimento, que consequentemente é o mais próximo da origem.

Geralmente não é simples construir explicitamente a soma de Minkowski de duas formas. Felizmente, também podemos usar o mapeamento de suporte aqui, pois:

Simplex

O algoritmo GJK procura iterativamente o ponto na diferença de Minkowski mais próximo da origem. Ele faz isso construindo uma série de simplexes que estão mais próximos da origem em cada iteração. Um simplex – ou mais especificamente, um k-simplex para um inteiro k – é o casco convexo de k + 1 pontos afinmente independentes em um espaço k-dimensional. Ou seja, se para dois pontos eles não devem coincidir, para três pontos eles também não devem estar na mesma linha, e se temos quatro pontos eles também não devem estar no mesmo plano. Assim, o 0-simplex é um ponto, o 1-simplex é um segmento de reta, o 2-simplex é um triângulo e o 3-simplex é um tetraedro. Se removermos um ponto de um simplex, diminuiremos sua dimensionalidade em um, e se adicionarmos um ponto a um simplex, aumentaremos sua dimensionalidade em um.

GJK em Ação

Vamos juntar tudo isso para ver como o GJK funciona. Para determinar a distância entre duas formas A e B , começamos tomando sua diferença de Minkowski A⊖B . Estamos procurando o ponto mais próximo da origem na forma resultante, pois a distância até esse ponto é a distância entre as duas formas originais. Escolhemos algum ponto v em A⊖B , que será nossa aproximação de distância. Também definimos um conjunto de pontos vazio W , que conterá os pontos no simplex de teste atual.

Então entramos em um loop. Começamos por obter o ponto de suporte w = s A⊖B (- v ) , o ponto em A⊖B cuja projeção em v está mais próxima da origem.

Se || w || não é muito diferente de || v || e o ângulo entre eles não mudou muito (de acordo com algumas tolerâncias pré-definidas), significa que o algoritmo convergiu e podemos retornar || v || como a distância.

Caso contrário, adicionamos w a W . Se o casco convexo de W (isto é, o simplex) contém a origem, as formas se cruzam, e isso também significa que terminamos. Caso contrário, encontramos o ponto no simplex que está mais próximo da origem e, em seguida, redefinimos v para ser essa nova aproximação mais próxima. Finalmente, removemos quaisquer pontos em W que não contribuam para o cálculo do ponto mais próximo. (Por exemplo, se tivermos um triângulo, e o ponto mais próximo da origem estiver em uma de suas arestas, podemos retirar de W o ponto que não é vértice dessa aresta.) Em seguida, repetimos esses mesmos passos até que o algoritmo converge.

A próxima imagem mostra um exemplo de quatro iterações do algoritmo GJK. O objeto azul representa a diferença A⊖B de Minkowski e o vetor verde é v . Você pode ver aqui como v afia no ponto mais próximo da origem.

Para uma explicação detalhada e aprofundada do algoritmo GJK, confira o artigo A Fast and Robust GJK Implementation for Collision Detection of Convex Objects , de Gino van den Bergen. O blog para o motor de física dyn4j também tem um ótimo post sobre GJK.

Box2D tem uma implementação do algoritmo GJK em b2Distance.cpp, na função b2Distance . Ele só usa GJK durante o cálculo do tempo de impacto em seu algoritmo para detecção de colisão contínua (um tópico que discutiremos mais adiante).

O mecanismo de física Chimpunk usa GJK para todas as detecções de colisão, e sua implementação está em cpCollision.c, na função GJK . Se o algoritmo GJK relatar interseção, ele ainda precisa saber quais são os pontos de contato, juntamente com a profundidade de penetração. Para isso, utiliza o Algoritmo de Polítopo em Expansão, que exploraremos a seguir.

Determinando a Profundidade de Penetração - O Algoritmo do Polítopo em Expansão

Como dito acima, se as formas A e B estiverem se cruzando, GJK irá gerar um simplex W que contém a origem, dentro da diferença A⊖B de Minkowski. Neste estágio, sabemos apenas que as formas se cruzam, mas no projeto de muitos sistemas de detecção de colisão, é desejável poder calcular quanta interseção temos e quais pontos podemos usar como pontos de contato, de modo que lidamos com a colisão de forma realista. O Expanding Polytope Algorithm (EPA) nos permite obter essa informação, começando de onde GJK parou: com um simplex que contém a origem.

A profundidade de penetração é o comprimento do vetor de translação mínimo (MTV), que é o menor vetor ao longo do qual podemos transladar uma forma de interseção para separá-la da outra forma.

Quando duas formas se cruzam, sua diferença de Minkowski contém a origem, e o ponto no limite da diferença de Minkowski que está mais próximo da origem é o MTV. O algoritmo da EPA encontra esse ponto expandindo o simplex que GJK nos deu em um polígono; subdividindo sucessivamente suas arestas com novos vértices.

Primeiro, encontramos a aresta do simplex mais próxima da origem e calculamos o ponto de apoio na diferença de Minkowski em uma direção que é normal à aresta (ou seja, perpendicular a ela e apontando para fora do polígono). Em seguida, dividimos essa aresta adicionando esse ponto de suporte a ela. Repetimos esses passos até que o comprimento e a direção do vetor não mudem muito. Uma vez que o algoritmo converge, temos o MTV e a profundidade de penetração.

Usando GJK em combinação com EPA, obtemos uma descrição detalhada da colisão, não importa se os objetos já estão se cruzando, ou apenas próximos o suficiente para serem considerados uma colisão.

O algoritmo EPA é descrito no artigo Proximity Queries and Penetration Depth Computation on 3D Game Objects , também escrito por Gino van den Bergen. O blog dyn4j também tem um post sobre EPA.

Detecção de Colisão Contínua

As técnicas de física de videogame apresentadas até agora realizam a detecção de colisão para um instantâneo estático da simulação. Isso é chamado de detecção de colisão discreta e ignora o que acontece entre as etapas anteriores e atuais. Por esse motivo, algumas colisões podem não ser detectadas, especialmente para objetos em movimento rápido. Esse problema é conhecido como tunelamento .

As técnicas de detecção de colisão contínua tentam descobrir quando dois corpos colidiram entre a etapa anterior e a atual da simulação. Eles calculam o tempo de impacto , então podemos voltar no tempo e processar a colisão naquele ponto.

O tempo de impacto (ou tempo de contato) t c é o instante de tempo em que a distância entre dois corpos é zero. Se pudermos escrever uma função para a distância entre dois corpos ao longo do tempo, o que queremos encontrar é a menor raiz dessa função. Assim, o tempo de cálculo do impacto é um problema de descoberta de raízes .

Para o cálculo do tempo de impacto, consideramos o estado (posição e orientação) do corpo na etapa anterior no tempo t i -1 , e na etapa atual no tempo t i . Para tornar as coisas mais simples, assumimos movimento linear entre as etapas.

Vamos simplificar o problema assumindo que as formas são círculos. Para dois círculos C 1 e C 2 , com raio r 1 e r 2 , onde seu centro de massa x 1 e x 2 coincidem com seu centróide (isto é, eles giram naturalmente em torno de seu centro de massa), podemos escrever a função distância Como:

Considerando o movimento linear entre passos, podemos escrever a seguinte função para a posição de C 1 de t i -1 a ti

É uma interpolação linear de x 1 ( ti -1 ) a x 1 ( ti ) . O mesmo pode ser feito para x 2 . Para este intervalo podemos escrever outra função de distância:

Defina esta expressão igual a zero e você obterá uma equação quadrática em t . As raízes podem ser encontradas diretamente usando a fórmula quadrática. Se os círculos não se cruzarem, a fórmula quadrática não terá solução. Se o fizerem, pode resultar em uma ou duas raízes. Se tiver apenas uma raiz, esse valor é o tempo de impacto. Se tiver duas raízes, a menor é o momento do impacto e a outra é o momento em que os círculos se separam. Observe que o tempo de impacto aqui é um número de 0 a 1. Não é um tempo em segundos; é apenas um número que podemos usar para interpolar o estado dos corpos para o local preciso onde ocorreu a colisão.

Detecção de Colisão Contínua para Não Círculos

Escrever uma função de distância para outros tipos de formas é difícil, principalmente porque sua distância depende de suas orientações. Por esse motivo, geralmente usamos algoritmos iterativos que aproximam os objetos cada vez mais em cada iteração até que estejam próximos o suficiente para serem considerados colidindo.

O algoritmo de avanço conservador move os corpos para frente (e os gira) iterativamente. Em cada iteração, ele calcula um limite superior para o deslocamento. O algoritmo original é apresentado na tese de doutorado de Brian Mirtich (seção 2.3.2), que considera o movimento balístico de corpos. Este artigo de Erwin Coumans (o autor do Bullet Physics Engine) apresenta uma versão mais simples que usa velocidades lineares e angulares constantes.

O algoritmo calcula os pontos mais próximos entre as formas A e B , desenha um vetor de um ponto ao outro e projeta a velocidade nesse vetor para calcular um limite superior para o movimento. Garante que nenhum ponto do corpo se mova além dessa projeção. Em seguida, avança os corpos nessa quantidade e repete até que a distância caia abaixo de um pequeno valor de tolerância.

Pode levar muitas iterações para convergir em alguns casos, por exemplo, quando a velocidade angular de um dos corpos é muito alta.

Resolvendo colisões

Uma vez que uma colisão foi detectada, é necessário alterar os movimentos dos objetos em colisão de forma realista, como fazer com que eles quiquem uns nos outros. Na próxima e última parte dessas teorias, discutiremos alguns métodos populares para resolver colisões em videogames.

Referências

Se você estiver interessado em obter uma compreensão mais profunda sobre física de colisões, como algoritmos e técnicas de detecção de colisões, o livro Real-Time Collision Detection , de Christer Ericson, é obrigatório.

Como a detecção de colisões depende muito da geometria, o artigo da Toptal Computational Geometry in Python: From Theory to Application é uma excelente introdução ao tópico.