I have an uncommon problem. There are 2 3D objects, which are represented by arr

Question

I have an uncommon problem. There are 2 3D objects, which are represented by arrays of vertices and triangles (.stl files). Each of them contains a big enough amount of vertices: 1-10 mln ones. The surfaces of these models are rough, and can contain different spikes or hollows.

The aim is to determine path of one these objects, when it moves with contact on the surface of the other one. Moreover, the algorithm should consider how many degrees of freedom are available. In every case there are only 2 objects and one of them is fixed.

Example, object M1 moves on a surface of object M2, which is fixed. It's necessary to move M1 from point A to B. For M1 it's also available one more degree of freedom - along the axis (let's call it AC) perpendicular to AB. So, the path can be only the curve in the plane (AC, AB). But due to this path, during the motion M1 should always has at least one contact point.

I tried to perform it with collision detection algorithm, but it seems it will be very complicated calculations for ordinary computers. Can anybody advise some algorithms, libraries or concepts how to perform this idea? P.S. I use C, C++ and Java.

Explanation / Answer

One problem is figuring out how the free object can move (e.g. flips along some axis, or translation movements). The other problem is determining how far the free object can move, where it makes contact again with the fixed object (i.e. the collision detection).

I assume that this collision detection is the bottleneck. You can vastly reduce the number of calculations required if you simplify the shape of your objects (i.e. reduce the number of vertices). However, the simplified object must be larger than the actual object. When doing collision detection, you start with a copy of the reduced model. When you find a collision, then you add the vertices etc. from the full-detail model to the copy

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.