Modélisation géométrique d'une scène

La conception d'une application graphique réprésentée en 3D se fait en plusieurs étapes

• choix des scènes devant être représentées,
• modélisation géométrique de ces scènes,
• choix et placement des textures, des matériaux et des lumières,

Vient ensuite l'étape de dessin via une interface ou en programmation.

On s'intéresse dans cette partie à la seconde étape (la modélisation) et comment celle-ci peut être mémorisée.

Dans ce qui suit, on se place dans l'espace euclidien $\mathbb{R}^3$ dans lequel on construit la base orthonormée directe $(O,i,j,k)$.

Dans ce qui suit on utilise les classes Image, ImageDraw du module PIL, et le module numpy comme suit :

   import Image, ImageDraw
   import numpy as np

Modélisation à base de triangles

Par la suite, un objet 3D est représenté par un ensemble de triangles. Chaque triangle est défini par trois segments et chaque segment est défini par deux sommets. Ceci est une version simplifiée du standard Gnu Triangulated Surface (GTS).

Le cube donné ci dessus serait codé par

  8 18 12
  #sommet
  0 0 1
  1 0 1
  0 0 0 
  1 0 0
  0 1 1
  1 1 1
  1 1 0
  0 1 0
  #segment
  1 2
  2 6
  6 5
  5 1
  2 4
  4 7
  7 6
  4 3
  3 8
  8 7
  3 1
  5 8
  1 6
  2 7
  4 8
  3 5
  5 7
  2 3
  #face
  5 6 14
  7 2 14
  8 9 15
  10 6 15
  12 9 16
  11 4 16
  3 7 17
  10 12 17
  8 5 18
  1 11 18
  1 2 13
  3 4 13

Dans ce fichier, la première ligne récapitule qu'il y a 8 sommets, 18 segments et 12 faces.

Travaux pratique : parseur de fichiers GTS

Construire une programme python qui prend en paramètre un fichier GTS et qui mémorise

• les triplets de coordonnées des sommets dans la liste sommets
• les paires d'indices des extrémités des segments dans la liste segments
• les triplets de d'indices de segment de triangles dans la liste triangles

Vérifier que votre parseur traite correctement les exemples de la page sur les GTS

Affichage en fils de fer d'un objet en 3D

On commence par construire l'image de taille 800*800. Pour information, le pixel dans le coin supérieur gauche a pour coordonnées $(0,0)$.

  im = Image.new('RGB',(800,800))

Puis on munit ce plan d'un repère orthonormé $(O,i,j)$ centré, où l'axe des abscisses va de $-\textit{maxI}$ à $+\textit{maxI}$. Ceci est défini par le code:

  class RepereOrtho:
    def __init__(self, im, maxI=5):
        self.centre_x = im.size[0]/2
        self.centre_y = im.size[1]/2
        self.draw = ImageDraw.Draw(im)
        self.unite = im.size[0]/(2*maxI)

    def pixel_correspondant (self,(x,y)):
        x1 = self.centre_x + self.unite*x
        y1 = self.centre_y - self.unite*y
        return (int(x1),int(y1))

où

• pixel_correspondant donne les coordonnées dans l'image du pixel correspondant au point d'abscisse $(x,y)$.
• draw servira à dessiner dans le repère

Méthode d'affichage

Quel que soit la méthode d'affichage, on doit passer d'un espace en 3D à un espace en 2D. La technique la plus simple consiste à projeter chaque triangle dans le plans $(O,i,j)$ selon l'axe des $z$. Ceci s'obtient en oubliant les coordonnées $z$ de chaque sommet. C'est le tableau xyp du code ci-dessous.

Afficher un objet en fils de fer, c'est afficher ses arrêtes et considérer chaque face comme transparente. Pour dessiner ensuite chaque segment du triangle, on récupère les indices de ses extrémités, on en déduit ses coordonnées via xyp et on le dessine via draw.line.

  class Obj3D:
    def __init__(self, f):
        gtsp = GTSParseur(f)
        self.sommets = gtsp.sommets
        self.segments = gtsp.segments
        self.triangles = gtsp.triangles

    def dessine_fil_de_fer(self,repere):
        xyp = [repere.pixel_correspondant((x,y)) for [x,y,_] in self.sommets]
        for t in self.triangles:
            for s in t :
                repere.draw.line([xyp[self.segments[s][0]],xyp[self.segments[s][1]]],"white")

Travaux pratiques : Affichage en fils de fer

Compléter le code précédent pour afficher tous les exemples GTS.

Déplacement des objets de la scène

On considère deux types de déplacement : les translations et les rotations qui sont modélisés par de simple calculs matriciels.

Translation

Dans $\mathbb{R}3$, le point $N(N_x,N_y,N_z)$ qui est l'image de $M(x,y,z)$ par la translation selon le vecteur $\vec{T} = (T_x,T_y,T_z)$ est

$ \left[ \begin{array}{l} N_x \\ N_y \\ N_z \end{array} \right]$ = $ \left[ \begin{array}{l} T_x + x \\ T_y + y \\ T_z + z \end{array} \right]$

Rotation autour des axes

Dans ce qui suit on se restreint aux rotations autour d'un des axes passant par l'origine. Dans ce cadre, une rotation est définie par un angle $\alpha$ et un axe :

$ R_{\alpha,x} = \left[ \begin{array}{3}1 & 0 & 0 \\ 0 & \cos( \alpha ) & -\sin \alpha) \\ 0 & \sin( \alpha ) & \cos ( \alpha) \end{array} \right]$,

 $R_{\alpha,y} = \left[ \begin{array}{3}\cos(\alpha) & 0 & \sin(\alpha)  \\ 0 & 1 & 0  \\ -\sin( \alpha ) & 0 &\cos ( \alpha)  \end{array} \right]$ 
 et $R_{\alpha,z} = \left[ \begin{array}{4} \cos(\alpha) & - \sin(\alpha) & 0  \\ \sin(\alpha) & \cos(\alpha) & 0  \\ 0 & 0 & 1  \end{array} \right]$. 

Le point $N(N_x,N_y,N_z)$ qui est l'image de $M(x,y,z)$ par la rotation $R_{\alpha,u}$ est obtenu grâce au produit matriciel suivant :

$ \left[ \begin{array}{1} N_x \\ N_y \\ N_z \end{array} \right] = R_{\alpha,u} \cdot\left[\begin{array}{1}x \\ y \\ z \end{array} \right]$.

Travaux pratiques

1. Implanter les rotations et translations données ci-dessus et les appliquer aux exemples GTSa
2. Le format GIF supporte les animations. La bibliothèque image2gif permet de générer ce genre d'animations. La fonction writeGif("fichier.gif",listeDimages) sauvegarde la liste d'images listeDimages dans le fichier fichier.gif. Enregistrer

dans un fichier gif une animation de rotation d'un objet 3D choisi.

Gestion des faces cachées

Algorithme du peintre

Le nom d'« algorithme du peintre » fait référence à un peintre qui dessinerait les parties lointaines d'une scène avant les parties proches (cf. wikipedia).

Par rapport à l'algorithme précédent, on ajoute les contraintes suivants

• on souhaite dessiner d'abord les triangles qui sont les plus éloignés de la caméra : on ordonne donc les triangles du plus loin au plus proche
• on attribue une couleur a chaque triangle : sombre pour un triangle éloigné, clair pour un triangle proche
• de dessiner non plus les arrêtes mais les triangles

Travaux pratiques : implantation de l'algorithme

Développer la méthode dessine_peintre de la classe Objet3D qui intègre ces contraintes.

Algorithme de F. Roberts

On considère dans cette partie que la scène ne contient qu'un polyèdre. Pour celui-ci il s'agit de savoir:

• quels polygones sont visibles car faces à nous et
• lesquels sont invisibles car masqués par les polygones face à nous.

Pour chaque polygone, l'idée de F. Roberts est la suivante : calculer le vecteur normal $\vec{n}$ extérieur au polyèdre. Calculer le produit scalaire $s$ du vecteur de vision (la caméra) par $\vec{n}$. Si $s$ est positif ou nul, le polygone est caché sinon il est visible. Cela peut être implanté comme suit:

    def dessineb(self,repere):
        A,B,C = self.sommets[0],self.sommets[1],self.sommets[2]
        AB = Vecteur(A,B)
        BC = Vecteur(B,C)
        n = AB.produit_vectoriel(BC)
        s = n.produit_scalaire(vision)
        if s <= 0 :
            xy = self.projete()
            xyp = [repere.pixel_correspondant(s) for s in xy]
            repere.draw.polygon(xyp,fill=self.remplissage,outline=self.bordure)

où

• $A$, $B$ et $C$ sont les trois premiers sommets du polyèdre
• N le vecteur normal extérieur au polyèdre
• vision est le vecteur de vision (par défaut $(0,0,-1)$)
• produit_vectoriel et produit_scalaire sont ...

Travaux pratiques

Compléter le code précédent pour afficher vos pyramides et votre cube en gérant les faces cachées.

Autre représentation : les quaternions

Introduction aux quaternions

On connaît l'interprétation géométrique de l'arithmétique des nombres complexes : un nombre complexe représente un point dans le plan. Les quaternions sont l'analogue dans l'espace à trois dimensions. D'un point de vue historique, ils ont été inventés par Rowan Hamilton en 1843.

Tout quaternion H peut être considéré comme une combinaison linéaire des quatre quaternions "unités" 1, $i$, $j$, et $k$ :

$ H = a \cdot 1 + b\cdot i + c\cdot j + d\cdot k $

où $a$, $b$, $c$ et $d$ sont des nombres réels:

• $a$ s'appelle la composante réelle de $H$,
• $b$, $c$ et $d$ sont les composantes complexes de $H$ et
• les imaginaires $i$, $j$ et $k$ ont la propriété $i^2 = j^2 = k^2 = ijk = -1$

Parfois, on note ce quaternion $(a,v)$ où $s$ est la composante réelle et $v$ est le vecteur définissant la composante complexe.

Opérations définies pour les quaternions

• conjugué d'un quaternion. Le conjugué d'un quaternion $(a,v)$ , que l'on note $H^*$ est défini par $H^* = (a,-v) = a - b\cdot i - c\cdot j - d\cdot k $. * produits de quaternions le produit des deux quaternions $q_1 = (a_1,v_1)$ et $ q_2 = (a_2,v_2)$ est défini par

$q_1\cdot q_2 = \left(a_1\cdot a_2-v_1 \bullet v_2, a_1\cdot v_2 + a_2 \cdot v_1 + v_1\wedge v_2 \right)$ où $\bullet$ représente le produit scalaire $\wedge$ représente le produit vectoriel.

Rotations et quaternions

Le principal intérêt pratique des quaternions est qu'ils expriment simplement les rotations dans l'espace tout en permettant des calculs plus simples d'image que la forme matricielle. En effet une rotation $R_{\alpha,u}$ est représenté par le quaternion

$ q_R = \cos \left( \frac{\alpha}{2} \right) + u_x \cdot \sin \left( \frac{\alpha}{2} \right)\cdot i + u_y \cdot \sin \left( \frac{\alpha}{2} \right) \cdot j + u_z \cdot \sin \left( \frac{\alpha}{2} \right) \cdot k $

On note aussi ce quaternion $\left(\cos \left( \frac{\alpha}{2} \right), \sin \left( \frac{\alpha}{2} \right) \cdot u \right)$

Étant donné un point $A$ de l'espace représenté par $\vec{OA} = (a_x \cdot i + a_y \cdot j + a_z \cdot k$, vu comme le quaternion $(0,(a_x,a_y,a_z))$ que l'on note $q_A$ par la suite. L'image par $R_{\alpha,u}$ de $\vec{0A}$ est donné par le produit de quaternion $q_R \cdot q_A \cdot q_R^*$

Librairie euclid

La librairie python euclid http://pyeuclid.googlecode.com/svn/trunk/euclid.py définit la classe Quaternion. Pour définir un quaternion correspondant à une rotation, on peut utiliser le constructeur new_rotate_axis(angle, axis)où

• angle est l'angle de la rotation
• axis est le vecteur de rotation

L'image du point $M(2,0,0)$ par la rotation d'angle $\pi/2$ selon le vecteur $(0, 0, 1)$ s'obtient en codant comme suit :

 OM = Vector3(2,0,0)
 OMP = Quaternion.new_rotate_axis(math.pi,OM)
 # quaternion unitaire qui représente OM ; OM = abs(OM).OMP
 q = Quaternion.new_rotate_axis(math.pi / 2, Vector3(0, 0, 1))
 qp = q.conjugated()
 print abs(OM),"*",(q*OMP)*qp

Ou directement comme cela

 q = Quaternion.new_rotate_axis(math.pi / 2, Vector3(0, 0, 1))
 OM = Vector3(2,0,0)
 print q*OM

Travaux pratiques

Exploiter la librairie python 'euclid' pour représenter la scène et les déplacement à l'aide quaternions.