• FEATURED

View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Sweep test and physics

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

80 replies to this topic

#1Bow_vernon  Members

Posted 03 March 2011 - 06:06 PM

Ok, Im worried about tunneling now, and I guess the best thing to do is a sweep test. now how to do it. with many objects there are many TOI. what do I do with them? and what is this "it may stuck, Bow!" my friend said on the phone? sadly he isnt able to explain more(on vacation). any suggestion?

#2wildbunny  Members

Posted 04 March 2011 - 03:40 AM

Ok, Im worried about tunneling now, and I guess the best thing to do is a sweep test. now how to do it. with many objects there are many TOI. what do I do with them? and what is this "it may stuck, Bow!" my friend said on the phone? sadly he isnt able to explain more(on vacation). any suggestion?

Ok, first let me say this: there is no way to avoid penetration in all cases. You *will* have to deal with it at some point, so all your collision detection/response routines will have to be able to detect and recover from it.

Secondly, dealing with lots of TOI events from multiple simultaneous collisions is *hard* and can be *very* slow. I faced this problem when writing the physics engine on little big planet psp...

The solution (and i can't take credit for it, unfortunately) is not to do it. Instead you need to use what i'm going to call 'predictive contacts'. These are detected by your usual time stepping collision detection code - there are several ways to do this, the most simple is to just use a closest points between objects routine.

These predictive contacts should do *no work* in the solver until the collision is due to happen, and when they do act, they don't remove all the relative normal velocity, they only remove exactly the right amount to bring the object to exactly touch the surface.

Thats the basic gist of it anyway, really this needs its own article and demo - if you'd like to see one please register your interest in this thread

Cheers, Paul.

#3Bow_vernon  Members

Posted 04 March 2011 - 04:53 AM

Eh? of course Im all interested. I know it's unvoidable, Im just trying to avoid tunnelling with a minimum of fuss. Im not used to CCD, what do I do with TOI? what should I add to the integration scheme (with the TOI)? Anyway, I dont need accurate TOI. Just a 'safe' value is enough. Thanks...

#4wildbunny  Members

Posted 04 March 2011 - 05:40 AM

Eh? of course Im all interested. I know it's unvoidable, Im just trying to avoid tunnelling with a minimum of fuss. Im not used to CCD, what do I do with TOI? what should I add to the integration scheme (with the TOI)? Anyway, I dont need accurate TOI. Just a 'safe' value is enough. Thanks...

I'm saying you might want to consider forgetting about TOI completely, use predictive contacts and let your contact solver do the hard work for you...

If you really must use TOI events then i would sit down on paper and draw out a bunch of different scenarios with several objects colliding in the next time-step each with different TOIs and note what happens when you solve each scenario in a certain order. Then switch the order around and try again - you'll notice it leads to a different outcome each time. The TOI events must be processed from earliest to latest...

If enough people chime in on this thread then i will consider writing the predictive contacts thing up formally with a demo

Cheers, Paul.

#5Bow_vernon  Members

Posted 04 March 2011 - 06:29 AM

Ok, Im very scared of tunnelling, ya know especially with small sized objects. I'll forget the TOI altogether, ok. Oh man if we wait for enough people in this thread, Im affraid it will take a long time...
I'll wait though, oops Im too happy and cant wait to see it >.<

#6wildbunny  Members

Posted 04 March 2011 - 07:55 AM

Ok, Im very scared of tunnelling, ya know especially with small sized objects. I'll forget the TOI altogether, ok. Oh man if we wait for enough people in this thread, Im affraid it will take a long time...
I'll wait though, oops Im too happy and cant wait to see it >.<

Maybe i can explain using a simple example

• Ok, take a small sized sphere object, travelling very quickly towards the ground.
• Around the sphere, form a bounding box which encompasses the sphere on the current frame AND where the sphere will travel to on the next frame. Lets call this the swept bounding box.
• If this swept bounding box intersects the ground on the current frame, there will possibly be a collision on the next frame.
• So, we generate a predictive contact for the sphere and the ground. The simplest way to do this, is just to pick the closest points between the two objects as the collision points, and the normal is the unit length vector between these two points.
• At contact solve time, the predictive contact will remove *only* the portion of the relative normal velocity that would cause the sphere to just touch the ground on the following frame.

Thats the gist of it - I've over simplified here for example purposes but that should get you started

Cheers, Paul.

#7Bow_vernon  Members

Posted 04 March 2011 - 09:18 AM

Im confused +.+a suppose I get the predictive CP, but at the current frame and the objects havent collided yet. Should I solve the predictive contact? that's weird. The objectsarent intersecting but we've solved CP. Or Im missing something??
*.*

#8Bow_vernon  Members

Posted 04 March 2011 - 09:25 AM

Me needs more explanation, puh lease +.+a

#9wildbunny  Members

Posted 04 March 2011 - 10:00 AM

Me needs more explanation, puh lease +.+a

Because you know the objects will have collided somewhere between the current frame and next frame, its ok to solve the predictive contact on the current frame, because after you've solved it and the next frame rolls around, the objects will be just touching

Basically, you're throwing away some of the time involved in the collision by doing this, but in practice it looks totally unnoticeable

Cheers, Paul.

#10__MosteM__  Members

Posted 04 March 2011 - 10:30 AM

Hey wildbunny,

I'm really interested in this topic. An article about it from you would be great!

#11Bow_vernon  Members

Posted 04 March 2011 - 10:31 AM

Ok I'll try this, but theoritically there could exist a 'accumulated' energy gain, which could be a problem later. Anyway, why choose box as the swept shape? why not swept sphere? Since you mention 'take the sphere of the small shapes'

#12wildbunny  Members

Posted 04 March 2011 - 10:34 AM

Ok I'll try this, but theoritically there could exist a 'accumulated' energy gain, which could be a problem later. Anyway, why choose box as the swept shape? why not swept sphere? Since you mention 'take the sphere of the small shapes'

There isn't any noticeable energy gain - just play little big planet and you'll see

The swept bounding box is just for broad phase collision detection...

Cheers, Paul.

#13Bow_vernon  Members

Posted 04 March 2011 - 10:47 AM

for broad phase? you mean AABB? anyway like Mostem said, an article or source code or proof of concept would be great! Thanks in advance...right now Im working on how to generate contacts from two colliding OBB...

#14wildbunny  Members

Posted 04 March 2011 - 11:15 AM

for broad phase? you mean AABB? anyway like Mostem said, an article or source code or proof of concept would be great! Thanks in advance...right now Im working on how to generate contacts from two colliding OBB...

Yes, the AABB contains the sphere this frame and where it will be next frame - its bounded swept motion.

The contact points need to be on the sphere and the ground, not the AABB

#15Bow_vernon  Members

Posted 04 March 2011 - 02:12 PM

Ok, but ermmm sorry if I mind you, but...ehm can you give me a small 'demo' to proof the concept? teehee. I dont have the little big planet CD to install...I cant even download it...

#16erwincoumans  Members

Posted 04 March 2011 - 09:10 PM

I created a proof of concept for predictive contacts in the Bullet SDK, thanks Paul for motivating me to do this. We discussed speculative contacts previously here.

and see the minimal changes needed to enable them in this commit: http://code.google.c...e/detail?r=2326
The demo allows you to toggle between predictive contacts and conservative advancement using the P key. Shoot boxes using mouse button or . key.

In a nutshell, expand the bounding boxes with the motion, and for predictive contacts (with positive distance) adjust the constraint solver target velocity,
so that after integration the object will be in touching contact.

Cheers,
Erwin

#17Dirk Gregorius  Members

Posted 04 March 2011 - 09:49 PM

How do you guys deal with restitution when using predictive contacts?

#18Dirk Gregorius  Members

Posted 04 March 2011 - 09:55 PM

I also don't believe that predictive contacts avoid tunneling reliable. You can still easily rotate of the world.

#19erwincoumans  Members

Posted 04 March 2011 - 11:24 PM

How do you guys deal with restitution when using predictive contacts?

Combining it with restitution requires some more work beyond my proof of concept implementation.

I also don't believe that predictive contacts avoid tunneling reliable. You can still easily rotate of the world.

I've seen several AAA games using predictive contacts to help preventing tunneling (sometimes combined with other techniques). There are several possible artifacts with predictive contacts, such as resolving contacts that didn't actually happen, but those game companies took those for granted. You can notice this effect in the demo when shooting boxes with the right mouse button. DonDickieD's "rotate of the world" issue is a separate issue: predictive contacts bring the objects into touching contact. From there you can generate multiple contact points using your favorite method to avoid tunneling.

Let's stay on-topic: the links I provided show a sweep test using conservative advancement as well as a proof of concept of predictive contacts, as requested.
Here is the actual code to modify the right hand side of the contact setup to enable predictive contacts:

btScalar	velocityError = restitution - rel_vel;
if (penetration>0)
{

// predictive contact: adjust the velocity error to allow to bring the objects into touching contact
// positive penetration values means separating/closest distance

positionalError = 0;
velocityError -= penetration / infoGlobal.m_timeStep;
} else
{
positionalError = -penetration * infoGlobal.m_erp/infoGlobal.m_timeStep;
}

Thanks,
Erwin

#20Dirk Gregorius  Members

Posted 05 March 2011 - 10:25 AM

Erwin, I like to look at the demo and it doesn't run for me. Is this 64bit? Can you recompile it or add it to the Bullet trunk please.

Thanks,
-Dirk

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.