Pontos espaçados uniformemente ao longo de uma curva de bezier

10

Eu olhei em volta por um tempo e não consigo encontrar uma solução para esse problema. Digamos que eu tenho uma curva cúbica de bezier (definida por 4 pontos) e desejo obter um conjunto de pontos espaçados uniformemente ao longo da curva. Pense em colocar um texto ao longo de uma curva, por exemplo.

Agora, o problema é que, se eu inserir t(valor de interpolação de 0-1) com um incremento constante, os pontos não serão espaçados uniformemente. A distância ao longo da curva é menor quando a curva faz uma curva e maior quando a curva é reta.

Então, como coloco pontos uniformemente ao longo de uma curva de bezier?

Potrus
fonte
4
Você está procurando uma solução "puramente matemática" (ou particularmente eficiente)? Caso contrário, a abordagem direta é: Converta a curva em uma polilinha, caminhando ao longo da curva, aumentando os t, digamos, 100 passos e meça as distâncias entre os pontos resultantes. Em seguida, interpole ao longo dessa polilinha, conforme desejado.
Marco13
Acho que você está procurando a palavra-chave "parametrização do comprimento do arco", que foi respondida, por exemplo, nesta pergunta .
Wondra
O que @ Marco13 disse!
David van brink
De acordo com as respostas / comentários, a abordagem que mencionei não é apenas direta, mas também bastante comum. Isso é para um idioma específico? Talvez alguém ia postar algumas linhas de código, então ...
Marco13

Respostas:

3

É mais uma questão de matemática. Assim, uma curva de Bezier tem a seguinte fórmula , tanto no xe 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

O comprimento percorrido ao tlongo de uma curva gammaé dado por:

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

Não há solução gravável em humanos para a integral, então você precisa se aproximar.

Substitua gamma(t)by pela expressão B(t)para obter o comprimento length_Bpercorrido ao tlongo do segmento bezier. Digamos que ele viaja de 0para L.

Agora escolha nvalores entre 0e Lque correspondam aos pontos espaçados igualmente. Por exemplo, comprimentos do formulário k*L/npara kde 0até n.

Agora você precisa inverter a função length_B, para poder calcular as tcostas a partir do comprimento l. É muita matemática e eu sou preguiçoso como o inferno, tente fazer isso sozinho. Se não puder, pode ir para a troca de pilha matemática . Para uma resposta mais completa, você pode ir para lá de qualquer maneira.

Depois de ter essa length_Bfunção inversa (ou uma aproximação razoável), o processo é bastante simples.

  • Crie comprimentos l[k]de distância do caminho especificado longe da origem (P0_x,P1_x).
  • Calcule o t[k]uso correspondente length_B_inverse.
  • Posicionando os pontos usando (B_x(t[k]),B_y(t[k])).
Lærne
fonte
11
Obrigado! Acontece que a matemática necessária para integrar o polinômio de Bernstein é um pesadelo. Eu era capaz de usar esta solução
Potrus
0

Apenas para expandir o que Marco disse, uma técnica comum para fazer isso é descer a curva em incrementos muito menores do que os passos de comprimento fixo que você deseja executar e armazenar o ponto de saída resultante (e talvez a distância?) Em uma tabela.

Em seguida, você percorre a tabela e descarta todas as entradas, exceto os pontos mais próximos dos múltiplos inteiros das distâncias que deseja percorrer.

Você fica com uma tabela que pode indexar diretamente em tempo de execução muito rapidamente. Se você quiser ir para o ponto que é 5 vezes o tamanho da sua distância, procure na tabela no índice [5].

Observe que você pode executar as duas etapas em uma e não armazenar os itens extras na tabela para começar, mas é mais fácil visualizar e entender em duas etapas.

Certa vez, vi uma técnica para calcular isso rapidamente, sem pré-calcular uma tabela (também não usava iteração / localização de raiz!), Mas, infelizmente, não me lembro dos detalhes:

Se eu me lembrar ou encontrar, postarei as informações!

Alan Wolfe
fonte
11
isso também pode ser de seu interesse: math.stackexchange.com/questions/15896/...
Alan Wolfe
0

Etapa 1 - Gere N + 1 pontos interpolando a curva em incrementos de 1 / N. N deve ser grande o suficiente para obter bons resultados visuais, mas pequeno o suficiente para ser facilmente calculado. Um valor de 50 deve ser bom para a maioria das situações, mas deve ser ajustado para o seu caso específico. Vou chamar isso de "pontos interpolados".

Como alternativa, você pode gerar uma lista curta de segmentos e interromper recursivamente cada segmento maior que o comprimento máximo desejado do segmento (inicialmente você deve gerar pelo menos quatro segmentos para contabilizar as curvas S, onde o início está muito próximo do fim).

Etapa 2 - "Ande na linha" usando os pontos interpolados e o espaçamento desejado entre cada ponto.

Vou deixar aqui meu código do Unity:

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
fonte
-1

Aqui está um algoritmo que fornece bons resultados:

  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
fonte