# Correspondence

Solution to find matching triangles between two meshes
from the paper:<br>
- <i>Robert W. Sumner, Jovan Popovic.</i> Deformation Transfer for Triangle Meshes. ACM Transactions on Graphics. 23, 3. August 2004.
    http://graphics.csail.mit.edu/~sumner/research/deftransfer/



<div style="display:table;">
<div style="display: table-row;">
<div style="display: table-cell; min-width:100px;"><b>Task:</b></div>
<div style="display: table-cell;">Find a triangle mapping of a source mesh to a target mesh.</div>
</div>
<div style="display: table-row;">
<div style="display: table-cell;min-width:100px;"><b>Idea:</b></div>
<div style="display: table-cell;">Repeated closest point transformations controlled by user-defined markers</div>
</div>
</div>
<br/>

## Algorithm:
1. Transform the source mesh to match user-defined markers while keeping the identity.
2. Search for closest vertices in the target.
3. Transform the source mesh again but additionally with the closest points.
4. Repeat from step 2.


The transformations in each step start from the initial source mesh.
It is updated iteratively by the transformation
that is created by the least squares solution of cost functions.
Instead for searching for a transformation, the costs are solved directly for the transformed mesh.
The user-defined markers forces the equation system
to solve for the target shape.
The smoothness cost $E_S$ and identity cost $E_I$ try to preserve the source mesh.
By enforcing the markers these cost functions find a "best" fit for the source
into the target mesh.
The closest point cost $E_C$ is the third cost function which
weighting is increase iteratively and so it slowly adapts the target mesh.
The closest points are re-computed after each iteration.
In the first iteration there are no closest points used (since there are none yet).

## Triangle transformation

A triangle (or face) without position can be described in the form of span vectors written in columns
that are produced by the three vertices $\vec{a}, \vec{b}, \vec{c}$ and a fourth square-rooted normal $\vec{d}$.
The vertex $\vec{d}$ allows lateral movement of the face $V_i$ when a transformation is applied.

$$V_i = \left[\vec{b}-\vec{a}, \vec{c}-\vec{a}, \vec{d}-\vec{a}\right]$$

The fourth span vector $\vec{d}$ is the square-root normalized normal of the face, given by:

\begin{equation}
    \vec{d} = \vec{a} + \frac{\left(\vec{b}-\vec{a}\right)\times\left(\vec{c}-\vec{a}\right)}
    {\sqrt{\left|\left(\vec{b}-\vec{a}\right)\times\left(\vec{c}-\vec{a}\right)\right|}}
\end{equation}

A face (or triangle) transformation $T_i$ for a face-index $i$ is then given by:

$$\widetilde{V}_i = T_i\cdot V_i \longrightarrow T_i=\widetilde{V}_i V_i^{-1}$$


## Transformation Definition

The transformation to the target mesh is controlled by a cost function
that can be solved directly for the vertices of the transformed mesh including the fourth face normal.
It searches for the least square solution for the vertices $x = (\vec{v}_1, ..., \vec{v}_n)$, $x \in \mathbb{R}^{3 \times n}$ which contains
the vertices of the mesh as well as the artifical fourth face normals. </br>
The solution can be expressed as the sum of the cost functions weighted by $w_S$, $w_I$, and $w_C$.

\begin{equation}
    \widetilde{x} = \underset{\widetilde{V}}{\min}\left( w_S E_S + w_I  E_I + w_C E_C \right)
\end{equation}



Name | Equation
:---- | :-----
Smoothness | $$E_S(v_1,...,v_n)=\sum_{T_i}\sum_{T_j\in\text{adj}(T_i)}\left\|T_i - T_j\right\|^2_F$$
Identity | $$ E_I(v_1,...,v_n) = \sum_{T_i}\left\|T_i-\mathbf{I}\right\|^2_F $$
Closest Valid Point | $$E_C(v_1,...,v_n; c_1,...,c_n)=\sum_{i}\left\|v_i-c_i\right\|^2$$

Each cost function can be expanded and expressed as a sum of individual terms
and merged back into a single Frobenius norm (like an accordion).</br>
For example the identity cost can be converted as followed:

## Frobenius Norm
#### Merging equations

The equations can be merged into a single Frobenius Norm which can be solved by common solvers.

\begin{align}
\sum_{k}\left\|Z_k\right\|^2_F &= \sum_{k}z_{k1}^2+z_{k2}^2+...+z_{kl}^2
\\
 &= (z_{11}^2+z_{12}^2+...+z_{1l}^2)+ (z_{21}^2+z_{22}^2+...+z_{2l}^2) + ... + (z_{k1}^2+z_{k2}^2+...+z_{kl}^2)
 \\
 &= \left\|\sum_{k}Z_k\right\|^2_F
\end{align}

with $l$ element in $Z$.

#### Transposed

The frobenius norm and its minimization does not change if the equation is transposed.

\begin{equation}
\left\|Z\right\|^2_F = z_{1}^2+z_{2}^2+...+z_{l}^2 = \left\|Z_k^T\right\|^2_F
\end{equation}


## Transformation Structure

A equation system of squared Frobenius norms can be reordered into another structure.
This can be used to structure a matrix equation system that can be solved efficiently.



### Matrix Structure
The triangle transformation $T_i$ can be expressed as a equation on all vertices $x \in \mathbb{R}^{3\times n}$
and $\hat{V}^{-1} \in \mathbb{R}^{n\times 3}$:

\begin{equation}
T_i = \widetilde{V} V^{-1} \quad \xrightarrow[]{\text{Expand to } x} \quad \hat{T}_i = x \hat{V}^{-1}
\end{equation}

<!--
% \quad \xrightarrow[]{Transpose} \quad \hat{T}_i^T=(\hat{V}^{-1})^Tx^T
-->

This applied to any $T_i$, it follows with $C_i \in \mathbb{R}^{3\times 3}$ as constant:

\begin{align}
\left\|T_i-C_i\right\|^2_F
&= \left\|\widetilde{V}_i V_i^{-1}-C_i\right\|^2_F
& \xrightarrow[]{\text{Expand to } x} \quad& \left\|x \hat{V}_i^{-1}-C_i\right\|^2_F
\end{align}

Transposing and merging the equations for $m$ triangle transformations $T_i$

\begin{align}
\sum_{i=1}^{m}\left\|x\hat{V}^{-1}-C_i\right\|^2_F
&= \sum_{i=1}^{m}\left\| \left( x\hat{V}^{-1}-C_i \right)^T \right\|^2_F
\\&=\sum_{i=1}^{m}\left\| \left(\hat{V}_i^{-1}\right)^T x^T - C_i^T  \right\|^2_F
\\&= \left\| \begin{pmatrix}
\left(\hat{V}_1^{-1}\right)^T \\
\left(\hat{V}_2^{-1}\right)^T \\
... \\
\left(\hat{V}_m^{-1}\right)^T
\end{pmatrix}
x^T - \begin{pmatrix}
C_1^T \\
C_2^T \\
... \\
C_m^T
\end{pmatrix} \right\|^2_F
&&= \left\|Ax^T-b\right\|^2_F
\end{align}

### Cost Matrices

Each cost builds a separate matrix in which each row is minimized with a least square method.

#### Identity cost matrix

\begin{equation}
E_I(v_1,...,v_n) = \sum_m^{\left|T_i\right|}\left\|T_i-\mathbf{I}\right\|^2_F
= \left\| \begin{pmatrix}
\left(\hat{V}_1^{-1}\right)^T \\
\left(\hat{V}_2^{-1}\right)^T \\
... \\
\left(\hat{V}_m^{-1}\right)^T
\end{pmatrix}
x^T - \begin{pmatrix}
\mathbf{I} \\
\mathbf{I} \\
... \\
\mathbf{I}
\end{pmatrix} \right\|^2_F
= \left\|A_Ix^T-b_I\right\|^2_F
\end{equation}


where $A_I \in \mathbb{R}^{3m\times n}$  and $b_i \in \mathbb{R}^{3m\times 3}$

#### Smoothness cost matrix

\begin{equation}
E_S(v_1,...,v_n)=\sum_m^{\left|T_i\right|}\sum_{T_j\in\text{adj}(T_i)}\left\|T_i - T_j\right\|^2_F
= \left\| \begin{pmatrix}
\left(\hat{V}_1^{-1} - \hat{V}_{j_1}^{-1}\right)^T \\
\left(\hat{V}_1^{-1} - \hat{V}_{j_2}^{-1}\right)^T \\
... \\
\left(\hat{V}_1^{-1} - \hat{V}_{j_{\left|\text{adj}(T_i)\right|}}^{-1}\right)^T \\
\left(\hat{V}_2^{-1} - \hat{V}_{j_1}^{-1}\right)^T \\
... \\
\end{pmatrix}
x^T - 0
\right\|^2_F
= \left\|A_Sx^T-b_S\right\|^2_F
\end{equation}


where $A_S \in \mathbb{R}^{3q\times n}$, $b_i \in \mathbb{R}^{3q\times 3}$, and
$q = \sum_m^{\left|T_i\right|}\left|\text{adj}(T_i)\right|$.


### Closest point cost matrix

The closest point is the 2-Norm and can be handled the same way like the Frobenius norm.

\begin{equation}
E_C(v_1,...,v_n; c_1,...,c_n)=\sum_{i}\left\|v_i-c_i\right\|^2
= \left\| \mathbf{I}
x^T - \begin{pmatrix}
c_1^T \\
c_2^T \\
... \\
c_n^T
\end{pmatrix}\right\|^2_F
= \left\|A_Cx^T-b_C\right\|^2_F
\end{equation}

where $A_C \in \mathbb{R}^{n\times n}$  is the identity, and $b_c \in \mathbb{R}^{n\times 3}$ are the transposed
closes points.


### Final equation for least-squares solver
Each cost is weighted, which needs to be reflected into the equation system.
We can do this by weighting each row.

\begin{equation}
E = w_S E_S + w_I  E_I + w_C E_C
\end{equation}


\begin{align}
\widetilde{x} = \underset{x}{\text{arg}\min}\left\|
\begin{pmatrix}
w_I A_I \\
w_S A_S \\
w_C A_C \\
\end{pmatrix}x^T -
\begin{pmatrix}
w_I b_I \\
w_S b_S \\
w_C b_C \\
\end{pmatrix}
\right\|^2_F
\end{align}


Before the least-squares solution is searched, the columns for all marker vertices
are resolved and subtracted from the right side $b_I, b_S, b_C$.
Then the marker positions on the left side $A_I, A_S, A_C$ are set to 0.
This forces the equation to find a solution with the marker vertices fixed.


### Transformation Vertex Indicies
In the expansion of V to $\hat{V}$ for the big $x$ vertices list each transformation is indexed as followed:

\begin{align}
    \mathbf{T} &= \widetilde{V}V^{-1}
    = \left[\vec{b}-\vec{a}, \vec{c}-\vec{a}, \vec{d}-\vec{a}\right] V^{-1}  \\
    \\
    &= \begin{pmatrix}
        b_{1} - a_{1} & c_{1} - a_{1} & d_{1} - a_{1} \\
        b_{2} - a_{2} & c_{2} - a_{2} & d_{2} - a_{2} \\
        b_{3} - a_{3} & c_{3} - a_{3} & d_{3} - a_{3}
    \end{pmatrix}
    \begin{pmatrix}
        \overline{v}_{1,1} & \overline{v}_{1,2} & \overline{v}_{1,3} \\
        \overline{v}_{2,1} & \overline{v}_{2,2} & \overline{v}_{2,3} \\
        \overline{v}_{3,1} & \overline{v}_{3,2} & \overline{v}_{3,3}
    \end{pmatrix}
\end{align}

The resulting matrix $\mathbb{R}^{3\times 3}$ has the following equation for each entry:

\begin{align}
    w_{i,j}
    &= (b_{i} - a_{i}) \overline{v}_{1,j}
    + (c_{i} - a_{i}) \overline{v}_{2,j}
    + (d_{i} - a_{i}) \overline{v}_{3,j}
    \\
    &= b_{i}\overline{v}_{1,j}  - a_{i}\overline{v}_{1,j}
    + c_{i}\overline{v}_{2,j} - a_{i}\overline{v}_{2,j}
    + d_{i}\overline{v}_{3,j} - a_{i}\overline{v}_{3,j}
    \\
    &=
    - (\overline{v}_{1,j} + \overline{v}_{2,j}+ \overline{v}_{3,j})a_{i}
    +\overline{v}_{1,j}b_{i}
    + \overline{v}_{2,j}c_{i}
    + \overline{v}_{3,j}d_{i}
\end{align}

## Implemenation

Numpy + Scipy + Plotly (for plotting)

### Optimization

Since the three XYZ components of the vertices are independent, the minimization problem can be solved independetly
by component. One optimization is to create a diagonal block matrix and solve it single-threaded;
or use multiple threads to solve the least-square problem for each XYZ component.

### Imports


```python

```

ba358abe33310695a1381edc1d083bf80b50a00a
ipynb
Jupyter Notebook
correspondence.ipynb
mickare/Deformation-Transfer-for-Triangle-Meshes
5809c92ddcaecc6df45443e3109a3848b55d9045
MIT
2021-03-22T02:46:38.000Z
2022-03-30T08:41:44.000Z
correspondence.ipynb
hendrikp/Deformation-Transfer-for-Triangle-Meshes
fbb3b73c78cf3df529759f7497cc1894be5754bb
MIT
2021-06-18T13:43:27.000Z
2021-08-02T16:38:58.000Z
correspondence.ipynb
hendrikp/Deformation-Transfer-for-Triangle-Meshes
fbb3b73c78cf3df529759f7497cc1894be5754bb
MIT
2021-04-09T10:23:03.000Z
2022-02-21T11:51:17.000Z
Qwen/Qwen-72B
1. YES
2. YES