Collision Detection – Need for ‘stepping’
Patrick Lam | 28 February, 2009 | 21:55
The collision detection works pretty well for basic objects (ie. cube) at the moment. However, when these objects start to move faster (ie. travel larger distance in small amount of time), a hidden problem becomes more apparent and needs a solution.
The solution to this is ‘stepping’. As briefly explained in a previous blog, the basic idea behind ‘stepping’ is that we take a normal ‘step’ (ie. an update), and break it down into smaller steps. So in the case of a moving object, lets say in one update, it travels from current location to 10 meters ahead. Now what we do instead of checking for a collision at the current location and at the 10 meter mark, is break this 10 meter into smaller steps and check for collision at each of them. So lets say we break it into 5 smaller steps, therefore, we’d be checking for collisions at current location, 2m, 4m, 6m, 8m, and finally at 10m.
Why we need to do this and what’s the problem if we don’t?
Imagine there is a wall 6m ahead of the object. If we didn’t perform stepping, the object would have ended up directly from one side of the wall to the other without detection a collision. With stepping, we can now detect a collision when we are at one of the smaller steps when checking for collision at 6m.
Imagine the wall is 5m ahead instead. Now what would happen in this case? When we check for collision at 4m, they’re not touching yet, but what about at 6m? It could be touching, or we could have past it already, or we might have half our body stuck inside the wall. In this case, it might have been better, if we broke the steps into even smaller ones.
Deciding on an appropriate step size is very important. If the step size is too small, we might miss some collision, but if the step size is too big, it might slow down the update and other processes too much. I find that doing some trial and error helps to get a better understanding how much this stepping affects the overall performance. It can also help you figure out what the appropriate step size is too.
Here is a link to a demo which shows what happens when stepping into not used. The example is similar to the one I used to explain, about an object ending up in a wall.
http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev3/testDemo.html
The solution to this is ‘stepping’. As briefly explained in a previous blog, the basic idea behind ‘stepping’ is that we take a normal ‘step’ (ie. an update), and break it down into smaller steps. So in the case of a moving object, lets say in one update, it travels from current location to 10 meters ahead. Now what we do instead of checking for a collision at the current location and at the 10 meter mark, is break this 10 meter into smaller steps and check for collision at each of them. So lets say we break it into 5 smaller steps, therefore, we’d be checking for collisions at current location, 2m, 4m, 6m, 8m, and finally at 10m.
Why we need to do this and what’s the problem if we don’t?
Imagine there is a wall 6m ahead of the object. If we didn’t perform stepping, the object would have ended up directly from one side of the wall to the other without detection a collision. With stepping, we can now detect a collision when we are at one of the smaller steps when checking for collision at 6m.
Imagine the wall is 5m ahead instead. Now what would happen in this case? When we check for collision at 4m, they’re not touching yet, but what about at 6m? It could be touching, or we could have past it already, or we might have half our body stuck inside the wall. In this case, it might have been better, if we broke the steps into even smaller ones.
Deciding on an appropriate step size is very important. If the step size is too small, we might miss some collision, but if the step size is too big, it might slow down the update and other processes too much. I find that doing some trial and error helps to get a better understanding how much this stepping affects the overall performance. It can also help you figure out what the appropriate step size is too.
Here is a link to a demo which shows what happens when stepping into not used. The example is similar to the one I used to explain, about an object ending up in a wall.
http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev3/testDemo.html
While an explicit level of substepping is useful, adaptive substepping
Joe | 7 March, 2009 | 0:57While an explicit level of substepping is useful, adaptive substepping would help even more. That way, the dynamics engine could decide the level of substepping needed for the correct results.
This might need to be implemented with an upper-bound in order to ensure adequate performance, though.