MIM Images
année 2003-2004
http://www710.univ-lyon1.fr/~jciehl/

TD1 - Algorithmes 2D

1. tracé de segment

Ecrivez une version de l'algorithme de Bresenham - point milieu. La fonction se limitera aux cas du tracé de gauche à droite (soit 4 octants au lieu des 8 possibles).

Le résultat sera soit :

affiché directement dans une fenêtre openGL à l'aide de GLUT. Chaque point pourra être affiché comme un rectangle de plusieurs pixels de coté afin de suivre le fonctionnement de l'algorithme. Modifier l'exemple du chapitre 1 du programming guide : minigl.c.
soit sauvé dans une image. Voici quelques fonctions pour lire/écrire des images TGA 24bits (non compréssées) et BMP 256 couleurs et 24 bits (non compréssées) libimg.tar.gz.

2. application au remplissage de triangle

Utilisez la fonction précédente afin de tracer un triangle 2D (les sommets seront définis dans le plan image). On supposera que les 3 sommets sont visibles.

Proposez un algorithme efficace de remplissage de triangle (idée : balayage de l'espace image et utilisation de cette progression régulière).

3. interpolation d'attributs définis sur les sommets (Gouraud Shading)

Modifiez le tracé de droite afin d'interpoler linéairement des attributs définis sur les extrémités du segment.

L'interpolation des attibuts sur la surface du triangle nécessite une interpolation bilinéaire. Les bords actifs de chaque ligne de balayage définissent la première interpolation. Dans l'exemple ci-dessous, les valeurs des attributs en ab et en ac sont nécessaires à l'interpolation d'un point de la ligne ab-ac.

Peut-on utiliser l'interpolation bilinéaire pour remplir n'importe quel polygone ? L'interpolation bilinéaire est-elle stable par rotation du polygone / triangle ?

4. remplissage d'une bande de triangles (triangle strip)

Afin de limiter le nombre d'opérations nécessaires au remplissage d'un ensemble de triangles, il est possible de ré-utiliser une partie des calculs effectués lors du remplissage du triangle précédent. Il suffit de fournir les sommets dans un ordre décrivant implicitement l'orientation du triangle et respectant la connexité des triangles, voir GL_TRIANGLE_STRIP ci-dessous :

(image issu du openGL 1.4 Programming Guide)

Les sommets v0, v1, v2 définissent le premier triangle. Le sommet v3 définit implicitement le triangle v2, v1, v3. Notez que l'orientation des sommets des triangles est conservée, ce qui permettra de déterminer la normale d'une surface décrite par un ensemble de bandes de triangles définis dans l'espace objet (cf. TD2, très certainement).

Question subsidiaire : restriction à une fenêtre (clipping)

Modifiez les fonctions précédentes afin de tracer et de remplir correctement des triangles partiellement visibles.

Question subsidiaire : subdivision de surface

L'algorithme de remplissage proposé ci-dessus reflète le fonctionnement d'opengGL, mais il existe d'autres méthodes. De manière générale, au lieu de convertir les primitives à afficher en listes de triangles de tailles quelconques, il est possible de subdiviser la primitive jusqu'à obtenir des éléments plus petits qu'un pixel que l'on peut très facilement afficher. Autre avantage de cette méthode, lorsque plusieurs primitives se projettent sur le même pixel, il est relativement simple de déterminer la couleur du pixel en tenant compte de la présence de toutes les primitives (application directe : anti-aliasing).

Pour les curieux, cet article compare la méthode d'affichage d'openGL avec celle de RenderMan (Pixar) qui utilise une méthode de subdivision.

Annexes : applications du tracé de droite discret

    extension à la 3D : algorithmes de suivi de rayons discrets (ray-shooting, ray-traversal, ray-casting, etc)

    parcours de structures accélératrices : octree, arbres de partition spatiale (BSP)
    visibilité (tampon de profondeur / Z-buffer)

    placage de textures contraint (Doom original, par exemple)
    la méthode générale du point milieu utilisé pour le tracé de droite est également capable de plaquer une texture sur la projection d'un triangle 3D quelconque.