how to align two meshes

Question

I have a very nice & tricky question for you. I need to align two meshes using a very fast algorithm. Given mesh1 and mesh2 I want to find how I need to traslate and rotate mesh1 to be in the same position of mesh2. Firstly I did this using inertia moments of the two meshes, but the algorithm does not work if the second mesh is similar to the first one but with some missing parts. In other words, take two identical meshes and from one of them cut same parts off.

I'd like to write the code in C because I need to perform that on multiplatform machines (linux/win) and do that in a very fast way: it has to be put into a GA algorithm.

The two meshes are in STL (stereolitography) format (binary or ascii) but maybe can be useful using another kind of file format.

Do you have any idea how to perform this stuff?

question update:

first of all I want to thank you guys very much for all your suggestions. I've downloaded an install PCL on my machine and compiled the ICP (tutorial) algorithm successfully, taken from PCL web site. But now I have some questions about that, maybe because for me is a brand new thing. what is the meaning of the 4x4 matrix output for the fitness? I should expect a rotational matrix and a traslational vector..

I hope some of you can help me. If you need any other info please ask.

Answer 1

Point Cloud Library has several resources that you may find useful. As @Throwback1986 says, ICP is one excellent algorithm for aligning geometry. Pcl also features other, often faster alignment algorithms, based on identifying and matching features of interest in two pieces of geometry. The library finds a lot of use in the robotics communities, who, like you, are very performance conscious.

Pcl is written in c++. While not as portable as straight C, They offer installation instructions for windows, a few *nix flavors, and mac os. I've seen it running on ios and android as well. Check out the tutorials.

Answer 2

Iterative Closest Point (ICP) is one way of registering (aligning) 3D point clouds with rigid transformations. (It can also apply to meshes.)

Here is a good introduction: http://www.cs.duke.edu/courses/spring07/cps296.2/scribe_notes/lecture24.pdf

Here is a reasonable summary: students.asl.ethz.ch/upl_pdf/314-report.pdf

Here is a matlab implementation: http://www.mathworks.com/matlabcentral/fileexchange/12627-iterative-closest-point-method

Here are some potential optimizations: http://www.cs.princeton.edu/~smr/papers/fasticp/