The technique can detect the intersection point of a (fixed size, axially aligned) moving bounding box and a hull defined as a BSP tree. In this sense it is rather limited compared to newer methods but it works rather well and the implementation is pretty robust, and fast enough for the primitive hardware of the day.
Also shameless self promotion - if you're interested in 4D collision detection (and rendering, and rigid body physics), I've made a semi-tutorial-style repo here:
Nice to see you here, I’m a big fan of your videos! I did some work on Q3 mapping tools for mac back in the day and always been very interested in everything quake related.
If you want to do collision detection in something like a game and you don't want to be constantly debugging collision issues, you have to be way way more aware of numerical precision issues than this article is.
For example, even a basic "point in sphere" test can return logically inconsistent results if the point is right on the surface of the sphere and you swap the x and z coordinates.
Ignoring issues like precision can result in players falling through the world or walking through walls.
One of my favorite books is Real-Time Collision Detection[1] which covers this and other adjacent topics(like cache line aware data structures!). I generally refer to it as "data structures for 2D/3D" and I think only the Art of Electronics has more value on a page-by-page basis for the domains I've enjoyed.
I think the advice and mechanics are timeless. This is robust CS and Math stuff which stood the test of time. And this makes the book itself so valuable. I own it.
Even logic with line intersection has to be careful! I wrote some code to use line intersection tests for 2D platforming. Turns out "find a line this line collides with, move to that point, and repeat" is easy to mess up due to FP precision.
I second Real Time Collision Detection. I used its section on line segment intersection to get my code working.
Sure, you'd look for division-by-zero issues, like black holes.
Or notice that 256-bit numbers floats are used (with 237-bit mantissas), which give roughly 10^71 distinct full-precision values: about the same as the width of the universe in plank lengths.
At the edge of the universe, you'd expect the lack of precision to turn the simulation into garbage, noise, or just heat. We call that the cosmic event horizon, which is sort-of what happens when you go too far in Minecraft. The heat we call the cosmic microwave background.
Similarly, you could notice that the simulation uses fixed-precision numbers for the simulation of local fields. You would expect this to manifest as a whole range of "minimum" values below which no physical process can go. Quantums of action, as it were. We call the study of this: Quantum Mechanics.
One could also envisage the universe being simulated on clusters of computers, but then you run into issues with data transfer bandwidth between nodes -- the ones simulating lots of complicated stuff will have trouble sending their data to other nodes fast enough. So a simple fix is to slow them down so that they don't overwhelm their neighbours. This temporal distortion is what we call gravity, and its study is general relativity.
Each cluster node running the simulation exchanges its state with its neighbours at each time step. It takes two time steps for the nodes one step further than that to receive an update. Three time steps for three nodes, and so forth. This limits the speed at which all information (causality) can flow through the grid of cluster nodes. We call this the speed of light, and its study we've named special relativity.
Not only collision detection, but everything that uses floats like graphic does.
I would recommend introductions to numerics and linear algebra, which should cover everything needed (the theory and how to actually use floats in programs) but not be overly "mathematical" formulated. But as I am a mathematician (who learned that 25 years ago) I don't háve any concrete recommendations of books or videos of lectures and you would not be able to read my handwriting, as I would have problems reading what I wrote back then ;).
I ask this because I speculate that I discovered "new math". It is unlikely, because I failed math in school, but I dared to imagine 0=1 like many others. But the complete line of math I am trying to prove is -1=1=0=∞. It does sound crazy, I know. But I honestly think this line of math is what separates us from actual, working fusion. Of course, I realize how insane I sound, and that is why I am looking for ways to probe my hypothesis. I think I am getting closer, but literally every single person I talked to about this told me I should visit a psychiatrist :')
There really ought to be more resources for 3d collision detection, and in general 3d computational geometry. Existing resources usually suffer from one or more of the following:
- only 2d is considered
- edge cases are handwaved/not treated/rest-of-the-fucking-owl'ed
- edge cases are not even mentioned
- abstract mathematical operation is used, whose implementation (which isn't always obvious) is not given or described
- ok, hit or no hit... but then how to get the actual collision manifold? In which direction should the objects be separated and by how much?
- numerical accuracy is not regarded
- unnecessary muddying of the concepts by using OOP - just use (math) vectors and matrices please
Write one? Just covering 2D plus some of the edge cases (and still having issues) took 20 pages of text and examples.
Reason that most 3D collision is simply handled with approximate spheres or cubes around objects, or else floating planes. IE: Feature-based Algorithms
Advanced stuff, if you want to implement it: Simplex Based Algorithms, Image-Space Occlusion Culling Algorithms, Bounding Volume Hierarchies.
With "simplex based" do you mean algorithms that require a tetrahedralized mesh? Because tetrahedralization is yet another non-straightforward topic...
Its basically anything related to the GJK (Gilbert-Johnson-Keerthi) algorithm mentioned elsewhere in this comment thread. Pg 2 of the first PDF linked above.
"GJK was generalized to be applied to arbitrary convex point sets, not just to polyhedra. [It] operates on the Minkowski difference between the objects. Two convex objects collide if and only if their Minkowski difference contains the origin."
So far I was only familiar with the "separating plane theorem" algorithm, and GJK by name. Do you know any good sources for where to get started when coding up a minkowski difference algorithm?
I guess that's because the concepts transfer nicely from 2d to 3d. E.g. the math for circle/circle collision is basically the same as the one for sphere/sphere collision.
Not really for more complicated meshes however, which compose planar geometries to form a solid. For 2 objects A and B you could iterate all pairs of planes that they have to see if there's any overlap, and although that works out as "elegant" math, not so elegant performance. Also, it won't yield a manifold.
I generally port over collision code I wrote years ago. I kind of like it that way.
If I'm only doing 2D (and that is about all I have done) I don't really want/need a general collision framework. Code to detect rectangle collisions, circle-circle collisions, convex polygon collisions is fairly small and tight. Even the polygon collision code uses only simple linear algebra (dot products and such).
To your last point, because I own the code, I can guarantee no OOP ... I just use math.
I recently started playing around with a physics engine library and it quickly became clear to me that I had no business attempting to build my own. I thought I was "close" with my DIY attempt and then read docs like the following:
Configuring mandatory basics like "solver iterations" sent some strong signals to me that I was attempting to fight a dragon I couldn't even fully see.
The most important part of this feeling is not giving in to being intimidated. By realising there is a dragon, you’ve already made a big step! Others could fight the dragon because they made the same first step at some point, not because they are so much smarter than you.
Indeed. I've discovered with experience that one can learn surprisingly complicated things by taking one methodical step at a time and just giving it lots of time and effort. If you want to do it, go for it! Just don't expect results on day 1.
I've tried a number of times to build a physics engine for my 2D canvas library - the one thing that's defeated me every time has been the collision detection. In the end I gave up on building the whole thing and settled on just doing the particle part of the job; it's enough for my purposes without over-complexifying the library[1]. If people need collision detection for their canvas animation they can include a 3rd party library that does the job properly[2].
But it was definitely worth making the attempt - an excellent learning experience into an area of computing I never want to visit again!
Note that this book talks about static collision detection.
In games you'll be better off calculating the function of distance between the two objects over time and registering a hit if it reaches zero.
For instance, the square of distance between two circles moving at a constant speed is a parabola, so it's enough to sample it at three points in time to get its coefficients.
Kinetic triangulation problems are formulated similar to this. I've written an algorithm for a specific kind of triangulation schema [1] where collision events are sorted as quadratic inequalities. The math becomes quite involved when robustness is required and floating point representation is avoided. You have to treat the irrational time points of collision events as existing but expressed implicitly, as in a sort of unevaluated symbolic form. Kind of like imaginary numbers.
It’s a nice site and collection of techniques. However, it doesn’t fully follow through on the first page context of a resource for people new to CD in game making.
CD is expensive, so knowing when to check for it, and when to approximately check for it vs accurately check for it is very important. Filtering is going to save you many more clock cycles than most CD tuning. For example distance checking, and checking when you don’t need to check for tunnelling, and simple things like avoiding sqrt. You need to establish “good enough” CD for each use case.
I didn’t read every word so I may have glossed past those parts. I enjoyed what I did read but a chapter on the “practical” side would be a welcome addition.
A general technique that works for any convex shapes in any number of dimensions is GJK [1].
Conceptually it goes like this:
1. Consider your shapes as sets of points
2. If A and B intersect, there is some a in A and b in B such that a=b, or equivalently a - b = 0
3. Consider the Minkowski difference, A - B = { a - b : a in A, b in B }. Two shapes intersect if 0 is in A - B.
4. So answer this question.
And then to actually do this, you want A and B to be convex which importantly means you get (i) that A - B is a convex hull, and (ii) a support function which for any direction can tell you the point in the hull most in that direction. If f is the support function for A and g for B then the support function for A - B is h(x) = f(x) + g(-x).
The final problem is, given the support function for the Minkowski difference of your two sets, how do you determine if it has 0 in it? The answer in 2d is: 1. Pick a random direction and its opposite direction. If both are on the same side of the origin then you are done, otherwise you pick a vector perpendicular to the previous one which points towards the origin (or randomly if there is no such choice) giving you a triangle and three cases: the origin is in the triangle, the origin is not in the hull, or that you need to repeat. 3D is similar except you are going for tetrahedra instead of triangles. You can hopefully find some articles online with illustrations that show how this actually works.
The reason GJK was commonly used in real time usage is that you can cache the previous iterations solution to seed the next iteration which will often have the same result turning it into an O(1). Other commonly used algorithms were SAT (Separating Axis Theorem) and MPR (Minkowski Portal Refinement) although these were all popular in the 2000s and I have no idea what modern engines use nowadays.
Minimizing Minkowski difference between convex bodies can also be formalized as a quadratic program. I wonder how the GJK performs against the QP formulation.
Here is a recent and interesting paper connecting GJK and convex optimization [1]. They show that GJK is equivalent to the iterations of the Frank-Wolfe algorithm applied to the QP, and that recent improvements to Frank-Wolfe can be applied to improve GJK.
Frank-Wolfe is a somewhat less well-known (compared to simplex, interior point, etc) convex optimization algorithm with many interesting properties [2, Section 3.3].
Yeah I had a look for a good article and didn’t find anything I loved in my brief search. I think illustrations are much more useful than code, fwiw. In particular:
- for what Minkowski sums/differences are (maybe some kind of sweep animation would help)
- maybe something to describe what a convex set is / what support functions are. Phrasing them as a supremum of dot products isn’t super useful. You need some idea of some properties implied by sets being convex to follow the next part
- maybe some kind of visual demonstration for the support function of the Minkowski difference
- several illustrations of the steps of the algorithm for determining if 0 is in the set. I think these are some of the more useful and specific illustrations
The collision problem always makes me wonder if we miss something obvious. It's so hard to solve it mathematically/algorithmically specially when a lot of vertices are involved, yet give the same problem to a semi awake brain and can immediately give you the right answer.
the brain and eyes are massively parallel devices with stochastic ray tracing simulated for free.
If you can brute-force raycasts without paying the computational burden then collision is an embarrassingly parallel problem.
On the other hand, calculating collision on a computer is akin to a blind man feeling his way through a scene carefully checking against every object.
The blind man has to simulate his own raytracing with his hands, unless he can perform echolocation which once again is basically lower-resolution raytracing.
It does make me wonder though whether newer generation GPU focused on raytracing could finally bring hardware acceleration to collision?
We somewhat have this with object picking. You can render objects with unique IDs to a framebuffer, so it's all in parallel. Then you just query the buffer at your mouse coordinates.
Of course you lose some properties of the object and it's on a one frame delay. There's the added complexity of collision response, working in 3-dimensions, etc. But, to the point of just "eyeballing" collision, we can actually parallelize it!
The brain solves it by noticing where two solid polygons overlap. In that sense, you could also find the collision by rasterizing both shapes and testing whether any pixels overlap, but that's going to be slower and less precise than an algorithmic version.
With just an algebraic version of two polygons, your brain can't solve it as easily.
Actually, your "pixel overlap" method can be developed into a technique that is pretty efficient, provided we have (a) a quick way to partition any polygon into 2 roughly equal-size polygons and (b) a quick way to come up with a "covering disk" for any polygon (that is, a circle that contains the polygon, and doesn't extend too much further):
isColliding(poly P, poly Q):
if dist(P.circle.centre, Q.circle.centre) > P.circle.radius + Q.circle.radius:
return false
if P.circle.radius > THRESH:
(P1, P2) = subdivide(P)
return isColliding(P1, Q) || isColliding(P2, Q)
if Q.circle.radius > THRESH:
(Q1, Q2) = subdivide(Q)
return isColliding(P, Q1) || isColliding(P, Q2)
// Both P and Q are "small"
return detectOverlapByRasterising(P, Q)
The problém with collision detection is less that is hard to do at all (it is actually quite simple), it is that it takes too long to brute-force check all of them. The samé problém as with raytracing.
I don’t think we can generally eyeball if things will collide with the accuracy needed for a physics engine. For example, consider golfers, if they could just run the simulation they would get excited before getting a hole in one, not after.
Which can be replaced with "return distance <= r". It's always funny to me when booleans get treated like that. My big favorite is "if a == true return true else return false".
Anyhow it's probably pedantic of me. I bookmarked that, no doubt I will find its use.
I've dabbed in collision detection in the past, and here are a couple of notes:
* The square root operation is relatively expensive. Don't use it. If you're doing point-circle or circle-circle collision detection, you're better off comparing r²< a²+b² than r < sqrt(a²+b²). The same goes for 3D, obviously.
* Use a hierarchy of bounding volumes, with coarser bounding volumes calculated at runtime and determined based on the computational cost of the collision detection method. Say you have an element comprised of several sub-elements. You start with a coarse sphere that groups all elements and start by evaluating a collision based on that sphere. If you detect a collision, you re-test with finer-grained bounding volumes.
* In some applications it pays off to discretize coordinates and sizes and replace accurate floating point math with less accurate integer math. This approach can be a part of the hierarchical collision detection approach.
I did a simple game where I rolled my own physics and collision detection. It only had to deal with rectangles so the math should have been fairly simple, but I had a bit of a hard time with things like detecting which side/face was being collided with, dealing with slight overlaps, and handling all the different edge cases.
I'm sure it gets much harder with more shapes and dimensions, but also easier if you just want to detect any overlap and not "resolve" the collision physics.
I have been using bsps and quadtrees and grid spatial indexing datastructures for years in gamedev amd graphics, raytracingg etc, and I only recently discovered that quadtrees and bsp's have a failure case when the aabb's within are at harmonic intervals of the space division, or very large. You end up putting your data into basically every single child node. With only a few objects I ran out of 32gb of ram. 4^n.
I changed it to an rtree and the problem went away.
> Ellipses, which seem like they should be pretty easy, are actually very difficult.
Been there, felt that.
Surprisingly this came up several times in my career in different contexts. Iirc there is one relatively good heuristic and several iterative methods to calculate point to ellipse distance (and therefore collisions).
A nice article. It would be cool to go a little bit deeper to finding the collision points and depths, though. These are very useful for the next phase, which is typically reacting to detected collisions, e.g. by applying some impulse to the objects involved.
I taught myself collision detection and resolution and then collision avoidance. It was like sticking my brain in ice cold water and then in hot water. I arrived back where I started but completely disturbed.
https://www.youtube.com/watch?v=wLHXn8IlAiA
The technique can detect the intersection point of a (fixed size, axially aligned) moving bounding box and a hull defined as a BSP tree. In this sense it is rather limited compared to newer methods but it works rather well and the implementation is pretty robust, and fast enough for the primitive hardware of the day.