¿Cómo determinaría la longitud de un camino?

11

Tengo un juego que requiere que cada jugador se mueva a lo largo de un camino específico. Dibujo el camino usando curvas de Bézier. ¿Cómo puedo determinar la longitud total real (no lineal) de la ruta y la distancia que ha recorrido cada jugador? (La distancia entre el punto de inicio y un punto especificado en la ruta).

ACTUALIZAR:

La ruta se representa en un plano cartesiano (2D).

Valentin Radu
fuente
Su pregunta se responde casi al final de esta respuesta
BlueRaja - Danny Pflughoeft

Respuestas:

7

Como decían las respuestas anteriores, calcular la longitud de una curva de Bezier es difícil ( ¿ imposible ?). Diría que el 100% de los juegos usan una aproximación de la longitud, que casi siempre es lo suficientemente precisa.

Hace unos meses lo implementé usando el enfoque propuesto de dividir la curva en segmentos "pequeños" y agregar su longitud. Hay un ejemplo de una implementación de C ++ aquí .

Dan
fuente
11

Medir la longitud de una curva de Bezier es difícil. Si no le importa una pequeña imprecisión, una solución simple sería aproximar las curvas de Bezier con líneas rectas y calcular la suma de las longitudes de línea. Cuantos más segmentos cree, mejor será la aproximación.

bummzack
fuente
Podría considerar eso, pero ¿cómo puedo determinar cuántos segmentos debo tener y cómo puedo mapear los segmentos para tener su punto de inicio y punto final en mi camino? ¿Esta técnica tiene un nombre? (así que lo busco en Google)
Valentin Radu
Un enfoque simple sería usar una distribución lineal de puntos desde B (0) a B (1) ... muy similar a algo que usaría para trazar la curva. Mira el código fuente en la respuesta de Dan.
bummzack
Agradecería una explicación de la votación negativa, solo para saber qué podría mejorar en mi respuesta ...
bummzack
7

La parametrización de longitud de spline de orden superior (es decir, mayor que 1er orden) debe ser aproximada; no se puede representar directamente, de ahí el hecho de que no es fácil encontrar soluciones directas a esto.

Algunas implementaciones existentes (copiar y pegar código):

Utilizando aproximaciones de Chebyshev , según los autores, la precisión aumenta a medida que aumenta el tamaño de la curva. Mire las p. 7-8 pseudocódigo, el resto es una descripción de otros algoritmos en los que basaron su enfoque que puede ignorar. Una serie de referencias en línea se refieren a este método como uno bueno.

Ver también estos enfoques concisos.

Ingeniero
fuente
5

Esto comenzó como un comentario sobre el comentario en la respuesta de @ bummzack, pero creció demasiado.

¿Cómo puedo determinar cuántos segmentos debo tener?

Hay dos enfoques. El primero es solo el algoritmo estándar para representar una curva de Bézier: los puntos de control forman un cuadro delimitador de la curva, por lo que si todos los puntos de control están dentro del épsilon del segmento de línea desde el punto inicial hasta el punto final, usted se aproxima como una línea; de lo contrario, se subdivide usando el algoritmo de de Casteljau. Epsilon se elige según el error que desee en el resultado final. (Para renderizar es generalmente 0.5 píxeles).

El otro enfoque es un refinamiento de eso usando la aritmética de intervalos. Tome la longitud de la línea de principio a fin como el límite inferior y la suma de las longitudes de las líneas a través de los puntos de control como el límite superior. Nuevamente, subdivida según lo requieran sus requisitos de error final.

Uno normalmente se subdivide en t = 0.5, pero el algoritmo de de Casteljau permite la división en cualquier punto, por lo que si tiene un Bézier cúbico con puntos de control C_0 a C_3 y C_2 está mucho más cerca del segmento de línea entre los puntos finales que C_1, puede encontrar que la división en uno de 1/3 o 2/3 da límites más estrechos. No he trabajado en el álgebra para justificar cuál sería mejor, pero puedes experimentar e informar si lo deseas. Si nada más, quería señalar que la opción está ahí.

Peter Taylor
fuente
3

Se puede calcular la longitud de una curva parametrizada tomando la integral de sqrt ((dx / dt) ² + (dy / dt) ²), donde dx / dt es la derivada del componente x de la curva, y dy / dt es la derivada del componente y de la curva. En el caso de una spline de Bézier, estos dos son iguales, ya que la ecuación se puede extender a cualquier dimensión.

La fórmula para una Bézier-spline cúbica es la siguiente: B (t) = (1 - t³) * P0 + 3 (1 - t) ²t * P1 + 3 (1 - t) t² * P2 + t³ P3 donde P0 a través de P3 son los puntos de control.

Según Wolfram | Alpha, la derivada de esta fórmula es: d (B (t)) / dt = 3 (t (t (P3 - P0) + P2 (2 - 3t) + P1 (3t² - 4t + 1))

Ahora puede volver a poner esto en la ecuación para la longitud de una curva, y calcular la integral de t = 0 a t = 1. Desafortunadamente, Wolfram | Alpha agota el tiempo cuando trato de hacer esto. Sin embargo, puedes hacer integración numérica.

Ruud
fuente