Simulação Física de Corpos
Rígidos com Detecção e Reação
à Colisões
Detecção de Colisões
• Para N objetos, temos C(N,2) possíveis
colisões.
• Novas colisões surgem a cada frame
gerado.
• Testar todas possibilidades? O(n^2)
– 40 objetos = 780 testes
Computar só o necessário
• Objetos que não possuem nenhuma chance de
colisão não devem ser testados em um
algoritmo eficiente.
Detecção de Colisões
Solução usada: Algoritmo com duas etapas
• Etapa ampla: Detectamos, com baixa
precisão, objetos que possuem alguma
chance de colisão.
• Etapa “narrow”: Usamos os pares da
etapa anterior para o algoritmo preciso de
colisão
Sweep and Prune
• Usamos uma forma geométrica mais
simples para testar por possíveis colisões.
Como temos objetos em
movimento, temos que
fazer uma modificação na
caixa que envolve cada
esfera.
Interação com Usuário
• “Clicar” nos objetos para selecioná-los.
• Para N objetos, levamos tempo linear para
testar a posição do ponteiro com cada
objeto.
• O(n) é OK, mas podemos fazer melhor!
Divisão de espaço
• Dividimos a nossa área de simulação em
um formato de árvore binária.
(esquerda/direita, baixo/cima).
• Somente testamos o mouse contra
objetos da área clicada.
Por que não usar a divisão de espaço
também para a detecção de colisão?
• Alto custo para manter a árvore
atualizada! (com um algoritmo simples)
• Bom para ambientes estáticos.