度量的球面嵌入(Spherical Metric Embedding)算法

仅给定三角网格的所有边长,已知网格所有顶点位于以原点为球心、半径为R的球面上,如何在欧氏空间中得到符合度量的所有点的坐标?

在离散黎曼几何中,里奇流(Ricci Flow)、卡拉比流(Calabi Flow)、Yamabe Flow等几何学流动的结果都是一组度量(Metric)的形式,即我们直到的仅仅是结果的一组边长。在基于这些方法的平面参数化里,必须将结果嵌入到欧氏空间中得到所有点的坐标。

将度量嵌入到欧氏空间,或者说从边长得到坐标,是一个看似简单实则坑点满满的问题,常规的数值优化方法常常会陷入局部最优无法自拔。对于一般情形下的解决方法,可以参阅SIGGRAPH 2018的一篇论文Shape From Metric。本文介绍的是一个特殊得多的球面情况——已知网格所有顶点位于以原点为球心、半径为R的球面上。

对于平面的情况,可以参阅这篇文章


球线相交法

在球面上,我们可以很容易地先嵌入第一条边AB。

接着,对于已嵌入的边AB,在三角形ABC中,已知AB坐标、|AC|和|BC|。下面为了描述方便,我们令A(x_0, y_0, z_0)B(x_1, y_1, z_1)C(x_2, y_2, z_2)|AC|=l_0|BC|=l_1。显然,我们有以下关系:

\left\{\begin{matrix} x_2^2 + y_2^2 + z_2^2 = R^2 & (1)\\ (x_2-x_0)^2 + (y_2-y_0)^2 + (z_2-z_0)^2 = l_0^2 & (2) \\ (x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2 = l_1^2 & (3) \end{matrix}\right.

可以得到:

\left\{\begin{matrix} x_2^2 + y_2^2 + z_2^2 = R^2 & (1)\\2x_0x_2+2y_0y_2+2z_0z_2=l_0^2-x_0^2-y_0^2-z_0^2-R^2=l_0^2-2R^2 & (2)-(1)\\ 2x_1x_2+2y_1y_2+2z_1z_2=l_1^2-x_1^2-y_1^2-z_1^2-R^2=l_1^2-2R^2 & (3)-(1) \end{matrix}\right.

观察上面的方程组,由于仅有C(x_2, y_2, z_2)为未知量,因此(1)为一球面方程,而(2)-(1)和(3)-(1)为空间直线的一般式,从几何角度看,这个方程相当于求球与直线的相交点

由于所求的直线相交点有2个,因此必须对其作出筛选。一种可行的方法是向量。令三角形ABC逆时针方向的法向量n_1、原点到ABC重心的向量n_2,规定嵌入过程中n_1n_2的内积恒为正或恒为负,即可每次从得到唯一满足条件的C(x_2, y_2, z_2)

此外,在实际求解过程中要注意的一点是,各种解法大多涉及除以x_0x_1y_0y_1z_0z_1这些系数来达到消元的目的,这时需要考虑中一个或多个数为0或近似0的情形,否则将导致最后嵌入的误差较大或者直接崩溃。

 

称谓(*)
邮箱
留言(*)