Bezier curve

bezier-curve.markdown

Bezier curve

A Pen by Andreas Borgen on CodePen.

License.

index.html

<script>console.clear();</script>
<script src="https://unpkg.com/vue@2"></script>
<script src="https://unpkg.com/drag-tracker@1"></script>
<script src="https://unpkg.com/@sphinxxxx/zoomable-svg@0.2"></script>


<h2>Bezier curve</h2>

<section id="app">
    <label id="t-marker">
        <span><i>t</i></span>
        <input type="range" v-model.number="svg.t" min="0" max="1" step=".001">
        <output>{{ svg.t.toFixed(3) }}</output>
    </label>
    <div id="config">
        <p></p>
        <label>
            <input type="radio" v-model.number="svg.approx" :value="false">
            <span>Curve</span>
        </label>
        <label>
            <input type="radio" v-model.number="svg.approx" :value="true">
            <span>Approximated polyline <i>({{ subcurves.length }} segments)</i></span>
        </label>
        <!--label>
            <span>...accuracy</span>
            <input type="range" v-model.number="svg.subdiv.accuracy" min="0" max="100">
            <output>{{ svg.subdiv.accuracy }}</output>
        </label-->
        <label>
            <span>...tolerance</span>
            <input type="range" v-model.number="svg.subdiv.tolerance" min="0" max=".2" step=".01">
            <output>{{ svg.subdiv.tolerance }}</output>
        </label>
        <label>
            <span>...max subdivisions</span>
            <input type="number" v-model.number="svg.subdiv.max" min="0">
        </label>
    </div>
    <div id="wrapper" ref="wrapper">
        <svg ref="svg" viewBox="-100 -100 500 500">
            <!--
                https://en.wikiversity.org/wiki/CAGD/B%C3%A9zier_Curves
                "The curve of the first derivative of a standard Bézier curve is known as a hodograph. If the curve passes through the origin of the hodograph, it corresponds to a cusp on the original curve."
            -->
            <path class="axes" d="M-200,0 h400 M0,-200 v400" />
            <bezier class="deriv" :bez="svg.curve.derivative()" :t="svg.t" :interactive="false" />

            <g class="divided">
                <bezier v-for="sub in subcurves" :bez="sub" :interactive="false" />
            </g>
            <polyline v-if="svg.approx" :points="subcurves.map(c => [c.a, c.d])" />
            <bezier :bez="svg.curve" :t="svg.t" :interactive="true" :class="{ hidecurve: svg.approx }" />
        </svg>
    </div>

    <!--details>
        <summary>Advanced</summary>
        <div>
            <label>
                <input type="radio" v-model="svg.divideByDist" :value="true">
                <span>Divide by distance</span>
            </label>
            <label>
                <input type="radio" v-model="svg.divideByDist" :value="false">
                <span>Divide by <i>t</i></span>
            </label>
            <label>
                <input type="checkbox" _model="debugSinglePath">
                <span>Single path</span>
            </label>
        </div>
    </details-->
</section>

script.js

/**
 * https://gamedev.stackexchange.com/questions/5373/moving-ships-between-two-planets-along-a-bezier-missing-some-equations-for-acce
 * https://gamedev.stackexchange.com/a/5427
 */
class Bezier {

    constructor(controls) {
        this.controls = controls;
    }
    get a() { return this.controls[0]; }
    get b() { return this.controls[1]; }
    get c() { return this.controls[2]; }
    get d() { return this.controls[3]; }

    pointAtT(t) {
        const _t = 1 - t,
              [a, b, c, d] = this.controls;

        const x =    _t * _t * _t * a[0]
               + 3 * _t * _t *  t * b[0]
               + 3 * _t *  t *  t * c[0]
               +      t *  t *  t * d[0];

        const y =    _t * _t * _t * a[1]
               + 3 * _t * _t *  t * b[1]
               + 3 * _t *  t *  t * c[1]
               +      t *  t *  t * d[1];

        return [x, y];
    }
    
    derivative() {
        const [a, b, c, d] = this.controls;
        function coordMath(u, v, expr) {
            return [expr(u[0], v[0]), expr(u[1], v[1])];
        }

        //https://en.wikipedia.org/wiki/B%C3%A9zier_curve
        //
        //  The derivative of the cubic Bézier curve with respect to t is
        //  B′(t) = 3(1−t)²(P1−P0) + 6(1−t)t(P2−P1) + 3t²(P3−P2)
        //
        //  A quadratic Bézier curve is (...)
        //  B(t)  =  (1−t)²(P0)    + 2(1−t)t(P1)    +  t²(P2)
        //
        //So, the derivate of a *cubic* Bezier curve (C0-C3) is a *quadratic* Bezier curve (Q0-Q2) with control points:
        //  Q0 = 3(C1 - C0)
        //  Q1 = 3(C2 - C1)
        //  Q2 = 3(C3 - C2)
        //
        const q0 = coordMath(b, a, (c1, c0) => 3 * (c1 - c0)),
              q1 = coordMath(c, b, (c2, c1) => 3 * (c2 - c1)),
              q2 = coordMath(d, c, (c3, c2) => 3 * (c3 - c2));
        //console.log('Q', q0, q1, q2);

        //For convenience, we want to present this as another cubic curve, so:
        //https://stackoverflow.com/questions/3162645/convert-a-quadratic-bezier-to-a-cubic-one
        const deriv = new Bezier([
            q0,
            coordMath(q0, q1, (q0, q1) => q0 + 2/3 * (q1 - q0)),
            coordMath(q2, q1, (q2, q1) => q2 + 2/3 * (q1 - q2)),
            q2,
        ]);
        return deriv;
    }

    //https://jeremykun.com/2013/05/11/bezier-curves-and-picasso/
    subdivide() {
        function midpoint(p, q) {
            return [(p[0] + q[0]) / 2, (p[1] + q[1]) / 2];
        }

        function midpoints(pointList) {
            const midpointList = new Array(pointList.length - 1);
            for (let i = 0; i < midpointList.length; i++) {
                midpointList[i] = midpoint(pointList[i], pointList[i + 1]);
            }
            return midpointList;
        }

        const points = this.controls,
              firstMidpoints = midpoints(points),
              secondMidpoints = midpoints(firstMidpoints),
              thirdMidpoints = midpoints(secondMidpoints);

        return [new Bezier([points[0], firstMidpoints[0], secondMidpoints[0], thirdMidpoints[0]]),
                new Bezier([thirdMidpoints[0], secondMidpoints[1], firstMidpoints[2], points[3]])];
    }
    
    //https://agg.sourceforge.net/antigrain.com/research/adaptive_bezier/index.html#toc0013
    isFlat(accuracy) {
        /* accuracy: 0 (sloppy) - ~100 (detailed) */

        const [xA, yA] = this.a,
              [xD, yD] = this.d;

        const dx = (xD - xA),
              dy = (yD - yA),
              minLen2 = (dx * dx + dy * dy),
              tol2 = minLen2 / accuracy**2;
        
        function closeEnough(p, offset) {
            const xTarget = xA + (dx * offset),
                  yTarget = yA + (dy * offset),
                  xErr = xTarget - p[0],
                  yErr = yTarget - p[1];
            
            const err2 = (xErr * xErr + yErr * yErr);
            return (err2 <= tol2);
        }

        //console.log('l', level);
        return (closeEnough(this.b, 1/3) && closeEnough(this.c, 2/3));
    }
    isFlat2(tolerance) {
        /* tolerance: 0 (detailed) - 1 (sloppy) */

        function vector(from, to) {
            return [to[0] - from[0], to[1] - from[1]];
        }
        function magn2(v) {
            return (v[0]**2 + v[1]**2);
        }
        function dot(v1, v2) {
            return (v1[0] * v2[0]) + (v1[1] * v2[1]);
        }
        //https://www.cuemath.com/geometry/angle-between-vectors/
        function cos2(v1, v2) {
            const d = dot(v1, v2),
                  c2 = (d * d) / (magn2(v1) * magn2(v2));
            return c2;
        }

        const [a, b, c, d] = this.controls,
              vAD = vector(a, d),
              vAB = vector(a, b),
              vAC = vector(a, c);
        
        //Check that both control points (B and C) are projected on (i.e. "in-between") the line segment AD,
        //and that they don't overlap (i.e. B should be closer to A, and C should be closer to D):
        //https://stackoverflow.com/a/3122532/1869660
        const lenAD2 = magn2(vAD),
              t1 = dot(vAB, vAD) / lenAD2,
              t2 = dot(vAC, vAD) / lenAD2;
        
        if((t1 < 0) || (t2 > 1) || (t1 > t2)) { return false; }
        
        //The curve is flat if the angle between AD/AB and DA/DC is small.
        //Dot products can be used to measure the cosine of an angle between vectors,
        //so here we'll check if the cosine (squared) is accordingly large:
        const tol2 = tolerance**2,
              cosB = cos2(vAB, vAD),
              errB = 1 - cosB;
        //console.log('cosB', cosB, errB, Math.acos(Math.sqrt(cosB)) * 180.0/Math.PI);
        if(errB > tol2) { return false; }
        
        const errC = 1 - cos2(vector(d, c), vector(d, a));
        if(errC > tol2) { return false; }
        
        //console.log('flat2');
        return true;
    }

    subcurves(/*accuracy = 100,*/tolerance = .01, level = 0, maxLevel = 10) {
        if ((level > maxLevel) || this.isFlat2(tolerance)) {
            return [this];
        } else {
            return this.subdivide().map(b => b.subcurves(tolerance, level + 1, maxLevel)).flat();
        }
    }
}


(function() {
    "use strict";

    //Global state model. Can be changed from within Vue or from the outside.
    const _svgState = {
        //size: [400, 400],
        curve: new Bezier(
            [[65, 178], [336, 201], [113, 456], [282, 348]]
            //[[202.1114044189453,190.51483154296875], [-110.42572021484375,136.91456604003906], [50.04252243041992,5.081179618835449], [-3.977078914642334,255.50296020507812]]
            //.map(([x, y]) => [x*100, y*100])
        ),
        t: .5,
        approx: true,
        subdiv: {
            accuracy: 10,
            tolerance: .1,
            max: 8,
        },
    };


    Vue.component('drag-node', {
        template: '<circle data-draggable @dragging="onDragging" :cx="absCoord[0]" :cy="absCoord[1]" :r="r" />',
        props: {
            coord: Array,
            //If 'coord' is relative to some other point:
            offsetCenter: Array,

            r: {
                default: 16,
            }
        },
        model: {
            prop: 'coord',
            event: 'do_it',
        },
        computed: {
            absCoord() {
                const point = this.coord,
                      center = this.offsetCenter,
                      absCoord = center ? [ point[0] + center[0], point[1] + center[1] ]
                                        : point;
                return absCoord;
            },
        },
        methods: {
            onDragging(e) {
                const point = e.detail.pos,
                      center = this.offsetCenter,
                      relCoord = center ? [ point[0] - center[0], point[1] - center[1] ]
                                        : point;
                this.$emit('do_it', relCoord);
            },
        },
    });

    Vue.component('connector', {
        template: '<line class="connector" :x1="start[0]" :y1="start[1]" :x2="end[0]" :y2="end[1]" />',
        props: ['start', 'end'],
    });

    Vue.component('bezier', {
        template:
`<g class="bezier">
    <circle class="t-marker" v-if="tPoint" :cx="tPoint[0]" :cy="tPoint[1]" />
    <path :d="pathData" />
    <g v-if="interactive" class="controls">
        <connector :start="bez.a" :end="bez.b" />
        <connector :start="bez.c" :end="bez.d" />
        <drag-node class="control" v-model="bez.controls[0]"  />
        <drag-node class="control" v-model="bez.controls[1]" _offsetCenter="bez.a" />
        <drag-node class="control" v-model="bez.controls[2]" _offsetCenter="bez.d" />
        <drag-node class="control" v-model="bez.controls[3]" />
    </g>
    <g v-else class="controls">
        <connector :start="bez.a" :end="bez.b" />
        <connector :start="bez.c" :end="bez.d" />
    </g>
</g>`,
        props: ['bez', 't', 'interactive'],
        data() {
            return {
            }
        },
        computed: {
            pathData() {
                const bez = this.bez;
                return `M${bez.a} C${bez.b} ${bez.c} ${bez.d}`;
            },
            tPoint() {
                const t = this.t;
                if(t || (t === 0)) {
                    return this.bez.pointAtT(t);
                }
            },
        },
    });

    new Vue({
        el: '#app',
        data: {
            svg: _svgState,
        },
        computed: {
            subcurves() {
                //const subs = this.svg.curve.subcurves(this.svg.subdiv.accuracy, 1, this.svg.subdiv.max);
                const subs = this.svg.curve.subcurves(this.svg.subdiv.tolerance, 1, this.svg.subdiv.max);
                return subs;
            }
        },
        watch: {
            'svg.curve.controls': function(nu, old) {
                //console.log('cc', ''+newVal);
            }
        },

        mounted() {
            console.log('MTD');
            const svg = this.$refs['svg'];

            dragTracker({
                container: svg,
                selector: '[data-draggable]',
                callback: (node, pos) => {
                    //Transform to SVG coordinates:
                    //https://www.sitepoint.com/how-to-translate-from-dom-to-svg-coordinates-and-back-again/
                    const svgBounds = svg.getBoundingClientRect(),
                          screenCoord = svg.createSVGPoint();
                    screenCoord.x = pos[0] + svgBounds.left;
                    screenCoord.y = pos[1] + svgBounds.top;

                    const svgCoord = screenCoord.matrixTransform(svg.getScreenCTM().inverse()),
                          pos2 = [svgCoord.x, svgCoord.y];

                    //var event = new CustomEvent('dragging', { detail: { pos } });
                    var event = document.createEvent('CustomEvent');
                    event.initCustomEvent('dragging', true, false, { pos: pos2 });

                    node.dispatchEvent(event);
                },
            });

            Vue.nextTick(() => {
                zoomableSvg(svg, {
                    container: this.$refs['wrapper'],
                    onChanged: function() {
                        const zoomer = this;
                        svg.style.setProperty('--screen-px', 1 / zoomer.getZoom());
                    },
                });
            });
        },

        methods: {
        },
    });

})();

style.scss

body {
    display: flex;
    margin: 0;
    min-height: 100vh;
    flex-flow: column nowrap;
    align-items: center;
    font-family: Georgia, sans-serif;
    
    h2 {
        font-size: 1.1em;
        text-align: center;
    }
    input {
        font-size: inherit;
    }
}

#app {
    width: 100%;
    padding: 0 1em;
    box-sizing: border-box;

    display: flex;
    flex-flow: column nowrap;
    gap: .5em;
    
    summary, label {
        cursor: pointer;
    }
}

#t-marker, #config {
    position: relative;
    z-index: 1;
}
#t-marker {
    display: flex;
    gap: 1ch;
    
    input {
        flex: 1 1 auto;
    }
}
#config {
    align-self: start;

    label {
        display: block;
        
        input[type="number"] {
            width: 3em;
        }
    }
}

#wrapper {
    position: absolute;
    top:0; left:0; bottom:0; right:0;
}
svg {
    --screen-px: 1;

    display: block;
    width: 100%;
    height: 100%;

    path, polyline, line, circle {
        fill: none;
        stroke-width: 2;
        vector-effect: non-scaling-stroke;
    }
    
    path, polyline {
        stroke: black;
    }
    
    .axes {
        stroke: lightskyblue;
    }
    
    .connector, .control {
        stroke: dodgerblue;
        stroke-dasharray: 8;
    }

    .control {
        r: calc(var(--screen-px) * 16);
        stroke-dasharray: 6 4;
        fill: transparent;
        cursor: move;
    }
    .t-marker {
        r: calc(var(--screen-px) * 12);
        fill: gold;
        fill-opacity: .5;
    }
    
    .hidecurve path {
        stroke: none;
    }
    
    .divided {
        pointer-events: none;
        
        .bezier {
            color: lime;
            &:nth-child(2n) {
                color: red;
            }

            path {
                stroke: currentColor;
                stroke-opacity: .25;
                stroke-width: 8;
                stroke-linecap: round;
            }
            .connector {
                stroke: currentColor;
                stroke-width: 6;
                stroke-dasharray: none;
            }
        }
    }
    
    .deriv {
        path {
            stroke: silver;
        }
        line {
            stroke: #eee;
            stroke-dasharray: none;
        }
    }
}