---
title: VISI601_CMI Paramétrisation de maillages
type: slide
slideOptions:
transition: slide
progress: true
slideNumber: true
---
# Paramétrisation de maillages
> [name=Jacques-Olivier Lachaud][time=January 2022][color=#907bf7]
> (Les images peuvent être soumises à des droits d'auteur. Elles sont utilisées ici exclusivement dans un but pédagogique)
###### tags: `visi601`
Retour à [VISI601_CMI (Main) Algorithmique numérique](https://codimd.math.cnrs.fr/s/IWTaBkA9m)
---
## Paramétrisation = illustration
---
## Paramétrisation = système de coordonnées (u,v)
|  |  |
| ------------------------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------ |
| | |
Trouver une application $f: S \rightarrow \mathbb{R}^2$, qui associe des coordonnées $(u,v)$ à chaque point de $S$. En fait, association aux sommets + interpolation linéaire
---
## Formulation du problème de paramétrisation
Soit $V=\{1,\ldots,n\}$ les $n$ sommets de $S$, et $B \subset V$ les sommets du bord de $S$
Soit $E \subset V \times V$ les arêtes de $S$
On cherche $\mathbf{u}$ et $\mathbf{v}$, vecteurs de taille $n$, coordonnées $(u_i,v_i)$ de chaque sommet $i$
==minimiser une distorsion== ici on choisit de limiter les variations de $u$ et $v$
$E(\mathbf{u},\mathbf{v})=\sum_{i=1}^n \sum_{j, (i,j) \in E} |u_j-u_i|^2 + |v_j-v_i|^2$
minimiser $E(\mathbf{u},\mathbf{v})$, en fixant les $(u_k,v_k)$, $k \in B$ du bord
---
## Paramétrisation de Tutte
On fixe $(u_j,v_j)$, $j \in B$ du bord, par exemple sur un cercle ou un carré
Soit $\mathbf{U}$ la concaténation de $\mathbf{u}$ et $\mathbf{v}$
Soit $L$ le Laplacien de graphe du maillage, $L_2:=\begin{bmatrix} L & \mathbf{0}\\ \mathbf{0} & L \end{bmatrix}$
$\min_{\mathbf{u},\mathbf{v}} E(\mathbf{u},\mathbf{v}) \,\Leftrightarrow\, \min_{\mathbf{U}} \mathbf{U}^T L_2 \mathbf{U} \,\Leftrightarrow\, (L_2^T+L_2) \mathbf{U} = \mathbf{0} \,\Leftrightarrow\, L_2 \mathbf{U} = \mathbf{0}$
==Fixer le sommet bord $j$ à $x_j$==
$\begin{bmatrix} \ddots & \ddots & \ddots & \vdots & \ddots \\ \ddots & \ddots & \ddots & 1 & \ddots \\ \ddots & \ddots & \ddots & \vdots & \ddots \\ \cdots & 1 & \cdots & -4 & \cdots \\ \ddots & \ddots & \ddots & \vdots & \ddots \\\end{bmatrix}\mathbf{U}=\begin{bmatrix}\vdots \\ \vdots \\ \vdots \\ \vdots \\ \vdots \end{bmatrix}$ devient $\begin{bmatrix} \ddots & \ddots & \ddots & \vdots & \ddots \\ \ddots & \ddots & \ddots & 0 & \ddots \\ \ddots & \ddots & \ddots & \vdots & \ddots \\ \cdots & 0 & \cdots & 1 & \cdots \\ \ddots & \ddots & \ddots & \vdots & \ddots \\\end{bmatrix}\mathbf{U}=\begin{bmatrix}\vdots \\ \cdots -x_j \\ \vdots \\ x_j \\ \vdots \end{bmatrix}$
---
## Paramétrisation de Tutte
On résoud $L'_2 \mathbf{U} = \mathbf{b}$, système transformé pour fixer le bord
| |  |
| -------- | -------- |
| $f(S)$ + paramétrisation | $S$ + paramétrisation |
:::success
Si bord convexe, paramétrisation **injective**. On peut même mettre des poids variables
:::