2.6 A matemática em ação: Polígonos e Colisões

Ao longo da aula vimos alguns conceitos relacionados a polígonos. Agora, estudaremos a aplicação desses conceitos a jogos digitais, através do estudo da colisão de objetos que compõe um jogo 2D qualquer.

Começaremos lembrando que, inicialmente, um mundo virtual não contém qualquer tipo de física. Não há inércia, não há gravidade e também não há qualquer tipo de solidez. Os objetos envolvidos simplesmente passarão por dentro de outros objetos, sem qualquer colisão. Para modificar isso, podemos adicionar essa solidez através da detecção de colisões.

A detecção de colisões determina quando dois objetos colidem ou não, apesar de parecer simples, computacionalmente não é. Quanto mais complexos são os objetos, mais complicado de se detectar a colisão e, com isso, maior é o gasto computacional para realizar essa operação.

Considere o polígono formado por 20 pontos, exibido na Figura 29:

Imagine a detecção de colisão sendo feita para esse polígono como está exibido. Deveríamos testar se o objeto alvo está, de alguma maneira, em contato com qualquer parte da superfície. Isso incluiria testes se o objeto está na posição indicada pelo ponto A, que é uma região delicada externa ao polígono.

Agora, lembre-se que esses testes de colisão devem ser feitos a cada frame. Toda vez que os objetos são movidos, novos testes devem ser feitos com todos os objetos. Existem algumas técnicas para melhorar esse processo, mas inicialmente, sendo n o número de objetos na cena, precisaremos realizar $n \cdot (n+1)$ cálculos a cada frame. Para garantir a performance do nosso jogo, a primeira coisa que pensamos é que, no mínimo, esses cálculos devem ter a menor complexidade possível. Para isso, podemos simplificar o polígono contra o qual realizaremos o teste de colisão. Uma maneira de fazer isso é definindo o fecho convexo do nosso polígono inicial. Observe a Figura 30:

Agora que temos um novo polígono, mais simples que o anterior, definido pelo fecho convexo exibido (em azul) na imagem, podemos realizar os testes de colisão contra esse novo polígono, o que resulta em operações menos complexas, otimizando, assim, o processamento dos frames do nosso jogo. Isso acontece a custo da detecção se tornar menos precisa, porém, se necessário, é possível utilizar o próprio polígono para detectar a colisão, usando o fecho convexo apenas como filtro, a descartar colisões que não ocorreram.

Se vocês buscarem na memória (ou no material), lembrarão que na Aula 01 estudamos uma das formas mais simples de colisão, utilizando círculos para representar os elementos e a simples distância entre pontos como forma de calcular a colisão ou não. Perceba que agora temos um método mais preciso para calcular essas colisões, uma vez que não mais temos um círculo como representação e sim um fecho convexo que, como visto, é a menor região convexa contendo todos os pontos de um polígono qualquer. Ou seja, agora já estamos melhorando a detecção de colisões que, de fato, ocorreram, lidando menos com colisões que não deveriam ter ocorrido.

Para que a detecção possa acontecer da melhor maneira possível, podemos adicionar ainda uma nova fase para lidar com o polígono original diretamente. Após utilizarmos o fecho convexo para descartar, através de operações mais simples, os casos em que não há colisão, podemos passar ao próprio polígono para testar a ocorrência ou não de colisão. Podemos fazer isso utilizando uma das técnicas estudadas de posição relativa entre polígonos e pontos para descobrir se o objeto está dentro ou fora de nosso polígono.