News for hackers. Stuff that matters.

A comment on Ask HN: What are some cool but obscure data structures you know about?. Parent comment

Re:Ask HN: What are some cool but obscure data structures yo... by trebcon on Thursday July 21, 2022 @10:03PM (#32187623)
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

[ Parent | on HN ]
Re:Ask HN: What are some cool but obscure data structures yo... by phkahler on Friday July 22, 2022 @04:10AM (#32189736)
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.
[ Parent | on HN ]