I am looking for a fast algorithm to remove keyframes based on a maximum error. So if a keyframe is near enough to what can be interpolated from the other keyframes, then that keyframe should be removed. I am using linear interpolation only, so this should be relatively simple to do.
For example, let's say I have these keyframes, with their times and values:
In this example I can remove the key at 2.9s, because interpolating the keys at 2.0s and 3.0s would give the exact same value. Depending on the error threshold I might also be able to delete the key at 0.4s, since removing that one gives an error of only 0.1.
I need an algorithm that can handle several floating point data types, like floats, 2D positions and colours (rgba, so 4D).
Of course I managed to come up with simple brute force algorithms for this, but I would like to use something more efficient. I add a lot of keys in real-time over time and ideally the algorithm would do a small amount of work every time a keyframe is added, instead of doing a lot of work at the end, since otherwise I would get hickups whenever I need to finish a block of keyframes.
I tried searching for algorithms for this, but I mostly found info about things like MPEG keyframes and tools in Blender.
Thanks in advance!