Collision Detection (2015)
jeffreythompson.org
jeffreythompson.org
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.
https://github.com/beaumayns/box4d
Not nearly as polished as your video, but hopefully someone finds it interesting.
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.
https://x.com/christerericson/status/1050488747010060288?s=4...
Also, in my experience, right from the beginning you should be aware of performance issues and should be familiar with a quad tree.
I build shooters for Android mobile in 2016 and heavy action and lots of screen fun was impossible without quad trees.
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.
You can't physically get there, it's always the same distance from where you are (though it's shrinking over time they say)
I second Real Time Collision Detection. I used its section on line segment intersection to get my code working.
- 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
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.
(tbh it's been 20 years since I did that by hand ... but I would assume that the underlying math has not changed since then)
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.
Collision Detection: A Survey, S. Kockara et al, 2007 IEEE International Conference on Systems, Man and Cybernetics. https://d1wqtxts1xzle7.cloudfront.net/50445336/Collision_det...
3D Collision Detection: A Survey, P. Jimenez et al, Institute de Robotica, 2001, https://digital.csic.es/bitstream/10261/30526/1/doc1.pdf
"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."
Link is Access Denied btw, but sci-hub works.
Consider also the minkowski portal refinement algorithm: http://xenocollide.snethen.com/mpr2d.html . Similar idea, but I find it more intuitive.
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.
https://github.com/bepu/bepuphysics2/blob/master/Documentati...
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.
But it was definitely worth making the attempt - an excellent learning experience into an area of computing I never want to visit again!
[1] - Some examples:
A particle emitter - https://scrawl-v8.rikweb.org.uk/demo/particles-003.html
Emulate a flag with a net of particles - https://scrawl-v8.rikweb.org.uk/demo/particles-008.html
Position things using particles - https://scrawl-v8.rikweb.org.uk/demo/particles-012.html
[2] - My favourite JS physics library is MatterJS - https://brm.io/matter-js/ . I want to like Rapier, which is coded in Rust and can be imported into the browser via WASM, but I haven't had the time to properly play with it - https://rapier.rs/docs/user_guides/javascript/getting_starte...
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.
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.
could be optimized by instead just checking if distanceSqr < (radius * radius)
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.
[1] https://en.m.wikipedia.org/wiki/Gilbert–Johnson–Keerthi_dist...
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].
- 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
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?
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!
Reading a texture from the GPU can take more than one frame.
Physx has collision detection.
With just an algebraic version of two polygons, your brain can't solve it as easily.
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)Probably more my problem than the author's, but I get triggered by that:
> boolean pointPoint(float x1, float y1, float x2, float y2) { > if (x1 == x2 && y1 == y2) { > return true; > } > return false; >}
And
> if (distance <= r) { > return true; > } > return false;
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.
* 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'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 changed it to an rtree and the problem went away.
Terrible idea. Use a library like this if you're in the JavaScript ecosystem:
Then include these values into a database with index, so it’s super fast to check if you need to run the formulas or not.
Often have to do this if you want to calculate if some objects is colliding/intersecting on the surface of the earth.
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).
Collision Detection (2015) - https://news.ycombinator.com/item?id=24735824 - Oct 2020 (33 comments)