I am placing myself in the following situation: in the horizontal plane, a circle is placed among convex polygons with which it can collide (but polygons do not collide with each other). Each object is given an initial velocity, yet none of the objects rotate. I want to implement a collision detection system, which I will then use to make the ball bounce on the polygon edges. I know (or can find out on my own) any necessary formulas for checking if a polygon edge and a circle intersect or eliminating any overlaps, and can also implement a naive underoptimized system. What I am looking for is suggestions about usual algorithmic optimizations of this situation, in order to reduce as much as possible the amount of overlap (or collision) checks. The goal of this is to compare my own personal collision detection method with the generally used ones. Since both my method and the usual methods benefit from space partitioning algorithms, I am also looking for at least two different collision detection system optimizations: one which uses space partitioning, and one which does not. Thank you.

Ok, so basically you're asking about space partitioning algorithms/data structures, right? Here are some which you could use:

1. Quadtrees
2. Sphere trees
3. AABB trees
4. RDC - Recursive Dimension Check - it's solely algorithm, rather than data structure, basically you pass in vector of objects, and it returns vector of groups of objects that collide with each other.
5. Brute force - in some situations, when there won't be too many objects, it may be fastest.

Obviously, you can find info about any of them on Google.


Btw, I assumed your simulation will be in 2D.

Quote:Original post by Koshmaar
Ok, so basically you're asking about space partitioning algorithms/data structures, right?

I'm asking about any optimizations, including ones that do not use space partitioning. And thank you for your answer.

Quote:Btw, I assumed your simulation will be in 2D.

I mentioned it was in the 2D plane.

This sounds like you're after the kinds of algorithms that would be used in a pinball game.
In that case probably none of your polygons would be moving, though moving polygons do make a big difference as to how you handle them.

In cases like that, instead of binary partitioning, you can have a grid/lookup system, whereby you take the x & y coordinates, and quantise them and use them as lookup into a grid cell containing all the polygons that you need to test against.

Another optimisation might be removing edges, or even entire polygons for which the circle can never come into contact with.

Quote:Original post by ToohrVyk
The goal of this is to compare my own personal collision detection method with the generally used ones. Since both my method and the usual methods benefit from space partitioning algorithms, I am also looking for at least two different collision detection system optimizations: one which uses space partitioning, and one which does not.

Unless you are going to be testing your circle against, oh, hundreds of convex polygons, collision detection isn't likely to be a bottleneck in the setup you describe, so the optimization may be wasted effort. (Assuming your target platform is a PC and not something small and slow like a cellphone, that is.)

For a small number of objects, a brute force approach is often faster than trying to do something clever with spatial partitioning or some other broad-phase method. It's hard to say exactly how small that number is, but it may range from, say, tens of objects to hundreds of objects, depending on your target platform, implementation language, and lots of other parameters.

For a brute-force approach you want to do a number of things, including:

1. Storing your objects (the convex polygons) in a cache-efficient format.
2. Test not against the convex polygons directly, but encapsulate them in a bounding volume (such as a circle or axis-aligned bounding box) and test your circle against the bounding volume before testing against the convex polygon. This serves to quickly prune away the polygons you cannot possibly be colliding with.
3. Use an efficient algorithm for testing the circle against the polygons (when the bounding volume wasn't able to exclude the polygon from testing).

For a system using a broad-phase method, your best bet is probably a grid-based approach, where you map the polygons (or, rather, their bounding volumes) into a grid, and only test your circle against the polygons that map to the grid squares overlapped by the circle.

Note that you can work in a space where the circle is stationary by subtracting off the velocity of the circle from the velocities of the polygons (i.e. in the space of relative movement).

You would need to specify additional information if you hope for a more detailed answer (such as how many polygons there are, how many sides they have, how large they and the circle are, how large the velocities are, size of the simulation world, the objects' distribution in the simulation world, etc).

Quote:Original post by Christer Ericson
Unless you are going to be testing your circle against, oh, hundreds of convex polygons, collision detection isn't likely to be a bottleneck in the setup you describe, so the optimization may be wasted effort.

I want to compare two general methods of collision detection. In many real-world situations, these would not be used without prior optimization, which is why I need to in order to perform the relevant comparisons.

Quote:For a small number of objects, a brute force approach is often faster than trying to do something clever with spatial partitioning or some other broad-phase method.

Let's then make a small modification to the setup: I have a very large amount of circles which can collide with a very large amount of polygons, and everything is moving.

Quote:
For a brute-force approach you want to do a number of things, including: [...]
For a system using a broad-phase method, [...]

Thank you for your input.

Quote:You would need to specify additional information if you hope for a more detailed answer (such as how many polygons there are, how many sides they have, how large they and the circle are, how large the velocities are, size of the simulation world, the objects' distribution in the simulation world, etc).

I am trying to keep the setup as general as possible, so there would no limit on object sizes or speeds, and no specific information on information.

Quote:Original post by ToohrVyk

Quote:You would need to specify additional information if you hope for a more detailed answer (such as how many polygons there are, how many sides they have, how large they and the circle are, how large the velocities are, size of the simulation world, the objects' distribution in the simulation world, etc).

I am trying to keep the setup as general as possible, so there would no limit on object sizes or speeds, and no specific information on information.

I think you may be missing something fundamental here; optimization is all about exploiting information! There is no one method that's better than others in some general sense. Algorithms are tuned for certain input parameters. For optimization to make sense, you have to define the parameters (and the more specific you can be, the better you can optimize for them). This follows trivially from the fact that if you have no information at all, you clearly cannot even begin to approach the problem.

Your modified problem does not change what I suggested earlier, other than that you no longer can work in the space relative to the movement of the one circle. As a broad-phase method I would still suggest using a grid. I would still recommend bounding the convex polygons in a simpler bounding volume and I would suggest a "speed box" approach, where you let the bounding volume encapsulate the volume/area swept by the object under motion.

For the narrow-phase, I would suggest utilizing that the polygons are convex, using O(log n) binary search to locate edges that may be in collision, and pruning edges that are backfacing. Overall, I would pay attention to the design and layout of the involved data structures to avoid cache misses and branch penalties.

I'm afraid that's about as precise one can be with the little information you are willing to specify. People can of course suggest that you should use some other spatial partitioning method (e.g. trees of various kinds), but for a generic problem they would be no more efficient than a grid-based solution (indeed, they would likely have a lot of cache inefficiencies that a grid-based solution would not have).