Collision Detection (2015)

https://www.jeffreythompson.org/collision-detection/index.php

by todsacerdoti • 3 years ago

233 79 3 years ago

aappleby2• 3 years ago

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.

vvanders• 3 years ago

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.

[1] https://realtimecollisiondetection.net/books/rtcd/

OnionBlender• 3 years ago

I'm surprised there was never a 2nd edition in the past 20 years.

lebaux3• 3 years ago

Nice, I literally just asked the OP to provide a link! Thank you!

samlittlewood• 3 years ago

NB: there is a planned 2nd edition without the involvement and against the wishes of the author :(

https://x.com/christerericson/status/1050488747010060288?s=4...

djmips• 3 years ago

This is a damn good book. I always recommend it to colleagues.

dannyfritz07• 3 years ago

https://www.realtimerendering.com/intersections.html

lebaux3• 3 years ago

This is super interesting, what further reading would you recommend for a complete beginner in collision detection? Thank you.

ReleaseCandidat3• 3 years ago

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 ;).

_the_inflator2• 3 years ago

Speedrunners will not appreciate it. ;)

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.

eggdaft• 3 years ago

If the simulation hypothesis of reality is correct, does this mean we might encounter such edge cases in physics? Where should we look?

jiggawatts• 3 years ago

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.

whateveracct• 3 years ago

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.

whatever1• 3 years ago

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.

xeonmc• 3 years ago

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?

guitarlimeo• 3 years ago

This is a nice analogy, never thought of it that way but it makes sense!

battesonb• 3 years ago

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!

ReleaseCandidat3• 3 years ago

could finally bring hardware acceleration to collision

Physx has collision detection.

hypercube33• 3 years ago

Is it possible to use ray tracer hardware to say raytrace polygone vertices and use that for fast collision?

raincole• 3 years ago

No? It's just one of the thousands of tasks that biological brains are envolved to do well.

ReleaseCandidat3• 3 years ago

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.

Jasper_• 3 years ago

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.

akoboldfrying• 3 years ago

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)

bee_rider• 3 years ago

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.

dang• 3 years ago

Collision Detection (2015) - https://news.ycombinator.com/item?id=24735824 - Oct 2020 (33 comments)

bob1029• 3 years ago

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:

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.

9dev• 3 years ago

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.

kqr• 3 years ago

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.

rikroots• 3 years ago

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!

[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...

elwell• 3 years ago

Here is my very basic collision detection in ClojureScript: https://github.com/celwell/wordsmith/blob/master/src/cljs/wo...

kipi2• 3 years ago

Shameless self promotion, but if you're interested in how collision detection was done in 3D (in Quake) I made a video on the topic here:

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.

abrarsami• 3 years ago

Thank you for this

mcyc• 3 years ago

Your videos are absolutely fantastic, thanks for making them!

drdator• 3 years ago

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.

beaumayns2• 3 years ago

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:

https://github.com/beaumayns/box4d

Not nearly as polished as your video, but hopefully someone finds it interesting.

bfors• 3 years ago

Amazing. How did you create the animation of the quake level getting broken down into BSP nodes?

kipi2• 3 years ago

Thanks. I made it in Blender, with a Python script for loading the Quake level and setting up the Blender scene

Tade0• 3 years ago

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.

arketyp• 3 years ago

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.

[1] https://github.com/mpihlstrom/femton

yzydserd• 3 years ago

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.

nnevatie• 3 years ago

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.

punnerud• 3 years ago

If you want to optimize this you probably want to calculate the biggest distance from a center point to the edge of a complex object.

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.

bruce3434344• 3 years ago

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

fho3• 3 years ago

only 2d is considered

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.

bruce3434344• 3 years ago

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.

araes2• 3 years ago

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.

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

bruce3434344• 3 years ago

With "simplex based" do you mean algorithms that require a tetrahedralized mesh? Because tetrahedralization is yet another non-straightforward topic...

JKCalhoun• 3 years ago

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.

weaksauce• 3 years ago

real time collision detection is a good book on those fundamentals with real world considerations.

fho3• 3 years ago

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).

jjgreen• 3 years ago

Look at the Perram-Werthiem contact function

dan-robertson2• 3 years ago

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.

[1] https://en.m.wikipedia.org/wiki/Gilbert–Johnson–Keerthi_dist...

markisus• 3 years ago

Minimizing Minkowski difference between convex bodies can also be formalized as a quadratic program. I wonder how the GJK performs against the QP formulation.

lqr• 3 years ago

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].

[1] https://roboticsproceedings.org/rss18/p039.html

[2] https://arxiv.org/abs/1405.4980

jagged-chisel• 3 years ago

It’s nice that you understand this. But the explanation is too abstract. Need code to accompany the wiki illustration.

dan-robertson2• 3 years ago

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

plopz• 3 years ago

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.

foofie• 3 years ago

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.

upmostly• 3 years ago

I'm building a Web and iOS game (https://brawlbugs.com) as a side project and started implementing collision detection from scratch.

Terrible idea. Use a library like this if you're in the JavaScript ecosystem:

https://www.npmjs.com/package/detect-collisions

wegfawefgawefg2• 2 years ago

Good idea for education though. Quadtrees and rtrees are simple enough you can roll your own in a couple hours and get your nlogn query performance.

nickpow43• 3 years ago

Very cool, If it isn't mentioned elsewhere I'd add a note that often times you can avoid the expensive sqrt calculation. For example the last if statement in https://www.jeffreythompson.org/collision-detection/circle-r...

could be optimized by instead just checking if distanceSqr < (radius * radius)

besttof• 3 years ago

I always appreciated Metanet’s collision detection and response tutorial (2011) for its practicality and thoroughness.

http://www.metanetsoftware.com/technique/tutorialA.html

slowhadoken• 3 years ago

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.

wegfawefgawefg2• 3 years ago

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.

naet• 3 years ago

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.

charles_f• 3 years ago

This seems interesting.

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.

big_paps• 2 years ago

While collision detection is quite straightforward its collision resolution which always leaves stopping me attempts

Collision Detection (2015)

Related Stories