Can we fix the problem of time warping through planets?

[JonnyOThan]

When on a collision or aerobraking trajectory, it’s pretty easy to warp through a point where rails warp should have been disabled. Can we do anything about this? It shouldn’t be difficult to calculate a point on your orbit where you shouldn’t warp past.

[gotmachine]

shouldn’t be difficult

Famous last words :P

To describe the full problem, what is needed is a way to detect if a point moving along an arbitrary 3D ellipse is intersecting a sphere moving along another arbitrary ellipse between a time interval, where those two objects have an arbitrary and non linear velocity over time.

I don't think even the most cutting edge CCD stuff out there is capable of this, AFAIK they assume linear velocity between time steps, at best they account for angular velocity too. Maybe a 3D ellipse / ellipse analytical intersection test algorithm is possible, but that would likely be quite complex.

But lets simplify the problem a bit. Assume the vessel and bodies are moving in a straight line : the problem is now a relatively simple ray / capsule intersection check, which can be done by decomposing the check into two ray/sphere intersections and a ray/cylinder intersection.

But you have to consider that at the timesteps of the highest timewarp rates, a vessel or a body can move by a significant portion of a full orbit revolution, and in many cases, by more than a full revolution. If you just take the position of the vessel and of the body at the current fixed frame and at the next fixed frame to generate your ray and capsule respectively, that will generate garbage results.

To have the ray and capsule be an acceptable representation of the elliptical trajectories, you need to decompose the time step into smaller ones where both orbits curvature between the start and end times is small enough, said otherwise, where the angle between the normalized velocity vectors at times t and t+n is small enough. There are probably smart ways to find those points, but a naive bisection is gonna take a lot of iterations.

So, to summarize :

• For each vessel
• Discretize the next fixed time step into smaller steps approximating the orbit ellipse section into lines of acceptable error.
• For each body that it can potentially collide with
• Discretize its trajectory too
• For every vessel and body time pair, get their position and perform a ray/capsule intersection check.

Obviously, this would be quite computationally expensive, and definitely not compatible with decent frame rates if done naively using the KSP orbit stuff. There are maybe a few smart ways to early out of the full check and to make it faster, but I wouldn't qualify any of this as "not difficult".

Edit :
Ok, actually, stock does all of this already to find where an orbit patch encounter a SOI edge, which is a basically an arbitrary radius centered on a body. So it should be possible to adapt that code to check for encounters with the body itself.

[JonnyOThan]

Ah, yeah this isn’t a complex math problem at all. The game already knows where the SOI translations are. Even within a single SOI you can warp through the body or atmosphere. That’s a simple calculation to find the time at which you cross a certain altitude.

The hard part, I think, is making sure timewarp doesn’t go past that point.

[gotmachine]

That’s a simple calculation to find the time at which you cross a certain altitude

You're right, I was overthinking this as a need for a generalized method to find intersections with any body. But since KSP already discretize any potential intercept by splitting the trajectory into separate orbit patches for each encountered SOI, all we have to do is find when each orbit patch is crossing a specific altitude threshold.

The hard part, I think, is making sure timewarp doesn’t go past that point.

Once we have encounter UT for every patch, it's trivial : get the smallest one, and if current UT + next time step > smallest UT, stop (or lower) warp rate. Although we can make it a bit fancier by slowing warp progressively like stock does on SOI transitions (see TimeWarp.ClampRateToOrbitTransitions()).

All this should likely be done as additional logic in TimeWarp.getMaxOnRailsRateIdx() which is the code that is supposed to slow warp rate depending on the altitude thresholds / body intersect. Specifically, the part that isn't smart enough is the if (lookAhead...) part, which is testing the body and its altitude warp limits against the current UT + deltaT at current warp rate, failing to detect an intersection happening during that deltaT.

This being said, that (not very reliable) stock code is currently only checking the active vessel. I'd say ideally we would do this for every vessel, but then the perf overhead would start to be significant. The "next encounter UT" could be cached, more or less eliminating the issue, it doesn't need to be recomputed as long as the vessel is on rails and no new orbit patch is added, but that entails doing the caching somewhere, likely another "object extension" static dictionary.

Another question then becomes what should happen when a not-active vessel intersects a body. Having timewarp being stopped because a random debris at the other end of the system is about to crash into a moon doesn't feel like a good idea, I'd say for other vessels we should probably just treat this as a collision detection improvement and destroy it.

Anyway, quick and dirty test implementation here, seems to work well enough :

[KSPAddon(KSPAddon.Startup.Flight, false)]
public class TestBodyEncounter : MonoBehaviour
{
    private double nextEncounterUT;

    void FixedUpdate()
    {
        TimeWarp timeWarp = TimeWarp.fetch;

        if (timeWarp.current_rate_index <= timeWarp.maxPhysicsRate_index)
            return;

        Vessel v = FlightGlobals.ActiveVessel;
        Orbit currentPatch = v.orbit;

        nextEncounterUT = double.MaxValue;
        while (currentPatch != null)
        {
            double periapsis = currentPatch.PeR;
            double stopWarpRadius = currentPatch.referenceBody.Radius + timeWarp.GetAltitudeLimit(timeWarp.current_rate_index, currentPatch.referenceBody);
            if (double.IsFinite(periapsis) && periapsis <= stopWarpRadius)
            {
                double encounterTA = currentPatch.TrueAnomalyAtRadiusSimple(stopWarpRadius);
                if (double.IsFinite(encounterTA)) // will be NaN if no intercept
                {
                    double encounter1DT = currentPatch.GetDTforTrueAnomaly(encounterTA, 0.0);
                    double encounter2DT = currentPatch.GetDTforTrueAnomaly(-encounterTA, 0.0);

                    double patchEncounterUT = currentPatch.epoch + Math.Min(encounter1DT, encounter2DT);

                    if (patchEncounterUT < nextEncounterUT)
                        nextEncounterUT = patchEncounterUT;
                }
            }

            if (currentPatch.patchEndTransition == Orbit.PatchTransitionType.FINAL)
                break;

            currentPatch = currentPatch.nextPatch;
        }

        if (nextEncounterUT == double.MaxValue)
            nextEncounterUT = double.NaN;
        else if (Planetarium.GetUniversalTime() + Time.fixedDeltaTime * timeWarp.warpRates[timeWarp.current_rate_index] >= nextEncounterUT)
            timeWarp.setRate(timeWarp.current_rate_index - 1, true, true, true, true);
    }

    void OnGUI()
    {
        GUI.Label(new Rect(50, 80, 400, 20), "Next encounter: " + KSPUtil.PrintDateDelta(nextEncounterUT - Planetarium.GetUniversalTime(), true, true));
    }
}

[JonnyOThan]

A vesselmodule would be a good place to cache "next UT" for unloaded vessels. I only really care about the active one though.

[gotmachine]

Adding a VesselModule for storing two values is totally overkill, I prefer the static dictionary approach.

[JonnyOThan]

Yeah, fair...if we have a VesselModule for other fixes we could combine some...although they might have different update requirements.

I missed this part though - sounds like a better solution anyway:

I'd say for other vessels we should probably just treat this as a collision detection improvement and destroy it.

The one wrinkle is non-loaded vessels that enter atmosphere but where the periapsis is above the auto-destruction threshold. I think you'd just have to ignore them because you can't simulate drag at that point anyway so there's no point in dropping out of timewarp. This seems pretty consistent with the timewarp behavior in the tracking station.