24 mai 2012

0 commentaire — commenter cet article

Comment dessiner un hécatonicosachore ?

Jos Leys

Mathematical Imagery (page web)

L’hécatonicosachore est un polyèdre régulier de l’espace de dimension 4, qui est peut-être mieux connu sous le nom plus simple de 120-cellules. Le 120-cellules possède 600 sommets, 1200 arêtes et 120 cellules qui sont des dodécaèdres. [1] Les polyèdres de l’espace à quatre dimensions sont bien plus compliqués que leurs collègues de la dimension trois ! Il faut donc une liste assez longue de données nécessaires pour les dessiner : les coordonnées des 600 sommets, et en plus il faut savoir quelles paires de sommets il faut connecter pour dessiner les 1200 arêtes.

Nous allons parler ici d’une méthode [2] qui n’a pas besoin de toutes ces données. Il suffit de connaître les symétries de l’objet. La même méthode permet de dessiner tous les polyèdres réguliers de dimension 4 : nous allons rencontrer le pentachore ou simplex, le tesseract ou hypercube, l’hexadécachore ou 16-cellules, l’icositétrachore ou 24-cellules et le hexacosichore ou 600-cellules. Nous allons aussi rencontrer quelques polyèdres irréguliers...

Les outils dont on aura besoin dans ce qui suit sont la projection stéréographique et le lancer de rayon.

Projection stéréographique

Une image n’a que deux dimensions et l’objet qui nous intéresse en a quatre. Pour obtenir une image de l’objet il faut donc réduire le nombre de dimensions à l’aide de projections. On peut passer de quatre dimensions à trois par une projection orthogonale : on prend une des quatre coordonnées comme constante. Pour mieux apprécier la géométrie des polyèdres en quatre dimensions on peut choisir la projection stéréographique, car celle-ci la montre beaucoup mieux. [3]

La figure à gauche montre la projection stéréographique en trois dimensions : un point sur la sphère de dimension 2, $S^2$, est projeté depuis le pôle Nord sur un plan tangent au pôle sud. On peut prendre n’importe quel plan parallèle à celui-là qui ne passe pas par le pôle Nord, par exemple le plan équatorial qui passe par le centre de la sphère.
Dans ce cas un point de la sphère avec coordonnées $(x,y,z)$ est projeté vers un point du plan avec coordonnées $(\frac{x}{1-z,},\frac{y}{1-z})$.

Il en est de même de la sphère de dimension 3, $S^3$, d’équation $x^2+y^2+z^2+w^2=1$. Un point de cette sphère est projeté dans « l’espace 3D équatorial » sur le point $(\frac{x}{1-w,},\frac{y}{1-w},\frac{z}{1-w})$. [4]

La deuxième projection, de 3 dimensions vers les 2 dimensions de l’image se fait par le lancer de rayon.

Lancer de rayon

On choisit une position d’une caméra virtuelle, une direction de vue et un plan qui est perpendiculaire à cette direction. On va projeter tout ce qui se trouve sur des droites, donc des rayons, entre la caméra et chaque pixel d’un rectangle qui se trouve sur ce plan, et qui est centré à l’intersection de la droite de direction et du plan. Tout ce qu’il faut faire c’est de déterminer la couleur de ce pixel. Supposons qu’un objet se trouve entre la caméra et ce rectangle. Pour certains objets on peut déterminer analytiquement le point d’intersection entre une droite vers un pixel et l’objet. Le pixel va alors prendre la couleur de l’objet, corrigée par la position d’une source lumineuse virtuelle.

Si la détermination du point d’intersection est impossible (par exemple pour des objets fractals 3D [5] ), ou difficile (objects compliqués..), on cherche une fonction qui donne la distance, ou une estimation d’une distance, entre un point sur un rayon et l’objet en question. On peut alors avancer ce point sur le rayon avec des pas qui sont égaux ou plus petits que l’estimation de la distance, et s’arrêter quand cette estimation devient inférieure à un petit nombre. Sur la figure à gauche, la distance entre le point $P$ et l’objet est indiquée par les sphères avec les positions successives de $P$ comme centre. Dans le cas de la figure, c’est une estimation conservative, donc plus petite que la vraie distance.

Si un rayon ne rencontre pas l’objet, on donne au pixel la couleur du fond de l’image.

Un kaléidoscope sur un polyèdre 3D

On peut paver une sphère avec des triangles sphériques d’angles $\pi/2$, $\pi/3$ et $\pi/4$. Si on prend un de ces triangles et si on prend itérativement les points symétriques du point bleu dans la figure de gauche par rapport aux trois plans qui passent par les côtés du triangle et le centre de la sphère, on obtient les six sommets d’un octaèdre.

Si on fait la même chose avec le point bleu de la figure de droite, on obtient les huit sommets d’un cube.

Si on imagine les trois plans comme des miroirs, on obtient un kaléidoscope...qui a donc des miroirs autour du triangle vert, qu’on appelle le triangle fondamental.

Il y a aussi une construction similaire pour le tétraèdre en prenant un triangle sphérique d’angles $\pi/2$, $\pi/3$ et $\pi/3$.

On peut aussi paver une sphère avec des triangles sphériques d’angles $\pi/2$, $\pi/3$ et $\pi/5$. Avec ce pavage, on peut construire les sommets du dodécaèdre et de l’icosaèdre, comme dans les figures de gauche et de droite.
Si on choisit la position du point ailleurs sur les côtés du triangle, on peut obtenir les sommets des solides d’Archimède, comme le ballon de foot ( icosaèdre tronqué) de gauche et le petit rhombicosidodécaèdre à droite.

Tout ceci donne une méthode pour dessiner tous ces polyèdres.

On choisit le triangle sphérique à utiliser (angles $\pi/2$ et $\pi/3$, et pour le troisième angle, $\pi/3$, $\pi/4$ ou $\pi/5$), ce qui donne les trois plans par les trois côtés. On choisit aussi un point dans le triangle qui va devenir un sommet du polyèdre.

On prend un point sur un rayon. On fait subir à ce point une série de réflexions dans les trois plans, jusqu’à ce que le point transformé se trouve dans la zone pyramidale entre les trois plans.

Puis on calcule la distance de ce point vers un sommet, une arête et une face (on donne une certaine épaisseur aux arêtes et sommets). On peut alors avancer le point original sur le rayon de la plus petite de ces trois distances, pour obtenir un dessin comme dans la figure à droite.

Comment faire ça en détails ?

On a un point $\vec P$ avec coordonnées $(x,y,z)$ sur le rayon. On identifie les trois plans par leur normales $\vec N_1,\vec N_2$ et $\vec N_3$, dirigés vers l’intérieure du triangle. On calcule le produit scalaire $a=\vec P \cdot \vec N_i$ pour les trois normales. Si $a$ est négatif on transforme $\vec P$ en $\vec P'=\vec P-2a\vec N_i$, et on répète jusqu’à ce que $a$ soit positif pour les trois normales.

On cherche d’abord les trois sommets du triangle sphérique. On les trouve par les produits vectoriels : $\vec S_1=\vec N_2\times\vec N_3$, $\vec S_2=\vec N_3\times\vec N_1$, $\vec S_3=\vec N_1\times\vec N_2$, On se donne alors trois paramètres $u, v, w$ avec $u+v+w=1$ et on définit le point $\vec S'=u\vec S_1+v\vec S_2+w\vec S_3$, qu’on normalise en $\vec S=\vec S'/|S'|$.

$S$ sera le sommet du polyèdre et les trois arêtes par $S$ sont des segments qui partent de $S$ selon les trois vecteurs $N_i$. Les trois faces au sommet $S$ sont des plans par $\vec S$, perpendiculaires sur les vecteurs $\vec S_i$,

On a le point $\vec P'$ que se trouve « à l’intérieur » des trois plans avec normales $N_i$.

La distance vers le sommet est $d_s=|\vec P'-\vec S|$. Si on veut montrer les sommets comme des petites sphères de rayon $R_s$, on calcule $d_s=|\vec P'-\vec S|-R_s$

Pour les distances vers les arêtes on prend d’abord la projection orthogonale de $\vec P'$ sur une droite par $\vec S$ selon une normale $\vec N_i$, donc $\vec M_i=\vec P'-(\vec P' \cdot \vec N_i)\vec N_i$. A condition que le produit scalaire $\vec P' \cdot \vec N_i$ soit positif, la distance vers l’arête est alors $d_{ai}=|\vec P'-\vec M_i|$. On retient le plus petit des trois. Si on veut montrer les arêtes comme des cylindres de rayon $R_a$, on calcule $d_{ai}=|\vec P'-\vec M_i|-R_a$.

Pour les distances vers les faces, on calcule d’abord les trois produits scalaires $a_i=\vec S \cdot \vec S_i$. Les distances vers les faces sont alors $d_{fi} =\vec P' \cdot \vec S_i-a_i$ et on retient le plus grand.

On prend le plus petit de $d_s$, $d_a$ et $d_f$, et on peut avancer le point $P$ sur le rayon avec cette distance. On s’arrête quand la distance est plus petit qu’on nombre petit à choisir, ou si le point $P$ s’éloigne trop loin sur le rayon ce qui veut dire que le rayon ne coupe pas le polyèdre.. Pour déterminer la normale sur la surface,on tire aux moins deux autres rayons très proches du rayon original pour trouver deux autres points d’intersection. On déduit la normale du produit vectoriel de ces trois points.

C’est donc une méthode pour dessiner des polyèdres qui n’exige pas qu’on connaisse les coordonnées des sommets, ni les paires de sommets à relier pour obtenir les arêtes. Tout ce qu’il faut, c’est savoir quel triangle sphérique il faut choisir, et quel point dans ce triangle servira comme sommet.

Les symétries des polyèdres contiennent tout ce qui est nécessaire ! Des réflexions engendrées par trois plans bien choisis engendrent tous les polyèdres. Ces réflexions forment un groupe de Coxeter.

Essayons donc de faire quelque chose d’analogue pour les polyèdres de l’espace de dimension 4.

Un kaléidoscope en quatre dimensions

On doit maintenant s’occuper de la sphère $S^3$ à trois dimensions. Au lieu du triangle sphérique fondamental, on aura maintenant un tétraèdre fondamental dont les quatre sommets se trouvent sur la sphère. Au lieu de trois plans de symétrie, on en aura quatre !

Le triangle fondamental sur la sphère $S^2$ avait comme angles $\pi/2$, $\pi/3$ et $\pi/n$, avec $n$ égal à 3, 4 ou 5. Pour le polyèdre en dimension 4, les angles entre les plans du tétraèdre doivent être $\pi/2$, $\pi/3$, $\pi/3$ et $\pi/n$, encore avec $n$ égal à 3, 4 ou 5.

Pour construire un tel tétraèdre, on détermine les normales sur les quatre plans en se basant sur les angles entre les plans. Les sommets du tétraèdre sont calculés par les produits vectoriels de ces normales. Il ne faut pas oublier qu’on se trouve en dimension 4, donc les « produits vectoriels » réclament trois vecteurs !

Le tétraèdre fondamental en détail

La première chose à faire c’est de déterminer les quatre plans $a, b, c, d$ qui seront les faces de ce polyèdre fondamental. Pour les angles, on sait que $\widehat {ab}=pi/2$, $\widehat {ac}=pi/n$, $\widehat {ad}=pi/2$, $\widehat {bc}=pi/3$, $\widehat {bd}=pi/3$, $\widehat {cd}=pi/2$. Choisissons $\vec N_a=(1,0,0,0)$ et $\vec N_b=(0,1,0,0)$ comme normales sur $a$ et $b$.

Comme $\widehat {ac}=pi/n$ et $\widehat {bc}=pi/3$ on a que $\vec N_c=(-\cos(\pi/n),-1/2,N_cz,N_cw)$.

Comme $\widehat {ad}=pi/2$ et $\widehat {bd}=pi/3$ on a que $\vec N_d=(0,-1/2,N_dz,N_dw)$.

Il nous reste la condition que $\widehat {cd}=pi/2$, et évidemment que les vecteurs doivent être des vecteurs d’unité. On peut alors choisir un des inconnus comme on veut. Prenons $N_dw=0$, ce qui mène à $\vec N_c=(-cos(pi/n),-1/2,-1/2\sqrt{3},\sqrt{2/3-\cos(\pi/n)^2})$ et $\vec N_d=(0,-1/2,\sqrt{3}/2,0)$.

Les sommets du tétraèdre sont donnés par les produits vectoriels : $\vec S_a=\vec N_b \times \vec N_c \times \vec N_d$, $\vec S_b=\vec N_c \times \vec N_d \times \vec N_a$, $\vec S_c=\vec N_d \times \vec N_a \times \vec N_b$, $\vec S_d=\vec N_a \times \vec N_b \times \vec N_c$.

Pour en savoir plus sur le produit vectoriel en quatre dimensions, voir ce lien (en Anglais)

On va dessiner la projection stéréographique d’un polyèdre 4D, et on va lancer des rayons vers cette projection. Cette fois-ci, on ne va dessiner que les sommets et les arêtes, car si on dessine les faces aussi, on va cacher une bonne partie de la géométrie de l’objet.

On prend un rayon et on avance un point $P$ partant de la caméra. Pour calculer la distance du point vers les sommets et les arêtes, on va devoir se déplacer dans l’espace de dimension 4 : on calcule la position de la projection stéreographique inverse du point $P$, ce qui donne un point $P'$ sur $S^3$.

La première chose à faire alors est de mettre en marche le kaléidoscope : transformer le point par des réflexions par les quatre plans, jusqu’à ce que le point se trouve « à l’intérieur » du tétraèdre fondamental.

On choisit un point $S$ à l’intérieur du tétraèdre qui sera un sommet du polyèdre que nous voulons dessiner, et on va déteminer la distance entre le point $P'$, transformé par les réflexions, et ce point $S$, mais aussi la distance de $P'$ vers les arêtes qui partent de $S$.

Comment faire ça en détail ?

On a un point $\vec P$ avec coordonnées $(x,y,z)$ sur le rayon. Le point correspondant sur $S^3$ est $P' (\frac{2x'}{1+R^2,},\frac{2y'}{1+R^2},\frac{2z'}{1+R^2},\frac{1-R^2}{1+R^2})$, avec $R^2=x'^2+y'^2+z'^2$.

On calcule le produit scalaire $a=\vec P \cdot \vec N_i$ pour les quatre normales. Si $a$ est négatif on transforme $\vec P$ en $\vec P'=\vec P-2a\vec N_i$, et on répète jusqu’à ce que $a$ est positif pour les quatre normales.

On se donne quatre paramètres $u, v, m, t$ avec $u+v+m+t=1$ et on définit le point $\vec S'=u\vec S_1+v\vec S_2+m\vec S_3+t\vec S_4$, avec $S_i$ les quatre sommets du tétraèdre fondamental. On normalise $\vec S$ en $\vec S=\vec S'/|S'|$.

On a le point $\vec P'$ qui se trouve « à l’intérieur » des quatre plans avec normales $N_i$.

La distance vers le sommet est $d_s=\arccos{(\vec P' \cdot \vec S)}-R_s$, avec $R_s$ le rayon d’une petite sphère qui représentera les sommets, exprimé en radiales.

Pour les distances vers les arêtes on prend d’abord la projection orthogonale de $\vec P'$ sur un plan déterminé par $\vec S$ et une normale $\vec N_i$.

Pour trouver ce point $\vec A$, on calcule d’abord $s=\vec P' \cdot \vec S$, $n=\vec P' \cdot \vec N_i$, $k=\vec N_i \cdot \vec S$.
Puis $f=s-kn$, $g=n-ks$. À condition que $g$ est négatif, le point $\vec A$ est alors $\vec A=f\vec S+g\vec N_i$, qu’on normalise pour le mettre sur $S^3$. Si $g$ est positif on ignore ce point et on passe à la prochaine $N_i$.

La distance vers l’arête est alors $d_{ai}=\arccos{(\vec P' \cdot \vec A)}-R_s$. On retient le plus petit.

On prend le plus petit de $d_s$ et $d_a$, qui sont tous les deux des angles.

On va exprimer ces distances comme des angles. Par exemple, la distance entre $P'$ et $S$ suit du produit scalaire entre les deux : $\cos{(d_s)}=\vec P' \cdot \vec S$. [6]

Les arêtes se trouvent sur $S^3$ dans des plans par les vecteurs $\vec S$ et $\vec N_i$ avec $i=a, b, c, d$. Trouver la distance du point $P'$ vers les arêtes, est un peu plus compliqué, mais on arrive à des distances $d_a$ vers les arêtes qui prennent en compte une certaine épaisseur des arêtes.

La distance qui nous intéresse est donc la plus petite des distances $d_s$ et $d_a$, appelons-là $d_{min}$. Si on avance notre point $P$ sur notre rayon en 3D d’une distance $d$, pour arriver à un point $Z$, alors l’angle sur $S^3$ entre les points correspondants $P'$ et $Z'$, doit être égal ou inférieur à $d_{min}$.

Cela nous donne une équation quadratique en $d$ et des deux solutions, on prend celle qui est positive, afin de ne pas faire marche arrière sur notre rayon. Si l’équation n’a pas de solution réelle, on ne va pas rencontrer des sommets ou arêtes et on peut donc passer au prochain pixel de l’image.

La figure à gauche montre l’analogue en 3D : La projection inverse d’un rayon est un cercle (jaune) qui passe par le pôle Nord, le centre de projection. Le cercle vert sur la sphère montre une distance autour du point $P'$, et ce cercle coupe le cercle jaune en deux points, les deux solutions de l’équation.

Si le rayon passe par une arête ou un sommet, l’équation va nous donner la distance exacte à parcourir, ce qui veut dire que l’algorithme est très rapide : il ne faut pas faire un grand nombre de pas pour en finir avec le calcul d’un rayon. Les images qui vont suivre ont été calculées en quelques secondes. [7]

Avec le choix qu’on a fait pour les normales sur les quatre faces du tétraèdre fondamental, un des sommets du tétraèdre sera $\vec S_i=(0, 0, 0, 1)$ ce qui est le pôle de projection. La conséquence, c’est qu’on obtient facilement des polyèdres dont un sommet ou une arête passe à l’infinie par la projection stéréographique. La solution est alors de faire subir au point $ P'$ su $S^3$ des rotations en quatre dimensions pour obtenir un polyèdre bien positionné en 3D.

Dessiner un hécatonicosachore

Voici quelques résultats. Prenons d’abord le tétraèdre fondamental où un des angles est $\pi/5$, et avec le point $\vec S$ à un sommet bien choisi : on obtient bien le 120-cellules :

Le même tétraèdre, mais le point $\vec S$ sur un autre sommet nous donne le 600-cellules :

Encore le même tétraèdre, encore un autre sommet, produit un polyèdre irrégulier, c’est-à-dire que pas tous les cellules sont identiques.

Si on choisit un point sur une arête du tétraèdre, on peut obtenir un ballon de foot 4D :

Un autre point sur une arête :

Avec un tétraèdre où un des angles est $\pi/4$, on obtient entre autres l’hypercube et le 24-cellules :

Avec la même méthode, on peut aussi dessiner des pavages d’un espace hyperbolique, comme le montre l’image en dessous, faite dans le logiciel Fragmentarium. [8]

Pour l’espace hyperbolique on fait une projection stéréographique sur une hyperboloïde en quatre dimensions, qui vit dans un espace de Minkowski. C’est un peu plus compliqué, mais la même méthode réussit toujours à engendrer des images comme celle en dessous. [9]

P.S. :

La rédaction d’Images des maths et l’auteur remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Serge Cantat,
Yannick Danard et
gammella.

Notes

[1Voir cet article pour une autre vue sur le « 120 ».

[2C’est Abdelaziz Nait Merzouk (Algérie) qui a publié le code de cette méthode sur Fractalforums. Il a écrit le code pour Fragmentarium, un logiciel ultra-rapide (et gratuit !) par Mikael Hvidtfeldt Christensen, qui utilise les processeurs de la carte graphique

[3Pour une comparaison des deux méthodes, voir chapitre 3 et 4 du film Dimensions.

[4La projection inverse, d’un point 3D $(x',y',z')$ vers un point de $S^3$ est donnée par $(\frac{2x'}{1+R^2,},\frac{2y'}{1+R^2},\frac{2z'}{1+R^2},\frac{1-R^2}{1+R^2})$, avec $R^2=x'^2+y'^2+z'^2$.

[5Pour le lancer de rayon sur des objets fractals, on peut aussi voir cet article.

[6Comme on veut montrer les sommets comme des petites sphères de rayon $R_s$, on va calculer la distance $d_s=\arccos{(\vec P' \cdot \vec S)}-R_s$.

[7Sur un ordinateur à 4 coeurs avec l’algorithme réalisé en Ultrafractal.

[8Avec le code de Knighty alias Abdelaziz Nait Merzouk.

[9Réalisée en Ultrafractal.

Affiliation de l'auteur

Soyez le premier à déposer un commentaire

Pour citer cet article : Jos Leys, « Comment dessiner un hécatonicosachore ? »Images des Mathématiques, CNRS, 2012.

En ligne, URL : http://images.math.cnrs.fr/Comment-dessiner-un.html

Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :