Como se executa a detecção de colisões em objetos feitos de muitos pequenos triângulos?
13
Entendo que qualquer forma pode ser criada (ou aproximada) por triângulos menores. Qualquer retângulo pode ser criado por 2 triângulos menores. Qualquer círculo pode ser criado por muitos triângulos finos de "fatia de pizza". Como isso se traduz em detecção de colisão?
Eu entendo como calcular a sobreposição de retângulos usando os vértices. Entendo como calcular a sobreposição de círculos usando o centro, raios e distância.
Mas, como é possível detectar colisões em formas feitas de pequenos triângulos? Não é específico, mas apenas o conceito geral ....
Mas, como é possível detectar colisões em formas feitas de pequenos triângulos?
Por não fazer isso.
A detecção de colisão contra uma coleção arbitrária de triângulos (ou pior, entre duas coleções de triângulos arbitrários) é proibitivamente cara.
Em vez disso, normalmente executamos a detecção de coleções de maneira hierárquica, começando primeiro com formas simples extremamente brutas (como caixas ou esferas) que aproximam (mal) o objeto subjacente.
Isso nos permite rejeitar rapidamente a maioria das colisões em potencial como "não ocorrendo", como é o caso usual. No caso em que uma verificação grosseira passa, isso indica uma possível colisão real, e procedemos à verificação em uma aproximação mais detalhada da forma subjacente (como uma feita de várias formas de cápsulas bem ajustadas ou muitas caixas delimitadoras alinhadas).
Essencialmente, a detecção de colisão começa com testes brutos e, à medida que esses testes passam, continua a ter uma representação cada vez mais detalhada. Esta imagem, fornecida por Shiro em um comentário à resposta de Alexandre , ilustra como um modelo complexo (um humano) pode ser representado por uma série de formas mais simples:
Raramente precisamos realmente executar colisão no nível do triângulo individual e, quando o fazemos, geralmente usamos os métodos mais brutos para detalhar um conjunto muito pequeno de triângulos em potencial para testar. Nesse ponto, algoritmos específicos são usados para executar os testes, assim como você testaria se dois retângulos se sobrepusessem. Por exemplo, você pode determinar se e onde um raio atinge um triângulo .
Obrigado. Sim, se eu estivesse realmente fazendo um jogo, usaria apenas algum mecanismo existente. Mas só quero entender as idéias básicas implementadas em um mecanismo de detecção de colisão pré-fabricado. No diagrama acima, você usaria a matemática do retângulo para ver se alguma coisa está tocando em QUALQUER das dezenas de retângulos que compõem o homem. Essa é a ideia básica?
JackOfAll
Essas são caixas delimitadoras orientadas (3D) e não retângulos. Mas sim. Se eu fosse testar se um raio (representando, por exemplo, uma bala) colidia com o jogador, eu estaria testando o raio contra essas caixas - possivelmente após o primeiro teste contra uma caixa gigante representando todo o personagem - e não contra todos triângulo da malha de renderização).
A ideia é que você possa usar uma aproximação aproximada do caractere, como as caixas delimitadoras orientadas mostradas na imagem acima, e testar primeiro para fazer um teste de acerto mais barato e, se houver colisão, faça um drill down para um nível mais baixo SE NECESSÁRIO, teste triângulos individuais contidos na caixa delimitadora. Normalmente, pode haver várias BVs diferentes usadas hierarquicamente, com a externa sendo menos precisa, mas a mais rápida de testar (esfera, caixa delimitadora), e aprofundando-se em algo mais específico (k-DOP), e potencialmente aprofundando ainda mais (triângulos )
Kik
4
A detecção de colisão é baseada na geometria (primitivas como linhas, planos, esferas, caixas, cápsulas, cilindros).
Se você precisar executar a detecção de colisão em formas feitas de triângulo, por exemplo, um terreno que não seja plano, será necessário testar todos os triângulos que formam a malha.
Se você chegar a esse ponto, eu recomendaria fortemente o uso de um mecanismo de detecção de colisão pré-fabricado, pois esse tipo de coisa fica muito complexo, muito rápido.
Como você detecta colisões em formas compostas de triângulos?
26415 JackOfAll
@JackOfAll ele já mencionou que na sua resposta, é usando a geometria molda normalmente i.stack.imgur.com/CAhxn.jpg
dimitris93
@JackOfAll editei minha resposta; e, como Shiro diz, se você tem "itens" mais complexos em seu ambiente (corpos, cadeiras, carros, etc ...), no desenvolvimento de jogos, eles geralmente são feitos de primitivas mais simples que estão ligadas. A detecção de colisões é feita nas formas primitivas, mas a simulação da física é feita em todo o corpo.
Vaillancourt
4
Não estou literalmente tentando fazer um jogo, apenas quero entender as idéias básicas que são implementadas em um mecanismo de detecção de colisão pré-fabricado. Se eu estivesse realmente fazendo um jogo, claramente não estaria reinventando a roda, concordou.
A detecção de colisão é baseada na geometria (primitivas como linhas, planos, esferas, caixas, cápsulas, cilindros).
Se você precisar executar a detecção de colisão em formas feitas de triângulo, por exemplo, um terreno que não seja plano, será necessário testar todos os triângulos que formam a malha.
Se você chegar a esse ponto, eu recomendaria fortemente o uso de um mecanismo de detecção de colisão pré-fabricado, pois esse tipo de coisa fica muito complexo, muito rápido.
fonte