Skip to main content
GameDev.net gamedev.net
🔒 Locked

multi-body collision

Started by LiuWei Oct 10, 2010 at 4:57 PM 4 replies 2.6k views
Original Post
LiuWei
LiuWei
I have a multi-body collision question. I knew how to deal with collision detection and response if only two objects involved, but when there are many objects, if we deal with them one by one, or say, sequentially, then managed objects maybe affected by unmanaged objects later, especially when objects speed is relatively high.
I just thought about this problem when I did cloth simulation; people use a method called "zone" to include area collision then treat it as a whole.
But I am thinking can we use some systematically method, put something in a matrix, then solve it?

Please enlighten me.
MoundS
MoundS
If I understand your post correctly, I think your problem is that you're advancing some of your objects to the end of the frame before you even check the rest of your objects for collisions.

What I do is search through ALL the objects and find the pair that collides first. If that collision happens after the end of the frame, then you're done. You just advance all your objects to the end of the frame. If the collision happens during the frame, you advance ALL your objects to the time of the collision, apply the collision reponse to those two objects, and then repeat the whole process.

Of course, when I did this, it was for bouncing balls. I'm not familiar with cloth simulation, but I assume you can use the same idea.
LiuWei
LiuWei
thank you for you reply,
I just realized it should not be called multi-body collision
you are right; that is a method to solve this problem, you mean find the potential collision pairs and do some response, that find the potential collision pairs again.... till no collision, right?
I am thinking if there exists a method which we can find all potential collisions in one iteration,
such as the bouncing ball example you said, if in the first iteration, we only find A and B will collide, then we do some collision response, but then B will collide C since B's velocity is changed.
can we have some method to directly find all collisions, both A and B and B and C, simultaneously, using some optimization method?
MoundS
MoundS
Well, calculating the collision between B and C relies on information that you only have after you've processed the collision reponse from A and B, so I'm not sure how you can calculate them simultaneously.

There is some room for improvement in the method I describe though. You don't have to recalculate ALL the potential collisions from scratch each iteration. You only have to recalculate collisions that involve the two balls that change in response to the collision. For example, if there's another ball D that doesn't collide with anything in the first iteration, then after you process the A-B collision, you have to recheck A-B, A-C, A-D, B-C, and B-D, but not C-D. It's extra work to keep track of all this, but in a more realistic simulation with lots of objects, it might be worth it.
WindowRunner
WindowRunner
Unfortunately I don't know anything about the "zone" method.
In Ian Millington's book "Game Physics Engine Development" he proposes an iterative approximation.
He starts by finding the worst contact point, the one with the greatest penetration depth, and solves that one first in a single time step. He then updates all other contact points that reference the same two colliding rigid bodies with the new calculated positions & orientation, which in turn will either decrease or increase their penetration depth. He then repeats this until all penetration depths are gone or the max amount of iterations has been reached.

So the contact point from A & B will update/adjust the contact point from B & C, and in this way you account for all relevant collisions at once. Not 100% accurate since the proper order of events aren't observed but is a simple enough concept to implement.

It's in Chapter 14 of the book.
Send me a message if you're interested in reading it and don't have access to the book.

Pseudo Code:
//big multiplier => more robust & longer to solveunsigned MaxIterations = NumCurContacts * 4;ContactIter itrWorstPt, itrRelatedContact;Vector3 LinearChange[2];Vector3 AngularChange[2];Vector3 deltaPosition;for(unsigned numIter=0; numIter<MaxIterations; ++numIter){  itrWorstPt = max_element(Contacts.begin(), Contacts.end(), CompPenDepth);  if(itrWorstPt->PenDepth < 0.01f)    break;//they are all small enough to stop  //this will update the two rigid bodies  //update the new PenDepth,which should be ~ 0  //also cache the linear and angular change;  itrWorstPt->ApplyResolution();  itrWorstPt->GetLinAngChange(LinearChange, AngularChange);    //for each rigid body involved with Worst Contact Point  for(unsigned i=0; i<2; ++i)  {    //find relevant contact points    ContactList &       GuysToCheck = AssociatedContacts[ itrWorstPt->RigidBody->GetID() ];    //update their penetration depths    for(itrRelatedContact = GuysToCheck.begin();       itrRelatedContact!=GuysToCheck.end();       ++itrRelatedContact)    {      if(itrRelatedContact->RigidBody[0]==itrWorstPt->RigidBody)      { //note RelativeContactPosition = ContactLoc - RigidBody->Center        deltaPosition = LinearChange + Cross(AngularChange, itrRelatedContact->RelativeContactPosition[0]);        itrRelatedContact->PenDepth -= Dot(deltaPosition, itrRelatedContact->ConNormal);      }else      {        deltaPosition = LinearChange + Cross(AngularChange, itrRelatedContact->RelativeContactPosition[1]);        itrRelatedContact->PenDepth += Dot(deltaPosition, itrRelatedContact->ConNormal);      }    }//end relevant contacts loop  }//end two rigid body loop}//end MaxIterations loop
LiuWei
LiuWei
thank you very much, guys;
Some guys told me that it doesn't work to find and correct all collisions in a single iteration, since that will not be a static model (no idea what's the meaning of it)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.