# 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

For *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

Knowing the point of origin

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,

The *point* function returns the coordinates of a point on the circle defined by a specific angle (between 0 and

where

## Bounding Boxes

The same tutorial introduced bounding boxes, or more precisely, axis-aligned bounding boxes, also called *AABB*s. 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