绘制路径点简化/减少JavaScript

Question

我们正在开发iOS和Android的绘图应用程序.我使用立方二次曲线绘制平滑曲线,因为在移动设备(主要是焊盘)上绘制立方Bézier曲线的速度很慢.

用很多点绘制长二次曲线在垫中仍然很慢,所以我试图减少我必须在画布上绘制的点以加快绘图.

我试过了,

1. Catmull-Rom splines
2. 拉默 - 道格拉斯 - 普克

但它们适用于三次曲线,而且对于四曲线并没有正常工作.

四边形曲线是否有任何算法或技术？可以进行任何其他优化以加速路径绘制？

Answer 1

您可以递归细分样条线段,直到它们几乎是一条直线.

功能划分(Ç:曲线,MAXDEPTH:整数)
开始
    ,如果 MAXDEPTH ≤1 或折线-长度(Ç)≤1px的或 StraightLineMeasure(ç)<ε 然后
        返回列表-单(C ^)
    端
    C1,C2 ←拆分(C ^)
    返回 List-Concat(细分(C1,maxDepth - 1),细分(C2,maxDepth - 1))
结束

其中
Polyline-Length计算控制点形成的多义线的长度.
StraightLineMeasure对于一条直线返回零,对于几乎直线返回一个小数字.
Split返回两组控制点,每组控制点代表原始曲线的一半.

B样条很容易细分(pdf).

(点击这里进行演示)

这是javascript中的一个实现:

$(function() {
    var canvas = document.createElement('canvas');
    document.body.appendChild(canvas);

    var ctx = canvas.getContext('2d');
    ctx.fillStyle = '#f00';
    ctx.strokeStyle = '#f00';
    ctx.lineWidth = 1;

    var segments = BSplineSegment.FromBSpline([
        new Vector(10, 10),
        new Vector(110, 10),
        new Vector(110, 110),
        new Vector(10, 110),
        new Vector(10, 10),
        new Vector(110, 10),
        new Vector(110, 110)
        ]);

    for (var i = 0; i < segments.length; i++) {
        var subsegments = segments[i].subdivide(30);
        for (var j = 0; j < subsegments.length; j++) {
            var bss = subsegments[j];
            ctx.fillRect(bss.p1.x, bss.p1.y, 1, 1);
        }
    }

    var segment = new BSplineSegment(
        new Vector(110, 10), new Vector(210, 10),
        new Vector(110, 110), new Vector(210, 110));
    subsegments = segment.subdivide(50);
    for (var j = 0; j < subsegments.length; j++) {
        var bss = subsegments[j];
        ctx.fillRect(bss.p1.x, bss.p1.y, 1, 1);
    }
});

function Vector(x, y) {
    this.x = x;
    this.y = y;
}

Vector.prototype = {
    lengthSquared: function() {
        return this.x * this.x + this.y * this.y;
    },
    length: function() {
        return Math.sqrt(this.lengthSquared());
    },
    add: function(other) {
        return new Vector(this.x + other.x, this.y + other.y);
    },
    sub: function(other) {
        return new Vector(this.x - other.x, this.y - other.y);
    },
    mul: function(scale) {
        return new Vector(this.x * scale, this.y * scale);
    },
    div: function(scale) {
        return new Vector(this.x / scale, this.y / scale);
    },
    cross: function(other) {
        return this.x * other.y - this.y * other.x;
    },
};


function BSplineSegment(p0, p1, p2, p3) {
    this.p0 = p0;
    this.p1 = p1;
    this.p2 = p2;
    this.p3 = p3;
};

BSplineSegment.FromBSpline = function(pts) {
    var n = pts.length;
    var segments = [];
    for (var i = 3; i < n; i++) {
        segments.push(new BSplineSegment(pts[i - 3], pts[i - 2], pts[i - 1], pts[i]));
    }
    return segments;
};

BSplineSegment.prototype = {
    polylineLength: function() {
        return this.p2.sub(this.p1).length();
    },
    straightLineMeasure: function() {
        var det0 = this.p1.cross(this.p2);
        var det1 = det0 + this.p2.cross(this.p0) + this.p0.cross(this.p1);
        var det2 = det0 + this.p2.cross(this.p3) + this.p3.cross(this.p1);
        return (Math.abs(det1) + Math.abs(det2)) / this.p2.sub(this.p1).length();
    },
    split: function() {
        var p0 = this.p0.add(this.p1).mul(0.5);
        var p1 = this.p0.add(this.p1.mul(6)).add(this.p2).mul(0.125);
        var p2 = this.p1.add(this.p2).mul(0.5);
        var p3 = this.p1.add(this.p2.mul(6)).add(this.p3).mul(0.125);
        var p4 = this.p2.add(this.p3).mul(0.5);
        return [new BSplineSegment(p0, p1, p2, p3), new BSplineSegment(p1, p2, p3, p4)];
    },
    subdivide: function(maxLevels) {
        if (maxLevels <= 0 || this.polylineLength() < 1.0 || this.straightLineMeasure() < 1.0) {
            return [this];
        }
        else {
            var children = this.split();
            var left = children[0].subdivide(maxLevels - 1);
            var right = children[1].subdivide(maxLevels - 1);
            return left.concat(right);
        }
    }
};?