TD 1 - Surfaces de subdivision

TriangulationDS_2

Maintenant on va se familiariser avec une autre structure de données pour les maillages. En particulier, le but de cette partie est de vous illustrer le fonctionnement de la classe TriangulationDS_2, permettant de représenter des triangulations planaires et des maillages surfaciques 3D triangulés. Du point de vue combinatoire, on a vu en amphi qu'une surface combinatoire de genre 0 correspond à un graphe planaire: c'est aussi pour cette raison que la classe TriangulationDS_2 est une classe générique, parametrée par le type de point qu'on veut associer au sommet du maillage.

Ainsi, si on veut représenter un maillage 3D surfacique on aura:

TriangulationDS_2<Point_3>

Alors que si on veut coder une triangulation planaire, on écrira:

TriangulationDS_2<Point_2>

Schema de subdivision: Loop subdivision

Ici on vous demande d'implanter le schéma de subdivion connu sous le nom de "Loop subdivision".
Vous pouvez trouver plus de détails concernant la description du schéma de subdivision, ainsi qu'un esquisse de la solution ici.

Important: avant de commencer, vous devez télécharger le squelette LoopSubdivision.java d'un programme java contenant un certain nombre de fonctions dont vous aurez besoin, pour lire des données, ainsi que pour manipuler/créer un maillage triangulaire. Vous y trouverez aussi des fonctions pour tester le résultat.

Il ne vous reste qu'à compléter le squelette ci-dessus, étape par étape, en tenant compte des suggestions fournies par les transparents.

Important: le maillage d'origine ne doit pas etre modifié. Le résultat de votre programme doit etre un nouveau maillage (aucune information n'est partagée avec l'ancien)

calcul des nouveaux points (associés aux aretes)
calcul de la nouvelle position des points déjà existants
calcul des nouvelles relations d'incidence faces/sommets
création du maillage subdivisé (à partir de l'ensemble des nouveaux sommets, et des nouvelles relations d'incidence faces/sommets)

Ce qui vous est demandé

But: écrire un programme qui permet de subdiviser une triangulation donnée.
Entrée du programme: un maillage triangulé sans bord (de genre arbitraire), codé sous forme de fichier OFF.
Sortie du programme: un maillage triangulé, codé sous forme de TriangulationDS_2. Pour gagner du temps et de l'énérgie, on pourra se servir des fonctions déjà fournies par la librairie Jcg.
Notamment, il est possible de construire une TriangulationDS_2 à partir de la suite des points (géométriques), ainsi que des relations d'incidence faces/sommets.