Comment obtenir une vitesse de déplacement uniforme sur une courbe de Bézier?

22

J'essaie de déplacer une image le long de la courbe de Bézier. Voici comment je le fais:

- (void)startFly
{    
 [self runAction:[CCSequence actions:
             [CCBezierBy actionWithDuration:timeFlying bezier:[self getPathWithDirection:currentDirection]],
             [CCCallFuncN actionWithTarget:self selector:@selector(endFly)],
             nil]];

}

Mon problème est que l'image ne bouge pas uniformément. Au début, il se déplace lentement, puis il accélère progressivement et à la fin, il se déplace très rapidement. Que dois-je faire pour me débarrasser de cette accélération?

Andrey Chernukha
la source

Réponses:

27

Il est possible d'approcher une solution à ce problème pour la plupart des trajectoires paramétriques. L'idée est la suivante: si vous zoomez assez profondément sur une courbe, vous ne pouvez pas distinguer la courbe elle-même de sa tangente à ce point.

En faisant cette hypothèse, il n'est pas nécessaire de précalculer plus de deux vecteurs (trois pour les courbes de Bézier cubiques, etc. ).

Donc pour une courbe M(t) on calcule son vecteur tangent dMdttMTΔtMTΔtLL÷MT

Application: courbe de Bézier quadratique

Si les points de contrôle de la courbe de Bézier sont , et , la trajectoire peut être exprimée comme:UNEBC

M(t)=(1-t)2UNE+2t(1-t)B+t2C=t2(UNE-2B+C)+t(-2UNE+2B)+UNE

La dérivée est donc:

Mt=t(2UNE-4B+2C)+(-2UNE+2B)

Il vous suffit de stocker les vecteurs et quelque part. Alors, pour un donné , si vous voulez avancer d'une longueur , vous faites:v1=2UNE-4B+2Cv2=-2UNE+2BtL

t=t+Llength(tv1+v2)

Courbes cubiques de Bézier

Le même raisonnement s'applique à une courbe avec quatre points de contrôle , , et :UNEBC

M(t)=(1-t)3UNE+3t(1-t)2B+3t2(1-t)C+t3=t3(-UNE+3B-3C+)+t2(3UNE-6B+3C)+t(-3UNE+3B)+UNE

Le dérivé est:

Mt=t2(-3UNE+9B-9C+3)+t(6UNE-12B+6C)+(-3UNE+3B)

Nous précalculons les trois vecteurs:

v1=3A+9B9C+3Dv2=6A12B+6Cv3=3A+3B

et la formule finale est:

t=t+Llength(t2v1+tv2+v3)

Problèmes de précision

Si vous utilisez une fréquence d'images raisonnable, (qui doit être calculé en fonction de la durée de la trame) sera suffisamment petit pour que l'approximation fonctionne.L

Cependant, vous pouvez rencontrer des inexactitudes dans des cas extrêmes. Si est trop grand, vous pouvez faire le calcul par morceaux, par exemple en utilisant 10 parties:L

for (int i = 0; i < 10; i++)
    t = t + (L / 10) / length(t * v1 + v2);
sam hocevar
la source
1
Salut. Je lis votre réponse, mais je ne comprends pas ce qu'est L. Que voulez-vous dire par "qui devrait être calculé en fonction de la durée de la trame"?
Michael IV
L = longueur du segment de courbe?
Michael IV
L est la longueur de la courbe, c'est-à-dire la distance que vous souhaitez parcourir pendant l'image actuelle.
sam hocevar
OK, je vois maintenant. Et vous pensez que cette approximation est aussi bonne que la technique de fractionnement de courbe de la réponse ci-dessous?
Michael IV
Quand Lest suffisamment petit, cette approximation est en fait toujours plus précise que la réponse ci-dessous, oui. Il utilise également moins de mémoire (car il utilise le dérivé au lieu de stocker toutes les valeurs de points). Lorsque Lcommence à grandir, vous pouvez utiliser la technique que je suggère à la fin.
sam hocevar
6

Vous devez re-paramétrer la courbe. La manière la plus simple de le faire est de calculer les longueurs d'arc de plusieurs segments de la courbe et de les utiliser pour déterminer d'où vous devez échantillonner. Par exemple, peut-être à t = 0,5 (à mi-chemin), vous devez passer s = 0,7 à la courbe pour obtenir la position "à mi-chemin". Pour ce faire, vous devez stocker une liste des longueurs d'arc de divers segments de courbe.

Il existe probablement de meilleures façons, mais voici un code C # très simple que j'ai écrit pour le faire dans mon jeu. Il devrait être facile de porter sur l'objectif C:

public sealed class CurveMap<TCurve> where TCurve : struct, ICurve
{
    private readonly float[] _arcLengths;
    private readonly float _ratio;
    public float length { get; private set; }
    public TCurve curve { get; private set; }
    public bool isSet { get { return !length.isNaN(); } }
    public int resolution { get { return _arcLengths.Length; } }

    public CurveMap(int resolution)
    {
        _arcLengths = new float[resolution];
        _ratio = 1f / resolution;
        length = float.NaN;
    }

    public void set(TCurve c)
    {
        curve = c;
        Vector2 o = c.sample(0);
        float ox = o.X;
        float oy = o.Y;
        float clen = 0;
        int nSamples = _arcLengths.Length;
        for(int i = 0; i < nSamples; i++)
        {
            float t = (i + 1) * _ratio;
            Vector2 p = c.sample(t);
            float dx = ox - p.X;
            float dy = oy - p.Y;
            clen += (dx * dx + dy * dy).sqrt();
            _arcLengths[i] = clen;
            ox = p.X;
            oy = p.Y;
        }
        length = clen;
    }

    public Vector2 sample(float u)
    {
        if(u <= 0) return curve.sample(0);
        if(u >= 1) return curve.sample(1);

        int index = 0;
        int low = 0;
        int high = resolution - 1;
        float target = u * length;
        float found = float.NaN;

        // Binary search to find largest value <= target
        while(low < high)
        {
            index = (low + high) / 2;
            found = _arcLengths[index];
            if (found < target)
                low = index + 1;
            else
                high = index;
        }

        // If the value we found is greater than the target value, retreat
        if (found > target)
            index--;

        if(index < 0) return curve.sample(0);
        if(index >= resolution - 1) return curve.sample(1);

        // Linear interpolation for index
        float min = _arcLengths[index];
        float max = _arcLengths[index + 1];
        Debug.Assert(min <= target && max >= target);
        float interp = (target - min) / (max - min);
        Debug.Assert(interp >= 0 && interp <= 1);
        return curve.sample((index + interp + 1) * _ratio);
    }
}

Edit: Il convient de noter que cela ne vous donnera pas la longueur d'arc exacte, car il est impossible d'obtenir la longueur d'arc d'une courbe cubique. Il ne s'agit que d'estimer la longueur des différents segments. Selon la longueur de la courbe, vous devrez peut-être augmenter la résolution pour l'empêcher de changer de vitesse lorsqu'elle atteint un nouveau segment. J'utilise généralement ~ 100, avec lesquels je n'ai jamais eu de problème.

Robert Fraser
la source
0

Une solution très légère consiste à approximer la vitesse plutôt qu'à approximer la courbe. En fait, cette approche est indépendante de la fonction de courbe et vous permet d'utiliser n'importe quelle courbe exacte au lieu d'utiliser des dérivés ou des approximations.

Voici le code pour C # Unity 3D:

public float speed; // target linear speed

// determine an initial value by checking where speedFactor converges
float speedFactor = speed / 10; 

float targetStepSize = speed / 60f; // divide by fixedUpdate frame rate
float lastStepSize;

void Update ()
{   
    // Take a note of your previous position.
    Vector3 previousPosition = transform.position;

    // Advance on the curve to the next t;
    transform.position = BezierOrOtherCurveFunction(p0, p1, ..., t);

    // Measure your movement length
    lastStepSize = Vector3.Magnitude(transform.position - previousPosition);

    // Accelerate or decelerate according to your latest step size.
    if (lastStepSize < targetStepSize) 
    {
        speedFactor *= 1.1f;
    }
    else
    {
        speedFactor *= 0.9f;
    }

    t += speedFactor * Time.deltaTime;
}

Bien que la solution soit indépendante de la fonction de la courbe, je voulais la noter ici car je cherchais également comment atteindre une vitesse constante sur une courbe de Bézier, puis j'ai trouvé cette solution. Compte tenu de la popularité de la fonction, cela peut être utile ici.

Guney Ozsan
la source
-3

Je ne sais rien de cocos2, mais une courbe de Bézier est une sorte d'équation paramétrique, vous devriez donc être en mesure d'obtenir vos valeurs x et y en termes de temps.

Jebbles
la source
4
Ajoutez un exemple + plus d'explications et ce serait une bonne réponse.
MichaelHouse