3 ms·

Realtime collision detection[1] has a fantastic chapter in this with some really good practical examples if I remember right. Great book, I used to refer to it

• trebcon 4y ago
  The implicit grid data structure from there is a personal favorite of mine. I used it in a game once and it performed incredibly well for our use case. It's a bit too complicated to totally summarize here, but it uses a bit per object in the scene. Then bit-wise operations are used to perform quick set operations on objects. This data structure got me generally interested in algorithms that use bits for set operations. I found the Roaring Bitmap github page has a lot of useful information and references wrt this topic: https://github.com/RoaringBitmap/RoaringBitmap https://github.com/RoaringBitmap/RoaringBitmap
  • phkahler 4y ago
    I spent a lot of time optimizing an octree for ray tracing. It is my favorite "spatial index" because it's the only one I know that can be dynamically updated and always results in the same structure for given object placement.
• SotCodeLaureate 4y ago
  I often recommend this book, RTCD, as a "better intro to data structures and algorithms" (sometimes as "the best"). The advice often falls on deaf ears, unfortunately.
• Gene_Parmesan 4y ago
  Seconding the RTCD recommendation. Handy code examples, and my favorite part is that the book is real-world-performance-conscious (hence the "real-time" in the title).
• thegeomaster 4y ago
  It's a stellar book. I work on a commercial realtime physics engine, the "orange book" is practically required reading here.