CODEWITHSUNDEEP
c++algorithmcollision-detectionphysicscollision
Petipo
Petipo

Reputation: 31

Good way to handle collisions between mass-spring systems

I am programming a C++ simulation application in which several mass-spring structures will move and collide and I'm currently struggling with the collision detection and response part. These structures might or might not be closed (it might be a "ball" or just a chain of masses and springs) so it is (I think) impossible to use a "classic" approach where we test for 2 overlapping shapes.

Furthermore, the collisions are a really important part of that simulation and I need them to be as accurate as possible, both in terms of detection and response (real time is not a constraint here). I want to be able to know the forces applied to each Nodes (the masses), as far as possible.

At the moment I am detecting collisions between Nodes and springs at each time step, and the detection seems to work. I can compute the time of collision between one node and a spring, and thus find the exact position of the collision. However, I am not sure if this is the right approach for this problem and after lots of researches I can't quite find a way to make things work properly, mainly on the response aspect of the collisions.

Thus I would really like to hear from any technique, algorithm or library that seems well suited for this kind of collisions problems or any idea you might have to make this work. Really, any kind of help will be greatly appreciated.

Upvotes: 1

Views: 1414

Answers (2)

Penguino
Penguino

Reputation: 2176

If you can meet the following conditions:

 0) All collisions are locally binary - that is to say 
    collisions only occur for pairs of particles, not triples etc, 
 1) you can predict the future time for a collision between 
    objects i and j from knowledge of their dynamics (assuming that no other
    collision occurs first)
 2) you know how to process the physics/dynamicseac of the collision

then you should be able to do the following:

Let Tpq be the predicted time for a collision between particles p and q, and Vp (Vq) be a structure holding the local dynamics of each particle p (q) (i.e its velocity, position, spring-constants, whatever)

For n particles...

Initialise by calculating all Tpq (p,q in 1..n)
Store the n^2 values of Tpq in a Priority Queue (PQ)
repeat
  extract first Tpq from the PQ
  Advance the time to Tpq
  process the collision (i.e. update Vp and Vq according to your dynamics)
  remove all Tpi, and Tiq (i in 1..n) from the PQ
    // these will be invalid now as the changes in Vp, Vq means the
    // previously calculated collision of p and q with any other particle
    // i might occur sooner, later or not at all
  recalculate new Tpi and Tiq (i in 1..n) and insert in the PQ
until done

There is an o(n^2) initial setup cost, but the repeat loop should be O(nlogn) - the cost of removing and replacing the 2n-1 invalidated collisions. This is fairly efficient for moderate numbers of particles (up to hundreds). It has the benefit that you only need to process things at collision time, rather than for equally spaced time steps. This makes things particularly efficient for a sparsely populated simulation.

Upvotes: 1

Chaos
Chaos

Reputation: 382

I guess an octree approach would do best with your problem. An octree devides the virtual space into several recursive leaves of a tree and lets you compute possible collisions between the most probable nodes.

Here a short introduction: http://www.flipcode.com/archives/Introduction_To_Octrees.shtml :)

Upvotes: 0

Related Questions