While working on Worldbuilder v0.2, I spent a fair amount of time implementing an algorithm for generating distance fields on the surface of a sphere. It was admittedly a struggle, with many false starts, but I finally stumbled upon a solution that works well, producing a distance field with a high degree of accuracy, and executing very quickly with the help of the GPU.
Most of the literature I could find on the topic was focused either on generating distance fields for flat 2D images, or for full 3D space. In both cases, space was always Euclidean, whereas distance on the surface of a sphere behaves quite differently. Additionally, most algorithms I ran across were focused on calculating distances from a collection of points, but for reasons I’ll discuss below, I needed to calculate accurate distances from polygon outlines. Some of the 3D algorithms were tantalizingly close to what I wanted, since they often started with a triangle mesh as their input, but the 3D aspect greatly increased the complexity of the algorithms relative to my needs, while still not addressing my non-Euclidean needs.
In the end, the algorithm that I finally implemented is honestly nothing very impressive, and I kind of figured it out by accident. But it works, and it works well, despite being something of an ugly hack. As it might help others needing to do something similar, allow me to share the details of this algorithm, along with the journey getting there. Though admittedly, the journey does get a bit verbose at times, so feel free to jump straight to the final algorithm. I tried to keep that section relatively self-contained. Just know that you’re skipping over loads of pretty pictures. (more…)