Sign in to follow this  
FlorianapoliS

Seperating objects after collision?

Recommended Posts

FlorianapoliS    122
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.

Share this post


Link to post
Share on other sites
jyk    2094
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...)

Share this post


Link to post
Share on other sites
RichardoX    175
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
Shamino    100
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.

Share this post


Link to post
Share on other sites
Antimode Siker    146
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. :)

Share this post


Link to post
Share on other sites
discman1028    212
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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?

Share this post


Link to post
Share on other sites
RichardoX    175
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

Share this post


Link to post
Share on other sites
suggestion...
Do you Really need to know exactly When the ships collide?
I personally find that exact timing of the collision, is less important than the outgoing velocities afterwards. The collision only happens for an instant, its the after effects that the human eye will see as obviously right or wrong.

even as the objects are interpenetrating over a few timesteps, the normal of the contact plane isn't going to be changing all that much, so you can get away with approximating it...

so rather than find exact time of collision, i just calculate what the new velocities should be, then apply those to the previous position of each object.
cheap, stable, looks good...

Share this post


Link to post
Share on other sites
Antimode Siker    146
Well, there is a surprising fact about the time issue. The reason for calculating the time of the collision isn't really that you need to know exactly /when/ it happens, even that that's a nice side effect. The reason is that you need to know exactly /what/ happens instead.

By what I mean what did the object collide against? What will happen is that you do your ray-triangle intersection tests, and the ray will intersect a number of triangles. How do you know which one is the one you will collide with? Well, from the math you easily get the time of the collision. So to find the triangle you will collide with, you just pick the one which would take the least time to get to giving your current velocity vector.

Now if this time actually is longer than your whole timestep, the triangle is so far away that you won't collide with it at all within the timestep. It might be on the other side of the map for all you know. So then there's no collision.

Share this post


Link to post
Share on other sites
discman1028    212
Quote:
Original post by Anonymous Poster
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?


This is not a general physics book, but a book completely on collision detection. Reviews say it is "all-encompassing" with all approaches, and he speaks from experience. The author is an expert, and posts on this forum actually. See his site (http://realtimecollisiondetection.net) here. He also posts corrections to his book on the site, which is very cool.

I'm not an expert on collision detection, but I want to be someday, and this book came highly recommended.

Share this post


Link to post
Share on other sites
FlorianapoliS    122
Thanks for all the suggestions, I might look into trying to calculate the time of the collision. So is the basic idea that I send out rays from one model (from its verticies?) and check to see if they collide with any triangles on the other model. I can then use the model that sent out its rays velocity to calculate the time taken to get to the intersection point, and find the triangle with the lowest time taken, and if that is lower than my timestep I can move the model to pos += vel * time_taken - epislon and do my collision response?

Cheers,
Mark.

Share this post


Link to post
Share on other sites
Antimode Siker    146
Yeah, that's the basic idea. What you would normally do though is to just send out one ray from the center of your object in the direction of your velocity vector. Then you would aproximate your object in some way. Say you aproximate it with a bounding sphere. Then you wouldn't actually test ray-triangle but sphere-triangle for a sphere with a certain radius. You can use other aproximating shapes, but try not to use the whole model. That's very slow - for each model triangle, you would have to test against all potential trianges possible to collide with. Say that you have 1000 potential triangles to collide with and your model has 1000 triangles too. Then you have to perform 1000*1000 triangle-triangle intersection tests. As you add more triangles this grows very quickly.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this