shade.ca
Games
Art
Coding
Beauty Contest
Reviews
Spoofs
Corporate site
Webcams
Links




Tell Me the Truth

Hacky the raccoon
Shade.ca Web Design

3D Molecule representation (C++)

SouthPark Slot Machine

Random Review
Random Review



Join our mailing list!   Tell a friend about this site!

3DMOL - Les mathématiques

Les mathématiques derrière le projet

Formules employées pour passer des coordonnées en 3D aux coordonnées en 2D

    Avant de commencer, rappelons que la caméra pointe dans la direction de l'axe des Z et que les points à afficher seront devant celle-ci. Nous allons voir où les points seraient projetés sur le plan servant d'écran de projection. La formule que nous allons trouver ne tiendra pas compte des dimensions de l'écran, nous allons nous en occuper plus tard au moment de voir quels points seront dans le champ de vision de la caméra.

    La caméra est une sorte de pyramide à base rectangulaire, dont le sommet touche à l'origine (0,0,0) et la base sert d'écran de projection pour l'univers en 3D. Ce que l'utilisateur verra sera l'image de ce monde 3D sur cette base rectangulaire. La longueur focale de la caméra est la distance entre l'origine (0,0,0) et le plan comprenant la base de la pyramide.


(représentation 2, l'écran de projection)

    Sur ce graphique, la pyramide verte est la caméra avec son écran de projection, le segment de droite mauve est un objet en 3D à projeter sur l'écran en 2D et les droites bleues sont les droites qui vont nous aider à trouver les points de percée sur l'écran de projection.

        soit le plan écran PI(e): Ax + By + Cz + D = 0

        soit le point en 3D que nous allons transformer en 2D : P(x1,y1,z1)



Plan servant d'écran

    Habituellement, le vecteur normal à un plan n'a pas de grandeur spécifique, mais pour cette fois, nous avons assigné une grandeur (soit celle de la longueur focale) au vecteur N , vecteur normal au plan PI(e). Pour simplifier les expressions, disons que N est la grandeur du vecteur N (et la valeur de la longueur focale en même temps).

    N=(0,0,N) puisque la caméra pointe parallèlement avec le vecteur k .

    Définissons maintenant mieux PI(e) avec N et le point (0,0,N) élément de PI(e) .

PI(e):
    0x + 0y + Nz + D =0
    0x + 0y + N*N + D = 0        en rentrant le point (0,0,N) dans l'équation
    D = - N*N


(formule 1, plan de la caméra)

    Il serait aussi juste de dire que l'équation du plan est z=N , mais il est plus facile de voir qu'il s'agit d'un plan sans cette simplification.



Droite perçant le plan

    Le vecteur directeur de la droite y passant par l'origine (0,0,0) et P(x1,y1,z1) sera le vecteur (x1-0,y1-0,z1-0).

    Soit la droite appelée y, passant par l'origine et P(x1,y1,z1) :
        x=x1*t + 0
        y=y1*t + 0
        z=z1*t + 0
    L'intersection de cette droite y, dont le vecteur directeur est (x1,y1,z1), avec le plan PI(e) sera définie par l'équation 0(x1*t) + 0(y1*t) + N(z1*t) - N*N=0

    Nous trouvons donc que t = (N*N)/(N*z1) = N/z1 quand y perce PI(e).

    En reprenant les formules de tout à l'heure, nous voyons que les coordonnées du point de percée de la droite y dans le plan PI(e) , endroit où sera la projection 2D de ce point, seront définies par :


(formule 2, points de percée)



Problème de l'écran d'ordinateur

    Il est bien pratique d'avoir enfin nos formules pour passer du monde 3D au monde 2D, mais sans les bonnes conversions pour les afficher sur l'écran d'ordinateur, elles ne serviront à rien. Un écran d'ordinateur est fait de façon à ce que la gauche de l'écran soit le zéro des x et que les x positifs aillent en croissant vers la droite. Le haut de l'écran est le zéro des y et les y croissent en descendant vers le bas de l'écran. Nous avons donc dû trouver certaines formules de conversion pour passer des points 2D sur l'écran imaginaire de notre caméra aux points concrets affichés sur l'écran cathodique. Ces formules sont des transformations linéaires de la formule 2 (voir ci-haut) et ont été vérifiées avec un peu d'expérimentation.

        soit P(x1,y1,z1) le point en 3D à afficher à l'écran d'ordinateur,
            P(xc,yc) le point où P(x1,y1,z1) sera une fois transformé,
            Sw la largeur de l'écran d'ordinateur,
            Sh la hauteur de l'écran d'ordinateur,
            N la longueur focale de la caméra,


(formules 3, coordonnées sur écran d'ordinateur)

    Quand vient le temps d'afficher ces points à l'écran, nous vérifions s'ils ne débordent pas de l'écran. Les écrans d'ordinateurs de nos jours fonctionnent très fréquemment en 800 pixels de largeur par 600 pixels de hauteur. Il suffit s'assurer que 0 < Xc < 800 et que 0 < Yc < 600 . Si un point ne répond pas à ces exigences, le logiciel l'ignore et ne l'affiche pas. De plus, si le z du point à afficher est inférieur à N, le point ne sera pas devant la caméra et n'aura donc pas à être affiché. Les points ne figurant pas sur l'écran ne ralentissent pas la machine avec des instructions d'affichage inutiles puisqu'ils sont rapidement ignorés par ces petits tests.



Formules de rotation en trois dimensions selon un axe

Quelques formules utilisées au cours de la démonstration suivante





Pourquoi des rotations en 2D

    Effectuer une rotation en 3D équivaut à en faire trois en 2D, soit une autour de chaque axe. Nous allons premièrement trouver comment en faire une autour de l'axe des z et ensuite il sera simple de l'adapter pour tous les autres axes. Il suffit de prendre les coordonnées en Y et Z pour faire une rotation autour de l'axe des X, de prendre les coordonnées en X et Z pour faire une rotation autour de l'axe des Y et de prendre les coordonnées en X et Y pour faire une rotation autour de l'axe des Z. Le fait que nous n'ayons aucunement besoin de l'angle initial formé par le point à faire tourner et l'origine nous donne beaucoup de liberté.



(représentation 3, rotation en 2D autour de l'axe des Z)




    Pour trouver la coordonnée " c " à partir de delta theta, a et b




(formule 4, première coordonnée après rotation)

    Pour trouver la coordonnée " d " à partir de delta theta, a et b




(formule 5, deuxième coordonnée après rotation)



Rotation en sens inverse

    Pour changer la direction de rotation des formules, nous pourrions effectuer une rotation de -Theta et transformer les formules (puisque cos et sin sont respectivement des fonctions paires et impaires) pour obtenir d'autres formules effectuant une rotation de sens inverse au sens habituel.



Formules spécifiques

    Encore une fois, répétons que les coordonnées initiales (a,b) seront composées de la paire de coordonnées pour lesquelles ne nous tournons pas autour de l'axe. Les voici donc, exprimées à l'aide des formules:


(formule 6, rotations autour des axes)

    Ces formules de rotation pourraient aussi être exprimées sous forme de matrices de transformation.


    Il serait donc possible de composer une matrice 3x3 effectuant toutes les rotations en multipliant les matrices de transformation par la gauche. Nous remarquons aussi que le déterminant de ces matrices est toujours 1, mais nous ignorons pour le moment ce que cela implique.



Tri des faces

    Lors de la création des solides, il était important de bien ordonner des points en ordre anti-horaire et nous allons maintenant voir pourquoi. Il est important de mentionner que nous n'avons pas trouvé ce petit truc nous-mêmes et que nous avons essayé quelques autres idées avant de demander à Jérôme St-Louis (auteur d'une page consultée pour réaliser notre projet) comment faire.



Algorithme

    Pour savoir si une face nous fait face, il suffit de faire le produit mixte de 3 vecteurs formés par 3 points consécutifs de cette face et l'origine. Comme mentionné précédemment, nous avons choisi de prendre un axe des z opposé à l'axe des z que l'on retrouverait normalement. Si le z avait été normal, la face nous ferait face si le volume (produit mixte) était positif, mais puisque z est dans l'autre sens dans notre logiciel, la face nous fait face si le produit mixte est négatif.


(formule 7, tri des faces cachées)


(représentation 4, tri des faces cachées)

    Nous utiliserons une pyramide à base triangulaire pour expliquer la théorie derrière cette formule. Les vecteurs v1, v2 et v3 touchent aux points de la base de la pyramide. Le produit scalaire de v1^v2 donne un vecteur pointant vers la droite dans la représentation. Si nous pouvons voir base de la pyramide, v3 n'aura pas le choix d'être en-dessous du plan comprenant v1 et v2 puisque les vecteurs sont en ordre anti-horaire. Le produit scalaire entre v1^v2 et v3 serait donc négatif. On appelle produit mixte un produit vectoriel suivi d'un produit scalaire. Un produit mixte s'exprime aussi comme le déterminant d'une matrice 3x3 formée des trois vecteurs en question. La face est donc cachée si le produit mixte est positif.



Note des auteurs - Introduction - Le logiciel
Les mathématiques derrière le projet - Discussion





Jason  
( 2001-05-23 )  




Lisez cet article en anglais




Back



Français - English