Box2D Forums

I have continuous physics prototyped in SVN. Continuous collision is always used between static and dynamic objects. You can optionally set b2BodyDef.isFast so that a body always gets continuous collision.

The method I'm using handles fast translations and rotations. However the method does not conserve time and you may see some stalling. For this reason, I don't recommend using isFast on large stacks of bodies. 2 or 3 is okay. Keep in mind that all bodies will still get continuous collision with the ground.

I made the bomb very fast so you can see the continous physics in action. Also, I added some single stepping capability to the GUI.

Feedback and bug reports are welcome. Consider this alpha.

Very impressive! That's looking very close to done - I played with the CCD demo for a while, and I was able to make a board tunnel through the floor once, but I couldn't figure out how to repeat it (I think one board was vertical, pinned between two flat ones while the bomb hit, or something like that, didn't have it in step mode).

When you say it doesn't conserve time, do you mean it doesn't finish the time step if the CA step predicts a collision before it's up? Does this mean that the time between collisions is not bounded from below? I know this is asking a lot since you're so busy getting the engine working, so don't feel obligated at all, but once you have all this worked out, I would love to see a full explanation of the algorithm (I noticed that your post at http://www.bulletphysics.com/Bullet/phpBB3/viewtopic.php?f=4&t=1710&sid=2e2a43a492d5881a1ab01ad7c4bc4736 was met with silence, which disappointed me as I've found most CA explanations to be lacking details such as that one). If you can't get around to it, no big deal since the code is there, but I think it would fill a gap if it was clearly explained.

One little thing: I don't know if this is new to this version, but the pyramid demo looks like it's barely making it, it seems like it has a lot more give than it used to. Vertical stack also seems to wobble a little more than in the past. I don't think it's like that in 1.4.3 (Java port @ ~1.4.3 seems okay, though I don't have the C++ to check against, already updated to SVN), so it must have to do with the CCD stuff - assuming the pyramid blocks do not have that flag set, maybe the friction response against the floor in CCD mode is a bit off, leading to more slip than usual?

One last question: is this stuff going to be live in the next couple of releases? Should I start porting what you have, or is it going to change too much before it settles to be worth starting on now?

Looking good, in any case, I believe I've already mentioned how excited I am to use this feature in games...once this is stable I'll finally be able to nail the coffin on my hand-rolled engine and start worrying more about programming the games than the physics!

I'm happy to explain the algorithm. Feel free to poke holes in it.

First some terminology:
core shapes - shapes that have been shrunk by b2_toiSlop which is larger than b2_linearSlop.
TOI - time of impact of core shapes, between 0 and 1, where 1 means no impact.
CCD - continuous collision detection, a method for computing TOIs.
CA - conservative advancement, a CCD method which gently moving bodies forward in time so that core shapes do not overlap. It is an iterative algorithm with a tolerance. It handles fast translations and rotations. Computes TOI. GJK forms the core of this algorithm.
CP - continous physics, the algorithm that manages the movement of bodies using TOIs.

Box2D uses core shapes for TOI calculation. Normally shapes in steady contact do no have their core shapes touching. Contact constraints work on the normal shapes, which are larger than the core shapes. So if you have a stack of boxes without large velocities, the TOIs will all be 1, meaning that no backtracking is necessary. The full time step can be taken without risk of tunneling.

So here's the basic structure of the time step:

1. Integrate forces to get new velocities
2. Solve velocity constraints.
3. Store initial body transforms.
4. Integrate velocities to get new body transforms.
5. Update the broad-phase with swept AABBs. This creates new b2Contacts to allow for TOI computation.
6. Continous physics (explained below).
7. Compute contact points.
8. Solve position constraints.

Here's how CP works. Each body stores an initial and final transform. These are not modified during CP. Each body also stores a TOI value and a flag that indicates if the body has been resolved. The TOI value is initially 1 and the flag is cleared. I loop over all b2Contacts computing the TOIs and I find the contact with the minimum TOI. The bodies for the minimum TOI contact are marked as resolved. Then continue looping over all contacts looking for a new minimum TOI. During these successive TOI computations, resolved bodies are held fixed at their resolved TOI.

This process allows fast moving stacks to stop all at once without tunnelling. Once a body is resolved it is not reintegrated for the remaining portion of the time step. This is why I say that time is not conserved. Time is not conserved for any body that has a TOI less than 1. However, normally most bodies in the world have a TOI of 1.

Having step 7 and 8 after step 6 are critical and are the solution to the problem I posted on the Bullet forum. Step 8 gives the contact some breathing room for future TOIs due to fast rotation. However, step 7 is making step 2 work with some stale information, leading to some decreased stability in stacking. I have some ideas for this, so it shouldn't be a big deal to fix it.

Weaknesses:
- Performance. There's a ton to do here, much of it is obvious, like caching results, early outs, etc. One aspect of performance I haven't resolved is whether it is possible to avoid looping over all bodies and contacts. Perhaps using some islands would help.

- Time is not conserved for some bodies. It is probably possible to extend my algorithm to conserve time, but I haven't figured it out yet.

- Shapes can tunnel during step 8. Position constraints should be prioritized so that static-vs-dynamic always wins.

I know this is a lot to digest and pictures would help a lot. However, the algorithm is in a state of flux and nothing is final yet. My goal right now is to make the algorithm as solid as possible. There will be some other architecture changes and this will all go out in 2.0.0. Hopefully in the next couple weeks.

Could conservation of time be made an option? For zero-gravity scenarios, resting contacts don't come up nearly as often, so conserving time would be more usable there.

Unless something changes an object's velocity (i.e. a collision), its position can be evaluated at any time during the step without actually moving the object at all. The lowest-TOI pair would advance to the TOI, update their velocities, and then update their TOI links with all potentially-colliding bodies. No other body needs to be touched. That minimizes the amount of work done.

We had a continuous-collision detection during the early development of Star Wars: the Clone Wars, but it advanced every body in the world when advancing the sub-step timer to the lowest TOI. A "lazy" evaluation saves a lot of unnecessary work, especially when bodies are segregated into "islands". Resting contact (zero TOI) still causes all sorts of problems, which is something we never solved.

I think conservation of time can be made to work with resting contact because I only compute TOIs on the core shapes. I will need to resolve each TOI contact, including some position correction, to make this work. Box2D already handles penetration, so resolving just a little bit of penetration should be no problem.

Somehow I should be able to make use of the b2Contact graph to partition the problem. In fact I think this will be quite easy since I already do this sort of thing.

Do you guys have any ideas for good test cases? It is easier to solve a problem when I have a problem to solve. Any ideas for troublesome cases are welcome.

Good to see the addition of CCD/CP to Box 2D as well.



We discussed this over private conversation with Erin, and I just replied on the topic what we discussed.

Conservative Advancement with continuous physics using a smaller 'core shape' was used in Bullet 1.4 physics engine. It has been disabled after some refactoring.

Brian Mirtich used Time Warp, but I found that performance spikes due to excessive number of 'time of impacts', the cost of rolling back the simulation, splitting and merging islands, and memory allocation to store the rollback stack of operations was very high. I'm interested to see what methods you come up with to solve those issues. In the meanwhile, I enable the approximation in upcoming Bullet as well (continuous physics by default between dynamic and static objects, and optional CP between dynamic objects with a very limited number of subdivisions (loosing time).

The method seems to work quite well and is also used in other physics engines like PhysX etc.

Thanks,
Erwin

One case that would likely be troublesome is a heavy box falling from rest onto a vertically moving light box beneath it (which will bounce quickly between the ground and the upper box with a decent restitution value). This will cause some issues with time, since in the limit as the light box's velocity goes to infinity, the upper box will only move half the distance that its velocity would dictate (it will be instantly frozen whenever the lighter box moves upwards, but will simulate normally while it goes down, i.e. every other step). Add another light box exactly halfway out of phase with the first, and you get a motionless heavy box with a non-zero velocity, which is a bit of a paradox...

I'm not sure that there's anything to do about it, or if it's even that much of a problem - it's a pathological case, to be certain. This type of thing shows up a little bit in the CCD test if you hit the stack with the bomb right as it touches the ground, and it leads to a noticeable lag, so it's probably at least worth thinking about. I'm sure no perfect solution exists (imagine a fast box smashing through a thousand smaller boxes in one step, you can't allow the simulator to calculate all of the thousands of collisions or you'll be waiting forever), so don't waste too much time on it, but maybe there's some sort of hack that could allow approximate time conservation for common cases like bouncing an object into one at rest on the ground.

I'm now thinking that for 2.0 I will have 3 types of bodies:

- static
- normal dynamic
- fast dynamic

These cases will get CCD:
normal dynamic vs static
fast dynamic vs static
fast dynamic vs normal dynamic
fast dynamic vs fast dynamic

So normal dynamic bodies won't do CCD with normal dynamic bodies. I think this will keep performance and behavior reasonable while making bullets feasible and preventing all bodies from tunneling through static geometry. Big stacks of bodies should not be marked as fast.

Just a thought..
Can you just automatically turn on CCD for the body if a body is moving really fast?
Mike

Yeah, I thought about that. It may be hard to gauge what is "fast". It would depend on the units and and size of the shapes. It would also depend on the other shapes in the collision. Small shapes vs fat shapes may not risk tunneling, but small shapes vs thin shapes may be a problem. If I use the wrong heuristic people will have either poor performance or unexpected tunneling.

So for now I'll leave the "fast" option to the game designer.