How to connect points and absorbing momentum?

Question

I am currently working with a show laser device like this. The device receives a list of 2D points which is then displayed. Internally there's a galvanometer that controls the mirror for projecting the laser points.

Let's say I want to display 5 laser points (A, B, C, D, E). Since the laser device doesn't like to travel long distances within short time intervals, one has to add intermediate points, called blanking points (the laser is off while traveling along these blanking points). This procedure is fulfilling the purpose of not stressing the galvanometer too much.

I am currently calculating the "shortest path" in between the 5 points with a simple Nearest Neighbor algorithm, ending up with straight blanking lines (red dotted line in following illustration).

I achieve already quite good results with this optimization. But I want to go a step further. The galvanometer has some physical momentum when moving. When doing sharp turns, e.g. travelling from C->D and D->E, it does stress the laser device.

So I was thinking about absorbing some of this physical momentum by introducing curved blanking lines instead of straight blanking lines (cp. to last image in above illustration "Solution?").

Any idea how to achieve that?

Pointing to some algorithm resources and/or some pseudo-code or C# would be helpful. Thank you!

Answer 1

As others have mentioned, you want to use some kind of cubic spline interpolation for this.

Once you know the time at which each key point will be visited, and the velocity at each point, then you can calculate a piecewise cubic Hermite spline that passes through the key points at the chosen velocities. See: https://en.wikipedia.org/wiki/Cubic_Hermite_spline

Since you don't have any particular requirements for the velocities, you probably want to use a classic cubic spline (yes the names for these thing are ambiguous): http://mathworld.wolfram.com/CubicSpline.html This form of spline determines the velocities to ensure that both the first derivative (speed) and second derivative (acceleration) are smoothly varying along the whole path.

Since you also don't have any particular requirements for the exact times at which each key point is reached, you probably want to set the maximum time for the whole path and then choose the timings of the key points to minimize maximum acceleration or something like that. I don't have a really easy way to do that. What I would try is:

Initially, make the time between key points proportional to the distance between those points. Then, apply a few rounds of:

1. Adjust the time spent in each segment to make tangential acceleration 0 at the key points.
2. recalculate the spline

You may be perfectly happy without these optimization rounds, though -- the initial guess is not going to be too bad.