Deciding on interpolation

[tombh]

In #14 we discovered that interpolation improves viewshed results. But interpolation is expensive, so we should try to find the most efficient approach.

Interpolation to prevent distortion

• Try 3-way skewing to achieve rotation, like in Matt Parker's video: https://www.youtube.com/watch?v=1LCEiVDHJmc
• Try other interpolation methods like spline 8 or 16.
• Explore only interpolating the elevations nearest the centre, say up to a radius of 90 points. 90 creates a square of "circumfrence" 360, so outside that radius interpolation doesn't counteract distortions.
• Whilst bilinear seems to already be a good approach, it does have some artefacting close to the centre, apparently around the specific angles; -135 and -215. What if we just increased the number of rotations around those angles? We might be able to remove the artefacting without unnecessarily doing unneeded extra computations on the other angles.

Interpolation to improve coverage

The academic literature says that rotating 360 (or 180 if you do backward and forward lines of sight) times is optimal for viewshed analysis. However we are not just reconstructing viewsheds, we are specifically looking for individual longest lines of sight. As such, ideally we would rotate approximately 55,000 times to ensure that every possible 100m elevation point was considered in our largest 600km tiles. Not only is this expensive, but also redundant, as the accumulation of error over such distances is non-trivial. So instead of increasing the number of angles we could increase the distance of the samples taken during interpolation. We could always maintain, say, a 4-sample interpolation, just that the spread of the samples increased with the distance from the centre of the tile.

Notes

• It looks like interpolation, namely the bilinear interpolation on the Vulkan kernel, causes black borders on the edge of the tile circle.