Longitud de arco de las curvas de Bézier

Question

Véase también: respuestas con código en GameDev.SE

¿Cómo puedo averiguar la longitud de arco de una curva de Bézier? Por ejemplo, la longitud de arco de una curva lineal de Bézier es simplemente:

$$s = \sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}$$

¿Pero qué pasa con las curvas de Bézier cuadráticas, cúbicas o de grado n?

$$\mathbf{B}(t) = \sum_{i=0}^n {n\choose i}(1-t)^{n-i}t^i\mathbf{P}_i$$

Answer 1

He mostrado en los comentarios cómo conseguir Mathematica para generar la función arclength para una curva de Bézier cuadrática; para esta respuesta daré una derivación explícita.

Consideremos la parametrización

$$\begin{align*}x&=(1-u)^2 x_1+2u(1-u) x_2+u^2 x_3 \\ y&=(1-u)^2 y_1+2u(1-u) y_2+u^2 y_3\end{align*}$$

Dejar $\Delta x_i=x_{i+1}-x_i$ y de forma similar para $\Delta y_i$ la integral de longitud de arco correspondiente a esta parametrización es

$\displaystyle \scriptsize 2\int\sqrt{\Delta x_1^2+\Delta y_1^2+2\left(\Delta x_1\left(\Delta x_2-\Delta x_1\right)+\Delta y_1\left(\Delta y_2-\Delta y_1\right)\right)u+\left(\left(\Delta x_2-\Delta x_1\right)^2+\left(\Delta y_2-\Delta y_1\right)^2\right)u^2}\mathrm du$

Dejamos que $c=\Delta x_1^2+\Delta y_1^2$ , $b=\Delta x_1\left(\Delta x_2-\Delta x_1\right)+\Delta y_1\left(\Delta y_2-\Delta y_1\right)$ y $a=\left(\Delta x_2-\Delta x_1\right)^2+\left(\Delta y_2-\Delta y_1\right)^2$ para simplificar aún más las cosas.

Consideremos ahora la integral

$$2\int \sqrt{c+2bu+au^2}\mathrm du$$

Al completar el cuadrado se obtiene

$$2\sqrt{a}\int \sqrt{\left(u+\frac{b}{a}\right)^2+\frac{ac-b^2}{a^2}}\mathrm du$$

Omitiendo los detalles (pero vea aquí para saber cómo se puede obtener la respuesta), la integral se evalúa como

$$\sqrt{a}\left(\left(u+\frac{b}{a}\right)\sqrt{\left(u+\frac{b}{a}\right)^2+\frac{ac-b^2}{a^2}}+\left(\frac{ac-b^2}{a^2}\right)\mathrm{arsinh}\left(\frac{au+b}{\sqrt{ac-b^2}}\right)\right)$$

o

$$\left(u+\frac{b}{a}\right)\sqrt{c+2bu+au^2}+\left(\frac{ac-b^2}{a^{3/2}}\right)\mathrm{arsinh}\left(\frac{au+b}{\sqrt{ac-b^2}}\right)$$

Como he mencionado en los comentarios, la forma cerrada para el caso cuadrático es bastante complicada (aún más para el caso cúbico), y es mejor utilizar la cuadratura numérica para calcular la arclitud.

Answer 2

Consulte estos documentos:

• Parametrización de la longitud de arco aproximada , en SIBGRAPI 1996.

• Muestreo adaptativo de curvas paramétricas en Graphics Gems V, 1995.

• Cálculo de la longitud de arco de las curvas paramétricas IEEE Computer Graphics and Applications, 1990.

• Métodos basados en puntos para estimar la longitud de una curva paramétrica Journal of Computational and Applied Mathematics, 2006.

Answer 3

Véase también "Adaptive subdivision and the length and energy of Bézier curves" de Jens Gravesen en Computational Geometry Volume 8, Issue 1, June 1997, Pages 13-31.

La idea es que la longitud de arco de la curva de Bézier se encuentra entre la longitud de cuerda (distancia del primer al último punto de control) y la longitud de polígono (distancia entre cada par sucesivo de puntos de control). La subdivisión repetida de la curva reduce el intervalo de la longitud de arco, hasta una precisión cercana arbitraria.

Answer 4

Sospecho que la respuesta que busca difiere de la pregunta que ha formulado. Permítame considerar algunos escenarios en 3-D (0un puesto cada uno).

ESCENARIO #1: Cargas un programa 3D como Blender, y añades una curva Bezier a la escena. Hay tiradores de control, y la curva se aproxima por segmentos. Aumenta la resolución de la curva, y la aproximación es cada vez mejor. Aleja el zoom de la curva, y en algún momento la resolución de tu curva excederá la resolución mostrada. Estaría bien eliminar los puntos innecesarios.

Si te refieres a esto, estás de suerte:
La curva dibujada es ya una aproximación lineal. Aumentar y disminuir la resolución no tiene ningún efecto sobre el orden de la curva. Construyamos una curva de este tipo.

Sea el orden 3, y los puntos dados sean A,B,C,D. y sea la curva 3D dada por
$(1a)\;\;\;\;\; {\bf x}(t) = A + 3 P t + 3Q t^2 + R t^3, \;\;\;\;\; 0\le t \le 1$
${\small \hspace{60pt} P = (B\!-\!A),\;\; Q = (C\!-\!2B\!+\!A),\;\; R= (D\!-\!3C\!+\!3B\!-\!A)}$
o, inmediatamente en los puntos dados
$(1b)\;\;\;\;\; {\bf x}(t) = A(1\!-\!t)^3 + 3 Bt (1\!-\!t)^2 + 3C t^2 (1\!-\!t) + D t^3 \;\;\;\;\; 0\le t \le 1$

Los puntos A y D son los extremos de la curva, y si unimos los segmentos AB, CD, encontraremos que son los conocidos asideros. Consideremos ahora dos tareas

1. Cambia la resolución. ¿Cómo se dibuja esa curva? Digamos que queremos n segmentos. Entonces necesitaremos n+1 valores t:
$\;\;\;\;\;\{t_k\} = 0, \tfrac{1}{n}, \tfrac{2}{n}, ..., \tfrac{n}{n} = 1,\;\;$ o
$\;\;\;\;\;\{t_k\} = {k/n}, \;\;\;k = 0, \ldots, n $
A continuación, evalúe (1a) o (1b) en los n valores t. Únelos con líneas rectas. Esta curva es tu aproximación. La distancia entre puntos es la distancia en línea recta.

Ahora vamos a pensar en esto. Aunque no sea esto lo que quieres decir, ¿estás seguro de que quieres la longitud del arco? Tengo dos puntos en el espacio, A y B. Sabré si dos puntos se superponen en mi pantalla comprobando su distancia euclidiana ordinaria. La distancia entre ellos a lo largo de la curva no sólo es mucho más difícil de calcular, sino que no responde a la pregunta.

2. Aumentar el número de puntos de control/manillas. Los polinomios de alto orden son monstruos rebeldes. En lugar de aumentar el orden de la curva, voy a concatenar Curvas de tercer orden (que compartan puntos finales comunes, y tal vez tangentes). Esto tiene el aspecto familiar: un punto de la curva tiene un asa que se extiende a ambos lados. Como regla general, utilizaremos curvas de 3er orden en todas partes, de modo que entre dos puntos de control cualquiera de la spline, hay una única curva de 3er orden, y los tiradores dan la dirección, y la fuerza, de la tangente en ese punto,
así .

En ambos casos, evito elevar el orden, todas las curvas son de orden 3.

---

Permítanme que me tome en serio esta aplicación. No estoy convencido de que tenga que cambiar la resolución, excepto por algunas reglas muy generales (digamos, basadas en la distancia de la cámara y el cuadro delimitador). He aquí por qué.

Consideremos la representación (1b). Has posteado en un foro de Juegos, así que asumiré que estás dispuesto a usar una tarjeta gráfica o SSE2 para hacer algunas matemáticas vectoriales. Elijo una resolución arbitraria: digamos, 32 puntos (31 segmentos). Acepto no cambiar este número, sino utilizarlo en todas partes, para todas las splines que se muestran en la pantalla.

Considera el punto k de mi spline. Lo escribiré como un producto vectorial:

$\left[\begin{array}{} A & B & C&D \end{array}\right] \left[\begin{array}{} (1\!-\!t_k)^3 \\(1\!-\!t_k)^2 t_k \\ (1\!-\!t_k){t_k}^2\\{t_k}^3 \end{array}\right]\;\;\;$ o, $\left[\begin{array}{} A & B & C&D \end{array}\right] \cdot T_k$ ,
donde Tk es un vector de columnas. Entonces los 32 puntos de mi spline son $\left[\begin{array}{} A & B & C&D \end{array}\right] \left[ \left[\begin{array}{} \;\\ \!T_0 \!\\\; \end{array}\right] \left[\begin{array}{} \;\\ \!T_1\! \\\; \end{array}\right] \left[\begin{array}{} \;\\ \!\ldots \! \\\; \end{array}\right] \left[\begin{array}{} \;\\ \!T_{31}\! \\\; \end{array}\right] \right] $

La matriz 4x32 de la derecha, que contiene todas las potencias de tk, es constante, y se utilizará para todas las splines de mi pantalla. Todo el problema se puede pasar a la tarjeta gráfica (o SSE) como la multiplicación matricial (particionada) de [Pts] $\cdot$ [Constantes], y luego dibujar las líneas rectas que unen los puntos de la misma curva.

Siendo lo que hay que hacer
Adelante. (POR HACER: EDITAR.)

Answer 5

He elaborado la expresión de forma cerrada de la longitud para un Bezier de 3 puntos (cuadrático) (abajo). No he intentado elaborar una forma cerrada para 4+ puntos. Esto probablemente sería difícil o complicado de representar y manejar. Sin embargo, una técnica de aproximación numérica como un Runge-Kutta algoritmo de integración funcionaría bastante bien integrando mediante el fórmula de la longitud del arco .

Aquí hay un código Java para la longitud de arco de un Bezier de 3 puntos, con puntos a , b y c .

    v.x = 2*(b.x - a.x);
    v.y = 2*(b.y - a.y);
    w.x = c.x - 2*b.x + a.x;
    w.y = c.y - 2*b.y + a.y;

    uu = 4*(w.x*w.x + w.y*w.y);

    if(uu < 0.00001)
    {
        return (float) Math.sqrt((c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y));
    }

    vv = 4*(v.x*w.x + v.y*w.y);
    ww = v.x*v.x + v.y*v.y;

    t1 = (float) (2*Math.sqrt(uu*(uu + vv + ww)));
    t2 = 2*uu+vv;
    t3 = vv*vv - 4*uu*ww;
    t4 = (float) (2*Math.sqrt(uu*ww));

    return (float) ((t1*t2 - t3*Math.log(t2+t1) -(vv*t4 - t3*Math.log(vv+t4))) / (8*Math.pow(uu, 1.5)));