optimization - 解决 3d 多边形网格的最佳对齐问题

Question

我正在尝试实现一个几何模板引擎。其中一个部分是采用原型(prototype)多边形网格并将实例化与较大对象中的某些点对齐。

所以，问题是这样的:给定多边形网格中某些(可能是所有)顶点的 3d 点位置，找到一个缩放旋转，使变换后的顶点和给定点位置之间的差异最小化。如果有帮助，我还有一个可以保持固定的中心点。顶点和 3d 位置之间的对应关系是固定的。

我认为这可以通过求解变换矩阵的系数来完成，但我有点不确定如何构建系统来求解。

这方面的一个例子是立方体。原型(prototype)将是单位立方体，以原点为中心，带有顶点索引:

4----5
|\    \
| 6----7
| |    |
0 |  1 |
 \|    |
  2----3

适合的顶点位置示例:

• v0: 1.243,2.163,-3.426
• v1: 4.190,-0.408,-0.485
• v2:-1.974，-1.525，-3.426
• v3:0.974，-4.096，-0.485
• v5: 1.974,1.525,3.426
• v7: -1.243,-2.163,3.426

那么，给定原型(prototype)和那些点，我如何找到单个比例因子，以及关于 x、y 和 z 的旋转，以最小化顶点和那些位置之间的距离？最好将该方法推广到任意网格，而不仅仅是立方体。

Answer 1

假设您有所有点及其对应关系，您可以通过解决最小二乘问题来微调您的匹配:

minimize Norm(T*V-M)

其中 T 是您要查找的变换矩阵，V 是要拟合的顶点，M 是原型(prototype)的顶点。范数是指 Frobenius 范数。 M 和 V 是 3xN 矩阵，其中每一列是原型(prototype)顶点和拟合顶点集中相应顶点的 3 向量。 T 是一个 3x3 变换矩阵。那么最小化均方误差的变换矩阵是inverse(V*transpose(V))*V*transpose(M)。生成的矩阵通常不是正交的(您想要一个没有剪切的矩阵)，因此您可以解决矩阵 Procrustes 问题以使用 SVD 找到最近的正交矩阵。

现在，如果您不知道哪些给定点将对应于哪些原型(prototype)点，您要解决的问题称为表面配准。这是一个活跃的研究领域。参见示例 this paper ，其中还包括严格的注册，这就是您所追求的。