As-rigid-as possible shape manipulation: 第一步算法详解

论文算法的处理对象是所有三角形的三个顶点,在第一步算法中,定义一个三角形为

那么我们现在定义一个关于这个三角形的局部坐标系。

如果以向量

为局部坐标系 x 轴的正方向,把这个向量逆时针旋转 90° 定义为局部坐标系 y 轴的正方向。如下图所示。

就得到了一个关于这个三角形的局部坐标系,进而得到局部坐标

这个局部坐标的意思是,该点(v₂)相对于其他两个点(v₀ v₁)的坐标。

那么现在可以把v₂表示成v₀ v₁的线性表达式。如下公式。

其中

当图形发生变形,图形内部的每个三角形也发生变形,把变形后的三角形表示为

如下图所示。为了尽量使变形后的三角形保持原来的形状

我们期望变形后三角形的 v₂' 要尽可能接近原始三角形中的 v₂。在这里表示为

。如上图,保有原始三角形中的 v₂ 的局部坐标 (x₀₁, y₀₁) 的

。用如下公式表达。

和 v₂‘ 之间的误差可表示为

那么最小化这个误差就是刚才说的“尽量使变形后的三角形保持原来的形状”的数学含义

我们在Mathematica软件中可以推导公式。

如上Mathematica代码中,代码可视化效果非常接近于手写公式,我们先定义三角形三个顶点的表示,旋转矩阵的表示,

的表示。然后使用Mathematica函数Expand[]展开。得到如下表达式。

输出的公式太长,不便于观看。

我们知道

展开一定是关于 v' 的等式。

也可表达成系数矩阵的形式。

在Mathematica中继续写程序,展开系数矩阵G 。

输出结果为:

考虑最小化

。刚才说到

展开一定是关于 v' 的等式。也就是以 v' 内各个坐标为变量的函数。

本算法以三角形为单位,三角形的三个顶点都要计算一次误差函数。

可以得到

对每个三角形内三个点的误差加和,得到

我们把所有的点 v’ 分为自由点 u 控制点 q,再把误差函数按照 u 和 q 的顺序重新排列系数矩阵,可以得到。

最小化误差,需要对自由点 u 求偏导,并使偏导值为0。

用 G' 和 B 来重写这个等式。

注意到G'和B都是固定的矩阵。因为矩阵元素都是由类似于局部坐标 (x₀₁, y₀₁)的组合组成的,而这些局部坐标都是来自于输入的原始图形中的那些三角形,所以G'和B可以在程序输入图形后做一次预计算即可。另外控制点 q 是随用户的拖动而实时变化的,q的坐标我们可以实时获取。

所以这个等式中,只有自由点 u 是未知量,我们只需要对 u 求导。上述过程因为只涉及到方程求解,计算量很小,可以实时计算。

至此,这一步算法我们详解结束,在下一篇文章中,我们将把这些公式用C++代码实现。

本文分享自微信公众号 - 无雨森的技术分享(forestsen_tech)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券