Broad phase e narrow phase de colisão: candidatos versus contatos

Por que dividir o trabalho de colisão?

Um pipeline de colisão tem duas tarefas distintas: descobrir quais formas podem interagir e, depois, determinar o que a geometria delas de fato indica. Confundir as duas gera visualizações de depuração enganosas e otimizações no lugar errado. Uma bounding box sobreposta é um motivo para investigar, não prova suficiente de que dois objetos do jogo se tocaram.

O contrato dos candidatos

A broad phase usa limites conservadores para evitar testar todos os pares de formas. A árvore dinâmica do Box2D organiza limites alinhados aos eixos em uma hierarquia binária. [1] As rotinas da narrow phase trabalham sobre as próprias formas e podem produzir manifolds de contato, com pontos de contato e uma normal. A filtragem de colisão e o solver de restrições, que atua depois, têm responsabilidades distintas. [2]

Exemplo prático

Imagine 100 caixotes em movimento. Testar todos os pares não ordenados exigiria 100 × 99 / 2 = 4950 testes de par. Suponha que uma consulta espacial, a título de ilustração, produza 180 candidatos após a filtragem por camadas, e que os testes geométricos encontrem 24 pares em contato. Esses números são inventados para explicar as etapas do pipeline; não são um resultado de desempenho.

Um caixote comprido e girado na diagonal pode ter uma caixa alinhada aos eixos grande, com cantos vazios. Outro caixote que entre em um desses cantos deve passar pela broad phase, mas falhar no teste de forma. Tratar cada um dos 180 candidatos como colisão geraria eventos de dano falsos. Por outro lado, um limite que não contenha por completo a sua forma pode descartar um contato real antes de a narrow phase chegar a vê-lo.

Fluxo de trabalho na prática

Defina quem atualiza os proxies espaciais após movimento, redimensionamento, ativação ou destruição. Use identidades de par estáveis, para que a redescoberta repetida de um par não crie eventos de jogo duplicados. Decida se os filtros se aplicam antes da emissão de candidatos, antes do teste de forma ou nos dois pontos, e documente as regras que possam mudar durante o jogo.

Meça separadamente a quantidade de candidatos, a quantidade de contatos reais, o custo de atualização da árvore e o custo dos testes geométricos. Em uma cena de diagnóstico, visualize tanto a forma real quanto os seus limites. Inclua objetos finos e girados, pilhas densas e um objeto grande em movimento entre vários pequenos. Analise os contatos perdidos antes de ajustar a redução de candidatos.

Compromissos e limites

Limites folgados podem reduzir a manutenção do índice espacial, mas admitem mais candidatos. Limites justos podem inverter esse equilíbrio. Uma grade, uma árvore ou um sweep-and-prune deve ser avaliado em relação ao tamanho dos objetos, ao movimento e à densidade da carga de trabalho prevista.

Cenas densas ainda podem produzir muitos pares válidos; uma estrutura espacial não faz desaparecer interações inevitáveis. Mantenha separadamente observáveis a sobreposição da broad phase, o contato da narrow phase, a resposta do solver e a política de acerto do jogo. A detecção contínua de colisão também exige uma política de consulta que leve o tempo em conta; a sobreposição estática na posição final, sozinha, não cobre um intervalo de movimento.

Fontes

[1] Dynamic tree — Erin Catto e colaboradores do Box2D.

[2] Collision — Erin Catto e colaboradores do Box2D.