Jump to content
  • Advertisement
Sign in to follow this  
programering

Simultaneously collision detection

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by bzroom
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).

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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!