Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


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.

  • You cannot reply to this topic
80 replies to this topic

#1 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

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?

Sponsor:

#2 wildbunny   Members   -  Reputation: 550

Like
0Likes
Like

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.

#3 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

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...

#4 wildbunny   Members   -  Reputation: 550

Like
0Likes
Like

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.




#5 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

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 >.<

#6 wildbunny   Members   -  Reputation: 550

Like
0Likes
Like

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.

#7 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

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??
*.*

#8 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

Posted 04 March 2011 - 09:25 AM

Me needs more explanation, puh lease +.+a

#9 wildbunny   Members   -  Reputation: 550

Like
0Likes
Like

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   -  Reputation: 116

Like
0Likes
Like

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!

Thanks in advance!

#11 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

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'

#12 wildbunny   Members   -  Reputation: 550

Like
0Likes
Like

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.

#13 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

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...

#14 wildbunny   Members   -  Reputation: 550

Like
0Likes
Like

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 :)

#15 Bow_vernon   Members   -  Reputation: 137

Like
0Likes
Like

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...

#16 erwincoumans   Members   -  Reputation: 272

Like
1Likes
Like

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.

You can check out a Windows demo here:http://code.google.com/p/bullet/downloads/detail?name=SpeculativeContactsWin32.zip
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

#17 Dirk Gregorius   Members   -  Reputation: 817

Like
0Likes
Like

Posted 04 March 2011 - 09:49 PM

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

#18 Dirk Gregorius   Members   -  Reputation: 817

Like
0Likes
Like

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.

#19 erwincoumans   Members   -  Reputation: 272

Like
0Likes
Like

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

#20 Dirk Gregorius   Members   -  Reputation: 817

Like
0Likes
Like

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.



PARTNERS