5 ms·

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

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 3y 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/ https://realtimecollisiondetection.net/books/rtcd/
- OnionBlender 3y ago
  I'm surprised there was never a 2nd edition in the past 20 years.
  - _the_inflator 3y ago
    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 3y ago
    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/1050488747010060288 https://twitter.com/ChristerEricson/status/10504887470100602...
- lebaux 3y ago
  Nice, I literally just asked the OP to provide a link! Thank you!
  - aappleby 3y ago
    Yep that's the book.
- samlittlewood 3y 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=46&t=Oehu9L_wdmo9CGRfAH-KKA https://x.com/christerericson/status/1050488747010060288?s=4...
- djmips 3y ago
  This is a damn good book. I always recommend it to colleagues.
- dannyfritz07 3y ago
  https://www.realtimerendering.com/intersections.html https://www.realtimerendering.com/intersections.html
lebaux 3y ago
This is super interesting, what further reading would you recommend for a complete beginner in collision detection? Thank you.
- ReleaseCandidat 3y 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 ;).
  - lebaux 3y ago
    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 :')
_the_inflator 3y 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.
- deleted 3y ago
  [deleted]
eggdaft 3y 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 3y 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.
  - fegu 3y ago
    I enjoyed this :)
    - throwaway290 3y ago
      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)
whateveracct 3y 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.

vvanders 3y 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/ https://realtimecollisiondetection.net/books/rtcd/

OnionBlender 3y ago
I'm surprised there was never a 2nd edition in the past 20 years.
- _the_inflator 3y ago
  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 3y ago
  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/1050488747010060288 https://twitter.com/ChristerEricson/status/10504887470100602...
lebaux 3y ago
Nice, I literally just asked the OP to provide a link! Thank you!
- aappleby 3y ago
  Yep that's the book.
samlittlewood 3y 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=46&t=Oehu9L_wdmo9CGRfAH-KKA https://x.com/christerericson/status/1050488747010060288?s=4...
djmips 3y ago
This is a damn good book. I always recommend it to colleagues.
dannyfritz07 3y ago
https://www.realtimerendering.com/intersections.html https://www.realtimerendering.com/intersections.html

lebaux 3y ago

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

ReleaseCandidat 3y 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 ;).
- lebaux 3y ago
  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 :')

_the_inflator 3y 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.

deleted 3y ago
[deleted]

eggdaft 3y 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 3y 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.
- fegu 3y ago
  I enjoyed this :)
  - throwaway290 3y ago
    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)

whateveracct 3y 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.