2

Bresenham の線画アルゴリズムでエラー累積部分がどのように機能するかを理解するのに問題があります。

と があるx1としx2ます。簡単にするためx1 < x2に、 、y1 < y2、および と仮定しましょう。(x2 - x1) >= (y2 - y1)

線を引く単純な方法から始めましょう。次のようになります。

void DrawLine(int x1, int y1, int x2, int y2)
{
    float y = y1 + 0.5f;
    float slope = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x)
    {
        PlotPixel(x, (int)y);
        y += slope;
    }
}

もっとブレゼンハム風にして、y の整数部分と浮動小数点部分を分けてみましょう。

void DrawLine(int x1, int y1, int x2, int y2)
{
    int yi = y1;
    float yf = 0.5f;
    float slope = (float)(y2 - y1) / (x2 - x1);
    for (int x = x1; x <= x2; ++x)
    {
        PlotPixel(x, yi);
        yf += slope;
        if (yf >= 1.0f)
        {
            yf -= 1.0f;
            ++yi;
        }
    }
}

この時点で、乗算yfしslopeて2 * (x2 - x1)整数にすることができ、浮動小数点数はなくなります。という事は承知しています。

私が完全に理解していない部分は次のとおりです。

    if (yf >= 1.0f)
    {
        yf -= 1.0f;
        ++yi;
    }

それは実際にどのように機能しますか？なぜ 1.0 と比較してから減分するのですか?

Bresenham の基本的な質問は、次のようなものであることは知っています。現在ピクセルx, yを使用していて、次のピクセルを描画したい場合、または を選択する必要がありますx + 1, yかx + 1, y + 1? - その小切手が、この質問に答えるのにどのように役立つのか理解できません.

それをエラー用語と呼ぶ人もいれば、しきい値と呼ぶ人もいますが、それが何を表しているのかわかりません。

説明をいただければ幸いです。

4

2 に答える 2

2

Bresenham のライン ラスター化アルゴリズムは、すべての計算を整数演算で実行します。あなたのコードでは float 型を使用していますが、使用すべきではありません。

まず、線上にある 2 つのピクセルがわかっているとします。開始ピクセルと終了ピクセル。アルゴリズムが計算するのは、ラスタライズされた線が 2 つの入力ピクセルで開始および停止するように、線を近似するピクセルです。

次に、描画されるすべての線は、傾きが 0 ～ 0.5 の線の反射です。垂直線には特殊なケースがあります。アルゴリズムがこの入力に対して正しい場合は、ラスタライザーの開始状態を初期化して、ラインを正しくラスタライズする必要があります: 開始ピクセル (x, y)、Δx、Δy、および D 決定変数。

すべての線が左から右に描かれ、正の勾配が 0.5 以下であると想定できるため、問題は次のようになります。現在のピクセルの右または右と 1 ピクセル上にある次のラスタライズされたピクセルです。

ラスタライズされた線が実際の線からどれだけずれているかを追跡することで、この決定を下すことができます。そうするために、直線方程式は陰関数 F(x, y) = Δyx - Δxy + Δxb = 0 に書き直され、F(x + 1 y + 0.5) を繰り返し評価します。これには浮動小数点演算が必要なため、真の線の上にあるか、上にあるか下にあるかを特定することに集中します。したがって、F(x + 1 y + 0.5) = Δy - 0.5Δx と 2 を掛けると、2 * F(x + 1 y + 0.5) = 2Δy - Δx となります。これが最初の決定です。結果が 0 未満の場合は、x に 1 を追加し、y に 0 を追加します。

2回目以降の判定も同様で、誤差が累積されます。決定変数 D は 2Δy - Δx に初期化されます。D < 0 の場合、D = D + 2Δy; それ以外の場合は、y = y + 1 および D = D + 2(Δy - Δx) です。x 変数は常にインクリメントされます。

Jim Arvo はBresenham のアルゴリズムについて素晴らしい説明をしてくれました。

于 2016-02-16T03:45:43.713 に答える