Bounding Shapes

Once we have the final positions for our objects, we can perform the collision tests, which boil down to testing for overlap. But what overlaps? Each of our objects needs to have some mathematically defined form or shape that bounds it. The correct term in this case is bounding shape. Figure 8-8 shows a couple of choices we have for bounding shapes.

Triangle Mesh Axis Aligned Bounding Box Bounding Circle Figure 8-8. Various bounding shapes around Bob

The properties of the three types of bounding shapes in Figure 8-8 are as follows:

Triangle mesh: This bounds the object as tightly as possible by approximating its silhouette with a couple of triangles. It requires the most storage space, and it's hard to construct and expensive to test against. It gives the most precise results, though. We won't necessarily use the same triangles for rendering, but instead just store them for collision detection. The mesh can be stored as a list of vertices, where each subsequent three vertices form a triangle. To conserve memory, we could also use indexed vertex lists.

■ Axis-aligned bounding box: This bounds the object via a rectangle that is axis aligned, which means that the bottom and top edges are always aligned with the x-axis, and the left and right edges are aligned with the y-axis. This is also fast to test against, but less precise than a triangle mesh. A bounding box is usually stored in the form of the position of its lower-left corner plus its width and height. (In the case of 2D, these are also referred to as bounding rectangles).

■ Bounding circle: This bounds the object with the smallest circle that can contain the object. It's very fast to test against, but it is the least precise bounding shape of them all. The circle is usually stored in the form of its center position and its radius.

Every object in our game gets a bounding shape that encloses it, in addition to its position, scale, and orientation. Of course, we need to adjust the bounding shape's position, scale, and orientation according to the object's position, scale, and orientation when we move the object, say, in a physics integration step.

Adjusting for position changes is easy: we simple move the bounding shape accordingly. In the case of the triangle mesh we just move each vertex, in the case of the bounding rectangle we move the lower-left corner, and in the case of the bounding circle we just move the center.

Scaling a bound shape is a little harder. We need to define the point around which we scale. Usually this is the object's position, which is often given as the center of the object. If we use this convention, then scaling is easy as well. For the triangle mesh we scale the coordinates of each vertex; for the bounding rectangle we scale its width, height, and lower-left corner position; and for the bounding circle we scale its radius (the circle center is equal to the object's center).

Rotating a bounding shape is also dependent on the definition of a point around which to rotate. Using the convention just mentioned (where the object center is the rotation point), rotation becomes easy as well. In the case of the triangle mesh, we simple rotate all vertices around the object's center. In the case of the bounding circle, we do not have to do anything, as the radius will stay the same no matter how we rotate our object. The bounding rectangle is a little bit more involved. We need to construct all four corner points, rotate them, and then find the axis-aligned bounding rectangle that encloses those four points. Figure 8-9 shows the three bounding shapes after rotation.

Figure 8-9. Rotated bounding shapes with the center of the object as the rotation point

While rotating a triangle mesh or a bounding circle is rather easy, the results for the axis-aligned bounding box are not all that satisfying. Notice that the bounding box of the original object fits tighter than its rotated version. This leads us to the question of how we got our bounding shapes for Bob in the first place.

0 0

Post a comment