求解 3D 多边形网格的最佳对齐问题

Question

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

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

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

一个例子是立方体。原型是单位立方体，以原点为中心，具有顶点索引：

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

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

Answer 1

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

minimize Norm(T*V-M)

在哪里 T 是您要寻找的变换矩阵，V 是要拟合的顶点，M 是原型的顶点。范数指的是弗罗贝尼乌斯范数。M 和 V 是 3xN 矩阵，其中每列是原型顶点和拟合顶点集中对应顶点的 3 向量。T 是 3x3 变换矩阵。那么最小化均方误差的变换矩阵是 inverse(V*transpose(V))*V*transpose(M). 。生成的矩阵通常不是正交的（您想要一个没有剪切的矩阵），因此您可以解决矩阵 Procrustes 问题以找到与 SVD 最近的正交矩阵。

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

Answer 2

如果您想在任意 3D 几何体上创建网格，这不是通常的做法。

您应该查看八叉树网格生成技术。如果您使用真正的 3D 图元（这意味着四面体而不是立方体），您将会取得更大的成功。

如果您的几何体是 3D 实体，那么您所拥有的只是表面描述。确定“最佳”内部点没有意义，因为您没有任何内部点。您会希望它们的排列方式使得内部的四面体不会太扭曲，但这是您能做到的最好的。