4 ms·

I have had to do some non-trivial work with quadtrees, and one thing I realized, which is not so well-advertised, is that there are really two main categories o

I have had to do some non-trivial work with quadtrees, and one thing I realized, which is not so well-advertised, is that there are really two main categories of quadtrees. So-called "linear" quadtrees are a somewhat different beast that the more typical "pointer to children" ones. They're really just different representations of the same thing (a quadtree), but those representations have such different use-cases and performance characteristics that I tend to think of them differently. Linear quadtrees typically use Morton codes (or another space-filling curve), and are good at doing fast queries against static data. You build the tree once, then query it lots. Whereas "standard" quadtrees are more about dynamism — being able to add and remove items quickly. This is a great SO post on dynamic-style quadtrees: https://stackoverflow.com/questions/41946007/efficient-and-well-explained-implementation-of-a-quadtree-for-2d-collision-det/48330314#48330314 https://stackoverflow.com/questions/41946007/efficient-and-w... It was quite hard for me to find open-source implementations of linear quadtrees. Whereas there are all kinds of implementations of the more common kind. One day I'll open-source my code. I was going back to papers from the '80s for some of that stuff (:

exDM69 4y ago
I'm also working on a linear octree (like quadtree but 3d) right now. An array sorted by Morton code is a quadtree/octree and an equally spaced kd-tree. Radix sorting can be used for sorting in linear time (and GPUs). When looking at the Morton code, if the most significant bit is 0 then it is on the left side of the x=0 plane, and right side if the bit is 1. You can find the split position where the bit flips with binary search. Then recurse to both halves using the next most significant bit which corresponds to the y=0 plane. Each level of recursion splits the space in two. You could also get the splits "for free" from the histograms produced during radix sorting to reduce the number of binary searches. This idea can be extended to AABBs instead of points by XORing the end point Morton codes and counting the leading zeros. A lot of literature was written on this topic in the past 10-20 years for the purpose of building acceleration structures for Ray tracing on the GPU.
gniv 4y ago
> It was quite hard for me to find open-source implementations of linear quadtrees. You probably know this, but the S2 library has one: https://github.com/google/s2geometry https://github.com/google/s2geometry
- turtledragonfly 4y ago
  Thanks for the link — no, I had not heard of it. Though I must say, looking at it briefly, I see no direct mention of "linear quadtree" (or even just "quadtree"), nor morton codes, z-order curves, BIGMIN/LITMAX functions, etc. I suppose that's another difficulty with quadtrees — they're so common and amenable to hand-rolling that there are lots of different variations on terminology. Do you happen to know where the linear-quadtree-related code is, in that library?
  - gniv 4y ago
    It's the S2 cell ids (S2CellId in the library). See also this slide deck: https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSn...
  - yencabulator 4y ago
    S2 uses Hilbert curves, which is slightly different but definitely the same idea. https://s2geometry.io/devguide/s2cell_hierarchy https://s2geometry.io/devguide/s2cell_hierarchy A cell ID in the S2 coordinate system is equivalent to he path to a quadtree node, as in 0101101 describes which sub-sub-sub-etc-quadrant you're talking about. It seems like linear quadtree in this context would essentially be an array sorted by S2 cell ids? (I'm not entirely clear is linear quadtrees are just the old trick of array-ifying a fixed-fanout tree structure, where k's children are 2k+1, 2k+2, etc.)
    - turtledragonfly 4y ago
      A linear quadtree is (most commonly, in my experience) just a list of Morton codes, sorted. So yes, very similar to sorted S2 cell Ids, it would seem. One way to efficiently do a spatial query on such a sorted list is the BIGMIN/LITMAX algorithm I mentioned earlier. I believe the originating paper is: http://hermanntropf.de/media/multidimensionalrangequery.pdf http://hermanntropf.de/media/multidimensionalrangequery.pdf (see section 4 — "Range Search"). In my particular case, I also only cared about the "black" nodes in a tree (that is, ones with some data inside), so the linear quadtree is also sparse, speeding it up more. I think since S2 is modeling the entire sphere's surface, it is fully dense. A sparse version might be "only include the cells that contain land," if that were all that was needed for the application. Though in the sparse version, you don't have fixed-fanout (or at least, it's not embodied in the array), so can't use the trick you mention. Pros and cons (: One key advantage of Morton codes is that, given a cell ID, you can split it into the "x bits" and "y bits", to get a genuine (x,y) coordinate in the mapped space. Then you can, for instance, easily navigate to your (spatial) neighbor by incrementing X or Y. If I understand your last sentence correctly, this is not something you can do so easily with a plain array-ifying trick.

exDM69 4y ago

I'm also working on a linear octree (like quadtree but 3d) right now. An array sorted by Morton code is a quadtree/octree and an equally spaced kd-tree. Radix sorting can be used for sorting in linear time (and GPUs). When looking at the Morton code, if the most significant bit is 0 then it is on the left side of the x=0 plane, and right side if the bit is 1. You can find the split position where the bit flips with binary search. Then recurse to both halves using the next most significant bit which corresponds to the y=0 plane. Each level of recursion splits the space in two. You could also get the splits "for free" from the histograms produced during radix sorting to reduce the number of binary searches. This idea can be extended to AABBs instead of points by XORing the end point Morton codes and counting the leading zeros. A lot of literature was written on this topic in the past 10-20 years for the purpose of building acceleration structures for Ray tracing on the GPU.

gniv 4y ago

> It was quite hard for me to find open-source implementations of linear quadtrees. You probably know this, but the S2 library has one: https://github.com/google/s2geometry https://github.com/google/s2geometry

turtledragonfly 4y ago
Thanks for the link — no, I had not heard of it. Though I must say, looking at it briefly, I see no direct mention of "linear quadtree" (or even just "quadtree"), nor morton codes, z-order curves, BIGMIN/LITMAX functions, etc. I suppose that's another difficulty with quadtrees — they're so common and amenable to hand-rolling that there are lots of different variations on terminology. Do you happen to know where the linear-quadtree-related code is, in that library?
- gniv 4y ago
  It's the S2 cell ids (S2CellId in the library). See also this slide deck: https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSn...
- yencabulator 4y ago
  S2 uses Hilbert curves, which is slightly different but definitely the same idea. https://s2geometry.io/devguide/s2cell_hierarchy https://s2geometry.io/devguide/s2cell_hierarchy A cell ID in the S2 coordinate system is equivalent to he path to a quadtree node, as in 0101101 describes which sub-sub-sub-etc-quadrant you're talking about. It seems like linear quadtree in this context would essentially be an array sorted by S2 cell ids? (I'm not entirely clear is linear quadtrees are just the old trick of array-ifying a fixed-fanout tree structure, where k's children are 2k+1, 2k+2, etc.)
  - turtledragonfly 4y ago
    A linear quadtree is (most commonly, in my experience) just a list of Morton codes, sorted. So yes, very similar to sorted S2 cell Ids, it would seem. One way to efficiently do a spatial query on such a sorted list is the BIGMIN/LITMAX algorithm I mentioned earlier. I believe the originating paper is: http://hermanntropf.de/media/multidimensionalrangequery.pdf http://hermanntropf.de/media/multidimensionalrangequery.pdf (see section 4 — "Range Search"). In my particular case, I also only cared about the "black" nodes in a tree (that is, ones with some data inside), so the linear quadtree is also sparse, speeding it up more. I think since S2 is modeling the entire sphere's surface, it is fully dense. A sparse version might be "only include the cells that contain land," if that were all that was needed for the application. Though in the sparse version, you don't have fixed-fanout (or at least, it's not embodied in the array), so can't use the trick you mention. Pros and cons (: One key advantage of Morton codes is that, given a cell ID, you can split it into the "x bits" and "y bits", to get a genuine (x,y) coordinate in the mapped space. Then you can, for instance, easily navigate to your (spatial) neighbor by incrementing X or Y. If I understand your last sentence correctly, this is not something you can do so easily with a plain array-ifying trick.