Question about splitting splines

[Michael-F-Bryan]

I wasn't sure whether this would be the most appropriate way to get in contact, but I'm wondering if you ever looked into splitting splines as part of your research?

At $JOB we develop a CAD system and a common task is to break an entity into two at a particular point. For example, say the first half generates the desired shape perfectly, but you don't need the rest. This is easy enough to implement for regular shapes like lines and arcs, and even ellipse segments, but I wasn't sure how it'd be implemented for a B-Spline or Bezier Curve.

Have you come across anything in the literature around this sort of operation?

[nanjizal]

With Quadratic Bezier curves ( 3 point rather than 4 point Beziers ) this is not too hard. ( explained with haxe code, it's my goto code language ). For instance consider this Div generated Bezier Chain ( you can drag the coloured points ). https://rawgit.com/nanjizal/divtasticDemo/master/bezier_chain/BezierChain.html It's an old experiment that helps visualise what I am talking about ( the render approach is not sensible ). Now instead of the coloured control points that are external to the curve you can define a quadratic Bezier by a point that passes through the curve. So in my Trilateral library I have quadThru function:

// assumes in this code that x0, y0 is stored by your pen
// ie: your last draw position, and used internally by quadTo
    public inline
    function quadThru( x1: Float, y1: Float, x2: Float, y2: Float ): Void {
        var newx = 2*x1 - 0.5*( x + x2 );
        var newy = 2*y1 - 0.5*( y + y2 );
        return quadTo( newx, newy, x2, y2 );
    }

A quadratic bezier ( quadTo ) can be drawn as a set of short lines using a while loop over both axis.

// 
    public static inline
    function quadratic ( t: Float, s: Float, c: Float, e: Float ): Float {
        var u = 1 - t;
        return Math.pow( u, 2 )*s + 2*u*t*c + Math.pow( t, 2 )*e;
    }

Where t is from 0 to 1 over the Quadratic Bezier curve, s is the start position of x or y, and c the control point of x or y and e the end point of x or y ( likely in z as well ).
Essentially something like.

// some details omitted for simplicity.
        var t = step;
        while( t < 1. ){
            p[ l++ ] = quadratic( t, ax, bx, cx );
            p[ l++ ] = quadratic( t, ay, by, cy );
            t += step;
        }

So to define a partial path you would just need to iterate from 0 to 1 along the ordinary Quadratic Bezier path until you reach the nearest point to the point where you wish to stop your curve. Typical use case, when a user clicks on screen to select a new end point - to only calculate part of the segment we can work out the closest x and y for t using Pythagorus.

        var nearest: { t: Float, delta: Float } = { t: 0: delta: 1000000000 };
        var t = step;
        while( t < 1. ){
            qx = quadratic( t, ax, bx, cx );
            qy = quadratic( t, ay, by, cy );
            dx = qx - mouseX;
            dy = qy - mouseY;
            delta = dx*dx + dy*dy;
            if( dist2 < nearest.delta ) nearest = { t: t, delta: delta };
            t += step;
        }
        trace( 'new end point = ' + nearest.t );

So the new end point is easy to calculated based on the users mouse selection to be:

            var newEx = quadratic( delta.t, ax, bx, cx );
            var newEy = quadratic( delta.t, ay, by, cy );

Now if we then calculate our quadThru control point by choosing one halfway between the new end point and the start.

            var halfNewT =  delta.t/2;
            var newCx = quadratic( halfNewT, ax, bx, cx );
            var newCy = quadratic( halfNewT, ay, by, cy );

So we can now draw our new partial curve.

      quadThru( newCx, newCy, newEx, newEy );

Within the quadThru we generate the new control points for ordinary Quadratic Bezier these could be extracted for normal use instead.

var cx_ = 2*newCx - 0.5*( x + newEx );
var cy_ = 2*newCy - 0.5*( y + newEy );

so

quadTo( cx_, cy_, newEx, newEy );

Obviously exactly the same approach could be used to create a new start point and controlThru point, and perhaps there are much simpler approaches.

Some of the code related is within my trilateral experiment library although not the splitting part specifically: https://github.com/nanjizal/Trilateral/blob/master/src/trilateral/geom/Algebra.hx I think there are equations around for constructing Cubic Beziers from two Quadratic Beziers but you would need to google for that.

Hopefully this approach is useful for at least one case, but I am sure that Ralph could implement more flexible solutions for all his curve code, I just thought for Beziers the approach is not difficult, unfortunately I don't have link to the quadThru derivation likely mine is based on some old actionscript code I found on a blog.