Spatial (resolution-aware) caching

[Keavon]

Spatial, and likely temporal, caching needs to with based on storing cached data at different zoom levels, areas in space (forming a patchwork quilt of cache hit areas within surroundings of cache miss areas), and different times in the animation timeline. All this will be needed to make Cache nodes relation-aware to work with footprint data.

[0HyperCube]

@Keavon I'm not really sure how we can do this. If we have f(Footprint) = disk sampled points and want to avoid doing the disk sampling many times, then how can we be sure that changing the footprint won't impact the result?

If we actually implemented the cull node, then changing the footprint by panning around would certainly impact the result - so if the shape was initially outside the viewport and we cached the empty result, then that would not be ideal.

[TrueDoctor]

If we actually implemented the cull node, then changing the footprint by panning around would certainly impact the result - so if the shape was initially outside the viewport and we cached the empty result, then that would not be ideal.

The idea of resolution aware caching would be that we only reuse the cached result if the outcome would be the same and otherwise recompute. The click targets are a bit more tricky to update but that's the basic idea

[0HyperCube]

@TrueDoctor How do we know if the "outcome would be the same" without computing the outcome?

[Keavon]

@TrueDoctor wrote in Discord:

There are basically two possible ways of going about this:

1. Fix the performance and actually make everything fast enough to be executed in real time
2. Change how click targets are propagated: If instead of just storing the click targets in the monitor nodes, we instead attach the click targets to the data type, we can modify the click target in the cache node. When the user then pans around in the viewport and we know that the data we have cached is basically still correct, we could modify the click target in the cache node to reflect the proper location.

But I honestly think that we really should not need to rely on caching for purely vector data. There are a bunch of potential optimizations we can do which should could speed this up (e.g. eliminating unnecessary clones etc.)

[0HyperCube]

@TrueDoctor / @Keavon

For 1, this is quite challenging given that poisson disk sampling inherently requires quite a lot of allocation and computation. A popular algorithm for fast poisson disk sampling is https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf. I have also noticed that the code for sampling based on Euclidean distance is very inefficient and I might try and improve that sometime. However even with the current total caching currently we get a frame time of 80ms or ~12fps which doesn't really give a lot of room for these algorithms to run in real time.

For 2, I'm not sure how this is relevant as click targets are stored in document space so don't change as the user pans around the document.