Introduction à la modélisation et

à l'algorithmique géométriques

Travaux pratiques avec Scilab

Vous trouverez les supports de cours regroupés sur une autre page.

La Modélisation et l'Algorithmique Géométriques (sur ordinateur) sont abordés ici à travers des exemples et exercices simples qui ne demandent pas de connaissances pointues en programmation (pour maitriser des langages comme C++ ou Java, ou des librairies comme CGAL). Le langage utilisé pour ces travaux pratiques est assez intuitif : il ne demande pas de typage et s'apparente au langage de Matlab. Il pourrait aussi être comparé à Python; certain TP sont d'ailleur proposés dans ce langage (notés avec *). Nous aborderons ici les 3 principales approches pour décrire une géométrie (Geometric Modeling) :

l'approche par les limites ou Brep (Boundary Representation) : les polygones en 2D, les polyèdres ou plus simplement les triangulations en 3D,
l'approche constructive ou CSG (Constructive Solid Geometry) qui est abordé ici avec l'arbre booléen de construction,
l'approche discrête avec les modèles d'énumération spatiale, illustré ici à travers un exemple de traitement d'image (ou de Morphologie Mathématique)

L'Algorithmique Géométrique (ou Computational Geometry, AG ou CG) est une discipline "récente" (~1980) qui traite les problèmes géométriques en 2D, 3D, nD, du point de vue des algorithmes et de leur complexité. Le problème du voyageur de commerce est un exemple très connu car sa complexité est non polynomiale. Il existe plusieurs librairies qui proposent des algorithmes optimum pour des problèmes type (enveloppes convexes, plus proches voisins, triangulations optimales...) comme par exemple la très belle librairie CGAL (pour les experts en C++). L'objectif ici est de proposer une introduction simple à travers quelques problèmes typiques. Il existe principalement 3 approches (déterministes) en Algorithmique Géométrique :

l'approche incrémentale (les données sont traitées les unes après les autres sans ordre particulier a priori),
l'approche par balayage (les données sont traitées les unes après les autres suivant une direction fixée),
l'approche diviser pour régner (les données sont traitées par petits paquets et les résultats partiels sont fusionnés récursivement).

Dans les travaux pratiques proposés ici nous n'aborderons que : les structures de recherche, les triangulations de Delaunay et de leur dual (les graphes de Voronoi)...

Un énoncé d'examen pour exemple ici.

Pour charger les données nécessaires à la réalisation des travaux pratiques, il suffit de suivre le lien correspondant au titre du TP.

1.Calculs géométriques de base :

Ce TP d'introduction vous propose une prise en main de Scilab à travers des exercices simples de géométrie 2D : la localisation de points, calcul de distance...

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Il contient aussi une demo (CORRIGE) qui presente les résultats à obtenir à chaque étape.

2. Polygones :

Ce TP (~2h) permet de se familiariser avec Scilab. Il propose de manipuler des polygones sous la forme de tableau de points (sommet-arete), de programmer quelques méthodes de base (calcul de l'aire, calcul de l'AABB) et d'utiliser l'algorithme de localisation d'un point dans un polygone (vu en cours). Ce dernier permettra d'estimer l'aire d'un polygone qui sera comparé au calcul exact...

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt la copie de la présentation, peut être téléchargé ici.

2.bis Sommes de Minkowski : gestion des obstacles pour un mobile

Ce TP (~2h) propose d'aborder un problème classique de la plannification de trajectoires. Il s'agit de calculer l'espace accessible à un mobile de forme donnée (ici une ellipse) en remplaçant ce dernier par un simple point.

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt la copie de la présentation, peut être téléchargé ici.

3*. Triangulation (affichage et parties cachées) :

Ce TP (~2h) propose de manipuler des triangulations dans le plan et dans l'espace et de programmer un algorithme simple de parties cachées pour afficher la géométrie. Le problème sera traité avec l'algorithme du peintre "simplifié" que l'on abordera par étapes successives :

la projection sur le plan image,
la suppression des faces "mal" orientées (le "back face culling"),
le tri des facettes suivant la distance à l'observateur,

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt la copie de la présentation, peut être téléchargé ici.

4*. Triangulation (rendu, "ombrage") :

Ce TP (~2h) est une extension du TP précédent. Il permettra de comprendre les modèles d'éclairage (shading) sur les triangulations :

Programmation du modèle d'éclairage diffus
Calcul des normales unitaires ("flat-shading")
Interpolation des normales (lissage de "Gouraud").

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt la copie de la présentation, peut être téléchargé ici.

Rendu et mapping de texture, analyse du format .obj sous Meshlab

Ce TP (~2h) devrait vous permettre de vous familiariser avec les triangulations et leurs attributs géométriques et graphiques sur l'exemple du format OBJ et leurs manipulations à l'aide du logiciel MeshLab.

Pour faire ce TP suivre le lien.

4.bis Frontières, triangulations et topologie (TP sur Meshlab) :

Ce TP (~2h) autour de la topologie (le support de cours est ici) devrait vous permettre de découvrir le logiciel MeshLab. Son utilisation est ici limitée à quelques manipulations élémentaires, entre autre à l'analyse des caractéristiques topologiques des maillages et à la corrections des "malformations" potentielles (simples). Entre autre :

D'analyse des caractéristiques topologiques des maillages, de localiser des "trous" et de les BOUCHER,
De NETTOYER un maillage, de localiser les arêtes et les sommets "non 2 manifold" et de les supprimer,
De générer des maillages représentant la même géométrie à différents niveau de détails (LOD) à l'aide d'outil de DECIMATION,
De COMPARER 2 maillages (représentant la même géométrie) pour localiser les défauts avec la distance de Hausdorff,
...

Pour faire ce TP suivre le lien.

5. Constructive Solid Geometry (CSG Tree)

Ce TP (~2h) vous permettra de définir et de manipuler des structures arborescentes à l'aide d'un algorithme de parcours récursif et de méthodes de calcul (PTdans, Plot). Les étapes du TP sont les suivantes :

Programation d'un algorithme de parcours recursif d'une "list" d'objets représentant une expression arithmétique,
Définition d'un CSG-Tree à l'aide de "list" contenant des operateurs, des transformation ou et ou des primitives (CSG-Tree)...
Estimation de l'aire d'une geometrie définie par un CSG 2D à l'aide d'un tirage aléatoire de points dans la boite d'encombrement du CSG,
Ajout d'une primitive "triangle" : définition des méthodes "Plot" et "PTdans" pour la nouvelle géoémtrie,
Ajout de la méthode "AABB" pour toutes les primitives (circle, box, triangle),
...

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt; la copie de la présentation, peut être téléchargé ici.

6. Enumération spatiale : traitement d'image et morphologie mathématique

Ce TP (~2h) propose de traiter une image (ci-contre) afin d'en extraire les informations pertinentes à l'aide de techniques de traitement d'images et de morphologie mathématique. Il se compose de plusieurs étapes :

Programmation d'une érosion et d'une dilatation en 8-connexité,
Nettoyage d'une image à l'aide d'opérateurs d'ouverture et ou de fermeture

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt; la copie de la présentation, peut être téléchargé ici.

7. KD Tree et structures de recherche :

Ce TP (~1h30) propose d'explorer la structure KD-Tree. Cette dernière est très utilisée en Algorithmique Géométrique (dans l'approche diviser pour régner) car elle est optimale (arbre de recherche est équilibré). Les principales étapes de ce TP sont les suivantes :

Analyse d'un KD-Tree sur un graphique
Construction "à la main" d'un KD-Tree sur des points fournis.
Programmation d'une requête boite (fonction récursive) sur le KD-Tree.

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt; la copie de la présentation, peut être téléchargé ici.

8*. Triangulation de Delaunay-Graphes de Voronoi :

Ce TP (~1h30) propose de se familiariser avec les structures de données utilisées pour représenter les triangulations, d'apprehender les propriétés des triangulations de Delaunay et de leur structure duale : les graphes de Voronoi. Le TP est constitué de plusieurs étapes :

Manipulation de la structure de données correspondant à une triangulation.
Analyse de la propriété de Delaunay.
Extraction de l'enveloppe convexe.
Programmation d'un algorithme de conversion vers un graphe de Voronoi.

Pour charger le sujet et les données du TP suivre ce lien (un fichier zip).

Le support de cours correspondant ou plutôt; la copie de la présentation, peut être téléchargé ici.

9. Lancé de rayon et modèle de réflexion :

Ce TP propose de programmer des modèles de reflexion dans le cas d'un algorithme de lancé de rayon. Les images générées seront celles d'une sphère vue avec une caméra "orthographique".

Intersection des "rayons" avec une sphère centrée.
Intégration d'un modèle de réflexion ambiante puis de réflexion diffuse.
Intégration d'un modèle de réflexion spéculaire.
Extension : Antialiasing par lissage puis par sur-échantillonnage.

Pour charger le sujet suivre ce lien.