Collision Detection Overview
Collision detection is the process of determining whether objects in a game world overlap each other. The XNA Framework provides several classes and methods to speed implementation of collision detection systems in games.
- Bounding Volume Classes
- Non-Bounding Volume Classes
- Contains and Intersects Methods
- Adding New Collision Data Structures
Bounding Volume Classes
The XNA Framework has three classes that represent three-dimensional areas in the world. You can use the bounding volume classes to approximate the volume occupied by models with shapes that are less expensive to do collision checks with. All of the bounding volume classes support intersection and containment tests with each other and the plane and ray classes.
The BoundingSphere Structure represents the space occupied by a sphere.
There are several benefits of using a bounding sphere for collision detection.
- Sphere to sphere checks are very fast. To check for collision between two spheres, the distance between the centers of the spheres is compared to the sum of the radii of both spheres. If the distance is less than the combined radii of both spheres, the spheres intersect.
- The BoundingSphere Structure class is compact. It stores only a vector representing its center and its radius.
- Unlike a bounding box, a bounding sphere doesn’t need to be recreated if the model rotates. If the model being bounded rotates, the bounding sphere will still be large enough to contain it.
- Moving a bounding sphere is inexpensive; just add a value to the center.
There is one major drawback to using the bounding sphere class for collision detection.
- Unless the object being approximated is sphere shaped, the bounding sphere will have some empty space, which could result in false positive results. Long narrow objects will have the most empty space in their bounding spheres.
The BoundingBox Structure represents the space occupied by a box. The bounding box class is axis aligned. Each face of the bounding box is perpendicular to the x-axis, the y-axis, or the z-axis.
There are several benefits of using the bounding box for collision detection.
- The bounding box class fits rectangular shapes aligned with the axis very well. Compared to the bounding sphere class, the bounding box class provides a much tighter fit for non-rotated rectangular objects.
- Because the bounding box class is axis aligned, you can make certain assumptions that result in collision checks between bounding boxes being quicker than a bounding box that can be rotated.
There are a few drawbacks of using the bounding box for collision detection.
- Rotating a bounding box causes it to no longer be axis aligned. Because of this, if you rotate a model being bounded, you will need to recreate the bounding box. Doing so can be slow, since all the points in an object are iterated through to get the bounding box. If the model has not changed orientation, you can translate the bounding box instead of recreating it.
- If the model being bounded is not aligned to the axis, the bounding box will have some empty space. The amount of empty space will be greatest when the object is rotated 45 degrees from an axis.
- Empty space in the bounding box can result in false positives when checking for collision.
You can use BoundingFrustum Class to create a bounding volume that corresponds to the space visible to the camera. You create a bounding frustum from the combined view and projection matrix that the camera is using currently. If the camera moves or rotates, you need to recreate the bounding frustum. The bounding frustum isn’t used to determine when two objects collide, but rather when an object is in collision with the volume of space viewable by the camera. Objects that do not intersect and are not contained by the bounding frustum are not visible to the camera and don’t need to be drawn. For complex models, this can save the graphics card a lot of work.
Non-Bounding Volume Classes
The Plane Structure describes a plane in space. The plane is defined by a vector perpendicular to the plane and a point on the plane. The plane class supports intersection tests with the bounding volume classes. The plane class’s intersection test returns the tested object's position relative to the plane. The return value indicates whether the object intersects the plane. If the object does not intersect the plane, the return value indicates whether the object is on the plane’s front side or back side.
The Ray Structure describes a ray starting at a point in space. The ray structure supports intersection tests with the bounding volume classes. The return value of the ray intersection tests is the distance the intersection occurred at, or null if no intersection occurred.
Contains and Intersects Methods
Bounding volume classes have methods to support two types of collision tests: intersection tests and containment tests. The intersects methods check whether the two objects being tested overlap in any way. As soon as the test finds that the objects do intersect, it returns without trying to determine the degree of the intersection. The contains methods determine whether the objects simply intersect or whether one of the objects is completely contained by the other. Since the intersects methods need only determine whether an intersection occurred, they tend to be faster than the contains methods. Use the contains methods only when the degree of intersection is relevant.
Adding New Collision Data Structures
When implementing other bounding volume classes and intersection tests, you will probably need to add a custom content pipeline processor. For example, your game might need to use convex hulls for collision detection. You could use a custom processor to determine the convex hull and then place it in the model's tag field. Then, when the model is loaded at run time, the convex hull information would be available in the model. For more information, see Extending an XNA Framework Standard Processor.