Clever Geek Handbook

Curvas de Bézier. Um pouco sobre cruzamentos e o mais simples possível

Você já encontrou a construção de um caminho (contínuo) para atravessar uma curva em um plano definido por segmentos de linha e curvas de Bézier?



Parece não ser uma tarefa muito difícil: unir os segmentos das curvas em um caminho e contorná-lo "sem levantar a caneta". Uma curva fechada atravessa em uma direção, os ramos avançam e retrocedem e começam e terminam no mesmo nó.



Tudo estava bem até que caminhos monstruosos começaram a rastejar para fora das mãos dos designers, onde curvas individuais poderiam se cruzar ou não exatamente atracar. A explicação foi extremamente simples - visualmente todos mentem como deveriam, e para a máquina que vai contornar esse caminho, tais desvios são invisíveis.



Munido do conhecimento do desvio máximo admissível, iniciei a pesquisa, cujos resultados desejo compartilhar.



A primeira coisa que fiz foi descobrir como as coisas estão hoje (outubro de 2020) ao encontrar os pontos de interseção das curvas. Ou eu estava procurando no lugar errado, ou talvez estivesse perguntando, mas não consegui encontrar uma solução simples. Porém, a ideia com a resultante de um par de polinômios é bastante interessante. Muitos algoritmos diferentes relacionados às curvas de Bézier são coletados aqui .



O que não gostei nos métodos conhecidos e não quero fazer é pesquisar numericamente as raízes dos polinômios, ou mesmo resolver equações quadráticas. Eu realmente não quero explorar as curvas para extremos. De qualquer forma, gostaria de evitar divisões, exponenciações e tudo o que pode levar a comportamentos indefinidos.



Exemplo

, ,



Então, com o que você tem que trabalhar.



  • Os pontos são especificados por tipo Point, como este:



    using Point = std::array<double, 2>;


    Para Pointos operadores de adição, subtração, multiplicação por um escalar, a multiplicação escalar é definida.



  • O valor do Rdesvio admissível de pontos é definido.



  • As curvas são definidas por matrizes de pontos de controle (controle) std::vector<Point>.



  • Curvas quase coincidentes devem ser marcadas e, se possível, excluídas, por exemplo, se for uma duplicata esquecida (copiar-colar é mau).





, , . ( ):



Point point(const std::vector<Point> &curve, double t, int n, int i)
{
    return n == 0 ? curve[i] : (point(curve, t, n - 1, i - 1) * (1 - t) + point(curve, t, n - 1, i) * t);
}


— , :



Point point(const std::vector<Point> &curve, double t)
{
    return point(curve, t, curve.size() - 1, curve.size() - 1);
}


, curve — : , .



— - , R:



template <>
struct std::less<Point>
{
    bool operator()(const Point &a, const Point &b, const double edge = R) const
    {
        for (auto i = a.size(); i-- > 0;) {
            if (a[i] + edge < b[i])
                return true;
            if (a[i] > b[i] + edge)
                return true;
        }
        return false;
    }
};


. , , , . — :



struct Rect
{
    Point topLeft, bottomRight;
    Rect(const Point &point);
    Rect(const std::vector<Point> &curve);
    bool isCross(const Rect &rect, const double edge) const
    {
        for (auto i = topLeft.size(); i-- > 0;) {
            if (topLeft[i] > rect.bottomRight[i] + edge
                || bottomRight[i] + edge < rect.topLeft[i])
                return false;
        }
        return true;
    }
};




void find(const std::vector<Point> &curveA, const std::vector<Point> &curveB,
          double tA, double tB, double dt)
{


1. , . 
    if (m_isSimilarCurve)
        return;


2. , 
    Rect aRect(curveA);
    Rect bRect(curveB);
    if (!aRect.isCross(bRect, R))
        return;


3. R/2, , 
    if (isNear(aRect.tl, aRect.br, R / 2) && isNear(bRect.tl, bRect.br, R / 2)) {
        // 3.1        
        addBest(curveA.front(), curveA.back(), curveB.front(), curveB.back(), tA, tB, dt);
        m_isSimilarCurve = (m_result.size() > curveA.size() * curveB.size());
        return;
    }


4. 
    const auto curveALeft = subCurve(curveA, 0, 0.5);
    const auto curveARight = subCurve(curveA, 0.5, 1.0);
    const auto curveBLeft = subCurve(curveB, 0, 0.5);
    const auto curveBRight = subCurve(curveB, 0.5, 1.0);


5. 
    const auto dtHalf = dt / 2;
    find(curveALeft, curveBLeft, tA, tB, dtHalf);
    find(curveALeft, curveBRight, tA, tB + dtHalf, dtHalf);
    find(curveARight, curveBLeft, tA + dtHalf, tB, dtHalf);
    find(curveARight, curveBRight, tA + dtHalf, tB + dtHalf, dtHalf);


}


- : , t t1 t2?



t = (t2 - t1) t' + t1 . t = t1, t = t2. , ( ) . : k t2 t1, k:



Point point(const std::vector<Point> &curve, double t1, int n, int i, double t2, int k)
{
    return n > k ? (point(curve, t1, n - 1, i - 1, t2, k) * (1 - t2) +
                    point(curve, t1, n - 1, i, t2, k) * t2)
                 : point(curve, t1, n, i);
}


, :



std::vector<Point> subCurve(const std::vector<Point> &curve, double t1, double t2)
{
    std::vector<Point> result(curve.size());
    for (auto k = result.size(); k-- > 0;) {
        result[k] = point(curve, t1, curve.size() - 1, curve.size() - 1, t2, curve.size() - 1 - k);
    }
    return result;
}


, , .



.



  1. t1e t2pode ser qualquer:

    • subCurve(curve, 1, 0)dará uma curva que "se move" do ponto final curveao ponto inicial,
    • subCurve(curve, 1, 2)extrapola curvealém do último ponto de ancoragem.
  2. Algumas implementações de método são omitidas intencionalmente porque não contêm nada particularmente interessante.
  3. A função point(curve, t)não é adequada para calcular muitos pontos em uma curva (por exemplo, para rasterização); para isso, o cálculo usando uma matriz triangular é mais adequado.


More articles:


All Articles