Collision Detection and Object Representation in 3D
In Chapter 8, we discussed the relationship between object representation and collision detection. We strive to make our game-world objects as independent from their graphical representation as possible. Instead, we'd like to define them in terms of their bounding shape, position, and orientation. Position and orientation are not much of a problem: we can express the former as a Vector3 and the latter as the rotation around the x-, y-, and z-axes (minding the potential gimbal lock problem mentioned in the last chapter.) Let's take a look at bounding shapes.
Bounding Shapes in 3D
In terms of bounding shapes, we again have a ton of options. Figure 11–12 shows some of the more popular bounding shapes in 3D programming.
Figure 11–12. Various bounding shapes. From left to right: triangle mesh, axis aligned bounding box, and bounding sphere
- Triangle Mesh: This bounds the object as tightly as possible. However, colliding two objects based on their triangle meshes is computationally heavy.
- Axis-Aligned Bounding Box: This bounds the object loosely. It is a lot less computationally intensive than a triangle mesh.
- Bounding Sphere: This bounds the object even less well. It is the fastest way to check for collisions.
Another problem with triangle meshes and bounding boxes is that we have to reorient them whenever we rotate or scale the object, just as in 2D. Bounding spheres on the other hand don't need any modification if we rotate an object. If we scale an object, we just need to scale the radius of the sphere, which is a simple multiplication.
Bounding Sphere Overlap Testing
The mathematics of triangle mesh and bounding box collision detection can be pretty involved. For our next game, bounding spheres will do just fine. There's also a little trick we can apply, which we already used in Super Jumper: to make the bounding sphere fit a little better, we make it smaller than the graphical representation. Figure 11–13 shows you how that could look in case of the space ship.
Figure 11–13. Making the bounding sphere smaller to better fit an object
That's, of course, a very cheap trick, but it turns out that, in many situations, it is more than sufficient to keep up the illusion of mostly correct collision detection.
So how do we collide two spheres with each other? Or rather, how do we test for overlap? It works exactly the same as in the case of circles! All we need to do is measure the distance from the center of one sphere to the center of the other sphere. If that distance is smaller than the two radii of the spheres added together, then we have a collision. Let's create a simple Sphere class. Listing 11–13 shows you the code.
Listing 11–13. Sphere.java, a Simple Bounding Sphere
package com.badlogic.androidgames.framework.math;
public class Sphere {
public final Vector3 center = new Vector3();
public float radius;
public Sphere(float x, float y, float z, float radius) {
this.center.set(x,y,z);
this.radius = radius;
}
}
That's the same code that we used in the Circle class. All we changed is the vector holding the center, which is now a Vector3 instead of a Vector2.
Let's also extend our OverlapTester class with methods to check for overlap of two spheres and to test whether a point is inside a sphere. Listing 11–14 shows the code.
Listing 11–14. Excerpt from OverlapTester.java, Adding Sphere-Testing Methods
public static boolean overlapSpheres(Sphere s1, Sphere s2) {
float distance = s1.center.distSquared(s2.center);
float radiusSum = s1.radius + s2.radius;
return distance <= radiusSum * radiusSum;
}
public static boolean pointInSphere(Sphere c, Vector3 p) {
return c.center.distSquared(p) < c.radius * c.radius;
}
public static boolean pointInSphere(Sphere c, float x, float y, float z) {
return c.center.distSquared(x, y, z) < c.radius * c.radius;
}
That's again exactly the same code as in the case of Circle overlap testing. We just use the center of the spheres, which is a Vector3 instead of a Vector2, as in the case of a Circle.
NOTE: Entire books have been filled on the topic of 3D collision detection. If you want to dive deep into that rather interesting world, we suggest the book Real-time Collision Detection by Christer Ericson (Morgan Kaufmann, 2005). It should be on the shelf of any self-respecting game developer!
GameObject3D and DynamicGameObject3D
Now that we have a nice bounding shape for our 3D objects, we can easily write the equivalent of the GameObject and DynamicGameObject classes we used in 2D. We just replace any Vector2 with a Vector3 instance and use the Sphere class instead of the Rectangle class. Listing 11–15 shows you the GameObject3D class.
Listing 11–15. GameObject3D, Representing a Simple Object with a Position and Bounds
package com.badlogic.androidgames.framework;
import com.badlogic.androidgames.framework.math.Sphere;
import com.badlogic.androidgames.framework.math.Vector3;
public class GameObject3D {
public final Vector3 position;
public final Sphere bounds;
public GameObject3D(float x, float y, float z, float radius) {
this.position = new Vector3(x,y,z);
this.bounds = new Sphere(x, y, z, radius);
}
}
This code is so trivial that you probably don't need any explanation. The only hitch is that we have to store the same position twice: once as the position member in the GameObject3D class, and again within the position member of the Sphere instance that's contained in the GameObject3D class. This is somewhat ugly but, for the sake of clarity, we'll stick to it.
Deriving a DynamicGameObject3D class from this class is also simple. Listing 11–16 shows you the code.
Listing 11–16. DynamicGameObject3D.java, the Dynamic Equivalent to GameObject3D
package com.badlogic.androidgames.framework;
import com.badlogic.androidgames.framework.math.Vector3;
public class DynamicGameObject3D extends GameObject {
public final Vector3 velocity;
public final Vector3 accel;
public DynamicGameObject3D(float x, float y, float z, float radius) {
super(x, y, z, radius);
velocity = new Vector3();
accel = new Vector3();
}
}
We again just replace any Vector2 with a Vector3 and smile happily.
In 2D, we had to think hard about the relationship between the graphical representation of our objects (given in pixels) and the units used within the model of our world. In 3D, we can break free from this! The vertices of our 3D models that we load from, say, an OBJ file can be defined in whatever unit system we want. We no longer need to transform pixels to world units and vice versa. This makes working in 3D a little easier. We just need to train our artist so that he or she provides us with models that are properly scaled to the unit system of our world.