How to find if a 3D object fits in another 3D obje

问题:

Given two 3d objects, how can I find if one fits inside the second (and find the location of the object in the container).

The object should be translated and rotated to fit the container - but not modified otherwise.

Additional complications:

1. The same situation - but look for the best fit solution, even if it's not a proper match (minimize the volume of the object that doesn't fit in the container)

2. Support for elastic objects - find the best fit while minimizing the "distortion" in the objects

This is a pretty general question - and I don't expect a complete solution. Any pointers to relevant papers \ articles \ libraries \ tools would be useful

回答1:

Here is one perhaps less than ideal method.

You could try fixing the position (in 3D space) of 1 shape. Placing the other shape on top of that shape. Then create links that connect one point in shape to a point in the other shape. Then simulate what happens when the links are pulled equally tight. Causing the point that isn't fixed to rotate and translate until it's stable.

If the fit is loose enough, you could use only 3 links (the bare minimum number of links for 3D) and try every possible combination. However, for tighter fit fits, you'll need more links, perhaps enough to place them on every point of the shape with the least number of points. Which means you'll some method to determine how to place the links, which is not trivial.

回答2:

This seems like quite hard problem. Probable approach is to have some heuristic to suggest transformation and than check is it good one. If transformation moves object only slightly out of interior (e.g. on one part) than make slightly adjust to transformation and test it. If object is 'lot' out (e.g. on same/all axis on both sides) than make new heuristic guess.

Just an general idea for a heuristic. Make a rasterisation of an objects with same pixel size. It can be octree of an object volume. Make connectivity graph between pixels. Check subgraph isomorphism between graphs. If there is a subgraph than that position is for a testing.

This approach also supports 90deg rotation(s).

Some tests can be done even on graphs. If all volume neighbours of a subgraph are in larger graph, than object is in.

In general this is 'refined' boundary box approach.

回答3:

Another solution is to project equal number of points on both objects and do a least squares best fit on the point sets. The point sets probably will not be ordered the same so iterating between the least squares best fit and a reordering of points so that the points on both objects are close to same order. The equation development for this is a lot of algebra but not conceptually complicated.

回答4:

Consider one polygon(triangle) in the target object. For this polygon, find the equivalent polygon in the other geometry (source), ie. the length of the sides, angle between the edges, area should all be the same. If there's just one match, find the rigid transform matrix, that alters the vertices that way : X' = M*X. Since X' AND X are known for all the points on the matched polygons, this should be doable with linear algebra.

If you want a one-one mapping between the vertices of the polygon, traverse the edges of the polygons in the same order, and make a lookup table that maps each vertex one one poly to a vertex in another. If you have a half edge data structure of your 3d object that'll simplify this process a great deal.

If you find more than one matching polygon, traverse the source polygon from both the points, and keep matching their neighbouring polygons with the target polygons. Continue until one of them breaks, after which you can do the same steps as the one-match version.

There're more serious solutions that're listed here, but I think the method above will work as well.

回答5:

What a juicy problem !. As is typical in computational geometry this problem can be very complicated with a mismatched geometric abstraction. With all kinds of if-else cases etc. But pick the right abstraction and the solution becomes trivial with few sub-cases.

Compute the Distance Transform of your shapes and Voilà! Your solution is trivial. Allow me to elaborate.

The distance map of a shape on a grid (pixels) encodes the distance of the closest point on the shape's border to that pixel. It can be computed in both directions outwards or inwards into the shape. In this problem, the outward distance map suffices.

• Step 1: Compute the distance map of both shapes D_S1, D_S2
• Step 2: Subtract the distance maps. Diff = D_S1-D_S2
• Step 3: if Diff has only positive values. Then your shapes can be contained in each other(+ve => S1 bigger than S2 -ve => S2 bigger than S1) If the Diff has both positive and negative values, the shapes intersect.

There you have it. Enjoy !