Continuous Physics Engine's Collision Detection Techniques

Question

I'm working on a purely continuous physics engine, and I need to choose algorithms for broad and narrow phase collision detection. "Purely continuous" means I never do intersection tests, but instead want to find ways to catch every collision before it happens, and put each into "planned collisions" stack that is ordered by TOI.

Broad Phase The only continuous broad-phase method I can think of is encasing each body in a circle and testing if each circle will ever overlap another. This seems horribly inefficient however, and lacks any culling.

I have no idea what continuous analogs might exist for today's discrete collision culling methods such as quad-trees either. How might I go about preventing inappropriate and pointless broad test's such as a discrete engine does? I also would like to be able to see collisions more than 1 frame ahead to.

Narrow Phase
I've managed to adapt the narrow SAT to a continuous check rather than discrete, but I'm sure there's other better algorithms out there in papers or sites you guys might have come across.
What various fast or accurate algorithm's do you suggest I use and what are the advantages / disatvantages of each?

Final Note:
I say techniques and not algorithms because I have not yet decided on how I will store different polygons which might be concave, convex, round, or even have holes. I plan to make a decision on this based on what the algorithm requires (for instance if I choose an algorithm that breaks down a polygon into triangles or convex shapes I will simply store the polygon data in this form).

Answer 1

I am really just throwing ideas around here. Assuming you have (at the very least) the current position and next position; for each frame.

You would need two separate broad phases, followed by your narrow phase:

• One that figures out that a collision will occur.
• One that figures out roughly where the collision actually occurs (e.g. a broad phase/inaccurate SAT)
• Finally your narrow phase would improve the result of the second broad phase.

Initial Broad Phase

You could look into spatial hashing (using the next position, not current) for the initial broad phase. This would partition your problem space nicely into groups of collision candidates.

Second Broad Phase

Do a binary multi-sample using the circle intersection method you described. In other words:

left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

That accuracy tweak could also take distance into consideration - I think using the 'length squared' of next - current would get a pixel-perfect result.

Narrow Phase

Do a binary multi-sample using something like PMask - the logic will be exactly the same as above; just using a different collision routine.

Finally

You will be able to work out the time-of-intersection from pointOfCollision, current and your current speed and acceleration (assuming you have a reasonable integrator).

Answer 2

Alright, I've seen you've updated your question so as to be more specific. I'll try and help you out some more.

For your first broad-phase check, I would strongly recommend spatial hashing.

Essentially, you divide your screen into equal-sized grids. Then, if an object lies within a grid, you add it to a "bucket" in a 1D hash table.

That's your first check done. If objects aren't in the same bucket, it would be impossible for them to intersect.

Continuing with that, you now have a list of buckets with objects (potentially) in them. You can do another broad-phase check here by either:

A.) Dividing this bucket into 4 other buckets, and checking the resulting 1D hash table. If they aren't in the same bucket, no collision.

Or:

B.) Doing a simple distance check and keeping the width and/or height of the object in mind to ensure accuracy.

But what about when you potentially have a collision?

Then I would recommend something along the lines of this. It's essentially a kind of mix between polygonal collision (for complex shapes) or rectangle/circle for less complex shapes.

Also, if you really want to "catch collisions before they happen and store them" then you can always do something like this:

If two objects are in the same bucket, then they might collide.

Furthermore, are the objects close enough that they may collide soon? (Taking into account velocity, object size and distance)

If the answer to both is yes, then go ahead and store it to do an intersection test later.

---

"Old answer

Well, unfortunately I have lost track of my "All Collision Types and What They Are Used For" Handbook. :)

However, even though this is an extremely broad queston, I'll get you started.

There's a good (answered) question pertaining to something like this here.

As well as an article by the people who made N and N+ over here.

Not to mention, you've got the good ol' fallback Per-pixel Collision.

I sincerely doubt that anyone will have a list handy of each and every type of collision, but this should help get you started.

However, I should mention that the type of collision you need (and will end up using) largely depends on the type of game you are creating. That's why you find tutorials - most people assume you have an idea of what you want, so they help you in that specific area. I realize that most of my links are tutorials on a specific subject, but I think a tutorial will honestly help you more. A list is one thing, but if you read about each bulletpoint yourself, you can come to a more educated decision that will likely suit your needs more specifically.