How to Design a Generic Collision Detection System?

Question

I'm designing a C++ 2D collision module, and I ran into a problem designing a system where the collider is unaware of the shape it's colliding against.

I'd like to have a abstract base class called Collision Component and the subclasses define the specific shape (circle, rectangle, polygon, etc...).

The Quad tree and Axis Aligned Bounding Box checks are fine. The difficulty I ran into is when I'm calculating intersection tests. I don't know how to define a function in the parent class similar to this:

bool CollisionComponent::IsIntersecting(CollisionComponent* other);

The easiest approach is to cast other to specific subclasses and invoke overloaded functions:

bool IsIntersecting(const Circle& a, const Circle& b);
bool IsIntersecting(const Rectangle& a, const Circle& b);
bool IsIntersecting(const Line& a, const Circle& b);
// on and on

I prefer not to implement functions this way.

I thought of breaking down polygons to its elements, and pass an array of segments into a function.

bool IsIntersecting(const std::vector<Line>& relevantSegments);

Although this would be more robust, I feel like this is more expensive, and I may lose precision when interpreting curves as polygons. This approach seems to be the best so far though since I can probably optimize it for complicated shapes.

Another approach I've considered was to find the closest point to the center of the other shape, and test if the shape encompasses the point. Unfortunately, this runs into issues with concave polygons, and cases where the shapes are barely clipping at the edges such as this example:

*------------------------------*
|                              |
|             C                |   
|                            __+--*
*-------------------x-____-----* /
                ___---          /   
          ___-x-               /   
    ___---          C         /
_---                         /
                            /
---------------------------*

/*
C = center
* = vertex
x = point on shape that's closest to the other shape's center
*/

I feel like this problem was solved before, but my reading material doesn't cover this. How do I design a collision system where the base class does not care about specific shapes?

Answer 1

It doesn't get more general than checking Lines (possibly building curves out of sectors). The problem with just getting a bunch of lines is being able to tell if you're on the inside (no intersections).

In my previous experience with creating a collision detection system we went down the 'overloaded functions' approach.

1. Because it's easy

2. A number of shapes have short-cut maths on collision detection. (Eg: IsIntersecting(Circle, Circle) will be faster than the more general IsIntersecting(Sector, Sector))

3. It's a form of generalized collision system

Most of the shape you'll use can probably be represented as one or more circles, quads, or triangles.

Eg. a car may be 2 circles, and a couple of squares and triangles:

    ______
___/|    |\___
---()----()---

Following some other component-driven game engine examples, we made our game support multiple collision shapes per entity.

If the intersection shape is useful to you, you could make a function to return a manifold structure, which contains the points of contact for any shape:

if (IsIntersecting(Shape, Shape)) {
    Manifold = GetManifold(Shape, Shape);
    /* Use manifold for something */
}