Calculating a Flight Path Between Two CFrames

[JimmyChance]

Background

In a project I am working on, I want to create a path between a start and end CFrame for an airplane to follow. However, linear interpolation will obviously not work because airplanes travel in the direction they face.

Issue

This would not be especially hard to do using Bézier curves, but there are a few restrictions which have made it extremely challenging for me:

1. The path must support an airplane that can travel at a maximum velocity of v studs/second
2. The path must support an airplane that can turn at a maximum angular velocity of t degrees/second along each of its principal axes.

And it would be preferred if the path minimizes the distance traveled.

Attempts

With Bézier curves, it is simple to create a cubic function with a controlled sharpness between two CFrames. The only problem is that the curves generated are not wide enough for the first and second conditions to be satisfied.

Additionally, there are many different flight paths a plane can take even with the restrictions mentioned which complicates the problem further. (Just finding one would be enough.)

Is there a method or formula I can use to figure this out?

[0x_7777]

You are going to want to avoid using a Bezier curve, as using a Bezier curve is going to really limit you if you wish to impose certain physical restrictions (velocity, angular velocity, whatever you want). Representing your path via a Hermite Spline is going to be the best route, as this representation allows you to easily validate and constrain your splines states (position & derivatives).

edit: good, quick, and accessible ppt on splines http://www.cs.cornell.edu/courses/cs4620/2012fa/lectures/28splines.pdf

[JimmyChance]

I tried using Hermite splines, but the conditions imposed are still too challenging for me to implement using them. The restrictions in the opening post are to make sure the curvature of the path does not exceed a certain value, but constraining spline curvatures is a nontrivial task. It is probably best if I show my current approach.

1. Define three fourth degree parametric polynomials x(t), y(t), z(t), t ∈ [0, 1] (15 unknown coefficients)
2. Specify the positions at the start point and end point (6 equations generated)
3. Specify the velocity at the start point and end point (6 equations generated)
4. There are three unknowns left, but the problem is that the curvature formula is especially complex in this case. When I tried solving a simpler problem on a 2D plane (z = 0), the polynomial in the numerator of the curvature equation alone was of degree 9. I did not attempt to solve the inequality after that.

I am using the formula that defines the curvature as the ratio of the magnitude of the cross product of the velocity and acceleration vectors (<x’(t), y’(t), z’(t)> and <x’’(t), y’’(t), z’’(t)>) and the magnitude of the velocity vector cubed.

Edit: Added pictures to show the bad flight path and desired flight path. (Note the curvature.)

[Quasiduck]

You can control the rate at which you traverse the curve using the same method used here for Bezier curves. ios - How to achieve uniform speed of movement on a bezier curve? - Game Development Stack Exchange Using this, it follows that if you want to travel along the curve L units every second, then you can increment t by L*dt / ||dM/dt||. (Ensure L * dt is sufficiently small. dt is the time elapsed per heartbeat if you choose to use heartbeat.) This will allow you to set the current Speed of your airplane of which you can accelerate by changing L which represents speed. Overall, you have much more control over speed along the curve with this method and can worry less about the magnitude of the velocities at your control points. What matters more is control of the actual path-shape as rate of traversal is easily controlled.

Trying to find a spline which turns at a set maximum angular velocity (or in your case, trying to constrain the curvature by setting a max value for curvature) is not easy. However, it’s not really necessary for good control over the curvature. Using: https://www.cs.uky.edu/~cheng/PUBL/Paper-Geometric-Hermite.pdf. On page 287, multiply both of your velocities at the control points by the value, a*. Note that the sum of both x-coordinates (from both velocities) must be greater than 0 to avoid a* being negative and flipping the direction of your velocities.

What this does is minimise sharp turns (whilst also preventing some other unwanted byproducts of hermite splines) along the curve. More specifically, it minimises the integral of the squared second derivative over the interval to achieve this. From there, set the direction of the velocity vectors at your control points reasonably and it shouldn’t curve too much. The closer they are to having the same direction, the less curving is usually done allowing for decent control over the curvature.

If the path minimizes the distance travelled, it would quickly converge onto a straight line between the start and end point, curving very sharply near them to match the starting and ending velocity directions.
This would not look nice.

As for applying the appropriate CFrame, you should calculate both your position on the curve and the tangent at your position which will be it’s vector derivative at that point. From there, use CFrame.new(pos, pos + tangent)*CFrame.Angles(0, 0, k). You probably want your airplane to turn left/right with greater x-z curvature (ignoring y because plane shouldn’t turn left/right when going up/down). And so, you can scale k with that curvature to create the turn.

Problem is, the curvatures between different pieces of the entire spline aren’t continuous, (i.e. no C2 continuity) and so, the k value will jump between connecting curves causing the turns to suddenly “jump” rather than change smoothly. For this, two solutions are:

1. Use a quintic hermite spline to define the starting & finishing “acceleration” and set the starting acceleration on the next curve as the finishing acceleration on the previous. This ensures the second derivatives are continuous between curves allowing for smooth changes in curvature. https://www.rose-hulman.edu/~finn/CCLI/Notes/day09.pdf
   However, you’ll have to re-derive the advantage gained from point 2’s paper for quintic hermite splines by following the paper and trying the similar methods that they used to derive it for cubic hermite splines.

2. Much easier and not too less-aesthetic. Just use the cubic hermite but (for each separate curve) from t = 0.25 to t = 0.75, use the curvature of the spline as the value for k, but from t = 0.75 to t = 0.25 on the next curve, lerp k from curve1’s curvature at t = 0.75 to curve2’s curvature at t = 0.25. Then, start setting k to curve2’s curvature again between t = 0.25 and 0.75 (on curve2 now), and repeat the process for further curves.

[JimmyChance]

I read the paper, and while it does help for some cases, there are still times when the curvature can be erratic. I know it cannot be perfect, however, so I will make use of the results I have now. I give you and everyone else thanks though.

[Quasiduck]

Try limiting the magnitude of the velocity vectors at the start and end points to further control curvature. (I think.)
Also within that paper is a0 and a1 which you can try multiplying start velocity by a0 and end by a1. It might yield better results.

If it still isn’t too satisfying, you’ll simply have to be more wise about choosing your velocity directions and start and end points.

Out of curiosity, in that image, which one of the two curves is the optimized one?

Also, did you manage to keep points evenly spaced using my point 1. ?

[JimmyChance]

Yeah, I was already using those two values (k1 = a0, k2 = a1):

local offset = endPosition - startPosition
local theta = math.acos(math.clamp(startVelocity.Unit:Dot(offset.Unit), -1, 1))
local phi = math.acos(math.clamp(endVelocity.Unit:Dot(offset.Unit), -1, 1))

local k1 = 6*math.cos(theta) - 3*math.cos(phi)*math.cos(theta + phi)/(4 - startVelocity.Magnitude*math.cos(theta + phi)^2)
local k2 = 6*math.cos(phi) - 3*math.cos(theta)*math.cos(theta + phi)/(4 - endVelocity.Magnitude*math.cos(theta + phi)^2)

The optimized curve should be the blue one. And to your last point, I have not tested that yet.

[Quasiduck]

Uh… I don’t think that’s correct because theta and phi will never return negative angles when you use dot product (as it’s scalar). Whilst this won’t affect any of the math.cos(theta)'s or math.cos(phi)'s as math.cos(-x) = math.cos(x). It will affect the math.cos(theta + phi) causing it to not be a true optimized curve.

You should just be using the formula on page 285 under Theorem 2.
The vector squared notation just means dot product with itself. i.e. V ^2 = V . V
This will yield much better results than what you had previously.

Btw if you wanted to try, the curvature k(t) of the cubic hermite should be a polynomial of 5th degree I think. Using some approximation method, find for which 0<=t<=1, k’(t) = 0. From there, plug-in all values of t values derived into k(t), until you find whichever is the maximum value of k(t), the curvature. Then, substitute v0 for a0v0 and v1 for a1v1 and try to find your own a0 and a1 which ensures the max value of k(t) does not exceed some specified “maximum curvature” value.