-
Notifications
You must be signed in to change notification settings - Fork 69
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Downsampling is slow #2961
Comments
I can see two approaches:
I'd be happy to send a PR for either of them. |
Note for the first approach that there is a nice bound for cubic Hermite splines in particular; see Lemma 1 from this paper by Carlson and Hall. |
Note that I am not at all sure that a cubic is really what we want, it was just convenient when this code was implemented. Once you have specified continuity of the position and velocity at the endpoints, a cubic doesn't give you many degrees of freedom (understatement!). A higher degree polynomial, like we use for continuous trajectory, might be preferable. If we look at the problem as trying to find a point in a suitable function space that is "close enough" to the trajectory, I have a hunch that we could be sublinear as long as we are not looking for the closest possible match. Pick a subset of the points, find an approximation, add more points, repeat until the approximation stabilizes. |
Since vessels are user controllable, their trajectories can have weird kinks in them. I don’t see any way to detect these without checking every point (although of course these checks do not have to be performed at interpolation time; they can be performed when the points are initially added to the trajectory). That is, I don’t think it is possible to do better than O(N) amortized. |
This ties into our ideas in #2400 (comment) (the sections of trajectory that do not contain burns should not be serialized, and thus the burns need to be flagged in some fashion). It would probably be a good idea to have a more concrete plan on that side before we start changing the representation from an interpolating spline to something else (downsampling and reanimation will have to coëxist, the former to make sizes mangeable in memory, and the latter to keep saves small). |
Going forward it will be important to separate burns from coasts, both for serialization and for downsampling. I have some ideas about serialization, but I won't start coding until the stuff in Grassmannian is finalized. Regarding downsampling: The burns are integrated using an adaptive step integrator, it's not even clear that downsampling buys us a lot, as the integrator adapts to the kinks. Surely errors of 10 m are excessive, e.g., when doing a rendezvous. The coasts on the other hand must be close to arcs of conics, so I am hoping to reuse some of the work that didn't quite pan out for #2400. |
Possible low-hanging fruit: I ran into this code which seems rather dumb: Principia/physics/discrete_trajectory_body.hpp Lines 311 to 328 in 9e6326d
In the very common case where these functions are called with an actual point of the trajectory, maybe they could avoid constructing an interpolation and just do a lookup in the map instead. |
There has to be a better way to approximate a trajectory by a low-degree polynomial. The current implementation does O(N Ln N) evaluations of the cubic sequentially.
The text was updated successfully, but these errors were encountered: