Mesures et quantifications sur les maillages

Jean-Marie Favreau — ISIMA 3^ème année F1

Premiers éléments de mesure

sortons le double décimètre

aire de la surface

boîte englobante

centre d'un objet

directions principales

Analyse en composantes principales (PCA)

Vecteurs propres de la matrice de covariance

estimation du volume

Distances : calculs et applications

les plus courts chemins

définition (rappel)

chemin géodésique

Le chemin le plus court, ou l'un des plus courts chemins s'il en existe plusieurs, entre deux points d'un espace pourvu d'une métrique est une géodésique. (wikipédia)

algorithme (rappel)

approche simplifiée : le chemin d'arêtes le plus court entre deux sommets

entrée : un maillage, deux sommets
sortie : une liste d'arêtes
algorithme de Dijkstra

Limitations : cas de grilles dégénérées

chemins linéaires par morceaux

un plus court chemin linéaire par morceaux

chemins linéaires par morceaux

Exact and approximate computation (Surazhsky 2005)

chemins linéaires par morceaux

Exact and approximate computation (Surazhsky 2005)

application

signature de maillages (Smeets 2010)

application

mesure de dimension (Thierny 2008)

Topologie

Structure des objets

genre (rappel)

Caractéristique d'Euler

Compter le nombre de faces, arêtes et sommets d'un cube, d'un tétraèdre, d'un tore.

Calculer χ = #vertices − #edges + #faces

Calculer g = (2-χ)/2

graphe de Reeb

ingrédients

Prérequis :

M : variété différentiable
f: M → ℝ : fonction scalaire lisse

Ligne de niveau : image inverse d'un point de ℝ

Point critique : p point critique ⇔ gradient de f en p est 0 (extremums, points selles)

Point critique non dégénéré : nombre de directions décroissantes ≤ 2

graphe de Reeb

fonctions de Morse

Fonction de Morse : fonction scalaire lisse sans point critique dégénéré

On définit M^a=f^-1(]- ∞; a])

Soit a<b. Si f^-1([a;b]) est un compact sans point critique entre a et b, alors M^b se rétracte de manière continue en M^a.

graphe de Reeb

définition, intuition

On défini la relation d'équivalence p ~ q ⇔ p et q appartiennent à la même composante connexe d'un f^-1(c) pour un c réel.

Graphe de Reeb : espace quotient M/~.

graphe de Reeb sur les maillages

quelques idées sur l'implémentation

Fonctions scalaires définies sur les sommets (+interpolation linéaire)
Ajout d'un epsilon différent pour chaque f(p) pour préserver un ordre
Points critiques identifiés par les valeurs de la première couronne

squelette

Tierny 2008, Reuter 2010

topologie locale

Taylor (Mortara 2004)

Géométrie

Du local et du global

estimation de normale

approche variable suivant les communautés scientifiques

En géométrie algorithmique

n'utiliser que le maillage
calculer la moyenne des normales dans un voisinage
ingrédients complémentaires (rayon du voisinage, aire des triangles)

courbures principales

calcul (Alliez 2003)

B : disque géodésique
β(e) : angle entre les normales des triangles
|e ∩ B| : longueur de e dans B
ē vecteur unité parallèle à e

κ_min, κ_max : valeurs propres de τ, amplitude de courbure
γ_min, γ_max : vecteurs propres de τ, vecteurs de courbure

courbures principales

résultats (Cohen-Steiner and Morvan 2003, Alliez et al, 2003)

courbure minimum

bleu : minimum, rouge : maximum

Shape Diameter Function

Shapira 2008

Segmentation

en faire des rondelles

découper le maillage en régions avec propriétés cohérentes

Propriétés : géométrie, topologie, informations additionnelles

Motivations : analyse de forme, mise en correspondance, reconnaissance partielle, substitution, ...

qu'est-ce qu'un élément de surface ?

Labels portés par les faces ou les sommets
Segmentation basée contours ou basée régions

marches aléatoires

Lai 2008

Approche basée graphe
Nœuds, et probabilité de marcher d'un nœud à un autre
Description par matrice creuse
Résultat : probabilité d'atteindre les nœuds depuis les graines en utilisant une marche aléatoire