2

輪郭を描いた線を描くための高速なアルゴリズムを探しています。このアプリケーションでは、アウトラインの幅は1ピクセルで十分です。デフォルトでもオプションでも、共通のポイントを共有している場合は、2本の線をシームレスに接続できるはずです。

アスキーアートを失礼しますが、これはおそらくそれを実証するための最良の方法です。

通常の線：

 ##
   ##
     ##
       ##
         ##
           ##

「アウトライン」行：

 **
*##**
 **##**
   **##**
     **##**
       **##**
         **##*
           **

私はdsPIC33FJ128GP802に取り組んでいます。これは、40 MIPS（1秒あたり100万命令）が可能な小型のマイクロコントローラー/デジタルシグナルプロセッサーです。整数演算のみが可能です（加算、減算、乗算：除算は可能ですが、約19サイクルかかります）。 OSDレイヤーを同時に処理し、処理時間の3〜4 MIPSのみが計算に使用できるため、速度が重要です。ピクセルは、黒、白、透明の3つの状態を占めます。ビデオフィールドは192x128ピクセルです。これは、オープンソースプロジェクトであるSuper OSD用です：http ：//code.google.com/p/super-osd/

私が考えた最初の解決策は、最初のパスで輪郭が描かれたピクセルと2番目のパスで通常のピクセルを持つ3x3の長方形を描画することでしたが、すべてのピクセルについて少なくとも3ピクセルが上書きされ、それらの描画に費やされた時間が無駄になるため、これは遅くなる可能性があります。だから私はもっと速い方法を探しています。各ピクセルのコストは約30サイクルです。100ピクセルの長さの線を描画するには、ターゲットは<50、000サイクルです。

4

2 に答える 2

1

私はこれを提案します（C /擬似コードミックス）：

void draw_outline(int x1, int y1, int x2, int y2)
{
    int x, y;
    double slope;

    if (abs(x2-x1) >= abs(y2-y1)) {
        // line closer to horizontal than vertical
        if (x2 < x1) swap_points(1, 2);
        // now x1 <= x2
        slope = 1.0*(y2-y1)/(x2-x1);
        draw_pixel(x1-1, y1, '*');
        for (x = x1; x <= x2; x++) {
            y = y1 + round(slope*(x-x1));
            draw_pixel(x, y-1, '*');
            draw_pixel(x, y+1, '*');
            // here draw_line() does draw_pixel(x, y, '#');
        }
        draw_pixel(x2+1, y2, '*');
    }
    else {
        // same as above, but swap x and y
    }
}

編集：連続する線をシームレスに接続したい場合は、最初のパスですべての輪郭を描画し、次に線を描画する必要があると思います。上記のコードを編集して、アウトラインのみを描画しました。draw_line()関数はまったく同じですが、4つではなく1つのシングル を draw_pixel(x, y, '#');使用しdraw_pixel(..., ..., '*');ます。そして、あなたはただ：

void draw_polyline(point p[], int n)
{
    int i;

    for (i = 0; i < n-1; i++)
        draw_outline(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
    for (i = 0; i < n-1; i++)
        draw_line(p[i].x, p[i].y, p[i+1].x, p[i+1].y);
}
于 2010-10-12T20:23:38.323 に答える
0

私のアプローチは、ブレゼンハムを使用して複数の線を引くことです。アスキーアートを見ると、アウトラインラインはブレゼンハムラインとまったく同じで、上下に1ピクセルだけシフトしていることに気付くでしょう。さらに、最初のポイントの左側と最後のポイントの右側に1ピクセルあります。 。

一般的なバージョンの場合、ラインがフラットか急勾配かを判断する必要があります。つまり、abs(y1 - y0) <= abs(x1 - x0)。急なラインの場合、アウトラインは左右に1ピクセルシフトされ、終了ピクセルは開始点の上と終了点の下にあります。

ラインピクセルごとに一度にラインと2つのアウトラインピクセルを描画することで、これを最適化する価値があります。ただし、シームレスなアウトラインが必要な場合、最も簡単な解決策は、最初にすべてのアウトラインを描画し、次に線自体を描画することです。これは、「3ピクセルブレゼンハム」最適化では機能しません。

于 2015-03-01T13:31:53.543 に答える