M2 - Images

TP 3 : Transformations et
coordonnées homogènes






Rappels / Partie 1 : retour sur le pipeline graphique

    Le pipeline graphique d'openGL décrit toutes les transformations à l'aide de 2 matrices : MODELVIEW (M) et PROJECTION (P).
    Lorsque l'on fournit un sommet à openGL, sa position est transformée successivement par ces deux matrices.

    Exemple : un sommet v de coordonnées (x y z w)T est transformé / projetté par :

v'= M v
v"= P v'
c'est à dire v"= P (M v)

    La matrice M est la composition de toutes les transformations fournies à travers mat44/gl Rotate, mat44/gl Translate, mat44/gl Scale.
    La matrice P est, en général, le résultat de mat44/glu Perspective ou de mat44/gl Frustum.
    Quelle transformation réalise la matrice P ?

    Pourquoi 4 coordonnées pour décrire un sommet 3D ? Quel point de l'espace 3D correspond au point homogène (x y z w)T ?

    Comment déterminer si un point est visible par la caméra ? Comment déterminer les coordonnées des sommets de la pyramide de vision (dans le repère de la scène) ?

    Qu'est ce qu'une caméra pour openGL / un pipeline graphique ? Comment représenter une projection perspective ? une projection orthographique 2D ?

    Les détails sont disponibles par exemple dans openGL specification, chapitres 2.11 et 2.12.
    Les détails sur les constructions des différentes matrices sont dans openGL Programming Guide, chapitre 4.

Rappel / Partie 2 : remplir un triangle 2D

    L'étape suivante du pipeline, après avoir transformé les coordonnées des sommets des triangles à afficher, consiste à afficher le triangle à l'écran. Que se passe-t-il lorsque le triangle "dépasse" de l'écran ? (autre question: dans quel espace ou repère sont tranformés les coordonnées des sommets ?)

    Il y a deux types de solutions :
  1. soit calculer l'intersection du triangle avec la pyramide de vision et afficher le polygone résultat.
    Quel est le nombre maximal de sommets de ce polygone ?
    Pourquoi, ou dans quel cas, obtient-on un polygone alors que l'on souhaitait afficher un triangle ??
    Comment découper un polygone en triangles ? (indice : le polygone devrait être convexe, il y a une solution très simple dans ce cas)

  2. soit projetter l'écran sur le plan portant le triangle.
    Ou se trouve le plan image (l'  "écran") ? Dans quel espace / repère travailler ?
    Une solution pour projetter l'écran sur le plan portant le triangle, consiste à tester si un pixel de l'écran se projette dans le triangle. Une solution élégante consiste à calculer les coordonnées barycentriques du pixel dans le triangle et à n'afficher que les pixels effectivement à l'intérieur du triangle.

Rappel : coordonnées barycentriques,

Un point p du plan peut s'exprimer sous la forme : p= alpha * a + beta * b + gamma * c, avec a, b, c trois points du plan définissant un triangle A.


avec :
alpha= Aa / A
beta= Ab / A
gamma = Ac / A
et alpha + beta + gamma = 1
l'aire d'un triangle est simplement la norme du produit vectoriel de 2 aretes : A = ac x ab

donc le point p appartient au triangle A (abc) si  alpha + beta + gamma = 1,
et cette condition n'est vérifiée que si les triangles Ac (abp), Aa (bcp) et Ab (cap) sont orientés de la même manière que le triangle A (abc),
ou encore, p se trouve à gauche des 3 aretes du triangle A.

    Les détails sont disponibles par exemple dans openGL specification, chapitre 3.5.1

    La fonction triangle_display de sdlkit du TP1 utilise ce principe directement.


Partie 3 : extension à la 3D

    L'objectif du tp est de programmer la version 3D de l'idée précédente. La méthode est décrite dans l'article :
    On peut étendre directement l'idée de l'algorithme 2D en travaillant sur des tetrahèdres définis par 3 points et l'origine.
    L'autre solution, décrite dans l'article, repose sur une construction différente mais le test est équivalent. Le calcul de l'aire signée des triangles permet de vérifier que le point p se trouve à l'intérieur de chaque arete (lorsque l'aire est positive). Par exemple, l'aire du triangle abp sera positive si p se trouve à gauche de l'arete ab. Si le point p se trouve à gauche des 3 aretes, il est à l'intérieur du triangle. Dans l'article, ce test est remplacé par un produit scalaire avec la normale à l'arète, ce qui permet aussi de déterminer de quel coté se trouve le point p.
  
    Q1: lisez attentivement les sections 1, 2, 2.1, 2.2, et 4 (la partie sur la page 5)
    Q2: que représentent E0 E1 et E2 pour un triangle ?
    Q3: comment déterminer si le pixel (x, y) se projette dans le triangle ?
    Q4: comment remplir le triangle (avec une couleur uniforme pour l'instant)
    Q5: écrivez la fonction de remplissage d'un triangle.
        Dans un premier temps, on se contentera de parcourir tous les pixels de l'écran pour tracer un triangle.

       Vous n'utiliserez, bien sur, que les fonctions fournies par mat44.h et vec.h pour les calculs (y compris la gestion de la camera) ainsi que point_display() pour l'affichage (cf. sdlkit du TP1).


    Les annexes proposent une "sélection" de rappels sur les matrices, déterminants et adjoints.

Partie 4 : interpolation d'attributs

    Un attribut est une valeur associée à un sommet : sa couleur, sa normale, ses coordonnées de textures, etc. et surtout sa profondeur. Comment connaître la profondeur de chaque pixel appartenant au triangle ? Encore une fois, une solution élégante consiste à utiliser les coordonnées barycentriques calculées pendant le remplissage du triangle pour déterminer les coefficients de l'interpolation.

    Q1: calculer l'interpolation de la profondeur de chaque pixel pendant le remplissage du triangle.

    Q2: écrivez l'algorithme récursif permettant de ne tester que le minimum de pixels de l'écran.
        Mesurez les gains entre la méthode naive et celle-ci.
   
    Question subsdiaire : interpolez également les couleurs des sommets.
    Question subsidiaire : comment tracer plusieurs triangles en même temps sur un processeur multi-coeur ?


Partie 5 : élimination des parties cachées

    Comment afficher un ensemble de triangles correctement (c'est à dire en tenant compte de leur visibilité) ?

    Q1: écrivez une fonction utilisant les idées du Z-buffer permettant d'afficher un ensemble de triangles.

    Question subsidiaire : optimisez votre fonction en utilisant une représentation hiérarchique du Z-buffer.



Annexes : réferences

comment remplir un triangle sans le projetter sur le plan image :
pour plus tard :
quelques remarques sur l'interpolation des attributs de sommets (profondeur, couleur, normale, etc.) :
pour comprendre la section 2 : "equation setup" et "edge equations"
autre méthode de remplissage de triangles basée sur la même idée :

Annexes : tranformations

exemple de transformations : transform.c transform.h

#include "vec.h"
#include "mat44.h"

float modelview_matrix[16];
float projection_matrix[16];
float viewport_matrix[16];

float projection_near= 1.f;
float projection_far= 100.f;

void transform_init(void)
{
    mat44_identity(modelview_matrix);
    mat44_identity(projection_matrix);
    mat44_identity(viewport_matrix);
    projection_near= 1.f;
    projection_far= 100.f;
}

/* definition des transformations "standards"
 */

/* matrice modelview */
void set_modelview(const float *M)
{
    mat44_copy(modelview_matrix, M);
}

/* matrice projection (perspective) */
void set_perspective(const float fovy, const float aspect,
    const float near, const float far)
{
    mat44_perspective(projection_matrix, fovy, aspect, near, far);
    projection_near= near;
    projection_far= far;
}

/* matrice projection (ortho 2D) A FINIR */
void set_ortho(const float left, const float right, const float bottom, const float top,
    const float near, const float far)
{
    // TODO
    projection_near= near;
    projection_far= far;
}

/* matrice viewport : passage du repere homogene de la camera vers "les coordonnées fenetre" */
void set_viewport(const int _x, const int _y, const int _w, const int _h)
{
    float x= (float) _x;
    float y= (float) _y;
    float w= (float) _w;
    float h= (float) _h;
   
    mat44_identity(viewport_matrix);
   
    M44(viewport_matrix, 0, 0)= .5f * w;
    M44(viewport_matrix, 0, 3)= x + .5f * w;
    M44(viewport_matrix, 1, 1)= .5f * h;
    M44(viewport_matrix, 1, 3)= y + .5f * h;
    M44(viewport_matrix, 2, 2)= .5f;
    M44(viewport_matrix, 2, 3)= .5f;
    M44(viewport_matrix, 3, 3)= 1.f;
}

/* transforme un point
 */
void transform_4fv(const float *v, float *tv)
{
    VEC ve;

    mat44_mul_vec(ve, modelview_matrix, v);
    mat44_mul_vec(tv, projection_matrix, ve);
}

void perspective_divide(float *v)
{
    vec4_const_mul(v, 1.f / v[3], v);
}

void viewport_transform(const float *v, float *tv)
{
    mat44_mul_vec(tv, viewport_matrix, v);
}

/* determine la visibilite d'un point
    renvoie 0 si le point n'est pas visible
 */
int clip_4fv(const float *v)
{
    return ((-v[3] < v[0]) && (v[0] < v[3])
        && (-v[3] < v[1]) && (v[1] < v[3])
        && (-v[3] < v[2]) && (v[2] < v[3]));
}


exemple d'utilisation pour placer une camera et choisir une perspective :

    /* deplace la camera */
    float M[16];

#if 1
    /* construit une rotation et une translation
     */
    float T[16];

    mat44_identity(M);
   
    mat44_rotate(T,
        camera_rotation, 0.f, 1.f, 0.f); // rotation autour de Y
    mat44_compose(M, T);

    mat44_translate(T,
        camera_position[0], camera_position[1], camera_position[2]);
    mat44_compose(M, T);

#else
    /* utilise mat44_lookat
     */
    VEC center, up;

    vec4_init(center, 0.f, 0.f, -1.f, 1.f);
    vec4_init(up, 0.f, 1.f, 0.f, 0.f);
   
    mat44_lookat(M, camera_position, center, up);
#endif

    /* fixe la matrice modelview */
    set_modelview(M);
   
    /* fixe le viewport */
    int w, h;
    sdlkit_get_size(&w, &h);
    set_viewport(0, 0, w, h);
   
    /* definit une projection perspective */
    set_perspective(90.f, (float) w / (float) h, 1.f, 100.f);
   

exemple de transformation d'un sommet :

    VEC t, a, ta;

    vec4_init(a, -2.f, -2.f, -15., 1.f);
    transform_4fv(a, t);
    if(clip_4fv(t))
    {
        clip++; // le point est visible
        viewport_transform(t, at);
        // retrouve les coordonnees reeles du point pour l'afficher
        point_display( at[0] / at[3], at[1] / at[3]);
    }