Discussion :

[khayyam90]

bien le bonsoir,

actuellement je travaille sur un jeu de rubikub et j'aimerais que vous me confirmiez ou infirmiez mon modèle mathématique.

mon rubikub est composé de plusieurs cubes. et chaque cube possède une position initiale ainsi que des valeurs d'angles de rotation autour des axes x,y et z (repère direct)
le rubikub est centré en O, orienté selon les axes de la manière la plus simple, pour que les rotations se passent le mieux possible.

puis à chaque mouvement, je mets à jour les champs de rotation des cubes ayant bougé en y ajoutant l'angle de rotation.

Puis pour l'affichage de mon rubikub, je boucle sur les cubes, je les positionne chacun à leur position initiale puis j'effectue les 3 rotations, autour de chaque axe, pour obtenir la nouvelle position du cube.

Obtenant actuellement des résultats un peu ..... surprenants dirais-je, j'aimerais savoir si ma méthode est correcte, étant donné que par exemple si je fais une rotation autour de x puis une rotation autour de z, cela revient (dans ma structure de données) à faire une rotation autour de z puis une roration autour de x, alors que les produits matriciels ne sont pas commutatifs.

[Laurent Gomila]

rubikub

Rubik's Cube, en fait

par exemple si je fais une rotation autour de x puis une rotation autour de z, cela revient (dans ma structure de données) à faire une rotation autour de z puis une roration autour de x, alors que les produits matriciels ne sont pas commutatifs

Les rotations peuvent être effectuées dans n'importe quel ordre, du moment qu'elles ont toutes le même centre. Par contre attention au gimbal lock, pense aux quaternions si tu as des problèmes.

Sinon, je pense qu'il faudrait que tu détailles tes problèmes et la manière dont tu effectues tes transformations.

[khayyam90]

Rubik's Cube, en fait

ayant trouvé plusieurs orthographes, je ne savais laquelle prendre.

Les rotations peuvent être effectuées dans n'importe quel ordre, du moment qu'elles ont toutes le même centre.

Tous mes axes de rotation sont coucourrents, si c'était l'objet de ta remarque.

Sinon, je pense qu'il faudrait que tu détailles tes problèmes et la manière dont tu effectues tes transformations.

Chaque champ rotationx/y/z de chaque cube est initialisé à 0.
Chaque mouvement autour d'un axe augmente le champ relatif à cet axe de l'angle de la rotation, et ceci pour chacun des cube à bouger (une rotation autour de l'axe x amènera un [rotation_x +=angle_de_rotation])

l'affichage des cubes se fait de la manière suivante :
translation d'un cube jusqu'à sa position initiale.
3 rotations autour de l'axe x resp y resp z de [champ relatif à la rotation autour de x resp y resp z] degrés.
cube suivant

Mon problème est qu'après plusieurs rotations autour de différents axes, certains cubes de mon rubiks cube bougent n'importe comment(surement d'une manière précise, mais alors laquelle ... ), un peu comme si ils faisaient des rotations en plus de celles demandées.

Les rotations peuvent être effectuées dans n'importe quel ordre

en voilà une phrase qu'elle est belle et qu'elle me plait

Mais si ma méthode de modélisation des rotations est correcte, alors mon problème est ailleurs.

[Laurent Gomila]

l'affichage des cubes se fait de la manière suivante :
translation d'un cube jusqu'à sa position initiale.
3 rotations autour de l'axe x resp y resp z de [champ relatif à la rotation autour de x resp y resp z] degrés.
cube suivant

Attention au mix avec les translations (là ce n'est plus commutatif). D'autant plus que chaque rotation aura un centre différent, a priori. Un cube peut être modifié en tournant l'une des 2 ou 3 faces qu'il partage, du coup ça fait pas mal de rotations différentes que tu ne peux pas composer simplement en additionnant les angles.

Du coup, ton "modèle" paraît un peu trop simple pour gérer ça, non ?

A mon avis, tu ferais mieux de faire la méthode barbare mais simple et efficace : à chaque rotation d'une face ou du cube tu contruis simplement la matrice correspondante, que tu multiplies (attention à l'ordre) par la matrice de chaque cube afin d'avoir leur nouvelle position.

[khayyam90]

Attention au mix avec les translations (là ce n'est plus commutatif). D'autant plus que chaque rotation aura un centre différent, a priori.

de ce côté là, je n'ai pas d'inquiétude, vu que tous mes cubes restent bien dans le volume du rubiks cube. s'il y avaient des centres différents, un cube sortirait du rubiks cube, ou bien rentrerait dans le rubiks cube, bref, il quitterait sa surface et/ou il perdrait son alignement.

A mon avis, tu ferais mieux de faire la méthode barbare mais simple et efficace

je garde cette option mais en dernier recours

[Nemerle]

.... si je fais une rotation autour de x puis une rotation autour de z, cela revient (dans ma structure de données) à faire une rotation autour de z puis une roration autour de x, alors que les produits matriciels ne sont pas commutatifs.

Je ne comprends pas cette phrase: en rubik's cube, il n'y a pas qu'une composition de rotations, mais il y a sur QUELLES FACES tu opères tes rotations! Donc la notion de commutativité (qui n'existe effectivement pas) doit s'évaluer sur les triplets (A,r,F) où

A est l'axe de rotation
r l'angle de rotation (en multiple de 90° je pense )
F la face sur laquelle s'opère sur rotation.

Si tu représentes ton rubik's cube par des (x,y,z) dans {-1,0,1}^3, tu as par exemple comme action (X,45°,x=1)

[Médiat]

r l'angle de rotation (en multiple de 45° je pense )

C'est pas plutôt 90° ?

[Matthieu Brucher]

Les rotations peuvent être effectuées dans n'importe quel ordre, du moment qu'elles ont toutes le même centre. Par contre attention au gimbal lock, pense aux quaternions si tu as des problèmes.

T'es certains de ce que tu dis ?
Si je fais une rotation autour de x de 20° puis une rotation selon z de 40°, ce n'est pas la même chose si je fais z puis x !!

[Nemerle]

Les rotations peuvent être effectuées dans n'importe quel ordre, du moment qu'elles ont toutes le même centre. Par contre attention au gimbal lock, pense aux quaternions si tu as des problèmes.

T'es certains de ce que tu dis ?
Si je fais une rotation autour de x de 20° puis une rotation selon z de 40°, ce n'est pas la même chose si je fais z puis x !!

Plutôt que d'affirmer, donne voir un exemple CONCRET ou cela ne marche pas, avec coordonnées!


Mediat: je ne comprends pas, c'est bien 90°...

[Médiat]

Mediat: je ne comprends pas, c'est bien 90°...

Je suis à deux doigts, pardon, à 10° de bouillir

[Matthieu Brucher]

Puisque tu y tiens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
octave:2> R1 = [1 0 0; 0 cos(20) sin(20); 0 -sin(20) cos(20)]
R1 =
 
   1.00000   0.00000   0.00000
   0.00000   0.40808   0.91295
   0.00000  -0.91295   0.40808
 
octave:3> R1 * R1'
ans =
 
  1  0  0
  0  1  0
  0  0  1
 
octave:4> R2 = [cos(40) sin(40) 0; -sin(20) cos(20) 0 ; 0 0 1]
R2 =
 
  -0.66694   0.74511   0.00000
  -0.91295   0.40808   0.00000
   0.00000   0.00000   1.00000
 
octave:5> R1 * R2
ans =
 
  -0.66694   0.74511   0.00000
  -0.37256   0.16653   0.91295
   0.83347  -0.37256   0.40808
 
octave:6> R2 * R1
ans =
 
  -0.66694   0.30407   0.68025
  -0.91295   0.16653   0.37256
   0.00000  -0.91295   0.40808

Voilà.

[khayyam90]

.... si je fais une rotation autour de x puis une rotation autour de z, cela revient (dans ma structure de données) à faire une rotation autour de z puis une roration autour de x, alors que les produits matriciels ne sont pas commutatifs.

Je ne comprends pas cette phrase: en rubik's cube, il n'y a pas qu'une composition de rotations, mais il y a sur QUELLES FACES tu opères tes rotations! Donc la notion de commutativité (qui n'existe effectivement pas) doit s'évaluer sur les triplets (A,r,F) où

A est l'axe de rotation
r l'angle de rotation (en multiple de 90° je pense )
F la face sur laquelle s'opère sur rotation.

Si tu représentes ton rubik's cube par des (x,y,z) dans {-1,0,1}^3, tu as par exemple comme action (X,45°,x=1)

c'est en effet comme ça que j'ai procédé pour définir mes actions possibles.
Lorsque je parle de

.... si je fais une rotation autour de x puis une rotation autour de z, cela revient (dans ma structure de données) à faire une rotation autour de z puis une roration autour de x, alors que les produits matriciels ne sont pas commutatifs.

je parle de la manière que j'utilise pour repérer chacun des cubes de mon rubik's cube. A chaque mouvement du rubiks cube, je mets à jour les angles de rotation de tous les cubes concernés par le mouvement.

C'est pas plutôt 90° ?

pas nécessairement, je souhaite me garder la possibilité de faire des rotations de n'importe quel angle, dans le but d'animer le rubiks cube. bien sûr, tant qu'un mouvement ne sera pas terminé (pas un multiple de 90°), un mouvement d'un autre plateau ou autour d'un autre axe ne sera pas autorisé.

[DrTopos]

Bonjour.

Toutes les rotations vectorielles dans l'espace à 3 dimensions ont un axe bien défini (sauf l'identité, c'est à dire la rotation d'angle zéro). Par ailleurs, deux rotations distinctes de l'identité commutent si et seulement si elles ont le même axe. L'affirmation selon laquelle elles commutent si elles ont le même centre est donc fausse. C'est vrai par contre pour la dimension 2.

Maintenant, en ce qui concerne le Rubick's Cube, les 26 petits cubes ont l'air de se déplacer en plus du fait qu'ils tournent. Mais ça c'est un faux problème. En effet, on peut considérer le Rubick's Cube comme un assemblage de 26 grands cubes 'virtuels' (de la taille du Rubick's Cube lui-même) dont seulement 1/27eme est matérialisé (le petit cube, qui est soit au centre d'une face, soit au centre d'une arête, soit dans un coin). Avec cette modélisation, tous les mouvements de ces cubes sont des rotations autour du centre du Rubick's Cube. Il n'y a donc pas à considérer de translations. Bien entendu, les rotations de ces 26 cubes ne sont pas indépendantes les unes des autres (sinon le jeu serait trivial).

La position de chacun des 26 cubes virtuels est définie par une matrice de rotation dans l'espace, c'est à dire une matrice orthogonale 3x3. Maintenant, grâce aux cubes virtuels, les contraintes de mouvement entre les cubes sont très faciles à formaliser. En effet, un mouvement consiste à faire tourner une face du Rubick's Cube, soit 9 cubes virtuels. Or ces 9 cubes virtuels subissent exactement la même rotation. En conséquence, l'état du jeu est défini par 26 matrices, et jouer consiste à multiplier 9 d'entre elles (pas n'importe lesquelles bien sûr) par la même matrice.

Comme toutes les rotations sont de 90 degrés, on est en fait dans un sous-groupe du groupe des rotations. Ce sous-groupe est fini et se compose de seulement 24 éléments. C'est le groupe des isométries directes du cube.

Maintenant, on peut aussi vouloir avoir plusieurs points de vue sur un état du cube, ce qui revient à faire tourner (d'un angle quelconque et selon un axe quelconque) le cube central (le 27eme cube qui est invisible). Pour cela il suffit de multiplier nos 26 matrices par une même matrice.

Par ailleurs, j'ai l'impression que tu utilises des angles d'Euler pour repérer la position de tes cubes. Je crois que c'est une mauvaise idée, car la simulation de la composition des mouvements risque d'être un casse-tête. Il vaut mieux utiliser des matrices.

Bien sûr, il y a plein d'autres problèmes à résoudre, mais je crois que cette notion de cube virtuel pourrait aider.

Bon courage.

[Médiat]

DrTopos, je te trouve bien catégorique (pardon, mais j'étais obligé, et je ne l'aurais pas fait sans ton avatar )

[DrTopos]

J'étais sûr que cet avatar allait faire jaser... et je crois que ce n'est pas fini.

[khayyam90]

deux rotations distinctes de l'identité commutent si et seulement si elles ont le même axe. L'affirmation selon laquelle elles commutent si elles ont le même centre est donc fausse.

voilà qui fixe bien les idées. Ma méthode d'affichage n'était donc pas bonne (bon, ça se voyait, mais maitenant je sais algébriquement pourquoi)

Il n'y a donc pas à considérer de translations.

Mes translations me servent juste à amener le cube

soit au centre d'une face, soit au centre d'une arête, soit dans un coin

. Elles n'interviennent donc pas directement dans les mouvements du cube. Elles étaient présentes d'un point de vue purement pratique, en rapport avec l'API 3D que j'utilise.

Comme toutes les rotations sont de 90 degrés

euuh ... pas exactement, je souhaite pouvoir faire des mouvements partiels, bien sûr, il ne sera pas possible de faire un autre mouvement tant que le mouvement précédent n'aura pas été terminé.

un mouvement consiste à faire tourner une face du Rubick's Cube, soit 9 cubes virtuels. Or ces 9 cubes virtuels subissent exactement la même rotation.

C'était bel et bien mon raisonnement, tu y rajoutes le formalisme algébrique.

Maintenant, on peut aussi vouloir avoir plusieurs points de vue sur un état du cube, ce qui revient à faire tourner (d'un angle quelconque et selon un axe quelconque) le cube central (le 27eme cube qui est invisible).

Je gère cet aspect dans l'autre sens. Plutôt de faire tourner mon cube, je fais tourner la caméra autour du cube. Mon cube reste donc toujours à la même place, orienté de la même manière et ces multiplications de matrices sont gérées pour moi par l'api 3d.

j'ai l'impression que tu utilises des angles d'Euler pour repérer la position de tes cubes

Dans un soucis de simplicité et surtout d'utilisation dans la suite de mon application, je repère mes cubes par les coordonnées cartésiennes (tout simplement) du centre de chacun de mes cubes.

J'étais sûr que cet avatar allait faire jaser... et je crois que ce n'est pas fini.

je m'y mets aussi ... pour la forme [mode jasage], ui, l'est sacrément catégorique ce DrTopos[/mode jasage]

[DrTopos]

Comme toutes les rotations sont de 90 degrés

euuh ... pas exactement, je souhaite pouvoir faire des mouvements partiels, bien sûr, il ne sera pas possible de faire un autre mouvement tant que le mouvement précédent n'aura pas été terminé.

Si donc ton cube ne bouge pas (puisque la camera tourne autour), les mouvements ne font intervenir que les trois rotations autour des axes principaux (et leurs inverses). Les matrices de ces trois rotations sont les suivantes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
1   0   0         0  -1   0          0   0   1
0   0  -1         1   0   0          0   1   0
0   1   0         0   0   1         -1   0   0

C'est simple pour la raison suivante. Dans le plan, la matrice de rotation d'angle 'a' est

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
cos(a)   -sin(a)
sin(a)    cos(a)

Quand a = 90 degrés, ça donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
0   -1
1    0

Si donc on veut tourner dans l'espace de 90 degrés autour de l'axe des x, il suffit de tourner dans le plan des y et z, ce qui donne la première des trois matrices. Les deux autres sont obtenues en permutant circulairement lignes et colonnes, c'est à dire en permutant les rôles de x, y et z.

Si maintenant on veut animer le mouvement, il suffit de prendre (pour tourner autour de l'axe des x) la matrice suivante

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
1   0          0
0   cos(a)     -sin(a)
0   sin(a)     cos(a)

et de faire varier 'a' de 0 à 90 degrés. Pour les autres axes c'est pareil toujours en permutant lignes et colonnes.

je repère mes cubes par les coordonnées cartésiennes (tout simplement) du centre de chacun de mes cubes.

Si tu utilises les cubes virtuels dont j'ai parlé, tu n'as plus à te préoccuper des coordonnées du centre puisque c'est toujours (0,0,0). C'est une matrice 3x3 qui détermine complètement la position du cube. Par contre, il ne faut pas se tromper dans la détermination de la partie du (grand) cube virtuel qui constitue le (petit) cube réel.

Le lien entre les angles d'Euler et les matrices de rotation n'est pas facile à manier. On démontre que pour toute matrice orthogonale 3x3 H, il existe trois angles a, b et c, tels que H = U(a)V(b)U(c) où U(t) est la,rotation d'angle t autour de l'axe des x, et V(t) la rotation d'angle t autour de l'axe des z. a, b et c sont les angles d'Euler de H. Avec la formule ci-dessus on trouve facilement la matrice de rotation H à partir des angles d'Euler, mais l'opération inverse est beaucoup plus périlleuse. Je crois qu'il vaut mieux oublier les angles d'Euler, et utiliser des matrice 3x3 uniquement même si ça a l'air un peu plus lourd.

Une astuce encore qui peut être utile: pour inverser une matrice de rotation (quelle que soit la dimension de l'espace), il suffit de la transposer. 8)

Bonne programmation.

[khayyam90]

même s'il m'a fallu relire le post 15x pour le rendre compte que c'était la démarche (plus ou moins intuitive) que j'avais adoptée, je suis bien content qu'il y ait un algébricien de plus sur ce forum.

[Matthieu Brucher]

deux rotations distinctes de l'identité commutent si et seulement si elles ont le même axe. L'affirmation selon laquelle elles commutent si elles ont le même centre est donc fausse.

voilà qui fixe bien les idées. Ma méthode d'affichage n'était donc pas bonne (bon, ça se voyait, mais maitenant je sais algébriquement pourquoi)

Parce que les matrices n'ont jamais défini un anneau commutatif, c'est ça l'explication algébrique.

[DrTopos]

Parce que les matrices n'ont jamais défini un anneau commutatif, c'est ça l'explication algébrique.

Si on veut, mais il faut être un peu plus précis que cela. Quand un anneau de matrice est suffisamment trivial il est commutatif (matrices 1x1 sur un anneau commutatif), mais en général il ne l'est pas. Toutefois, un sous-groupe du groupe des inversibles d'un anneau de matrice peut être commutatif. Parmi ceux-là, il y a les ``tores'' qui jouent un rôle très important.

Toutefois, dans le cas qui nous intéresse, le groupe SO(3) des isométries de sens direct de l'espace réel à 3 dimensions, le groupe est loin d'être commutatif. Il est tellement pas commutatif, que c'est un groupe ``simple''. Je vais essayer d'expliquer ``simplement'' (pardon pour le jeu de mots) ce que ça veut dire.

Si on prend deux rotations de même angle et d'axes différents, quitte à changer la position de la caméra (voir ce que dit kayyam90), l'une peut se faire passer pour l'autre. Mathématiquement, on exprime cette propriété en disant que ces deux rotations sont conjuguées. Quitte à changer de point de vue, c'est la même. Si P est la matrice de rotation qui change la position de la caméra, et si R1 et R2 sont nos deux rotations, on a R2 = P^(-1) R1 P. On voit bien que si le groupe SO(3) était commutatif, on pourrait permuter R1 et P, et on obtiendrait R2 = R1, c'est à dire qu'on serait incapables de voir où se trouve l'axe d'une rotation ! Maintenant, la simplicité de SO(3) dit que les seuls sous-groupes de SO(3) qui sont stables par conjugaison (c'est à dire que dès qu'ils contiennent une rotation, ils contiennent aussi toutes ses conjuguées) sont 1 (le sous-groupe réduit à l'identité) et SO(3) lui-même. En pratique ça signifie que si on prend une rotation quelconque différente de l'identité, et si on se permet de la conjuger de toutes les façons possibles, de composer et inverser les résultats obtenus, on obtient SO(3) tout entier.

C'est aussi cette non commutativité qui fait la difficulté du jeu du Rubik's cube. Si on joue un peu on voit très rapidement qu'on n'obtient pas la même chose si on fait les mêmes mouvements dans un ordre différent. Ceci dit, le groupe des ``actions'' possibles sur le Rubik's cube n'est pas SO(3). C'est un groupe fini, bien sûr, mais assez gros, nettement plus compliqué en tous cas que le groupe des isométries du cube, et évidemment pas commutatif.