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