Split one quadratic bezier curve into two

3
votes

So I have an imaginary circle divided into multiple parts (I use 8 for simplicity, but in the end, I would like to divide it to 16 or 32 parts).

Then I have N number of quadratic bezier curves, that is between 2 nearest segments. It may rest upon the circle or further from the center, but not nearer than the circle.

I know how to find, what in witch line I should look for intersection in, but I do not know how to split it into two parts... I know, that if I looked for intersection of the line and curve I should get the point that the previous curve should end and the next should start, and that by derivation I may be able to get the vector, but I do not know how to do it.

Example image where I have only 8 parts for easier problem solving.

smaller example of problem

The point is, to make "progress" bar using bezier curves. Side note: The curves will change every frame, as they are part of music visualization.

If there is a better way to spit color a curve, I am all for it!

3
javascriptmathcanvasbezier
That's far from being perfect, but it may give you an idea : jsfiddle.net/4ekgwLwo For the spline calculation see stackoverflow.com/questions/17083580/… – Kaiido
@Kaiido This is awesome way to do it! love it ;) If you make as answer I will accept it. – Akxe
@Kaiido very true indeed... it is up only from IE11... Anyway as I need a AudioContext I have dropped IE since start :D – Akxe
be aware that if you want to do the color using linear distance (e.g. it fills up 100px every second, or you need a true progress bar) then regular curve splitting will be insufficient, as you will not be splitting at a linear distance. at 25%, 50% or 75% of the progress, plain curve splitting will almost never yield a subcurve that is 25%, 50% or 75% of the full curve. Of course your users won't know the true progress, so it's probably fine, but it's an important fact to remember about Bezier curves. – Mike 'Pomax' Kamermans
@Mike'Pomax'Kamermans Yeah I figured this a bit ago... :/ but the globalCompositeOperation seems great... – Akxe

3 Answers

7
votes

Spliting cubic and quadratic Beziers

Splitting a bezier is relatively easy. As there is already an answer I will just copy the functions needed to split a single bezier, cubic or quadratic at a position along its path range from 0 to 1. The function Bezier.splitAt takes a position (0 to 1) and depending on start = true returns the from 0 to position or the if start = false returns the bezier from position to 1. It will handle both 2nd order (quadratic) and 3rd order (cubic) Beziers

Example usage

var bezier = createBezierCubic( 146, 146, 134, 118, 184, 103, 217, 91 );
// split in two
var startingHalf = bezier.splitAt(0.5, true);
var endingHalf = bezier.splitAt(0.5, false);
// split into four. 
var quart1 = startingHalf.splitAt(0.5, true)
var quart2 = startingHalf.splitAt(0.5, false)
var quart3 = endingHalf.splitAt(0.5, true)
var quart4 = endingHalf.splitAt(0.5, false)

// getting a segment
var startFrom = 0.3;
var endAt = 0.8;
var section = bezier.splitAt(startFrom, false).splitAt((endAt - startFrom) / (1 - startFrom), true);

The bezier is made up of a start and end point p1, p2 and one or two control points cp1, cp2. If the bezier is 2nd order then cp2 is undefined. The points are Vec and take the from Vec.x, Vec.y

To render a 2nd order

ctx.moveTo(bezier.p1.x, bezier.p1.y);
ctx.quadraticCurveTo(bezier.cp1.x, bezier.cp1.y, bezier.p2.x, bezier.p2.y);

To render the 3rd order

ctx.moveTo(bezier.p1.x, bezier.p1.y);
ctx.bezierCurveTo(bezier.cp1.x, bezier.cp1.y, bezier.cp2.x, bezier.cp2.y, bezier.p2.x, bezier.p2.y);

The code with dependencies.

As you are all programmers see the code for more info in usage. Warning there could be typos as this has been pulled from a more extensive geometry interface.

var geom = (function(){
    function Vec(x,y){ // creates a vector
        if(x === undefined){
            x = 1;
            y = 0;
        }
        this.x = x;
        this.y = y;
    }
    Vec.prototype.set = function(x,y){
        this.x = x;
        this.y = y;
        return this;
    };
    // closure vars to stop constant GC
    var v1 = Vec();
    var v2 = Vec();
    var v3 = Vec();
    var v4 = Vec();
    var v5 = Vec();
    const BEZIER_TYPES  = {
        cubic : "cubic",
        quadratic : "quadratic",
    };

    // creates a bezier  p1 and p2 are the end points as vectors.
    // if p1 is a string then returns a empty bezier object.
    //          with the type as quadratic (default) or cubic
    //  cp1, [cp2] are the control points. cp2 is optional and if omitted will create a quadratic 
    function Bezier(p1,p2,cp1,cp2){
        if(typeof p1 === 'string'){
            this.p1 = new Vec();
            this.p2 = new Vec();
            this.cp1 = new Vec();
            if(p1 === BEZIER_TYPES.cubic){
                this.cp2 = new Vec();
            }
        }else{
            this.p1 = p1 === undefined ? new Vec() : p1;
            this.p2 = p2 === undefined ? new Vec() : p2;
            this.cp1 = cp1 === undefined ? new Vec() : cp1;
            this.cp2 = cp2;
        }
    }    
    Bezier.prototype.type = function(){
        if(this.cp2 === undefined){
            return BEZIER_TYPES.quadratic;
        }
        return BEZIER_TYPES.cubic;
    }
    Bezier.prototype.splitAt = function(position,start){ // 0 <= position <= 1 where to split. Start if true returns 0 to position and else from position to 1
        var retBezier,c;
        if(this.cp2 !== undefined){ retBezier = new Bezier(BEZIER_TYPES.cubic); }
        else{ retBezier = new Bezier(BEZIER_TYPES.quadratic); }
        v1.x = this.p1.x;
        v1.y = this.p1.y;
        c = Math.max(0, Math.min(1, position));  // clamp for safe use in Stack Overflow answer
        if(start === true){
            retBezier.p1.x = this.p1.x;
            retBezier.p1.y = this.p1.y;            
        }else{
            retBezier.p2.x = this.p2.x;
            retBezier.p2.y = this.p2.y;            
        }
        if(this.cp2 === undefined){ // returns a quadratic
            v2.x = this.cp1.x;
            v2.y = this.cp1.y;
            if(start){
                retBezier.cp1.x = (v1.x += (v2.x - v1.x) * c);
                retBezier.cp1.y = (v1.y += (v2.y - v1.y) * c);
                v2.x += (this.p2.x - v2.x) * c;
                v2.y += (this.p2.y - v2.y) * c;
                retBezier.p2.x = v1.x + (v2.x - v1.x) * c;
                retBezier.p2.y = v1.y + (v2.y - v1.y) * c;
                retBezier.cp2 = undefined;
            }else{
                v1.x += (v2.x - v1.x) * c;
                v1.y += (v2.y - v1.y) * c;
                retBezier.cp1.x = (v2.x += (this.p2.x - v2.x) * c);
                retBezier.cp1.y = (v2.y += (this.p2.y - v2.y) * c);
                retBezier.p1.x = v1.x + (v2.x - v1.x) * c;
                retBezier.p1.y = v1.y + (v2.y - v1.y) * c;
                retBezier.cp2 = undefined;
            }
            return retBezier;
        }
        v2.x = this.cp1.x;
        v3.x = this.cp2.x;
        v2.y = this.cp1.y;
        v3.y = this.cp2.y;
        if(start){
            retBezier.cp1.x = (v1.x += (v2.x - v1.x) * c);
            retBezier.cp1.y = (v1.y += (v2.y - v1.y) * c);
            v2.x += (v3.x - v2.x) * c;
            v2.x += (v3.x - v2.x) * c;
            v2.y += (v3.y - v2.y) * c;
            v3.x += (this.p2.x - v3.x) * c;
            v3.y += (this.p2.y - v3.y) * c;
            retBezier.cp2.x = (v1.x += (v2.x - v1.x) * c);
            retBezier.cp2.y = (v1.y += (v2.y - v1.y) * c);
            retBezier.p2.y = v1.y + (v2.y - v1.y) * c;
            retBezier.p2.x = v1.x + (v2.x - v1.x) * c;
        }else{
            v1.x += (v2.x - v1.x) * c;                
            v1.y += (v2.y - v1.y) * c;
            v2.x += (v3.x - v2.x) * c;
            v2.y += (v3.y - v2.y) * c;
            retBezier.cp2.x = (v3.x += (this.p2.x - v3.x) * c);
            retBezier.cp2.y = (v3.y += (this.p2.y - v3.y) * c);
            v1.x += (v2.x - v1.x) * c;
            v1.y += (v2.y - v1.y) * c;
            retBezier.cp1.x = (v2.x += (v3.x - v2.x) * c);
            retBezier.cp1.y = (v2.y += (v3.y - v2.y) * c);
            retBezier.p1.x = v1.x + (v2.x - v1.x) * c;
            retBezier.p1.y = v1.y + (v2.y - v1.y) * c;
        }
        return retBezier;              
    }

    return {
        Vec : Vec,
        Bezier : Bezier,
        bezierTypes : BEZIER_TYPES,
    };
})();

// helper function 
// Returns second order quadratic from points in the same order as most rendering api take then
// The second two coordinates x1,y1 are the control points
function createBezierQuadratic(x, y, x1, y1, x2, y2){
    var b = new geom.Bezier(geom.bezierTypes.quadratic);
    b.p1.set(x, y);
    b.p2.set(x2, y2);
    b.cp1.set(x1, y1);
    return b;
}
// Returns third order cubic from points in the same order as most rendering api take then
// The coordinates x1, y1 and x2, y2 are the control points
function createBezierCubic(x, y, x1, y1, x2, y2, x3, y3){
    var b = new geom.Bezier(geom.bezierTypes.cubic);
    b.p1.set(x, y);
    b.p2.set(x3, y3);
    b.cp1.set(x1, y1);
    b.cp2.set(x2, y2);
    return b;
}
2
votes

[Edit]

The algo for getting the length is still not working, it seems I forgot to calculate the last path, if someone wants to point me to the solution that would be very nice since I don't have time right now. (Otherwise, I'll try to find it in the weekend...)

Since you don't need support for older IE (<=11), one easy way is to use the setLineDash() method.

This will allow you to only draw your path once, and to only have to get the full length of your path.

To do so, I use a js implementation of this algo made by tunght13488. There may be better implementations of it.

var ctx = c.getContext('2d');
var percent = 90;
var length = 0;

// all our quadraticCurves points
var curves = [
  [146, 146, 134, 118, 184, 103],
  [217, 91, 269, 81, 271, 107],
  [263, 155, 381, 158, 323, 173],
  [279, 182, 314, 225, 281, 223],
  [246, 219, 247, 274, 207, 236],
  [177, 245, 133, 248, 137, 211],
  [123, 238, 10, 145, 130, 150]
];

// get the full length of our spline
curves.forEach(function(c) {
  length += quadraticBezierLength.apply(null, c);
});
// that's still not it...
length += quadraticBezierLength.apply(null,curves[curves.length-1]);

var anim = function() {

  var offset = (percent / 100) * length;

  ctx.clearRect(0, 0, c.width, c.height);
  ctx.beginPath();

  ctx.moveTo(133, 150);
  // draw our splines
  curves.forEach(function(c) {
    ctx.bezierCurveTo.apply(ctx, c);
  })
  ctx.closePath();

  // the non completed part
  ctx.strokeStyle = "gray";
  // this will make the part from 0 to offset non drawn
  ctx.setLineDash([0, offset, length]);
  ctx.stroke();

  // the completed part
  ctx.setLineDash([offset, length]);
  ctx.strokeStyle = "blue";
  ctx.stroke();

  percent = (percent + .25) % 100;
  requestAnimationFrame(anim);
}

// modified from https://gist.github.com/tunght13488/6744e77c242cc7a94859
function Point(x, y) {
  this.x = x;
  this.y = y;
}

function quadraticBezierLength(p0x, p0y, p1x, p1y, p2x, p2y) {
  var a = new Point(
    p0x - 2 * p1x + p2x,
    p0y - 2 * p1y + p2y
  );
  var b = new Point(
    2 * p1x - 2 * p0x,
    2 * p1y - 2 * p0y
  );
  var A = 4 * (a.x * a.x + a.y * a.y);
  var B = 4 * (a.x * b.x + a.y * b.y);
  var C = b.x * b.x + b.y * b.y;

  var Sabc = 2 * Math.sqrt(A + B + C);
  var A_2 = Math.sqrt(A);
  var A_32 = 2 * A * A_2;
  var C_2 = 2 * Math.sqrt(C);
  var BA = B / A_2;

  return (A_32 * Sabc + A_2 * B * (Sabc - C_2) + (4 * C * A - B * B) * Math.log((2 * A_2 + BA + Sabc) / (BA + C_2))) / (4 * A_32);
};

anim();
<canvas width="500" height="500" id="c"></canvas>
1
votes

To anyone still landing on this page, take a look at Bezier.js (https://github.com/Pomax/bezierjs), especially at the API: https://pomax.github.io/bezierjs/

You can extract a quadratic Bezier curve between t = 0.25 and t = 0.75 like so:

var curve = new Bezier(150,40 , 80,30 , 105,150);
var segment_curve = curve.split(0.25, 0.75);

context.moveTo(segment_curve.points[0].x, segment_curve.points[0].y);
context.quadraticCurveTo(segment_curve.points[1].x, segment_curve.points[1].y, segment_curve.points[2].x, segment_curve.points[2].y);
context.stroke();