[HN Gopher] Collision Detection (2015)
___________________________________________________________________
Collision Detection (2015)
Author : todsacerdoti
Score : 186 points
Date : 2024-01-21 05:17 UTC (17 hours ago)
(HTM) web link (www.jeffreythompson.org)
(TXT) w3m dump (www.jeffreythompson.org)
| aappleby wrote:
| 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 wrote:
| 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 wrote:
| I'm surprised there was never a 2nd edition in the past 20
| years.
| _the_inflator wrote:
| 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.
| bananaboy wrote:
| 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/1050488747010060
| 2...
| lebaux wrote:
| Nice, I literally just asked the OP to provide a link! Thank
| you!
| aappleby wrote:
| Yep that's the book.
| samlittlewood wrote:
| 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 wrote:
| This is a damn good book. I always recommend it to
| colleagues.
| dannyfritz07 wrote:
| https://www.realtimerendering.com/intersections.html
| lebaux wrote:
| This is super interesting, what further reading would you
| recommend for a complete beginner in collision detection? Thank
| you.
| ReleaseCandidat wrote:
| 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
| have 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_inflator wrote:
| 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 wrote:
| If the simulation hypothesis of reality is correct, does this
| mean we might encounter such edge cases in physics? Where
| should we look?
| jiggawatts wrote:
| 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.
| fegu wrote:
| I enjoyed this :)
| throwaway290 wrote:
| 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)
| hnuser123456 wrote:
| You don't have to get there, it will eventually come to
| you. https://youtu.be/eVoh27gJgME?si=ld9M-ZAfK37XdyJL
| whateveracct wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| This is a nice analogy, never thought of it that way but it
| makes sense!
| battesonb wrote:
| 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!
| charcircuit wrote:
| >and it's on a one frame delay
|
| Reading a texture from the GPU can take more than one
| frame.
| ReleaseCandidat wrote:
| > could finally bring hardware acceleration to collision
|
| Physx has collision detection.
| hypercube33 wrote:
| Is it possible to use ray tracer hardware to say raytrace
| polygone vertices and use that for fast collision?
| raincole wrote:
| No? It's just one of the thousands of tasks that biological
| brains are envolved to do well.
| lebaux wrote:
| You are missing one single line of math, basically 1=0=[?].
| This line of math is what separates humanity from fusion
| energy. Of course, I am fully aware of how crazy that sounds --
| go ahead, try to find proof that 1=0=[?] does not compute. It
| is impossible to prove this does not work and at the same time;
| the proof that this line of math works is impossible to grasp.
| If I am right, this very comment will become pretty famous, if
| I am wrong, literally nothing happens and we all move on with
| our lives. Sadly, for me personally, it is impossible to ignore
| this math problem.
|
| I call it "The Last Paradox". It is at very least interesting
| mental/math/physics exercise. Gotta run!
| weregiraffe wrote:
| Someone forgot to take their pills...
| maroonblazer wrote:
| Are you Eric Weinstein?
| ReleaseCandidat wrote:
| The problem 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 same problem as with
| raytracing.
| Jasper_ wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Related:
|
| _Collision Detection (2015)_ -
| https://news.ycombinator.com/item?id=24735824 - Oct 2020 (33
| comments)
| bob1029 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Here is my very basic collision detection in ClojureScript:
| https://github.com/celwell/wordsmith/blob/master/src/cljs/wo...
| kipi wrote:
| 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 wrote:
| Thank you for this
| mcyc wrote:
| Your videos are absolutely fantastic, thanks for making them!
| drdator wrote:
| 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.
| beaumayns wrote:
| 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 wrote:
| Amazing. How did you create the animation of the quake level
| getting broken down into BSP nodes?
| kipi wrote:
| Thanks. I made it in Blender, with a Python script for
| loading the Quake level and setting up the Blender scene
| Tade0 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| bruce343434 wrote:
| 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
| fho wrote:
| > 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 wrote:
| 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.
| fho wrote:
| 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)
| araes wrote:
| 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
| bruce343434 wrote:
| With "simplex based" do you mean algorithms that require a
| tetrahedralized mesh? Because tetrahedralization is yet
| another non-straightforward topic...
| araes wrote:
| 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."
| bruce343434 wrote:
| 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.
| beaumayns wrote:
| 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.
| JKCalhoun wrote:
| 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 wrote:
| real time collision detection is a good book on those
| fundamentals with real world considerations.
| fho wrote:
| > 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).
| dan-robertson wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| It's nice that you understand this. But the explanation is too
| abstract. Need code to accompany the wiki illustration.
| dan-robertson wrote:
| 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 wrote:
| 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 wrote:
| 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 r2< a2+b2 than r <
| sqrt(a2+b2). 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 wrote:
| 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
| nickpow43 wrote:
| 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 wrote:
| I always appreciated Metanet's collision detection and response
| tutorial (2011) for its practicality and thoroughness.
|
| http://www.metanetsoftware.com/technique/tutorialA.html
| slowhadoken wrote:
| 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.
___________________________________________________________________
(page generated 2024-01-21 23:00 UTC)