38
Nilson Souto - xissburg - Twitter @xissburg - http://xissburg.com Simulação de Física em Games

Game physics

Embed Size (px)

DESCRIPTION

Physics simulation in games.

Citation preview

Page 1: Game physics

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

Simulação de Física em Games

Page 2: Game physics

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

Page 3: Game physics

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

Page 4: Game physics

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

Page 5: Game physics

Engine de Física

Criar e configurar objetos Aplicar forças

Atualizar velocidade e posição

Detectar colisões

Resolver constraints

Exibir resultado

Step

Page 6: Game physics

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

Page 7: Game physics

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

Page 8: Game physics

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

Page 9: Game physics

•Em 3 dimensões:

Simulação de Partículas

y

x

x1

y1v = (x1, y1, z1)

zz1

O

Page 10: Game physics

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

Page 11: Game physics

•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

Page 12: Game physics

Simulação de Partículas

vipi

t0 t1

fi

t2

Page 13: Game physics

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

Page 14: Game physics

Simulação de Corpos Rígidos

Centro de Massa

p

v

!

Page 15: Game physics

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

Page 16: Game physics

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)

Page 17: Game physics

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

Page 18: Game physics

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

Page 19: Game physics

•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

Page 20: Game physics

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

Page 21: Game physics

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)

Page 22: Game physics

Constraints

rA0

rB0

pA(t0)

pB(t0)

Page 23: Game physics

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

Page 24: Game physics

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

Page 25: Game physics

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

Page 26: Game physics

Colisões - Broad Phase

Page 27: Game physics

Colisões - Broad Phase

Axis Aligned Bounding Box

- AABB

Page 28: Game physics

Colisões - Broad Phase

Pares que estão potencialmente

colidindo

Page 29: Game physics

Colisões - Narrow Phase

d > 0

Page 30: Game physics

Colisões - Narrow Phase

Page 31: Game physics

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)

Page 32: Game physics

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

Page 33: Game physics

Colisões - CCD

tittoi

Page 34: Game physics

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

Page 35: Game physics

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 !

Page 36: Game physics

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

Page 37: Game physics

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

Page 38: Game physics

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