1

与えられxlenた delta-xylenは delta-ylenは線の長さです なぜこのコードは:

//Bresenham implementation
float x = x0, y = y0;

if (slope < 1) {
    while (x < xlen) {
        paintpt(x, y));
         x += step;
        if (left.y > right.y) 
            y += slope * step;
        else 
            y -= slope * step;
   }
}

このコードより効率的ですか？

//Naive vector addition
int x = x0, y = y0;
float xinc = xlen / len, yinc = ylen / len;

for (float i = 0; i < len; i++) {
   paintpt(x, y);
   x += i * xinc;
   y += i * yinc;
}

（つまり、初期化は別として、明らかに。線の長さと方向だけが与えられており、勾配などを元に戻す必要があると仮定します。）

4

2 に答える 2

5

Bresenham アルゴリズムは、コンピューターが大きなクローゼットに収まった 60 年代に生まれました。その特徴は次のとおりです。

  • 浮動小数点演算なし、
  • 乗算/除算はありません。

当時は、整数の除算や乗算でさえ「高価」でした。「真の」ブレゼンハムの実装では、除算や乗算は行われず、浮動小数点演算は使用されません。あなたの実装は「false」です。ここで「本当の」ものをチェックしてください。

于 2013-09-18T09:25:55.943 に答える
3

1)x += i * xinc;これは整数に丸められた浮動小数点乗算です。xあなたからfinalまでのすべての整数を通過することを保証するものではありませんx。これは、ラインに穴が開いている可能性があることを意味します...

2) Bresenham の実装が間違っています。にステップを追加しませんx。x反復ごとにインクリメントしdelta_y、エラー カウンターに追加します。エラー カウンターが大きい場合は、エラー カウンターdelta_xをインクリメントyおよび減算delta_xします。

これは、delta_yが 0 より大きく より劣る線の説明ですdelta_x。他のすべての場合にローテーションを行います。

3) 効率のために: これは少し注意が必要です。最も古いコンピューターは、浮動小数点計算を簡単に行うことができませんでした。Pentium までは、x87 コプロセッサがなく、すべての浮動小数点計算がソフトウェアで行われるのが一般的でした。これは、単純な整数演算を行うよりも 1000 倍遅くなりました。今日では、すべてのコンピューターが SIMD 操作を実行できます (つまり、浮動小数点ベクトル拡張を使用します)。もうそうではないかもしれません。

于 2013-09-18T07:57:17.463 に答える