[Paper Reading] Automatic Rigging and Animation of 3D Characters

Overview

该文提出了一种3D几何模型自动化绑定骨架、自动化蒙皮的技术，实现了输入几何模型、骨架结构、动画数据，无需人工干预，自动驱动几何模型按照指定的动画运动。

该技术包含两个关键步骤：

骨架嵌入(Skeleton Embedding)：构建输入几何模型的几何结构图(Geometric Graph)，定义骨架嵌入的惩罚函数，将输入骨架嵌入到几何结构图中，并对最优的骨架嵌入进一步优化得到最终的骨架嵌入。
蒙皮绑定(Skin Attachment)：根据热平衡方程(Heat Equilibrium)，将骨架骨骼对周围模型顶点的权重转化为热传导平衡态时的温度的分布，从而得到连续光滑的骨骼蒙皮权重。

自动化骨架绑定通常包含两种实现方式：骨架嵌入(Skeleton Embedding)和骨架提取(Skeleton Extraction)。先前的大部分工作采用骨架提取方法，即直接根据几何模型的拓扑结构提取骨架结构。骨架提取主要的问题有：

提取的骨架与输入的骨架之间可能无法很好的对应。尤其对于复杂的几何模型，可能会提取与所需动画驱动不相符的骨架结构。如图1所示，耳朵并不需要骨骼绑定，但耳朵区域的几何特征特别明显，导致骨架提取方法在该区域抽取骨架结构信息。
完全依赖模型几何拓扑结构，无法充分利用输入骨架结构的先验知识。例如，虽然躯干部分只用一个几何拓扑结构描述，但根据动画驱动，需要绑定多根骨骼。骨架嵌入完全依赖局部的拓扑结构，导致无法抽取符合要求的骨架结构。

图1: 骨架提取(left)与骨架嵌入的效果比较(right)[1]

Skeleton Embedding

骨架嵌入通过调节给定骨骼的位置和大小，使之较好的嵌入到输入的几何模型内部。该文算法对给定的几何模型有如下约束：

几何模型表面是紧致而连通的(watertight)，即无开放的空洞和非连通结构。
几何模型的拓扑结构需要和输入的骨架结构在拓扑上近似。
几何模型的朝向需要和输入骨架的朝向保持一致。

总体上来说，一个好的骨架嵌入需要能够尽可能完美的嵌入到模型内部，而且与给定的输入骨架尽可能的相似。此外还可以针对给定的具体类型骨架增加特定的约束，例如：骨架在嵌入时左右对称；指定某骨关节点为“脚关节”，从而约束其嵌入时的位置较低。由于这些条件主要是针对骨架嵌入进行约束，而与几何模型无关，因此并不影响算法的通用性。

骨架结构通常通过层次化的骨关节(Joints)来描述。一个包含 $s$ 个关节的骨架，其空间的自由度为 $3s$ 。由于计算量极大，直接在嵌入空间进行连续性优化是不可行的。该文采用图嵌入的方式将骨架嵌入转化为离散优化问题。具体的，根据几何模型构建图结构，图中每个节点都是潜在的骨关节，每个子图都是一种潜在的骨架。通过寻找一个与给定输入骨架结构最相似的子图，将连续空间的骨架嵌入问题转化为图上的离散优化问题。

算法整体的流程步骤如下：

构造模型几何结构图：构造符合模型拓扑结构的内嵌几何结构图，作为输入骨架潜在的嵌入图。
简化输入骨架图：降低输入骨架嵌入到几何结构图中节点的度，从而降低计算量。
训练惩罚函数：定义若干离散的惩罚函数基，并采用改进的SVM学习各惩罚函数基的加权系数，定量描述骨架嵌入的质量。
优化骨架嵌入：根据定义的惩罚函数，采用 $A^*$ 算法，在几何结构图上搜索得到最佳的骨架嵌入。
优化嵌入结果：定义连续惩罚函数，进一步微调离散空间优化得到的骨架嵌入结果。

Discretization

在将几何模型离散化为几何结构图之前，需要对输入几何模型归一化，即将模型缩放到轴对称的单位立方体中。

从任意给定的模型中构造几何结构图，首先采用自适应八叉树描述模型表面的符号距离场(Signed Distance Field)，然后通过符号距离场的一阶非连续性提取模型的近似中值面(Medial Surface)。以中值面上点为球心，利用球体最大化填充模型的内部空间。按照一定规则连接填充球的球心坐标，得到模型的几何结构图。整体流程如下图所示：

构造模型几何结构图，从左到右分别为：中值面提取、球体填充、结构图构造

Distance Field

为了便于提取中值面及简化后续计算，通过三线性自适应八叉树结构描述模型的符号距离场。在使用八叉树结构近似描述模型的距离场时，首先采用KD-Tree结构计算空间任意点到模型表面的有符号距离，其中位于模型内部点的距离为负。

在轴对齐的单位立方体空间内，使用八叉树自顶向下划分子单元，直到满足如下一个条件，即停止分割：

子单元不包含模型面片，即子单元各顶点处的距离取值符号相同；或者，
直到子单元内任意点到模型表面的距离可通过子单元的八个顶点处的距离，以误差不超过 $\tau=0.003$ 的精度三线性插值逼近。

子单元顶点到模型表面的距离通过KD-Tree方式精确计算，自适应八叉树依据几何体拓扑结构，用距离场近似描述几何体表面。

Approximate Medial Surface

中值面定义了一组离散的采样点。以中值面上离散点为球形，符号距离为半径，与几何体内表面有两个或更多的切点。在2D空间，将距离描述为高度场，则中值面集中在脊(Ridge)的位置。

脊位置的距离场是 $C^1$ 不连续的，而八叉树网格内部的距离场是连续的，因此 $C^1$ 不连续只出现在网格边界的顶点。根据此规则，中值面上的采样点需满足如下条件：

包含顶点的相邻网格上的距离场梯度向量的夹角大于 $120^o$ ；
采样点到几何体表面的距离大于指定阈值( $2\tau$ )

通过如上计算，即可得到几何体的近似离散中值面。

Sphere Packing

根据到几何物体表面的距离由大到小排序中值面的点，并按顺序轮训所有点。如果该点不在任何之前已经添加的球体内部，则以该点为球心，该点距离为半径填充球体到物体内部空间。以距离作为半径填充球，能够保证球体尽可能的填充较大的空间。以最大的球开始填充则保证尽可能以较少数量的球进行填充。

Graph Construction

按照一定规则连接填充球的中心点，即可构成物体的几何结构图。满足以下条件之一的两个填充球中心点，既可构成结构图的一条边：

若两个填充球体相交，则连接其中心点，构造一条边；
虽然两个球体未相交，但其中心连线位于几何物体内部，并且组成的边是"重要"的。例如位于脖子和左/右肩的球体通常不相交，但仍然需要在球体之间构造一条边，因为大部分的输入骨架结构都包含此类边。

其中第二条规则中，对于"重要"边的精确描述为：边上任意点到几何物体表面的距离均不小于组成边的两个填充球中较小球体的半径的1/2，并且距离边中点位置最近的填充球必须是组成边的两个填充球之一。该条件等价于边是由所有填充球中心点组成的Gabriel图中的一条边。

Gabriel图描述了任意点集一个连接图，以该图任意边为直径构造圆(三维空间为球)，圆内不包含图中其它的节点。Gabriel图是Delaunany图的子图。2D空间的描述形式如下图所示：

2D空间的Gabriel示意图[wikipedia]

左图中， $c$ 点位于 $a$ 和 $b$ 点组成的圆之外，因此由 $a$ 和 $b$ 组成的边符合Gabriel描述。同理右图中 $a$ 和 $b$ 组成的边则不符合Gabriel描述。Gabriel图是 $\beta$ -skeleton的一种实例，即图中任意两条边形成的夹角大于指定值 $\beta$ 。在几何图构造中，通过Gabriel约束增加了在几何模型局部相隔较远，但属于直接关节连通的区域之间的骨骼连接。

通过上述处理，可以将几何模型离散化为几何结构图 $G=(V, E)$ ，输入的骨架结构将嵌入到几何结构图 $G$ 。

Reduced Skeleton

输入骨架通过层次化的关节点描述。当骨骼关节点数量较多时，增加了优化骨架嵌入的计算量，因此需要对输入骨架进行简化。通过直接将所有度为2的关节进行融合，可以较大的简化了输入骨架整体的节点度数。在该文中输入骨架的节点数为 $s$ =18，经过简化后骨架节点数 $r$ =7。

输入骨架在关节简化过程中丢失较多信息，嵌入到模型几何结构图后，需要在几何结构图中恢复输入骨架的原始结构。由于简化骨架嵌入到几何结构图的关节点已知，通过在几何结构图上计算关节点之间最短路径，并依据原始输入骨骼关节比例，在最短路径上插值计算被简化掉的关节点，从而恢复输入骨架的原始结构。

Discrete Penalty Function

为了判定输入骨架嵌入效果的质量，需要定义骨架嵌入损失函数，以惩罚不符合要求的嵌入结果。一个好的骨架嵌入需要同时满足通用的约束条件(例如骨架比例、朝向、大小与输入骨架近似)，以及针对输入骨架的特定条件(例如关节对称性、"脚"关节嵌入位置位于模型较低位置)等。由于很难定义一个通用的惩罚函数覆盖所有的约束条件，该文定义了九个独立的惩罚函数基，分别对应不同的约束条件。通过线性组合惩罚函数基得到最终的惩罚函数。

定义模型几何结构图为 $G$ ；原始输入骨架结构图为 $S_i$ ，简化的输入骨架结构图为 $S_r$ ， $S_r$ 嵌入到图 $G$ 中的骨架结构图为 $S_e$ ； $S_i$ 中的骨骼定义为 $B_i$ ， $S_r$ 中的骨骼定义为 $B_r$ ， $S_e$ 中的骨骼定义为 $B_e$ ；骨骼即为所定义的骨架结构图中的边。定义 $s^{c \to d}_{a \to b}(x)$ 为受边界约束的线性插值函数。当 $x<a$ 时取值为 $b$ ，而 $x>c$ 时取值为 $d$ ，在边界内取值为 $b+(d-b)(x-a)/(c-a)$ 。九个独立的惩罚函数基定义如下[2]:

Short Bones

惩罚过短的骨骼。假设组成某个 $B_e$ 的关节点坐标分别为 $v_1$ 和 $v_2$ ，关节点对应的填充球的半径为 $r_1$ 和 $r_2$ 。两个关节点在图 $G$ 中的最小路径长度为 $d$ ，而在为简化的原始输入骨架中的路径为 $d'$ 。过短骨骼的惩罚函数定义为：
$(s^{2 \to 3}_{0.5 \to 0}(\frac{d'}{d+0.7(r_1+r_2)}))^3$

Improper Orientation between Joints

定义相邻骨骼(先后连接关系)或者共享同一个父关节的两根骨骼为骨骼对，该惩罚函数惩罚输入骨骼对{ ${B_{r1}, B_{r2}}$ }与嵌入骨骼对{ ${B_{e1}, B_{e2}}$ }方向的不一致。定义{ ${B_{r1}, B_{r2}}$ }的(非共享)关节点坐标为 $v_1$ 和 $v_2$ ，{ ${B_{e1}, B_{e2}}$ }对应的关节点坐标为 $s_1$ 和 $s_2$ 。计算向量 $v_1-v_2$ 和 $s_1-s_2$ 之间夹角的余弦值 $c$ 。如果 $c<\alpha_1$ 惩罚值为无穷大，否则惩罚值为 $0.5max(0, \alpha_2 \cdot (1-c)^2-\alpha_3)$ 。其中：如果骨骼对中两个骨骼之间是相邻关系，则 $(\alpha_1, \alpha_2, \alpha_3)=(0, 16, 0.1)$ ；如果两者共享同一个父关节，则 $(\alpha_1, \alpha_2, \alpha_3)=(-0.5, 4, 0.5)$ 。

Length Differences in Bones Marked Symmetric

惩罚对称骨骼对的长度不一致。定义 $B_{r1}$ 和 $B_{r2}$ 为对称骨骼对，其对应的嵌入骨骼 $B_{e1}$ 和 $B_{e2}$ 的关节点和填充球半径分别为 $(v_1, r_1),(v_2, r_2), (v_3, r_3), (v_4, r_4)$ ， $B_{e1}$ 和 $B_{e2}$ 的长度为 $d_1＝||v_1-v_2||_2$ 和 $d_2＝||v_3-v_4||_2$ 。定义如下函数：
$q=0.2max(\frac{d_1}{d_2}, \frac{d_2}{d_1})+0.8max(\frac{d_1}{d_2+0.7(r_3+r_4)},\frac{d_2}{d_1+0.7(r_1+r_2)})$
则该惩罚函数的计算为 $max(0, q^3-1.2)$

Bone Chains Sharing Vertices

惩罚共享顶点的骨骼。如果多根骨骼共享同一个顶点，并且顶点到几何物体表面的距离小于0.02，则惩罚函数值为无穷大。假设一个骨骼嵌入到一条由顶点序列{ $v_1, v_2, \dots, v_n$ }定义的路径，其中 $v_n$ 为父节点， $v_1$ 为根节点。 $S$ 是与先前嵌入骨骼共享，且位于顶点序列内的顶点子集。惩罚函数定义为： $0.5+\sum_{v_i \in S}\frac{1}{2i^2}$

Joints Marked as 'Feet'

惩罚标记为脚的关节点不是位于几何物体模型底部。惩罚函数定义为 $G$ 中 $y_{min}$ 与脚关节 $y$ 值的差值。

Zero-Length Bone Chains

惩罚长度为0的骨骼。如果一个关节与其父关节嵌入到同一个关节，即 $S_e$ 中两个节点重叠，则惩罚值为1。

Improper Orientation of Bones

惩罚骨架朝向的不一致。依据简化骨架嵌入图 $S_e$ ，在经过关节的最短路径上插入度为2的关节点，恢复跟原始输入骨架图 $S_i$ 拓扑结构一致的骨架嵌入。设 $\overline{u}'$ 和 $\overline{u}$ 分别为嵌入前和潜入后对应骨骼的向量，则两个骨骼朝向不一致的惩罚定义为：
$50||\overline{u}'||^2((1-c)s^{0 \to 1}_{-0.5 \to 6}(c))^2$
其中 $c=\overline{u}' \cdot \overline{u} / ||\overline{u}'|| ||\overline{u}||$
整个骨架的朝向不一致则通过累加所有对应骨骼朝向不一致的惩罚值得到。

Degree-one Joints not embedded at Extreme Vertices

惩罚距离父节点没有足够远，且度为1的节点。假设 $S_e$ 中某节点 $v_2$ 的父节点为 $v_1$ ，其临近的位于 $G$ 中的节点为 $v_3$ 。节点 $v_3$ 的填充半径大于节点 $v_2$ 的填充半径的1/2，并且满足如下两个约束条件：
$\frac{(v_2-v1)\cdot(v_3-v1)}{||v_2-v1||||(v_3-v1||} \geq 0.95$
和
$\frac{(v_2-v1)\cdot(v_3-v2)}{||v_2-v1||||(v_3-v2||} \geq 0.8$
则惩罚值为1。此外，如果节点 $v_3$ 的条虫半径大于节点 $v_2$ 的填充半径的1/2，并且满足如下约束条件：
$\frac{(v_3-v1)\cdot(v_1-v2)}{||v_3-v1||||(v_1-v2||} \geq 0.8$
则算法避免在节点 $v_1$ 嵌入度为1的骨骼关节点。

Joints Far along Bone-chains but Close in the Graph

惩罚 $S_r$ 中两个在节点路径上相距较远，但距离很近的骨骼关节点。定义任意两个关节点 $v_1$ 和 $v_2$ ，如果
$2d(v_1, v_2) + r_1 + r_2 < d(v_1, v_L)+d(v_2, v_L)$
则惩罚值为1。其中 $d$ 为两个节点在图的路径上的距离。 $r_1$ 和 $r_2$ 是两个点对应的填充球的半径。 $v_L$ 是两个节点的最近公共祖先节点。

对于任意嵌入 $v$ ，其惩罚函数定义为： $f(v)=\sum_{i=1}^{9}\gamma_ib_i(v)$ 。其中 $b_i(v)$ 对应如上的惩罚函数基， $\gamma_i$ 为对应的权重系数。可通过基于最大化最小间距的SVM训练得到。按照如上的定义顺序，各惩罚函数基最终的权重为 $(0.27, 0.23, 0.07, 0.46, 0.14, 0.12, 0.72, 0.05, 0.33)$ 。具体训练过程见附录。

Discrete Embedding

由于 $S_e$ 的嵌入方式随骨骼关节点呈指数增长，很难直接整体优化离散的惩罚函数。论文通过分支界限法(branch-and-bound)，针对骨架部分嵌入(partial embedding)估算下界，然后采用 $A^*$ 算法，逐步增加骨骼嵌入，从而得到惩罚值最小的嵌入方式。具体方式为：

步骤一： 构造一个关于骨架部分嵌入的优先队列。队列按照当前部分骨架嵌入的惩罚函数值由小到大排列。
步骤二： 从当前列表中选择最好的部分骨架嵌入，评估增加下一根骨骼所有可能嵌入方式，计算增加骨骼后的部分嵌入惩罚函数值，并添加到优先队列中。
步骤三： 重复步骤二，直到队列中出现第一个完全的骨架嵌入。此嵌入即为最佳的嵌入，有最小的惩罚函数值。

为了加速计算过程，定义部分嵌入的下界阈值。如果某个部分嵌入的下界超过了指定的阈值，说明该嵌入的惩罚值太高，则直接丢弃而无需添加到队列中。

$S_e$ 中骨骼关键点按照定义的顺序连接，每个关节点给定索引值，其中根节点索引值为1，关节点总数为 $r$ 。对于索引值为 $i(1<i<r)$ 的关节点，其父关节点定义为 $p_R(i), p_R(i)<i$ 。惩罚函数定义为：
$f(v_1,\dots,v_r)=\sum^{r}_{i=2}f_i(v_i, v_{p_R(i)})+\sum^{r}_{i=2}f_D(v_1, \dots, v_i)$
其中第一项为所有独立骨骼( $v_i, v_{p_R(i)}$ )的惩罚值之和；第二项为不同骨骼关节之间相互依赖的惩罚值。 $f$ 按上节中定义方式计算。

对于只包含首 $k$ 个关节的部分嵌入，其下界估算公式为：
$\sum^{k}_{i=2}f_i(v_i, v_{p_R(i)})+\sum^{k}_{i=2}f_D(v_1, \dots, v_i) + \sum_{i>k | p_R(i) \leq k}min_{v_i \in V}f_i(v_i, v_{p_R(i)})$
前两项与上述公式中各项含义相同，第三项则描述了所有本身不在首 $k$ 个关节，但其父节点在首 $k$ 个关节的独立骨骼的最小惩罚值。

在基于下界的优化过程中，骨骼的嵌入顺序对优化性能有重要影响。度较高的骨骼需要被优先嵌入，因为高自由度骨骼可以覆盖更多的嵌入可能性，从而保证第三项中的估计值能够尽可能低，从而更加准确的逼近真实下界。

Embedding Refinement

通过上述离散优化过程，从简化输入骨架 $S_r$ 在模型几何结构图 $G$ 中所有可能的嵌入{ $S_e$ }中，得到最优的简化骨骼嵌入。寻找嵌入骨架 $S_e$ 中骨骼在 $G$ 中的最短路径，并基于输入骨骼 $S_i$ 的比例尺寸，插值增加度为2的骨骼关节点，恢复与原始输入骨架 $S_i$ 相同拓扑结构的嵌入骨架。

恢复的骨架与几何模型的拓扑近似，但通常情况下还会存在局部区域不一致，尤其是较小骨骼的朝向可能不正确，主要是上述优化过程中，较小骨架的影响权重较小导致。由于恢复的嵌入骨架位置大致正确，可以采用连续性优化方法。定义恢复的嵌入骨架为 $(q_1,\dots, q_s), s=18$ ，连续性优化函数为：
$g(q_1,\dots, q_s)=\alpha_Ag^A(q_1, \dots, q_s)+\sum_{i=2}^{s}g_i(q_i, q_{p_S(i)})$
其中 $p_{S(i)}$ 表示索引值为 $i$ 的关节点的父节点索引值。第一项为非对称惩罚项，第二项 $g_i=\alpha_Sg_i^{S}+\alpha_Lg_i^{L}+\alpha_Og_i^{O}$ ，分别描述了骨骼嵌入离中心面较远的惩罚，骨骼太短的惩罚，以及嵌入骨骼与输入骨骼朝向不一致的惩罚。

Asymmetry Penalty

惩罚输入骨架中标记为对称的骨骼对，但在嵌入后骨骼对非对称情况。假设关节点为 $(q_1, q_2)$ 和 $(q_3, q_4)$ 的两个嵌入骨骼，在输入骨架中标记为对称骨骼，则惩罚函数定义为：
$max(1.05, \frac{||q_1-q_2||^2}{||q_3-q_4||^2}, \frac{||q_3-q_4||^2}{||q_1-q_2||^2})$
$g_A$ 描述了所有标记为对称骨骼的非对称惩罚值之和。

Far-from-center Embedding Bones Penalty

惩罚嵌入骨骼离模型中心太远的情况。在每根骨骼上随机采样10个坐标点。针对每个采样点 $q_i$ ，定义如下的惩罚函数：
$r(0.003, min(m(q_i), 0.001+max(0, 0.05+s(q_i))))$
其中 $m(q_i)$ 表示点 $q_i$ 离最近中值面采样点的距离。 $s(q_i)$ 表示该该点处的符号距离。对于惩罚函数 $r(a, x)$ ，如果 $x<a$ 则取值为0，否则取值为 $x^2$ 。

Too Short Bones Penalty

惩罚嵌入结果太短的骨骼。假设 $(q_1, q_2)$ 和 $(s_1, s_2)$ 的分别表示嵌入后和嵌入前的骨骼的关节点坐标，定义如下惩罚函数：
$max(0.5, \frac{||s_2-s_1||^2}{((q_2-q_1) \cdot (s_2-s_1))^2/||s_2-s_1||^2})$

Orientation Improperly Penalty

惩罚骨骼嵌入前后的朝向不一致。假设 $(q_1, q_2)$ 和 $(s_1, s_2)$ 的分别表示嵌入后和嵌入前的骨骼的关节点坐标。 $\theta$ 为向量 $q_1-q_2$ 和 $s_1-s_2$ 的夹角。如果 $\theta>0$ ，则 $(0.3+0.5\theta)^3$ ；否则 $10 \cdot (0.3+0.5\theta)^3$ 。

实际优化过程中，各系数取经验值 $(\alpha_A, \alpha_S, \alpha_L, \alpha_O)=(1, 15000,0.25,2)$ 。优化前后的效果如下所示：

骨骼嵌入优化前后对比图[1]

Skin Attachment

蒙皮绑定的目的是关联嵌入骨架与几何物体的表面。利用骨骼驱动几何物体变形最常用的方式是线性融合蒙皮(Linear Blend Skinning, LBS)。对于几何物体表面的顶点 $v_j$ ，设 $T^i$ 是顶点周围嵌入骨骼 $i$ 的变换矩阵， $w^i_j$ 是骨骼 $i$ 对顶点 $j$ 的变形影响权重系数。依据LBS计算顶点变化后的运动为：
$v_j{'}=\sum_iw_j^iT^i(v_j)$
蒙皮绑定的目的就是求解每根骨骼对每个顶点的权重系数。好的权重系数求解算法需要满足如下的条件：

不依赖于几何物体的顶点分布的分辨率；
权重系数在几何物体表面的分布需要足够光滑；
两个骨骼连接处权重过渡区的宽度需要与连接处关节点到物体表面的距离近似成比例。

该文使用热传导平衡方程求解几何物体表面温度。假设几何体内部是绝缘导热体，即几何体内部可以热传导，但对外无热交换。每根骨骼对几何表面的权重系数，可以通过定义当前骨骼的温度为1，其它骨骼温度为0，计算整个系统在热传导平衡态下的温度分布，此时几何体表面的温度即为权重系数。由于计算热传导需要离散几何体内空间，为了简化计算，只在表面计算热平衡方程。此外，考虑每个顶点与其最邻近骨骼温差产生的热传输(此时并不计算邻近骨骼的热传导过程)。每根骨骼 $i$ 对几何体所有顶点的热传输达到平衡态的描述为：
$\frac{\partial{\textbf{w}^i}}{\partial{t}}=\Delta{\textbf{w}^i}+\textbf{H}(\textbf{p}^i-\textbf{w}^i)＝0$
其中，最左边项描述了该点在时间上的温度变化，变化为0表示没有温度变化，即为平衡态；右边第一项是该点领域内的对其温度变化的贡献，第二项则描述了最邻近的骨骼由于温差传递的热量。如果当前骨骼对某个顶点而言是最邻近的，则 $p^i＝1$ ，否则为0。 $H$ 为对角线矩阵，对角线元素 $H_{jj}=c/d(j)^2$ ，其中 $d(j)$ 是顶点 $j$ 离其最近骨骼的距离， $c$ 为常数1。如果顶点到最近骨骼连接的线段不是完全位于几何体内部，说明该顶点与骨骼不是最邻近的连通域，则 $H_{jj}=0$ 。一种典型的情况是，离腰部侧身轮廓上顶点最近的骨骼有可能是臂骨骼，此时不应受其骨骼的热传导影响。

为了进一步理解，对于当前骨骼某个顶点，如果该骨骼为该点最邻近的骨骼，则该顶点的达到平衡态的方程为：
$\frac{\partial{w}}{\partial{t}}=\Delta{w}+c/d^2 \cdot(1-w)＝0$

Appendix

Training Weighs of Discrete Penalty Functions

在骨架嵌入的过程中，需要用到9个独立的惩罚函数基。通过对函数基系数加权求和，得到任意骨骼的惩罚函数。由于很难通过手动调节出较好的系数，文章通过采用基于支持向量机(Support Vector Machine, SVM)的半自动化方式学习各惩罚函数的加权系数。

考虑给定的加权系数 $\Gamma=(\gamma_1,...,\gamma_k)$ ，对一个指定的几何模型，提供若干骨架嵌入样本，并人为判定标记为“好”或者“坏”(此时，由于 $\Gamma$ 并不是最优的，因此不能依据惩罚值确定好坏，而是由人观察判断确定)。对于一个骨架嵌入 $v$ ，其惩罚值为 $f(v)=\sum^k_{i=1}\gamma_ib_i(v)$ 。假设 $p_1, \dots, p_m$ 为 $m$ 个 $k$ 维的好嵌入， $q_1, \dots, q_n$ 为 $n$ 个 $k$ 维的坏嵌入。

一个好的 $\Gamma$ 值应该保证当惩罚值 $f(v)$ 取最小值时，对应的嵌入也应该是好的。即由算法优化判断出来的好的嵌入(算法认为惩罚值最小时就是好的判断)，由人判断是也的确是好的嵌入。因此，好的 $\Gamma$ 需要能够区分出当前惩罚值最小的好嵌入和惩罚值最小的坏嵌入，即最大化两个惩罚值：
$min_{i=1}^n\Gamma^Tq_i-min_{i=1}^m\Gamma^Tp_i$
简单来说，即当前有两个嵌入，由人判定分别为好的骨架嵌入和坏的骨架嵌入。计算两个嵌入的惩罚值， $\Gamma$ 需要最大化两个惩罚值的差值。
实际优化过程中，在训练集中所有类型的几何模型的所有嵌入上优化如上目标函数。假设训练集中有 $C$ 类几何模型，每类几何模型有 $(m_i+n_i), i=1,...,C$ 个嵌入。则整体的目标优化函数为：
$\sum_{k=1}^C min_{i=1}^{n_k}\Gamma^Tq_i^k-min_{i=1}^{m_k}\Gamma^Tp_i^k$
其中 $p_i^k$ 和 $q_i^k$ 分别为第 $k$ 类几何模型的第 $i$ 个好嵌入和第 $i$ 个坏嵌入。

Learning Procedure

选择一组几何模型，手动选择 $\Gamma$ 初始值。依据离散嵌入优化过程，得到当前 $\Gamma$ 值下算法认为的最优嵌入(惩罚函数极值点)。由于 $\Gamma$ 值是任意选取的，因此这个嵌入在人观察判断后，极有可能是不好的嵌入。通过手动调整 $\Gamma$ 值，保证每个模型的嵌入都是好的。 $\Gamma$ 的优化采用Nelder-Mead方法，即从一个位于 $[0, 1]^k$ 空间的随机 $\Gamma$ 开始，通过Nelder-Mead方法得到一个当前优化解。以包含该优化解的较小立方体空间进行下一次迭代，直到每个模型的嵌入都是好的。

然后利用最大化最小间距的优化，在当前数据集上优化，得到当前使间距最大的 $\Gamma$ 值。以此 $\Gamma$ 来运行离散嵌入优化过程，从而得到一批新的骨架嵌入。对于新计算的骨架嵌入，通过观察判断并手动进行分类为好和坏的嵌入，并添加到当前的训练集中。

重复上面的过程，直到 $\Gamma$ 不产生明显的变化为止。每次迭代都会增加一些新的嵌入。在该文中，当嵌入总数约为400时， $\Gamma$ 趋于稳定，在最终的 $\Gamma$ 下运行离散嵌入优化过程，所有的模型得到的嵌入结果都是好的。

参考文献

[1] Automatic Rigging and Animation of 3D Characters
[2] Penalty Functions for Automatic Rigging and Animation of 3D Characters