Comprimento do arco da curva de Bezier

23

Veja também: mesma pergunta no Math.SE

Como posso encontrar o comprimento de arco de uma curva de Bezier? Por exemplo, uma curva linear de Bezier tem o comprimento:

length = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));

Mas e as curvas de Bezier quadráticas, cúbicas ou n graus?

(Meu objetivo era estimar uma resolução de amostragem de antemão, para não perder tempo verificando se o próximo ponto está tocando o ponto anterior.)

Mateen Ulhaq
fonte
1
Você deve reformular a pergunta para se referir ao comprimento da curva, que é um termo muito mais direto (e pesquisável).
Sparr
sugiro postar isso em matemática, eu tenho certeza que alguns cara inteligente lá vai lhe dar a resposta em um deles fontes web inteligentes: p
Tor Valamo
2
@ Tor eu fiz (ontem), mas me disseram que é muito complicado e, portanto, impraticável. [ math.stackexchange.com/q/12186/2736 ]
Mateen Ulhaq 28/11
Supostamente, curvas / splines clotóides são uma alternativa aos beziers e têm expressões de comprimento de arco de forma fechada, mas ainda não sei muito sobre isso. (Tentando gerar pontos de distância igual ao longo de uma curva.) As catenárias também têm expressões de comprimento de arco em formato fechado?
endolith

Respostas:

9

Uma maneira simples para Beziers cúbicos é dividir a curva em N segmentos e somar os comprimentos dos segmentos.

No entanto, assim que você precisar do comprimento de apenas parte da curva (por exemplo, até um ponto 30% do comprimento), a parametrização do comprimento do arco entrará em jogo. Postei uma resposta bastante longa em uma de minhas perguntas sobre Béziers, com um exemplo simples de código.

Ivo Wetzel
fonte
Estou fazendo isso no LEGO Mindstorms NXT, que tem um processador realmente fraco (48Mhz), por isso preciso da maior velocidade possível. Adotarei a abordagem de divisão para economizar velocidade e obtê-la com precisão suficiente (para renderização "não em tempo real"). Eu também tenho uma opção na qual você pode definir o valor de 1.0/t(chamado resolution), então isso é para "tempo real" (que é no máximo 10fps no lento NXT). Toda iteração,, t += resolutione um novo ponto / linha são desenhados. De qualquer forma, obrigado pela ideia.
Mateen Ulhaq
4

Embora eu esteja de acordo com as respostas que você já obteve, quero adicionar um mecanismo de aproximação simples, mas poderoso, que você pode usar para qualquer curva de Bézier: Você subdivide continuamente a curva usando a subdivisão de Casteljau até a distância máxima dos pontos de controle de uma sub-curva para a linha de base da sub-curva está abaixo de algum epsilon constante . Nesse caso, a subcurva pode ser aproximada por sua linha de base.

De fato, acredito que essa é a abordagem geralmente adotada quando um subsistema gráfico precisa traçar uma curva de Bézier. Mas não me cite, não tenho referências em mãos no momento.

Na prática, será assim: (exceto que o idioma é irrelevante)

public static Line[] toLineStrip(BezierCurve bezierCurve, double epsilon) {
    ArrayList<Line> lines = new ArrayList<Line>();

    Stack<BezierCurve> parts = new Stack<BezierCurve>();
    parts.push(bezierCurve);

    while (!parts.isEmpty()) {
        BezierCurve curve = parts.pop();
        if (distanceToBaseline(curve) < epsilon) {
            lines.add(new Line(curve.get(0), curve.get(1)));
        } else {
            parts.addAll(curve.split(0.5));
        }
    }

    return lines.toArray(new Line[0]);
}
Matthias
fonte
Embora essa seja uma boa abordagem, ouvi falar de instabilidade numérica nas curvas de Bezier de alta ordem, que exigem outra idéia: dividir as curvas de ordem superior em curvas cúbicas menores.
Mateen Ulhaq
Além disso, se o objetivo final for uma estimativa precisa, pode ser uma boa ideia aproximar com quadráticos em vez de linhas para garantir que não subestimemos nossa estimativa em locais de alta curvatura.
Mateen Ulhaq
2

Os comprimentos do arco para as curvas de Bezier são apenas de forma fechada para os lineares e quadráticos. Para cubicos, não é garantido que você tenha uma solução fechada. O motivo pelo qual o comprimento do arco é definido por uma integral radical, para a qual somente os polinômios de 2º grau foram fechados.

Apenas para referência: o comprimento de um Bezier quadrático para os pontos (a, p) (b, q) e (c, r) é

(a ^ 2 · (q ^ 2 - 2 · q · r + r ^ 2) + 2 · a · (r - q) · (b · (p - r) + c · (q - p)) + ( b · (p - r) + c · (q - p)) ^ 2) · LN ((√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · √ (a ^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) + a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) / (√ (a ^ 2 + 2 · A · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) · √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) + a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2) ^ (3/2) + (√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · (a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) - √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) · (a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2)

Onde LN é o logaritmo natural e ^ denota potência e √ a raiz quadrada.

Portanto, deve ser mais fácil e barato aproximar o arco de alguma outra regra, como um polígono ou um esquema de integração como a regra de Simpson, porque as raízes quadradas do LN são operações caras.

Robert
fonte
2

Elaborei a expressão fechada de comprimento para um Bezier de 3 pontos (abaixo). Não tentei elaborar um formulário fechado para mais de 4 pontos. Isso provavelmente seria difícil ou complicado de representar e manipular. No entanto, uma técnica de aproximação numérica, como o algoritmo de integração Runge-Kutta, funcionaria muito bem ao integrar usando a fórmula de comprimento do arco . Minhas perguntas e respostas sobre o RK45 no MSE podem ajudar na implementação do RK45.

Aqui está um código Java para o comprimento do arco de um 3 pontos Bezier, com pontos a, be 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)));
Pixel
fonte