4 ms·

Fast, Constant-Time Sphere Indexing

117 points by strangecasts 8y ago

alanbernstein 8y ago
I first parsed the title as (Fast, Constant) Time-Sphere indexing, and thought of http://timecube.2enp.com/ http://timecube.2enp.com/. Anyway, neat article, the interactive diagrams are very nice.
- test6554 8y ago
  What did I just read?
nine_k 8y ago
(1) Nice interactive demos of the things being discussed, with live code. (2) Math being directly applied to near-hardware level, the GPU, with a good explanation. What's not to love?
dllu 8y ago
Spatial subdivision with fast indexing on a sphere is quite useful for mapping. We want map tiles to be of close to constant size and shape, and find the tile for any point on Earth. Usually, subdividing the faces of a Platonic solid is the way to go. This post describes tessellation of triangles on the faces of an octahedron. The dual approach is squares on the faces of a cube. A good implementation of this is s2 [1]. [1] http://s2geometry.io/ http://s2geometry.io/
h3throw 8y ago
I used this a lot when I worked at Uber. Very similar but maps to variably sized Hexagons which were nice for things like surge/dispatch algorithms: https://github.com/uber/h3 https://github.com/uber/h3
nimish 8y ago
Hm, I wonder what the algebra would look like if done with Cl(3)/G(3) operations. I think that would be a great exercise to understand geometric algebra and see if it's powerful enough (there's a lot of projecting vectors onto planes, which is trivial in that formalism)
danbruc 8y ago
In case somebody is interested, this [1] is the Microsoft Research paper that introduced this schema under the name Hierarchical Triangular Mesh. Among other things it provides an analysis of the distortion and discusses many operations one may want to perform with such a grid with a focus on GIS applications. And in case someone is interested in the Spherical Fibonacci Mapping mentioned in the article, here [2] is a non-broken link to the paper. [1] https://www.microsoft.com/en-us/research/wp-content/uploads/2005/09/tr-2005-123.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [2] https://docplayer.net/40493580-Spherical-fibonacci-mapping.html https://docplayer.net/40493580-Spherical-fibonacci-mapping.h...
- acemarke 8y ago
  I actually used HTM in a project a few years back. I had a 360x180 sphere of values, and I needed to rotate the sphere in some combination of translations. I did this by converting the az/el/value triplets to Cartesian XYZ and multiplying by a rotation matrix. However, when I tried to convert the translated values back to a rotated az/el/value result, the results broke due to what was effectively lat/lon narrowing (ie, 1x1-degree cells are smaller nearer the "poles", so the rotations didn't map evenly). After research, I settled on using HTM. I was able to borrow the C code from some MySQL extension that implemented HTM (looks like it's at https://github.com/smonkewitz/scisql https://github.com/smonkewitz/scisql ), then use that math to more reliably convert the rotated values back to an appropriate az/el/value result. Still one of the neatest problems I ever solved.
user2994cb 8y ago
There is a neat way of doing this style of indexing using barycentric coordinates: https://www.shadertoy.com/view/MlVfzG https://www.shadertoy.com/view/MlVfzG

117 points by strangecasts 8y ago

I first parsed the title as (Fast, Constant) Time-Sphere indexing, and thought of http://timecube.2enp.com/ http://timecube.2enp.com/. Anyway, neat article, the interactive diagrams are very nice.

test6554 8y ago
What did I just read?

nine_k 8y ago

(1) Nice interactive demos of the things being discussed, with live code. (2) Math being directly applied to near-hardware level, the GPU, with a good explanation. What's not to love?

dllu 8y ago

Spatial subdivision with fast indexing on a sphere is quite useful for mapping. We want map tiles to be of close to constant size and shape, and find the tile for any point on Earth. Usually, subdividing the faces of a Platonic solid is the way to go. This post describes tessellation of triangles on the faces of an octahedron. The dual approach is squares on the faces of a cube. A good implementation of this is s2 [1]. [1] http://s2geometry.io/ http://s2geometry.io/

h3throw 8y ago

I used this a lot when I worked at Uber. Very similar but maps to variably sized Hexagons which were nice for things like surge/dispatch algorithms: https://github.com/uber/h3 https://github.com/uber/h3

nimish 8y ago

Hm, I wonder what the algebra would look like if done with Cl(3)/G(3) operations. I think that would be a great exercise to understand geometric algebra and see if it's powerful enough (there's a lot of projecting vectors onto planes, which is trivial in that formalism)

danbruc 8y ago

In case somebody is interested, this [1] is the Microsoft Research paper that introduced this schema under the name Hierarchical Triangular Mesh. Among other things it provides an analysis of the distortion and discusses many operations one may want to perform with such a grid with a focus on GIS applications. And in case someone is interested in the Spherical Fibonacci Mapping mentioned in the article, here [2] is a non-broken link to the paper. [1] https://www.microsoft.com/en-us/research/wp-content/uploads/2005/09/tr-2005-123.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [2] https://docplayer.net/40493580-Spherical-fibonacci-mapping.html https://docplayer.net/40493580-Spherical-fibonacci-mapping.h...

acemarke 8y ago
I actually used HTM in a project a few years back. I had a 360x180 sphere of values, and I needed to rotate the sphere in some combination of translations. I did this by converting the az/el/value triplets to Cartesian XYZ and multiplying by a rotation matrix. However, when I tried to convert the translated values back to a rotated az/el/value result, the results broke due to what was effectively lat/lon narrowing (ie, 1x1-degree cells are smaller nearer the "poles", so the rotations didn't map evenly). After research, I settled on using HTM. I was able to borrow the C code from some MySQL extension that implemented HTM (looks like it's at https://github.com/smonkewitz/scisql https://github.com/smonkewitz/scisql ), then use that math to more reliably convert the rotated values back to an appropriate az/el/value result. Still one of the neatest problems I ever solved.

user2994cb 8y ago

There is a neat way of doing this style of indexing using barycentric coordinates: https://www.shadertoy.com/view/MlVfzG https://www.shadertoy.com/view/MlVfzG