I'm writing a simple physics engine in 2D. My first goal is to get collision detection working. I know that my objects will eventually be made up of primitive shapes, but I was wondering - would a collision detection library be composed of a bunch of special case functions, like "rayAndLine", "rectangleRectangle", "rectangleCircle" etc, or is there a common, underlying framework for collision detection that works regardless of which primitives are used to make the shape?
Getting collision detection working is a great first goal for your 2D physics engine. It's good that you've decided that for now you're specifically working in 2D, as not every rule in 2D works in 3D, despite the amount of n-dimension related algorithms, at some point you have to specialize them (do a more specific variant like how cross product only satisfies the Jacobi identity in 3D).
Your question is inherently about architecture and framework design not about 2D physics, so the concern of what your building should be separate in your mind for how those pieces are used. Essentially, you need to separate the mentality of building the engine/library/framework from it's usage in another project.
Architecting solving engines: With any mathematics engine, we essentially want to put values into some function, and we expect the values that come out to be useful for making an interesting simulation.
The core elements of this process should be as abstract as possible while the atomic elements (smallest useful pieces of data/methods) should be specific to individual purposes and be useful to compose together. In our case nearly the only useful atomic is a 2D vector, which should be a single class of object which allows expression of an (x,y) structure, and has methods for all basic math operations that are useful for vector computations in 2D. Addition, subtraction, normalization, normal (perpendicular), cross product, dot product, magnitude/length, and whatever else you encounter that is specifically inherent to vector -> vector operations or vector -> real number operations. If you're using a class based language, a simple
class Vector with each of these as a member function or operator overload would do very well.
After all atomic types are constructed, then you would compose their algorithms into another layer on top of our atomic type
Vector. My go to's would be a
Line and a
Curve. We'll decide here that a
Curve is out of scope for this and requires much specialization (the concept you refer to above as creating many special case functions). From
Vector I would also compose a
Rectangle as a 4
Vector primitive, compose
Circle from vector using a
Vector and a
radius, and then I would compose a
Vector as well.
Polygon should be made from
Vector and not
Line here because each line would share a duplicate point with the last line in the polygon.
Now you have shapes, but we don't know what to do with them.
Collision Detection Collision detection is not an exact science and there's not one single perfect algorithm (or any). There's many methods which can be used to achieve a variety of quality of effects or even have more accuracy than others. Basically though, it can be separated into a few different levels of concern and thus a few different processes.
Broad phase collision detection is the act of sectioning areas where we care about what might/could/does collide, and separate them for the narrow phase process. In 2D I would typically recommend using a quad tree for this. For that we'll need our
Rectangle we built earlier and to provide it with a AABB collision detection. This stands for Axis Aligned Bounding Box and we'll use it to determin that for a non-rotating box
A that no part of box
B exists within
A. It follows from the assumption that no part of
B can exist within
A that a collision exists if they do intersect.
A quad tree is a recursive process where you determine a maximum depth, or allow your object quantity to prevent infinite recursion depth instead. It groups physics bodies into 4 regions (hence the name) and should allow you to access each quad separately. You then would enter into each of those four quads, and perform the same process which I won't outline here for brevity but is available here: https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374
Narrow phase collision is the process of going through your groups of shapes that we've already determined will/might/do collide and performing a more discrete collision check, at this point in time, we begin caring whether the objects are rotating or not (I won't cover this, when you get passed these collision phases look into detecting collision with angular momentum) and what shape their collision body actually is. To perform this part of the collision you would specialize your methods as you have described above (making specific functions for AABBvsCircle, OBBvsCircle, CirclevsCircle, PolygonvsPoint, PolygonvsCircle, PointvsCircle, etc.) However, these methods themselves can also be done in a layered manner as above. The key is to know what complexity of operations that you need at a given time to decide if you can use the most general form like the Separating Axis Theorem would be a great place to start for your narrow phase detection.
Your primitive separation checks are the discrete, specialized collision detection methods or general ones like SAT depending on use case and should all simply return either a true/false value, or return a relational object such as a
CollisionObject etc. which would have a connection with the two shapes found to be colliding, and any information about them necessary for resolving the collision, like how deep they're colliding or at what speed (what data you need in your manifold depends on what resolution method you use). That object you then pass to a
Solver which should abstract away the differences between all of the different shapes that could collide, by only accepting a
Manifold and not accepting any particular information about the shapes.
Solver will take the
Manifold produced by colliding some primitive
A with some primitive
B, using first broad phase grouping (all vs world) and then narrow phase detection (A vs B) and if shapes are non-polygon must be specialized, the
Solver then produces either new
Vectors for the collided shapes positions and velocities, or an object which the
World can then use to resolve collision on it's children, then finally update the
QuadTree and repeat this process on the next frame. If both colliding shapes are polygons then specialization should only be done with concerns to increased performance, otherwise simply using Separating Axis Theorem