Collision Detection (2015)(jeffreythompson.org)

233 pointsby todsacerdoti2 anni fa81 comments

Collision Detection (2015)

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

86 comments

kipi2 anni fa

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.

beaumayns2 anni fa

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.

[deleted]2 anni fa

drdator2 anni fa

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.

bfors2 anni fa

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

kipi2 anni fa

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

mcyc2 anni fa

Your videos are absolutely fantastic, thanks for making them!

abrarsami2 anni fa

Thank you for this

aappleby2 anni fa

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.

vvanders2 anni fa

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/

samlittlewood2 anni fa

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

dannyfritz072 anni fa

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

OnionBlender2 anni fa

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

_the_inflator2 anni fa

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.

bananaboy2 anni fa

Note that there may be a 2nd edition coming but any release is against Christer Ericson's wishes and he's not involved: https://twitter.com/ChristerEricson/status/10504887470100602...

lebaux2 anni fa

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

aappleby2 anni fa

Yep that's the book.

djmips2 anni fa

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

_the_inflator2 anni fa

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.

[deleted]2 anni fa

whateveracct2 anni fa

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.

eggdaft2 anni fa

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

jiggawatts2 anni fa

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.

fegu2 anni fa

I enjoyed this :)

throwaway2902 anni fa

Meh... saying cosmic event horizon is like far lands is flat earthing at cosmic scale.

You can't physically get there, it's always the same distance from where you are (though it's shrinking over time they say)

hnuser1234562 anni fa

You don't have to get there, it will eventually come to you. https://youtu.be/eVoh27gJgME?si=ld9M-ZAfK37XdyJL

[deleted]2 anni fa

lebaux2 anni fa

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

ReleaseCandidat2 anni fa

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

lebaux2 anni fa

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 :')

bruce3434342 anni fa

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

araes2 anni fa

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

bruce3434342 anni fa

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

araes2 anni fa

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

bruce3434342 anni fa

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?

Link is Access Denied btw, but sci-hub works.

beaumayns2 anni fa

For a pretty good explanation of the algorithm, check this out: https://caseymuratori.com/blog_0003

Consider also the minkowski portal refinement algorithm: http://xenocollide.snethen.com/mpr2d.html . Similar idea, but I find it more intuitive.

fho2 anni fa

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

bruce3434342 anni fa

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.

fho2 anni fa

No, but on some level line and plane equations are similar too. It's more about splitting bodies into convex parts to speed up the calculations.

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

JKCalhoun2 anni fa

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.

weaksauce2 anni fa

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

bob10292 anni fa

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.

9dev2 anni fa

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.

kqr2 anni fa

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.

rikroots2 anni fa

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

Tade02 anni fa

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.

arketyp2 anni fa

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

yzydserd2 anni fa

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.

nickpow432 anni fa

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)

dan-robertson2 anni fa

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

plopz2 anni fa

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.

markisus2 anni fa

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

lqr2 anni fa

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-chisel2 anni fa

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

dan-robertson2 anni fa

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

whatever12 anni fa

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.

xeonmc2 anni fa

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?

battesonb2 anni fa

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!

charcircuit2 anni fa

>and it's on a one frame delay

Reading a texture from the GPU can take more than one frame.

hypercube332 anni fa

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

ReleaseCandidat2 anni fa

> could finally bring hardware acceleration to collision

Physx has collision detection.

guitarlimeo2 anni fa

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

Jasper_2 anni fa

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.

akoboldfrying2 anni fa

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)

ReleaseCandidat2 anni fa

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.

bee_rider2 anni fa

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.

raincole2 anni fa

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

[deleted]2 anni fa

lebaux2 anni fa

(2)

charles_f2 anni fa

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.

foofie2 anni fa

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.

naet2 anni fa

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.

wegfawefgawefg2 anni fa

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.

upmostly2 anni fa

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 anni fa

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.

punnerud2 anni fa

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.

elwell2 anni fa

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

fho2 anni fa

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

jjgreen2 anni fa

Look at the Perram-Werthiem contact function

besttof2 anni fa

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

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

nnevatie2 anni fa

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.

slowhadoken2 anni fa

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.

dang2 anni fa

Related:

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

big_paps2 anni fa

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