animació basada en f´ısica - mat upc · 12 cap´ıtol 1. conceptes matemàtics 1.4 càlcul del...

Animacio basada en Fısica

Antoni Susın

Index

1 Conceptes Matematics 5

1.1 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Matrius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Aplicacions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.1 Descomposicio LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.1.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Calcul del ’Bounding Box’ d’un conjunt de punts a l’espai . . . . . . . . . . . . . . 12

1.4.1 Matriu de covariancies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.2 Construccio del Bounding Box . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5 Transformacions geometriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5.1 Canvi de sistema de referencia . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5.2 Angles d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6 Quaternions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.1 Observacions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.2 Rotacions i quaternions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.6.3 Matriu de rotacio a partir d’un quaternio . . . . . . . . . . . . . . . . . . . . 17

1.6.4 Quaternio a partir d’una matriu de rotacio . . . . . . . . . . . . . . . . . . 17

1.6.5 Interpolacio esferica entre dues orientacions . . . . . . . . . . . . . . . . . . 18

1.7 Objectes i contactes dins un mon virtual . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7.1 Objectes geometrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7.2 Distancies entre objectes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.8 Objectes en moviment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.8.1 Col·lisisons entre esferes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.8.2 Col·lisisons entre una esfera i un Bounding Box . . . . . . . . . . . . . . . . 26

1.8.3 Col·lisisons entre Bounding Box . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2 Dinamica de partıcules 27

2.1 Trajectoria d’una partıcula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.1.1 Precisio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.1.2 Pas adaptatiu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.1.3 Estabilitat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Index

2.2 Tipus de Forces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.2.1 Forces constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.2.2 Forces centrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.2.3 Viscositat (fregament) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.2.4 Molles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3 Col·lisions amb partıcules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.3.1 Existencia de col·lisio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.3.2 Punt de col·lisio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.3.3 Col·lisio elastica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.3.4 Posicio rebotada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.3.5 Fregament . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4 Restriccions al moviment (I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.4.1 Funcions d’energia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.4.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.5 Restriccions al moviment (II) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

1

Conceptes Matematics

1.1 Vectors

Anomenem vector a una n-triple de numeros reals ~v =

v1

v2

...vn

vector columna. Aixı,

~vT = (v1, v2, . . . , vn).

Operacions:

(i) Suma de vectors: ~v + ~u =

u1 + v1

u2 + v2

...un + vn

-

�*

�

-

~v

~u

~u + ~v ~v

~u

~v − ~u

(ii) Escalat d’un vector: λ~v =

λu1

λu2

...λun

6 Capıtol 1. Conceptes Matematics

*

*

~v

(iii) Norma d’un vector: ‖ ~v ‖2=√

v21 + v2

2 + · · ·+ v2n =

√√√√n∑

i=1

v2i

‖ ~v ‖∞= maxi|vi| (maxim de les components en valor absolut)

‖ v ‖1=n∑

i=1

|vi|

Observacio. El concepte de norma d’un vector va lligat amb el de distancia entre punts,ja que si P i Q son dos punts es defineix λ(P,Q) =‖ −−−−→Q− P ‖

*

P

Q

Punts a distancia constant, per exemple 1, de l’origen:

‖ ‖2:

1

‖ ‖∞:

1.1. Vectors 7

‖ ‖1:

(iv) Producte escalar:

1.1.1 Definicio ~V · ~U = V1 · U1 + V2 · U2 + · · ·+ Vn · Un =n∑

i=1

Vi · Ui

Propietats:

(a) ~V · ~U = ~U · ~V

(b) ~V · ~U =‖ ~V ‖ · ‖ ~U ‖ · cos α

-

µ~u

~v

α

(c) ~V · ~V =‖ ~V ‖2 (α = 0)

Aplicacions geometriques:

– Orientacio de l’espai:

3~v

~u · ~v < 0 ~u · v > 0

– Projeccio sobre una direccio:


- -

36 ~u

~vProj

Perp.

Utilitzant la Trigonometria sabem que:

Valor: ‖ ~V ‖ cos α =~V · ~U

‖ ~V ‖. Direccio:

~V

‖ ~V ‖.

Aixı,

Proj~V (~U) =

(~V · ~U

‖ ~V ‖

)~V

‖ ~V ‖=

(~V · ~U

‖ ~V ‖

2)~V

Perp~V (~U) = ~U − Proj~V (~U)

(iv) Producte vectorial: (dim 3)

~V × ~U =

U2V3 − U3V2

−U1V3 + U3V1

U1V2 − U2V1

=

∣∣∣∣∣∣

x y z

U1 U2 U3

V1 V2 V3

∣∣∣∣∣∣

Propietats

(a) ~V × ~U = −~U × ~V

(b) ‖ ~V × ~U ‖=‖ ~V ‖ · ‖ ~U ‖ sin α

(c) (~V × ~U) · ~W = det(~V , ~U, ~W ) =

∣∣∣∣∣∣

V1 V2 V3

U1 U2 U3

W1 W2 W3

∣∣∣∣∣∣

Aplicacions geometriques:

(I) ~V × ~U es ortogonal a ~U i a ~V . det(~V , ~U, ~V × ~U) > 0 (Regla de la ma dreta)

6

ª

-

~v × ~u

~v

~u

(II) Area del triangle P , Q, R; A =12‖ (Q− P )× (R− P ) ‖

1.2. Matrius 9

R

P Q

A =12‖ (Q− P )× (R− P ) ‖

1.2 Matrius

Anomenarem matriu a una taula de m files i n columnes

A =

a11 a12 . . . a1n

a21 a22 . . . a2n

...am1 am2 . . . am1n

= (aij)

i → filaj → columna

Si n = m =⇒ matriu quadrada.

Operacions:

(i) Suma: A + B = (aij + bij) (han de tenir les mateixes dimensions)

(ii) Escalat: λA = (λaij)

(iii) Trasposada: AT = (aji)

(iv) Traca d’una matriu: traca(A) =n∑

i=1

aii

(v) Producte de matrius: Cm × p

= Am × n

· Bn × p

⇒ cij =n∑

k=1

aik · bkj

Observacio. El producte es pot fer de diferents formes:(

1 23 4

)(5 67 8

)=

(1 · 5 + 2 · 7 1 · 6 + 2 · 83 · 5 + 4 · 7 3 · 6 + 4 · 8

)=

(19 2243 40

)

o be (13

) (5 6

)+

(24

) (7 8

)=

(5 615 18

)+

(14 1628 32

)

~U · ~UT ≡ matriun× n

UT · U ≡ escalar

(vi) Inversa d’una matriu

A ·A−1 = I (matriu identitat); (A−1 ·A = I)

(vii) (A ·B)−1 = B−1 ·A−1.


1.3 Aplicacions

(I) Sistemes d’equacions lineals: Ax = b

3x + 2y − 37 = 54x− 3y + 6z = 1

x− z = 3

=⇒

3 2 −34 −3 61 0 −1

A

x

y

z

x

=

513

b

Solucio: x = 13/10, y = −2 i z = −17/10.

1.3.1 Descomposicio LU

︸︷︷︸︸︷︷︸

A = (aij) =

L U

amb `ij =a(k)ij

a(k)ii

i a(k)ij = a

(k)ij −mika

(k)kj .

Per resoldre el sistema d’equacions Ax = b cal fer

LUx = b =⇒ (1r) Ly = b → y? (sistemes triangulars)(2n) Ux = y → x?

Observacio. Si el sistema es compatible determinat (det(A) 6= 0) podrıem fer Ax ⇐⇒A−1Ax = A−1b. Pero NO ho farem mai, ja que trobar A−1 es quasi el cost de n sistemesd’equacions.

(II) Vectors i valors propis. Direm que λ es un valor propi d’una certa matriu A si i nomessi existeix un vector ~v tal que A~v = λ~v. El vector ~v s’anomena vector propi associat al valorpropi λ.

Calcul dels valors propis.

A~v − λ~v = 0(A− λI)~v = 0 =⇒ det(A− λI) = 0 (Polinomi caracterıstic)

1.3.1.1 Exemple

A =(

1 13 −1

)

det(A− λI) =∣∣∣∣

1− λ 13 −1− λ

∣∣∣∣ = −(1− λ)(1 + λ)− 3 = λ2 − 4 = 0 ⇒ λ = ↗ 2

↘ −2

1.3. Aplicacions 11

λ1 = 2 (A− 2I)~v1 = 0

( −1 13 −3

) (vx

vy

)=

(00

)⇒ −vx + vy = 0

3vx − 3vy = 0

}vx = vy ⇒ ~v1 =

(11

)

λ2 = −2 (A + 2I)~v2 = 0

(3 13 1

) (vx

vy

)=

(00

)⇒ 3vx + vy = 0 ⇒ 3vx = −vy ⇒ ~v2 =

(1

−3

)

1.3.1 Proposicio Si A es una matriu simetrica (aij = aji) amb coeficients reals, llavors elsseus valors propis son valors reals i els vectors propis associats a valors propis diferents sonortogonals.

1.3.2 Exemple Donada A =

2 1 01 1 00 0 −1

, calculeu els seus valors i vectors propis:

(det(A− λI) =

∣∣∣∣∣∣

2− λ 1 01 1− λ 00 0 −1− λ

∣∣∣∣∣∣= · · · = −λ3 + 2λ2 + 2λ− 1 =

= −(λ + 1)(λ2 − 3λ + 1) ⇒ λ1 = −1, λ2 =3 +

√5

2, λ3 =

3−√52

λ1 = −1 (A + (−1)I)~v1 = 0

3 1 01 2 00 0 0

vx

vy

vz

=

000

⇒

3vx + vy = 0vx + 2vy = 0

0 = 0

⇒ xy = vu = 0

vz lliure

⇒ ~v1 =

001

λ2 =3 +

√5

2(A− λ2I)~v2 = 0

2− 3 +√

52

1 0

1 1− 3 +√

52

0

0 0 −1

vx

vy

vz

=

000

⇒

1−√52

vx + vy = 0

vx − 1 +√

52

vy = 0

−vz = 0

⇒ ~v2 =

1 +√

5210

. Analogament ~v3 =

1−√5210

.

Observacio: Son ortogonals.


1.4 Calcul del ’Bounding Box’ d’un conjunt de punts a l’espai

Donat un conjunt de N punts P1, P2, . . . , PN a l’espai, considerem cada punt Pi = (xi, yi, zi)de 3 coordenades.

Ens interessa calcular la caixa prismatica que els inclou; per a aixo primer calcularem la posiciocentral (centre de gravetat)

m =1N

N∑

i=1

Pi ,

mx =1N

N∑

i=1

xi

my =1N

N∑

i=1

yi

mz =1N

N∑

i=1

zi

(i) Bounding Box alineat amb els eixos de coordenades.

Si denotem per Pi = Pi − m les coordenades respecte la posicio central (xi, yi, zi) =(xi −mx, yi −my, zi −mz); llavors

m

2Bx2By

2Bz

(ii) Bounding Box orientat.

1.4. Calcul del ’Bounding Box’ d’un conjunt de punts a l’espai 13

�

Per orientar la caixa respecte la distribucio a l’espai dels punts considerats ens cal fer elque s’anomena Analisi de les components principals. La idea es determinar la direccioprimaria, que es aquella on hi ha mes variacio de les coordenades dels punts.

1.4.1 Matriu de covariancies

Es tracta d’una matriu simetrica que es defineix a partir de C =1N

N∑

i=1

Pi · PTi︸︷︷︸

3×3

, es una eina

fonamental a l’hora de construir bounding box orientats.

Explıcitament:

C =1N

N∑

i=1

x2i

N∑

i=1

xiyi

N∑

i=1

xizi

N∑

i=1

y2i

N∑

i=1

yizi

N∑

i=1

z2i

Les direccions principals coincideixen amb els vectors propis de la matriu de covariancies. Ladireccio primaria es la associada al valor propi de modul mes gran.

1.4.1 Exemple Donats els punts P1 = (−1,−2, 1), P2 = (1, 0, 2), P3 = (2,−1, 3), P4 =(2,−1, 2), calculeu el seu Bounding Box orientat.

Posicio central:

m =14

∑Pi = (1,−1, 2) ⇒ P1 = (−2,−1,−1), P2 = (0, 1, 0), P3 = (1, 0, 1), P4 = (1, 0, 0) .

Si calculessim el Bounding Box alineat amb els eixos: Bx = 2, By = 1, Bz = 1

C =14

6 2 32 2 13 1 2

=

3/2 1/2 3/41/2 1/2 1/43/4 1/4 1/2


Valors propis:

det(C − λI) =

∣∣∣∣∣∣

3/2− λ 1/2 3/41/2 1/2− λ 1/43/4 1/4 1/2− λ

∣∣∣∣∣∣= −λ3 +

52λ2 − 7

8λ +

116⇒

λ1 = 2.097λ2 = 0.3055λ3 = 0.09756

Observacio. Per calcular aquests valors es pot fer numericament o be per formules.

Vectors propis: Denotarem per U1, U2, U3 els vectors propis normalitzats associats a λ1, λ2 iλ3, respectivament (ordenats |λ1| ≥ |λ2| ≥ |λ3|.) Aleshores:

U1 =

−0.833−0.330−0.443

, U2 =

−0.257

0.941−0.218

i U3 =

0.489−0, 0675

0.870

.

1.4.2 Construccio del Bounding Box

En primer lloc calcularem els plans que determinen el Bounding Box. Per a aixo, per a cadadireccio denotem per

Ux1 x + Uy

1 y + Uz1 − Umin

1 = 0Ux

1 x + Uy1 y + Uz

1 − Umax1 = 0

onUmin

1 = mini=1...N

{(Pi · U1)}Umax

1 = maxi=1...N

{(Pi · U1)}

Analogament per a U2 i U3.

1.4.2 Exemple

<> U1 U2 U3

P1 1.05 −1.84 −1.25P2 −1.72 −0.693 −1.25P3 −2.67 −2.11 −1.56P4 −2.22 −1.89 −0.695

Ortogonal a U1:−0.833x− 0.330y − 0.443z + 2.67 = 0−0.833x− 0.330y − 0.443z − 1.05 = 0

Analogament per a U2 i U3.

Els plans que tallen el Bounding Box pel mig seran:

Q

2a2b

2c

1.5. Transformacions geometriques 15

(U1,−a)

x

y

z

t

on

a = 12 (Umin

1 + Umax1 )

b = 12 (Umin

2 + Umax2 )

c = 12 (Umin

3 + Umax3 )

centre: Q = aU1 + bU2 + cU3 .

1.5 Transformacions geometriques

Les transformacions geometriques que considerarem son essencialment tres, Escalat, Rotacioi Translacio.

En els dos primers casos, es pot expressar la transformacio com el producte per una matriu:~V ′ = M ~V

Escalat. D = diag (d1, d2, d3) ≡

d1

d2

d2

.

Rotacio. R ortogonal, es a dir, RRT = RT R = I.

Donat un eix de rotacio ~V = (Vx, Vy, Vz) i un angle θ, si denotem per S la matriu antisimetrica(ST = −S):

S =

0 −vz vy

vz 0 vx

−vy vx 0

, llavors:

R~V (θ) = I+sin(θ)S+(1−cos θ)S2 =

c + v2x(1− c) vxvy(1− c)− vzS vxvz(1− c) + vyS

vxvy(1− c) + vzS c + v2y(1− c) vyvz(1− c)− vxS

vxvz(1− c)− vyS vyvz(1− c) + vxS c + v2z(1− c)

.

Translacio. Donat un vector ~T , llavors ~X ′ = ~X + ~T .

1.5.1 Canvi de sistema de referencia

Donat un sistema de referencia ortonormal (O,~e1, ~e2, ~e3) passar a un nou sistema (O, ~u1, ~u2, ~u3)ortonormal es equivalent a aplicar una translacio i una rotacio: xo = Rxo + T , on R =(

u1 u2 u3

↓ ↓ ↓)

i T son les coordenades del nou origen o o be xo = RT (xo − T ).


Per expressar aquest canvi se sol utilitzar les coordenades homogenies

M =

R T

0T 1

=⇒ Xo = MXo

M−1 =

RT −RT T

0T 1

=⇒ Xo = M−1Xo

1.5.2 Angles d’Euler

Donada una certa rotacio a R3, la podem expressar com a composicio de 3 rotacions respecte als

eixos de coordenades: R(θ) = Rx(θ1)Ry(θ2)Rz(θ3), on Rx(θ1) =

1 0 00 cos θ1 − sin θ1

0 − sin θ1 cos θ1

,

Ry(θ2) =

cos θ2 0 − sin θ2

0 1 0sin θ2 0 cos θ2

, Rz(θ3) =

cos θ3 sin θ3 0− sin θ3 cos θ3 0

0 0 1

, de manera que

R(θ) =

c2c3 c2c3 −s2

s1s2c3 − c1s3 s1s2s3 + c1c3 s1c2

c1s2c3 + s1s3 c1s2s3 − ss1c3 c1c2

ci = cos(θi), si = sin)θi.

Tot i que son molt utilitzats en contexts de fısica i d’animacio, els angles d’Euler tenen dosdefectes principals. El primer es la dificultat en la propia descomposisio de la matriu de rotaciocom a producte dels angles d’Euler. En segon lloc esta la dificultat d’utilitzar-los per interpolarles orientacions entre dues posicions donades.

1.6 Quaternions

Una forma diferent d’expressar l’orientacio d’un cos es utilitzar el que s’anomenen quaternions.Aquests van ser introduıts per Hamilton el 1843 i es tracta d’una entitat quatre dimensionalq = s + vxi + vyj + vzk ≡ (s,~v), on i2 = j2 = k2 = −1 (unitats imaginaries); s = escalar, ~v =vector; uj = k, o be si ho escrivim al reves (es a dir (~v, s)): ji = −k.

1.6.1 Observacions

Suma: q1 + q2 = (s1 ± s2, ~v1 + ~v2) (suma per components).

Producte escalar: λq1 = (λs1, λ~v1).

1.6. Quaternions 17

Producte: q1 · q2 = (s1 · s2 − ~v1 · ~v2, s1~v2 + s2~v1 + ~v1 × ~v2).

Conjugat: q = (s,−~v). Aleshores q · q = s2+ ‖ v ‖2=‖ q ‖2.

Invers: q−1 =q

‖ q ‖2 .

Direm que q es unitari si, i nomes si, ‖ q ‖= 1.

1.6.2 Rotacions i quaternions

La rotacio d’angle θ i eix u = (ux, uy, uz) (unitari) es correspon al quaternio q = (cos(θ/2), sin(θ/2)u).

Aplicar una rotacio a un punt es el mateix que fer Ru(θ)p = qpq, on q es unitari i p ≡ (0, p)per fer els productes.

1.6.3 Matriu de rotacio a partir d’un quaternio

Si Q = (s,~v) amb ‖ q ‖= 1:

R =

1− 2v2y − 2v2

z 2vxvy − 2svz 2vxvz + 2svy

2vxvy + 2svz 1− 2v2x − 2v2

z 2vyvz − 2svx

2vxvz − 2svy 2vyvz + 2svx 1− 2v2x − 2v2

y

.

1.6.4 Quaternio a partir d’una matriu de rotacio

s =√

traca R + 12

si s 6= 0 vx =R32 −R23

4 · s , vy =R13 −R31

4 · s , vz =R21 −R12

4 · s .


1.6.5 Interpolacio esferica entre dues orientacions

Suposem que tenim una posicio inicial i una final corresponents als quaternions q1 i q2. Llavors

q(t) =(1− t)q1 + tq2

‖ tq1 + tq2 ‖

-

�

R

q1

q2

q(t)

1.6.1 Exemple Suposem que volem passar de la posicio inicial INI a la final FINAL:

6

3

s

-

6

3

s

Ry

x

z

y

x

z

Angles d’Euler:

(i) (ii)

6

3

s

6

3

s

6

3

s

π

π

π

x

z

x

z

x

z

Farıem una interpolacio:

(i) θ1(t) = tπ, 0 ≤ t ≤ 1; θ2 i θ3 fixats.

(ii) θ2(t) = tπ, θ3(t) = tπ, 0 ≤ t ≤ 1; θ1 fixat.

Observacio: Per a t = 1/2 :

1.7. Objectes i contactes dins un mon virtual 19

6

3

s

R

Quaternions:

(i) gir π en x: (cos(π/2), sin(π/2)(1, 0, 0)) = (0, (1, 0, 0)).

(ii) gir π en y: (0, (0, 1, 0)).

gir π en z: (0, (0, 0, 1)).

La composicio: q = (0, (0, 1, 0))(0, (0, 0, 1)) = (0, (0, 1, 1)×(0, 0, 1)) = (0, (1, 0, 0)); quedaria unaunica solucio.

Observacio: En els angles no podem fer aquesta composicio intermedia.

1.7 Objectes i contactes dins un mon virtual

1.7.1 Objectes geometrics

Punt: P0 = (x0, y0, z0).

Recta per dos punts: r(λ) = (1−λ)P1 +λP2, o el que es el mateix: r(λ) = P1 +λ(P2−P1) = P1 + λ~v.

Observacio. Si considerem nomes el segment entre els dos punts, aleshores exigiremλ ∈ [0, 1].

Pla en R3:

– Donats 3 punts: π(λ, µ) = P1 + λ(P2 − P1) + µ(P3 − P1), λ, µ ∈ R.

– Vector normal i punt: N ·(P −P1) = 0 ⇔ nx ·x+ny ·y+nz ·z+d = 0, amb d = −N ·P1.

⇔ π :< ~N, d >, (notacio.)

Observacio. N = (P2 − P1)× (P3 − P1).

Triangle en R3: es la mateixa equacio del pla que passa pels 3 vertex pero exigiremλ, µ ∈ [0, 1], λ + µ ≤ 1.


Esfera de centre C i radi R:

(P − C)T (P − C)−R2 = 0 =⇒ (x− cx)2 + (y − cy)2 + (z − cz)2 −R2 = 0

Prismes (Bounding Box): Centre C i direccions unitaries dels eixos U1, U2, U3, a1, a2, a3

semi-distancies

Obs: En ser un sistema de referencia local, el BB es −a1 ≤ x ≤ +a1, −a2 ≤ y ≤ +a2,−a3 ≤ z ≤ +a3.

altres objectes: Es podrien introduır tambe Cilindres, Cons, etc.

1.7.2 Distancies entre objectes

Dos punts:

d(P1, P2) =√

(P2 − P1)T (P2 − P1) =√

(P2x − P1x)2 + (P2y − P1y)2 + (P2z − P1z)2

Punt i recta:

¸

*

Q

Q′

~v

P

r

λ′ =~v(Q− P )

~vT · ~v ⇒ Q′ = P + λ′ · ~vd(Q, r) = d(Q,Q′)


Observacio. Si es tracta d’un punt i un segment

P2

P1

r

aleshores. si

λ′ < 0 ⇒ d(Q, r) = d(Q,P1)

0 < λ′ < 1 ⇒ d(Q, r) = d(Q,Q′)

λ′ > 1 ⇒ d(Q, r) = d(Q,P2)

Punt i pla:

6

...

...

...

...

...

...

...

> 0

< 0

d(P, π) =|P · ~N + d|

~N · ~N

Observacio. P ·N + d > 0 ⇒ esta per sobre.

Punt i Bounding Box:

Y

BB: C ± (a1U1 + a2U2 + a3U3)

Conegut el centre BB i C, els vectors normals U1, U2, U3 i a1, a2, a3 els valors dels costats.Si diem Ui · −−−−→P − C = di, |di| > ai, per a algun di exterior.

Punt i esfera:

d(P, C) > r ⇒ exterior

d(P, C) < r ⇒ interior

d(P, C) = r ⇒ sobre l’esfera


Dues rectes:

r

s

r(λ) = P1 + λ · ~V1

s(µ) = P2 + µ · ~V2

d2(r, s) = |r(λ)− s(µ)|2 = |(P1 + λ~V1)− (P2 + µ~V2)|2d2(r, s) = Aλ2 + 2Bλµ + Cµ2 + 2Dλ + 2Eµ + F

amb A = ~V1 · ~V1, B = −~V1 · ~V2, C = ~V2 · ~V2, D = ~V1(P1 − P2), E = −~V2(P1 − P2) iF = (P1 − P2) · (P1 − P2).

Per buscar el mınim podem derivar i igualar a zero:

λ =BE − CD

AC −B2i µ =

BD −AE

AC −B2

Observacio. Si AC −B2 = 0, les rectes son paral.leles ⇒ distancia punt–recta.

Recta i pla: La recta r(λ) = P + λ~V i el pla π :< ~N, d >. Imposem que un punt dela recta satisfaci l’equacio del pla:

~N · (P + λ~V ) + d = 0 ⇒ λ =−( ~N · P + d)

~N · ~V

Observacio. Si ~N · ~V = 0 son paral.leles ⇒ distancia punt–pla.

Recta i triangle: r(λ) = Q + λ~V ; T : P1, P2, P3

~N = (P2 − P1)× (P3 − P1) ⇒ pla: < ~N,−N · P1 >

P0P1

P2

P3

Calculem el punt d’interseccio amb el pla del triangle P0, per aixo calculem λ0 =−( ~N ·Q−N · P1)

~N · ~V;

aleshores P0 = Q + λ0 · ~V .


I~N

Projectem sobre 2-D eliminant la component que es correspon amb el maxim en valorabsolut de les coordenades de ~N i es mira el signe per a cada aresta: per a cada punt Pi

NE

Pi

?

Pi+1¾

/Pi+2

~E = Pi+1 − Pi

~F = Pi+2 − Pi

G = P0 − Pi

~NE = (−Ey, Ex)

Llavors, si ( ~NE · ~F ) · ( ~NE ·G) ≥ 0, ∀ i ⇒ es interior.

Recta i Bounding Box:

Recta i esfera: r(λ) = P + λ · ~V .

– Esfera: centre C i radi R.

S : (P − C)T (P − C)−R2 = 0


d(r, s) = αλ2 + βλ + γ , ambα = V 2

x + V 2y + V 2

z

β = 2 · (~V (P − C))γ =‖ ~V ‖2 + ‖ P ‖2 −2 · (P · ~V + R2)

r

S

Si β2 − αγ < 0 ⇒ no interseccio

λ =−β ±

√β2 − αγ

2α, λmin es el mes proper.

Observacio. El cas de distancia d’una esfera o d’un Bounding Box a un pla, pot reduir-sea la distancia del seu respectiu centre al pla. En el cas d’un Bounding Box utilitzarem

rq =12(|v1

~N |+ |~v2~N |+ |~v3N |) com a radi efectiu

~NIrf

1.8 Objectes en moviment

Considerem ara que els objectes estan en moviment. En aquest cas considerarem Esferes iBounding box i la seva interseccio.

Observacio. El cas partıcula en moviment es el mateix a la interseccio amb la recta P (t) =P0 + λ~V , on ~V es el vector velocitat.

1.8.1 Col·lisisons entre esferes

Suposem que tenim dues esferes de centres C1 i C2 i radis r1 i r2 respectivament i que esdesplacen amb velocitats ~V1 i ~V2 respectivament. Aixo vol dir que durant un temps t ∈ [0, 1]

1.8. Objectes en moviment 25

tindrem

C1(t) = C1 + t~V1 C2(t) = C2 + t~V2

a algun 0 < t < 1 les dues esferes son tangents, que voldra dir que en algun instant la distanciaentre els dos centres d es igual a r1 + r2

d2(t) =‖ C1(t)−C2(t) ‖2=‖ C1 −C2 + t(~V1 − ~V2) ‖2=‖ A + t ·B ‖2= |A|2 + 2t(A ·B) + t2|B|2

(prenent C2 com origen, A = C1 − C2 moviment relatiu i B~V1 − ~V2 velocitat relativa), que tesolucio

t1 =−(A ·B)−

√(A ·B)2 − |B|2(|A|2 − d2)

|B|2 t2 =−(A ·B) +

√(A ·B)2 − |B|2(|A|2 − d2)

|B|2

Imposant d = r1 + r2:

Si el radicand es negatiu, =⇒ no interseccio.

Si el radicand es positiu, es calcula t1 i, si es menor que 1, =⇒ tindrem contacte per aaquest valor.

Q = C1 + t1~V on ~V =C2 − C1

‖ C2 − C1 ‖


1.8.2 Col·lisisons entre una esfera i un Bounding Box

En primer lloc es pot descartar la col·lisio si considerem l’esfera que “enrotlla” al BoundingBox. Si diem b al centre del Bounding Box i U1, U2 U3, a1, a2 i a3 els seus eixos i midesrespectivament, aleshores rb = (a1U1 + a2U2 + a3U3) es el radi d’aquesta esfera.

Un primer test de no-col·lisio el farıem a partir d’aquestes dues esferes. En cas que aquestacol·lisio fos possible, passarıem a expressar-ho com un problema de distancies entre el centre del’esfera i el Bounding Box, pero ampliant aquesta distancia al radi r

d(C, BB)− r = 0 .

1.8.3 Col·lisisons entre Bounding Box

C1(t) = C1 + t · ~V1

C2(t) = C2 + t · ~V2 t ∈ [0, tmax]

Observacio. Sempre podem fer un primer descartament a partir de dues esferes de radis r1 ir2.

En el cas de trobar contacte entre elles caldra passar a estudiar el problema directament:

Prendrem un sistema de referencia centrat en un dels Bounding Box i les velocitats relatives:

BB1: −ai ≤∣∣∣∣∣∣

x

y

z

∣∣∣∣∣∣≤ ai

BB2 : C12 =

U1 → −U1 · C1

U2 → −U2 · C1

U3 → −U3 · C1

0 1

︸︷︷︸Q

(C2

1

)(analogament: b′i =

∏(bi

0

))

i la velocitat, ~V ′2 = ~V2 − ~V1.

2

Dinamica de partıcules

Anem a considerar el moviment d’una partıcula puntual. Des d’el punt de vista geometric lespartıcules seran punts 3D que estaran animades segons unes certes “caracterıstiques fısiques”.En principi podem fer la seguent classificacio:

1) El moviment es independent de la resta de partıcules: ⇒partıcules.

2) El moviment depen de les partıcules veınes:

a) Les distancies mutues poden variar: ⇒deformables.

b) Les distancies mutues NO poden variar: ⇒solids rıgids.

Una partıcula ve caracteritzada per la seva massa m, posicio x(t) i velocitat v(t).

2.0.1 Definicio Anomenarem vector d’estat d’una partıcula als valors X = (x, v). L’animacioconsisteix en passar del vector d’estat corresponent a un cert temps al vector d’estat del tempsseguent: t + ∆t

Xt −→ Xt+∆t

Per fer aquest calcul tenim la segona llei de Newton o llei de la dinamica que estableix:∑

Fi = m · a,

on a(t) es l’acceleracio. De fet,

a(t) = v(t) = x(t) =⇒∑

Fi = m · x (eq. dif. de 2n ordre).

Com veurem l’unic que ens cal per actualitzar el vector d’estats d’una partıcula es l’acceleracio,o de fet, la forca que actua sobre ella. L’actualitzacio de la posicio depen de la velocitat il’actualitzacio de la velocitat depen de la forca

mx = F︸︷︷︸eq. dif. 2n ordre

=⇒

x = v

v = a =F

m︸︷︷︸sist. d’eq. dif. 1r ordre

on F =∑

Fi es la forca total.

28 Capıtol 2. Dinamica de partıcules

Observacio. En el cas que la forca sigui constant =⇒ acceleracio constant. Llavors existeixenformules explıcites d’actualitzacio:

xn+1 = xn + ∆t · vn +12an(∆t)2 (mov. uniformement accel.)

vn+1 = vn + ∆t · an

2.1 Trajectoria d’una partıcula

Calcular la posicio d’una partıcula al llarg del temps es calcular el que anomenem “trajectoria”d’una partıcula

xn

vn

Fn

m

−→∆t

Solver −→xn+1

vn+1

Fn+1

m

Els diferents “Solvers” (metodes d’integracio numerica d’edos) no son res mes que diferentsmaneres d’avancar en la trajectoria. Ara estudiarem els mes importants d’acord a dues carac-terıstiques principals: Precisio i estabilitat.

2.1.1 Precisio

L’error comes, en funcio del pas h = ∆t, entre el valor aproximat xn+1 i el valor verdader xn+1.Si

error ∼= |xn+1 − xn+1| = k · hp direm que el metode es d’ordre p

Metode d’Euler (p = 1)

Aquest es el metode mes senzill, es tracta d’aproximar la trajectoria de la partıcula pel vectorsobre la tangent (la derivada)

Xn+1 = Xn + hXn com Xn =

(vn

Fn

m

)

2.1. Trajectoria d’una partıcula 29

que podem escriure com (xn+1

vn+1

)=

(xn

vn

)+ h

(vn

Fn

m

)

Implementacio. En general, a l’hora d’implementar el metode d’Euler es mes estable seguirl’ordre de calcul (semi-implicit):

vn+1 = vn + hFn

m,

xn+1 = xn + hvn+1.

Observacio. Notem que si h es “petit” l’error es mes petit. El problema es que no es pot fer“massa” petit ja que els errors numerics d’arrodoniment podrein creixer.

Metode d’Euler modificat. Punt mig (p = 2)

Xn+1 = Xn + hXn+1/2

tn + tn+1

2= tn +

12

xn + xn+1

2=

xn + (xn + h · f(tn, xn))2

= xn +h

2f(tn, xn)

aleshores

Xn+1 = Xn + h · f(

tn +h

2, xn +

h

2f(tn, xn)

).

Aixı, si tenim la funcio de forces F (t, x, v), aleshores el metode del punt mig es:

xmig = xn +h

2vn

vmig = vn +h

2F (xn, vn)

m

Llavors:xn+1 = xn + h · vmig

vn+1 = vn + h · F (xmig, vmig)m


Metode de Runge-Kutta 2 (p = 2)

Fem un promig entre el punt inicial i el punt final. Considerem dos punts amb que farempromig:

x1 = xn x2 = xn+1 = xn + hvn

iv1 = vn v2 = vn+1 = vn + hF (xn, vn)

Aleshores actualitzem l’estat actual a partir de l’expressio Xn+1 = Xn + h

(X1 + X2

2

), es a

dir:

xn+1 = xn + h

(v1 + v2

2

)= xn +

h

2(vn + vn + hF (xn, vn))

vn+1 = vn + h

(F1 + F2

2

)= vn +

h

2

(F (x1, v1)

m+

F (x2, v2)m

)

Metode de Runge-Kutta 4 (p = 4)

Xn+1 = Xn +h

6(k1 + 2k2 + 2k3 + k4)

2.1. Trajectoria d’una partıcula 31

on

k1 = f(xn, xn)

k2 = f

(tn +

h

2, yn +

h

2k1

)

k3 = f

(tn +

h

2, yn +

h

2k2

)

k4 = f (tn + h, yn + hk3)

Nota.

2.1.2 Pas adaptatiu

Triar el pas d’integracio es sempre un proces delicat, al fer-ho sempre s’ha de fixar un errormaxim que el vol cometre: emax. La mesura de l’error comes es pot aproximar fent dos calculs,

per exemple per pas ∆t i∆t

2i comparant

ea = |X∆t −X∆t2| .

En funcio de l’ordre del metode tindrem

en+1 = hp+1 · en =⇒ hactual =(

emax

ea

)p+1

hnou ;

aixı, si per exemple volem fer un calcul amb emax = 10−4 i calcular ea = 10−8 per Euler:

hnou =(

emax

ea

)1/2

hactual =(

10−4

10−8

)1/2

hactual = (104)1/2h = 100 · h .

Si el resultat fors el contrari: emax = 10−4 i ea = 10−2, llavors:

hnou =(

10−4

10−2

)1/2

hactual = (10−2)1/2hactual = 0.01 · hactual .

2.1.3 Estabilitat

Metodes implıcits (Euler)

Xn+1 = Xn + hFn+1 .

Es tracta d’utilitzar la informacio en el punt d’arribada per donar la direccio de sortida

{xn+1 = xn + h · vn+1

vn+1 = vn +h

m· F (xn+1, vn+1)

(2.1)


Aquesta segona equacio es una equacio en que nomes hi ha una incognita, que es vn+1. Enprincipi es tracta de calcular-ho a partir d’un metode de zeros de funcions o resolucio d’unsistema, etc...

Considerem∆x = x− n + 1− xn = h · vn+1

∆v = vn+1 − vn⇒ hvn+1 = vn + ∆v

llavors

F (xn+1, vn+1) = F (xn + ∆x, vn + ∆v) Taylor= F (xn, vn) +∂F

∂x(xn, vn)∆x +

∂F

∂v(xn, vn)∆v =

= Fn +∂F

∂x(h(vn + ∆v)) +

∂F

∂v∆v = fn + hvn

∂Fn

∂x+ ∆v

(h

∂Fn

∂x+

∂Fn

∂v

)

Aleshores el sistema (2.1) s’escriu:

∆X = h(vn + ∆v)

∆v =h

m

(Fn + hvn

∂F

∂v+ ∆v

(h

∂Fn

∂x+

∂Fn

∂v

))

La segona equacio dona:(

I − h2

m

∂F

∂x− h

m

∂F

∂v

)∆v =

h

mFn +

h2

mvn

∂F

∂x

Genericament a l’esquema tindrem una matriu i per tant el calcul de ∆v es la resolucio d’unsistema d’equacions lineals.

2.2 Tipus de Forces

2.2.1 Forces constants

(Gravetat, vent direccional, etc.)

F (x,v, t) =

w1

w2

w3

wi constants, per exemple

0−9.8

0

2.2. Tipus de Forces 33

2.2.2 Forces centrals

Atraccio d’un planeta

F (x,v, t) = −G · m

|O − x|2︸︷︷︸magnitud

· O − x|O − x|3︸︷︷︸

direccio

= −Gm · O − x|O − x|3

on O es el centre d’atraccio, m la massa total, x la posicio actual de la partıcula i G es unaconstant (6.67259 · 10−11Nm2/Kg2).

Atraccio entre dues masses

F (x,v, t) = −G · m1m2

|x2 − x1|2 ·x2 − x1

|x2 − x1|

Observacio. Atraccio electromagnetica es equivalent a la gravitatoria pero amb masses (carregues)positives i negatives.

2.2.3 Viscositat (fregament)

Es una forca proporcional i oposada a la velocitat:

F (x,v, t) = −kf · v, en tota l’escena, o be:

F (x,v, t) = −kf (−FN )vt sobre una superficie.

2.2.4 Molles

Si considerem dues partıcules p1, p2 que tenen posicio xi = (xi, yi, zi), i = 1, 2 i velocitatvi = (ui, vi, wi), i = 1, 2 respectivament, podem simular que estan unides per una molla apartir de les forces:


F (x,v, t) = −Ks(|x2 − x1| − `12)︸︷︷︸magnitud

x2 − x1

|x2 − x1| , on Ks constant d’elasticitat de la molla, `12

longitud inicial (es tendeix a recuperar).

O be esmorteıda:

F (x,v, t) = −[Ks(|x2 − x1| − `12) + Kd

(v2 − v1)(x2 − x1)|x2 − x1|

]x2 − x1

|x2 − x1|.

2.3 Col·lisions amb partıcules

2.3.1 Existencia de col·lisioSi el pla π : ( ~N, d) ⇒ ~N · x + d = 0, tindrem col·lisio si

( ~N · xn + d)( ~N · xn+1 + d) ≤ 0 (hi ha canvi de signe)

2.3.2 Punt de col·lisio

Recta que passa per xn i xn+1 i talla al pla π: tc =( ~N · xn + d)~N(xn+1 − xn)

aleshores el punt de tall sera

xc = xn + tcvn

2.4. Restriccions al moviment (I) 35

2.3.3 Col·lisio elastica

Descomposicio de la velocitat: (normal + tangencial): ~v = vN + vT , on vN = (v · ~N) ~N ivT = v − vN

2.3.4 Posicio rebotada

w = x′i+1 − xc; w = wN + wT , wN = ( ~N · w) ~N , wT = w − wN . Llavors

xi+1 = xc + (−wN + wT )

o, equivalentment:xi+1 = x′i+1 − 2[x′i+1 · ~N + d] ~N

Per a la velocitat:vi+1 = v′i+1 − 2(v′i+1 · ~N) ~N

En general, si introduım un factor d’elasticitat ε, on 0 ≤ ε ≤ 1

xi+1 = x′i+1 − (1 + ε)[x′i+1 · ~N + d] ~N

vi+1 = v′i+1 − (1 + ε)[v′i+1 · ~N ] ~N

2.3.5 Fregament

Podem introduir un factor de fregament, que en aquest cas nomes afectara a la velocitat tan-gencial.

Si v′i+1 = v′i+1,N + v′i+1,T , aleshores vi+1 = εv′i+1,N + (1− µ)v′i+1,T .

2.4 Restriccions al moviment (I)

Podem imposar certes restriccions C(x) = 0 al moviment d’una forma no estricta, de maneraque el que farem sera introduir unes forces que tendeixen a mantenir unes certes restriccions,pero que “competeixen” amb la resta de forces.


2.4.1 Funcions d’energia

Suposem que volem imposar una certa condicio, per exemple:

dues partıcules coincideixen: C(p1, p2) = p1 − p2 (3 cond.)

a distancia constant C(p1, p2) = ||p1 − p2|| − d (1 cond.)

La idea es considerar l’energia potencial

E =ks

2C(x) · C(x)

, ks coeficient d’elasticitat i la forca derivada del potencial:

fi =−∂E

∂xi= −ks · C(x)

∂C(x)∂xi

.

Aquesta forca fi es com una generalitzacio de una forca tipus molla que porta al sistema asatisfer C(x) = 0.

Per evitar un comportament oscil·latori al voltant de la restriccio podem afegir un terme d’es-morteıment:

fi = (−ksC(x)− kdC(x))∂C(x)∂xi

on kd es el coeficient d’esmorteıment i C(x) =dC(x)

dt.

2.4.2 Exemples

C(x1, x2) = x1 − x2 ⇒ C =dC

dt

∂C

∂x1=

∂

∂x1

Cx

Cy

Cz

=

Cx=x1x−x2xCy=x1y−x2yCz=x1z−x2z

∂Cx

∂x1x

∂Cx

∂x1y

∂Cx

∂x1z∂Cy

∂x1x

∂Cy

∂x1y

∂Cy

∂x1z∂Cz

∂x1x

∂Cz

∂x1y

∂Cz

∂x1z

=

1 0 00 1 00 0 1

= 0

Analogament,∂C

∂x1= −I.

Aixı, la forca en aquest cas es:

f1 = (−ks(x1 − x2)− kd(v1 − v2))Id

f2 = (−ks(x1 − x2)− kd(v1 − v2))(−Id)

A l’altre exemple:C(x1, x2) = |x1 − x2| − d (1-dim)

2.5. Restriccions al moviment (II) 37

tindrem

C =d

dt(|x1 − x2|) =

d

dt([(x− 1− x2)(x1 − x2)]−1/2)

=12(|x1 − x2|T |x1 − x2|)−1/22(x1 − x2)(v1 − v2)

=(x1 − x2)(v1 − v2)

|x1 − x2|i

∂C

∂x1=

∂

∂x1(|x1 − x2|) =

12(|x1 − x2|T |x1 − x2|)−1/22(x1 − x2) =

x1 − x2

|x1 − x2|∂C

∂x2=

∂

∂x1(|x1 − x2|) =

12(|x1 − x2|T |x1 − x2|)−1/22(x1 − x2) = − (x1 − x2)

|x1 − x2|aleshores la forca

f1 =[−ks(|x1 − x2| − d)− kd

(x1 − x2)(v2 − v2)|x1 − x2|

]x1 − x2

|x1 − x2|f2 = −f1

2.5 Restriccions al moviment (II)

Suposem que volem moure una partıcula sobre una superfıcie o be una corba: C(x) = 0.

Es tracta de calcular les forces que mantenen aquesta condicio al llarg del temps.

Notem que

C(x) = 0 ⇒ posicio valida

C(x) = 0 ⇒ velocitat valida

C(x) = 0 ⇒ acceleracio valida

Suposem que coneixem la posicio d’una partıcula x(t) i les forces que actuen sobre ella

x =1m

F (x, v, t)

si inicialment la posicio i velocitat son valides, tenim C(x) = C(x) = 0. El nostre problema escalcular la forca que fa la restriccio F que afegida a la forca total que esta actuant, F , garanteixC = 0 aixı, de fet aplicarem

x =1m

(F + F ) .

Veiem quines condicions ha de satisfer F :

C(x) =dC(x)

dt=

∂C(x)∂x

∂x

∂t=

∂C(x)∂x

x ≡ Jx


tornant a derivar:C(x) = J x + Jx = J x + JM−1(F + F )

imposant C = 0 quedaJM−1F = −J x− JM−1F .

La forca F s’ha de triar dins les direccions que ha de contrarestar, en particular les donades pelgradient a les restriccions:

F = JT λ on λ es un vector d’escalars (incognites)

AixıJM−1JT λ = −J x− JM−1F

que es un sistema d’equacions lineals. Per efectes d’estabilitat numerica es solen afegir dostermes “correctors”, C = −ksC − kdC, on ks es una constant d’elasticitat i kd de viscositat

JM−1JT λ = −J x− JM−1F − ksC − kdC .

animació basada en f´ısica - mat upc · 12 cap´ıtol 1. conceptes matemàtics 1.4 càlcul del...

Documents