Collision Engine in C++ (outline)

Collision Engines

1. Step based overlap detection.
1. (+)Simple
2. (+++)Sort and Sweep is a very powerful optimization
3. Compute a step forward
4. (-)Things that move too fast can jump over things
2. Full Prediction
1. (++)Not step based
2. Moderate complexity 
3. (++)Not possible to jump past other things
4. (+)Very fast with just a few objects
5. (--)Very slow with lots of objects.
6. (---)Only motion that can be "solved" are allowed. (linear)
3. Hybrid Engine
1. (-)Step based
2. The swept volume of the object's motion that step is used for overlap sort and sweep.
3. Objects with overlapping swept volumes are collected and given to a predictive engine for that step.
4. (++)Things don't get jumped over.
5. (+)Multiple collision within a step (rattle)
6. What do overlapping regions look like in a dense gas simulation?
7. (-)Motion within a step is limited to "solvable" motions (linear)

The Basics

Body

The top level objects that participate in the collision engine are called "Bodies".  A Body is is made up of one or more "Fixtures" and is either Static, Dynamic, or Kinematic.

1. Body Types:
• Static: The body is immovable.
• Dynamic: The body moves, bounces, and falls in gravity.
• Kinematic: The body moves but does not bounce or fall in gravity.
2. Dynamic Body limitations:
• Because the simulation doesn't handle rotations, dynamic bodies can only be made of either a single circular fixture or multiple circular fixtures with the same center point.
3. Static Body limitations:
• Static bodies can be made up of any number of any kind of fixture.
4. Kinematic Body limitations:
• A kinematic Body can be made of any number of any kind of fixture.  But it cannot rotate.  (kinematic bodies are currently not implemented)
5. AABB: the Axis Aligned Bounding Box of the Body is computed by union of the Fixture AABBs.

Fixture

A Fixture has a Geometry (circle, point, line, etc..), and a "Fixture Definition" that contains: Density, Collision Restitution,  and Physical vs. Sensor status.

1. Fixture Type:
• Physical Fixtures physically impact with other physical Fixtures.
• Sensor Fixtures is sent a notification when a physical fixtures overlaps it.  The physical fixture is not notified.   Nothing happens when two sensor fixtures overlap.
  Sensor Fixtures can be used for "traps", "Sight regions", and cross region doorways.
2. AABB: Axis Aligned Bounding Box.

Geometry

The geometries current available are: Point, Circle, Line Segment, and Poly Line.

1. Point is just a position.
2. Circle is a position and a radius.
3. Line Segment: Only the line segment itself is collided against the end points are not included as "corners" (see Poly Line below).  The Line Segment is represented as both
• Two endpoints
• A unit normal and the distance from the origin to the line in the normal direction.
4. Poly Line is a collection of lines connected by points (corners).   Both the line segments are the corners (and end points) are included in the collision detection.

Colliders

To work out collision we need to take geometries and motions and predict forward when, or if, they will intersect.   This is necessary even for a simple step-wise overlap detect engine.   You notice that next step (frame) two object that were not overlapping will be overlapping. So you then need to work out exactly where and when they first touch so the collision and "bounce" can be computed.

Collision Detection: Overview of the Basic Approach

Overview of the Basic Approach

I have two approaches to collision detection, each has its advantages and disadvantages.  When used used in combination the result is quite effective.

Approach #1. Step and Check

"Step and Check" breaks the simulation into steps of time, usually matching the "display frames" of the simulation, or an integer multiple of the "frame rate".  The simulation loop advances all moving object one frame, then check if any objects overlap.  If object overlaps then it computes the appropriate response.  The response is usually a "bounce" but it could be any number of things.  [see: collision response]

In the simplest form, you check every moving object against every other object in the simulation, every frame.

// Do not use this code.  This is just the simple general idea.
// mob == Moving Object

DoOneFrame()

{

    foreach(mob in mobList)

        AdvanceOneFrame(mob)

    foreach(obj in allObjList)

    {

        foreach(obj2 in allObjList)
        {
            // don't compare against itself
            // don't compare two fixed objects.

            if(obj != obj2 && (obj1->isMob() || obj2->isMob))

                if(IsOverlapping(obj1, obj2)

                    Respond(obj1, obj2);
        }

    }

}

Sort and Sweep

"Sort and Sweep" is an optimization to "Step and Check" where all the objects are sorted on one coordinate axis.  Then rather than a full N squared compare, the simulation sweeps through the sorted list only comparing objects adjacent and overlapping on the sorted list.
This is a huge reduction on "big O" complexity of the simulation and becomes the center point of the design.

DoOneFrame()

{

    foreach(mob in mobList)

        AdvanceOneFrame(mob)

    sortedList = SortMobs(allObjList);

    for(int i=0; i<sortedList.size(); i++)

    {

        obj1 = sortedList[i];

        for(int n=i+1; n<sortedList.size(); n++)

        {

            obj2 = sortedList[n];

            if(!OverlapsOnSortAxis(obj1, obj2))

                break;

            // don't check two fixed objects.

            if(obj1.isMob() || obj2.isMob())

            {

                if(IsOverlapping(obj, obj)

                    Respond(obj1, obj2);

            }

        }

    }

Pros:

• Easy to implement.
• Works with any sort of motion.
• The Sort-and-sweep optimization is very powerful.

Cons:

• Fast moving objects can "jump" past walls or each other.
• Doesn't handle multiple objects colliding within a single step.
• Doesn't handle object "rattle", i.e. multiple collisions inside of a single step.

Approach #2. Predictive Collision Queue

With "Predictive Collision Detection", the simulation projects the moving objects forward solving for their intersections in the future.  All future collisions are  sorted by time into a queue.  The top item is the next collision in simulation.
The "frame rate" of the application is outside of the collision detection.  There is no "per frame" collision engine work, as there is in "Step and Check".  Several collisions for a single objects can be processed between two consecutive frames.  If the next collision is predicted to be many "frames" away, the objects can moved through those frames with no collision engine work at all.

When the time of the next collision arrives the collision object is popped off the queue. and processed.  If the motion of the object(s) is changed by the collisions, all queued future predictions for the object are removed from the queue. The moving objects involved in then collisions compared against all the other objects in the simulation for all future collisions and the new collisions are sorted into the queue.

Pros:

• Very exact, not dependent on frame rate.  Yielding a better simulation.
• Can be very efficient if there are few collisions.

Cons:

• Predicting the collision require solving for the intersection of the object's predicted path.  This only works for motion that can be describing the motion with analytic function: straight lines, parabolas, etc.  
• A colliding object must be compared against every other object every time its motion changes.  This can be very expensive where there are lots of collisions and lots of objects.
• Sort and Sweep optimization cannot be applied if we predict arbitrarily far out because the bounding box of future path can be very large.

Synthesis #1 + #2

Plug the two approaches together.   Project the motion of all the objects forward one frame.  Instead of moving the objects forward we compute a path for each from last frame's position to this frame's position, and a Bounding Box of the complete path of the object in the inter-frame time period.
The objects of the "sort and sweep" collision detection are these bounding boxes of each object's motion.
When bounding boxes are found to overlap in the sort and sweep phase, their objects are put in a "Predictive Collision Queue" to do a full predictive analysis for the interaction, but only extent of the inter-frame time period.
We still have the restriction that the motion (path) of the object must be an analytic function (ie. line, parabola, etc.) but this approximation is only applied one frame at a time.  The endpoints of the per-frame motion are controlled by the object and over-all game simulation.  It is only the path between the frames, between those points, that is mathematically simplified.

Collision Detection: Minimum Goals

Introduction

When writing a Real Time Strategy game, or a Creature Simulation there is a need for a system to efficiently detect when items are near or touching each other.  This would be a minimal Collision Engine.

Goals

The minimum useful interesting Collision Engine would be:

• 2 dimensional.
• All moving objects are represented with circular bounding containers
• All fixed objects are represented as either circular, line segments, points (very small circles) or collections of these.
• Collision objects can be physical boundaries (actual collisions) or notification boundaries (like doorways or line of sight limits)
• Minimum of "physical" simulation: objects have mass, surfaces have restitution(*), but no friction, and no rotational momentum, or spinning.

(*) Restitution or "Coefficient of Restitution" is the "bounciness" of the surface.  See Wikipedia.

[...]
Old age hath yet his honour and his toil;
Death closes all: but something ere the end,
Some work of noble note, may yet be done,
Not unbecoming men that strove with Gods.
The lights begin to twinkle from the rocks:
The long day wanes: the slow moon climbs: the deep
Moans round with many voices. Come, my friends,
'Tis not too late to seek a newer world.
Push off, and sitting well in order smite
The sounding furrows; for my purpose holds
To sail beyond the sunset, and the baths
Of all the western stars, until I die.
It may be that the gulfs will wash us down:
It may be we shall touch the Happy Isles,
And see the great Achilles, whom we knew.
Tho' much is taken, much abides; and tho'
We are not now that strength which in old days
Moved earth and heaven, that which we are, we are;
One equal temper of heroic hearts,
Made weak by time and fate, but strong in will
To strive, to seek, to find, and not to yield.

Ulysses

by Alfred Lord Tennyson