原文地址:http://www.ziggyware.com/readarticle.php?article_id=128
Broadphase Collision Detection
By John Wells, 2007Special thanks to
Krisc for helping get this article online
What is broadphase collision detection?
Simply put, broadphase collision detection is a method of eliminating costly collision tests, avoid redundant tests, and just not testing most of your objects anyways.
"Rubbish!", you say, "How can you determine to objects are not colliding if you never test them together?"
Good question. Well, it turns out the easiest way to figure to out something is not colliding is to create a situation where you know, that the object (and potentially 1000s of others) could never collide with something in the first place!
Can I make Grand Theft Halo 2 with it?
Well, sort of. The broadphase method is just a part of the puzzle; but an enabler of complex games? Sure. The classic problem arises where in making a game; you have two objects, a player and the ground. Testing them for collision becomes easy, and you can use the results to render properly, do physics, or play sound effects. After a while, you've added barrels, trees, and goblins to your game and suddenly testing each object against each other object is getting very difficult.
Big O notation would describe this as an O(n²) problem, which means as your game grows, the performance is dropping exponentially because of all the collision checks. We need to find a method to drop this O notation to a much more linear (or better) performance curve. We may never get to O(1) performance, but with even mildly complex games, we'll certainly have to do something if we want any amount of detail.
Spatial partitioning
Broadphase collision detection is accomplished through a spatial partitioning algorithm, of which there are many known varieties. The two main branches of widely used algorithms either form some sort of grid or bucket system, or use a sorting algorithm. As with any algorithmic choice, no answer is one-size fits all, and there are several pluses and minuses to each method. For my purposes, I need an algorithm that has the following features:
- Creates no heap-based objects during runtime (The 360 hates that!)
- Can take advantage of multiple processors/cores
- Runs quickly, but does not take long to add/remove objects
- Does not limit the world size and works with disparate sized objects
Sort-and-Sweep
Of course no such algorithm exists, but for my purposes, the best choice was a sort-and-sweep algorithm. Also known as sweep-and-prune, this is considered by many to be the naive algorithm to implement, but it can still be very effective when used properly. The idea behind any spatial sorting algorithm is to break the problem of interference detection into a 'greater than' or 'less than' or 'equal to' problem. Implementing this algorithm with a simple array and an IComparer<> instance is actually quite easy and should scale well to many types of games you might think would be unfit for a '1D' implementation. For instance, Grand Theft Halo 2 would be a good candidate, as would any 2D-Platformer, because the action in these games generally takes place on one or two axes. A space shooter, where objects exist (bountifully) on three axes would not be a great choice for this algorithm.
Although it's not intuitive, follow me on this one. To implement this algorithm, take every object in your world, consider where they begin and end on one arbitrary axis, and sort that list. Say we're sorting on the X axis; objects with a bounding box minimum value of 8 sort before an object with a bounding box minimum of 15. We've effectively broken a 3D problem down to 1D - the interesting thing is that as long as your objects are not highly clustered, performance can be amazing.
Delimiters
When breaking the 3D problem down to 1D, we need to keep track of only two things in our array, for each object: where it starts on that axis, and where it ends. Consider the following structure used to represent a delimiter:
struct Delimiter
{
public BoundaryType Boundary;
public MyGameObject Body;
}
enum BoundaryType
{
Begin, End
}
class MyGameObject
{
public BoundingBox Bounds;
//... health, status, etc ...
}
So, for a moment, consider a 1D array, and imagine putting delimiters from every object in our game into the array, and then sorting that array. The only thing we need to ensure is that the 'Body' value has some sort of bounding volume such as an XNA BoundingBox or BoundingSphere. Suddenly, our world can be enumerated in 1D fashion, and in a bit I'll show you how finding objects can be optimized for speed.
Delimiter Comparison
The heart of a sorting algorithm is the comparer, and luckily the .NET Framework already has a standard pattern that will work fine for our needs, plus, by implementing a generic IComparer<Delimiter> class, we get loads of built-in functionality from the System.Array class static methods. Consider the following comparer, which for the purposes of example only compares on the X axis:
class DelimiterComparer : IComparer<Delimiter>
{
public int Compare(Delimiter a, Delimiter b)
{
if (a.Boundary == BoundaryType.Begin && b.Boundary == BoundaryType.Begin)
return a.Body.Bounds.Min.X.CompareTo(b.Body.Bounds.Min.X);
else if (a.Boundary == BoundaryType.Begin && b.Boundary == BoundaryType.End)
return a.Body.Bounds.Min.X.CompareTo(b.Body.Bounds.Max.X);
else if (a.Boundary == BoundaryType.End && b.Boundary == BoundaryType.Begin)
return a.Body.Bounds.Max.X.CompareTo(b.Body.Bounds.Min.X);
else
return a.Body.Bounds.Max.X.CompareTo(b.Body.Bounds.Max.X);
}
}
"Oh gosh," you say, "You've lost me!" Okay, lets try pictures; this concept sounds simple but can get confusing quickly without some visual aid. Consider a small collection of objects, now figure we've scattered them about our world and are arranging them based upon their X axis values only. In the picture below, I've labeled the 'Begin' (as '<') and 'End' (as '>')
of the objects near the axis. Note that the Y and Z axis arrangement of these objects isn't shown below, in fact, the entire point is that at this point we don't care.
Now consider taking the objects above, and sorting them into our array of delimiters. Here's the array:
Filling the array with delimiters for the beginning and end of each object is pretty simple. The Array.Sort() method takes our array, in un-sorted form, and an instance of our comparer class, and creates a sorted array like this one: (The #'s above the array elements show you which begin/end delimiter points to which body)
Finding Interference
Wow, with very little theory, we're at the point where we can begin to detect collisions! Almost, we're actually ready to detect what is called interference, a 1D collision. Going from interference to collision is simple, however, because we can test 'interfering' objects' bounding volumes to determine collision. For rendering purposes, this is almost always enough. In a physics engine, however, we may need to go one step further and find out if the actual objects within the bounding volumes intersect.
There are two approaches to finding interference, first, you could ask the broadphase algorithm to send you each pair of interfering objects, and second you could ask it "Which objects interfere with this one?" If you use the second bit of logic you will be better suited to multiple core execution and can use the .NET IEnumerable<> pattern.
Either way you go, the algorithm is very simple to implement:
- Create the 'Begin' delimiter for an object.
- Use Array.BinarySearch<> to find the index of that delimiter within your array.
- Enumerate through the array from that index on, following rules 4-6.
- If you hit the end of the array, you're done.
- If you hit another 'Begin' delimiter, you've found interference.
- If you pass the 'End' delimiter for the original object, start ignoring rule 5.
- If you hit an 'End' delimiter, construct the 'Begin' delimiter for it and compare to the delimiter at the index from rule 1. When greater than or equal to zero, ignore this delimiter. When less than zero, you've found interference.
Optimizations
The first thing you might notice is that rule 4, above, indicates you might be searching through much of the array looking for interfering objects. A simple optimization is to keep track of which delimiters border void space. This is simple figure out, because each update we have to sort the array, and in that time we can walk through it and mark some delimiters as 'touches void'. In the below diagram, I've started a stack, indicated in text below the array. Every time I hit a 'Begin', I add one, every time I hit an 'End' I remove one. Thus, every time the stack is zero, I know that there are no more objects in that space. I can then amend rule 4, above, to say "Also stop when you hit a delimiter that borders the void." The dotted lines below represent the placement of the 'Touches Void' flags.
When working with the .NET Framework, and especially with the .NET Compact Framework on the Xbox 360, avoiding garbage is a must. Two things we must be aware of are that we don't create new arrays or resize arrays dynamically where possible, and that we don't box values. Boxing is easy to do, for instance if you opt for the IEnumerable<> pattern, you might create the following structure:
struct MyEnumerator : IEnumerable<MyGameObject>, IEnumerator<MyGameObject>
{
//... implementation ...
}
In doing so, you avoid the garbage created by using the yield return keyword, but you will cause boxing (and thus garbage) unless you specifically reference your enumerator type as MyEnumerator, and not through the interfaces it implements. This one can be tricky, and certainly obfuscate your code, so take it with a grain of salt.
To avoid resizing arrays and having portions stored non-contiguously in memory, you might consider using a default large array and keeping track of how many items in the array are 'in use.' Do avoid, however, leaving references to MyGameObject in the unused portion of the array, and consider growing when needed, too. You might be tempted to use List<Delimiter>, which has a .ToArray() method; but watch out, that's a
new array you're playing with!
Every so often, you should evaluate the clustering of the sorted array, and potentially decide to start sorting on another axis. This axis, of course, does not have to be a cardinal axis, but picking X, Y, or Z is usually most straight forward. The best candidate axis could be either fixed, or better yet, the axis where values vary the most. For my Grand Theft Halo 2 example, for instance, this axis would not be the Y axis, because most objects usually cluster on the ground in those kind of games. Less
axial clustering means more 'Touches Void' flags, means fewer array enumerations.
References
- Johnnylightbulb - My project on CodePlex, where I am implementing this algorithm
- Real-Time Collision Detection, book by Christer Ericson - A very useful resource that is invaluable when discovering and implementing any collision related algorithm, an excellent book.
- Erwin Couman's Physics Simulation Forum - Centered around physics, but still useful for non-physics collision detection and trolled by the best of the best of industry experts in the field.
- XNADEV.RU - A C# implementation of Erwin Coumans' Bullet engine (see previous link)
- Open Dynamics Engine - An open source physics engine that has many C and C++ algorithms for collision detection implemented.
- GeometricTools.com - Dave Eberly's site with code and algorithms from his many incredibly useful books.