Speculative Contacts – a continuous collision engine approach

Iteration 1
Submit to StumbleUpon

Hello and welcome back to my blog…

Today i’m going to talk about a continuous collision detection technique called Speculative Contacts which has been employed in games such as Little Big Planet PS3 and PSP versions.

First of all we need to answer some basic questions.

What is continuous collision detection?

Continuous collision detection attempts to solve the bullet through paper problem as shown in Figure 1.

Figure 1

In Figure 1, object A is travelling so fast that within one frame it has passed straight through object B.

With traditional time-stepping techniques (i.e. an intersection check on each frame), this case is missed.

This is the first part of the problem (and actually the easiest part to solve). The second part of the problem is how you deal with many simultaneous collisions within one frame, the so called Time Of Impact ordering problem.

Figure 2

So in Figure 2, we’ve gone ahead and found the exact time of impact between A and B and we’re happy until C comes along and messes everything up by colliding with A before A collides with B.

This turns out to be a real pain in the ass in general because it means that the collision detection problem is no longer separated from the act of moving objects around, its now very closely tied to it which means everything suddenly gets a lot more expensive to compute.

To solve this problem you need to treat all collisions in TOI (Time Of Impact) order, from the earliest TOI in the scene to the latest.

And even if you do that, you might find that as you resolve each collision, the trajectory of the objects changes so much that now objects that you didn’t expect to be colliding at all, are now in fact colliding.

Figure 3

In Figure 3, A collides with B and is resolved, but A‘s new velocity causes it to collide with C which wasn’t originally expected by the collision system. This cannoning problem means that collision detection must be re-performed as each TOI impact is processed, which can get very expensive.

To mitigate this problem, typically each object is bounded by a box which contains the object at the start and end of the time-step, and then all such boxes which overlap are considered to reside within a TOI island, wherein any objects are candidates for collision with any other object in the island.

This is all very tiresome and expensive, it would be nice if there was just some magic solution to all these problems, or at least some acceptable approximation…

Speculative Contacts

Enter speculative contacts. The basic idea is to try and move the majority of the work out of the collision detection system and into the contact solver, which is designed for finding the ‘global correct solution’ to problems involving many simultaneous interacting influences (either through projected-gauss-seidel ref: Erin Catto of the excellent Box2d, or other methods).

Figure 4

In Figure 4, we compute the closest distance d between the two objects; the idea is that we want to remove exactly the right amount of velocity from A such that it will be exactly in touching contact with B on the next frame. This is the essence of the speculative contacts technique.

Figure 5

Figure 5 shows where we want to see A on the next frame. Note that this is cheating slightly because we’re throwing away time – compared to Figure 3, you can see that the motion of A is cut short; it no longer rolls across B as it used to. It postpones the secondary motion of A to the next frame.

Its very important that the speculative contact do no work (i.e. not have any influence on other objects) unless the relative normal velocity is greater than the distance between the objects divided by the time-step.

Figure 6

In Figure 6, v.n is less than the distance d (divided by time-step) – i.e. A will not touch B next frame, so the constraint should do nothing.

Contact con = contacts[i];
Vector2 n = con.m_normal;
 
// get all of relative normal velocity
double relNv = (con.m_b.m_Vel-con.m_a.m_Vel).Dot(n);
 
// we want to remove only the amount which leaves them touching next frame
double remove = relNv + con.m_dist/Constants.kTimeStep;
 
if (remove < 0)
{
	// compute impulse
	double imp = remove / (con.m_a.m_InvMass + con.m_b.m_InvMass);
 
	// apply impulse
	con.m_a.m_Vel += imp * n * con.m_a.m_InvMass;
	con.m_b.m_Vel -= imp * n * con.m_b.m_InvMass;
}

The above code fragment demonstrates the calculation involved to achieve the result in Figure 5, for a non rotating body. Note, this is simplified for understandability.

Stability

Stability is a measure of how stable a simulation is – i.e how much jittering is present, or how well the simulation copes with big piles of objects.

I just wanted to compare and contrast the discrete method for collision resolution at this point because i think it will prove very interesting.

In discrete collision detection, the above code fragment might look like this:

UPDATE: since i wrote this article a number of people contacted me and quite rightly pointed out that i didn’t include any penetration resolution in the discrete solver; the main reason was that i didn’t want to make the discrete solver look worse than it was in the simplest of demos – i often found that penetration resolution would actually cause a solver to jitter more than if it weren’t there at all.

However, by not including it i made the more complex demos behave more poorly than they should have, since they would tend to sink and sag more than they should. I have since updated all the live demos and code snippits to include penetration resolution.

Contact con = contacts[i];
Vector2 n = con.m_normal;
 
// get all of relative normal velocity
double relNv = (con.m_b.m_Vel-con.m_a.m_Vel).Dot(n);
 
// remove all of it + resolve penetration over the course of some frames
double remove = relNv + 0.4 * (con.m_dist + 1) / Constants.kTimeStep;
 
// but only when objects are intersecting and moving towards each other
if (remove < 0 && con.m_dist < 0)
{
	double imp = remove / (con.m_a.m_InvMass + con.m_b.m_InvMass);
 
	// apply impulse
	con.m_a.m_Vel += imp * n * con.m_a.m_InvMass;
	con.m_b.m_Vel -= imp * n * con.m_b.m_InvMass;
}

Note that probably you would never even get to the above code when the objects are separated in a discrete collision system (since why would you run the contact solver on separated objects?), but for comparison purposes i’ve converted the original code to be discrete.

Now, the actual difference between these two pieces of code is tiny, but the difference the speculative method makes to the stability of the simulation is amazing.

In all the demos on this page, the time-step is fixed to 1 / 30 of a second.

Install Microsoft Silverlight

You can pick the ball up by dragging it.

In this simple example, a frictionless ball is resting on the concave intersection of two rectangles; note the slight jittery motion of the ball. In this example there is no penetration resolution at all, and the solver defaults to the discrete code above running 1 iteration only.

The jittering present in this most simple of examples exemplifies the problem facing all physics engines which deal with the collision problem in a discrete manor – its a real PITA to solve.

The chief reason for it is this condition check (taken from the above code):

if (/*remove < 0 &&*/ con.m_dist < 0)
{
...
}

The check for intersection. The reason this causes the jittering is because it forces the contact to activate and deactivate constantly as the collision is resolved and then unresolved frame after frame.

A quick trace of the number of contacts solved on the first few frames confirms it:

  1. 1
  2. 1
  3. 1
  4. 2
  5. 1
  6. 2
  7. 1
  8. 2

Now, click on the drop-down labelled ’discrete’ and change the mode to speculative. Notice the jittering is gone?

The same trace this time looks like this:

  1. 2
  2. 0
  3. 1
  4. 2
  5. 2
  6. 2
  7. 2
  8. 2

Much more pleasing – the resolved contact count stabilises quite quickly leading to a much more stable simulation.

double remove = relNv + con.m_dist/Constants.kTimeStep;
 
if (remove < 0)
{
...
}

The above is the speculative code; the only difference is the handling of what relative normal velocity to remove. The speculative code always removes enough of the relative normal velocity for the object to just touch the surface on the next frame. The contact is now not getting turned on/off so often, and this makes all the difference.

Install Microsoft Silverlight

The above example defaults to a speculative solver, with a lot more balls. Note that there is still only one iteration! If you change the solver mode to discrete you can see the difference it makes.

I’ve included a sequential discrete solver in the drop down for comparison – even at 10 iterations the system isn’t fully resolved.

Angular

No article discussing continuous collision detection and resolution would be complete without attempting to address angular continuous collision. That is, when an object rotates very quickly it should still not miss collisions.

Figure 8

In Figure 8, we would still like to be able to detect the collision of A with B even though A is very thin and rotating very quickly.

Luckily, speculative contacts do trap this case, simply by using the closest points between objects a pretty good approximation can be made with the time of collision. Its not perfect, but it does a reasonable job.

Install Microsoft Silverlight

As you can see in the above demo, the collision is handled, although the exact point of collision can be slightly wrong in some cases.

It can also handle the following case which crops up a lot in production code.

Figure 9

In Figure 9, A is moving toward B quickly and with no rotation, the ensuing collision causes a fast rotation on A, which would cause the right side of A to penetrate B on the next frame. But by simply building the contact set as you would for any discrete collision system and adding both contacts, the case is handled just fine, even with only a few iterations of the solver.

Install Microsoft Silverlight

Goodbye TOI ordering

Ok, so now we have the simple stuff out of the way, we can get into the really interesting part; using a simple modification of the speculative code we can actually move the TOI ordering problem out of the collision detection system and into the constraint solver.

But first we need to cover the basics of using a solver to approach the globally correct solution to the problem of constraint resolution.

Globally correct

This is a little bit tricky to describe but it basically describes a situation where all constraints have been resolved, but only just – i.e there was no constraint after the solver has run which is over-resolved (too much correction).

The problem is mainly due to the uni-lateral contact constraint, which is only allowed to ‘push’ objects apart but never ‘pull’ them together; otherwise objects would stick together like glue.

Because contacts are only allowed to push, they have no mechanism available to them to counter adjust themselves – imagine a situation where solving one contact causes another contact to be solved ‘too much’ (relative normal velocity now positive rather than 0), this over corrected contact can do nothing about this problem. The result is an unstable simulation.

The solution is to use a solver, such as Erin Catto’s sequential impulse system which allows the uni-lateral constraints to push and pull during the iterations, but still ensures that the resulting final impulse only pushes. Please see his GDC slides for a much better explanation.

If it sounds confusing, don’t worry, the actual code associated with it is rather simple by comparison.

TOI joy

Ok, so now we have a global solver we can finally tackle the TOI problem. What we do is make a small change to the speculative code:

Contact con = contacts[i];
Vector2 n = con.m_normal;
 
// get all of relative normal velocity
double relNv = (con.m_b.m_Vel-con.m_a.m_Vel).Dot(n);
 
// we want to remove only the amount which leaves them touching next frame
double remove = relNv + con.m_dist/Constants.kTimeStep;
 
// compute impulse
double imp = remove / (con.m_a.m_InvMass + con.m_b.m_InvMass);
 
// accumulate
double newImpulse = Math.Min(imp + con.m_impulse, 0);
 
// compute change
double change = newImpulse - con.m_impulse;
 
// store accumulated impulse
con.m_impusle = newImpulse;
 
// apply impulse
con.m_a.m_Vel += change * n * con.m_a.m_InvMass;
con.m_b.m_Vel -= change * n * con.m_b.m_InvMass;

Notice the condition checking for negative relative normal velocity has gone, to be replaced by a clamp inside the impulse calculation, and the impulse is accumulated. This allows the system to converge towards the global solution.

Install Microsoft Silverlight

In the above demo, the balls are constrained on the y axis (you can move them by dragging them) and the ghost balls represent where the solid colour balls will end up next frame.

In the start scenario of this demo, red collides first with blue before later colliding with green, which should leave red hanging in the air incorrectly, as per the diagram in Figure 7

Figure 7

Because the mode is set to ‘speculative sequential’ this situation is handled correctly. If you change mode to simple ‘speculative’ you will see the difference.

Here is a step by step of what is happening over a course of 3 iterations (remember its the ghost balls we want to see colliding with each other):

Iteration 1

On the first iteration, red collides with blue first before green collides with blue at an earlier TOI leaving red in the air as per usual.

Iteration 2

On the second iteration, the motion of red which was postponed is now allowed to continue by the global solver (allowing pull as well as push during the iterations), but the collision isn’t resolved yet.

Iteration 3

The third iteration sees the solution converging to the correct global solution.

By moving the TOI ordering problem inside the constraint solver like this, we completely avoid having to do all the hard work in the collision detection phase.

The number of solver iterations used will affect the quality of the result, as ever.

Other advantages

I just wanted to touch on a few other advantages that speculative contacts give:

  • No collision threshold required – because we don’t have the discrete collision problem of toggling between colliding/not colliding we don’t need to mitigate this by having a collision threshold around objects.
  • No inner hull required – now that distance is a fundamental part of the constraint system we don’t need to try and avoid penetration by shrinking our collision hulls by some radius which can cause problems with triangular objects.
  • No need to distinguish between objects which are considered to be ‘fast’ and have special treatment in collision detection terms. All objects can go through the same system. This means you can have things which have previously been impossible, like a fast moving stack of blocks which all collide with the floor and each other.

Problems

Of course no technique is without its associated problems. The most notable problem suffered by speculative contacts is the problem of so called ‘ghost’ collisions.

Figure 10

In Figure 10, the closest points between A and B are shown, but due to the motion of A, a ghost collision will be generated where A incorrectly collides with the plane of the collision normal on B.

In practice the problem is less apparent for circles than it is for polygons. The correct way to solve this problem is to use a technique such as Conservative Advancement, ref Erwin Coumans of Bullet fame, rather than a simple closest points between objects approach as detailed in this article.

The second problem is that if an object is warped into severe penetration it will tend to ping back out again rather than smoothly correct to zero penetration. This can be solved by splitting the distance equation up for negative / positive, but i’ve not included that in this article for clarity’s sake.

Update

I just realised i’ve committed a physics faux par by not including a demo of the physics engine ‘hello world’ – the traditional Pile ‘O Boxes. So here it is, for your delectation. Running in only 3 iterations, the stability is impressive. I’ve updated the source code to contain this demo as well – if you already bought it and want this, just post a comment and i’ll email you the updated code for free :)

Install Microsoft Silverlight

Conclusion

I believe that speculative contacts are very well suited to physics simulation in computer games where the requirement for speed over absolute accuracy is a good fit for the technique. If you still remain unconvinced, buy a copy of Little Big Planet and have a play around with the ‘create mode’ – see if you can break it; its pretty robust.

Source code

If you found this article useful and would like to see more like this, please consider buying the source-code which i have made available on this page for a small cost – this will allow an indie developer like me to justify his existence for another month, and more importantly pay for things like food and rent!

After purchasing, you will be redirected to a page where you can download the source-code of every example in this article, written in c# and requires silverlight to build.

USD 6.99

Subscribers can access the source here

Have fun,

Cheers, Paul.

Submit to StumbleUpon

About Paul Firth

A games industry veteran of ten years, seven of which spent at Sony Computer Entertainment Europe, he has had key technical roles on triple-A titles like the Bafta Award Winning Little Big Planet (PSP), 24: The Game (PS2), special effects work on Heavenly Sword (PS3), some in-show graphics on the BBC’s version of Robot Wars, the TV show, as well as a few more obscure projects.   Now joint CEO of Wildbunny, he is able to give himself hiccups simply by coughing.   1NobNQ88UoYePFi5QbibuRJP3TtLhh65Jp
This entry was posted in Collision Detection, Physics, Silverlight, Technical and tagged , , , . Bookmark the permalink.

158 Responses to Speculative Contacts – a continuous collision engine approach

  1. raigan says:

    Excellent article! I have a couple questions:

    In Fig 5, shouldn’t the future position of A be further to the right? Currently it looks like A’s movement is being truncated, when really it should be projected straight above the future position in Fig 4… unless I’m missing something.

    Secondly, do you handle circles specially? Specifically, the contact normal n isn’t well-defined for two circles (i.e you can’t just use a fixed value, it changes as the circles move position) which means you have to calculate closest points/contact normal immediately before solving the constraint. Is this something that you do with all contact pairs, or just circle-circle pairs? I suppose I’m being lazy, I could just browse the source…

    Thanks :)

    • Paul Firth says:

      Hi Raigan,

      In figure 5, the collsion point is the at the first TOI between A and B – you’re correct in terms of where it would be if you projected the remaining velocity along B (like happens in figure 3), but this is one of the ‘features’ of speculative contacts; it postpones the movement until next frame…

      Circles are not handled any differently – just the closest points are used as usual at the start of the time-step. It isn’t perfectly correct, but the visible artefacts are minimal in the tests that i’ve run. If they are not acceptable in your case, you can simply linear sweep the circles together (equivalent to raycast from origin to minkowski sum) and take contact points from the real point of contact :)

      Cheers, Paul.

  2. So I used to do something similar, but totally broken. Collisions that would happen within the next frame would be handled in place. Because the solver ran before integrating position, objects would “pre collide”. This was sort of a nasty artifact where a high speed object would collide with a solid wall part of a step too early and fall to the ground. For a while I thought this was preferable to missing the collision, but eventually just started making games that avoided the need for swept collisions altogether.

    This is starting to make sense to me though. I’m totally going to have to try this out in Chipmunk! Now I just need to get off my lazy bum and implement CA…

    • Paul Firth says:

      Hi Scott,

      I think i’ve implemented a system like that before – IIRC it was from the Eran Guendelman paper, ‘stacking rigid bodies’ http://physbam.stanford.edu/~fedkiw/papers/stanford2003-01.pdf it would predict the contacts next frame but still in a discrete fashion which meant that things would bounce off the floor just slightly before they were supposed to, as you say :)

      This technique is quite different, and really easy to try out if you have a spare moment :)

      You don’t really need CA as prerequisite, you can get quite a long way without it – i know it can be a tricky thing to implement correctly :)

      Cheers, Paul.

  3. Yeah, it was inspired by that paper actually. I also used to use elastic iterations in Chipmunk for a long time until I figured out a trivial way to get rid of them by moving some operations around in my time step. I wasn’t actually repositioning objects and re-colliding them like in the paper, as I was only interested in stable stacking of elastic objects without using thresholds.

    I’ve dabbled with a couple ideas in the past few years for approximating TOI impacts without actually sorting, but none of them have actually worked well at all. This totally has that “Now why didn’t I think of that!” feel to it, though I know I never would have come up with it in a million years. Heh :)

    • Paul Firth says:

      Elastic collisions always seem to be a nightmare :) Oddly, none of the games i’ve ever worked on have called for them, so we’ve gotten off lightly because it makes solving the system a lot easier…

      I think the TOI ordering problem is a lot more difficult to solve than just predicting the TOI between two objects – it makes things a lot more messy which is why this is such a liberating technique, its only slightly more complex than discrete collision :)

      Cheers, Paul.

  4. Fantastic work, Paul! I utterly love it! :D

    Buy Paul’s clever code, people! (If you don’t, then you are just being nasty!)

  5. This looks like an interesting approach, will have to try it out at some point

    I wish the demos were in Flash rather than Silverlight though. I can’t view them on this computer…

    • Paul Firth says:

      Hi Alan,

      I’m trying to migrate to flash part by part (simply because the install base is so much better), but i just find silverlight much easier to work with :)

      Cheers, Paul.

      • I notice that you started writing examples in flash. If you feel like writing some of your future examples in Silverlight though, then I wouldn’t complain :) I prefer to read C# code over Actionscript, personally.

        • Paul Firth says:

          Hi Kris,

          Its a tricky one; I totally agree with you about the readability of c# over actionscript and indeed, I much prefer silverlight in general than flash, however the stats I’ve been gathering about the percentage of people with silverlight installed are worrying – something like only 50% which really cuts the readership in two… Its a shame…

          Cheers, Paul.

  6. Connie says:

    Amazing details! I have been previously looking for something such as this for a while now. Thx!

  7. raigan says:

    Could I get the latest source? Thanks :)

  8. Pingback: Advanced collision detection - Refactored scope

  9. Dirk Gregorius says:

    Hi Paul,

    thanks for the article. It seems as if your discrete solver is not using any stabilization. If I am correct I would argue that this is not a fair comparison since it let’s the discrete solver appear much worse than the speculative. The speculative contacts should solve tunneling issues and not lead to improved physics quality how it is suggested from your demos.

    Thanks,
    -Dirk

    • Paul Firth says:

      Hi Dirk,

      By stabilisation do you mean penetration correction? I’m sorry i’m not fully clued up on all the terminology :)

      If so, i always found that by doing any penetration resolution the stability of the simulation would always decrease – the reason being the main point i sight in the article – the transition from positive distance to penetration would always cause a jarring discontinuity which was the main cause of the jittering i found. The beauty of the speculative contacts is that because of the distance calculation, this is factored directly in to the solver making a much more stable simulation.

      I hope that makes sense :)

      Cheers, Paul.

  10. Erin Catto says:

    Hi Paul,

    Great article! I look forward to trying this in Box2D.

    On the flip side of separation, we have penetration. Your speculative solver also removes penetration.

    You can get the same effect in the discrete solver (often called Baumgarte stabilization) by modifying the discrete solver from:

    double remove = relNv;

    to:

    double remove = relNv + 0.4 * (con.m_dist + 1) / Constants.kTimeStep;

    The value 0.4 is the Baumgarte factor which removes overlap over several time steps. The value of 1 added to the distance is the collision slop which removes jitter by allowing a small overlap. Obviously this introduces some fudge factors that speculative contacts seem to avoid.

    I don’t think you will find a discrete solver without this type of position stablization or better, so you should probably update your demos because the difference is huge.

    Cheers,
    Erin

    • Paul Firth says:

      Hi Erin,

      You are quite right, the speculative solver does deal with penetration simply by the fact that its dealing with distance as a primary part of the solver. I had originally intentionally not tried to implement penetration resolution in the discrete solver in the articles because i was worried it would cause the first example to jitter more than it would otherwise have done, and unfairly skew the results in favour of the speculative solver.

      But i can see how it looks like an unfair comparison in the demos where there are many interacting bodies – so i’ve updated all the demos and source code to represent the penetration resolution you described :)

      Thanks for the feedback :)

      Cheers, Paul.

  11. Bart Siwek says:

    Excellent post!
    Did you considered submitting it to #altdevblogaday?

  12. Pingback: Continuous Collision | Wild Factor

  13. Pingback: Physics engines for dummies | Paul's blog@Wildbunny

  14. The Mad Pirate says:

    PKnzip ??????? Man !!!! You are EVIL !!!!

  15. Binh Nguyen says:

    This is basically what we did in dVC2d and dVC3d.
    That’s the reason why the two engines never had problems with tunelling issues. It’s also why I always bug Erwin for positive contact distance in Bullet. In the end, I had to modify Bullet to get it.

  16. peter says:

    i realy like the article, i did some beginners level into this, so you got my attention.
    i never programmed silverlight, is the sample code in silverlight ? (so a webserver is required) or is it both within and without that?

    instead of paypall do you accept other payment methods, (ideal) ?

    • Paul Firth says:

      Hi Peter,

      Yes this particular article’s sample code is written for silverlight in c#, but you don’t need a webserver to run it, just microsoft visual web developer express 2008, which is free and the silverlight 3.0 developer kit which is also free…

      Currently I can’t accept payment other than paypal, I’m afraid…

      Cheers, Paul.

  17. Pingback: Blog J.Schweiss | Physics engine

  18. Chris says:

    Hi Paul,

    I purchased the source for this article, and I’ve implemented your speculative contact system, which works brilliantly by the way, but I have a question about friction. Setting a higher friction factor causes linear movement to influence angular velocity more, and will slow linear velocity somewhat, however, no matter how high the friction is set, the bodies seem to always slide and rotate a little, and will never come to a complete stop. I realize I could zero velocities when they fall below an epsilon, but it seems that once they reach a certain point, they stop slowing down. Do you know how to solve this problem?

    Also, I believe you said implementing restitution in a specular contact system is very difficult. Do you have any tips on where to start?

    Thanks!
    Chris H.

    • Paul Firth says:

      Hi Chris,

      The friction stuff in the code was never really finished which is why I didn’t cover it in the article (and why it was set to zero in the demos) – I found the same thing as you when I was playing with it for a couple of minutes.

      It might be that I have a bug in there somewhere :| or its possible that the system doesn’t have enough iterations to converge for friction as well.

      Definitely do not zero the velocities below a threshold – that will cause all sorts of problems…. :)

      For restitution, I’ve never tried actually so i’m not sure what to advise – I have a feeling its hard to impossible i’m afraid :|

      Sorry I can’t help more,

      Cheers, Paul.

      • Chris says:

        Alright, I’ll see if I can try to get these things working. Let me know if you fix the friction problem. And great job on these articles! I’d love to see some more physics programming articles, and the source code is well worth the price, keep it up!

        Chris H.

  19. Pingback: Real-Time Rendering · Seven Things for May 4th, 2011

  20. Pingback: Physics engine. | Olhovsky

  21. Kris says:

    I notice that you don’t do anything with the contact positions in the Contacts (as the solver doesn’t require them explicitly). I’m experimenting with building a simple physics simulator and I was wondering what use we might have for the closest points on either object?

  22. Well, You shall not forget everybody that is browsing the internet on their phones, tables, iPads, whatnot either.

    The way of digesting internet content is rapidly changing, and the only safe bet to get your content to show up would be with HTML5.

    But that might not be most enjoyful way to make whatever your silverlight demos was supposed to show (No, I did not see them. I would bet that among all high-end internet enabled devices, the figure is far below 50%. Maybe its 50% of windows users which would be like 34% of all PCs, no squat of other internet devices, not even the 7% of windows phones I’d guess)

    I have not played around with Silverlight myself, but I’d guess that it’s probably waay better than Flash (Which really has grown beyond it’s scope).

    • Paul Firth says:

      Hi Frank,

      I dislike HTML5 with a passion – java-script is a joke of a language; no classes, weak types etc… I moved to flash pretty much directly after I wrote this article which is only slightly better than java-script as a language but has no adoption problems like silverlight did.

      Apple devices are pretty much the only ones not to support flash, which is a shame, but it still remains the one platform with the greatest reach dispite HTML5′s inroads. It will be years before HTML5 is even on level terms with flash; there is no way you can replace all the tools, shared knowledge and infrastructure quickly enough for HTML5 to become dominant any time soon. :)

      Cheers, Paul.

  23. Lurchi says:

    Hello Paul,

    first of all many thanks for all your physic-engine related articles. Very interesting technique (I was experimenting with repositioning the objects and they got stuck all the time and the whole simulation got instable). But finally my physic engine works fine with your help ;-)

    But I was wondering if it’s possible to let f.e. a ball bounce on a plane. Currently if a ball falls on a plane it’s perfectly sldiding on it. But sometimes it would be more useful that the ball is allowed to “bounce back” (Elastic collision?).

    Is there any way to implement this or any literature to read? Or is it simply not possible? :|

    Thank you,

    Lurchi

    • Paul Firth says:

      Hi Lurchi,

      No problem, glad you enjoyed them!

      Unfortunately, non-0 coefficients of restitution are not handled at all with this technique and I’ve never tried to implement them either – none of the games which use this technique have ever called for that.

      Sorry I can’t be more help!

      Cheers, Paul.

  24. Niall says:

    Hey Paul, first of all great article!

    I’ve been trying a simple dynamic circle – static line segment collision detection/response thing, and while the detection works I’m having trouble computing the right impulse. I understand everything regarding relative normal velocity and such, and normally my standard velocity reflection thing would be 2*(velocity dot normal)*normal so I assumed the speculative version’s impulse would just be remove divided by that, however it tends to just fall straight through.
    Do you know what I could be doing wrong?

    • Paul Firth says:

      Hi Niall,

      Can you post the code you’re using; its difficult to tell otherwise? :)

      Cheers, Paul.

      • Niall says:

        Hey Paul, here’s what my discrete solver code looks like:
        if (d < radius) {
        // Collision normal
        var ndx = dx/d;
        var ndy = dy/d;

        // Impulse
        var imp = 2*(char.vx*ndx+char.vy*ndy);

        char.vx -= imp*ndx;
        char.vy -= imp*ndy;

        // Positional correction
        char.x -= (radius-d)*ndx;
        char.y -= (radius-d)*ndy;
        }

        d being distance from the ball’s center point to the contact, dx and dy being the x/y components.

        So my speculative version looks like this:


        var rv = char.vx*l.nx+char.vy*l.ny;
        var remove = rv+d;
        if (remove < 0) {
        var ndx = dx/d;
        var ndy = dy/d;

        var imp = remove/(2*(char.vx*ndx+char.vy*ndy));

        char.vx -= imp*ndx;
        char.vy -= imp*ndy;
        }

        However the ball just falls straight through the line, and the impulse is very small.

        • Paul Firth says:

          Hi Niall,

          Have you got an implicit coefficient of restitution of 1 in there? I.e. elastic collision?

          That’s the one thing that this technique does not handle :) Its only designed for completely plastic collisions – i.e ball hits floor and stops dead.

          However, that may not be the exact cause of your bug… I think the maths you have for computing the speculative response is wrong.

          ‘remove’ is calculated correctly, although I don’t see you dividing by the timestep in there?

          But, apart from that, it would simply be:

          remove = rv+d/dt
          if (remove < 0)
          {
          imp = remove;
          char.vx -= imp*ndx;
          char.vy -= imp*ndy;
          }

          I think :)

          • Niall says:

            Ah right, I wasn’t aware of the coefficient of restitution problem. As for not dividing by the timestep, I was just neglecting it due to having a timestep of 1. I can’t see a reason why it wouldn’t still work, however it’s still just passing straight through ):

            Do you think this could be caused by a lack of positional correction, or is it something else at fault?

          • Paul Firth says:

            Its very difficult to say without sitting down in front of it and debugging it :)

            At the very least you should be able to get the ball to stop dead exactly at the point of collision, rather than passing straight though. Do you have a debugger? If not liberal use of printf/trace will help! :)

            Cheers, Paul.

  25. Niall says:

    Hi Paul, just a quick followup – turns out my distance variable was the closest point on the line segment to the circle’s center, not accounting for circle radius – so it behaved a bit oddly! I’ve got it working now, just needed to adjust remove to rv+(d-radius).

  26. Pingback: Speculative Contacts « Jitter Physics

  27. Joshua says:

    Paul, this is an excellent article. Thanks for all the effort you put into it. There is one benefit to this system that so far no one has mentioned, probably because it is aesthetic and not technical, and that is the “hit” frame. In traditional animation we try really hard to emphasize the impact frame of objects that are contacting. This system (by default) gives you a nice contact frame since it doesn’t immediately traverse the reflection trajectory. I notice that a lot of games, especially with very fast objects/projectiles have poor contact frames and sometimes the contact frame isn’t even visible. I’m not sure if you thought about this when designing this system, but I consider it a feature!

    P.S. I spent way to much time in the Little Big Planet editor breaking stuff :P

    • Paul Firth says:

      Hi Joshua,

      Thanks for the input – that’s a very good point you have there. I think the fact that the hit frame is always visible gives a very nice solidity to the feel of the system which is important as you say :)

      Thanks for pointing it out!

      Cheers, Paul.

  28. Matt says:

    Excellent point Joshua.
    Brilliant article as always Paul.

    I had a few questions trying to implement this myself and thought i’d ask here so others could share the answers.

    Not considering any kind of resting state:
    1.) Are Speculative contacts solved along side with penetrating elastic contacts? Or is all contact resolution handled in this speculative way?
    – The reason i suspect all contacts are handled this way is because if this system always prevents collision then there would be no other types of collision to handle? (only penetration)
    2.) How do speculative contacts work with persistence? Is it valid to keep monitoring the speculative contact witnesses after it has been resolved? Or is it best to ditch these immediately?
    3.) For the angular case, does one compute the impulse in the traditional elastic contact way, for the amount of velocity to be removed?

    Currently my physics step looks like this:

    * Update velocities from world forces( gravity )
    * Update broadphase to encompass current and predicted future location.
    * Perform SAT on potential pairs, keep the penetration and closest point for all pairs.
    * Iterate contact points adjusting velocities and correcting any penetration. Keep penetration up to date with each step.
    * Advance body’s positions and angles based on new velocities
    * Apply constraint forces and relax error

    Currently this addition has made my simulation more unstable, albeit nearly tunnel proof. I believe this is due to me locating position integration after contact resolution.

    Also, boxes that bounce up on to one corner and come to rest appear heavily damped, near the resting state. That’s why I asked about the persistence.

    When i initially read the article, and you mentioned loss of time. I took that as literally clamping dt for the current frame when integrating velocity into position. Such that no velocity is lost, literally only time. And then collision would be handled on the next frame as usual. Have you tried a method like that?

    Thank you so much for your time Paul. Please keep up these great articles.
    -Matt Kincaid

  29. Matt says:

    I have made good progress.
    Using only speculative collisions the simulation is extremely solid now!
    It allows my small ragdoll bodies to collide and come to rest on top of each other which was not possible before.

    I found the major problem with my stability was my implementation of this equation:
    //j = magnitude
    // ————————–
    // 1/ma + Dot( N, ((rAp x direction) / Ia) x rAp)
    from: David Baraff, Siggraph ’01

    I noticed the speculative contacts seem to produce an outward velocity to solve penetration somehow. Could you explain how this works?

    To me it just seems that the illustration flips over the collision plane and the function works to settle the velocity in the outward velocity. If that were the case it seems like it glue them together.

    Thanks again for the great reads Paul.

    • Paul Firth says:

      Hi Matt,

      Glad you are making good progress :)

      Regarding the penetration resolution – I found that speculative contacts would cause objects in penetration to ‘ping’ out slightly unnaturally (adding velocity to the system). So what I did in the angry birds article was to split the positive and negative component of the speculative contact – the positive is used as is and the negative (penetration) is separated and used as a split impulse so that no energy is introduced. This lead to a more stable simulation.

      Check the angry birds article for a description of how I handle persistence as well :)

      Cheers, Paul.

      • Alejandro Guillen B. says:

        Paul could you expand on this?
        I have the same problem of objects “bouncing” when they are interpenetrating. What is a split impulse?

  30. Pingback: How to make Angry Birds – part 2 | Paul's blog@Wildbunny

  31. Pingback: Figured contacts | Tomicren

  32. Pingback: Continuous Collision | Wild Factor

  33. Pingback: How to make a 2d platform game – part 2 collision detection | Paul's blog@Wildbunny

  34. Pingback: Collisions: Part 2 | Michael Rush

  35. Pierre says:

    Hello there,
    I’m actually trying to make a small game in AS3. And recently I put my hands into collision detection and simple physics (no rotations are needed for my game purposes)
    The shapes involved essentially are AABBs. I implementes a really simple brute force SAP to manage my broad phase and i’m trying to implement these speculative collisions described here. I find the approach much more logical than doing micro impulses.
    At this time, i extended my aabb shapes with their velocities for the broadphase to detect “future collisions”. My AABBtoAABB contact looks like this :

    private function collideAABB(other:AABB):void{

    amin.x=_x; amax.x=amin.x+_width;
    amin.y=_y; amax.y=amin.y+_height;

    bmin.x=other.x; bmax.x=bmin.x+other._width;
    bmin.y=other.y; bmax.y=bmin.y+other._height;

    // main collision detection;
    Vr.x = other._parent.velocity.x-_parent.velocity.x;
    Vr.y = other._parent.velocity.y-_parent.velocity.y;

    ax.x=(bmin.x+other._width/2)-(amin.x+_width/2);
    ax.y=(bmin.y+other._height/2)-(amin.y+_height/2);

    cw.x=_width/2+other._width/2;
    cw.y=_height/2+other._height/2;

    if(math.abs(ax.x)=math.abs(ax.y)){
    ax.y=cw.y=0;
    d=math.abs(ax.x)-cw.x;
    }

    N = ax.normalize();
    sV=Vr.dot(N);
    remove = sV+ (d/3);
    iM = _parent.invMass+other._parent.invMass;//totalInverseMass;

    if(remove<0){
    imp = (remove/iM);
    _parent.velocity.plusEq(N.mult(imp*_parent.invMass));
    other.parent.velocity.minusEq(N.mult(imp*other.parent.invMass));
    }
    }

    the thing is :
    I got some problems with "ghost collisions" when my character is for exemple affected by gravity and moving on x at the same time. It collides with the edges of the stage tiles.

    But most important, I think I have something wrong with my RigidBody integration
    and /or my distance calculation!
    my integration looks like this :
    position += velocity

    the distance calculation is :
    ax=distance between centers
    cw=combined halfextents

    I choose the axis where Math.abs(ax[i]) is the lowest
    then distance d = Math.abs(ax[i])-cw[i].

    I can't find any example of these kind because AABBtoAABB seems to be only
    used to return a boolean value.

    These errors I made are the reason why when I compute the impulse,
    if I do : impulse = relativeNormalVelocity + distance
    the objects seems to bounce against each other in a unrealistic way.
    So I need to divide this distance by a magic number (say 3 or 10).
    But When it comes to a stack of boxes with gravity I see there is some error somewhere. objects under other objects are jittering for some frames before to stabilize.

    So, sorry to ask, I would be glad to find this solution by myself but i'm still trying.
    Maybe it's the TimeStep missing in my implementation?
    don't know.

    If you can help or see an horrid mistake I commited ;)
    My last Math or Physic Lesson is waaaayyyy too far.
    Thanks. Oh! and I love this blog. For a newbie trying to figure out "how to" it's a real pleasure to read.

  36. David says:

    Hello,

    Would it be possible to avoid the ghost collisions by performing the algorithm and integrating the positions and afterwards check if there actually is a contact made? (this check could be quite fast I guess if we reuse the contact information from before). We do not apply the new impulses if there is no contact. Of course we get a kind of delay when a ghost collision takes place, but it should not be noticeable.

    BR

    David

    • Paul Firth says:

      Hi David,

      Its kind of tough, that, because there are lots of contacts that could potentially be affecting the result of the check after integration. You may end up with a situation where you accidentally discard contacts that you end up needing.

      Having said that, I’ve never tried this so it could work – worth a go! Let me know if you get around to trying it :)

      Cheers, Paul.

  37. Graeme says:

    Hi Paul

    Thanks for such an amazing and helpful website. I purchased this source code a while back but would really like a fuller explantion of the angular contact resolution(inertia, tensors etc). I know you have a link to another webpage for this information, but would love to have your down to earth explanation of it. If its covered in more detail in another download then please let me know.

    Many thanks

    Graeme

  38. el says:

    purchased source code and absolutely satisfied. thanks. simple and readable – c# is not my language but making port wasn’t too much work. getting friction to each rigid body was quite simple, but i have some troubles to implement bouncing. any hint please?

    • Paul Firth says:

      Hi el,

      Glad you’re having fun! Unfortunately, bouncing is something that this technique just cannot handle – its the main limitation of speculative contacts :)

      Cheers, Paul.

      • el says:

        ok. it’s not neccesary for my game. friction is enough.
        Anyway i think there is a bug in Vector2 class in function Clamp:

        public Vector2 Clamp(Vector2 min, Vector2 max)
        {
        this = Max(min);
        return Min(max);
        }

        modifying “this” is pretty undesired side-effect, probably it should be:

        public Vector2 Clamp(Vector2 min, Vector2 max)
        {
        return Max(min).Min(max);
        }

        i’m not c# expert so maybe i’m wrong.

  39. Steve says:

    Hi Paul,
    Truncating the velocity like this does seem like a neat shortcut to avoiding most of the pain of continuous collision detection. (I don’t see why adding restitution would be so difficult though. Surely you just need to factor it into the calculation of the next frame’s velocity.)

    However I get a little concerned that previously fast moving objects might suddenly spend a frame not moving hardly at all if they happened to start the next frame close to another object. Maybe the glitches won’t be noticeable, but I wondered if you might compensate slightly by elongating the object’s next frame timestep to account for the truncated velocity in the last frame. This runs the risk of adding energy to the system in a non-stop spiral of doom, but maybe something hacky could be done to detect and avert those situations.

    I just wondered if it was something you might have played around with.

    Cheers,
    Steve

  40. Ashish says:

    sir i m facing some problem
    i have downloaded the microsoft silverlight but the demos are not running even then.
    please assist me on the same.

  41. Ashish says:

    Thank u so much sir now the demos are running on the page in the article

  42. Alex Walters says:

    Why are all your articles so informative, thought provoking, and awesome? Your articles on physics make my mind hurt with all of the cool possibilities that I can think of. Thanks so much for writing them!

  43. Christian says:

    Hi Paul, great set of articles you have here. Really been enjoying reading them.

    I was wondering though, could you clarify what “sequential” means in the demos in this article? What’s different between “discrete” and “discrete sequential”?

    Thanks in advance.

    • Paul Firth says:

      Hi Christian,

      Discrete refers to collision detection (i.e. not continuous) and sequential refers to the manor in which the contact solver solves impulses; so discrete by itself just means discrete collision detection with standard non-sequential solver, and discrete+sequential is both.

      Cheers, Paul.

      • Christian says:

        So does “sequential” specifically refer to Catto’s sequential impulse solver, or are there other kinds of solvers called “sequential” as well? (The article is a bit confusing as you mention Catto’s sequential impulse system only after having already referred to a solver as sequential — so I’m not sure if they are the same.)

        And as for standard non-sequential solvers, can I assume those works as you describe solvers in the “physics engines for dummies” article?

        (As you can tell I’m simply not sure how many basic kinds of solvers there are.)

        Thanks for the quick response!

        • Paul Firth says:

          Hi Christian,

          Yes, sequential is Erin Catto’s solver technique. The non-sequential solver just applies individual impulses without considering impulse history; similar to the one I describe in the PED article, but with rotation as well.

          Cheers, Paul.

          • Christian says:

            Great, thanks for the clarification! See the post I added below as to why someone might find simply calling the technique “sequential” confusing given the context. :)

            Cheers!

        • Christian says:

          I should add, when I think of “sequential” in this context I think of “sequential vs simultaneous motion” — e.g. do you update objects one at a time (and completely solve its collision against the other, static, object) or do you move all at once (more physically accurate, but harder to solve because of TOI-issues etc.).

          The other related issue is “discrete vs continuous motion”, e.g. use of swept-volumes or not and so on.

          Using this terminology “discrete sequential” has a very specific meaning which doesn’t seem to apply here. :)

          Both these distinctions are from Ericson’s book on real-time collision detection, if you’ve read it.

  44. Andrew says:

    Hey Paul,
    Just downloaded the code- very clear and simple to understand.

    However, where in the code do you alter the values of say, the number of balls on screen, the position of the floor and even things like the images used for the balls?

    I checked the code but this may just be me being stupid… Your help is appreciated! :)

    Thanks in advance,
    Andrew

  45. Jon Slater says:

    Hi Paul,

    in your toi section, you state that ‘the condition checking for negative relative normal velocity has gone, to be replaced by a clamp inside the impulse calculation, and the impulse is accumulated’, and i can see this works great.

    but how would you incorporate this into a system that computes a rebound velocity as a function of incoming velocity and a coefficient of restitution? i am wondering if it could be better to use a split integration model in this type of system, so that the position can be corrected first to prevent inter-penetration, before computing the rebound velocity..

    what do you think?

    as ever thanks for a great article.

    cheers, Jon

    • Paul Firth says:

      Hi Jon,

      I’ve never done this myself – I just accept it as a limitation of the system. However I know some people have modified this system to work with restitution; I heard one idea was to run two sets of contacts; friction-less speculative, and also frictioned restitutional in the same system working independently. Unfortunately I have no further information about how this might be achieved in practice – if you manage to get something like this working, I’d love to hear about it! :)

      Cheers, Paul.

      • Jon Slater says:

        Hi Paul,

        Interesting. I’m trying to develop a solution to this now; i’ll let you know if i get anywhere..

        by the way sorry to be a pain again, but i also downloaded this article before my hard-drive fault, any chance of a download link for this too?

        thanks again,
        Jon

  46. PhisModeler says:

    Hello,Paul! Thanks for good and interesting lessons.
    Now,I have some question about this tutorial.
    For example, how I can calculate variable con.m_dist from first examples?

  47. Joe Holt says:

    Great article, it’s been a big help with a physics project I’m working on. I bought the code, studied it for a while and then implemented the technique into my code. I’ve got a weird problem though. Very often, objects will get “stuck” when sliding. They will just freeze in place. Maybe I’ve implemented the technique incorrectly but it’s a problem that I’ve spent weeks trying to fix. Not sure what’s going on, do you have any suggestions as to what the problem could be?
    Thanks,
    Joe.

    • Paul Firth says:

      Hi Joe,

      That kind of thing can happen if the contact constraint is allowed to pull as well as push overall. An easy quick way to test this is to make sure you only treat contacts with negative relative normal velocity. If that fixes it, you have a bug somewhere around that area of the code :)

      Cheers, Paul.

  48. Ilpo Nikulainen says:

    Hi,

    I can’t see how this technique and SI are compatible together.

    This technique needs a certain negative normal velocity (approaching) so that any work will be done by the contact. No work must be done for contacts which are not approaching fast enough.

    However, SI requires that positive normal velocity can do work (corrective pull) on temporarily receding contacts. I see that putting “if (remove < 0)" before compute, clamp and apply of the impulse, prevents SI from doing pull on contacts which have a positive normal velocity (temporal receding) from the previous iteration or from same iteration (applied by some other contact on same object).

    • Paul Firth says:

      Hi there,

      Yes, you can’t really put that condition in production code because as you rightly say it reduces the effectiveness. Instead you should use the code snippet I posted under the section named ‘TOI joy’ which is effectively just SI with speculative contacts thrown in.

      Cheers, Paul.

  49. Philip Borchert says:

    Paul Firth, GREAT article so great that any sort of article on speculative contacts in fact on http://jitter-physics.com/wordpress/?p=109 at the very start this author claims “Paul doesn’t claim to be the inventor of the mechanism but he made it quite popular. The idea of the algorithm is – as Paul stated -
    (..) to try and move the majority of the work out of the collision detection system and into the contact solver (..)

    I guess I have a burning desire to always find the start of something. I’ve done tons of google research and I know there was some discussion in the physics world of “Speculative contact” having nothing to do with coding but an idea… and I ASSUME this is where it originated from. However, I was looking for or wanting an article that would start with something like, Speculative Contact is the brain child of the term meaning to make an educated guess (Speculate) at what an object will contact given it’s current path. Then go on to discuss the math and various other components involved? Would you have any references or discussions that could help me with this? I think the only thing missing from this AMAZING article is references.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing