Mova um objeto uniformemente ao longo de uma curva

No processo de desenvolvimento de um jogo em categorias de gênero completamente diferentes, pode ser necessário "lançar" qualquer objeto do jogo ao longo de uma curva suave a uma velocidade constante ou controlada, seja um caminhão movendo-se da cidade A para a cidade B, um míssil disparado ao longo de uma trajetória astuta ou um avião inimigo executar uma manobra deitada.



Provavelmente, todo mundo relacionado ao tópico conhece ou pelo menos ouviu falar sobre curvas de Bézier, B-splines, Hermite splines e outras interpolações e splines de suavização e sugeririam absolutamente corretamente o uso de uma delas na situação descrita, mas nem tudo é tão simples como gostaríamos.



No nosso caso, uma spline é uma função que exibe um conjunto de parâmetros de entrada (pontos de controle) e o valor de um argumento $$$t$(geralmente assumindo valores de 0 a 1) para um ponto em um plano ou no espaço. A curva resultante é o conjunto de valores da função spline para$$$t\in [0,1]$...



Como exemplo, considere a curva de Bézier cúbica , que é dada pela seguinte equação:







Curva Cúbica de Bézier



A figura mostra duas curvas cúbicas de Bézier, definidas por quatro pontos (a curva passa por dois deles, os dois restantes definem a curvatura).





Animação de exibição do parâmetro t para um ponto de curva



A fim de construir uma rota mais complexa e variável a partir das seções da curva, elas podem ser conectadas em uma cadeia, deixando um elo de ponto comum:





Spline por partes Nós



descobrimos a tarefa e parametrização da rota, agora voltamos à questão principal. Para que nosso plano condicional se mova ao longo da rota a uma velocidade constante, precisamos a qualquer momento ser capazes de calcular um ponto na curva, dependendo da distância percorrida ao longo dessa curva.$$$s(len)$, embora tenha apenas a capacidade de calcular a posição de um ponto na curva a partir do valor do parâmetro $$$t$ (função $$$y(t)$) É nesta fase que começam as dificuldades.



Meu primeiro pensamento foi fazer um mapeamento linear$$$len\in [0,Length]\Rightarrow t\in [0,1]$ e calcular $$$y(t)$do valor resultante - fácil, computacionalmente barato, em geral, o que você precisa.







O problema com este método é imediatamente óbvio - na verdade, a distância percorrida$$$s$ depende de $$$t$ não linearmente, e para estarmos convencidos disso, basta organizar ao longo da rota uniformemente distribuída por valor $$$t$pontos: pontos





"uniformemente" distribuídos ao longo do trajeto



A aeronave irá desacelerar em alguns trechos e acelerar em outros, o que torna este método de parametrização da curva completamente inaplicável para a solução do problema descrito (o avião foi escolhido exclusivamente como exemplo ilustrativo e o objetivo de descrever seu movimento de forma fisicamente correta não foi perseguido ):





Visualização da parametrização incorreta da curva



Após consultar o mecanismo de busca, no stackoverflow e no youtube , encontrei uma segunda forma de calcular$$$s(len)=g(t)$, a saber, a representação da curva na forma de uma função linear por partes (calculando um conjunto de pontos equidistantes uns dos outros ao longo da curva):





Representação da curva como uma spline linear por partes



Este procedimento é iterativo: um pequeno passo é dado$$$t$, nós nos movemos ao longo de uma curva com ele, somando a distância percorrida como o comprimento de uma spline linear por partes até que uma determinada distância seja coberta, após o que o ponto é lembrado e o processo é retomado.





E, ao que parece, o problema está resolvido, porque você pode dividir a rota em vários segmentos e desfrutar de como o objeto se move de maneira suave e constante, já que calcular um ponto em uma função linear por partes é uma questão simples e rápida. Mas essa abordagem também tem desvantagens bastante óbvias que me assombravam - um procedimento bastante caro para alterar a etapa de partição ou geometria da curva e a necessidade de encontrar um equilíbrio entre precisão (mais consumo de memória) e economia de memória (a rota "interrompida" se torna mais perceptível).



Como resultado, continuei procurando e encontrei um excelente artigo "Movendo-se ao longo de uma curva com velocidade especificada" , com base no qual se baseiam mais raciocínios.



O valor da velocidade pode ser calculado como$$$\sigma (t)=|V(t)|=|\frac{dX}{dt}|$Onde $$$X(t)$- função spline. Para resolver o problema, você precisa encontrar a função$$$Y(t)=X(s)$Onde $$$s$ - o comprimento do arco do ponto inicial ao desejado, e esta expressão estabelece a relação entre $$$t$ e $$$s$...



Usando a substituição de variável de diferenciação, podemos escrever

$$

Levando em consideração que a velocidade é uma quantidade não negativa, obtemos

$$

Porque $$$|\frac{dX}{ds}|=1$ pela condição de que o módulo do vetor de velocidade permanece inalterado (em geral, $$$|\frac{dX}{ds}|$não é igual a um, mas a uma constante, mas para simplificar os cálculos, tomaremos essa constante igual a um).



Agora temos a proporção entre$$$t$ e $$$s$ explicitamente:

$$

de onde o comprimento total da curva $$$L$é obviamente calculado como $$$g(1)$... Usando a fórmula resultante, é possível, tendo o valor do argumento$$$t$, calcule o comprimento do arco até o ponto em que este valor é $$$t$é exibido.



Estamos interessados ​​na operação reversa, ou seja, calcular o valor do argumento$$$t$ ao longo de um determinado comprimento de arco $$$s$:

$$

Uma vez que não existe uma maneira analítica geral de encontrar a função inversa, você terá que procurar uma solução numérica. Nós denotamos$$$F(t)=g(t)-s.$ Para um dado $$$s$, é necessário encontrar esse valor $$$t$em qual $$$F(t)=0$... Assim, a tarefa se tornou a tarefa de encontrar a raiz da equação, com a qual o método de Newton pode lidar perfeitamente.



O método forma uma sequência de aproximações do formulário

$$

Onde

$$

Calcular $$$F(t)$ precisa calcular $$$g(t)$, cujo cálculo, por sua vez, requer integração numérica.



Escolha$$$t_0=\frac{s}{L}$como uma aproximação inicial agora parece razoável (lembre-se da primeira abordagem para resolver o problema).



Em seguida, iteramos usando o método de Newton até que o erro da solução se torne aceitável ou o número de iterações feitas seja proibitivamente grande.



Existe um problema potencial com o uso do método padrão de Newton. Função$$$F(t)$ - não decrescente, pois sua derivada $$$F^{\prime }(t)=|dY/dt|$não é negativo. Se a segunda derivada$$$F^{″}(t)>0$, então a função é chamada de convexa e o método de Newton nela convergirá para a raiz. No entanto, em nosso caso,$$$F^{″}(t)$ pode acabar sendo negativo, devido ao qual o método de Newton pode convergir fora do intervalo de definição $$$t\in [0,1]$... O autor do artigo propõe o uso de uma modificação do método de Newton, que, se o resultado da próxima iteração pelo método de Newton não cair no intervalo atual que delimita a raiz, selecione o meio do intervalo ( método da dicotomia ). Independentemente do resultado do cálculo na iteração atual, o intervalo é reduzido, o que significa que o método converge para a raiz.



Resta escolher o método de integração numérica - usei as quadraturas do método de Gauss , pois ele fornece um resultado bastante preciso a baixo custo.







A seguir, você pode ajustar o erro do método de Newton, escolher um método mais preciso de integração numérica, mas o problema, de fato, está resolvido - um algoritmo para calcular o argumento foi construído $$$t$spline para um determinado comprimento de arco. Para combinar várias seções de curvas em uma e escrever um procedimento de cálculo generalizado$$$s(t)$você pode armazenar os comprimentos de todos os segmentos e pré-calcular o índice do segmento onde deseja realizar um procedimento iterativo usando o método de Newton modificado.





Pontos uniformemente distribuídos ao longo do caminho





Agora o plano se move uniformemente.



Assim, consideramos várias maneiras de parametrizar o spline em relação à distância percorrida, no artigo que usei como fonte, como opção, o autor sugere resolver numericamente a equação diferencial, mas, segundo sua própria observação, prefere o método modificado Newton:

Eu prefiro a abordagem do método de Newton porque geralmente t pode ser calculado mais rápido do que com solucionadores de equações diferenciais.

Como conclusão, darei uma tabela de tempo para calcular a posição de um ponto na curva mostrada nas capturas de tela em um thread em um processador i5-9600K:

Acredito que essa velocidade de cálculos torna possível usá-los em vários jogos e simulações. Eu ficaria feliz em esclarecer e criticar em sua essência nos comentários.