- Introduction
-
With the advent of 3D technologies in the past several years, programmers have made radical changes in how they program applications, especially when regarding computer games. Collision detection is an essential part in 3D games. It ensures that the game physics are relatively realistic, so that an object does not cut through other objects or hovers when it should fall. How well a game can detect collisions is an integral part of the believability and enjoyment of the game. A poorly implemented collision detection system can be a bane to a product, whereas an excellent implementation can produce amazing results.
The two main parts in collision detection are detecting whether or not a collision has happened, and if so, responding to the collision. Discovering if a collision has occurred is the basis of this problem.
While responding to the collision is computationally much easier than discovering a collision, it can still pose several problems in how objects are going to react to each other. In modern computer games, if the character runs into a wall, then the character will either stop or will continue 'sliding' along the wall. However, if this character comes up to a movable box, then the character might start pushing the box instead. Or consider a ball bouncing around in a room. The ball is going to behave quite differently than a person walking around in a room.
The first step is to see if the viewer, or the 'camera', will move through any polygons or planes on its next move. Instead of just calculating if the camera will hit any particular polygon, all polygons are extended indefinitely along their plane. This makes calculations easier to initially perform. If the camera does not intersect the plane, then no calculations are necessary to see if the camera will cross through the polygon itself. This saves some computation by using an easier calculation (with less processing). When a collision with the plane is detected, further processing is done to check if the camera intersects the polygon itself.
2D applications can easily detect collisions by determining if two objects are trying to occupy the same area. If the circle in Figure 1 is trying to get to the triangle, it checks in all available directions. The circle cannot move to the right, since it is blocked by the gray wall, so its only option is to move down. Such a world can easily be represented by a 2D array.
Many older 2D games use a static drawing for the scene, which allows for only a single perspective, but it simplifies the process of drawing the scene. In comparison, 3D graphics require a large amount of mathematical calculations to render each scene.
Figure 1. 2D grid.
- Collision Detection Mathematics
-
A vector is essentially a directed line segment which has direction and magnitude. With graphics, this can be translated as the angle and length or distance. But the magnitude can also represent other factors such as the force or speed of an object. A scalar, as opposed to a vector, only has magnitude, but not direction.
Vectors differ from a point on a Cartesian plane, because the point represents only one spot on the plane, whereas a vector is the difference between two points on a plane. Vectors can be represented in a variety of ways, as shown in equations 1-1 through 1-3. A vector V can be represented as the difference of two points P1 and P2 (1-1), the difference of the components of those two points (1-2), or by the constituent vector components (1-3). A 2D world has only x and y components, whereas a 3D world adds the z axis and another component to each vector. Figure 2 gives a visual representation of these equations on a Cartesian plane.V = P2 - P1 ( 1-1 ) V = (x2 - x1, y2 - y1) ( 1-2 ) V = (Vx, Vy) ( 1-3 )
Figure 2. Vector representation.
Vectors play an important role in collision detection by determining how far apart objects are from each other. The magnitude or length of a vector can be found by taking the square root of the sum of the squares of each of the vector's components.2D Vector: |V| = sqrt(Vx2 + Vy2) ( 1-4 ) 3D Vector: |V| = sqrt(Vx2 + Vy2 + VZ2) ( 1-5 )
To normalize a vector, each component of the vector is divided by the magnitude of the vector. When all of the vector components are added together, they will equal 1. A plane's normal is important to provide realistic lighting and collision detection.Vx = Vx/|V| ( 1-6 ) Vy = Vy/|V| ( 1-7 ) Vz = Vz/|V| ( 1-8 ) Vx + Vy + Vz = 1 ( 1-9 ) Planar Equation: Ax + By + Cz + D = 0 ( 1-10 )
Figure 3. Plane normal.
A plane is defined by three non-collinear points. (x, y, z) from the planar equation are the coordinates of a point on the plane, and the coefficients A, B, C, and D are constants which describe the spatial properties of the plane. A, B, and C can also represent a vector (a, b, c) which is a normal of the plane.
- Back-face Culling
-
Back-face culling is the process of not rendering a polygon if its face is turned away from the viewer. A point can be identified as being on the inside or outside of a plane surface according to the sign of the plane equation. If Ax + By + Cz + D < 0, then the point (x, y, z) is on one side of the plane surface. If Ax + By + Cz + D > 0, then the point (x, y, z) is on the other side of the plane surface. Otherwise, if the planar equation is equal to zero, the point (x, y, z) is on the plane.
On the average, about half of the polygons in a scene will not be visible by the viewer. Eliminating these unseen polygons can help the performance of viewing the scene since not nearly as many polygons need to be rendered or be involved in the collision detection. This can save an enormous amount of time in calculating where an item may collide. One technique which can save time is the use of Binary Space Partitioning (BSP) trees, which divide up a world into convex hulls to remove unnecessary polygons.
To determine whether a plane is facing the viewer or not, the dot product is used to get the angle between the plane's normal and a vector from the viewer's position to a point on the plane. If the angle is between 90 and 270 degrees, then the polygon is facing the viewer. Otherwise, the polygon or plane is not facing the viewer.
- Sphere - Plane Collision
-
One way to detect a collision in a 3D world is the sphere - plane detection method. The demonstration program which was created with PIGE used this technique to detect if the user had bumped into an object. This demo is explained further in chapter 5, and the source code is available in Appendix A. The sphere-plane method is relatively easy to compute since not every polygon of a more complex model has to be compared to the environment to see if a collision has occurred. The viewer or camera can be thought of as one solid entity, such as a ball, instead of a human with several limbs.
Detecting collisions with a sphere tends to be easier to calculate because of the symmetry of the object. The entire surface on a sphere is the same distance from the center, so it is easy to determine whether or not an object has intersected with a sphere. If the distance from the center of the sphere to an object is less than or equal to the sphere's radius, then a collision has occurred.
Figure 4. Sphere - plane collision.
The main point is not to let the sphere get too close to the plane. Before doing so, every plane needs to have its own normal vector and D value, which are taken from the planar equation (1-10).
The distance between a vertex, which is the sphere's center point in this case, and the plane is calculated by taking the dot product of the plane's normal and the sphere's position.
distance = plane.normal · sphere.position ( 1-11 )
Depending on which side of the plane the sphere is on, the distance value can be either positive or negative. If the distance becomes zero, then the sphere is intersecting the plane, which is generally not a desirable effect when detecting a collision. This can be corrected by subtracting the sphere's radius from the distance.
Waiting for an object's distance to reach zero before detecting a collision will not always work. If the sphere's velocity is high, it might pass entirely through the plane on its next move. The way to check for this situation is to see if the distance to the plane has either turned negative or positive. If the sphere passed through the plane, the distance's numeric sign will change. If the numeric sign changes, then a collision occurred.
When checking for a collision, two points are important: the distance between the sphere and a plane should not become zero, and the numeric sign of the distance also should not change. If it does change, then the sphere has moved through the wall.
The game program will first check if a collision will result when the object moves in the desired direction. If there is a collision, then the program will respond appropriately, such as refusing to move in the desired direction.
- Links
-
- Collision Detection & Response (pdf)
- NeHe Collision Detection
- Flipcode: Collision detection tutorial
- CFXweb 3D graphics tutorials
- http://silcon.silcon.com/~brink/papers/collisions.html
- http://apgsoftware.co.uk/gl/collide.html
- Black Art of Macintosh Game Programming
- Computer Graphics C Version
- Source Code
-
- Collision.c - source code from Nanosaur
- Source code from peroxide.dk
- Map.c - source code from Chapter 18 of Black Art of Macintosh Game Programming
Page created: 25. November 2001
Last modified: 31. October 2003