3

iOS、Android向けのお絵描きアプリを開発中です。3次ベジエ曲線はモバイルデバイス（ほとんどのパッド）での描画が遅いため、滑らかな曲線を描くために3次二次曲線を使用しています。

多くのポイントを含む長い二次曲線の描画はまだパッドで遅いので、描画を高速化するためにキャンバスにプロットする必要があるポイントを削減しようとしています。

私が試してみました、

  1. Catmull-Rom スプライン
  2. ラーマー・ダグラス・ペイカー

しかし、それらは 3 次曲線用であり、4 次元曲線では適切に機能していません。

クワッド カーブのアルゴリズムやテクニックはありますか? パスの描画を高速化するために他の最適化を行うことはできますか?

4

1 に答える 1

5

ほぼ直線になるまで、スプライン セグメントを再帰的に分割できます。

function Subdivide ( C : Curve, maxDepth : int )
begin
    if maxDepth ≤ 1 or Polyline-Length( C ) ≤ 1px or StraightLineMeasure( C ) < ϵ then
        return List-Single( C )
    end
    C1 , C2 ← Split( C )
    return List-Concat( Subdivide( C1 , maxDepth - 1 ), Subdivide( C2 , maxDepth - 1 ) )
end

ここで、
Polyline-Lengthは、制御点によって形成されるポリラインの長さを計算します。
StraightLineMeasureは、直線の場合は 0 を返し、ほぼ直線の場合は小さい数を返します。
Splitは、それぞれが元の曲線の半分を表す 2 セットのコントロール ポイントを返します。

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);
        }
    }
};​
于 2012-06-18T18:03:06.750 に答える