Sign in to follow this  
PaulCunningham

'Swept Collision' design question

Recommended Posts

I am currently thinking about collision detection for my new game / engine. In a proof of concept app I've implemented Oliii's seperation of axis thingy for convex polys (and very good it is too). However, it's nailed my performance (DevPartner profiler) so I'm thinking of initially performing some quick swept circle tests in either of these 2 forms: A) 'bounding circle' that fully encompases the object B) 'best fit circle(s)' that try to fit the shape as close as possible. Once a basic collision is detected I could then look to use more refined tests (like Olii's or even child circles). Let's assume I go with A for now (as this is where I need the advice). I will potentially get a collison at time t. As the circle is actually bigger than the object this could potentially mean either there is not really a collision or the collision happens at a later time. Do I just say, 'oh well there would be a collison, I'll perform the sweep again with better fit shapes' or is there some other process I can then perform to detect the 'real' time of the collision. The game will be a top down shooter and will usually have many small enemies on screen at once. PS - Appologies if you think this is in the wrong forum and is more of a maths / physics question (I don't :) )

Share this post


Link to post
Share on other sites
For moving convex objects, here is how I would exploit the swept sphere algo :

A col det between bounding volumes is an internal event for your general algorithm, based on conservative tests.

Events are when spheres start collide (tmin(A,B)) and when they stop intersecting (tmax(A,B)). Now you are seeking for real events, that is contact points in space and time between your convex shapes. Such an event necessarilly occurs between tmin and tmax.

Your swept spheres allow you to cull and reduce most of the time-space intervals of potential events quickly. This partition allows you to focus on the real events, that is the output of your collision detection code, which is optimal in terms of algorithmic complexity.

At any tmin, you search for a separating axis and you should cache the closest d-facets involved in A and B. (For instance edge 3 of A against vertex 6 of B). This way, the next checks will be very speedy (roughly 5-6 dot products). I let you imagine the details unless this is what Oiii already explained.

Whatever. Next you recurse, reducing the interval (binary search accelerated with a relative velocity guess) until you find the contact point in a given margin of metric and time tolerance.

Then be sure your FPS won't drop on a 1GHz machine unless your implementation is realy dirty :)

Share this post


Link to post
Share on other sites
http://www.gamedev.net/reference/articles/article1234.asp

here is one very good example on how to do a sphere-sphere collision. Looks bloody quick too (I haven't tried it, but I want to put this in my demo as a broad-phase test).

If you want to mess around with times of collision (sorting collisions by time, processing the first one, ect...), then that algorithm can be very useful, since if you find a time of collision greater than the current minimum time, then you don,t need to refine the collision.

But even if you don't sort the collisions and process them as they come (like I do), that's still useful for a computationaly expensive collision routine (like the one I use). For space shooters, sorting collisions is rather unecessary in my opinion. You want speed over accuracy, and the accuracy is already pretty high.

Also, if you plan on using Axis-aligned bounding boxes for your entities (or even oriented bounding boxes), and you still want to use the swept polygon test, there are lots of optimisations you can add to the algorithm to make it a LOT faster (in my estimate, at least 5 times faster, maybe more).

You can also limit the collisions on enemy ships as just spheres, and not bother with polygons. Polygons are just an approximation of the sprite anyway. Maybe a better one, but spheres are faster. That applies especially for large bullets, obviously.

Also, you may not want to extract the collision data, and just return a true-false, if the objects have collided or not. Again, cutting that out will improve the speed a bit.

There are further optimisations for bullets and segment tests as well.

All the code I provided is intentionaly not optimised, for clarity and readability rather than obfuscation (I'm not sure I succeeded though :)), but I'm planning on writing a well optimised demo of a basic space shooter (at least on the physics part, maybe not on the rendering :)), then a platformer (needs some time-based collision with environment).

The swept method is necessary to a fast paced game, there is no denying that, but what kind of object you use really depends on the performance you require versus the accuracy, and how well simple shapes would approximate the object.

With a decent collision system, the collision process would be transparent, and perform the collision identically to many types of objects (point, segment, sphere, box, polygon), each of which would have it's own little optimisations.

Spheres can be tricky though, the separation axis theorem does not hold on them, since there are an infinite number of planes to test against. But you can approximate a sphere with an octagon or something, or find a clever sphere-polygon test.

Share this post


Link to post
Share on other sites

Spheres can be tricky though, the separation axis theorem does not hold on them, since there are an infinite number of planes to test against. But you can approximate a sphere with an octagon or something, or find a clever sphere-polygon test.


I don't think so Oiii. The separating axis applies to any convex shape. It's just a more specialized version we use for convex polyhedra. The additionnal info it gives is that the separating axis is given by two d-facets. (edge/edge, point/plane, etc...)

What counts is remember this separating plane is perp to the line segment that joins the two nearest points on each convex shape. BTW when these two points become identical, they form the contact point.

So with a sphere it's pretty simple to imagine. A sphere can be seen as a convex polyhedron made of only one vertex and with an extended radius of tolerance for collision. So it can collide with any vertex, edge or face of the polyhedron.

Anyway if you have a graph of connected Voronoi cells with your convex shape, finding the nearest d-facet, thus also the nearest point, on the convex polyhedron is quasi immediate, specially if you maintain frame to frame coherency.

Share this post


Link to post
Share on other sites
Cheers guys.

Quote:
Original post by Charles B
Next you recurse, reducing the interval (binary search accelerated with a relative velocity guess) until you find the contact point in a given margin of metric and time tolerance.


So are you saying that initially sweep to get possible collision and then use discrete steps from tmin to tmax with a better fit shape (or shapes) to find an overlap?

Quote:
Original post by Oliii
The swept method is necessary to a fast paced game, there is no denying that, but what kind of object you use really depends on the performance you require versus the accuracy, and how well simple shapes would approximate the object.


If you follow the link in my sig you can see my first game Alien Abduction*. The new game will contain similar looking models and sprites so simple shapes should be more than adequate really.


*AA uses a combination of Circle / AABB overlap tests but I'd like to enhance to sweep testing for the new game.

[Edited by - PaulCunningham on July 8, 2004 6:03:49 AM]

Share this post


Link to post
Share on other sites
In the static case, I guess you can still use a separation axis algo in the same way. The extra axes would be the normals of the each of the two lines tangent to the circle and passing through a vertex of the polygon, like Charles said.

but you can't do that in the dynamic case.

On the other hand, if you assume the sphere to be nothing more than a point with a radius, then you get the case where the ball will collide way outside the polygon if it has sharp corners. You'd need to bevel the polygon at the corners, like create a new plane, to smooth out the corner, and then the approximation will be improved. The sphere would still collide outside the polygon, but by not much.

it's the method used by Stan Melax in his Dynamic Plane Shifting approach for collisions against BSP trees.

...That's my intuition anyway.

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