Simultaneously collision detection

This topic is 3227 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm thinking of implementing a collision detection system for rectangles in 2D space. That checks for collision between all entities simultaneously. The first step I think of must be checking if any entity's rectangle's travel area from the current frame to the next frame intersects with any others. If any do, find their intersection point and take them two for the next step that is moving them in their velocities to the intersection and something. The first step I don't know how to do. Is there any mathematical formula for it? Or how do I find (if) the intersection between two travel areas? I have searched for it with "Simultaneously collision detection" but didn't find any material that could help. The second step I think I can figure out by myself as so far.

Share on other sites
the words simultaneously and computing do not go well together unforunately.

it's impossible to solve all the contact collision equations simultaneously. Once one collision is resolved, it will cause others, and so on. The only thing you can do is attempt to get as CLOSE to accurate as possible.

That being said, I'm not sure simultaneous collision detection is even a known topic. You should probably search for swept collision detection. And reduce the collision detection scope to between two object.

Then iterate over your scene checking for collisions between pairs of bodies.

Search for broadphase or early rejection and spacial partioning / structuring / querying for how to find the pairs.

[Edited by - bzroom on April 17, 2009 3:47:59 PM]

Share on other sites
Thanks for your info and yes, of course I meant checking them one and one(two at a time).

My way of doing this I though by (Step 1)marking the area(by bounding lines) every moving object(rectangle) is travelling from the current to the next frame. (Step 2) Then checking which objects travel area intersects with others(by one and one of course) and take them two and move them both(simultaneously) to see where they collide.

It was the first step I wondered if there were a mathematical formula for checking if two rectangles movement area intersects(It was that I couldn't find). The second step I think is not that hard to figure out on my own.

Share on other sites
it's called forecasting, to determine where the object _may_ end up. To give you an idea of where to search.

Sounds like you're on the right track, I would look up a swept sphere test to see what swept collision looks like, it gets a lot more complex for shapes like boxes and such but i do believe there are equations. it may be called "spiral motion" ? it's a technique for describing the non linear effects of simultaneously translating and rotating an object.

if i find a source i'll be sure to post it.

Share on other sites
To be more specific the (objects)rects are to be move just linearly. And no rotation so their sides are static to the x and y axis. How is this generally solved?

Share on other sites
I'll point you to a well written GDC tutorial by Brian Eiserloh that explains how to turn collision tests between moving 2D polygons into intersection tests between a segment and a fixed polygon, obtaining exact times and locations of contacts if necessary.
This technique can be combined with conservative advancement: if you know that unless something happens (a collision, an autonomous movement, etc.) objects move linearly for a certain interval, you can find the earliest collision before that horizon (in general, there can be collision groups of more than 2 objects and multiple groups that collide simultaneously) and process it before advancing the simulation to the next collision or to the desired instant.

Share on other sites
Thanks Lorenzo, That PowerPoint article was good. It showed a way to find the collision point for when a shape moves towards another and collides with it.
But the hard issue here comes when they both moves.

Share on other sites
I'm pretty sure you can treat one as stationary and just move the other one relative to it. Only for the purpose of collision detection, of course you'll want to use the correct velocities when computing the dynamics of the collision.

So if body A had a velocity of (1,0) and Body B had a velocity of (0,1), you'd pretend that A was stationary (0,0) and that body B had a velocity of (-1,1).

Share on other sites
Quote:
 Original post by bzroomI'm pretty sure you can treat one as stationary and just move the other one relative to it. Only for the purpose of collision detection, of course you'll want to use the correct velocities when computing the dynamics of the collision.So if body A had a velocity of (1,0) and Body B had a velocity of (0,1), you'd pretend that A was stationary (0,0) and that body B had a velocity of (-1,1).

Yes of coarse, sorry I seem to have missed that part in the .ppt article.
I think that helped enough. Thanks! Rate++;

[Edited by - programering on April 22, 2009 9:13:56 AM]

Share on other sites
'Simultaneous' collision detection shouldn't be hard. You just run your collision detection before you run your physics step. So if A is crashing into B and C at the same time, you mark A as having two repelling forces. Then in your physics time-step, you apply both those forces at once (sum of forces). Thus the collisions are 'simultaneous'.

If, however, you were to apply the forces immediately after the collision were detected, you might get some funky results.

Share on other sites
Quote:
 Original post by visage'Simultaneous' collision detection shouldn't be hard. You just run your collision detection before you run your physics step. So if A is crashing into B and C at the same time, you mark A as having two repelling forces. Then in your physics time-step, you apply both those forces at once (sum of forces). Thus the collisions are 'simultaneous'. If, however, you were to apply the forces immediately after the collision were detected, you might get some funky results.

How?

Share on other sites
Quote:
 Original post by LorenzoGattiI'll point you to a well written GDC tutorial by Brian Eiserloh [...]

I was flipping through the slides because I've implemented basically what's in that article before and I was like "I bet he's going to just skip the rotation part because it's gross" and sure enough he did. :P (You can treat one objects rotation as stationary in regards to another but when when translation is brought into the picture it becomes very interesting. Fun research project though if you've got a few months to waste.)

Share on other sites
Quote:
Original post by programering
Quote:
 Original post by visage'Simultaneous' collision detection shouldn't be hard. You just run your collision detection before you run your physics step. So if A is crashing into B and C at the same time, you mark A as having two repelling forces. Then in your physics time-step, you apply both those forces at once (sum of forces). Thus the collisions are 'simultaneous'. If, however, you were to apply the forces immediately after the collision were detected, you might get some funky results.

How?

Treat forces as vectors. Store the forces being applied to an object during the collision step. Do not apply them during that step. For the physics step, add the force vectors, and apply them. That way, all the collisions are applied simultaneously.

Share on other sites
Quote:
Original post by visage
Quote:
Original post by programering
Quote:
 Original post by visage'Simultaneous' collision detection shouldn't be hard. You just run your collision detection before you run your physics step. So if A is crashing into B and C at the same time, you mark A as having two repelling forces. Then in your physics time-step, you apply both those forces at once (sum of forces). Thus the collisions are 'simultaneous'. If, however, you were to apply the forces immediately after the collision were detected, you might get some funky results.

How?

Treat forces as vectors. Store the forces being applied to an object during the collision step. Do not apply them during that step. For the physics step, add the force vectors, and apply them. That way, all the collisions are applied simultaneously.

I still don't really understand. Maybe a programmatic example would help.

Share on other sites
struct Body;{  Vector V; Vector Forces;};void CollisionDetect(){ /* test all bodies vs each other  accumulate response forces in each Body::Forces */}void Integrate(){ /* iterate each body integrating Forces into V     clear Forces */}void Simulate(){ CollisionDetect(); Integrate();}

Share on other sites
Thanks bzroom. But I think I need to see the code for CollisionDetect() and Integrate() to really understand.

Share on other sites
I don’t think this is such an impossible problem. However, a worst case implementation it is N^2. Here’s what you can do. You calculate possible collisions for every pair of objects. You can always consider one stationary and one moving. You find the first collision at whatever time that occurs. Then you advance all objects along their trajectories to that time, calculate your first collision, recalculate the vectors for you pair of collision objects and start all over again. I’m pretty sure this is how this is typically done. The real challenge is to optimize things so it is no longer N^2 and can be done in real time.

Share on other sites
Quote:
 Original post by polypterusI don’t think this is such an impossible problem. However, a worst case implementation it is N^2. Here’s what you can do. You calculate possible collisions for every pair of objects. You can always consider one stationary and one moving. You find the first collision at whatever time that occurs. Then you advance all objects along their trajectories to that time, calculate your first collision, recalculate the vectors for you pair of collision objects and start all over again. I’m pretty sure this is how this is typically done. The real challenge is to optimize things so it is no longer N^2 and can be done in real time.
What do you mean with N^2 and how is it meant with "in real-time", what's the difference?

Share on other sites
Quote:
 Original post by programeringWhat do you mean with N^2 and how is it meant with "in real-time", what's the difference?

N^2 or N squared is the complexity of the problem. For instance if you have N number of objects and you have to check each object with all other objects the number of checks that needs to be done is N*N or N^2 (^ means power of). So if you have 100 objects that's 10,000 checks. Real time basically means it calculates fast enough to simulates the real word. Like first person shooters and so forth are in real time. N^2 can even be real time for a small number of objects. However if your object list gets large enough it won't be. You should probably organize your objects in such a way that you can eliminate as many object to object checks as possible for each time step you do.

I do think you "CAN" simulate multi-object simultaneous collisions pretty accurately. At any given point you can always find what the next collision will be so I think it's doable.

[Edited by - polypterus on April 24, 2009 3:41:56 PM]

Share on other sites
If you had n^2 collision time and 100 objects thats 10,000 checks.

If you split those 100 objects into two groups which can not interact with each other (other sides of the world) and still have n^2 look up, that's 5,000 checks!

10 groups of 10 objects at n^2 = 1000 checks..

Also real-time means interactive frame rate. Fluid and finite element simulations that take a whole day to compute, are NOT real time. A video game which operates at 60hz is very real-time.

Share on other sites
Quote:
 Original post by bzroomvoid CollisionDetect(){ /* test all bodies vs each other accumulate response forces in each Body::Forces */}

What exactly do you mean with response forces?
Please just show a little more how with sample code.

Quote:
 void Integrate(){ /* iterate each body integrating Forces into V clear Forces */}

void Integrate(){   Body *iterBody = bodies;   for (int i = 0; i < bodyCount; i++)   {       // integrate like this?:       iterBody->V.x = iterBody->Forces.x;       iterBody->V.y = iterBody->Forces.y;       iterBody->V.z = iterBody->Forces.z;       // Clear like this?:       iterBody->Forces.x = 0;       iterBody->Forces.y = 0;       iterBody->Forces.z = 0;       iterBody++;   }}