Moviendo naves entre dos planetas a lo largo de un bezier, faltan algunas ecuaciones para la aceleración

OK, ya publiqué esto en math.stackechange.com pero no obtuve ninguna respuesta :(

Primero, aquí hay una imagen de mi problema, la descripción sigue a continuación:

Así que configuré todos los puntos y valores.

La nave comienza a moverse alrededor del planeta izquierdo P1con un S=0.27 Degreesgametick, cuando llega Point Acomienza siguiendo la curva de Bezier hasta llegar Point D, luego viaja alrededor del planeta derecho P2con un S=0.42 Degreestic del juego. La diferencia Ses que el viaje con la misma velocidad de movimiento alrededor de los planetas.

Hasta ahora todo bien, lo puse en marcha, ahora mi problema.

Cuando S P1y S P2difieren mucho, el barco salta entre las dos velocidades cuando llega a su destino, lo que se ve bastante mal. Así que necesito acelerar el barco entre Point Ay Point Dde S P1a S P2.

Lo que me falta son de color púrpura, esos son:

• Una forma de calcular las garrapatas que le toma a la nave moverse a lo largo del bezier considerando la aceleración.

• Y una forma de encontrar una posición en la curva de Bezier basada en T, nuevamente considerando la aceleración.

ATM Calculo la longitud del bezier calculando la distancia entre Nsus puntos. Entonces, lo que creo que necesito es una forma de escalar lo Tque necesito poner en mi cálculo bezier de acuerdo con la aceleración.

OK, tengo todo funcionando, me llevó una eternidad, así que voy a publicar mi solución detallada aquí.
Nota: Todos los ejemplos de código están en JavaScript.

Así que vamos a dividir el problema en las partes básicas:

1. Debe calcular la longitud y los puntos intermedios 0..1en la curva de Bezier

2. Ahora necesita ajustar la escala de su Tpara acelerar el barco de una velocidad a otra

Conseguir el Bezier correcto

Encontrar un código para dibujar una curva de Bezier es fácil, aunque hay varios enfoques diferentes, uno de ellos es el Algoritmo DeCasteljau , pero también puede usar la ecuación para las curvas de Bézier cúbicas:

// Part of a class, a, b, c, d are the four control points of the curve
x: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
           + 3 * ((1 - t) * (1 - t)) * t * this.b.x
           + 3 * (1 - t) * (t * t) * this.c.x
           + (t * t * t) * this.d.x;
},

y: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
           + 3 * ((1 - t) * (1 - t)) * t * this.b.y
           + 3 * (1 - t) * (t * t) * this.c.y
           + (t * t * t) * this.d.y;
}

Con esto, ahora se puede dibujar una curva bezier llamando xy ycon tqué rangos 0 to 1, echemos un vistazo:

Uh ... eso no es realmente una distribución uniforme de los puntos, ¿verdad?
Debido a la naturaleza de la curva de Bézier, los puntos en 0...1son diferentes arc lenghts, por lo que los segmentos cercanos al principio y al final son más largos que los que están cerca del centro de la curva.

Mapeando T de manera uniforme en la curva AKA parametrización de longitud de arco

¿Entonces lo que hay que hacer? Bien en términos simples necesitamos una función para mapear nuestra Ten el tde la curva, por lo que nuestros T 0.25resultados en el tque está en 25%la longitud de la curva.

¿Como hacemos eso? Bueno, nosotros Google ... pero resulta que el término no es tan googleable , y en algún momento llegarás a este PDF . Lo que seguro es una gran lectura, pero en el caso de que ya hayas olvidado todas las cosas de matemáticas que aprendiste en la escuela (o simplemente no te gustan esos símbolos matemáticos) es bastante inútil.

¿Ahora que? Vaya y busque en Google un poco más (lea: 6 horas), y finalmente encontrará un excelente artículo sobre el tema (¡incluyendo fotos bonitas! ^ _ ^ "):
Http://www.planetclegg.com/projects/WarpingTextToSplines.html

Haciendo el código real

En caso de que no pudieras resistirte a descargar esos PDF aunque ya perdiste tu conocimiento matemático hace mucho, mucho tiempo (y te las arreglaste para omitir el excelente enlace del artículo), ahora puedes pensar: "Dios, esto tomará cientos de líneas de código y toneladas de CPU "

No, no lo hará. Porque hacemos lo que hacen todos los programadores, cuando se trata de matemáticas:
simplemente hacemos trampa.

Parametrización de longitud de arco, la forma perezosa

Seamos realistas, no necesitamos precisión infinita en nuestro juego, ¿verdad? Entonces, a menos que estés trabajando en la NASA y estés planeando enviar gente a Marte, no necesitarás una 0.000001 pixelsolución perfecta.

Entonces, ¿cómo Tmapeamos t? Es simple y solo consta de 3 pasos:

1. Calcule Npuntos en la curva usando ty almacene el arc-length(también conocido como la longitud de la curva) en esa posición en una matriz

2. Para asignar Ta t, primero se multiplica Tpor la longitud total de la curva para obtener uy luego buscar en la gama de longitudes para el índice del valor más grande que es menor queu

3. Si obtuvimos un resultado exacto, devuelva el valor de la matriz en ese índice dividido por N, si no interpola un poco entre el punto que encontramos y el siguiente, divida la cosa una vez más por Ny regrese.

¡Eso es todo! Así que ahora echemos un vistazo al código completo:

function Bezier(a, b, c, d) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;

    this.len = 100;
    this.arcLengths = new Array(this.len + 1);
    this.arcLengths[0] = 0;

    var ox = this.x(0), oy = this.y(0), clen = 0;
    for(var i = 1; i <= this.len; i += 1) {
        var x = this.x(i * 0.05), y = this.y(i * 0.05);
        var dx = ox - x, dy = oy - y;        
        clen += Math.sqrt(dx * dx + dy * dy);
        this.arcLengths[i] = clen;
        ox = x, oy = y;
    }
    this.length = clen;    
}

Esto inicializa nuestra nueva curva y calcula el arg-lenghts, también almacena la última de las longitudes como total lengthla curva, el factor clave aquí es this.lencuál es nuestro N. Cuanto más alto, más preciso será el mapeo, ya que una curva del tamaño en la imagen de arriba 100 pointsparece ser suficiente, si solo necesita una buena estimación de longitud, algo así 25ya hará el trabajo con solo 1 píxel de distancia en nuestro ejemplo, pero luego tendrá un mapeo menos preciso que dará como resultado una distribución no tan uniforme de Tcuando se asigna a t.

Bezier.prototype = {
    map: function(u) {
        var targetLength = u * this.arcLengths[this.len];
        var low = 0, high = this.len, index = 0;
        while (low < high) {
            index = low + (((high - low) / 2) | 0);
            if (this.arcLengths[index] < targetLength) {
                low = index + 1;

            } else {
                high = index;
            }
        }
        if (this.arcLengths[index] > targetLength) {
            index--;
        }

        var lengthBefore = this.arcLengths[index];
        if (lengthBefore === targetLength) {
            return index / this.len;

        } else {
            return (index + (targetLength - lengthBefore) / (this.arcLengths[index + 1] - lengthBefore)) / this.len;
        }
    },

    mx: function (u) {
        return this.x(this.map(u));
    },

    my: function (u) {
        return this.y(this.map(u));
    },

El código de mapeo real, primero hacemos un simple binary searchen nuestras longitudes almacenadas para encontrar la longitud más grande que sea más pequeña targetLength, luego simplemente regresamos o hacemos la interpolación y regresamos.

    x: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
               + 3 * ((1 - t) * (1 - t)) * t * this.b.x
               + 3 * (1 - t) * (t * t) * this.c.x
               + (t * t * t) * this.d.x;
    },

    y: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
               + 3 * ((1 - t) * (1 - t)) * t * this.b.y
               + 3 * (1 - t) * (t * t) * this.c.y
               + (t * t * t) * this.d.y;
    }
};

De nuevo, esto se calcula ten la curva.

Tiempo para resultados

Por ahora usando mxy myobtienes una distribución uniforme Ten la curva :)

¿No fue difícil, verdad? Una vez más, resulta que una solución simple (aunque no perfecta) será suficiente para un juego.

En caso de que quiera ver el código completo, hay un Gist disponible:
https://gist.github.com/670236

Finalmente, acelerando las naves

Entonces, todo lo que queda ahora es acelerar las naves a lo largo de su camino, mapeando la posición en la Tque luego usamos para encontrar la tcurva.

Primero necesitamos dos de las ecuaciones de movimiento , a saber, ut + 1/2at²y(v - u) / t

En el código real que se vería así:

startSpeed = getStartingSpeedInPixels() // Note: pixels
endSpeed = getFinalSpeedInPixels() // Note: pixels
acceleration = (endSpeed - startSpeed) // since we scale to 0...1 we can leave out the division by 1 here
position = 0.5 * acceleration * t * t + startSpeed * t;

Luego reducimos eso a 0...1:

maxPosition = 0.5 * acceleration + startSpeed;
newT = 1 / maxPosition * position;

Y ahí tienes, las naves ahora se mueven suavemente a lo largo del camino.

En caso de que no funcione ...

Cuando estás leyendo esto, todo funciona bien, pero inicialmente tuve algunos problemas con la parte de aceleración, cuando le expliqué el problema a alguien en la sala de juegos gamedev encontré el error final en mi pensamiento.

En caso de que aún no se haya olvidado de la imagen en la pregunta original, menciono sallí, resulta que ses la velocidad en grados , pero las naves se mueven a lo largo del camino en píxeles y me había olvidado de ese hecho. Entonces, lo que necesitaba hacer en este caso era convertir el desplazamiento en grados en un desplazamiento en píxeles, resulta que esto es bastante fácil:

function rotationToMovement(planetSize, rotationSpeed) {
    var r = shipAngle * Math.PI / 180;
    var rr = (shipAngle + rotationSpeed) * Math.PI / 180;
    var orbit = planetSize + shipOrbit;
    var dx = Math.cos(r) * orbit - Math.cos(rr) * orbit;
    var dy = Math.sin(r) * orbit - Math.sin(rr) * orbit;
    return Math.sqrt(dx * dx + dy * dy);
};

¡Y eso es todo! Gracias por leer ;)

El problema es que un barco no tomaría esa trayectoria naturalmente. Entonces, incluso si funciona perfectamente, todavía no se verá bien.

Si quieres simular la transición suave entre planetas, te sugiero que la modeles. Las ecuaciones son muy simples ya que solo tienes dos fuerzas significativas: la gravedad y el empuje.

Solo necesita configurar sus constantes: Masa de P1, P2, enviar

Con cada tick del juego (tiempo: t) estás haciendo 3 cosas

1. Calcule la gravedad de p1 en el barco y p2 en el barco, agregue los vectores resultantes al vector de empuje.

2. Calcule su nueva velocidad en función de su nueva aceleración del paso 1

3. Mueve la nave según tu nueva velocidad

Puede parecer mucho trabajo, pero se puede hacer en una docena de líneas de código y se verá muy natural.

Si necesita ayuda con la física, hágamelo saber.

Encontré un excelente artículo que explica una posible solución a este problema con un ejemplo de código escrito en javascript. Funciona "empujando el valor t" en la dirección correcta.

En cambio, podemos usar el hecho de que la longitud promedio de la pierna d_avg para cualquier distribución de puntos es casi idéntica a la longitud de las piernas que producirían los puntos espaciados uniformemente (esta similitud aumenta a medida que n aumenta). Si calculamos la diferencia d_err entre las longitudes de pierna reales d y la longitud de pierna promedio d_avg, entonces el parámetro de tiempo t correspondiente a cada punto puede ser empujado para reducir esta diferencia.

Esta pregunta ya tiene muchas respuestas interesantes, pero encontré que vale la pena notar esta solución.

Gracias por su excelente página que describe cómo resolvió este problema. Hice algo algo diferente a usted en un detalle, ya que estaba muy limitado en la memoria: no construyo una matriz, o tengo que buscar el 'segmento' correcto con una búsqueda binaria. Esto se debe a que siempre sé que me estoy moviendo de un extremo de mi curva de Bezier a otro: por lo tanto, simplemente recuerdo el segmento 'actual', y si veo que saldré de los límites de ese segmento para calcular mi próximo posición, calculo el siguiente (o anterior) segmento (basado en la dirección de desplazamiento). Esto funciona bastante bien para mi aplicación. La única falla que tuve que resolver fue que, en algunas curvas, el tamaño de los segmentos era tan pequeño que mi siguiente argumento era, en raras ocasiones, más de un segmento por delante del actual, por lo que en lugar de simplemente ir al '

No sé si esto tiene sentido, pero ciertamente me ayudó.

Ese tipo de modelado es extraño y puede producir resultados ilógicos extraños. Especialmente si la velocidad de los planetas de partida es realmente lenta.

Modele las naves con un poder de empuje.

Cuando las naves estén en su última órbita en el planeta inicial, acelere a toda velocidad.

Cuando la nave se encuentre dentro de una cierta distancia, utilice el empuje inverso para reducir la velocidad de la nave a la velocidad de órbita del planeta objetivo.

Editar: Realice la simulación completa de una vez cuando un nodo está a punto de abandonar la órbita. envíe todos los datos o envíe solo unos pocos vectores de movimiento a intervalos e interpole entre ellos.

Si lo entiendo correctamente, su problema es demasiado limitado.

Creo que desea que la nave espacial viaje a lo largo de un camino especificado entre las órbitas en algún momento t , y también desea que acelere de la velocidad s1 a la velocidad s2 al mismo tiempo t . Desafortunadamente, no puede (en general) encontrar una aceleración que satisfaga ambas restricciones simultáneamente.

Tendrás que relajar un poco tu problema para que sea solucionable.

Encontré esta respuesta porque estoy buscando distribuir puntos de manera uniforme a lo largo de una ruta svg que utiliza una curva bezier.

A pesar de que MDN dice que está en desuso, puede usar el path.getPointAtLengthpara obtener el resultado correcto. https://developer.mozilla.org/en-US/docs/Web/API/SVGPathElement/getPointAtLength

Actualmente funciona en Chrome / Safari / Firefox, y debería funcionar también en IE / Edge, pero no verifiqué esos 2.

El problema con la solución aceptada

Como Bezier es una función exponencial , esperamos diferentes tasas de avance en diferentes áreas de la curva.

Debido a que la solución de Ivo se interpola linealmente entre estas muestras exponenciales iniciales , las inexactitudes estarán muy sesgadas hacia los extremos / medio de la curva (típicamente cúbica) donde esos deltas son mayores; por lo tanto, a menos que la frecuencia de muestreo Naumente enormemente, como sugiere, los errores son aparentes y, en algún nivel de zoom, siempre serán evidentes para un determinado N, es decir, el sesgo es intrínseco para ese algoritmo. No es bueno, por ejemplo, para gráficos basados ​​en vectores donde el zoom puede ser ilimitado.

Contrarrestar el sesgo mediante muestreo guiado

Una solución alternativa es para volver a asignar linealmente distancea tdespués de la lucha contra el sesgo natural que la función de Bezier produce.

Asumiendo que esto es lo que idealmente queremos:

curve length = 10

t      distance
0.2    2
0.4    4
0.6    6
0.8    8
1.0    10

pero esto es lo que obtenemos de la función de posición de Bezier:

t      distance
0.2    0.12
0.4    1.22
0.6    2.45
0.8    5.81
1.0    10.00

Al observar las Nmuestras tomadas, podemos ver dónde los deltas de distancia son mayores y volver a muestrear ("dividir") a mitad de camino entre las dos distancias adyacentes, aumentando Nen 1. Por ejemplo, dividiendo en t=0.9(que está a mitad de camino en el delta más grande), podríamos obtener:

0.8    5.81
0.9    7.39
1.0    10.00

Repetimos este proceso para el siguiente intervalo de distancia más grande hasta que el delta máximo entre dos distancias cualesquiera en todo el conjunto esté por debajo de algo minDistanceDelta, y más específicamente, menos que epsilonlejos de distancias específicas que queremos mapear a pasos de t; entonces podemos asignar linealmente nuestros tpasos deseados a los distances correspondientes . Esto produce una tabla hash / mapa a la que puede acceder de forma económica y cuyos valores puede alternar, en tiempo de ejecución, sin sesgos.

A medida que el conjunto crece N, el costo para repetir esto aumenta, por lo que idealmente haga esto como un preproceso. Cada vez que Naumente, agregue los dos nuevos intervalos resultantes a una intervalscolección mientras elimina el antiguo intervalo único que reemplazaron. Esta es la estructura en la que trabaja para encontrar el siguiente intervalo más grande para dividir en dos. Mantenerse intervalsordenado por distancia hace que las cosas sean más fáciles, ya que puede sacar el siguiente elemento de trabajo del final, dividirlo, etc.

Terminamos con algo como lo que idealmente queríamos:

epsilon: 0.01

t            distance
0.200417     2.00417
0.3998132    3.9998132
0.600703     6.00703
0.800001     8.00001
0.9995309    9.995309

Dado que estamos haciendo conjeturas en cada paso, no obtendremos exactamente las distancias exactas 2, 4etc. que queríamos, pero a través de la repetición de iteración estos se acercan lo suficiente a los valores de distancia deseados para que pueda asignar sus tpasos con bastante precisión, eliminando el sesgo debido al muestreo casi equidistante.

Luego puede recuperar t=0.5, por ejemplo , como lo hace Ivo en su respuesta, es decir, interpolando entre los dos valores más cercanos arriba ( 3.9998132y 6.00703).

Conclusión

Para la mayoría de los casos, la solución de Ivo funcionará bien, pero para los casos en que se debe evitar el sesgo a toda costa, asegúrese de que sus correos electrónicos distanceestén tan dispersos como sea posible y luego se asignen linealmente t.

Tenga en cuenta que la división podría realizarse estocásticamente en lugar de dividirse por la mitad cada vez, por ejemplo, podríamos haber dividido ese primer intervalo de ejemplo en t=0.827lugar de en t=0.9.