Home

Saperating Axis Theorem collision detection preformance analysis

Introduction

The separating axis theorem is a theorem that can be used for real time collision detection. In the first half of this wiki entrance I am going to explain the theorem and the calculations for 2D collision detection and in the second part I am going to discuss performance of the implementation.

This prototype was build in unity. Unity is being used to visualize the objects that are being tested for collision.

Evaluation Proposal: Analysis of performance of a custum 2D SAT collision detection system in unity using trees for optimization.

Relevance: Realtime collision detection is essential for video games. Especially when alot of (moving) objects are being tested performance needs to be improved.

https://pdfs.semanticscholar.org/cd43/df36650f1e558db89a0ffd41c620709757b3.pdf

Seperating Axis Theorem

The Separating Axis Theorem (SAT) states that if you can draw a line between two convex polygons they are not colliding.

Convex Shapes

All line segments formed from points of a convex polygon are fully contained within the polygon.

https://mathworld.wolfram.com/ConvexPolygon.html

In the Image above you can see visualized how two cubes can or cannot be separated by an axis. To check whether or not a separating axis exists we project the two polygons on all the polygons axes normals and check if the projected polygons overlap. In the Image below you can see the visualisation of the projection for one of the axes.

The algorithm needs to check multiple axes to determine that the shapes overlap, however if one of the projections does not overlap, a separating axis is found and the calculation can be stop and continue with the next operation.

To determine which axes we need to project the polygons onto we can just take the normals for each of the Polygons axes.

We need to project the polygons on each axis:

//returns the info if the two colliders are overlapping
private CollisionInfo SATIntersection(Collider a, Collider b)
{
        CollisionInfo info = new CollisionInfo();
        foreach (Axis currentAxis in a.Axes)
        {
            Vector2 axis = currentAxis.AxisNormal;
            //returns the minimum and maximum Dot product between the axis and all the Vertices
            Tuple<float, float> minMaxA = ProjectShape.Project(axis, a.Info.vertices);
            Tuple<float, float> minMaxB = ProjectShape.Project(axis, b.Info.vertices);
            //checks if the projections overlap
            if (!ProjectShape.Overlap(minMaxA, minMaxB))
            {
                //stop collision detection if no Overlap was calculated
                info.hit = false;
                return info;
            }
        }
        //repeat for Axes of other Collider
        foreach (Axis currentAxis in b.Axes)
        {}
        //if this point is reached no seperating axis was found --> the two colliders overlap
        info.hit=true;
        return info;   
}

This "pseudo" code is the core of what you need to do to determine whether or not two polygons collide.

Performance

Brute Force

The most basic / brute force approach to iterate over all objects that are to be tested for collision is a double for loop:

  for (int i = 0; i < _SATColliders.Count; i++)
        {
            for (int j = i; j < _SATColliders.Count; j++)
            {
              // Call collision detection with both colliders
           }
        }

The amount of checks we have to do for this approach is O(n(n-1)/2).

On my machine with 180 colliders I dropped below 60 average frames per second and reached the brute forces limits at 190 colliders with 27 average fps

The framerate for the first ~100 Colliders does not really vary, but as you can see in the graph if you the framerate drops verry quickly after reaching ~150 colliders. If we want to have a scene with alot of colliders we should concider improving this brute force approach.

Grid Based Subdivision

A solution to this is to introduce the broad phase of collision detection. This means subdividing the the collision objects in a way that reduces the amount of collision checks.

The most simple broad phase subdivision is to seperate the colliders into a grid based on their position (polygons can be in multiple grid cells if they are positioned closely to a cell border). Instead of checking for intersection with all colliders for all other colliders we only need to calculate the intersection for all colliders with all other colliders within each grid cell.

This can highly improve the collision detection performance if the grid cell size is tweaked appropriately.

In my example I created a 50x30 Grid with a cellsize of 10x10.

With this improvement with the same amount of colliders (190) which made the brut force approach reach its limits there is still no significant loss in performance.

This improved version can handle up to 340 colliders on the 1500(50x30) unit area.

Grid Size

For my last test I increased the grid area size to 50 by 50 units, set amount of colliders to 350 and measured the framerate based on the cell size.

As you can see in the graph above setting the grid size to 1 results in a big hit in performance. The colliders are too big for such a fine grid which results in alot of overlaps and a more complex computation for the individual grid position. The optimal cell size seems to be somewhere between 4 and 5.