Puntos espaciados uniformemente a lo largo de una curva bezier

10

He mirado alrededor por un tiempo y no puedo encontrar una solución a este problema. Digamos que tengo una curva bezier cúbica (definida por 4 puntos) y quiero obtener un conjunto de puntos espaciados uniformemente a lo largo de la curva. Piense en colocar un texto a lo largo de una curva como ejemplo.

Ahora el problema es que si ingreso t(valor de interpolación de 0-1) con un incremento constante, los puntos no están espaciados uniformemente. La distancia a lo largo de la curva es menor cuando la curva gira y más larga cuando la curva es recta.

Entonces, ¿cómo coloco puntos uniformemente a lo largo de una curva bezier?

Potrillo
fuente
44
¿Está buscando una solución "puramente matemática" (o particularmente eficiente)? De lo contrario, el enfoque directo es: Convierta la curva en una polilínea, caminando a lo largo de la curva, incrementando ten, digamos, 100 pasos, y mida las distancias entre los puntos resultantes. Luego, interpola a lo largo de esta polilínea como desees.
Marco13
Creo que está buscando la palabra clave "parametrización de longitud de arco", que se respondió por ejemplo en esta pregunta .
wondra
¡Lo que dijo Marco13!
David Van Brink
Según las respuestas / comentarios, el enfoque que mencioné no solo es sencillo, sino también bastante común. ¿Es esto para un idioma en particular? Tal vez alguien publicaría unas pocas líneas de código entonces ...
Marco13

Respuestas:

3

Es más una pregunta matemática. Así que una curva de Bezier tiene la siguiente fórmula , tanto en el xy ycomponente.

B_x(t) = (1-t)^3 * P0_x + (1-t)^2 * t * P1_x + (1-t) * t^2 * P2_x + t^3 * P3_x
B_y(t) = (1-t)^3 * P0_y + (1-t)^2 * t * P1_y + (1-t) * t^2 * P2_x + t^3 * P3_y

La longitud recorrida por tuna curva gammaviene dada por:

length_gamma(t) = integration( sqrt( derivative(  gamma_x(s)  ) ^2 + derivative(  gamma_y(s)  ) ^2 ) )

No hay una solución de escritura humana para la integral, por lo que debe aproximarse.

Reemplace el gamma(t)por la expresión B(t)para obtener la longitud length_Brecorrida a lo tlargo del segmento bezier. Digamos que viaja de 0a L.

Ahora elija nvalores entre 0y Lque correspondan a los puntos espaciados uniformemente. Por ejemplo, longitudes del formulario k*L/npara kde 0a n.

Ahora necesita invertir la función length_B, para poder calcular el treverso a partir de la longitud l. Son muchas matemáticas y soy flojo como el infierno, intenta hacerlo tú mismo. Si no puede, puede ir al intercambio de pila matemática . Para una respuesta más completa, puedes ir allí de todos modos.

Una vez que tenga esa length_Bfunción inversa (o una aproximación razonable), el proceso es bastante simple.

  • Crear longitudes l[k]de distancia de ruta dada lejos del origen (P0_x,P1_x).
  • Calcule su t[k]uso correspondiente length_B_inverse.
  • Posicionar los puntos usando (B_x(t[k]),B_y(t[k])).
Lærne
fuente
1
¡Gracias! Resulta que las matemáticas que necesitas para integrar el polinomio de Bernstein es una pesadilla. Pude usar esta solución
Potrillo
0

Solo para ampliar lo que dijo Marco, una técnica común para hacer esto es caminar por la curva en incrementos mucho más pequeños que los pasos de longitud fija que desea tomar y almacenar el punto de salida resultante (¿y quizás la distancia?) En una tabla.

Luego, revisa la tabla y descarta todas las entradas, excepto los puntos más cercanos a los múltiplos enteros de las distancias que desea caminar.

Luego, queda una tabla que puede indexar directamente en tiempo de ejecución muy rápidamente. Si desea ir al lugar que es 5 veces el tamaño de su distancia, mire en su tabla el índice [5].

Tenga en cuenta que, para empezar, puede realizar los dos pasos en uno y no almacenar los elementos adicionales en la tabla, pero es más fácil de visualizar y comprender en dos pasos.

Una vez vi una técnica para calcular esto sobre la marcha sin calcular previamente una tabla (¡tampoco usaba iteración / búsqueda de raíz!), Pero desafortunadamente no puedo recordar los detalles en absoluto:

Si lo recuerdo o lo encuentro, ¡publicaré la información!

Alan Wolfe
fuente
1
esto también podría ser de su interés: math.stackexchange.com/questions/15896/…
Alan Wolfe el
0

Paso 1 - Genera N + 1 puntos interpolando la curva en incrementos de 1 / N. N debe ser lo suficientemente grande como para obtener buenos resultados visuales, pero lo suficientemente pequeño como para ser fácilmente calculado. Un valor de 50 debería estar bien para la mayoría de las situaciones, pero debería ajustarse para su caso específico. Llamaré a esto los "puntos interpolados".

Alternativamente, puede generar una lista corta de segmentos y dividir recursivamente cada segmento que sea más largo que la longitud máxima deseada del segmento (inicialmente debe generar al menos cuatro segmentos para tener en cuenta las curvas S donde el inicio está muy cerca del final).

Paso 2 - "Camina la línea" usando los puntos interpolados y el espacio que deseas entre cada punto.

Lo dejaré aquí mi código de Unidad:

public static Vector2[] InterpolateBezier(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, int segments)
{
    Vector2[] interpolated = new Vector2[segments + 1];
    interpolated[0] = start;
    interpolated[segments] = end;

    float step = 1f / segments;
    for (int i = 1; i < segments; i++)
    {
        interpolated[i] = GetBezierPosition(start, startControlPoint, end,
            endControlPoint, i * step);
    }

    return interpolated;
}

public static Vector2 GetBezierPosition(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, float t)
{
    float omt = 1f - t;
    float omt2 = omt * omt;
    float t2 = t * t;

    return
        start * (omt2 * omt) +
        startControlPoint * (3f * omt2 * t) +
        endControlPoint * (3f * omt * t2) +
        end * (t2 * t);
}

public static List<Vector2> WalkLine(Vector2[] points, float spacing, float offset = 0)
{
    List<Vector2> result = new List<Vector2>();

    spacing = spacing > 0.00001f ? spacing : 0.00001f;

    float distanceNeeded = offset;
    while (distanceNeeded < 0)
    {
        distanceNeeded += spacing;
    }

    Vector2 current = points[0];
    Vector2 next = points[1];
    int i = 1;
    int last = points.Length - 1;
    while (true)
    {
        Vector2 diff = next - current;
        float dist = diff.magnitude;

        if (dist >= distanceNeeded)
        {
            current += diff * (distanceNeeded / dist);
            result.Add(current);
            distanceNeeded = spacing;
        }
        else if (i != last)
        {
            distanceNeeded -= dist;
            current = next;
            next = points[++i];
        }
        else
        {
            break;
        }
    }

    return result;
}
Jorge Galvão
fuente
-1

Aquí hay un algoritmo que da resultados bastante buenos:

  Point Index(float pos) const
  {
    int count = p.NumPoints();
    Vector val(0.0,0.0,0.0);
    for(int i=0;i<count;i++)
      { 
        val += bin(pos,i,count-1)*Vector(p.Points(i));
      }
    return Point(val);
  }
  float bin(float pos, int i, int n) const
  { 
    return float(ni(n,i)) * pow(double(pos), double(i))*pow(double(1.0-pos), double(n-i));
  }
  int ni(int n, int i) const
  {
    if (i==0) { return 1; }
    if (n==i) { return 1; }
    return ni(n-1,i-1)+ni(n-1,i);
  }
tp1
fuente