Not my area at all, but having done some work on ray-tracing back in the days, it kinda reminded me of the ray-triangle acceleration structures there[1], except your entities are 1-D lines rather than 3-D triangles.
One which came to mind which possibly might be interesting would be the Bounding Interval Hierarchy[2], where you partition the space but also keep the min/max intervals of all children in each node. The "Instant ray tracing" paper[3] details some interesting techniques for speeding up construction.
Or perhaps it's a rubbish idea, haven't really thought it through.
Definitely! It's a great idea and something I've been trying out. So far I've tested typical bounding volume hierarchies and spatial acceleration structures in 1-d (e.g, some of the cache friendly quadtree designs applied to 1d, r-trees, k-d trees) but they weren't able to outperform my simple ordered map yet unfortunately.
Since you mentioned SIMD acceleration, did you look at things like QBVH[1]? I mean it would be kinda like a B-tree I suppose but with the min/max stuff.
I did look at QBVH and flattening it to a single dimension, but my understanding is that most specialized BVHs like this prefer mostly static geometry because updates are so expensive. I'd be happy to be wrong on this though - QBVH looked complicated enough that I didn't want to experiment with it without some strong signals that it would be the right direction.
From my ray-tracing days, I recall that the majority of the time spent in the acceleration structure was due to cache misses when traversing nodes.
It might be you want to use a binary partitioning algorithm or similar for just a few levels, and then have the leaf nodes be N spans in a (sorted) list, where N is somewhat large. Then you can have some fast loop to mow through the leaf spans.
Fair point. They mention they do a regular construction and then reduce it to the QBVH, so was wondering if the BIH approximate sort trick could be used effectively.
One which came to mind which possibly might be interesting would be the Bounding Interval Hierarchy[2], where you partition the space but also keep the min/max intervals of all children in each node. The "Instant ray tracing" paper[3] details some interesting techniques for speeding up construction.
Or perhaps it's a rubbish idea, haven't really thought it through.
[1]: https://en.wikipedia.org/wiki/Binary_space_partitioning
[2]: https://en.wikipedia.org/wiki/Bounding_interval_hierarchy
[3]: http://ainc.de/Research/BIH.pdf