求解 3D 多边形网格的最佳对齐问题
我正在尝试实现一个几何模板引擎。其中一个部分是采用原型多边形网格并将实例与较大对象中的某些点对齐。
因此，问题是这样的：给定多边形网格中某些（可能是全部）顶点的 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 将最小化顶点和这些位置之间的距离？该方法最好能够推广到任意网格，而不仅仅是立方体。
I'm trying to implement a geometry templating engine. One of the parts is taking a prototypical polygonal mesh and aligning an instantiation with some points in the larger object.
So, the problem is this: given 3d point positions for some (perhaps all) of the verts in a polygonal mesh, find a scaled rotation that minimizes the difference between the transformed verts and the given point positions. I also have a centerpoint that can remain fixed, if that helps. The correspondence between the verts and the 3d locations is fixed.
I'm thinking this could be done by solving for the coefficients of a transformation matrix, but I'm a little unsure how to build the system to solve.
An example of this is a cube. The prototype would be the unit cube, centered at the origin, with vert indices:
4----5
|\ \
| 6----7
| | |
0 | 1 |
\| |
2----3
An example of the vert locations to fit:
- 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
So, given that prototype and those points, how do I find the single scale factor, and the rotation about x, y, and z that will minimize the distance between the verts and those positions? It would be best for the method to be generalizable to an arbitrary mesh, not just a cube.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
假设您拥有所有点及其对应关系，您可以通过解决最小二乘问题来微调您的匹配：
其中
T是您要查找的变换矩阵，V 是要拟合的顶点，M 是原型的顶点。范数指的是弗罗贝尼乌斯范数。 M 和 V 是 3xN 矩阵，其中每列是原型顶点和拟合顶点集中对应顶点的 3 向量。 T 是 3x3 变换矩阵。那么最小化均方误差的变换矩阵是inverse(V*transpose(V))*V*transpose(M)。生成的矩阵通常不是正交的（您想要一个没有剪切的矩阵），因此您可以解决矩阵 Procrustes 问题以找到与 SVD 最近的正交矩阵。现在，如果您不知道哪些给定点将对应于哪些原型点，则您要解决的问题称为表面配准。这是一个活跃的研究领域。例如，请参阅本文，其中还涵盖了严格配准，这就是您所要做的后。
Assuming you have all points and their correspondences, you can fine-tune your match by solving the least squares problem:
where
Tis the transformation matrix you are looking for, V are the vertices to fit, and M are the vertices of the prototype. Norm refers to the Frobenius norm. M and V are 3xN matrices where each column is a 3-vector of a vertex of the prototype and corresponding vertex in the fitting vertex set. T is a 3x3 transformation matrix. Then the transformation matrix that minimizes the mean squared error isinverse(V*transpose(V))*V*transpose(M). The resulting matrix will in general not be orthogonal (you wanted one which has no shear), so you can solve a matrix Procrustes problem to find the nearest orthogonal matrix with the SVD.Now, if you don't know which given points will correspond to which prototype points, the problem you want to solve is called surface registration. This is an active field of research. See for example this paper, which also covers rigid registration, which is what you're after.
如果您想在任意 3D 几何体上创建网格，这不是通常的做法。
您应该查看八叉树网格生成技术。如果您使用真正的 3D 图元（这意味着四面体而不是立方体），您将会取得更大的成功。
如果您的几何体是 3D 实体，那么您所拥有的只是表面描述。确定“最佳”内部点没有意义，因为你没有任何内部点。您会希望它们的排列方式使内部的四面体不会太扭曲，但这是您能做到的最好的。
If you want to create a mesh on an arbitrary 3D geometry, this is not the way it's typically done.
You should look at octree mesh generation techniques. You'll have better success if you work with a true 3D primitive, which means tetrahedra instead of cubes.
If your geometry is a 3D body, all you'll have is a surface description to start with. Determining "optimal" interior points isn't meaningful, because you don't have any. You'll want them to be arranged in such a way that the tetrahedra inside aren't too distorted, but that's the best you'll be able to do.