6 ms·
Collision Detection (2015)
- aappleby 3y agoIf 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 3y agoOne 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/ https://realtimecollisiondetection.net/books/rtcd/
- OnionBlender 3y agoI'm surprised there was never a 2nd edition in the past 20 years.
- _the_inflator 3y agoI 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.
- bananaboy 3y agoNote 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/1050488747010060288 https://twitter.com/ChristerEricson/status/10504887470100602...
- lebaux 3y agoNice, I literally just asked the OP to provide a link! Thank you!
- aappleby 3y agoYep that's the book.
- samlittlewood 3y agoNB: there is a planned 2nd edition without the involvement and against the wishes of the author :( https://x.com/christerericson/status/1050488747010060288?s=46&t=Oehu9L_wdmo9CGRfAH-KKA https://x.com/christerericson/status/1050488747010060288?s=4...
- djmips 3y agoThis is a damn good book. I always recommend it to colleagues.
- dannyfritz07 3y agohttps://www.realtimerendering.com/intersections.html https://www.realtimerendering.com/intersections.html
- lebaux 3y agoThis is super interesting, what further reading would you recommend for a complete beginner in collision detection? Thank you.
- ReleaseCandidat 3y agoNot 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 ;).
- lebaux 3y agoI 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 :')
- _the_inflator 3y agoSpeedrunners 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 3y ago[deleted]
- eggdaft 3y agoIf the simulation hypothesis of reality is correct, does this mean we might encounter such edge cases in physics? Where should we look?
- jiggawatts 3y agoSure, 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.
- fegu 3y agoI enjoyed this :)
- throwaway290 3y agoMeh... 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)
- whateveracct 3y agoEven 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 3y agoThe 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 3y agothe 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 3y agoThis is a nice analogy, never thought of it that way but it makes sense!
- battesonb 3y agoWe 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!
- charcircuit 3y ago>and it's on a one frame delay Reading a texture from the GPU can take more than one frame.
- 3y ago
- dang 3y agoRelated: Collision Detection (2015) - https://news.ycombinator.com/item?id=24735824 https://news.ycombinator.com/item?id=24735824 - Oct 2020 (33 comments)
- bob1029 3y agoI 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/Documentation/ContinuousCollisionDetection.md 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 3y agoThe 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 3y agoIndeed. 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 3y agoI'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 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 https://scrawl-v8.rikweb.org.uk/demo/particles-008.html Position things using particles - https://scrawl-v8.rikweb.org.uk/demo/particles-012.html https://scrawl-v8.rikweb.org.uk/demo/particles-012.html [2] - My favourite JS physics library is MatterJS - https://brm.io/matter-js/ 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_started_js/ https://rapier.rs/docs/user_guides/javascript/getting_starte...
- elwell 3y agoHere is my very basic collision detection in ClojureScript: https://github.com/celwell/wordsmith/blob/master/src/cljs/wordsmith/physics.cljs https://github.com/celwell/wordsmith/blob/master/src/cljs/wo...
- kipi 3y agoShameless 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 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 3y agoThank you for this
- mcyc 3y agoYour videos are absolutely fantastic, thanks for making them!
- drdator 3y agoNice 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.
- deleted 3y ago[deleted]
- beaumayns 3y agoAlso 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 https://github.com/beaumayns/box4d Not nearly as polished as your video, but hopefully someone finds it interesting.
- bfors 3y agoAmazing. How did you create the animation of the quake level getting broken down into BSP nodes?
- 3y ago
- Tade0 3y agoNote 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 3y agoKinetic 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 https://github.com/mpihlstrom/femton
- yzydserd 3y agoIt’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 3y agoA 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 3y agoIf 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.
- bruce343434 3y agoThere 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
- fho 3y 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.
- bruce343434 3y agoNot 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.
- fho 3y agoNo, 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)
- araes 3y agoWrite 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_detection_A_survey20161120-10679-yjfxsi-libre.pdf?1479694690=&response-content-disposition=inline%3B+filename%3DCollision_detection_A_survey.pdf&Expires=1705850665&Signature=L1YIvu1twCVRkadXr2OsHBjLdtn~MMC07WJC1yE~Qq5YDhrblbbSHXMdKR6LeSCdDk0pgJWuPUPQcwxQ79QZBOWnDkV1Tx46jVjYkaqGfG4eVmGUx2FWhfD3r7D6fbv0rii8~uecCdrcQYa8z0e7IaOgGn8tqJvLZDz4rXmZk9VVvzMpaQVFXbQPSTXpmCd9c84D4nuhRBIhMxPscHncfM27lhFK5lwWAG-irT-y4~SbuA4LJF6DOlDvNO4~rwyKY1BXz58XyQQ79u5pS6mWE8K6kvSwYG-Ds7WKBNon0ZMA8GCo5t6unAcAJvikw479rVCS1plwPxYV2UIgIWv1EQ__&Key-Pair-Id=APKAJLOHF5GGSLRBV4ZA 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 https://digital.csic.es/bitstream/10261/30526/1/doc1.pdf
- fho 3y 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 3y agoLook at the Perram-Werthiem contact function
- dan-robertson 3y agoA 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_distance_algorithm https://en.m.wikipedia.org/wiki/Gilbert–Johnson–Keerthi_dist...
- markisus 3y agoMinimizing Minkowski difference between convex bodies can also be formalized as a quadratic program. I wonder how the GJK performs against the QP formulation.
- lqr 3y agoHere 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 https://roboticsproceedings.org/rss18/p039.html [2] https://arxiv.org/abs/1405.4980 https://arxiv.org/abs/1405.4980
- foofie 3y agoI'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 3y agoI'm building a Web and iOS game (https://brawlbugs.com 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 https://www.npmjs.com/package/detect-collisions
- wegfawefgawefg 3y agoGood 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 3y agoVery 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-rect.php https://www.jeffreythompson.org/collision-detection/circle-r... could be optimized by instead just checking if distanceSqr < (radius * radius)
- besttof 3y agoI always appreciated Metanet’s collision detection and response tutorial (2011) for its practicality and thoroughness. http://www.metanetsoftware.com/technique/tutorialA.html http://www.metanetsoftware.com/technique/tutorialA.html
- slowhadoken 3y agoI 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.
- wegfawefgawefg 3y agoI 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 3y agoI 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 3y agoThis 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 3y agoWhile collision detection is quite straightforward its collision resolution which always leaves stopping me attempts