Curved Path Constant Speed and End Points

Question

I’m trying to move at a constant speed over a curved path in a given amount of time. I calculated the average speed needed to travel the curve by taking the derivative at various points along the curve and averaging them. Then I multiply the path’s position (t) by a ratio of the average derivative and the derivative at the current location of the curve. This method for setting constant speed works great.

The problem I’m having occurs when multiple control points (3 or more) are put in the same location. Then the speed (or derivative) at this point is 0 and dividing the average speed by a speed of 0 obviously causes problems in the calculations.

BSpline requires three control points to be placed at the ends in order to have the curve actually reach the start and end at the end points. If I only put 1 or 2 control points at the ends the path starts after the first control point and ends before the last control point. For my application it is important that the motion reaches the end points because I will be linking together multiple BSplines and it’s important for them to line up correctly and to not have any time gaps between them either.

I’ve tried a few different attempts at fixing it, but none of them were successful.

Here is my sample code and I've included comments to indicate where the problem is.

NOTE: I used CatmullRomSpline in my example instead of BSpline only because I found a bug in the BSpline’s derivative method, which has been fixed but is not yet in the stable version of LibGDX.

Test.java

public class Test extends Game {
    private Stage stage;
    private MyPath path;

    @Override
    public void create () {
        Gdx.graphics.setDisplayMode(1000, 1000, false);
        stage = new Stage();
        stage.setViewport(new ScreenViewport(stage.getViewport().getCamera()));
        Gdx.input.setInputProcessor(stage);
        path = new MyPath(Gdx.graphics.getWidth(), Gdx.graphics.getHeight());
        stage.addActor(path);
    }
    @Override
    public void render () {
        Gdx.gl.glClearColor(0.1f, 0.1f, 0.1f, 1.0f);
        Gdx.gl.glClear(GL20.GL_COLOR_BUFFER_BIT);
        stage.act(Gdx.graphics.getDeltaTime());
        stage.draw();
    }
    @Override
    public void dispose(){
        path.dispose();
        stage.dispose();
        super.dispose();
    }
}

MyPath.java

public class MyPath extends WidgetGroup implements Disposable {
    private Path<Vector2> path;
    private Vector2 result=new Vector2(), derivative=new Vector2();
    private float time, t, tPrev, dt, tConst, tConstPrev, derivativeAverage;
    private Array<Texture> textures = new Array<Texture>(Texture.class);
    private Array<Image> points = new Array<Image>(Image.class);
    private Image dot;

    private final float CYCLE = 4;  // path cycle time (in seconds)

    private Vector2[] pointsData = {
            new Vector2(100, 100),
            new Vector2(100, 100),
//          new Vector2(100, 100),  // << UN-COMMENT TO PRODUCE BUG

            new Vector2(350, 800),
            new Vector2(550, 200),
            new Vector2(650, 400),
            new Vector2(900, 100),
            new Vector2(900, 100)
    };

    public MyPath(int width, int height){
        this.setSize(width, height);        
        path = new CatmullRomSpline<Vector2>(pointsData, false);
        // create and add images
        createImages();
        for (int i=0; i<points.size; i++){
            points.items[i].setPosition(pointsData[i].x - points.items[i].getWidth()/2, pointsData[i].y - points.items[i].getHeight()/2);
            addActor(points.items[i]);
        }
        addActor(dot);

        // calculate derivative average
        derivativeAverage();
    }

    @Override
    public void act(float delta){
        result = getValue(delta);
        dot.setPosition(result.x - dot.getWidth()/2, result.y - dot.getHeight()/2);     
    }
    private Vector2 getValue(float delta){
        // set t in the range [0,1] for path
        time += delta;
        if (time > CYCLE){
            time = tPrev = dt = tConst = tConstPrev = 0;
        }
        t = time / CYCLE;
        dt = t - tPrev;
        tPrev = t;

        // constant speed (tConst)
        path.derivativeAt(derivative, tConstPrev);
        tConst += dt * (derivativeAverage / derivative.len());  // << ERROR when derivative.len() is 0
        tConstPrev = tConst;

        path.valueAt(result, tConst);

        return result;
    }

    private void derivativeAverage(){
        float segmentCount = 20000;
        derivativeAverage = 0;      
        for (float i=0; i<=1; i+=1.0/segmentCount) {    
            path.derivativeAt(result, i);
            derivativeAverage += result.len();          
        }
        derivativeAverage /= segmentCount;
        if (derivativeAverage==0){ throw new GdxRuntimeException("ERROR: derivative average is zero"); }
    }

    private void createImages(){
        dot = getImage(Color.GREEN, true);
        for (int i=0; i<pointsData.length; i++){
            points.add(getImage(Color.WHITE, false));
        }
    }
    private Image getImage(Color color, boolean fillCircle){
        Pixmap pixmap = new Pixmap(50, 50, Pixmap.Format.RGBA8888);
        pixmap.setColor(color);
        if (fillCircle){
            pixmap.fillCircle(pixmap.getWidth()/2, pixmap.getHeight()/2, pixmap.getWidth()/2-1);
        } else {
            pixmap.drawCircle(pixmap.getWidth()/2, pixmap.getHeight()/2, pixmap.getWidth()/2-1);
        }
        textures.add(new Texture(pixmap));
        pixmap.dispose();
        return new Image(textures.peek());
    }
    @Override
    public void dispose(){
        while (textures.size > 0){
            textures.pop().dispose();
        }
    }
}

===================================================================

EDIT

===================================================================

Here is my latest attempt at increasing t until the dot is moving.

This method does occasionally work on some frames (moving smoothly past the zero derivative). But other times the dot does weird things lie starting over at the beginning of the curve when it hits the zero derivative or extending beyond the end of the curve moving a different direction or disappearing completely (because the position gets set to negative values).

So it seems like this method is really close as it does occasionally work on some frames, but it glitches and does weird things on other frames.

Vector2 lastPoint = new Vector2();
float minSpeed = 1;
float minDerivative = 1;
float temp;

...

private Vector2 getValue(float delta){      
    // set t in the range [0,1] for path
    time += delta;
    if (time > CYCLE){
        time = tPrev = dt = tConst = tConstPrev = 0;
    }
    t = time / CYCLE;

    // CONSTANT SPEED
    dt = t - tPrev;
    path.derivativeAt(derivative, tConstPrev);
    temp = dt * (derivativeAverage / derivative.len());
    path.valueAt(result, tConst + temp);

    //**************************************
    //  FIX FOR ZERO SPEED
    //  increase t in loop until speed > 0
    //**************************************
    while (result.dst(lastPoint)<minSpeed || derivative.len()<minDerivative){
        // set t in the range [0,1] for path
        time += delta;
        if (time > CYCLE){
            time = tPrev = dt = tConst = tConstPrev = 0;
            lastPoint.set(0,0);         
        }
        t = time / CYCLE;

        // CONSTANT SPEED
        dt = t - tPrev;
        // new derivative
        path.valueAt(derivative, t);
        derivative.sub(lastPoint);

        temp = dt * (speedAverage / derivative.len());
        path.valueAt(result, tConst + temp);
    }

    tConst += temp;

    lastPoint.set(result);
    tPrev = t;
    tConstPrev = tConst;

    return result;
}

I also do a similar thing when calculating the average speed to keep the zero derivatives from affecting it. I also tried using the commented out sections with the "addedSegmentCount" variable when calculating the average, but that actually caused more glitches for some reason...even though theoretically this seems like the "correct" way to calculate the average since some segments don't get added if the distance is too small.

private void pathLength_SpeedAverage(){
    float segmentCount = 20000;
//  float addedSegmentCount = 0;
    pathLength = 0;

    path.valueAt(lastPoint, 0);
    for (float i=0; i<=1; i+=1.0/segmentCount){
        path.valueAt(result, i);
        if (result.dst(lastPoint) >= minSpeed){
            path.derivativeAt(result, i);
            if (result.len() >= minDerivative){
                pathLength += result.len();

                lastPoint.set(result);
//              ++addedSegmentCount;
            }
        }
    }
    speedAverage = pathLength / segmentCount;
//  speedAverage = pathLength / addedSegmentCount;
    lastPoint.set(0,0);
}

Answer 1

You cannot completely avoid zero first derivatives if control points could be coincident. So, what I suggest is to not use the first derivatives at all. Your purpose is to traverse the path at a constant speed, which is equivalent to sample points along the path with equal arc length. The theoretical approach to solve this involves calculus to compute arc length numerically, but we can go with an approximation approach as in the following:

Suppose you would like to traverse the path in N steps,
1) Sample M points along the path uniformly in parameter domain (i.e., t=0.0, 0.1, 0.2, 0.3, ....) where M is preferred to be greater than N. Denoting these points as P0, P1, P2,....
2) Compute the distance between P0P1, P1P2, P2P3,....
3) Compile a look-up table that maps from parameter t(i) to the cumulative chord length |P0P1|+|P1P2|+.....+|P(i-1)P(i)|. At the end, you will also obtain the overall length of the path, denoted as L.
4) Now, for each value of kL/N (where k=0 to N), you can compute the corresponding t value from the look-up table by linear interpolating the two parameter values in which the kL/N falls on.