Inkscape 自动平滑节点背后的算法

Question

我通过内插（很多）点来生成平滑曲线。我想要本地支持（即只有少数点在本地确定平滑曲线），所以我不想使用经典插值样条。贝塞尔曲线对我来说是一个自然的解决方案，Inkscape 的自动平滑节点 (http://tavmjong.free.fr/INKSCAPE/MANUAL/html/Paths-Editing.html#Paths-Node-AutoSmooth) 可以很好地满足我的需求。但是我很难在源代码中找到实现或对底层算法的一些参考。

这里是否有人知道该算法或对 Inkscape 的来源足够熟悉，以便他们可以指出正确的方向？

对于上下文：我正在计算笔式绘图仪的平滑路径，但迫不及待地想获得所有可用的支撑点。

Answer 1

根据@fang 下面的评论。最好改用 Catmull-Rom Interpolating Spline，它既可以插值又可以进行本地控制属性。 See more here

要将插值的三次贝塞尔曲线拼接在一起（更像自然三次样条曲线），请参见下面的原始答案。

======================================== ===========================

以下是类似于 javascript 的伪代码，它计算一系列（最多）三次贝塞尔曲线，这些曲线组合在一起 通过给定点实现一个平滑的曲线传递 . 注意 bezier 假设下面的代码是一个函数，它通过给定的控制点（这是已知的算法）计算三次贝塞尔曲线（的多项式形式）。 Note2 下面的算法是针对 1d 曲线的，它很容易针对 2d 曲线进行调整（即计算 x 和 y 坐标）

function bezierThrough( knots )
{
    var i, points, segments;
    computePoints = function computePoints( knots ) {
        var i, p1, p2, a, b, c, r, m, n = knots.length-1;
        p1 = new Array(n);
        p2 = new Array(n);

        /*rhs vector*/
        a = new Array(n);
        b = new Array(n);
        c = new Array(n);
        r = new Array(n);

        /*left most segment*/
        a[0] = 0;
        b[0] = 2;
        c[0] = 1;
        r[0] = knots[0] + 2*knots[1];

        /*internal segments*/
        for(i=1; i<n-1; i++)
        {
            a[i] = 1;
            b[i] = 4;
            c[i] = 1;
            r[i] = 4*knots[i] + 2*knots[i+1];
        }

        /*right segment*/
        a[n-1] = 2;
        b[n-1] = 7;
        c[n-1] = 0;
        r[n-1] = 8*knots[n-1] + knots[n];

        /*solves Ax=b with the Thomas algorithm (from Wikipedia)*/
        for(i=1; i<n; i++)
        {
            m = a[i] / b[i-1];
            b[i] = b[i] - m*c[i - 1];
            r[i] = r[i] - m*r[i-1];
        }

        p1[n-1] = r[n-1] / b[n-1];
        for(i=n-2; i>=0; --i)
            p1[i] = (r[i]-c[i]*p1[i+1]) / b[i];

        /*we have p1, now compute p2*/
        for (i=0;i<n-1;i++)
            p2[i] = 2*knots[i+1] - p1[i+1];
        p2[n-1] = (knots[n]+p1[n-1])/2;

        return [p1, p2];
    };
    if ( 1 === knots.length )
    {
        segments = [knots[0]];
    }
    else if ( 2 === knots.length )
    {
        segments = [bezier([knots[0], knots[1]])];
    }
    else
    {
        segments = [];
        points = computePoints(knots);
        for(i=0; i<knots.length-1; i++)
            segments.push(bezier([knots[i], points[0][i], points[1][i], knots[i+1]]));
    }
    return segments;
}

另见 related post

改编自here

的代码

Answer 2

密码是here and I've implemented a version in Python using the svgpathtools library in a gist

Here is a diagram 显示方法。

给定三个点 a、b 和 c，其中 b 是自动平滑的，b 有两个控制点 u 和 v，然后：

设x为垂直于∠abc
u = b - x * 1/3|ba|
v = b + x * 1/3|bc|

据我所知，常数 1/3 没有什么特别之处，您可以改变它以使其具有更大或更小的曲率。

Inkscape 自动平滑节点背后的算法

Algorithm behind Inkscape's auto-smooth nodes

bezier

inkscape

cubic-bezier