MotionPath animation speed unconstant

Hi all,
I need an object moving along a spline with constant speed. I tried to achieve this using the MotionPath class but experienced strange bevaviour. The moving box seems to slow down while passing waypoints. Running the code below shows the problem I described.

[java]import com.jme3.animation.LoopMode;
import com.jme3.app.SimpleApplication;
import com.jme3.cinematic.MotionPath;
import com.jme3.cinematic.events.MotionEvent;
import com.jme3.material.Material;
import com.jme3.math.ColorRGBA;
import com.jme3.math.Quaternion;
import com.jme3.math.Spline.SplineType;
import com.jme3.math.Vector3f;
import com.jme3.scene.Geometry;
import com.jme3.scene.shape.Box;

public class InterpolationTest extends SimpleApplication {

@Override
public void simpleInitApp() {
    MotionPath path = new MotionPath();
    
    path.addWayPoint(new Vector3f(20, 1, 0));
    path.addWayPoint(new Vector3f(20, 1, 5));
    path.addWayPoint(new Vector3f(25, 1, 10));
    path.addWayPoint(new Vector3f(30, 1, 15));
    path.addWayPoint(new Vector3f(35, 1, 15));        
    
    path.setPathSplineType(SplineType.CatmullRom);
    
    path.setCurveTension(0.8f);
    path.setCycle(false);
    path.enableDebugShape(assetManager, rootNode);
    
    Box box = new Box(0.5f, 0.5f, 0.5f);
    Geometry g = new Geometry("Box", box);
            Material mat = new Material(assetManager,
            "Common/MatDefs/Misc/Unshaded.j3md");
    mat.setColor("Color", ColorRGBA.Green);
    g.setMaterial(mat);
    rootNode.attachChild(g);
    
    MotionEvent motionControl = new MotionEvent(g,path);
    motionControl.setDirectionType(MotionEvent.Direction.Path);
    motionControl.setSpeed(4);   
    motionControl.play();
    motionControl.setLoopMode(LoopMode.Loop);
    
    getCamera().setLocation(new Vector3f(4.7138753f, 6.6103964f, -3.0110395f));
    getCamera().setRotation(new Quaternion(0.1379087f, 0.53978395f, -0.09017422f, 0.82551986f));
    //getCamera().lookAtDirection(new Vector3f(0.8663331f, -0.32504195f, 0.37922895f), Vector3f.NAN);
}

public static void main(String[] args) {
    InterpolationTest wnd = new InterpolationTest();
    wnd.start();
}

}[/java]

Setting the spline’s type to Linear or Bezier resolves the issue but I need a smooth curve passing all waypoints so I am stuck with Catmull-Rom.

Thanks for your input!

I have the same behavior for a long time. Not found any solution :frowning:

I’m not sure if FastMath.interpolateCatmullRom() is working as expected…

Hmm… has nobody got an idea concerning this topic? I do think this is a relevant issue as it might affect all cinematics…

The problem seems to scale with the spline’s tension. E.g. a Catmull Rom spline with only two points, let’s say (20, 0, 0) and (20, 0, 20), and a tension of 0.5 seems to work pretty well. Changing the tension to 0.8 leads to an acceleration near the keypoints.

Also, keypoints in a straight line like in the example mentioned above seem to work much better than scattered points.

While I was doing some research on that topic I found out that the Catmull Rom spline is widely regarded to be a special case of a cardinal spline with no tension parameter at all. The naming in jme might be misleading in that case.

http://www.mvps.org/directx/articles/catmull/

A Matlab implementation if anybody interested:

Sorry, its not something I’ve ever tried to use. Hopefully some of the relevant devs will have time to respond to it soon.

Sorry for flooding this thread, but I thought I have to share this:

http://community.spinxengine.com/content/19-constant-speed-cubic-spline-interpolation.html

So it looks like everything we got works as desired- however simply interpolating a spline doesn’t lead to a constant movement. Maybe I find time to try implementing one of the presented solutions of the link above.

I would love to have that shipped with jme3. Just think of any smooth movement with constant velocity-

//EDIT
This might be the way to go:
http://devmaster.net/forums/topic/2963-constant-speed-following-bezier-curve/page__p__19079#entry19079

1 Like

I managed to write a quick and dirty implementation. 8)

The box is now following the spline at a constant speed- at least I can’t see it accelerating or decelerating anymore.
I’ll be happy to post my code if somebody is interested.

1 Like

Sorry i kind of completely missed this topic.
Seems I’m a bit late and things got to a point there is no more issue.
I had a hard time giving the motion path a constant speed, and indeed i didn’t really succeed.
Also the issue with BEzier curves is that the curve is not going through the control points so it can be difficult to control the moving object position from a user point of view.

I’m interested in what you came up with yeah.

So do I. That would be a great addition to JME !
Cinematics cannot really use bezier / catmullRom path for the moment.

The actual problem is that since segments of a spline do not necessarily have the same length, we can’t achieve a constant movement by increasing t constantly. In fact, even if all segments do have the same length we can’t use this approach maybe just because of the math behind of those splines… However, it’s getting worse with different tensions and segment lengths. This plot may help to explain the problem:

//EDIT sorry for image hoster, however you can follow the link in order to see the images

What we do need is a function that maps the arc length to the corresponding value of t. Doing this analytically might be not possible in reasonable time so we need to solve this numerical.

What I came up with is basically just the same what’s already done in the MotionPath’s getWayPointIndexForDistance() method. Computing the arc length of the curve numerical by summing up the results from every step. What is done between every checkpoint in getWayPointIndexForDistance(), I am doing now with a much higher sampling rate. For every sample, I store the total arc length of the spline (from the very beginning to the current position) as the key and the corresponding value of t as value into a TreeMap.
A very very basic approach using linear interpolation and a fixed sampling size could look something like this:
[java] // compute lookup table
float totallength = 0;
float t = 0;
for (int i = 0; i < controlPoints.size() - 1; i++) {
for (int ti = 0; ti < 1000; ti++) {
if ((t + 0.001f) <= 1) {
Vector3f p1 = interpolate(t, i, null);
Vector3f p2 = interpolate((t + 0.001f), i, null);
float length = p2.subtract(p1).length();
totallength += length;
tLookUp.put(totallength, t + 0.001f);
}
t = t + 0.001f;
}
t = 0;
}[/java]
which results in something like this:

Now, we can iterate over the full length of the spline and look up the correct value for t in our prepared table. This might be done in that way:
[java]
Float before = tLookUp.floorKey(l);
Float after = tLookUp.ceilingKey(l);
if (before == null) {
return new Vector2f(keypoint, tLookUp.get(after));
}
if (after == null) {
return new Vector2f(keypoint, tLookUp.get(before));
}
return new Vector2f(keypoint, tLookUp.get(before) + ((l - before) / (after - before)) * (tLookUp.get(after) - tLookUp.get(before)));
[/java]

In order to find the right waypoint to interpolate we can use the already computed segment lengths.

This is just a simple approach- in some cases it doesn’t work out so well, but in some others it does.
It might need a lot of refactoring regarding performance, but maybe one can use it as a starting point. I also do think that not doing the interpolation linear might lead to better results. Also the sampling size needs to be determined in a dynamical way. And last but not least there is this solution I posted above which actually might be more elegant in terms of memory usage. But I don’t know if it really applies to the type of spline’s I’m dealing with.

Which leads back to what I’ve mentioned before, I really do think that Catmull Rom is a very special subtype of a cardinal spline with no tension parameter at all. (Therefore everything I’m doing here is with a tension of 0.5, see wikipedia’s article about cubic hermite spline as a reference.)

However, the problem with the Bézier you mentioned might actually be solved using a hermite spline for construction and converting it to a Bézier then. I found various examples during my research yesterday, never tried one though.

2 Likes

In addition, this paper is basically what I tried to do.

Is there any chance to get something like this into the core? This might be useful not only in terms of cinematics but also when it comes to AI movement, vehicles on tracks etc.

A little demo video of what I’ve achieved so far:

3 Likes

Quite nice a result ! Congratulations.
Is this computed at runtime ? The paper you sent was quite technical and required algorithms seem time-consuming.

NIce!
Well if you have a patch, I’d be grateful

Yeah, that motion looks good now. :slight_smile:

It would be nice to have this as utility functions to allow people not using animation tracks but using curves to use your solution.

(HeroDex uses curves but not animation tracks - although in our case we keep all the curve segments the same length so don’t get a problem anyway).

@yang71 said: Is this computed at runtime ? The paper you sent was quite technical and required algorithms seem time-consuming.

No actually not. Of course you need to build up that look-up table but that can and should be done before you start traversing along the spline. Basically it’s the same what computeCatmullLenght() in the Spline class already does, but with a higher sampling rate.

During the actual movement you only need to search for the corresponding value of t by providing the current arc length. (= traveled distance) I used a Red-black tree (TreeMap) so that can be done in O(log n).
The mean execution time of that search including interpolating with the returned t and computing the direction vector is 7.1481e+04 ns with a table of ~50 000 entries- I used System.nanoTime() which does not necessarily perform better than currentMs() but however- the execution time will be <1ms.

@nehon said: NIce! Well if you have a patch, I'd be grateful

I’d love to help and I’d really love to have within the engine, however I’m not sure about a few things.

  1. This is not an exact solution it’s actually an heuristic method which can perform badly in some corner cases
  2. Where would one expect such a functionality? I don’t recommend recalculating this table every time a control point gets added/removed from a spline like it is currently done with computeLenght() for performance reasons- however one would need to do this before moving along the path using that method.
  3. This is actually not so MotionPath/MotionEvent/cinematics related, so I would recommend putting it into another place- e.g. I would not use it for cinematics in my game. Where would be such a place?
  4. There are better solutions to do this, so we might find a clever brain to come up with a nicer idea. Although this topic doesn’t seem to meet with a lot response up to now… :wink: (Which I don’t really get isn’t that kind of a crucial thing in almost any game?)

I would be very happy if you could share your ideas concerning those questions :slight_smile:

@zarch said: [...] although in our case we keep all the curve segments the same length so don't get a problem anyway).

Oh what kind of splines are you guys using? I’m asking, because at least for catmull-rom splines the speed will still vary. (According to the answer in that topic- I don’t get what that guy is saying, but he’s right in some cases of tangled splines XD )

I’d have to check the code but I think its catmull-rom…however in our case we have mostly constant values for both curvature and segment lengths so its not been a problem so far.

@mduck said: 4. There are better solutions to do this, so we might find a clever brain to come up with a nicer idea.
hehe I was counting on you, I barely know what "heuristic" means :p I'm not really a math guy, I read the catmull-rom paper and just implemented it with all its quirks.

so to fully answer your question in my humble opinion

  1. We don’t really care about exactitude, we’re not making real world simulations, so an approximation is definitely a valid solution.
  2. Why not, as long as it’s not done on every frame it’s ok. Maybe separate it from the addWayPoint method and make a refresh method that has to be called.
  3. mhh It seems related to me why makes you say that?
  4. This looks like the best solution that hit the forum :p, unknown better solution are no solution :p. Sorry about the unresponsive part, I did this catmullRom + motion path thing and I’ve been quite busy lately. As @zarch said, if you have somehow constant length segments the effect is a lot less noticeable, but @yang71 said he had similar issue. I’m not sure cinematics and motion path are a lot use though, so I guess this issue just went unnoticed or not significant enough to be reported until now.
1 Like

Yep.
I had to implement a zig-zag motion for a spy-plane… After 3 days playing with bezier and catmull-rom splines, I gave up because of the random speed. Only linear motion was constant-speed.
Finally, I did it with straight lines and half-circles… I simply rewrote the whole animation using updates, tpf and so on.

Edit : even with similar-length parts, speed was still visibly non-stable.