tag - tamaño metadescription

Manera barata de calcular la longitud del bezier cúbico

Question

Parece que no existe una solución analítica para la longitud del bezier cúbico, pero no significa que no exista la codificación de una solución barata. Por barato quiero decir algo como en el rango de 50-100 ns (o menos).

¿Alguien sabe algo así? Tal vez en dos categorías:

1) menos error como 1% pero código más lento. 2) mas error como 20% pero mas rapido?

Escanee un poco en Google pero no encuentra nada que parezca una buena solución. Solo algo como dividir en N segmentos de línea y sumar N sqrt - demasiado lento para mayor precisión, y probablemente demasiado impreciso para 2 o 3 segmentos.

¿Hay algo mejor?

Answer 1

Algoritmo más simple: aplanar la curva y calcular la distancia euclidiana. Siempre que desee una longitud de arco aproximada, esta solución es rápida y barata. Dada la LUT de coordenadas de su curva, está hablando de velocidad, así que asumo que las usa y no las calcula constantemente, es un bucle simple con un recuento. En código genérico, con una función dist que calcula la distancia euclidiana entre dos puntos:

var arclength = 0,
    last=LUT.length-1,
    i;
for (i=0; i<last; i++) {
  arclength += dist(LUT[i], LUT[i+1]);
}

Hecho. arclength ahora es la longitud de arco aproximada según el número máximo de segmentos que puede formar en la curva según su LUT. ¿Necesita cosas más rápido con un mayor error potencial? Controla el conteo de segmentos.

var arclength = 0,
    segCount = ...,
    last=LUT.length-2,
    step = last/segCount,
    s, i;
for (s=0; s<=segCount; s++) {
  i = (s*step/last)|0;
  arclength += dist(LUT[i], LUT[i+1]);
}

Este es prácticamente el algoritmo más simple posible que aún genera valores que se acercan incluso a la verdadera longitud del arco. Para algo mejor, tendrás que usar enfoques numéricos más costosos (como la técnica de cuadratura de Legendre-Gauss).

Si quiere saber por qué, toque la sección de longitud de arco de "A Primer on Bézier Curves".

Answer 2

Otra opción es estimar la longitud del arco como el promedio entre el acorde y la red de control. En la práctica:

Bezier bezier = Bezier (p0, p1, p2, p3);

chord = (p3-p0).Length;
cont_net = (p0 - p1).Length + (p2 - p1).Length + (p3 - p2).Length;

app_arc_length = (cont_net + chord) / 2;

Luego, puede dividir recursivamente su segmento de spline en dos segmentos y calcular la longitud del arco hasta la convergencia. Me probé y en realidad converge bastante rápido. Tengo la idea de este forum .

Answer 3

Primero, primero debes entender el uso del algoritmo en Bezier. Cuando estaba codificando un programa por c # El cual estaba lleno de material gráfico, usé beziers y muchas veces tuve que encontrar un punto coordinado en bezier, lo que parece impensable en el primer vistazo. . así que lo que hice fue escribir la función de Bizcé cúbico en mi clase de matemática de disfraces que estaba en mi proyecto. así que compartiré el código contigo primero.

    //--------------- My Costum Power Method ------------------//

public static float FloatPowerX(float number, int power)
        {
            float temp = number;
            for (int i = 0; i < power - 1; i++)
            {
                temp *= number;
            }
            return temp;
        }

    //--------------- Bezier Drawer Code Bellow ------------------//

public static void CubicBezierDrawer(Graphics graphics, Pen pen, float[] startPointPixel, float[] firstControlPointPixel
                , float[] secondControlPointPixel, float[] endPointPixel)
        {
            float[] px = new float[1111], py = new float[1111];
            float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0], secondControlPointPixel[0], endPointPixel[0] };
            float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1], secondControlPointPixel[1], endPointPixel[1] };
        int i = 0;

        for (float t = 0; t <= 1F; t += 0.001F)
        {
            px[i] = FloatPowerX((1F - t), 3) * x[0] + 3 * t * FloatPowerX((1F - t), 2) * x[1] + 3 * FloatPowerX(t, 2) * (1F - t) * x[2] + FloatPowerX(t, 3) * x[3];
            py[i] = FloatPowerX((1F - t), 3) * y[0] + 3 * t * FloatPowerX((1F - t), 2) * y[1] + 3 * FloatPowerX(t, 2) * (1F - t) * y[2] + FloatPowerX(t, 3) * y[3];
            graphics.DrawLine(pen, px[i - 1], py[i - 1], px[i], py[i]);
            i++;
        }
    }

Como se ve más arriba, esta es la forma en que funciona una función de Bézier y dibuja el mismo Bezier que la función de Bezier de Microsoft (lo he probado). puede hacerlo aún más preciso incrementando el tamaño de matriz y el tamaño de contador o dibujando elipse en lugar de línea y .... Todos ellos dependen de su necesidad y del nivel de precisión que necesite y ....

Volviendo al objetivo principal, la pregunta es ¿cómo calcular la longitud?

Bueno, la respuesta es que tenemos toneladas de puntos y cada uno de ellos tiene una coordenada x y una coordenada y que nos recuerdan una forma de triángulo y, especialmente, una forma de arco de derecha. así que si tenemos el punto p1 y p2, podemos calcular la distancia de ellos como un acorde de triángulo rectángulo. Como recordamos de nuestra clase de matemáticas en la escuela, en ABC Triangle of type Right Triangle, la longitud del acorde es -> Sqrt (Angle''s FrontCostalLenght ^ 2 + Angle''s SideCostalLeghth ^ 2);

y existe esta relación entre todos los puntos que calculamos la longitud entre el punto actual y el último punto antes del punto actual (exmp p [i - 1] & p [i]) y almacenamos la suma de todos ellos en una variable. vamos a mostrarlo en el código de abajo

//--------------- My Costum Power Method ------------------//

public static float FloatPower2(float number)
        {
            return number * number;
        }

//--------------- My Bezier Lenght Calculator Method ------------------//

public static float CubicBezierLenghtCalculator(float[] startPointPixel
            , float[] firstControlPointPixel, float[] secondControlPointPixel, float[] endPointPixel)
        {
            float[] tmp = new float[2];
            float lenght = 0;
            float[] px = new float[1111], py = new float[1111];

            float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0]
                , secondControlPointPixel[0], endPointPixel[0] };

            float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1]
                , secondControlPointPixel[1], endPointPixel[1] };

            int i = 0;

            for (float t = 0; t <= 1.0; t += 0.001F)
            {
                px[i] = FloatPowerX((1.0F - t), 3) * x[0] + 3 * t * FloatPowerX((1.0F - t), 2) * x[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * x[2] + FloatPowerX(t, 3) * x[3];
                py[i] = FloatPowerX((1.0F - t), 3) * y[0] + 3 * t * FloatPowerX((1.0F - t), 2) * y[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * y[2] + FloatPowerX(t, 3) * y[3];
                if (i > 0)
                {
                    tmp[0] = Math.Abs(px[i - 1] - px[i]);// calculating costal lenght
                    tmp[1] = Math.Abs(py[i - 1] - py[i]);// calculating costal lenght
                    lenght += (float)Math.Sqrt(FloatPower2(tmp[0]) + FloatPower2(tmp[1]));// calculating the lenght of current RightTriangle Chord  & add it each time to variable
                }
                i++;
            }
            return lenght;
        }

Si desea tener un cálculo más rápido, solo tiene que reducir la longitud de la matriz px y py y la cantidad de bucles.

También podemos disminuir la necesidad de memoria reduciendo px y py a la longitud de la matriz a 1 o hacer una variable doble simple, pero debido a la situación condicional que se produce, lo que Aumentó Nuestro Gran OI no lo hizo.

Espero que te haya ayudado tanto. Si tiene otra pregunta solo pregunte. Saludos cordiales, Heydar - República Islámica de Irán.

Answer 4

Trabajé la expresión de forma cerrada de longitud para un Bezier de 3 puntos (abajo). No he intentado elaborar un formulario cerrado para 4+ puntos. Esto sería muy difícil o complicado de representar y manejar. Sin embargo, una técnica de aproximación numérica, como un algoritmo de integración de Runge-Kutta ( vea mis preguntas y respuestas aquí para obtener detalles ) funcionaría bastante bien al integrarse utilizando la fórmula de longitud de arco .

Aquí hay un código Java para la longitud del arco de un Bezier de 3 puntos, con los 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)));

Answer 5

public float FastArcLength()
{
    float arcLength = 0.0f;
    ArcLengthUtil(cp0.position, cp1.position, cp2.position, cp3.position, 5, ref arcLength);
    return arcLength;
}

private void ArcLengthUtil(Vector3 A, Vector3 B, Vector3 C, Vector3 D, uint subdiv, ref float L)
{
    if (subdiv > 0)
    {
        Vector3 a = A + (B - A) * 0.5f;
        Vector3 b = B + (C - B) * 0.5f;
        Vector3 c = C + (D - C) * 0.5f;
        Vector3 d = a + (b - a) * 0.5f;
        Vector3 e = b + (c - b) * 0.5f;
        Vector3 f = d + (e - d) * 0.5f;

        // left branch
        ArcLengthUtil(A, a, d, f, subdiv - 1, ref L);
        // right branch
        ArcLengthUtil(f, e, c, D, subdiv - 1, ref L);
    }
    else
    {
        float controlNetLength = (B-A).magnitude + (C - B).magnitude + (D - C).magnitude;
        float chordLength = (D - A).magnitude;
        L += (chordLength + controlNetLength) / 2.0f;
    }
}