Realidade Virtual
Aula 9
Remis Balaniuk
Colisões
• Aprendemos como representar e mover objetos
tridimensionais.
• Aprendemos também a aplicar as leis da Física
aos objetos.
• Entretanto, no mundo real dois objetos não
podem ocupar o mesmo espaço, embora no
mundo virtual isso pode acontecer.
• Para isso precisamos saber como detectar e
tratar as sobreposições de volume, ou colisões,
de forma a recriar o que seria o comportamento
real.
Colisões
• O tratamento das colisões se dá em duas
etapas:
– Detecção
– Tratamento
• A detecção é um processo contínuo, que se
repete a cada passo de tempo da simulação, e
que verifica se os volumes dos objetos
tridimensionais se interceptam dadas as
posições e orientações em que se encontram.
Colisões
• O tratamento calcula a reação imposta aos
objetos para que se separem, respeitando
obviamente as propriedades físicas e
geométricas do fenômeno.
• Para um estudo aprofundado de detecção de
colisões e para obter código pronto algumas
referências úteis são:
• http://www.cs.unc.edu/~geom/V_COLLIDE/
• http://www.ams.sunysb.edu/~jklosow/quickcd/Qu
ickCD.html
• Nessa disciplina nos limitaremos a um estudo
superficial do assunto e disponibilizaremos
código implementado no Chai.
Colisões
• A detecção de colisões entre objetos
formados por grande número de vértices e
polígonos pode ser um processo muito
custoso, comprometendo inclusive a
performance em tempo real da simulação.
• A detecção de colisões representa
normalmente uma grande parte do esforço
computacional de uma simulação em 3D.
Colisões
• O tratamento de colisões exige um
cuidado especial pois muito do realismo
da simulação depende dele.
• Grandes penetrações ou reações
desproporcionais prejudicam o realismo e
a estabilidade.
Colisões
• A situação mais simples a ser considerada
numa colisão é a de um ponto que se
move na cena.
• Se a trajetória que esse ponto faz no
espaço atravessa um polígonos que
definem uma superfície ou objeto da cena,
então houve colisão.
p1
p0
Colisões
• Então o teste básico de colisão ponto-mesh
consiste em testar para cada triângulo do mesh
se o segmento p0->p1 intercepta o triângulo e
onde (ponto de colisão).
• Note que a colisão só pode ser detectada
quando já houve penetração, ou seja, uma vez
que p1 está dentro do objeto, o que fisicamente
não é muito correto.
• Note também que a detecção não pode perder
nenhum pedaço da trajetória do ponto, uma vez
que a penetração só é detectada no segmento
exato em que a superfície é atravessada.
Colisões
• O teste de intersecção entre um segmento de
reta e um triângulo é implementado no Chai no
método a seguir pertence à classe cTriangle:
inline bool computeCollision(
const cVector3d& a_rayOrigin,
const cVector3d& a_rayDir,
cGenericObject*& a_colObject,
cTriangle*& a_colTriangle,
cVector3d& a_colPoint,
double& a_colSquareDistance);
Colisões
• Um método de “força bruta” iria então
testar, triângulo a triângulo do mesh se a
colisão ocorreu.
• Esse teste bruto seria muito custoso em
objetos complexos, sendo que na enorme
maioria dos casos, no tempo e no espaço,
a colisão não esta acontecendo e esta
muito longe de acontecer.
Colisões
• Para economizar testes
inúteis pode se recorrer
aos chamados “volumes
englobantes”:
• Um volume englobante
(bounding volume) é uma
figura geométrica simples
(esfera ou paralelepipedo)
que envolve o objeto todo
ou uma parte dele.
Colisões
• Antes de começar testes
nos triângulos diretamente,
pode-se testar se existe
colisão com o volume
englobante.
• Se o teste der falso não há
o que fazer, se der
verdadeiro pode-se
aprofundar o teste.
Colisões
• Os volumes englobantes são organizados em
forma de árvore, as chamadas octtrees.
• Na raiz da árvore está o volume que engloba
todo o objeto.
• Nas folhas estão volumes que englobam cada
triângulo.
• Cada teste começa na raiz e desce em direção
às folhas, parando se algum teste falhar.
Colisões
• 3 tipos principais de volumes englobantes
são utilizados:
– Esferas
– Paralelepipedos (caixas) alinhadas aos eixos
do sistemas de coordenadas : AABB – axis
aligned bounding boxes.
– Caixas orientadas (rotacionadas
arbitrariamente): OBB – oriented bounding
boxes.
Colisões
• 2 critérios principais devem ser levados em
consideração ao escolher uma dessas formas:
– Ajuste às formas dos objetos
– Rapidez nos testes de intersecção.
• As esferas são as mais rápidas nos testes de
intersecção (um teste de distância ao centro)
mas são as piores no ajuste à forma dos
objetos.
• As caixas orientadas são as que melhor se
ajustam aos objetos mas a que exigem maior
custo no teste de intersecção.
Colisões
• As colisões entre meshes são ainda mais
complexas.
• A sequência de testes entre os meshes é a
seguinte:
– Detecção de colisão entre volumes envolventes
(raizes das duas árvores e suas subárvores)
– Detecção de colisão entre volumes envolventes das
primitivas que compõem o objeto (folhas)
– Detecção entre primitivas (triângulos) que compõem
os objetos.
Colisões no Chai
• Não é escopo desse curso aprendermos a
implementar detecção de colisões, pois esse é
um tópico complexo, envolvendo conhecimento
aprofundado de geometria.
• O Chai implementa (até o momento) a detecção
de colisões entre segmentos de reta e meshes.
• Isso se deve à prioridade dada no Chai para
implementações com interface háptica, nas
quais se toca os objetos com um ponto.
Colisões no Chai
• O Chai possui uma série de métodos associados à detecção de
colisões.
• Dois métodos foram implementados: as árvores de esferas e as AABBs.
• Para nosso uso o que importa é adicionar à um objeto (cMesh) um
detector de colisões.
• Isso se faz com os métodos:
//! Set up an AABB collision detector for this mesh and
(optionally) its children
virtual void createAABBCollisionDetector(bool
a_affectChildren, bool a_useNeighbors);
//! Set up a sphere tree collision detector for this
mesh and (optionally) its children
virtual void createSphereTreeCollisionDetector(bool
a_affectChildren, bool a_useNeighbors);
Colisões no Chai
• Esses métodos deve ser chamados quando
todos os vértices e triângulos do objeto tiverem
sido criados.
• No momento da chamada será criado o detector
de colisões (cCollisonAABB ou
cCollisionSpheres) e criada a octree de volumes
englobantes.
• Note que a árvore de volumes é construída no
sistema de coordenadas do objeto, de forma
que durante os movimentos do objeto a árvore
não precisa ser reconstruída, mas o segmento
de reta a ser testado precisa ser transformado
para o sistema de coordenadas local.
Colisões no Chai
• Para detectar a colisão entre um segmento de retas e um objeto
usamos o método da classe cGenericObjet:
// Compute collision detection using collision trees
virtual bool computeCollisionDetection(
cVector3d& a_segmentPointA,
cVector3d& a_segmentPointB,
cGenericObject*& a_colObject,
cTriangle*& a_colTriangle,
cVector3d& a_colPoint,
double& a_colSquareDistance,
const bool a_visibleObjectsOnly,
int a_proxyCall,
cGenericPointForceAlgo* force_algo=0);
• Se houver mais de uma colisão é retornada a mais próxima do início
do segmento (a_segmentPointA).
Colisões no Chai
• O mesmo método também é definido para
o mundo (cWorld) de forma que se
pedirmos a detecção de colisão entre um
segmento de reta e o mundo obteremos a
detecção encontrada mais próxima do
início do segmento.
Colisões no Chai
• Como não existe uma detecção meshmesh no Chai, implementei uma solução
“quebra-galho” nas classes dynamicObject
e dynamicWorld.
• A classe dynamicObject implementa um
objeto dinâmico rígido enquanto que a
classe dynamicWorld implementa um
mundo composto por objetos dinâmicos e
estáticos.
Colisões no Chai
• Na classe dynamicObject implementei o método abaixo
que testa a colisão entre o objeto atual e outro passado
como parâmetro:
bool dynamicObject::testCollision(cMesh
*otherOne, cVector3d& contactNormal,
cVector3d& contactPoint, double&
penetration);
• O método retorna TRUE se encontrou uma colisão e
retorna em contactPoint o ponto de contato, em
contactNormal a normal no ponto de contato e em
penetration a penetração do contato dentro do outro
objeto.
Colisões no Chai
• Na classe dynamicWorld implementei o
método:
void checkCollisions();
• Esse método verifica e trata todas as
colisões entre objetos dinâmicos e o resto
da cena virtual (outros objetos dinâmicos
ou estáticos).
Tratamento de colisões
• Como dito anteriormente, após detectar as
colisões é preciso trata-las de forma a simular o
comportamento de objetos reais em colisão.
• O objetivo do tratamento é impedir a
interpenetração e dos objetos.
• Esse tratamento pode ser simplificado,
simplesmente bloqueando (parando os objetos),
embora o mais correto seja recalcular suas
trajetórias de forma a conservar a energia
(quantidade de movimento) do sistema.
Tratamento de colisões
• Basicamente existem duas formas de
alterar a trajetória de um objeto devido a
uma colisão:
– Calcular a força (e torque) de repulsão
causada pela colisão e integrá-la ao estado
dos objetos em colisão
– Calcular diretamente uma mudança nas
velocidades linear e angular de ambos os
objetos.
Tratamento de colisões
• O método que calcula a força de repulsão
se baseia no fato que durante a colisão os
objetos armazenam energia elástica devido
à deformação e que essa energia se traduz
numa força que é aplicada aos objetos
durante a colisão.
• Esse método faz bastante sentido quando
os objetos se deformam durante a colisão,
sendo que dependendo do material de que
são feitos os objetos, a deformação pode
ser totalmente elástica, ou seja, o objeto vai
voltar ao seu formato normal após a colisão
e portanto nenhuma energia vai se perder
no processo, ou inelástica, no qual o objeto
se deforma definitivamente o que dissipa
parte da energia do sistema durante a
colisão.
Tratamento de colisões
• O método que recalcula as velocidades
diretamente, chamado de Impulso, se aplica a
objetos rígidos, para os quais a colisão é
considerada instantânea e nos quais não faria
tanto sentido calcular forças de repulsão.
• Esse método foi proposto num artigo que pode
ser encontrado no link abaixo:
• http://graphics.stanford.edu/courses/cs468-03winter/Papers/ibds.pdf
Tratamento de colisões
• Vamos focar no estudo e implementação do
Impulso, já que estamos lidando somente com
objetos rígidos.
• O cálculo do impulso leva em consideração as
seguintes variáveis:
– Impulso (p):
• O objetivo do método é calcular um vetor correspondente ao
impulso que deve ser aplicado nos objetos (p e –p) alterando
suas velocidades linear e angular.
– Coeficiente de restituição (e):
• Indica quanto da energia cinética dos objetos vai se perder
durante a colisão.
• e=1 indica que a colisão é totalmente elástica, ou seja,
nenhuma energia vai se perder.
• e=0 indica que a colisão é totalmente plastica e que os
objetos após a colisão não vão se separar.
Tratamento de colisões
• Massa do objeto i: mi
• Ji : matriz de inércia do objeto i
• vi : velocidade linear do centro de
massa do objeto i
• wi : velocidade angular do centro de
massa do objeto i
• ui : velocidade absoluta do objeto i
no ponto de contato
• ri : posição do ponto de contato
relativa ao centro de massa do
objeto i
Tratamento de colisões
• O impulso (p e –p) mais as velocidades iniciais
dos objetos (linear e angular) se combinam para
definir as novas velocidades dos objetos após a
colisão.
• Um dado importante para tratar a colisão é a
normal do ponto de colisão.
• A colisão é implementada como sendo DE um
objeto de origem PARA outro de destino.
• A normal da colisão deve corresponder à normal
do ponto de colisão na superfície do objeto de
destino (apontando para o objeto de origem).
Tratamento de colisões
• Implementação:
– No projeto9 as classes dynamicWorld e
dynamicObject foram definidas de forma a
contemplar a dinâmica dos objetos e as
colisões entre eles.
– Um objeto da classe dynamicWorld pode
conter objetos dinâmicos e estáticos e
gerenciar a interação entre eles.
Tratamento de colisões
– Na classe dynamicWorld foram implementados os métodos:
void checkMeshMeshCollision(dynamicObject *mesh1,
cMesh *mesh2);
void CollisionResponse(double e,double ma,
double mb,
cMatrix3d Ia,cMatrix3d Ib,
cVector3d ra,cVector3d rb,cVector3d n,
cVector3d vai, cVector3d vbi,
cVector3d wai, cVector3d wbi,
cVector3d& vaf, cVector3d& vbf,
cVector3d& waf, cVector3d& wbf);
– Nesse último método são passados os dados dos objetos em
colisão e se obtem as novas velocidades a serem atribuídas aos
objetos.
• vaf e vbf serão as novas velocidades lineares dos objetos 1 e 2
• waf e wbf serão as novas velocidades angulares dos objetos 1 e 2.
Tratamento de colisões
– Detalhamento do parâmetros de CollisionResponse:
double e – coeficiente de restituição (entre 0 e 1 - 1:
colisão elástica, 0: colisão plástica)
double ma – massa do objeto 1
double mb – massa do objeto 2
cMatrix3d Ia – matriz de inércia do objeto 1
cMatrix3d Ib - matriz de inércia do objeto 2
(as matrizes de inércia devem ser transformadas para o
sistema de coordenadas global – ver proximo slide)
cVector3d ra – vetor indo do centro de massa do objeto 1
ao ponto de colisão
cVector3d rb - vetor indo do centro de massa do objeto 1
ao ponto de colisão
cVector3d n – normal no ponto de colisão
cVector3d va – velocidade linear do objeto 1
cVector3d vbi - velocidade linear do objeto 2
cVector3d wai - velocidade angular do objeto 1
cVector3d wbi – velocidade angular do objeto 2
Tratamento de colisões
• Para transformar a matriz de inércia de um objeto para o
sistema de coordenadas global faça:
– IG = Rt . IL . R
– Ou seja, a matriz de inércia no sistema global é igual à matriz de
rotação do objeto transposta, multiplicada pela matriz de inércia
local, multiplicada pela matriz de rotação do objeto.
• Essa transformação foi implementada no método:
cMatrix3d dynamicObject::
getInertiaMatrix(bool transform2Global);