Seperating objects after collision?
Hi, I've been working on a simple collision detection between two models (loaded from *.obj files). I've got the collision detection down to triangles working, its inefficient but it works, and I don't notice any performance hit as my game will only use simple models. The way it works is each model has an AABB, when two AABB intersect, the triangles intersecting with the AABB are tested against each other. I have a little screenshot:
The green lines show the intersecting AABBs, and the blue colored faces the intersecting faces.
I'm a bit stuck however, on how to work out the shortest way to seperate the models after a collision is detected? I was wondering if anyone new of a good way that could be adapted/used with my collision detection system?
EDIT - I should mention the AABBs are on the largish side because the models weren't centered properly when modeled.
Cheers,
Mark.
Is this 2D only? In any case, separating non-convex objects like that can be tricky. You could just separate the triangles that are intersecting, but what if there are multiple intersecting pairs? Also, there can be configurations where displacing the objects in the most obvious way causes another interpenetration. There are other problems as well.
One option that might give acceptable results would be to construct convex hulls for your objects and use those for the narrow phase instead. Whether the inaccuracies would be noticable would depend I suppose on factors such as the speed and relative sizes of the objects.
Another option would be a swept test, but that can get pretty involved when implemented on the per-triangle or per-edge level.
Anyway, clarifying whether the simulation is 2D would probably help further discussion. (It looks like it might be essentially 2D but with 3D models...)
One option that might give acceptable results would be to construct convex hulls for your objects and use those for the narrow phase instead. Whether the inaccuracies would be noticable would depend I suppose on factors such as the speed and relative sizes of the objects.
Another option would be a swept test, but that can get pretty involved when implemented on the per-triangle or per-edge level.
Anyway, clarifying whether the simulation is 2D would probably help further discussion. (It looks like it might be essentially 2D but with 3D models...)
Its going to be 3d, I've just had it setup this way for testing, I find it easier to see whats going on
Cheers,
Mark.
Cheers,
Mark.
If I understood correctly, your models get stuck on each other upon collision. This is a very common problem related to collision detection and response.
AFAIC, there are 2 solutions. One which is inefficient and difficult, and another which is dead simple, but requires a bit of restructuring in the game logic.
The first one is moving the models after collision so that they no longer collide. That's the path you're trying to do atm if I understood correctly. This is easiest done by moving the objects away from each other by a small quantity. Easiest way to do is finding a quantity that seems to do the trick, but is not big enough to cause strange jittering upon collisions. The other way is to calculate the proper ammount of displacement by means of geometry. This is quite difficult, especially with complex 3d models.
The way I prefer is checking for the collisions _before_ they actually occur. To achieve this, I calculate the displacements of all objects I'm going to move. Then I check for collisions by adding each object's displacement to their position (and disorientation to the object's rotation/orientation) and then check for collisions. If no collisions occured, then I move the objects by the displacement I previously calculated. If a collision did in fact occur, then I calculate the appropriate collision response and reset the displacement. This way the objects will never actually intersect in the next frame they wont collide (and get stuck). This method works very nicely.
The above methods don't work for objects that travel at speeds that are so high that the collision happens "between" two frames, but not in the frames before and after. Such objects might be bullets, for example.
Hope this helps,
Richardo
AFAIC, there are 2 solutions. One which is inefficient and difficult, and another which is dead simple, but requires a bit of restructuring in the game logic.
The first one is moving the models after collision so that they no longer collide. That's the path you're trying to do atm if I understood correctly. This is easiest done by moving the objects away from each other by a small quantity. Easiest way to do is finding a quantity that seems to do the trick, but is not big enough to cause strange jittering upon collisions. The other way is to calculate the proper ammount of displacement by means of geometry. This is quite difficult, especially with complex 3d models.
The way I prefer is checking for the collisions _before_ they actually occur. To achieve this, I calculate the displacements of all objects I'm going to move. Then I check for collisions by adding each object's displacement to their position (and disorientation to the object's rotation/orientation) and then check for collisions. If no collisions occured, then I move the objects by the displacement I previously calculated. If a collision did in fact occur, then I calculate the appropriate collision response and reset the displacement. This way the objects will never actually intersect in the next frame they wont collide (and get stuck). This method works very nicely.
The above methods don't work for objects that travel at speeds that are so high that the collision happens "between" two frames, but not in the frames before and after. Such objects might be bullets, for example.
Hope this helps,
Richardo
Quote:Original post by RichardoX
...
The above methods don't work for objects that travel at speeds that are so high that the collision happens "between" two frames, but not in the frames before and after. Such objects might be bullets, for example.
In this case the engine has to check the bounding box or sphere collisions on the whole path between two frames. If a possible collision is detected the movement have to be stepped with sub frame accuracy (without rendering) and checked on each sub step. The closest non colliding position will be the last substep before the actual collision.
Viktor
why don't you reverse both, if not one of the objects directional vectors to move until collision stops occuring?
That is what my friend is doing for his breakout game.
That is what my friend is doing for his breakout game.
As Viktor says, the proper way to do the collision detection is to do some maths to calculate if and when the objects would intersect given their current velocity and the time step. If there is an intersection, the math will tell you when the collision occurs. Call this time t. Then just move both objects along their paths with a reduced timestep of t-epsilon, where epsilon is a small number to guard against rounding errors.
Now at this point, you have the objects aaaaalmost touching, but still not. You also know that if they continue in their current direction for even the tiny time epsilon, they will intersect. So from there you can proceed and do whatever reaction you want to collision: both objects stop dead in their tracks, explode, bounce, or whatever you want.
Search the internet for triangle-triangle intersection math, ray-triangle intersection, sphere-triangle intersection or whatever suits your optimization needs. Or better yet, just integrate a collision detection library. They're built to be really fast and you don't have to deal with the math.
At least I find the math pretty tricky, and I had to write some pretty fast collision detection for Bouncy Hunters. :)
Now at this point, you have the objects aaaaalmost touching, but still not. You also know that if they continue in their current direction for even the tiny time epsilon, they will intersect. So from there you can proceed and do whatever reaction you want to collision: both objects stop dead in their tracks, explode, bounce, or whatever you want.
Search the internet for triangle-triangle intersection math, ray-triangle intersection, sphere-triangle intersection or whatever suits your optimization needs. Or better yet, just integrate a collision detection library. They're built to be really fast and you don't have to deal with the math.
At least I find the math pretty tricky, and I had to write some pretty fast collision detection for Bouncy Hunters. :)
Just as a side-note, this book is an all-encompassing masterpiece on collision-detection techniques, IMO. I recommend laying down the $$, especially if you're jumping into 3D collision detection + response.
Quote:Original post by discman1028
Just as a side-note, this book is an all-encompassing masterpiece on collision-detection techniques, IMO. I recommend laying down the $$, especially if you're jumping into 3D collision detection + response.
I've been considering getting that book.... but I wonder if it's going to have anything I dont already know.
Whenever I go to a bookstore and pick a random game physics book off the shelf I find every single thing is familiar, is this any different? Or is it popular only because its well written?
Anonymous Poster above pointed out that to do proper collision detection, it must be checked whether or not the volumes of two objects collide between two frames. This is absolutely correct. However, for most "slowly" moving objects checking at each frame is sufficient. He also noted out that this should be done with bounding boxes/bounding spheres. Using bounding box/sphere collisions will never end up in correct results, just a rough approximation.
Shamino pointed out that moving both (instead of just the other) objects backwards upon collision could solve the problem we have. This is not a good method. It might work for breakout, but with complex 3d meshes it is very difficult to calculate how much the objects should be moved back from each other.
With collision detection, and game physics/mathematics it is important to remember that no model is perfect. It is important to decide what is close enough and go for that. It might be a good idea to use bounding boxes/spheres on one application while it wouldn't necessarily do the trick on another one.
As in all physical/mathematical modelling, we need a model that we use and a method to calculate whatever needs to be calculated. We choose a model that suits us best and use the mathematical methods we know to compute whatever is needed. For example, it is usually not necessary to use Einstein's Theorem of Relativity in most physical applications (especially on games), because classical physics provide us with answers that are "good enough". The same applies with games and collision detection. Choose a model that is good enough and use that. You might save yourself a lot of trouble and end up with "almost as good" results.
-Richardo
Shamino pointed out that moving both (instead of just the other) objects backwards upon collision could solve the problem we have. This is not a good method. It might work for breakout, but with complex 3d meshes it is very difficult to calculate how much the objects should be moved back from each other.
With collision detection, and game physics/mathematics it is important to remember that no model is perfect. It is important to decide what is close enough and go for that. It might be a good idea to use bounding boxes/spheres on one application while it wouldn't necessarily do the trick on another one.
As in all physical/mathematical modelling, we need a model that we use and a method to calculate whatever needs to be calculated. We choose a model that suits us best and use the mathematical methods we know to compute whatever is needed. For example, it is usually not necessary to use Einstein's Theorem of Relativity in most physical applications (especially on games), because classical physics provide us with answers that are "good enough". The same applies with games and collision detection. Choose a model that is good enough and use that. You might save yourself a lot of trouble and end up with "almost as good" results.
-Richardo
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement