TD9 - Surfaces de subdivision

L'objectif de ce TP est d'implémenter le schéma de subdivision de Loop ("Smooth Subdivision Surfaces Based on Triangles", 1987). Ce schéma ne s'applique qu'aux maillages triangulaires ; il subdivise chaque triangle en quatre. Il s'agit d'un schéma approximant qui converge vers une surface lisse de continuité $C^2$.

Téléchargez et compilez cette nouvelle base de code : mds3d_td9.zip. La classe Mesh a été modifiée pour utiliser la structure en demi-arête (half-edge) implémentée par Surface_mesh. Le maillage peut être affiché en fil de fer (wireframe) en utilisant la touche 'w'.

Ico-sphère après 0, 1, 2 et 4 subdivisions de Loop

1. Principe

L'algorithme est relativement simple :

1. insérer un nouveau sommet $u$ sur chaque arête de chaque triangle à la position : $$u_1 = \frac{3}{8} v_0 + \frac{3}{8} v_2 + \frac{1}{8} v_1 + \frac{1}{8} v_3$$

2. créer les 4 triangles : $$(v_0, u_5, u_1), (u_5, v_1, u_3), (u_3, v_2, u_1) \text{ et } (u_1, u_5, u_3)$$

Subdivision
3. calculer les nouvelles positions des sommets initiaux : $$v_i' = (1-\beta d_i) v_i + \beta \sum_{j=1}^{d_i} v_{ij}$$ avec $d_i$ le degré (valence) du sommet $v_i$, $v_{ij}$ son $j^{ième}$ voisin et $$\beta = \begin{cases} \frac{3}{16}, & \text{ si } d = 3\\ \frac{1}{d} \left( \frac{5}{8} - \left( \frac{3}{8} + \frac{1}{4} \cos \left(\frac{2 \pi}{d} \right) \right)^2 \right), & \text{ si } d > 3\\ \end{cases} $$ Le cas particulier des bords ouverts doit être géré séparément : $$u = \frac{1}{2} \left( v_0 + v_2 \right) \text{ et } v_i' = \frac{3}{4} v_i + \frac{1}{8} \left( v_{i1} + v_{i2} \right)$$

Nouvelles positions
Bords ouverts

2. Implémentation

Vous implémenterez cet algorithme dans la méthode subdivide de la classe Mesh. Pour réaliser ces opérations, il est nécessaire de parcourir le maillage. Pour cela, vous utiliserez un structure de half-edge, ou demi-arête, qui permet de stocker efficacement les relations d’adjacence et d’incidence sur le maillage. Pour vous familiariser avec la syntaxe de Surface_mesh, observez la méthode Mesh::load. Vous y découvrirez en particulier comment parcourir les sommets du maillage (Vertex_iterator) et comment accéder à leurs attributs (position, normale, etc.). Vous pourrez de la même façon parcourir les arêtes et les faces du maillage, ou circuler autour d'un sommet.

Dans un premier temps, ne considérez que des maillages fermés, donc sans bords ouverts. Il est plus simple d'implémenter la subdivision en utilisant deux structures en demi-arête (même si une version en place est aussi possible), l'une pour le niveau courant et l'autre pour le niveau suivant. Il faut cependant maintenir un mapping entre ces deux structures à l'aide d'attributs (properties) sur les sommets et les arêtes.

Je vous conseille de commencer par l'étape 3 de l'algorithme de subdivision. Créez une nouvelle instance de la classe Surface_mesh et ajoutez-y les sommets du niveau courant à leur position mise-à-jour (fonction add_vertex). Stockez le mapping entre les sommets de mHalfEdge et ceux de la nouvelle structure dans une nouvelle propriété :

Surface_mesh::Vertex_property<Surface_mesh::Vertex> vertex_mapping = _halfEdge.add_vertex_property<Surface_mesh::Vertex>("v:mapping")

Effectuez ensuite l'étape 1, c'est-à dire la subdivision de toutes les arêtes en utilisant la position initiale des sommets. Stockez cette fois le mapping sur les arêtes :

Surface_mesh::Edge_property<Surface_mesh::Vertex> edge_mapping = _halfEdgeMesh.add_edge_property<Surface_mesh::Vertex>("e:mapping");

Pour chaque face de l'ancien maillage, assemblez dans le nouvel half-edge les 4 nouveaux triangles (étape 2) en utilisant les deux mappings et la fonction add_face. (Attention, l'ordre des sommets est important.) Remplacez enfin mHalfEdge par la version de travail, et rechargez les buffers OpenGL en appelant Mesh::updateHalfedgeToMesh et Mesh::updateVBO.

  
"BigGuy" : version originale et subdivisée 3 fois

Bonus : considérez maintenant le cas des maillages possédant des bords ouverts. La méthode Surface_mesh::is_boundary vous permet de déterminer si un sommet, une arête ou un face est sur un tel bord.

"Pipes" après 0, 1, 2 et 4 subdivisions