Esta é a Parte II de nossa série de três partes sobre física de videogame. Para o restante desta série, consulte:
Parte I: Uma Introdução à Dinâmica de Corpo Rígido
Parte III: Simulação de corpo rígido restrito
Na Parte I desta série, exploramos corpos rígidos e seus movimentos. Nessa discussão, no entanto, os objetos não interagiram uns com os outros. Sem algum trabalho adicional, os corpos rígidos simulados podem se cruzar ou se “interpenetrar”, 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 cada vez que se movem e, se o fizerem, temos que fazer algo a respeito, como aplicar forças que mudam suas velocidades. que eles se moverão na direção oposta. É aqui que a compreensão da física de colisão é particularmente importante para desenvolvedores de jogos .
Na Parte II, cobriremos 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 parcela, falaremos mais sobre como 'resolver' essas colisões para eliminar interpenetrações.
Para uma revisão dos conceitos de álgebra linear referidos 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 fica abaixo de uma pequena tolerância.
Se tiver-mos n corpos em nossa simulação, a complexidade computacional de detectar colisões com testes de pares é OU ( 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ão, geralmente o dividimos em duas fases: fase ampla e fase estreita .
A fase ampla é responsável por encontrar pares de corpos rígidos que são potencialmente colidindo, e excluindo pares que certamente não estão colidindo, de todo o conjunto de corpos que estão na simulação. Esta etapa deve ser capaz de escalar muito bem com o número de corpos rígidos para garantir que fiquemos bem abaixo do OU ( n 2)complexidade do tempo. Para conseguir isso, esta fase geralmente usa particionamento do espaço acompanhado de volumes limitados que estabelecem um limite superior para colisão.
A fase estreita opera nos pares de corpos rígidos encontrados pela fase ampla que podem estar colidindo. É uma etapa de refinamento em que determinamos se as colisões estão realmente acontecendo e, para cada colisão encontrada, calculamos 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 ampla fase da física de colisão para videogames, precisamos identificar quais pares de corpos rígidos poderia 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 envolver o objeto. Se estes volumes limitados não se cruzam, então as formas reais também não se cruzam. Se eles se cruzam, então as formas reais poderia se cruzam.
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 min campo representa a localização do canto esquerdo inferior da caixa e max campo representa o canto superior direito.
Para testar se dois AABBs se cruzam, só precisamos descobrir se suas projeções se cruzam em todos os eixos coordenados:
BOOL TestAABBOverlap(AABB* a, AABB* b) d2y > 0.0f) return FALSE; return TRUE; Este código tem a mesma lógica do b2TestOverlap função do Box2D motor (versão 2.3.0). Ele calcula a diferença entre min e max de ambos 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 cada par possível, uma vez que ainda temos o indesejável OU ( n 2)complexidade do tempo. Para minimizar o número de testes de sobreposição AABB, podemos usar algum tipo de particionamento do espaço , que funciona com os mesmos princípios que í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 os í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 mais de perto em dois algoritmos de particionamento espacial populares: ordenar e varrer e hierarquias de volume limitante (BVH).
O algoritmo de classificação e varredura
o classificar e varrer método (alternativamente conhecido como varrer e podar ) é uma das escolhas favoritas entre os programadores de física para uso na simulação de corpo rígido. o Bullet Physics motor, por exemplo, tem uma implementação deste método no btAxisSweep3 classe.
A projeção de um AABB em um único eixo coordenado é essencialmente um intervalo[ b , é ](isto é, começo 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 cruzando.
No algoritmo de classificação e varredura, inserimos todos b e é valores em uma única lista e classifique-a em ordem crescente por seus valores escalares. Então nós varrer ou percorra a lista. Sempre que um b valor é encontrado, seu intervalo correspondente é armazenado em uma lista separada de intervalos ativos , e sempre que um é valor for encontrado, seu intervalo correspondente será removido da lista de intervalos ativos. A qualquer momento, todos os intervalos ativos estão se cruzando. (Verificação de saída Tese de Ph. D de David Baraff , p. 52 para detalhes. Eu 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 tipo de inserção , que é bom em classificar listas quase classificadas.
Em duas e três dimensões, executar a classificação e varredura, conforme descrito acima, sobre um único eixo de coordenada reduzirá o número de testes de interseção AABB diretos que devem ser realizados, mas o retorno pode ser melhor em um eixo de coordenada do que em outro. Portanto, variações mais sofisticadas do algoritmo de classificação e varredura são implementadas. No livro dele Detecção de colisão em tempo real (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 pelo min valor dos AABBs no eixo escolhido, usando ordenação rápida . Em seguida, a matriz é percorrida e os testes de sobreposição AABB são realizados. Para determinar o próximo eixo que deve ser usado para classificação, o variância do centro dos AABBs é calculado, e o eixo com maior variância é escolhido para a próxima etapa.
Árvores de volume delimitador dinâmico
Outro método de particionamento espacial útil é o árvore de volume de limitação dinâmica , também conhecido como Dbvt . Este é um tipo de hierarquia de volume delimitadora .
O Dbvt é uma árvore binária em que cada nó possui um AABB que delimita todos os AABBs de seus filhos. Os AABBs dos próprios corpos rígidos estão localizados nos nós de folha. Normalmente, um Dbvt é “consultado” fornecendo o AABB para o qual gostaríamos de detectar interseções. Esta 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 através da árvore apenas para nós AABB que se cruzam com o AABB consultado. A árvore pode ser equilibrada através de rotação de árvore , como em um Árvore AVL .
Box2D tem uma implementação sofisticada de Dbvt no b2DynamicTree classe . o b2BroadPhase classe é responsável por realizar a fase ampla e usa uma instância de b2DynamicTree para realizar consultas AABB.
Fase Estreita
Após a ampla fase da física de colisão de videogame, temos um conjunto de pares de corpos rígidos que sã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 estão se cruzando ou se sua distância cai abaixo de um valor de tolerância pequeno. Também precisamos saber quais são os pontos de contato entre os corpos em colisão, 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 difícil é a convexidade da forma. As formas podem ser convexo ou côncavo e 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 é verdadeiro para todos os segmentos de linha possíveis conectando os pontos na forma. Se você puder encontrar pelo menos um segmento de linha que esteja fora da forma, então a forma é côncava.
Computacionalmente, é desejável que todas as formas sejam convexas em uma simulação, uma vez que temos muitos algoritmos de teste de distância e interseção poderosos que trabalham com formas convexas. No entanto, nem todos os objetos serão convexos, e normalmente trabalhamos em torno deles de duas maneiras: casca convexa 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 volta de todos os pregos. Para calcular o casco convexo de um polígono ou poliedro, ou mais geralmente, de um conjunto de pontos, um bom algoritmo a ser usado é o casco rápido algoritmo, que tem uma complexidade de tempo média de OU ( n registro 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, uma vez que 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, em seguida, colocarmos uma caixa sobre ele, 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 irrealistas não são muito perceptíveis ou porque suas propriedades côncavas não são essenciais para o que quer que esteja 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 uma tigela fisicamente, não seremos capazes de colocar nada dentro dela. Os objetos irão apenas flutuar em cima dele. Neste caso, podemos usar um 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 podem se tornar proibitivamente caras para calcular e usar. No entanto, uma aproximação costuma ser boa o suficiente e, portanto, algoritmos como V-HACD produz um pequeno conjunto de poliedros convexos de um poliedro côncavo.
Em muitos casos de colisões de física, 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. Visto que o desempenho é um dos aspectos mais importantes nas 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 para interseções - o teorema do eixo de separação
o teorema do eixo de separação (SAT) afirma que duas formas convexas não estão se cruzando se e somente se houver pelo menos um eixo onde as projeções ortogonais das formas neste eixo não se cruzam.
Geralmente é mais intuitivo visualmente encontrar uma linha em 2D ou um plano em 3D que separa as duas formas, no entanto, 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 o “eixo de separação”.
Os motores de física do jogo têm várias classes diferentes de formas, como círculos (esferas em 3D), arestas (um único segmento de linha) e polígonos convexos (poliedros em 3D). Para cada par de tipo de forma, eles têm um algoritmo de detecção de colisão específico. 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; } Mesmo que o SAT se aplique a círculos, é muito mais simples apenas verificar se a distância entre seus centros é menor do 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 para separação. Portanto, determinar qual eixo testar primeiro é crucial para uma implementação SAT eficiente. Felizmente, ao testar se um par de polígonos convexos colide, podemos usar as normais de aresta 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 são em frente da borda.
Se algum teste passar - ou seja, se, para qualquer aresta, todos os vértices do outro polígono forem em frente dele - 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 para e b e um vértice v na outra forma, se( v - para ) n for maior que zero, o vértice estará na frente da aresta.
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; entretanto, para agilizar 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 em cache não separar mais as formas, podemos pesquisar um novo eixo começando nas faces ou arestas adjacentes à face ou aresta anterior. Isso funciona porque os corpos muitas vezes 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 de computação - Algoritmo Gilbert-Johnson-Keerthi
Em muitos casos da física de colisões, queremos considerar que os objetos estão colidindo não apenas se eles estão realmente se cruzando, mas também se estão muito próximos uns dos outros, o que exige que saibamos a distância entre eles. o Gilbert-Johnson-Keerthi O algoritmo (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 a seguir.
Funções de Suporte
PARA função de suporte s PARA( d )retorna um ponto no limite da formaPARAque tem a maior projeção no vetor d . Matematicamente, tem o maior produto escalar com d . Isso é chamado de ponto de apoio , e esta operação também é conhecida como mapeamento de suporte . Geometricamente, este ponto é o ponto mais distante da forma na direção de d .
Encontrar um ponto de apoio em um polígono é relativamente fácil. Para um ponto de apoio para vetor d , você apenas tem que percorrer seus vértices e encontrar aquele que tem o maior produto escalar com d , como isso:
Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i highest) { highest = dot; support = v; } } return support; } Porém, o verdadeiro poder de uma função de suporte é que facilita o trabalho com formas como cones, cilindros e elipses, entre outros. É 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, só temos que normalizar d (isto é, computar d / || d ||, que é um vetor com comprimento 1 (comprimento unitário) que ainda aponta na mesma direção de d ) e então o multiplicamos pelo raio da esfera.
Verifica Artigo de Gino van den Bergen para encontrar mais exemplos de funções de suporte para cilindros e cones, entre outras formas.
Nossos objetos, é claro, serão deslocados e girados da origem no espaço de simulação, portanto, precisamos ser capazes de calcular pontos de suporte para uma forma transformada. Nós usamos um transformação afim T ( x ) = R x + c para deslocar e girar nossos objetos, onde c é o vetor de deslocamento e R é o matriz de rotação . Essa transformação primeiro gira o objeto sobre a origem e, em seguida, o traduz. A função de suporte para uma forma transformadaPARAé:
Minkowski Sums
o Soma de Minkowski de duas formasPARAeBé definido como:
Isso significa que calculamos a soma de todos os pontos contidos emPARAeB. O resultado é como inflando PARAcomB.
Da mesma forma, definimos o Diferença de Minkowski Como:
que também podemos escrever como a soma de Minkowski dePARAcom-B:
adicione um listener de evento de clique no botão. passe uma função vazia como o segundo parâmetro.
Para convexoPARAeB,A⊕Btambé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 fica 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 entrePARAeBé o comprimento do menor vetor que vai dePARAparaB. Este vetor está contido emA⊖Be é o que tem o menor comprimento, que conseqüentemente é 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:
Simplexes
O algoritmo GJK procura iterativamente pelo ponto na diferença de Minkowski mais próximo da origem. Ele faz isso criando 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 inteiropara- é o casco convexo dek + 1 afinamente independente pontos em um espaço k-dimensional. Isto é, 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 tivermos quatro pontos, eles também não devem estar no mesmo plano. Portanto, 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, diminuímos sua dimensionalidade em um, e se adicionarmos um ponto a um simplex, incrementamos 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 formasPARAeB, começamos pegando a diferença de MinkowskiA⊖B. Estamos procurando o ponto mais próximo da origem na forma resultante, pois a distância até este ponto é a distância entre as duas formas originais. Nós escolhemos algum ponto v dentroA⊖B, que será nossa aproximação de distância. Também definimos um conjunto de pontos vazioDENTRO, que conterá os pontos no simplex de teste atual.
Então entramos em um loop. Começamos obtendo o ponto de apoio dentro = sA⊖B(- v ), o ponto sobreA⊖Bcuja projeção em v é o mais próximo da origem.
E se|| dentro ||não é muito diferente de|| v ||e o ângulo entre eles não mudou muito (de acordo com algumas tolerâncias predefinidas), isso significa que o algoritmo convergiu e podemos retornar|| v ||como a distância.
Caso contrário, nós adicionamos dentro paraDENTRO. Se o casco convexo deDENTRO(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 então redefinimos v para ser esta nova aproximação mais próxima. Finalmente, removemos todos os pontos emDENTROque não contribuem 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 remover o ponto deDENTROesse não é um vértice dessa aresta.) Em seguida, repetimos esses mesmos passos até que o algoritmo convirja.
A próxima imagem mostra um exemplo de quatro iterações do algoritmo GJK. O objeto azul representa a diferença MinkowskiA⊖Be 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, verifique o artigo Uma implementação GJK rápida e robusta para detecção de colisão de objetos convexos , de Gino van den Bergen. O blog para o dyn4j motor de física também tem um ótima postagem no GJK .
Box2D tem uma implementação do algoritmo GJK em b2Distance.cpp , no b2Distance função. 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 motor de física Chimpunk usa GJK para todas as detecções de colisão, e sua implementação está em cpCollision.c , no GJK função. Se o algoritmo GJK relatar interseção, ele ainda precisa saber quais são os pontos de contato, junto com a profundidade de penetração. Para fazer isso, ele usa o Algoritmo de Polítopo de Expansão, que exploraremos a seguir.
Determinando a profundidade de penetração - o algoritmo de expansão do politopo
Como afirmado acima, se as formasPARAeBestão se cruzando, GJK irá gerar um simplexDENTROque contém a origem, dentro da diferença de MinkowskiA⊖B. Neste estágio, sabemos apenas que as formas se cruzam, mas no projeto de muitos sistemas de detecção de colisões, é desejável ser capaz de calcular quanta intersecção temos e quais pontos podemos usar como pontos de contato, de modo que lidamos com a colisão de forma realista. o Algoritmo de expansão do politopo (EPA) nos permite obter essa informação, começando de onde GJK parou: com um simplex que contém a origem.
o profundidade de penetração é o comprimento do vetor de tradução mínimo (MTV), que é o menor vetor ao longo do qual podemos traduzir 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 é a MTV. O algoritmo 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 este ponto de suporte a ela. Repetimos essas etapas até que o comprimento e a direção do vetor não mudem muito. Uma vez que o algoritmo converge, temos a 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 perto o suficiente para ser considerada uma colisão.
O algoritmo EPA é descrito no artigo Consultas de proximidade e computação de profundidade de penetração em objetos de jogo 3D , também escrito por Gino van den Bergen. O blog dyn4j também tem um postar sobre EPA .
Detecção Contínua de Colisão
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 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. Este problema é conhecido como tunelamento .
Técnicas de detecção de colisão contínua tentam encontrar quando dois corpos colidiram entre a etapa anterior e a atual da simulação. Eles calculam o hora do impacto , para que possamos voltar no tempo e processar a colisão naquele ponto.
A hora do impacto (ou hora do 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 é o menor raiz desta função. Assim, o tempo de cálculo do impacto é um problema de encontrar raízes .
Para o momento do cálculo do impacto, consideramos o estado (posição e orientação) do corpo na etapa anterior no momento t Eu -1, e na etapa atual no momento t Eu . Para tornar as coisas mais simples, assumimos um movimento linear entre as etapas.
Vamos simplificar o problema assumindo que as formas são círculos. Para dois círculos C 1e C 2, com raio r 1e r 2, onde seu centro de massa x 1e x 2coincidir com seu centroide (ou seja, eles giram naturalmente em torno de seu centro de massa), podemos escrever a função de distância como:
Considerando o movimento linear entre as etapas, podemos escrever a seguinte função para a posição de C 1a partir de t Eu -1para t Eu
É uma interpolação linear de x 1( t Eu -1)para x 1( t Eu ). O mesmo pode ser feito por x 2. Para este intervalo, podemos escrever outra função de distância:
Defina esta expressão igual a zero e você obterá um Equação quadrática em t . As raízes podem ser encontradas diretamente usando o Fórmula quadrática . Se os círculos não se cruzam, a fórmula quadrática não terá uma solução. Se o fizerem, pode resultar em uma ou duas raízes. Se tiver apenas uma raiz, esse valor é o momento do 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 do 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 a colisão aconteceu.
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 movem os objetos cada vez mais perto em cada iteração até que eles sejam perto o suficiente para ser considerado colidir.
o avanço conservador algoritmo 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 em Tese de PhD de Brian Mirtich (seção 2.3.2), que considera o movimento balístico dos corpos. Este papel por 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 formasPARAeB, desenha um vetor de um ponto a outro e projeta a velocidade nesse vetor para calcular um limite superior para o movimento. Isso garante que nenhum ponto do corpo se moverá além dessa projeção. Em seguida, ele 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
Assim que uma colisão for detectada, é necessário alterar os movimentos dos objetos em colisão de uma forma realista, fazendo com que eles batam um no outro. Na próxima e última parte destas teorias, discutiremos alguns métodos populares para resolver colisões em videogames.
Referências
Se você estiver interessado em obter um entendimento mais profundo sobre a física de colisão, como algoritmos e técnicas de detecção de colisão, o livro Detecção de colisão em tempo real , de Christer Ericson, é um must-have.
Uma vez que a detecção de colisão depende muito da geometria, o artigo de ApeeScape Geometria computacional em Python: da teoria à aplicação é uma excelente introdução ao tópico.
Relacionado: Um tutorial introdutório de programação de robôs
