8
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ You ask about an underlying framework, but specifically state that you'd like to build this portion on your own. Can you clear up that last sentence where your actual question takes place, in order to more specifically separate your concern regarding building it yourself, from using someone else's framework that they've built. I'll provide an answer as well. \$\endgroup\$ – Joshua Hedges Oct 17 '17 at 13:50
  • \$\begingroup\$ Fair point. I meant underlying theory from which all of collision detection stems. In other words, if I'm writing a collision detection subsystem, do I need to write one function for each type of primitive/primitive collision, or is there a single generic function that works no matter what the primitive is? \$\endgroup\$ – Michael Stachowsky Oct 17 '17 at 13:58
  • \$\begingroup\$ Sort of. I just answered it. There are some that generalize solutions really well, like SAT works for any convex polygon, and any concave polygon can be broken down into convex polygons, which makes it work for any polygon with some work. After that you'd have to specialize against curves, spheres, and ovals. I've outlined it below. It's a big topic to cover so it's long. Let me know if you have any questions on specifics or anything else \$\endgroup\$ – Joshua Hedges Oct 17 '17 at 15:00
  • 2
    \$\begingroup\$ This previous question on abstracting different shape types might also be useful. \$\endgroup\$ – DMGregory Oct 17 '17 at 15:53
  • 1
    \$\begingroup\$ The more shared code, the better. If you ever find yourself using copy and paste, seriously check yourself! \$\endgroup\$ – corsiKa Oct 17 '17 at 19:34
9
\$\begingroup\$

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 Polygon from 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 Manifold, Joint, 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.

Summary The 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 PhysicsEnvironment or 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

\$\endgroup\$
  • 1
    \$\begingroup\$ Great answer, thanks. I'm curious, though: I had originally considered basing my most primitive object on the point, then building a vector from there. I see from your answer that this wasn't necessarily the best choice. Why is that? \$\endgroup\$ – Michael Stachowsky Oct 17 '17 at 15:34
  • 1
    \$\begingroup\$ The reason for that is because in 2 dimensions a vector and a point actually have the same definition. a Vector direction,Magnitude can be taken as a Point x,y if you simply ignore some of the operations the Vector provides. The best part about doing this, is just because you can ignore those operations now, when you want to determine things like angular momentum you're not changing object types. It's almost a matter of taste then, because what game developers call a "Point" mathematicians do indeed call a "Vector". So call it what you want, the important thing is what it offers. \$\endgroup\$ – Joshua Hedges Oct 17 '17 at 15:45
  • 1
    \$\begingroup\$ In a C style language, if I wanted to use the "Point" definition for readability in fact I would simply typedef it from a Vector, or alias the term "Point" to mean the same thing as "Vector". \$\endgroup\$ – Joshua Hedges Oct 17 '17 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.