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

Question

我正在通过插值（大量）点来生成平滑曲线。我希望具有局部支持（即仅少数点在局部确定平滑曲线），因此我不想使用经典的插值样条。对我来说，贝塞尔曲线是一种自然的解决方案，Inkscape的自动平滑节点（http://tavmjong.free.fr/INKSCAPE/MANUAL/html/Paths-Editing.html#Paths-Node-AutoSmooth）很好地实现了我想要的功能。但我在源代码中找不到实现或底层算法的任何参考。

这里是否有人知道该算法或熟悉Inkscape的源代码，可以指导我正确的方向？

背景：我正在为钢笔绘图仪计算平滑路径，但不能等待所有支持点都可用。

- Franz

---

你想要绘制贝塞尔曲线的算法吗？ - Nikos M.

我清楚地了解从已知控制点绘制图像(通过Casteljau或直接多项式计算)。我想要找出的是，在定义一个插值点为“自动平滑”时，Inkscape如何选择“内部”控制点。 - Franz

你知道如何连接多个立方贝塞尔曲线以实现通过给定点的一条平滑曲线吗？ - Nikos M.

Answer 1

代码在这里，我已经使用svgpathtools库在Python中实现了一个版本，并在gist中发布。

这里是一个图示展示了该方法。

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

• 令 x 为垂直于∠abc 角平分线的单位向量
• u = b - x * 1/3|ba|
• v = b + x * 1/3|bc|

据我所知，常数 1/3 并没有什么特别之处，您可以将其变化以得到更大或更小的曲率。

更新：在观看 this excellent video 的时候，我重新遇到了这个 1/3 常数，它确实是来自 Hermite 样条。它在 Cubic Hermite Spline 维基百科页面中被简要提到。编辑自动平滑控制节点相当于编辑 Hermite 样条速度向量。

- aconz2

---

哇，这个视频真的非常棒。谢谢分享！ - Franz

Answer 2

根据@fang的评论，最好使用Catmull-Rom插值样条曲线，它既插值又具有局部控制属性。点击此处查看更多。

对于将立方贝塞尔曲线拼接在一起以进行插值（更像自然立方样条）的方法，请参见下面的原始答案。

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

以下是类似于javascript的伪代码，用于计算一系列（最多）三次贝塞尔曲线，这些曲线组合在一起，以实现通过给定点的平滑曲线。请注意，下面代码中的bezier被假定为一个函数，该函数通过给定的控制点计算（多项式形式的）三次贝塞尔曲线（这已经是已知的算法）。注意2下面的算法适用于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;
}

另请参阅相关文章

代码改编自这里

- Nikos M.

---

谢谢！这是一个有趣的解决方案，但它没有本地支持。所以我必须知道所有点来解决任何控制点。事实上，我强烈怀疑这个算法给出的解决方案与样条插值给出的解决方案完全相同，只不过它是以贝塞尔形式呈现的。Inkscape似乎做的不同之处在于它不假设导数的实际连续性，而只假设几何连续性（导数仅平行而非相同），并利用额外的自由度提供一个局部合理的解决方案。 - Franz

据我所见，inkscape的源代码使用了三次贝塞尔曲线和分段贝塞尔曲线。自动平滑节点的示例表明，即使一个点发生变化，也会调整曲线的大部分。这样做是合理的，否则连续性和平滑性就无法实现。我认为，没有什么可以阻止你在单个点发生变化时只更新贝塞尔曲线的一部分。例如，对于5个点p1到p5，如果p3发生变化，您可以仅针对点p2、p3、p4重新运行算法，并仅更新受影响的线段，而其余部分保持不变。在我看来，这是可行的。 - Nikos M.

您提供的链接实际上描述了所谓的“自然三次样条”，这种方法确实没有“局部支持”的属性。Inkscape 的自动平滑节点看起来更像 Catmull-Rom 样条，而 Carmull-Rom 样条确实具有局部支持属性。 - fang

@fang 非常感谢您提供的关键词，您的评论实际上回答了我的问题！我从未听说过Carmull-Rom，但它似乎正好符合我的需求。我很高兴维基百科文章甚至提供了Python实现的示例;-) - Franz

@Franz，正如所看到的，答案似乎符合自然立方样条插值。请查看此在线讲座，了解带有或不带局部控制（即您所称的本地支持）的插值样条的整个主题。 - Nikos M.