Infographie - M1 Chapitre 1 - Rappels d'Algèbre
V.Padovani Equipe Preuves, Programmes et Systèmes, Université Paris 7 Nous rappelons i i les éléments d'algèbre élémentaire utilisés dans toutes la suite : points, ve teurs, oordonnées, matri es, ainsi que les trois opérations de base les plus fréquemment utilisées en algorithmique infographique - produit en
roix, produit s alaire, produit ve toriel. Les notions de points et ve teurs seront
onsidérées dans leur sens le plus intuitif - et non, si l'on souhaitait être plus rigoureux, omme les éléments d'un espa e a ne et eux d'un espa e ve toriel.
1
Points, Ve teurs
Un point est un empla ement dans l'espa e usuel.
Un ve teur est un trajet
re tiligne entre deux points, en onsidérant omme égaux les trajets de même dire tion et de même longueur, i.e. en notant à un point
B,
on a par exemple
~ = CD ~ AB
~ AB
le trajet allant d'un point
A
dans le diagramme i-dessous :
B
D
AB
CD
A
C
Deux ve teurs parallèles, mais éventuellement de dire tions opposées et de longueurs diérentes, seront dont olinéraires (( 'est-à-dire sur la même ligne).
1.1 Coordonnées des points et ve teurs Les points et ve teurs de l'espa e à 3 dimensions seront uniformément représen(x, y, z) ∈ R 3 représentant un point ou
tés par des triplets de réels. Un triplet
un ve teur sera appelé oordonnées de e point ou de e ve teur. En fon tion du
ontexte, un triplet pourra être vu soit omme un point, soit omme un ve teur.
A est don un ~ , un triplet de U
Un point ve teur
ve teur de oordonnées
(Ax , Ay , Az ) vu omme un point, et un (Ux , Uy , Uz ) vu omme un ve teur. Le point et le ~. nulles se notent respe tivement O et O triplet de réels
réels
1.2 Opérations sur les oordonnées On généralise l'addition usuelle des réels aux triplets de réels posant :
x
x′
x + x′
y + y′ = y + y′ z
z + z′
z′
1
(x, y, z) ∈ R 3 ,
en
On dé nit d'autre part la multipli ation d'un réel (x, y, z) ∈ R 3 en posant :
x
k∈R
k×x
et d'un triplet de réels
k× y = k×y k×z
z
On pose également:
x
x′
x
x′
x − x′
y − y ′ = y + (−1) × y ′ = y − y ′ z′
z
z − z′
z′
z
~ omme étant AB B − A = D − C , et que
Ave es onventions, on dé nit les oordonnés du ve teur égales à
B − A. Noter que ~ A, le ve teur OA
pour tout
~ = CD ~ AB
et le point
mais ont les même oordonneés. tous points
A, B, C ,
si et seulement
A
sont deux objets de nature distin te,
On véri e fa ilement d'autre part que pour
on a :
~ + BC ~ = AC ~ AB q ~ = Ux2 + Uy2 + Uz2 . La norme d'un ve teur est par dé nition ||U||
Les propriétés
suivantes sont fa ilement véri ables:
~ = • ||AB||
est égale à la distan e entre
A
et
B
~ || = |α| × ||U ~ || • ||α × U ~ + V || ≤ ||U ~ || + ||V ~ || • ||U Toutes es dé nitions se spé ialisent aux ouples de
R 2,
représentant les posi-
tions de points dans l'espa e à deux dimensions : il su t d'oublier la troisième
omposante de haque triplet, ou en ore de lui donner une valeur toujours nulle.
1.3 Modélisation de l'espa e 3D usuel Les oordonnées d'un point permettent de spé i er sa positions dans l'espa e relativement à un ertain repère, dé ni en hoisissant :
un point origine, de
O), et trois ve teurs deux à deux non olinéaires, i, ~j, ~k . Les oordonnés (Px , Py , Pz ) d'un point spé i ent alors sa position notés ~ ~ = Px ×~i+Py ×~j+Pz ×~z. En pratique, dans l'espa e en onvenant du fait que OP i, ~j, ~k) orthonormé de type main droite, dans on hoisit un repère standard (O,~ lequel les ve teurs ~ i, ~j, ~k sont de longeur 1, deux à deux orthogonaux, et orientés
oordonnés nulles (le point
omme suit :
2
y
Py P j O
x
k
Px
i
Pz z
2
Produit en Croix (en dimension 2)
2.1 Dé nition Le produit roisé ou produit en roix de deux ve teurs du plan est dé ni par:
~ ∝ V~ = U
Ux Uy
!
∝
Vx Vy
!
=
Ux
Vx
Uy
Vy
= Ux Vy − Uy Vx
2.2 Propriétés opératoires ~ ∝ V~ = −(U ~ ∝V ~) U
•
anti- ommutatif :
•
asso iatif ave le produit d'un réel et d'un ve teur :
~) ∝ V ~ = α × (U ~ ∝ V~ ) (α × U •
distributif par rapport à l'addition des ve teurs :
~ ∝ (V ~ +W ~ ) = (U ~ ∝V ~ ) + (U ~ ∝W ~) U
2.3 Interprétation Le produit roisé permet d'estimer le sinus de l'angle formé par deux ve teurs. En pratique, il fournit, en dimension 2, un test de olinéarité pour deux ve teurs non nuls, et d'autre part, un test de pla ement d'un point relativement à une droite. La propriété suivante est en eet démontrable :
~ ∝U ~ =k U ~ k×kV ~ k × sin θ U ~ et V ~ sont non nuls, on a U ~ ∝V ~ =0 ~d U V~ . En parti ulier, si U ~ ~ ~ ~ si et seulement si U et V sont olinéaires. Si par ontre U et V ne sont pas ~ alignant U ~ ave V ~ tourne dans
olinéaires, la rotation minimale du ve teur U ~ ~ ~ ~ le sens dire t si U ∝ V > 0, dans le sens indire t si U ∝ V < 0. où
θ
est l'angle
3
produit en croix = 0
U produit en croix > 0
Soit à présent
D
M
~ M , et de ve teur dire teur U ~ . En X tel que M~X = k × U ~ . on a alors : dire tion U
une droite ontenant un point
k ∈R
'est-à-dire ontenant pour tout plaçant en
produit en croix < 0
V
le point
un observateur regardant dans la
P MP
produit en croix > 0
D
U
produit en croix = 0
M
produit en croix < 0
~ ∝ M~P = 0 ⇐⇒ P • U
est sur
~ ∝ M~P > 0 ⇐⇒ P • U
est à gau he de
~ ∝ M~P < 0 ⇐⇒ P • U
est à droite de
D D
D
Le produit en roix permet d'autre part de retrouver l'équation de la droite à partir de la donnée de
M
et de
~. U
D
On a en eet :
~ ∝ M~X = 0 ⇐⇒ Ux × (y − My ) − Uy × (x − Mx ) = 0 X = (x, y) ∈ D ⇐⇒ U
3
Produit s alaire (en dimension 2 ou 3)
3.1 Dé nition Le produit s alaire de deux ve teurs de l'espa e (ou du plan, en oubliant la
omposante
z ),
est dé ni par :
Ux
Vx
~ ·V ~ = U Uy · Vy = (Ux × Vx ) + (Uy × Vy ) + (Uz × Vz ) Uz
Vz
3.2 Propriétés opératoires ~ ·U ~ =k U ~ k2 • U •
ommutatif
~ ·V ~ = V~ · U ~ U 4
•
asso iatif ave le produit d'un réel et d'un ve teur :
~ ) · V~ = α × (U ~ ·V ~) (α × U •
distributif par rapport à l'addition des ve teurs :
~ · (V ~ +W ~ ) = (U ~ ·V ~ ) + (U ~ ·W ~) U
3.3 Interprétation Le produit s alaire permet d'estimer le osinus de l'angle formé par deux ve teurs. En pratique, il permet de véri er si et angle est plus grand, plus petit ou égal à un angle droit - en parti ulier, il fournit un test d'orthogonalité pour deux ve teurs non nuls. En 3D, il fournit également un test de pla ement d'un point relativement à un plan, et permet de retrouver l'équation de e plan. La propriété suivante est en eet démontrable :
~ ·V ~ =k U ~ k × k V~ k × cos θ U où
~d ~ . On en déduit que : U V ~ ·V ~ >0⇔U ~ et V~ forment un angle • U
θ
est l'angle
stri tement plus petit que l'angle droit
~ ·V ~ =0⇔U ~ • U
et
V~
sont orthogonaux
~ ·V ~ <0⇔U ~ • U
et
V~
forment un angle
stri tement plus grand que l'angle droit
U produit scalaire > 0 produit scalaire = 0 V
Soit à présent un plan
Π
produit scalaire < 0
ontenant un point
M,
~ N
et de normale
(i.e.
un ve teur orthogonal au plan). On a :
plan de P normale N MP
N
produit scalaire > 0 produit scalaire = 0
M
produit scalaire < 0
~ · M~X = 0 ⇐⇒ X • N
appartient à
~ · M~X > 0 ⇐⇒ X • N
est du même té du plan que
~ · M~X < 0 ⇐⇒ X • N
est du té du plan opposé à
L'équation du plan est don
Π(X) = 0,
Π
ave
~. N
~. N
~ · M~X , Π(X) = N
soit:
Nx × (x − Mx ) + Ny × (y − My ) + Nz × (z − Mz ) = 0 5
~ N
est
4
Produit ve toriel (dimension 3)
4.1 Dé nition Le produit ve toriel de deux ve teurs de l'espa e est dé ni par :
Ux Vx Uy ∧ Vy = − Uz Vz
Uy
Vy
Uz
Vz
Ux
Vx
Uz
Vz
Ux
Vx
Uy
Vy
Uy Vz − Uz Vy
= −Ux Vz + Uz Vx Ux Vy − Uy Vx
4.2 Propriétés opératoire
~ ∧ V~ = −(V ~ ∧U ~) U
•
anti- ommutatif :
•
asso iatif ave le produit d'un réel et d'un ve teur :
~ = k × (U ∧ V ). (k × U ) ∧ V •
distributif par rapport à l'addition des ve teurs :
~ ∧ (V ~ +W ~ )=U ~ ∧V ~ +U ~ ∧W ~. U •
non asso iatif.
4.3 Interprétation Le produit ve toriel de deux ve teurs de l'espa e est un nouveau ve teur orthogonal aux deux premiers lorsque es deux ve teurs sont non nuls et non
olinéaires, nul sinon. Il permet en parti ulier de al uler une normale plan engendré par un point
~, V
M
~ au N ~ et U
et deux ve teurs non nuls et non olinéaires
don de retrouver l'équation de e plan et un test de pla ement d'un point
relativement au plan.
N V U Les propriétes suivantes sont démontrables :
6
~ ∧V ~ k=k U ~ k×kV ~ k × sin θ • kU •
~d θ=U V~ .
Si le produit ve toriel est non nul, la rotation ontinue minimale de alignant
•
où
si
~ U
ave
~ =U ~ ∧V ~ N
V~
puis ave
~ ∧V ~) (U
est non nul, alors
~ ⊥U ~ N
~ U
tourne dans le sens dire t. et
~ ⊥V ~. N
est le ve teur normal de tout plan engendré par
En parti ulier, e ve teur
~, V ~. U
~ , V~ deux ve teurs non nuls et non olinéaires, le ve teur M est un point et U ~ ∧V ~ est don une normale au plan Π ontenant M et engendré par U ~, N =U ~ . On peut don retrouver l'équation du plan en appliquant la méthode de la V ~′ = V ~ ∧U ~ , on obtient une normale se tion pré édente. Noter qu'en hoisissant N ′ ′ de dire tion opposée, et une équation Π (X) = 0 ave Π(X) = −Π (X) pour tout X . Le test de pla ement d'un point déduit de l'équation dépend don du Si
hoix de la normale.
5
Matri e de Transformations
Les transformations de points ou de groupes de points telles que translations, rotations, hangements d'é helle (s aling) sont habituellement représentées, à une dimension donnée (2 ou 3), par des matri es arrées, dont le té est égal à la dimension ourante plus 1. On traitera i i le as de la dimension 3, et des transformations uniformément représentées par des matri es pour al uler le transformé d'un point par la matri e
•
MT
On ajoute à
4 × 4. La méthode T représentée
par une transformation
est toujours la même :
P
une oordonnée, toujours égale à
On obtient un point
•
P
1.
′
P = (Px , Py , Pz , 1).
On al ule la valeur de
Q′ = MT × P ′ .
Par onvention, la matri e
MT Q′
est toujours onstruite de manière à e que la dernière omposante de soit égale à 1.
•
On oublie la dernière omposant de On obtient un point
Px Py Py −→ P z Pz 1
Px
Q′ .
Q = (Qx , Qy , Qz ) Px P −→ M × y P z 1
7
qui est l'image de
P
par
T.
Qx Qx Qy = Q −→ Qy z Qz 1
5.1 Rappels Le produit d'une matri e et d'un ve teur est dé ni omme suit :
a11
...
a1p
. . .
. . .
an1
anp
x1 a11 × x1 + . . . + a1p × xp .. . . × . = . xp an1 × x1 + . . . + anp × xp
Dans le as des matri es de transformation, la matri e a toujours la forme idessous :
a11
a21 a 31 0
a12
a13
a22
a23
a32
a33
0
0
a14
Px
a11 Px + a12 Py + a13 Pz + a14
a24 Py a21 Px + a22 Py + a23 Pz + a24 × = a34 Pz a31 Px + a32 Py + a33 Pz + a34 1 1 1
La omposition des transformations se fait par simple produit de leurs matri es :
MT ◦T ′ = MT × MT ′ L'inverse MT −1 = M−1 T .
d'une transformation se fait par al ul de sa
matri e inverse :
5.2 Transformations usuelles Voi i la forme des matri es orrespondant à diverses transformations usuelles :
•
Translation d'un point par un ve teur
•
1
0 0 0
Rotation d'angle
1
0
0 cosθ 0 sinθ 0 0
0 0 1 0 0 1 0 0 θ
Px
−sinθ cosθ
0
:
Px + Ux
Uy Py Px + Uy × = Uz Pz Px + Uz 1 1 1 x
autour de l'axe des
0
0
Ux
~ U
Px
:
Px
0 Py Py × cosθ − Pz × sinθ × = 0 Pz Py × sinθ + Pz × cosθ 1 1 1
y x z
8
•
Rotation d'angle
cosθ
0 −sinθ 0
θ
autour de l'axe des
0
sinθ
1
0
0
cosθ
0
0
0
y
Px
Px × cosθ + Pz × sinθ
0 Py Py × = 0 Pz −Px × sinθ + Pz × cosθ 1 1 1
y
x z •
Rotation d'angle
cosθ
sinθ 0 0
θ
−sinθ cosθ 0 0
z
autour de l'axe des
0 0
Px
:
Px × cosθ − Py × sinθ
0 0 Py Px × sinθ + Py × cosθ × = 1 0 Pz Pz 0 1 1 1
y x
z •
Changement d'é helle non uniforme pour les trois axes, entré en l'origine :
Sx
0 0 0
0
0
Sy
0
0
Sz
0
0
0
Px
Sx × Px
0 Py Sy × Px × = 0 Pz Sz × Pz 1 1 1
9
Sy
Sx Sz
5.3 Autres transformations Les rotations dont l'axe est une droite quel onque, toutes les formes de symétries, les isaillements (shearing), se onstruisent fa ilement par omposition de rotations, translations et hangements d'é helles. Pour les déformations, en général les matri es ne su sent plus.
10