Dans ce module, après des rappels mathématiques (espace vectoriel, espace affine, représentation matricielle, calcul projectif, etc.) sont étudiés quelques algorithmes fondamentaux en géométrie algorithmique appliqués à l'infographie tels que tracés (segments de droite, courbes de Bézier), intersections, localisations, géométrie convexe, plus court chemin, diagramme de Voronoï, triangulation de Delaunay.
En pratique, selon le langage de programmation retenu, on privilégiera des bibliothèques libres et portables telles que Xlib, GD (cette bibliothèque fournit des fonctions élémentaires et produit en sortie un fichier image, ce qui permet de développer des algorithmes en s'affranchissant des contraintes matérielles), SDL (Simple DirectMedia Layer) ou PIL (plus précisément Pillow, un fork de PIL, Python Imaging Library).
Transparents du cours
- rappels mathématiques
- tracé de lignes et de courbes planes
- algorithmes d'intersection
- recherche de chemins
- trangulation de polygones
Bibliographie (ouvrages sur lesquels sont basés les enseignements)
Sujets de T.P.
Les sujets sont indépendants des outils retenus, comme indiqué en introduction. Cependant, on utilisera de préférence le module CNG (Campus Naked Graphics) pour le langage Python, disponible en local en version 3.5. Pour information, cette bibliothèque est aussi disponible en C / C++ (et s'appuie sur OpenGL).
- TP 1 : passage de l'espace euclidien à l'espace écran
- TP 2 : tracé de segments de droite par Bresenham
- TP 3 : tracé de courbes par Bezier
- TP 4 : remplissage géométrique
Projets
- Projet : raycasting
- Projets des années antérieures : chemin