Maillages dans un viewer 3D et analyse topologique.
TerminéSprint S4-S5+S36-S41+S43 · 36 points
En bref, sans jargonpour les non-informaticiensLire le résuméRefermer
Ce que c'est
Un outil qui analyse la forme d'objets en 3D (un anneau, une sphère, un ruban de Möbius) : combien ils ont de trous, où ils sont courbés, comment leur forme se construit quand on les remplit du bas vers le haut.
À quoi ça sert
Ces mesures servent en imagerie médicale, en simulation et en conception industrielle, pour comparer et contrôler des formes.
Ce que ça montre
Mon cœur de métier, en tant que docteur en informatique graphique : des mathématiques exigeantes traduites en un outil rapide et vérifié, qu'on manipule à la souris.
Topologie (C++20, demi-arêtes) → API C (une seule interface) : invariants, courbure
API C (une seule interface) → WebAssembly (Emscripten)
WebAssembly (Emscripten) → Visionneuse (three.js, sur la fiche)
API C (une seule interface) → API Python (FastAPI, ctypes) : bibliothèque partagée
Faire tourner un maillage
La couleur montre la courbure de Gauss en chaque sommet. Invariants et courbure sont calculés par le code C++ du projet, compilé en WebAssembly, dans votre navigateur.
Exemples :
0
selle (K < 0)dôme (K > 0)
Échelle par quantiles : la moitié des sommets ont une courbure plus faible que la graduation du milieu de chaque côté, 90 % plus faible que celle de l'extrémité.
minimum
selle
maximum
Comme le filtre Elevation de ParaView : le maillage est coloré par sa hauteur, et le curseur ne garde que la partie sous le seuil (les triangles dont les trois sommets sont plus bas). Un point est critique quand son lien inférieur (ses voisins plus bas) n'est pas d'un seul tenant : aucun voisin plus bas pour un minimum, plusieurs morceaux pour une selle. Calculé par le C++ de topologie, en WebAssembly.
Diagramme de persistance
Explication guidée
Le seuil de hauteur monte pas à pas ; à chaque étape, la classe qui naît ou meurt est mise en avant.
Survolez, touchez ou parcourez au clavier (Tab puis flèches) une barre, un point ou une ligne du tableau : le sommet où la classe naît et celui où elle meurt s'entourent sur le maillage, et le seuil de hauteur se place entre les deux.
composante (H0)
boucle (H1)
cavité (H2)
Code-barres de la persistance
Le même diagramme en nuage de points
Pourquoi la boucle ne se referme-t-elle pas dès la seconde selle en montant ? La persistance regarde tout ce qui est sous le seuil (les sous-niveaux) : entre les deux selles du tore debout, c'est un cylindre d'un seul tenant, et la seconde selle y ajoute une anse au lieu de refermer la boucle. Le graphe de Reeb ne regarde que la tranche au seuil (la ligne de niveau) : deux cercles entre les selles, qui se rejoignent à la seconde. La persistance étendue réconcilie les deux : en redescendant, elle referme la boucle à la seconde selle.
Voir les paires
Dimension
Hauteur où elle naît
Hauteur où elle meurt
Persistance
Chaque composante (H0), boucle (H1) ou cavité (H2) des sous-niveaux naît à un point critique et meurt à un autre en montant ; celles qui ne meurent jamais en montant, autant que les nombres de Betti, sont refermées en redescendant (persistance étendue : après les sous-niveaux, le maillage relatif à ce qui est au-dessus du seuil). La longueur de la barre, sa persistance, sépare les vraies formes du bruit : le curseur grise les paires plus courtes que le seuil et ne garde sur le maillage que les points critiques des paires restantes. Calculé par le C++ de topologie, en WebAssembly : réduction de la matrice de bord sur Z/2, puis union-find en cohomologie.
Graphe de Reeb
Chaque composante de chaque ligne de niveau est réduite à un point : les nœuds sont là où elles naissent, se séparent, se rejoignent ou meurent, et chaque arc en suit une, tracé par les centres des lignes de niveau. Sur une surface fermée orientable, le graphe a autant de boucles que le genre, quelle que soit la direction. Calculé par le C++ de topologie, en WebAssembly ; dans le maillage, rendu transparent, il est coupé au seuil de hauteur.
Glisser pour tourner, molette ou pincement pour zoomer ; survoler un point pour lire sa courbure. Le repère en bas à gauche suit la caméra : x en rouge, y en vert, z en bleu.
Au bord, le défaut angulaire mesure la courbure du bord lui-même : les sommets du bord prennent la couleur de leurs voisins intérieurs.
Temps de calcul
Mesuré sur un tore debout, meilleur de 3 passages, sur un seul fil d’un Intel(R) Core(TM) i5-10400F CPU @ 2.90GHz : en natif (C++ compilé en Release par GCC) et en WebAssembly (le même code, dans Node, comme dans la page). Produit par projects/topologie/scripts/bench.mjs.
Triangles
Fichier OBJ
Lecture (Wasm)
Hauteur
Persistance
Graphe de Reeb
Persistance étendue
10 000
0,3 Mo
24 ms
2 ms natif · 2 ms Wasm
8 ms natif · 10 ms Wasm
5 ms natif · 6 ms Wasm
15 ms natif · 17 ms Wasm
30 000
1,0 Mo
75 ms
5 ms natif · 6 ms Wasm
26 ms natif · 37 ms Wasm
14 ms natif · 19 ms Wasm
57 ms natif · 60 ms Wasm
100 000
3,5 Mo
251 ms
24 ms natif · 24 ms Wasm
116 ms natif · 174 ms Wasm
56 ms natif · 68 ms Wasm
231 ms natif · 248 ms Wasm
300 000
10,8 Mo
788 ms
76 ms natif · 76 ms Wasm
502 ms natif · 736 ms Wasm
178 ms natif · 204 ms Wasm
945 ms natif · 968 ms Wasm
1 000 000
37,6 Mo
2,72 s
281 ms natif · 280 ms Wasm
2,38 s natif · refusé par la page
648 ms natif · refusé par la page
4,32 s natif · refusé par la page
Et un GPU ? Il accélérerait ce qui se fait sommet par sommet ou triangle par triangle, sans dépendance : la hauteur (un produit scalaire par sommet), le tri des sommets (tri parallèle), le lien inférieur de chaque sommet, et la persistance H0 par fusions en parallèle. La réduction de la matrice de bord, elle, traite les colonnes l’une après l’autre (chacune dépend des précédentes), et le graphe de Reeb repose, comme la persistance H0, sur des union-find aux accès imprévisibles : un GPU y passerait son temps à se synchroniser. Or la persistance domine (2,38 s pour un million de triangles en natif) et c’est elle qui s’y prête le moins : pas de version GPU (D49).
Pourquoi 32 Mo ? Avant tout calcul, lire un OBJ de 37,6 Mo (un million de triangles) prend 2,72 s en WebAssembly, sur le fil de la page, qui reste figée pendant ce temps ; la mémoire WebAssembly monte vers 190 Mo (750 Mo pour 4 millions de triangles), plafonnée à 1 Go par la compilation et à 4 Go en wasm32, et un téléphone en a moins. La limite garde l’attente sous deux secondes et demie ; la lever demanderait une lecture en flux dans un Web Worker et plus de mémoire (D49). Au-delà de 300 000 triangles, la page refuse aussi la persistance, sa version étendue et le graphe de Reeb : une demi-seconde à ce plafond, une seconde pour la persistance étendue.
Technologies
C++
Three.js
GoogleTest
Qui fait quoi
C++
La structure demi-arête, les invariants (Euler, genre, bords, orientabilité), la courbure de Gauss, la hauteur, ses points critiques (théorie de Morse discrète) sa persistance (réduction de la matrice de bord) et son graphe de Reeb ; compilé en WebAssembly par Emscripten pour la visionneuse, et en bibliothèque partagée pour l'API Python.
Three.js
La visionneuse de la fiche : le maillage coloré par sa courbure ou sa hauteur, filtré sous un seuil, ses points critiques marqués, son graphe de Reeb tracé dedans, tourné à la souris ou au doigt.
GoogleTest
Les tests du C++ : invariants des maillages de référence, courbure comparée aux valeurs théoriques, points critiques (sphère, tore, selle de singe, somme des indices égale à χ), persistance (nombres de Betti, stabilité), graphe de Reeb (boucles égales au genre), sous Linux, Windows et macOS.