Solving for optimal alignment of 3d polygonal mesh

Question

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.

Answer 1

Assuming you have all points and their correspondences, you can fine-tune your match by solving the least squares problem:

minimize Norm(T*V-M)

where T is 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 is inverse(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.

Answer 2

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.