This is a collision detection toolkit written in C#.
It provides geometry primitives for Circles, Rectangles, Triangles, and Line Segments, as well as a QuadTree structure for spatial partitioning.
Each of these primitives implements a standardized interface allowing them to be placed in the QuadTree for broad-phase quick culling.
These primitives also have a complete set of pairwise collision detection methods. That is to say this library can determine if any two given primitives are intersecting, regardless of which of the primitives are provided.
Setup this registry from the command line:
dotnet nuget add source --name LongHorse https://gitea.longhorse.studio/api/packages/LongHorse/nuget/index.json
To install the package using NuGet, run the following command:
dotnet add package --source LongHorse --version <VERSION> LongHorse.CollisionLib2D
The root of the repository contains the project solution, this readme, and git/gitlab configuration files.
The CollisionLib2D folder contains all source code, and the XunitTests folder contains some unit tests to validate basic functionality.
IBoundingArea is the common interface for all our shape primitives. This allows us to manage lists of mixed types while being able to query for basic information like global X and Y boundaries, and the ability to translate the objects global coordinates. There is also a BoundingType enum which allows us to down-cast to the underlying primitive to access more concrete geometrical properties.
X and Y boundaries (Top, Bottom, Left, Right) are read-only on the interface. Methods to resize shapes are left to the concrete implementation.
The rectangle class is the implementation of IBoundingArea that is most true to the interface.
The intersecting spaces between IBoundingArea and Rectangle are identical.
There are methods to allow you to move the Left, Top, Right, and Bottom of the shape to a position without changing the dimensions of the shape.
public Rectangle unitSquare = new Rectangle()
{
Size = new Vector2(1.0f, 1.0f),
Center = new Vector2(0.0f, 0.0f)
};The circle is the simplest implementation of IBoundingArea, with a Center and a Radius.
public Circle unitCircle = new Circle()
{
Radius = 0.5f,
Center = new Vector2(0.0f, 0.0f)
};Internally, the triangle is represented by three connected points.
The Top, Left, Right, and Bottom are the minimum and maximum X and Y values of the three points, creating a bounding square around the shape.
The center is the triangle Centroid, calculated on every access. Because of this, reducing unneeded calls to the Center property will help performance.
public Triangle triangle = new Triangle()
{
Points = new Vector2[]
{
new Vector2(-0.25f, 0.0f),
new Vector2(0.25f, 0.0f),
new Vector2(0.0f, 0.25f)
}
};Similar to the triangle, the LineSegment is represented by an array of points.
The center is the midpoint of the line, and is also calculated on each access.
public LineSegment line = new LineSegment(
new Vector2(-1.0f, -1.0f),
new Vector2(1.0f, 1.0f));For each of the IBoundingArea implementations, the NearestPoint method will determine the point within the given shape that is closest to the input vector. Each shape uses a different algorithm, most of them taken from [1]
public void Circle_Nearest_Point()
{
Circle unitCircle = new Circle()
{
Radius = 0.5f,
Center = new Vector2(0.0f, 0.0f)
};
//the center of the circle is the nearest point to itself
var p = new Vector2(0.0f, 0.0f);
var nearestPoint = p.NearestPoint(unitCircle);
var distance = nearestPoint.Length();
Assert.Equal(0.0f, distance);
//the edge of the circle is the nearest point to itself
p = new Vector2(0.5f, 0.0f);
nearestPoint = p.NearestPoint(unitCircle);
distance = nearestPoint.Length();
Assert.Equal(0.5f, distance);
//the edge of the circle is the nearest point
p = new Vector2(2.0f, 0.0f);
nearestPoint = p.NearestPoint(unitCircle);
distance = nearestPoint.Length();
Assert.Equal(0.5f, distance);
//any point outside of the circle should have a nearest point distance of 0.5
//but floating point precision kicks in when we dont choose nice even numbers along the axis
p = new Vector2(2.0f, 2.0f);
nearestPoint = p.NearestPoint(unitCircle);
distance = nearestPoint.Length();
Assert.True(distance - 0.5f < 0.00001);
}For each of the 16 primitive shape pairings, one of 10 distinct algorithms can be invoked to determine if the two primitives intersect.
public void Rect_Circle_Collision(IBoundingArea b, bool intersectionExpected)
{
Rectangle unitRectangle = new Rectangle()
{
Size = new Vector2(1.0f, 1.0f),
Center = new Vector2(0.0f, 0.0f)
};
Circle unitCircle = new Circle()
{
Radius = 0.5f,
Center = new Vector2(0.0f, 0.0f)
};
Assert.True(unitRectangle.Intersects(unitCircle));
}Basic QuadTree usage involves creating a new QuadTree and filling its space with IBoundingArea implementations.
Once the tree contains the objects we wish to query, we can call FindObjects() to search a local area for IBoundingArea neighbors in the vicinity of the search object.
//create a 500x500 quadTree
var treeSizeX = 500;
var treeSizeY = 500;
var quadTree = new QuadTree(treeSizeX, treeSizeY);
//add 50 random 1x1 rectangles to the structure.
Random rnd = new Random();
for (var i = 0; i < 50; i++)
{
//Size.X and Size.Y are width and height of the rectangle.
//randomly position the center of the rectangle.
var rect = new Rectangle() { Size = new Vector2(1.0f, 1.0f), Center = new Vector2(rnd.Next(0,500), rnd.Next(0,500)) };
quadTree.Insert(rect);
}
//search a random 10x10 area to determine which rectangles are 'in the neighborhood' of the search area.
//Note they may not necessarily overlap the rectangle.
//They are simply close enough that the QuadTree flags them as overlapping candidates.
var searchRect = new Rectangle() { Size = new Vector2(10.0f, 10.0f), Center = new Vector2(rnd.Next(0,500), rnd.Next(0,500))};
var neighbors = quadTree.FindObjects(searchRect);A QuadTree does not tell us with certainty if items overlap, only which are nearest the search area.
To find which items in the neighbors set overlap, we can iterate over them in a second pass and see which intersect.
//make a list to store items that are actually colliding
List<IBoundingArea> collisions = new List<IBoundingArea>();
//populate the list from the neighbor candidates
foreach (var candidate in neighbors)
{
//various definitions for Intersects() are defined for circle/circle, rect/rect, rect/circle, and circle/rect.
if(searchRect.Intersects(candidate))
{
collisions.Add(candidate);
}
}Portions of the QuadTree implementation were taken and modified directly from the Auios project.