TD8 : 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 : pghp_td8.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

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 possible d'implémenter la subdivision en place, sans dupliquer la structure en demi-arête. Pour cela, je vous conseille de commencer par l'étape 3 en stockant les positions mises-à-jour dans une nouvelle propriété des sommets, par exemple :

new_pos = _halfEdge.vertex_property<Point>("v:new_position")

Effectuez ensuite l'étape 1, c'est-à dire la subdivision de toutes les arêtes (Surface_mesh::insert_vertex) en utilisant la position initiale des sommets :

old_pos = _halfEdge.vertex_property<Point>("v:point");

Attention, lorsque la subdivision est en place, l'accès aux sommets $v_1$ et $v_3$ est progressivement modifié par les insertions.

Assemblez les 4 nouveaux triangles (étape 2). Je vous recommande d'utiliser les méthodes de bas-niveau de Surface_mesh (new_face, new_edge, set_halfedge, set_next_halfedge et set_face à rendre public) plutôt que la fonction add_triangle qui peut modifier profondément la topologie du maillage.

Remplacez enfin les anciennes positions (old_pos) par les nouvelles (new_pos) et rechargez les buffers OpenGL (Mesh::load et Mesh::init).

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

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