# Collision Geometry - Review

The most important geometrical objects in Flatland are lines, rays, line segments, rectangles, spheres, and polygons.

During the last few tutorials, we learned how to use most of these geometrical objects to do collision detection. In this tutorial, we will give a mathematically sound review of the concepts used in those previous tutorials and explain how to use them in a game project.

## Rays and Line Segments

The tutorial about basic line intersection used an ad hoc approach to lines and line segments. We now want to define those ideas a bit more rigorously.

A ray starts at a specific point, its point of origin, and extends infinitely in a specified direction. To work with rays in games, it is useful to represent them by parametric functions. Let be a ray, its point of origin and a vector specifying the direction of the ray, then can be defined as follows:

For , the function results in the point of origin of the ray. As grows, we ride on the ray, further and further away.

A line segment is a ray with an end point, that is, a line segment actually stops somewhere. A line segment can be represented using the same function definition, but with a closed interval as its domain:

Now, as before, for we are at the point of origin of the line segment and for we are at its end point.

Knowing the point of origin and its endpoint , the direction vector of a line segment can be easily computed as follows: .

To store rays and line segments in C++, a simple structure is sufficient:

The ride function returns the point on the ray or line segment after riding along on the ray or line segment for a specified amount of time.

In addition to the starting and end point, the line segment structure also computes the normal of the segment, in counter-clockwise order.

## Bounding Spheres

The tutorial about basic collision detection introduced bounding spheres. A sphere can be defined by two variables — a vector representing the centre of the sphere, , and a scalar for its radius, :

The point function returns the coordinates of a point on the circle defined by a specific angle (between 0 and ). The coordinates of the point are computed using the parametric form of the circle:

where is a parametric variable in the range to , interpreted geometrically as the angle that the ray from to makes with the positive -axis.

## Bounding Boxes

The same tutorial introduced bounding boxes, or more precisely, axis-aligned bounding boxes, also called AABBs. Those boxes can be represented by two points, the upper-left and the lower-right point:

To increase accuracy, one could ditch the requirement for axis parallelity. Unfortunately, the price for increased accuracy is a far more complicated collision detection test. We will thus postpone the discussion of those bounding boxes to a later time.

What we could do, however, is to use capsules, for example, to define bounding boxes around humanoids. A capsule is a cylinder in 2D, with two hemispheres attached to the top and bottom, or a rounded rectangle.

To define such a capsule, a line segment and a radius are needed:

## Polygons

Another important geometrical object are polygons. The word polygon is derived from the Greek words ολύς, or polýs, which means many, and γωνία, or gōnía, which means angle. A polygon is thus an object with many points or angles.

To work with polygons, it is sufficient to store all its vertices and to compute its centroid:

Please note that for the moment, only convex polygons are supported.

The bell0bytes game engine provides all of those classes in the mathematics::geometry namespace. You can download the source code here.

## References

• Game Programming Algorithms and Techniques, by S. Madhav
• Tricks of the Windows Programming Gurus, by A. LaMothe
• Wikipedia