CODEWITHSUNDEEP
bezierinkscapecubic-bezier
Franz
Franz

Reputation: 360

Algorithm behind Inkscape's auto-smooth nodes

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.

Upvotes: 5

Views: 1259

Answers (2)

aconz2
aconz2

Reputation: 346

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.

Upvotes: 5

Nikos M.
Nikos M.

Reputation: 8345

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

Upvotes: 1

Related Questions