semaine 04 3DMath - Cours

2018-01-13

34

Département de génie logiciel et des TI

Concepts mathématiques

LOG725 Ingénierie et conception de jeux vidéo

LOG725 Ing. et conception de jeux vidéo Hiver 2018 67


Concepts mathématiques

• Un jeu est un modèle mathématique d’un monde virtuel simulé en temps réel.

• Les mathématiques sont utilisés dans tous les aspects d’un jeu vidéo.

• Les programmeurs de l’industrie du jeu utilisent toutes les branches des mathématiques, mais plus particulièrement l’algèbre linéaire.

LOG725 Ing. et conception de jeux vidéoHiver 2018 68

2018-01-13

35


Résoudre des problèmes 3D en 2D

• La plupart des concepts décrit dans cette présentation peuvent autant être appliqués en 2D qu’en 3D (mais pas tous!).

• La plupart des exemples seront donc présentés en 2D, mais peuvent être généralisés en 3D.



Points

• Un point est un emplacement dans un espace à n-dimensions (où n = 2 ou 3 dans les jeux).

• Un point peut être représenté selon plusieurs systèmes de coordonnées.


Coordonnées cartésiennes Coordonnées cylindriques Coordonnées sphériques

2018-01-13

36


Coordonnées main gauche / main droite

• Pour placer les 3 axes dans un système de coordonnées cartésiennes, deux choix s’offrent à nous: main droite et main gauche.

• La seule différence entre les deux systèmes est la direction d’un des trois axes.



Coordonnées main gauche / main droite

• Le choix du système main gauche ou main droite est à la discrétion du programmeur.

• L’important est de faire un choix et d’y adhérer!

• Par contre, un système peut être plus pratique que d’autres pour certaines applications:– Pour le rendu, les programmeurs 3D utilisent

généralement un système main gauche. Pourquoi?


2018-01-13

37


Vecteurs

• Un vecteur est une quantité avec une direction (n dimensions).

• Un scalaire (un nombre réel) est quant à lui une quantité sans direction.

• Un vecteur 3D est représenté par 3 scalaires, comme pourun point (x, y, z).



Base cartésienne

• Il est souvent utile de définir trois vecteurs unitaires orthogonaux correspondant à chacun des trois axes cartésiennes.

• Ces vecteurs unitaires sont respectivement appelés i, j et k pour les axes x, y, z.

• i = [1, 0, 0], j = [0, 1, 0], k = [0, 0, 1]• N’importe quel point ou vecteur peut être

exprimé comme une somme de scalaires multipliés par ces vecteurs:– (5, 3, -2) = 5i + 3j – 2k


2018-01-13

38


Opérations vectorielles

• Multiplication par un scalaire:

• Le scalaire peut être différent pour chaque axe:




• Addition et soustraction:


2018-01-13

39



• Deux directions (vecteurs) peuvent être additionnées et soustraites sans problème, mais certaines contraintes s’imposent avec les points:– direction + direction = direction– direction – direction = direction– point + direction = point– point – point = direction– point + point = ?




• La quantité (norme) d’un vecteur est calculée à l’aide du théorème de Pythagore.


2018-01-13

40


Application des opérations vectorielles

• Avec ces simples opérations, on peut déjà résoudre plusieurs problèmes dans un jeu.

• Par exemple, avec le vecteur de position P1 d’un personnage contrôlé par l’IA, et son vecteur de vitesse v, on peut trouver P2 à la prochaine frame: P2 = P1 + v Δt



Application des opérations vectorielles

• On peut également déterminer si 2 sphères se coupent. Comment?

• Avec leur centre respectif C1 et C2, on trouve le vecteur de direction entre les deux: d = C2 – C1

• La norme du vecteur d indique la distance entre les deuxsphères. Si cette distance est plus petite que la somme des rayons des sphères, il y a intersection.


2018-01-13

41


Norme et normalisation

• Comme les racines carrées sont très lentes à calculer, la norme au carrée est plutôt utilisée:

• Dans l’exemple précédent, on compare donc d2 à la somme des rayons au carré (r1 + r2)2.

• Un vecteur de quantité arbitraire peut être transformé en vecteur unitaire en le divisant par sa norme:



Vecteur normal

• Un vecteur normal est un vecteur perpendiculaire à une surface.

• Ce concept est très utilisé dans les jeux vidéo. Des exemples?

• Ne pas confondre un vecteur normal et un vecteur normalisé!


2018-01-13

42


Produit scalaire

• Le produit scalaire est défini par l’addition des produits des composantes de deux vecteurs:

• Le résultat d est un scalaire. Il peut aussi être calculé ainsi:

• Le produit scalaire est commutatif et distributif sur l’addition.



Produit scalaire

• Si u est un vecteur unitaire, le produit scalaire a · u représente la longueur de la projection du vecteur a sur la droite infinie représentée par u.


2018-01-13

43


Produit scalaire• Le produit scalaire est très utile pour tester si deux

vecteurs sont colinéaires, perpendiculaires, ou s’ils pointent dans la même direction:– Colinéaires: a · b =|a||b| (l’angle entre les vecteurs est

d’exactement 0 degré)– Colinéaires mais opposés: a · b =|a||b| * -1 (l’angle entre

les vecteurs est de 180 degrés)– Perpendiculaires: a · b = 0 (l’angle entre les vecteurs est de

90 degrés)– Même direction: a · b > 0 (l’angle entre les vecteurs est

inférieur à 90 degrés)– Direction opposée: a · b < 0 (l’angle entre les vecteurs et

supérieur à 90 degrés)



Applications du produit scalaire

• Le produit scalaire est utilisé pour résoudre plusieurs problèmes dans la programmation des jeux.

• Par exemple: On peut déterminer si un ennemi fait face au personnage.


2018-01-13

44


Applications du produit scalaire

• On peut aussi l’utiliser pour calculer la hauteur d’un point P au dessus d’un plan (dans un jeu d’atterrissage lunaire par exemple).

• h = (P – Q) · n, où Q = n’importe quel point sur le plan, et n = vecteur unitaire normal au plan.



Produit vectoriel

• Le produit vectoriel de deux vecteurs résulte en un vecteur perpendiculaire aux deux vecteurs.

• Le produit vectoriel est uniquement défini en 3 dimensions.


2018-01-13

45


Produit vectoriel

• Le vecteur résultant du produit vectoriel peut être visualisé grâce à la règle de la main droite dans un système main droite, et la règle de la main gauche dans un système main gauche.

• Le produit vectoriel est entre autres utilisé dans la physique pour calculer le moment (force de rotation) lorsqu’une force est appliquée hors centre.



Interpolation linéaire de points et vecteurs

• Dans les jeux, il est souvent nécessaire de trouver un vecteur à mi-chemin entre deux vecteurs. Par exemple, pour animer un objet de façon fluide d’un point A au point B sur deux secondes, à 30 FPS, 60 positions intermédiaires doivent être calculées.


2018-01-13

46


Matrices

• Une matrice est un tableau rectangulaire de m x n scalaires. Les matrices sont une façon pratique de représenter des transformations linéaires, comme les translations, rotations et mises à l’échelle (scaling).



Matrices de transformation

• Sous certaines conditions, une matrice 4x4 peut représenter une transformation 3D arbitraire, qui peut inclure des translations, rotations, et mises à l’échelle. Ce sont des matrices de transformation.

• Ces matrices sont très utilisées dans les jeux vidéo.


2018-01-13

47


Multiplication matricielle

• Le produit P de deux matrices A et B est écrit P = AB. Si A et B sont des matrices de transformation, le produit P est une autre matrice de transformation qui applique les deux transformations originales.

• Deux matrices peuvent être multipliées seulement si leurs dimensions internes sont égales.– Pour A = nA x mA et B = nB x mB– La multiplication est seulement possible si mA = nB.– La matrice résultante est de taille nA x mB.



Multiplication matricielle

• Si A et B sont deux matrices 3x3, P = AB:

• La multiplication matricielle n’est pas commutative: AB != BA.


2018-01-13

48


Points/vecteurs sous forme de matrice

• Un point/vecteur peut être représenté comme une matrice rangée (1 x n) ou une matrice colonne (n x 1). Par exemple, le vecteur v = (3, 4, -1) peu être écrit de ces façons:



Points/vecteurs sous forme de matrice

• Si plusieurs matrices de transformations (A, B, C) sont appliquées dans cet ordre au vecteur v, les transformations sont « lues » de gauche à droite si v est une matrice rangée, et de droite à gauche si v est une matrice colonne.

• Truc: La matrice la plus près de v est appliquée en premier.


2018-01-13

49


Matrice identité

• La matrice identité est une matrice qui, lorsque multipliée par n’importe quelle matrice, résulte en la même matrice:



Translation

• Cette matrice déplace un point r par le vecteur t:


2018-01-13

50


Rotation

• Cette matrice effectue une rotation du point r autour de l’axe X:



Rotation

• Cette matrice effectue une rotation du point r autour de l’axe Y:


2018-01-13

51


Rotation

• Cette matrice effectue une rotation du point r autour de l’axe Z:



Mise à l’échelle

• Cette matrice effectue une mise à l’échelle du point r par les scalaires sx, sy et sz.


2018-01-13

52


Matrices

• La quatrième colonne d’une matrice de transformation affine est toujours [0 0 0 1]T.

• Pour cette raison, certaines librairies mathématiques omettent cette colonne et utilisent des matrices 4x3.

• Comme on utilise des matrices 4x4, nos vecteurs / points doivent être de dimension 1x4. On utilise donc la valeur 1 pour la quatrième valeur : [x, y, z, 1]



Matrices

• Quelques exemples!


2018-01-13

53


Espaces de coordonnées

• Un point ou un vecteur est toujours représenté de façon relative à des axes prédéfinis.

• Un même point a donc avoir des coordonnées différentes selon le système d’axes utilisé.



Espace modèle

• Quand un maillage (mesh), est créé dans un outil tel que Maya ou 3ds Max, les positions des vertex sont exprimés dans un système de coordonnées cartésiennes que l’on appelle l’espace modèle (model space).

• L’origine est généralement situé à un endroit central de l’objet, comme au centre de masse ou bien entre les pieds.


2018-01-13

54


Espace modèle

• La plupart des objets ont une direction. Par exemple, un avion a un nez, une queue et des ailes qui correspondent à l’avant, le haut et gauche/droite.



Espace monde

• L’espace monde (world space) est un espace de coordonnées fixe, dans lequel les positions, orientations et échelles des objets sont définies.

• Cet espace de coordonnée unifie les objets individuels dans un monde virtuel cohésif.

• L’origine de l’espace monde est à la discrétion du programmeur, mais est généralement placé proche du centre de l’espace jouable pour minimiser les problèmes de précision quand les coordonnées prennent de l’ampleur.


2018-01-13

55


Espace monde

• Par exemple, l’aile d’un avion peut être à (5,0,0) en espace modèle. Dans l’espace monde, on effectue une rotation et une translation sur l’avion, ce qui place l’aile à (-25,50,8).



Espace monde

• Dans l’exemple précédent, si nous avons plusieurs avions dans le monde, leur aile est toujours à (5,0,0) dans l’espace modèle.

• Les ailes sont à des positions différentes dans l’espace monde.


2018-01-13

56


Espace vue (espace caméra)

• L’espace vue est un espace de coordonnées fixé à la caméra. L’origine est placé au point focal de la caméra.

• Plusieurs orientations d’axes sont possibles, mais on utilise généralement la convention yvers le haut, et z qui augmente dans la direction qui fait face à la caméra.



Changement de base

• Il est souvent utile de changer la position, orientation et échelle d’un objet d’un espace de coordonnées à un autre.

• Les espaces de coordonnées sont exprimés sous forme de hiérarchie. L’espace monde est à la racine et n’a pas de parent.

• Les autres espaces sont tous des enfants directs ou éloignés de l’espace monde.


2018-01-13

57


Changement de base

• La matrice qui transforme des points et directions d’un espace de coordonnées enfant C vers l’espace de coordonnées de son parent P peut être écrite MC->P

• Un point PC de l’espace enfant peut être transformé en point PP dans un espace parent comme ceci:



Changement de base

• iC : Vecteur unitaire de l’axe x de l’espace enfant, exprimé en coordonnées de l’espace parent.

• jC : Vecteur unitaire de l’axe y de l’espace enfant, exprimé en coordonnées de l’espace parent.

• kC : Vecteur unitaire de l’axe z de l’espace enfant, exprimé en coordonnées de l’espace parent.

• tC : Translation de l’espace enfant relativement à l’espace parent.

• Exemple!


2018-01-13

58


Quaternions

• Une matrice 3x3 peut être utilisée pour représenter une rotation arbitraire en 3 dimensions, mais ce n’est pas toujours idéal:– Neuf valeurs float. Ceci semble excessif considérant

qu’on a seulement 3 degrés de liberté.– Une rotation d’un vecteur nécessite trois produits

scalaires, donc neuf multiplications et six additions.– Dans les jeux vidéo, c’est souvent nécessaire

d’interpoler entre deux rotations (animation sur quelques secondes par exemple). Avec des matrices, ceci est difficile.



Quaternions

• Le quaternion est une représentation rotationnelle qui résout ces 3 problèmes.

• Il a été développé en 1843 comme extension aux nombres complexes. Un quaternion peut être exprimé comme un nombre complexe 4D, avec un axe réel et trois axes imaginaires représentés par i, j et k.

• Pour ce cours, il est uniquement nécessaire de savoir qu’un quaternion unitaire représente une rotation 3D:

q = [qx qy qz qw] où qx2 + qy

2 + qz2 + qw

2 = 1


2018-01-13

59


Quaternions

• Un quaternion unitaire peut être visualisé comme un vecteur 3D en plus d’une coordonnée scalaire. La partie vectorielle qv est l’axe de rotation unitaire, mis à l’échelle avec le sinus de la moitié de l’angle de rotation. Le partie scalaire qs est le cosinus de la moitié de l’angle.

• Où a est le vecteur unitaire selon l’axe de rotation, et téta l’angle de rotation.



Quaternions

• On peut écrire q sous forme de vecteur à 4 éléments:


2018-01-13

60


Quaternions

• La plus importante opération des quaternions est la multiplication. Avec deux quaternions p et q qui représentent deux rotations P et Q, le produit pq représente la rotation composée (Q suivi de P).

• Une des façons de multiplier les quaternions, le produit Grassman:



Équivalence quaternion-matrice

• On peut facilement transformer une rotation 3D de sa forme matricielle 3x3 vers sa forme quaternion et vice versa.– Si q = [qvx qvy qvz qs] = [x y z w], alors:


2018-01-13

61


Quaternions – Interpolations

• Tel que mentionné précédemment, les quaternions permettent une interpolation linéaire de rotations. Avec deux quaternions qA et qB, on peut trouver une rotation intermédiaire ainsi:




• L’interpolation LERP est problématique, parce qu’elle ne considère pas le fait que les quaternions sont en fait des points sur une hypersphère 4D. LERP effectue donc une interpolation sur une corde de l’hypersphèreplutôt q’un arc, ce qui cause des animations qui n’ont pas une vitesse angulaire constante.

• La rotation sera donc plus lente au début et à la fin de l’animation, et plus rapide au centre.


2018-01-13

62



• Pour régler ce problème, on utilise l’interpolation linéaire sphérique, ou SLERP.

• SLERP utilise les sinus et cosinus pour interpoler sur l’arc d’un grand cercle de l’hypersphère 4D.




• SLERP est plus lent à calculer que LERP, et il n’y a pas de consensus sur lequel utiliser.

• Il est donc important de mesurer vos implémentations avant de prendre une décision.


2018-01-13

63


Comparaisons de rotations

• Angles d’Euler: Vecteur 3D : [ƟY, ƟP, ƟR] (yaw, pitch, roll)– +: Simplicité, petit (3 valeurs), intuitif.– -: Interpolation difficile lorsqu’autour d’axes

arbitraries. Gimbal lock. L’ordre de rotation autourdes axes est important.




• Matrices 3x3:– +: Les rotations peuvent être appliquées

simplement via la multiplication matricielle. La plupart des CPU et GPU ont des fonctionnalités pour accélérer les calculs matriciels.

– -: Pas très intuitif, beaucoup d’espace, pas facile à interpoler.


2018-01-13

64



• Axe + angle:– +: Relativement intuitif et compact.– -: Interpolation difficile. Pour appliquer la rotation

a des points et vecteurs, on doit convertir en matrice.




• Quaternion:– +: Compact. Interpolation simple avec LERP/SLERP.

Concaténation de rotations simple.– -: Peu intuitif, très complexe.


2018-01-13

65


Lignes, rayons

• L’équation paramétrique d’une ligne infinie:

• Un rayon est une ligne qui s’étend à l’infinidans une seule direction.


Ligne Rayon


Sphère, plan

• Une sphère est représentée par un centre C et un rayon r : [Cx Cy Cz r]

• Un plan est une surface 2D dans un espace 3D: Ax + By + Cz + D = 0

• Un plan est représenté par un point P0 et un vecteur unitaire n, normal au plan.

• Si le vecteur [A B C] est normalise à [a b c], iléquivaut à n.

• d = D / sqrt(A2 + B2 + C2) = distance du plan à l’origine.


2

DépartementdegénielogicieletdesTI

Définitions•  Point:localisationdansl’espacen-doùn=2(2D),n=3(3D)

•  SystèmedecoordonnéesCartésienpossèdedonc2ou3axesperpendiculairespourspécifierunepositiondansl’espace

•  Donc,unpointpestreprésentéparunepaire(x,y)outriplet(x,y,z)

3 LOG725Ing.etconceptiondejeuxvidéoÉté2017


Systèmedecoordonnées•  Lechoixdusystèmedecoordonnéesdoitêtremotivéparleproblème§  ex.animationselonunaxeenspiraleseramodéliséeavecdescoordonnéescylindrique


Coordonnées sphériques Coordonnées cylindriques

3


Règledelamaindroite•  Larègledelamaindroitepermetd’identifierl’ordredesaxesx,yetzdansunespaceCartésien.


x X y = z x

y

z

x = [1 0 0] y = [0 1 0] z = [0 0 1]


Quelquespropriétésdesvecteurs

• Multiplicationd’unvecteurparunscalaire•  Additionetsoustraction

§  dir+dir=dir§  point+dir=point§  point–point=dir§  point+point=?

• Magnituded’unvecteur•  Normed’unvecteur


4


Interpolationlinéaire(LERP)•  Utilisationdesopérateursaddition,multiplicationetfacteurd’échellepourgénérerdesdonnéesàpartirduconnu


ex. une balle qui tombe

Possibilité d’interpoler à chaque incrément de temps les positions pi.

p2=p1 +vΔt


Distanceentredeuxsphères


c1

c2

d=c2-c1 |d| est la distance relative entre les centres c

Les deux sphères se touchent lorsque: |d| < |r1 + r2| Note: la racine carrée est coûteuse en temps de calcul. Il est préférable d’utiliser la norme au carré.

5


Vecteurnormal•  Levecteurnormalàunesurfaceestunvecteurperpendiculaireàladitesurface

•  L’utilisationdesvecteursnormauxestprépondérantedansunengindejeuvidéo§  Pourquoi?Déterminationdel’illuminationd’unpixeldelascène3D


n source

Quelle est la différence entre normalisation et vecteur normal?


Rappelduproduitscalaire•  Produitscalaire:a.b=axbx+ayby+azbz=d(scalaire)•  Propriétés:

§  commutatif(a.b=b.a)§  distributifsurl’addition(a.(b+c)=a.b+a.c)§  combineavecunscalaire(sa.b=a.sb=s(a.b))


6


Projectiond’unvecteur•  L’utilitéduproduitscalaireestlaprojectiond’unvecteur.

•  ex.Soituunvecteurunitaire,alorsa.uestlalongueurduvecteurprojetésuru.


a

u

d =a.u

Note: la magnitude au carré |a|2 = a.a |a| = sqrt(a.a) Pourquoi? Indice: cosinus de l’angle entre a et a...


Applicationduproduitscalaire•  Leproduitscalaireestutilepourvérifiersideuxvecteurssontcolinéairesouperpendiculairesl’unparrapportàl’autre§  Colinéairelorsquea.b=|a||b|carl’angleentrelesdeuxvecteursestégalà0

§  Colinéairemaisopposélorsquea.b=-|a||b|§  Perpendiculairelorsquea.b=0carl’angleentrelesdeuxvecteurségale90o

§  Mêmeorientationlorsquea.b>90o.Opposéelorsque<90o


7


Exemplesd’application


Personnage Ennemi

f v

Détection de l’orientation d’un ennemi, pour activer une routine d’attaque par exemple. d = v . f si d > 0 ennemi en avant

d < 0 ennemi en arrière

E P vecteur f est tiré de la matrice world-view v = E-P

Source: Contras, Konami


Exemplesd’application•  LeproduitscalairepeutêtreutilisépourtrouverladistanceentreunplanetunpointP.


n P

Q h = (P-Q) . n

8


Rappelsurleproduitvectoriel•  Leproduitvectorielentredeuxvecteursproduitunvecteurperpendiculaireauplanformésparlesdeuxvecteursd’origine

axb=[aybz–azby,azbx–axbz,axby–aybx]axb=|a||b|sinΘ



Propriétésduproduitvectoriel•  Leproduitvectorieln’estpascommutatifaxbn’estpaséquivalentàbxa,maisà-(bxa)

•  Distributifsurl’addition§  ax(b+c)=axb+axc

•  Scalaire§  saxb=ax(sb)=s(axb)

•  Dansunespacecartésien§  ixj=-(jxi)=ketainsidesuitepourietj


9


Introductionàl’interpolationlinéaire

•  AnimationlinéaireentredeuxpointsAetBnotéeLERP(A,B,β)ouL(A,B,β).CettefonctionmathématiquetrouveunpointintermédiaireentreAetBselonunratioβvariantde0-1.Ex.LERP(A,B,t)=(1-β)A+βB

•  Enfait,LERPestlevecteurdepositiondeβ%selonladirectionA-B.Onappellecelaunemoyennepondéréeentredeuxpositions.



Quaternion•  Lesquaternionsunitairesreprésententl’orientationetlarotation,avecuneformulationplussimpleetplusefficace

•  “Vecteurderotation”facileàinterpoler,voirSLERPpourl’interpolationlinéairedesrotations


Source: https://en.wikipedia.org/wiki/Quaternion

Documents

semaine 04 3DMath - Cours