Upload
others
View
7
Download
0
Embed Size (px)
Citation preview
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:
8 Capıtol 1. Conceptes Matematics
- -
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.
10 Capıtol 1. Conceptes Matematics
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.
12 Capıtol 1. Conceptes Matematics
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
14 Capıtol 1. Conceptes Matematics
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 ).
16 Capıtol 1. Conceptes Matematics
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 .
18 Capıtol 1. Conceptes Matematics
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.
20 Capıtol 1. Conceptes Matematics
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′)
1.7. Objectes i contactes dins un mon virtual 21
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
22 Capıtol 1. Conceptes Matematics
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 .
1.7. Objectes i contactes dins un mon virtual 23
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
24 Capıtol 1. Conceptes Matematics
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 ‖
26 Capıtol 1. Conceptes Matematics
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
30 Capıtol 2. Dinamica de partıcules
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)
32 Capıtol 2. Dinamica de partıcules
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:
34 Capıtol 2. Dinamica de partıcules
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.
36 Capıtol 2. Dinamica de partıcules
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
38 Capıtol 2. Dinamica de partıcules
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 .