Déplacer un objet uniformément le long d'une courbe

Dans le processus de développement d'un jeu dans des catégories de genre complètement différentes, il peut être nécessaire de «lancer» un objet de jeu le long d'une courbe douce à une vitesse constante ou contrôlée, que ce soit un camion se déplaçant de la ville A à la ville B, un missile tiré le long d'une trajectoire rusée ou un avion ennemi effectuer une manœuvre fixe.



Probablement, tous ceux qui sont liés au sujet connaissent ou du moins ont entendu parler des courbes de Bézier, des B-splines, des splines Hermite et d'autres splines d'interpolation et de lissage et suggéreraient absolument d'utiliser l'une d'entre elles dans la situation décrite, mais tout n'est pas si simple comme on voudrait.



Dans notre cas, une spline est une fonction qui affiche un ensemble de paramètres d'entrée (points de contrôle) et la valeur de l'argument $$$t$ (prenant généralement des valeurs de 0 à 1) à un point sur un plan ou dans l'espace. La courbe résultante est l'ensemble des valeurs de la fonction spline pour$$$t\in[0,1]$ .



À titre d'exemple, considérons lacourbe de Béziercubique, qui est donnée par l'équation suivante:







Courbe de Bézier cubique



La figure montre deux courbes de Bézier cubiques définies par quatre points (la courbe passe par deux d'entre eux, les deux autres définissent la courbure).





Animation de l'affichage du paramètre t sur un point de la courbe



Afin de construire un itinéraire plus complexe et variable à partir des sections de courbe, elles peuvent être connectées en une chaîne, laissant un point-lien commun:





Spline par morceaux Nous avons



compris la tâche et le paramétrage de l'itinéraire, nous passons maintenant à la question principale. Pour que notre avion conventionnel se déplace le long de la route à vitesse constante, nous devons à tout moment être en mesure de calculer un point sur la courbe en fonction de la distance parcourue le long de cette courbe.$$$s(len)$ , tout en n'ayant que la possibilité de calculer la position d'un point sur la courbe à partir de la valeur du paramètre$$$t$ (fonction$$$y(t)$ ). C'est à ce stade que les difficultés commencent.



Ma première pensée a été de faire une cartographie linéaire$$$len\in[0, Length] \Rightarrow t\in[0,1]$ et calculer$$$y(t)$ partir de la valeur résultante - facile, peu coûteuse en calcul, en général, ce dont vous avez besoin.







Le problème avec cette méthode est immédiatement évident - en fait, la distance parcourue$$$s$ dépend de$$$t$ non linéaire, et pour s'en assurer, il suffit de disposer le long de l'itinéraire uniformément réparti$$$t$ points: points





répartis «uniformément» le long du trajet



Le plan ralentira dans certaines sections et accélérera dans d'autres, ce qui rend cette méthode de paramétrage de la courbe totalement inapplicable pour résoudre le problème décrit (le plan est choisi exclusivement comme exemple illustratif et le but de décrire son mouvement de manière physiquement correcte n'est a été poursuivi):





Visualiser le mauvais paramétrage de la courbe



Après avoir consulté le moteur de recherche, surstackoverflowetyoutube, j'ai découvert une deuxième façon de calculer$$$s(len) = g(t)$ , à savoir la représentation de la courbe sous forme de fonction linéaire par morceaux (calcul d'un ensemble de points équidistants les uns des autres le long de la courbe):





Représentation de la courbe comme une spline linéaire par morceaux



Cette procédure est itérative: un petit pas est fait$$$t$ , nous nous déplaçons le long d'une courbe avec elle, en additionnant la distance parcourue comme la longueur d'une spline linéaire par morceaux jusqu'à ce que la distance spécifiée soit couverte, après quoi le point est mémorisé, et le processus reprend.





Et, semble-t-il, le problème est résolu, car vous pouvez diviser l'itinéraire en plusieurs segments et apprécier la fluidité et la mesure avec laquelle l'objet se déplace, car le calcul d'un point sur une fonction linéaire par morceaux est une question simple et rapide. Mais cette approche a aussi des inconvénients assez évidents qui m'ont dérangé - une procédure assez coûteuse pour changer le pas de partition ou la géométrie de la courbe et la nécessité de trouver un équilibre entre précision (plus de consommation de mémoire) et économies de mémoire (l'itinéraire "cassé" devient plus perceptible).



En conséquence, j'ai continué à chercher et suis tombé sur un excellent article "Déplacement le long d'une courbe avec une vitesse spécifiée" , sur la base duquel un raisonnement supplémentaire est basé.



La valeur de la vitesse peut être calculée comme$$$\sigma(t) = |V(t)|=|\frac{dX}{dt}|$où$$$X(t)$ est une fonction spline. Pour résoudre le problème, vous devez trouver la fonction$$$Y(t)=X(s)$ , où$$$s$ - la longueur de l'arc entre le point de départ et celui souhaité, et cette expression définit la relation entre$$$t$ et$$$s$ .



En utilisant la substitution de variable de différenciation, nous pouvons écrire

$$

$$\frac{dY}{dt}=\frac{dX}{ds}\frac{ds}{dt}.$$

En tenant compte du fait que la vitesse est une quantité non négative, on obtient

$$

$$|\frac{dY}{dt}|=|\frac{dX}{ds}||\frac{ds}{dt}|=\frac{ds}{dt},$$

parce que $$$|\frac{dX}{ds}| = 1$à la condition que le module du vecteur vitesse reste inchangé (en général,$$$|\frac{dX}{ds}|$n'est pas égal à un, mais à une constante, mais pour la simplicité des calculs, nous prendrons cette constante égale à un).



Maintenant, nous obtenons le rapport entre$$$t$ et$$$s$ explicitement:

$$

$$s=g(t)=\int_{0}^{t}|\frac{dY(\tau)}{dt}|d\tau,$$

d'où la longueur totale de la courbe $$$L$ est évidemment calculé comme$$$g(1)$ . En utilisant la formule résultante, il est possible, ayant la valeur de l'argument$$$t$ , calcule la longueur de l'arc jusqu'au point où cette valeur$$$t$est affiché.



Nous nous intéressons à l'opération inverse, c'est-à-dire au calcul de la valeur de l'argument$$$t$ le long d'une longueur d'arc donnée $$$s$:

$$

$$t=g^{-1}(s).$$

Puisqu'il n'y a pas de méthode analytique générale pour trouver la fonction inverse, vous devrez rechercher une solution numérique. Nous dénotons$$$F(t)=g(t)-s.$ Pour un donné $$$s$, il est nécessaire de trouver une telle valeur $$$t$auquel $$$F(t)=0$... Ainsi, la tâche s'est transformée en tâche de trouver la racine de l'équation, que la méthode de Newton peut parfaitement gérer.



La méthode forme une suite d'approximations de la forme

$$

$$t_{i+1}=t_i-\frac{F(t_i)}{F'(t_i)},$$

Où

$$

$$F'(t)=\frac{dF}{dt}=\frac{dg}{dt}=|\frac{dY}{dt}|.$$

Calculer $$$F(t)$ besoin de calculer $$$g(t)$, dont le calcul nécessite à son tour une intégration numérique.



Choix$$$t_0=\frac{s}{L}$comme une première approximation semble maintenant raisonnable (rappelez-vous la première approche pour résoudre le problème).



Ensuite, nous itérons en utilisant la méthode de Newton jusqu'à ce que l'erreur de solution devienne acceptable ou que le nombre d'itérations effectuées soit prohibitif.



Il y a un problème potentiel avec l'utilisation de la méthode standard de Newton. Une fonction$$$F(t)$ - non décroissant, puisque son dérivé $$$F'(t)=|dY/dt|$est non négatif. Si la seconde dérivée$$$F''(t)>0$, alors la fonction est appelée convexe et la méthode de Newton dessus est garantie de converger vers la racine. Cependant, dans notre cas,$$$F''(t)$ peut s'avérer négatif, en raison de laquelle la méthode de Newton peut converger en dehors de la plage de définition $$$t\in[0,1]$... L'auteur de l'article propose d'utiliser une modification de la méthode de Newton, qui, si le résultat de l'itération suivante par la méthode de Newton ne tombe pas dans l'intervalle courant délimitant la racine, sélectionne à la place le milieu de l'intervalle ( méthode de la dichotomie ). Quel que soit le résultat du calcul à l'itération actuelle, la plage est réduite, ce qui signifie que la méthode converge vers la racine.



Reste à choisir la méthode d'intégration numérique - j'ai utilisé les quadratures de la méthode de Gauss , car elle fournit un résultat assez précis à faible coût.







Ensuite, vous pouvez ajuster l'erreur de la méthode de Newton, choisir une méthode d'intégration numérique plus précise, mais le problème, en fait, est résolu - un algorithme de calcul de l'argument a été construit $$$t$spline pour une longueur d'arc donnée. Pour combiner plusieurs sections de courbes en une seule et écrire une procédure de calcul généralisée$$$s(t)$vous pouvez stocker les longueurs de tous les segments et pré-calculer l'index du segment où vous souhaitez exécuter une procédure itérative à l'aide de la méthode Newton modifiée.





Points uniformément répartis le long de la trajectoire





Maintenant le plan se déplace uniformément



Ainsi, nous avons envisagé plusieurs façons de paramétrer la spline par rapport à la distance parcourue, dans l' article que j'ai utilisé comme source, en option, l'auteur propose de résoudre l'équation différentielle numériquement, mais, selon sa propre remarque, préfère la méthode modifiée Newton:

Je préfère l'approche de la méthode de Newton car généralement t peut être calculé plus rapidement qu'avec des solveurs d'équations différentielles.

En conclusion, je vais donner un tableau de temps pour calculer la position d'un point sur la courbe montrée dans les captures d'écran dans un thread sur un processeur i5-9600K:

Je crois qu'une telle rapidité de calcul permet de les utiliser dans divers jeux et simulations. Je serais heureux de clarifier et de critiquer essentiellement dans les commentaires.