Match a 3D submesh-template in main mesh

I am in python loading 3D models as meshes (their data consists of vertices, normals and faces). I want to find their connectable points. These connection points are modeled the same way in every of these models: either a cylindrical pin as male connector or a hole as female connector. However, the model dataset doesn't contain the connection points, so I want to infer them via code.

This means: I am trying to match and locate all occurences of a template mesh that I specify and create once for every connector type (one male + one female template) in a greater model mesh.

I am going to illustrate what I mean with LEGO pieces:

Piece A: hole connection/female	Piece B: pin connection/male

find location of these holes	find location of these pin halves

I thought this would be a pretty standard task to do and there would be some libraries where I can just proivde a mesh and I get all occurences of this mesh in my main mesh. However, I cant seem to find any. So, I am wondering if my approach to this problem is wrong, and if it's even possible. While researching, I had some other ideas:

instead of finding the male connector in male mesh, try to insert the female mesh. This seems to not be a great idea
convert to pointcloud and use pointcloud analysis. However, I'm not sure if this helps
convert model to graph and try to find a sub-graph. However, I don't know how i should convert the models. Maybe rasterizing/voxelizing beforehand.
check every vertex myself and try to complete the sub-mesh from there. However, coding this from scratch would be error prone, and I would like a robust solution that maybe even has some tolerance when matching the sub-meshes.

So, my questions are:

How is this problem called, so I can research more?
What is the typical/best approach? This is done as data preprocessing, so it doesn't need to run in real-time. I am in python.

Thank you!

Solution

For what I understand, this would fall under the category of partial shape retrieval/matching problems.

A classification was proposed already some time ago in Tangelder, J. W., & Veltkamp, R. C. (2004). A survey of content based 3D shape retrieval methods. Proceedings Shape Modeling Applications, 2004., 145-156. Basically the resolution methods can fall into a few distinct categories such as: feature based, graph based and geometry based. Only local features and graphs are adapted to partial matching according to this article.

For potential experimentations using Python:

Local features can be computed using for example PyMeshLab (it can compute different geometric information like curvature, geodesic distance, or local vertex density) and then somehow compared with existing meshes. This comparison step is the hard part in my opinion and I don't think there is a good answer.
Meshes are already graphs (vertices connected by edges, forming faces) so you could indeed compare graphs, using for example the VF2 algorithm of the NetworkX library. However, note that the "subgraph isomorphism problem is NP-complete" as said in the doc so concretely it doesn't scale well. You could also try to segment your mesh into patches (planar, cylindrical, etc.) and make a graph out of it, but same limitation.

You could also use a matching/registration algorithm such as the ICP provided for example by Open3D. This is however very sensitive to the initial alignment/position of the meshes.

Another solution would be to use deep learning and segmentation. If you have a list of examples that is big enough (and a lot of time to correctly label your data), you could try sampling your mesh and using the PointNet model using for example Keras. This would result in a list of labels associated your points that are themselves associated to a particular class like "pin" or "hole".

But unfortunately for you, I don't think this is a "pretty standard task" :(