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

173 Responses to Speculative Contacts – a continuous collision engine approach

  1. Xiaoyu says:

    Hi Paul,

    I am wondering how to handle rotation in a speculative solver. Is the angular velocity also removed to ensure that on the next frame the two colliding bodies are just touching each other? Or we respectively compute translational velocity in a speculative way and rotational response in a discrete way?

    Thanks, Xiaoyu

    • Paul Firth says:

      Hi Xiaoyu,

      We use chris hecker’s impulse equation which solves for both angular and linear velocities, with a couple of additions to make it handle speculative contacts.

      Cheers, Paul.

  2. Ilpo Nikulainen says:

    Paul,

    I have succeeded in my experiments with SC + bounces, frictions, joints and flexible bodies in 3D. One thing though for what I haven’t found a solution is the sleep control of the model objects.

    My current (non-functioning) solution puts the objects to sleep when their filtered movement is below a given threshold. And after a collision the objects will be awaken recursively as long as there exists resting contacts or joints. Resting contacts (ie. wake-up-linkedlists in the counterpart objects) are formed up when the sleep controller detects that both colliding objects are going to sleep at the same model update interval. When an object is in sleep, no movement is calculated for it and it is not used as a collision test source.

    With Speculative Contacts, I’m between two conflicting requirements:
    A) all the potential colliding objects should be awake before computing the speculation to prevent undetected collisions; Even the objects in middle of a chain shall become a collision test source. I don’t see re-speculation rounds as an option.
    B) On the other hand the objects will be awaken only after there is some activity on it through it’s resting contacts or joints.

    Have you succeeded with the SC + sleep control?

    I can see an alternative approach which would use the broad phase collision detection for waking up the objects: take big enough bounding box and wake up everything inside it. But it would be quite inefficient and still there could exist chains of objects reaching outside the box and would not get included in the contact speculation.

    • Ilpo Nikulainen says:

      I would make an obvious correction the requirement “B”: the objects shall be awaken also (and primarily) when a speculative contact does work on them.

      I appreciate your patience :-)

      Regards, Ilpo

    • Paul Firth says:

      Hi Ilpo,

      Sleep control is one of the hardest things to get looking right – all the things you’ve mentioned are the problems that everybody needs to consider when implementing something like this. Although, I don’t think adding speculative contacts vs discrete contacts has much impact on the behaviour this.

      In general, any external forces should recursively wake any objects in a group. And objects in a group should only sleep either all at once or not at all.

      Cheers, Paul.

      • Ilpo Nikulainen says:

        Paul,

        Thank you for the useful information, once again.

        I agree that adding speculative contacts vs discrete contacts does not have much impact on the behaviour. However, I’m afraid that as speculative contacts moves the computation from the collision detection to the collision response calculation, increasing size of the “clearance space” (ie. bounding boxes) in the broad phase collision detection will make much greater effect on performance than it would make when there would exist a narrow phase collision detection (as exists in a discrete contacts method).

        In any case it is relevant to minimize the “clearance space”, perhaps by using a maximum speed parameter in the broad phase detection.

        From your answer I also realized that if the recursive put-to-sleep procedure hits to a not-ready-to-sleep object, the whole procedure shall be cancelled in the inverse way, and the procedure should not be initiated anymore to those objects on this model update interval. I also need to add the wake-up to happen when the external forces like gravity and user input are changing.

        Regards, Ilpo

  3. Kaeel says:

    Hi Paul, your pages are still open on my browser since a lot of days :P
    I tried to implement the speculative contacts technique: to get the minimum distance vector, I implemented the Poly VS Poly strategy you suggested here http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/
    and it works very well (vectors and distances calculations seem very accurate).

    Now, I’m not able to find a solution to this problem: after removing the normal component of the velocity and moving the polygon, it stops exactly in the position of contact (and this is good!).
    The problem is that on the following frame, the distance vector between the 2 polygons is zero so, when I normalize it to get the ‘n’ versor, I get another vector with both components equal to zero.
    At this point, the projection of the remaining velocity on that vector gives zero, nothing is removed and the polygon continues to move with reduced velocity.

    What could be a solution to this problem?
    Maybe there’s some operation I’m missing before updating position (such as adding a small offset in the correction, so that next distance will never be equal to zero) or there may be something wrong in the way I compute distance when it’s zero?

    Ty again for the support, these articles are very good in trying to learn how these techniques work!

  4. Joshua says:

    So I am trying to make something like the scene with one dynamic ball and the concave static walls. However, from what I have right now, the velocity is slowed almost to a halt after it hits the polygon when it should continue with only a slightly reduced velocity. Do you have any idea what the problem might be?

    • Paul Firth says:

      Hi Joshua,

      Afraid not – without seeing it, it’s very hard to understand what could be wrong :)

      Best bet is to debug it.

      Cheers, Paul.

      • Joshua says:

        Thanks. Ill figure it out then (Thanks for the quick response btw). I have got another question too. What about in a situation like this:

        http://postimg.org/image/klhmtdqa3/

        Where the blue ball is dynamic and its velocity is in the direction of the arrow and the triangle is static. According to speculative contacts, wouldn’t this remove all of the ball’s velocity since it is already in contact with the static triangle? This would result in really weird results… or am I wrong?

  5. Joshua says:

    is there any way I can solve the issue where the ball is no longer colliding because it is sitting on the static body and is now (I think due to rounding error) no longer considering on top of the static body because it is inside. What I mean is that I think due to rounding error, the ball is no longer on top but inside the static body? Do you understand? Sorry for the bad explanation. Thanks.

    • Paul Firth says:

      It shouldn’t matter if the ball is right in the middle of the static body – there should always be a shortest direction out to leave them just touching. The collision detection routine must cope with this case as well.

  6. Joshua says:

    I was just thinking that if I did it right because i am only using one dynamic body I could just use SC without penetration resolution.

  7. Joshua says:

    Ok. So then how would I deal with a ball at a corner where it has two contact points?

  8. Joshua says:

    I know that but what about if two convex objects from a concave object. Sorry if what I previously said was confusing.

  9. Ricardo Baptista says:

    Hi Paul!

    In the speculative contact approach, if there is bouncing involved (coeffiecient of restitution > 0) then the two objects are not expected to be perfectly touching in the next frame, but already slightly apart (due to restitution), right? So they will never really touch/penetrate?
    If it is the case, then to make this happen should I remove not only the amount to leave they touching, but also some amount (restitution) (using Chris Hecker impulse resolution formula) so they start to move in opposite directions? I mean:
    double remove = (1 + e) * relNv + con.m_dist/Constants.kTimeStep;
    If that is right, should I expect some decrease in speed along the normal after a bounce (even when restitution is 1.0), because I just clipped con.m_dist/Constants.kTimeStep from the original velocity?

    Thanks!

    • Paul Firth says:

      Hi Ricardo,

      Unfortunately, speculative contacts does not work with non zero restitution coefficients.

      Cheers, Paul.

      • Ricardo Baptista says:

        Hi, Paul!

        Thanks for the fast reply.
        So, was that what you meant by “the coefficient of restitution is never required to be non-0″ on the “Physics engines for dummies” article when you solved the problem of balls penetrating each other?
        Then a good option would be to use the discrete sequencial approach for bouncing objects and the speculative for non-bouncing pairs? Is it ok to merge the two strategies by checking the restitution factor of a pair and decrease their velocities (speculative) only if they don’t bounce? And handle the other (bouncing) pairs by the discrete way?

        Cheers

  10. Joshua says:

    Thanks so much for your help so far. I have been trying to solbe a problem and I really have had a hard time, Maybe you could help me. What I am trying to do is particle (or small circle) against convex polygon collision. What I have works, but only if the convex polygons don’t make up concave polygons because then the particles fall through the cracks in between the convex polygons. Anything you could do to help me would be very appreciated. Thanks.

  11. Joshua says:

    I got some particle based liquid physics working so now I am trying to get it to collide with the world which consists of static convex objects

  12. Jason Eaton says:

    Hi,

    This was a great series of articles!!! I have been trying to get a good simple platformer engine for a long time now, and this seemed to be the last piece of the puzzle. Check out my demo:

    http://jeaton.matero.net/misc/PlatformTestBed.html

    It is funny, we were having the exact same thoughts about wanting a simple engine like the old snes and nes games (I read the same MC kids article for my independent study in college). This current version does not use speculative contacts quite like yours does, but I did come to the current form from implementing them your way for a bit. This current engine actually guarantees that there is no penetration using a very simplified sweep that is almost like a speculative contact (there are some ghost collisions, but not noticeable) Except there is one case where an object is wedged between two other objects and penetration is forced. (no rotations are used to achieve this).

    Now for my question, could you go into a little more depth on how you do the rotation speculative contact? If an object has a velocity, and angular velocity, I’m not sure where to stop it exactly. No rotation is easy, just clip the velocity with the normal of the closest features, but I’m not sure how you would go about clipping a rotational velocity? And deciding if the normal velocity should be clipped as well?

    Thanks for the great article!

  13. Joshua says:

    So for the impulse equation with the collision, if the collision feature on a shape is a line, would I just use the midpoint of the line as the contact point for that shape? Or would I need to adjust for that second contact point in Chris Hecker’s impulse equation?

    Thanks

  14. Joshua says:

    Hmm, would you mind expounding a little more, right now I am doing just dynamic box to static box interaction with rotation. So what I did with the impulse equation was just treat each contact point as another point and just added it to the denominator of the impulse equation, just how Chris Hecker adds the contacts in the denominator (except he only accounts for one per body). I then calculated the rotational velocity added by each contact point using the equation he gives. Is this right?

    Thanks so much for your time,
    Joshua

  15. vinny says:

    Hello i have bought your source code, there are some projects covering different parts, i’ like to ask what is the most complete to start to convert into c++ , is there any differnece with angular and hardangular ( i am referring to 2 different projects ) , is one more complete than the other to be used in a small game ?. Another question is about silverlight i didn’t install it because i didn’t want to mess with my visual studio installation, and since i am not very well versed in c# i’d like to ask you if the transformation is performed in the control class from whose you derive the rigid body class, i need to implement my rotation code using matrices am i right ?
    thanks for your time

    • Paul Firth says:

      Hi Vinny,

      The pileoboxes project is the most complete to convert to c++.

      Regarding visual studio, if you download visual web developer 2010 express, that will keep the installation separate from any other versions you might have, and will make your life much easier when you need to compare behaviours in your port.

      Transformation should be performed in the Matrix23 class.

      Cheers, Paul.

  16. vinny says:

    I have already installed visual studio pro and i don’t want to mess with this installation.
    By the way i mean, how do you store the trasnformed vertices you collect after the transformgroup function ? are they stored internally ? i have seen in one of your demo a ball falling and sticking to a box, is there any inherent (sp??) reason why the restituition factor is so low ? its becasue of the speculative algorithm ?

    • Paul Firth says:

      Hi Vinny,

      VS2010 web express installs as a separate program.

      Vertices are not transformed and then stored, they are transformed as required in Rectangle.GetWorldSpacePoint(). This isn’t massively efficient, I would recommend changing that so once per frame the vertices are transformed and then stored.

      Non-zero restitution is not possible with speculative contacts.

      Cheers, Paul.

  17. vinny says:

    So basically you say that thins don’t bounce back when they collide , don’t you ?

  18. Joshua says:

    So I bought the source code and was just wondering if the RectRectClosestPoints function also works with arbitrary convex polygons. Thanks.

  19. Joshua says:

    So if two polygons are seperated, are the contact points computed the same way ad if they are intersecting? Just wondering because if they are seperated the contact points will move as the two polygons/bodies move, so it would make it hard to generate contact points for two moving seperated polygons.

    • Paul Firth says:

      Hi Joshua

      Separation is dealt with differently than penetration, although both are dealt with simultaneously in the code. Actually, contact points will move as the two bodies move even in the case of penetration.

      Cheers, Paul.

  20. Joshua says:

    I was also wondering where you resolve the penetration in the Pile O Boxes demo. Thanks.

  21. Joshua says:

    Ok thanks. I actually just got it working last night. One problem I ran into is that when it hits the ground, the body flies up due to the penetration. Is there a way I can keep it from found this?

  22. Joshua says:

    I’m not sure why you say there wouldn’t be any penetration. There is penetration in the first angular demo.

  23. karim says:

    Hi dear Paul, i have took a look at your source codes, your contact class have two argument for contact point, but in some situation we just have one contact point like this:
    http://www.freeuploadsite.com/do.php?img=34845
    i’m confused, what is your contact generation method ?
    thanks

  24. karim says:

    Hi again, thank you for reply, i have some other problem, whats going on in”Geometry.RectRectClosestPoints()” ? Can you explain more?

  25. vinny says:

    Hello , its me again i am going further into 2d physics thanks to your code and tutorials.
    But i have a problem , i want to create a system of particles ( not a particle system ) connecting many spheres and keep them at a fixed distances between each ohter.
    I have succesfully implemented a single constraints between 2 particles, but when i connect more than 2 , the simulation explodes, this is due to the fact that continous rearrangement of velocities ( i am using an impulse method ) move the particles around and creat a sort of race between them.
    How can i solve this problem ??? is it possibile to hire you ? i have read about jacobian but looks like every document doesn’t hint to a possible solution for multiple distances.

  26. Nathan says:

    Hello. I am trying to get the code beneath figure 6 to work and have looked at some debug messages. Is it possible for the distance between the two AABBs to be negative and have the remove variable > 0? That is happening to me and it doesn’t seem right.

  27. Nathan says:

    Sorry that I’m asking a lot of questions, but I’m trying to get this to work and really appreciate your help. I have gotten speculative contacts to work perfectly with one dynamic and one static object, but I get a lot of problems when I try to collide two dynamic objects. I have done the math and I believe it is correct. Is this a proper collision?

    Ninja vs physics tile
    Collision normal: 0,-1
    Ninja velocity: 0.0,40.0
    Tile velocity: 0.0,0.0
    Relative velocity: 0,40
    Relative normal velocity: -40
    Dist: 26
    Remove: -14
    Ninja new velocity: 0.0,36.315735
    Tile new velocity: 0.0,10.315735

    I think that is correct, but the problem is when the tile collides with another object and its velocity is decreased, there is penetration between the first two. Is that normal?

  28. Nate says:

    How are multiple iterations implimented besides just looping over the collision function a few extra times? Is the timeStep affected?

    • Paul Firth says:

      Hi Nate,

      The iterations are all inside the solver – as I explain in the article, speculative contacts obviate the need for multiple collision iterations as they move the TOI problem inside the constraint solver.

      Cheers, Paul.

  29. Hosam Mahmood says:

    One thing comes to mind, and I admit I haven’t tested yet, but doing speculative collision detection, if I remove velocities from the particle as it approaches another one to just touch, wouldn’t that hurt resolving the collision responses, in terms of restitution(bounciness)?

    Currently I’m doing discrete collision detection, resolving the response and do positional correction based on penetration and a slop. Only after the actually collide. So this approach is kinda playing with my head :P

    • Hosam Mahmood says:

      Also one thing that I was wondering about, in the source code, you retrieve contacts, however you never do culling, contacts with (Ball1,Ball2) and (Ball2,Ball1) both get impulse applied to them, I would imagine this to be problematic, however its working fine. Would culling increase performance, or make it perform any differently?

    • Paul Firth says:

      Hi Hosam,

      Yes, restitution (bounciness) is not supported by this algorithm at all.

      Cheers, Paul.

      • Hosam Mahmood says:

        In your experience, what would be the best algorithm to do collision detection that resolves restitution and positional correction? If you can point me in the right direction that would be awesome.

        • Paul Firth says:

          Take a look at box2d is the short answer. The long answer is extremely complex – spec contacts solve so many of the issues with continuous collision detection and resolution.

          I did hear of someone who used a hybrid of speculative contacts and regular contacts with restitution, but I’m afraid I don’t know any of the details.

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