4

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.

Eugene
  • 169
  • 4

1 Answers1

2

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 – but only in the region around the collision! You then resume collision detection with the full detail. For the next movement, you restart collision detection with a new copy of the low-detail model.

This dynamic-detail strategy can be cascaded multiple times. If each level has only half the number of vertices compared with the previous level, then reducing the number of vertices from 10 million to less than thousand would require 14 levels of detail. Less vertices means less calculations to do during collision detection, although storing the multiple levels requires more memory.

amon
  • 132,749
  • 27
  • 279
  • 375