Game physics

Nilson Souto - xissburg - Twitter @xissburg - http://xissburg.com

Simulação de Física em Games

Conteúdo•Fenômenos físicos que nos interessam •Engines de Física •Simulação de Partículas •Simulação de Corpos Rígidos •Constraints •Colisões •Alguns Engines Populares

Fenômenos Físicos•Diversos fenômenos físicos podem simulados em um computador

•No caso dos jogos, em geral, apenas nos interessam a Mecânica

•A Mecânica de Newton é suficiente •Leis de Newton: •Inércia •F = ma

•Ação e Reação

Engine de Física•Engines de física são softwares que simulam o movimento de objetos de acordo com as leis da física

•Não possuem representação gráfica internamente

•O resultado da simulação pode ser usado para criar a animação procedural de objetos representados graficamente

Engine de Física

Criar e configurar objetos Aplicar forças

Atualizar velocidade e posição

Detectar colisões

Resolver constraints

Exibir resultado

Step

Engine de Física•Após criar os objetos, iniciamos o main loop da simulação

•Em cada iteração fazemos um passo na simulação proporcional ao intervalo de tempo que passou entre a iteração anterior e a atual, conhecido como delta-time ou time-step

•Após cada passo, obtemos as novas posições e velocidades para cada objeto, e assim podemos redesenhar a cena

Simulação de Partículas•Partículas possuem posição, velocidade linear, massa e reagem à forças

•Partículas possuem volume infinitamente próximo de zero

•Partículas não rotacionam •Relativamente simples de simular várias partículas se movimentando e reagindo aos efeitos de forças quaisquer

Simulação de Partículas•Posição, velocidade e força são grandezas vetoriais geralmente de 2 ou 3 dimensões

•Vetores são objetos geométricos que possuem comprimento e apontam numa direção

y

xx1

y1 v = (x1, y1)

O

•Em 3 dimensões:

Simulação de Partículas

y

x

x1

y1v = (x1, y1, z1)

zz1

O

Simulação de Partículas• : posição da i-ésima partícula • : velocidade da i-ésima partícula • : força aplicada na i-ésima partícula • : massa da i-ésima partícula

pi

vi

fimi

•Algoritmo

Simulação de Partículas

for i in [1,n] do

pi = p0i

vi = v0i

end

loop

for i in [1,n] do

fi = ComputeForce(i)

vi = vi + (fi/mi)dt

pi = pi + vidt

end

end

Simulação de Partículas

vipi

t0 t1

fi

t2

Simulação de Corpos Rígidos•Um corpo rígido é uma idealização de um sólido em que suas deformações podem ser ignoradas

•Pode ser simulado de forma semelhante à partícula

•Possui volume, forma fixa, e pode rotacionar •Temos que considerar o momento de inércia, orientação, torque e velocidade angular

Simulação de Corpos Rígidos

Centro de Massa

p

v

!

Simulação de Corpos Rígidos•O Centro de Massa é o ponto médio da distribuição da massa de um corpo !

!

!

•M é a massa total do corpo, r é o vetor posição de um ponto do corpo, V é o volume do corpo, e ρ é a função densidade do corpo, onde ρ(r) = m(r)/v(r)

R =1

M

Z

V⇢(r)rdV

Simulação de Corpos Rígidos•A posição do Centro de Massa é a considerada posição do corpo rígido

•A rotação é um ângulo em radianos em 2D •A velocidade do Centro de Massa é a velocidade do corpo

•A velocidade angular ω é um escalar em 2D (radianos por segundo)

Simulação de Corpos Rígidos•O momento de inércia é o análogo da massa para a rotação

•Determina o quão rápido um corpo ganha ou perde velocidade angular ao receber um torque

•Em 2D o momento de inércia é um escalar com unidade kgm2 que é calculado a partir da massa e da forma do corpo

I =

Z

V⇢(r) r2 dV

Simulação de Corpos Rígidos•Exemplos de momento de inércia:

w

h I =m(h2 + w2)

12

rI =

mr2

2

p0

p1

p2 p3

p4

p5p6

I =m

6

N�1Pn=1

k~Pn+1 ⇥ ~Pnk((~Pn+1 · ~Pn+1) + (~Pn+1 · ~Pn) + (~Pn · ~Pn))

N�1Pn=1

k~Pn+1 ⇥ ~Pnk

•Algoritmo

Simulação de Corpos Rígidos

SetupRigidBodies(n)

loop

for i in [1, n] do

fi = ComputeForce(i)

vi = vi + (fi/mi)dt

pi = pi + vidt

⌧i = ComputeTorque(i)

!i = !i + (⌧i/Ii)dt

↵i = ↵i + !idt

end

end

Constraints•Restrição no movimento de um objeto •Utilizadas para criar juntas e conexões entre corpos e para resolver colisões

•Representada por uma função C e um conjunto de equações e/ou inequações envolvendo C

Constraints•Por exemplo, uma constraint para criar uma junta entre dois corpos rígidos pode ser descrita da seguinte maneira:

C(t) = krA(t)� rB(t)kC(t) = 0

rA(t) = pA(t) +RA(t)rA0

rB(t) = pB(t) +RB(t)rB0

RA(t) =

cos↵A(t) � sin↵A(t)sin↵A(t) cos↵A(t)

�

Constraints

rA0

rB0

pA(t0)

pB(t0)

Constraints•Constraints podem ser satisfeitas aplicando forças ou impulsos em determinados pontos do objeto

Colisões•Colisão entre corpos rígidos é um dos efeitos mais importantes numa simulação

•Permite que os corpos interajam entre si de forma realista

•O processo é dividido em duas partes: detecção e resolução de colisões

Colisões - Detecção•Em geral, o processo de detecção de colisões é dividido em duas partes •Broad Phase: utiliza formas simplificadas das formas originais dos objetos para encontrar potenciais pares que estão colidindo de forma eficiente

•Narrow Phase: verifica se os pares da Broad Phase colidem de fato e calcula os pontos de contato

Colisões - Broad Phase

Colisões - Broad Phase

Axis Aligned Bounding Box

- AABB

Colisões - Broad Phase

Pares que estão potencialmente

colidindo

Colisões - Narrow Phase

d > 0

Colisões - Narrow Phase

Colisões - Narrow Phase•Para detectar se os corpos estão colidindo, calculamos a distância entre eles ou o penetration depth caso estejam penetrando

•Dois algoritmos elegantes para executar essa fase são o GJK (cálculo de distância entre formas convexas) e EPA (Expanding Polytope Algorithm para cálculo de penetration depth)

Colisões - Detecção•Pode ser dividida em dois tipos: •Discreta: identifica em cada passo os pares que colidem. Tem problemas com objetos que se movimentam muito rápido e objetos de pequenas dimensões, onde um objeto pode eventualmente atravessar outro (tunneling)

•Contínua (CCD): calcula o instante em que ocorreu a colisão (time of impact) durante um passo. Evita que objetos atravessem uns aos outros

Colisões - CCD

tittoi

Colisões - Resolução•A resolução de colisões calcula e aplica forças ou impulsos nos pontos de contato para evitar que os corpos penetrem

•Impulse-Based Dynamics é a forma mais popular de se resolver colisões, calculando e aplicando impulsos nos corpos de acordo com algumas propriedades dos materiais como o coeficiente de restituição e o coeficiente de atrito

Colisões - Resolução•Partindo da expressão vrel(ti)=ϵvrel(ti+1), onde ϵ é o coeficiente de restituição, podemos chegar à famosa fórmula do impulso normal !

Colisões - Resting Contacts•Resting Contacts são pontos de contatos que persistem por mais que um passo da simulação

•Precisam de um tratamento especial para manter a estabilidade da simulação, principalmente no empilhamento de objetos (stacking)

•Sequential Impulses é um método popular para resolver os resting contacts e constraints em simulações baseadas em impulsos

Engines•Box2D: engine de física 2D criada por Erin Catto em C++, licença zlib

•Chipmunk: engine de física 2D criada por Scott Lembcke em C, licença MIT

•Bullet Physics: engine de física 3D criada por Erwin Coumans em C++, licença zlib

•PhysX: engine de física 3D proprietário da Nvidia, suporta aceleração por hardware em placas GeForce

Referências•Halliday, Resnick. Fundamentals of Physics, 8th Ed. •Andrew Witkin, David Baraff. Physically Based Modeling: Principles and Practice. http://www.cs.cmu.edu/~baraff/sigcourse/index.html

•Gino van den Bergen.A Fast and Robust GJK Implementation for Collision Detection of Convex Objects. http://www.win.tue.nl/~gino/solid/jgt98convex.pdf