Skin weight optimization (lagrange) (4)
Constraint optimization (Lagrange multiplier)
We introduce the Lagrange energy function as:
$$
\mathcal L(\vec w, \vec \lambda) = E(\vec w) - \sum_{i=1}^v { \lambda_i g_i( \vec w) }
$$
with \(\vec \lambda = [ \lambda_0, \lambda_1, \lambda_2, \cdots, \lambda_v ] \) and \( g_i \) a constraint at each vertex to preserve skin weight normalization. Finding the minimum \( \vec w_{min} \) of \( E \) under the constraints \( g_i \) is equivalent to solve the system:
$$
\nabla \mathcal L(\vec w, \vec \lambda) = 0 \iff
\left \{
\begin{array}{lll}
\nabla E(\vec w) - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} & = & 0\\
g_1(\vec w) & = & 0 \\
\vdots & & \\
g_v(\vec w) & = & 0\\
\end{array} \right .
$$
A single constraint is defined as:
$$
\begin{array}{lll}
g_i( \vec w_i) & = & 0 \\
1 - \sum_{j=1}^{|\vec w_i|} w_{ij} & = & 0 \\
\left [ \begin{matrix} 1 & \dots & 1 \end{matrix} \right ] \vec w_i & = & 1 \\
\mathbf g_i^T \vec w_i & = & 1 \\
\end{array}
$$
We can represent the system of constraints for every vertices:
$$
\begin{bmatrix}
1 & \cdots & 1 & 0 & 0 & 0 & \cdots & 0 \\
0 & \cdots & 0 & 1 & 1 & 0 & \cdots & 0 \\
0 & \cdots & 0 & 0 & 0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots & \vdots & 0 & \ddots & 0 \\
0 & \cdots & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{bmatrix} . \begin{bmatrix}
\vec w_0 \\
\vec w_1 \\
\vec w_2 \\
\vdots \\
\vec w_v \\
\end{bmatrix} = \vec 1 \\
\mathbf C \vec w = \vec m
$$
As for the system \( \nabla E(\vec w) - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} = 0 \) we already know \( \nabla E(\vec w) = (\mathbf A \vec w - \vec b) \) so lets focus on \( g(\vec w) = - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} \) of our system:
$$
\begin{array}{lll}
\nabla g_i (\vec w) & = & 1 - \sum_{j=1}^{|\vec w_i|} w_{ij} \\
& = & \nabla[1] - \nabla \left [ \sum_{j=1}^{|\vec w_i|} w_{ij} \right ] \\
& = & 0 - \begin{bmatrix} 0 & \dots & 0 & 1_{i0} & \dots & 1_{ij} & \dots & 1_{i|\vec w_i|} & 0 & \dots & 0 \end{bmatrix}^T \\
& = & - \vec 1_i \text{ vector of ones for the entries } |\vec w_i| \text{ of vertex i and zero otherwise}
\end{array}
$$
$$
\begin{array}{lll}
\nabla g(\vec w) & = & - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} \\
& = & - \sum_{i=1}^v {\lambda_i . (- \vec 1_i)} \\
& = & \sum_{i=1}^v { \vec \lambda_i }\\
& = & \begin{bmatrix} \vec 1_0 & \vec 1_1 & \dots & \vec 1_i & \dots & \vec 1_{v} \end{bmatrix} \vec \lambda\\
& = &
\begin{array}{c|cccccc|}
\nabla \mathbf G & 0 & 1 & \dots & i & \dots & v \\
\hline
w_{00} & 1 & 0 & \dots & 0 & \dots & 0 \\
w_{10} & 0 & 1 & 0 & 0 & 0 & 0 \\
w_{11} & 0 & 1 & 0 & 0 & 0 & 0 \\
& 0 & 0 & \ddots & 0 & 0 & 0 \\
w_{i0} & 0 & 0 & 0 & 1 & 0 & 0 \\
w_{ij} & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
w_{in_i}& 0 & 0 & 0 & 1 & 0 & 0 \\
& 0 & 0 & 0 & 0 & \ddots & 0 \\
w_{vn_v} & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}
\phantom{.} .
\begin{bmatrix}
\lambda_0 \\
\lambda_1 \\
\vdots \\
\lambda_i \\
\vdots \\
\lambda_v \\
\end{bmatrix} \\
& = &
\nabla \mathbf G \vec \lambda\\
\end{array}
$$
Which translates to:
$$
\begin{array}{lll}
\nabla E(\vec w) - \sum_{i=1}^v {\lambda_i \nabla g_i (\vec w)} & = & 0\\
(\mathbf A \vec w - \vec b) + \nabla \mathbf G \vec \lambda & = & 0\\
\mathbf A \vec w + \nabla \mathbf G \vec \lambda & = & \vec b \\
\end{array}
$$
Let's seek the matrix representation \( \mathbf M \mathbf x = \mathbf m\) of \( \nabla \mathcal L(\vec w, \vec \lambda) = 0 \):
- \( \vec m \in \mathbb R^v \text{ and } \vec m = \vec 1 \)
- \( \mathbf M : (|\vec w| + |\vec \lambda|) \times (|\vec w| + |\vec \lambda|) \)
- \( \mathbf A : |\vec w| \times |\vec w| \)
- \( \mathbf C : |\vec w| \times |\vec w| \)
- \( \nabla \mathbf G \in \mathbb R^{ v \times |\vec w| } \)
$$
\begin{bmatrix}
\mathbf A & \nabla \mathbf G \\
\mathbf C & 0 \\
\end{bmatrix}
\begin{bmatrix}
\vec w_0 \\
\vdots \\
\vec w_i \\
\vdots \\
\vec w_j \\
\vdots \\
\vec w_v \\
\lambda_0 \\
\vdots \\
\lambda_i \\
\vdots \\
\lambda_v \\
\end{bmatrix}
=
\begin{bmatrix}
\vec b_0 \\
\vdots \\
\vec b_i \\
\vdots \\
\vec b_j \\
\vdots \\
\vec b_v \\
m_0 \\
\vdots \\
m_i \\
\vdots \\
m_v \\
\end{bmatrix}
$$
No comments