Algorithm behind Inkscape's auto-smooth nodes

Question

I am generating smooth curves by interpolating (lots of) points. I want to have local support (i.e. only few points determine the smooth curve locally), so I do not want to use a classical interpolation spline. Bezier curves to me would be a natural solution and Inkscape's auto-smooth nodes (http://tavmjong.free.fr/INKSCAPE/MANUAL/html/Paths-Editing.html#Paths-Node-AutoSmooth) do pretty well what I want to have. But I have trouble finding the implementation in the source or some reference to the underlying algorithm.

Is anybody here aware of the algorithm or familiar enough with Inkscape's source so they can point me in the right direction?

For context: I am calculating a smooth path for a pen plotter but can not wait to have all supporting points available.

Cooe

so you want algorithm for drawing bezier curves? – Assisi

Drawing from known control points is clear to me (by Casteljau or direct plynomial evaluation). What I want to find out is how Inkscape choses the “interior” control points when an (interpolating) point is defined as “auto-smooth”. – Cooe

do you know how to connect multiple cubic bezier curves to achieve one smooth curve that passes through given points? – Assisi

Answer 1

The code is here and I've implemented a version in Python using the svgpathtools library in a gist

Here is a diagram showing the method.

Given three points a, b, and c where b is auto-smooth and b has two control points u and v, then:

• Let x be a unit vector perpendicular to the the angle bisector of ∠abc
• u = b - x * 1/3|ba|
• v = b + x * 1/3|bc|

As far as I know, there is nothing special about the constant 1/3 and you could vary it to have larger or smaller curvature.

UPDATE: while watching this excellent video I re-encountered this 1/3 constant and indeed it is special and comes from a Hermite spline. It is briefly mentioned on the Cubic Hermite Spline Wikipedia page. Editing the auto-smooth control nodes acts to edit the Hermite spline velocity vectors.

Kamilah

Wow, this video is really really excellent. Thanks for sharing! – Cooe

For those not so comfortable with math notations: Tangent in: -(nextPos - prevPos).normalized * Distance(curPos, prevPos) / 3 Tangent out: (nextPos - prevPos).normalized * Distance(curPos, nextPos) / 3 – Gravedigger

Answer 2

Per @fang's comment below. It may be beter to use Catmull-Rom Interpolating Spline instead, which both interpolates and has local control property. See more here

For stitching together cubic bezier curves that interpolate (more like natural cubic splines) see below original answer.

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

The following is javascript-like pseudo-code that computes a series of (up to) cubic bezier curves that together combine to achieve one smooth curve passign through given points. Note bezier in below code is assumed to be a function that computes (the polynomial form of) a cubic bezier through given control points (which is already known algorithm). Note2 below algorithm is for 1d curves it is easily adjusted for 2d curves (ie compute x and y coordinates)

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;
}

see also related post

Adapted code from here

Assisi

Thank you! This is an interesting solution, but it does not have local support. So I have to know all Points to solve for any control points. In fact, I strongly suspect this algorithm gives the very same solution as does a spline interpolation, except it is in Bezier form. What the Inkscape seems to do differently is that it does not assume actual continuity in the derivative, but only geometric continuity (derivatives just parallel not identical) and uses the additional degrees of freedom to come up wirh a locally reasonable solution. – Cooe

@Cooe as far as I can see the source code of inkscape, it uses cubic bezier curves and piecewise bezier curves as well. The examples of auto-smooth nodes suggest that a large part of the curve is adjusted when even one point changes. It is reasonable to do so else continuity and smoothness could not be achieved. I presume there is nothing stopping you to update only a part of the bezier when a single point changes. For example for 5 points p1 to p5 if p3 changes you can re-run the algortihm only for points p2 p3 p4 and update only the affected segments while the rest remain the same. IMO – Assisi

The link you provided actually describes the so-called "natural cubic spline", which indeed does not have the property of "local support". The Inkscape's auto-smooth node looks more like Catmull-Rom spline to me and Carmull-Rom spline does have local support property. – Taffy

@Taffy Thank you very much for the decisive keyword, your comment actually answers my question! I've never come across Carmull-Rom, but it seems to do exactly what I need. Am pretty delighted the wikipedia article even features a python implementation ;-) – Cooe

@Franz, indeed as it seems answer confroms to natural cubic spline. Check out the whole subject of interpolationg splines with and without local control (what you call local support) on this online lecture – Assisi