ライン・ルーチン (3)高速化の手法

この章では、線分描画を高速化するための手法について紹介します。

1) 両端からの同時描画

まずはじめに気づくところといえば、線分が点対称であることを利用して片端からでなく両端から同時に描画することでしょう。これにより、誤差項 Eの計算などを半分にすることが可能となります。

/*
  dblLine : ラインルーチン(両端からの同時描画)

  Coord c0, c1 : 始点・終点の座標値
  unsigned int col : 色コード
*/
void dblLine( Coord c0, Coord c1, unsigned int col )
{
  int i;

  if ( clipping( &c0, &c1 ) < 0 ) return;

  Coord d; /* 二点間の距離 */
  d.x = ( c1.x > c0.x ) ? c1.x - c0.x : c0.x - c1.x;
  d.y = ( c1.y > c0.y ) ? c1.y - c0.y : c0.y - c1.y;

  Coord s; /* 二点の方向 */
  s.x = ( c1.x > c0.x ) ? 1 : -1;
  s.y = ( c1.y > c0.y ) ? 1 : -1;

  /* 傾きが1より小さい場合 */
  if( d.x > d.y ) {
    int E = -d.x;
    for( i = 0 ; i < ( d.x + 1 ) >> 1 ; i++ ) {
      pset( c0, col );
      pset( c1, col );
      c0.x += s.x;
      c1.x -= s.x;
      E += 2 * d.y;
      if( E >= 0 ) {
        c0.y += s.y;
        c1.y -= s.y;
        E -= 2 * d.x;
      }
    }
    if ( ( d.x % 2 ) == 0 ) pset( c0, col ); /* d.x + 1 が奇数の場合、残った中央の点を最後に描画 */
  /* 傾きが1以上の場合 */
  } else {
    int E = -d.y;
    for( i = 0 ; i < ( d.y + 1 ) >> 1 ; i++ ) {
      pset( c0, col );
      pset( c1, col );
      c0.y += s.y;
      c1.y -= s.y;
      E += 2 * d.x;
      if( E >= 0 ) {
        c0.x += s.x;
        c1.x -= s.x;
        E -= 2 * d.y;
      }
    }
    if ( ( d.y % 2 ) == 0 ) pset( c0, col ); /* d.y + 1 が奇数の場合、残った中央の点を最後に描画 */
  }
}

2) 特殊な場合の処理

比較的よく使用される処理である水平・垂直な線分の描画方法を特別視するのもよく使われる方法です。また、傾き m(またはその逆数 1/m)が完全な整数となる場合、水平または垂直方向に並ぶピクセル数は必ず一定となるため、ブレセンハムの線分発生アルゴリズムを使わずに線分を書くことが可能です。

  /* 傾きが1より小さい場合 */
  if( d.x > d.y ) {
    n = d.x / d.y;
    for( i = 0 ; i <= d.y ; i++ ) {
      for( j = 0 ; j < n ; j++ ) {
        pset( c0, col );
        ( c0.x )++;
      }
      ( co.y )++;
    }
  /* 傾きが1以上の場合 */
  } else {
    n = d.y / d.x;
    for( i = 0 ; i <= d.x ; i++ ) {
      for( j = 0 ; j < n ; j++ ) {
        pset( c0, col );
        ( cy.0 )++;
      }
      ( c0.x )++;
    }
  }

3) ダブルステップ線分発生アルゴリズム

1993年、Phil Grahamと S. Sitharama Iyengarによって、ブレセンハムの線分発生アルゴリズムの改良版である「ダブルステップ/トリプルステップ線分発生アルゴリズム(Double- and Triple-step Incremental Generation of Lines)」が発表されました。この中にあるダブルステップ線分発生アルゴリズムでは、オリジナルのブレセンハム線分発生アルゴリズムを 2ステップ分まとめて実行し、2ピクセル分まとめて描画するため、ループ回数は 1/2に、さらに上述の両端からの同時描画を使えば 1/4に半減されます。

まず、傾きが 0から 1までの範囲の線分を描画するパターンを 3ピクセル分のみ切り出してみると、下図に示すような 4パターンが考えられます。
ここで、さらに傾き mを 0≦m＜1/2 と 1/2≦m＜1の場合に分けて考えると

まず、0≦m＜1/2の場合のみ注目します。ブレセンハムの線分発生アルゴリズムで求めた、誤差項 Eの増分と、Eが正になったときの補正値は、

となります。Eに 2ステップ分の増分である 4dyを加えて結果を見ると、a)のパターンでは y座標が変化しないことから E<0、また b),c)の場合は y座標が増加しているため E≧0になります。これにより a)であるかどうかが区別できます。b)と c)を区別するには Eの値で判断します。仮に、1ステップずつ増分2dyを Eに加えたとすると、1回目の加算において b)のパターンはまだ E<0のままですが、c)のパターンでは E≧0になります。そのため、2回目の加算では b)の場合 E<2dy、c)の場合 E≧2dyであり、この結果を使って区別することが可能です。

パターン	Eのとり得る値
a)	E＜0
b)	0≦E＜2dy
c)	E≧2dy

1/2≦m＜1の場合も同様な処理になります。但し、b),c),d)のパターンでは y座標が最低一回は必ず変化するため、2ステップ分の増分のほかに補正値の減算も合わせ、( 4dy - 2dx )を Eに加えます。このとき Eの値は以下のようになります。

パターン	Eのとり得る値
b)	E＜2dy - 2dx
c)	2dy - 2dx≦E＜0
d)	E≧0

描画するのは 2ピクセル分なので、a)とb)、c)とd)はそれぞれ同じ描画を行なうことになります。前者を H、後者を Dのパターンとしたとき、処理の流れは次のようになります。

以下に、ダブルステップ線分発生アルゴリズムのコーディングを示します。

/*
  VLine, HLine : 垂直・水平方向の線分描画

  Coord c : 始点の座標値
  int dx, dy : 描画する長さ
  unsigned int col : 色コード
*/
void VLine( Coord c, int dy, unsigned int col )
{
  for ( int y = 0 ; y <= dy ; y++ ) {
      pset( c, col );
      ( c.y )++;
  }
}
void HLine( Coord c, int dx, unsigned int col )
{
  for ( int x = 0 ; x <= dx ; x++ ) {
      pset( c, col );
      ( c.x )++;
  }
}

/*
  dblHPset/dblVPset/dblDPset : 水平/垂直/斜線方向のダブル・ステップ点描画

  Coord c0, c1 : 始点・終点の座標値
  Coord s : 始点と終点の方向(+/-)
  unsigned int col : 色コード
*/
void dblHPset( Coord c0, Coord c1, Coord s, unsigned int col )
{
  pset( c0, col );
  pset( c1, col );
  c0.x += s.x;
  c1.x -= s.x;
  pset( c0, col );
  pset( c1, col );
}
void dblVPset( Coord c0, Coord c1, Coord s, unsigned int col )
{
  pset( c0, col );
  pset( c1, col );
  c0.y += s.y;
  c1.y -= s.y;
  pset( c0, col );
  pset( c1, col );
}
void dblDPset( Coord c0, Coord c1, Coord s, unsigned int col )
{
  pset( c0, col );
  pset( c1, col );
  c0.x += s.x;
  c1.x -= s.x;
  c0.y += s.y;
  c1.y -= s.y;
  pset( c0, col );
  pset( c1, col );
}

/*
  dblStepLine : ダブル・ステップ線分発生ルーチン(傾き1以下)

  Coord c0, c1 : 始点・終点の座標値
  Coord d : 始点と終点の間の距離
  Coord s : 始点と終点の方向(+/-)
  unsigned int col : 色コード
*/
void dblStepGentleLine( Coord c0, Coord c1, Coord d, Coord s, unsigned int col )
{
  int E = -d.x;
  /* 0<|ｍ|<1/2の場合 */
  if ( d.x > 2 * d.y ) {
    for( int i = 0 ; i < ( d.x + 1 ) >> 2 ; i++ ) {
      E += 4 * d.y;
      if ( E < 2 * d.y ) {
        dblHPset( c0, c1, s, col );
      } else {
        dblDPset( c0, c1, s, col );
      }
      c0.x += s.x * 2;
      c1.x -= s.x * 2;

      if ( E >= 0 ) {
        E -= 2 * d.x;
        c0.y += s.y;
        c1.y -= s.y;
      }
    }
  /* 1/2≦|ｍ|<1の場合 */
  } else {
    for ( int i = 0; i < ( ( d.x + 1 ) >> 2 ); i++ ) {
      E += 4 * d.y - 2 * d.x;
      if ( E < 2 * d.y - 2 * d.x ) {
        dblHPset( c0, c1, s, col );
      } else {
        dblDPset( c0, c1, s, col );
      }
      c0.x += s.x * 2;
      c1.x -= s.x * 2;
      c0.y += s.y;
      c1.y -= s.y;

      if ( E >= 0 ) {
        E -= 2 * d.x;
        c0.y += s.y;
        c1.y -= s.y;
      }
    }
  }

  /* 4ピクセル未満の端数分を描画 */
  for ( int i = 0 ; i < ( ( d.x + 1 ) % 4 ) ; i++ ) {
    pset( c0, col );
    c0.x += s.x;
    E += 2 * d.y;
    if( E >= 0 ) {
      c0.y += s.y;
      E -= 2 * d.x;
    }
  }
}

/*
  dblStepLine : ダブル・ステップ線分発生ルーチン(傾き1より大)

  Coord c0, c1 : 始点・終点の座標値
  Coord d : 始点と終点の間の距離
  Coord s : 始点と終点の方向(+/-)
  unsigned int col : 色コード
*/
void dblStepSharpLine( Coord c0, Coord c1, Coord d, Coord s, unsigned int col )
{
  int E = -d.y;
  /* |ｍ|≧2の場合 */
  if ( d.y >= 2 * d.x ) {
    for( int i = 0 ; i < ( d.y + 1 ) >> 2 ; i++ ) {
      E += 4 * d.x;
      if ( E < 2 * d.x ) {
        dblVPset( c0, c1, s, col );
      } else {
        dblDPset( c0, c1, s, col );
      }
      c0.y += s.y * 2;
      c1.y -= s.y * 2;

      if ( E >= 0 ) {
        E -= 2 * d.y;
        c0.x += s.x;
        c1.x -= s.x;
      }
    }
  /* 1≦|ｍ|<2の場合 */
  } else {
    for ( int i = 0; i < ( ( d.y + 1 ) >> 2 ); i++ ) {
      E += 4 * d.x - 2 * d.y;
      if ( E < 2 * d.x - 2 * d.y ) {
        dblVPset( c0, c1, s, col );
      } else {
        dblDPset( c0, c1, s, col );
      }
      c0.y += s.y * 2;
      c1.y -= s.y * 2;
      c0.x += s.x;
      c1.x -= s.x;

      if ( E >= 0 ) {
        E -= 2 * d.y;
        c0.x += s.x;
        c1.x -= s.x;
      }
    }
  }

  /* 4ピクセル未満の端数分を描画 */
  for ( int i = 0 ; i < ( ( d.y + 1 ) % 4 ) ; i++ ) {
    pset( c0, col );
    c0.y += s.y;
    E += 2 * d.x;
    if( E >= 0 ) {
      c0.x += s.x;
      E -= 2 * d.y;
    }
  }
}

/*
  dblStepLine : ラインルーチン(ダブルステップ + 両端からの同時描画)

  Coord c0, c1 : 始点・終点の座標値
  unsigned int col : 色コード
*/
void dblStepLine( Coord c0, Coord c1, unsigned int col )
{
  if ( clipping( &c0, &c1 ) < 0 ) return;

  Coord d; /* 二点間の距離 */
  d.x = ( c1.x > c0.x ) ? c1.x - c0.x : c0.x - c1.x;
  d.y = ( c1.y > c0.y ) ? c1.y - c0.y : c0.y - c1.y;

  /* 水平・垂直線分は別処理 */
  if ( d.x == 0 ) {
    VLine( Coord( c0.x, ( c0.y < c1.y ) ? c0.y : c1.y ), d.y, col );
    return;
  }
  if ( d.y == 0 ) {
    HLine( Coord( ( c0.x < c1.x ) ? c0.x : c1.x, c0.y ), d.x, col );
    return;
  }

  Coord s; /* 二点の方向 */
  s.x = ( c1.x > c0.x ) ? 1 : -1;
  s.y = ( c1.y > c0.y ) ? 1 : -1;

  /* 傾きが1より小さい場合 */
  if( d.x > d.y ) {
    dblStepGentleLine( c0, c1, d, s, col );
  /* 傾きが1以上の場合 */
  } else {
    dblStepSharpLine( c0, c1, d, s, col );
  }
}

サンプル・プログラムの中で、dblStepGentleLineは傾きが 1より小さい場合、dblStepSharpLineは傾きが 1以上の場合に利用される描画ルーチンです。両者は変数をx方向とy方向で入れ替えただけで、処理の内容は全く同じです。うまく工夫すれば、一つのルーチンとしてまとめられそうですが、逆にわかりづらくなる可能性があったため、ここでは二つに分けてあります。
なお、水平・垂直線分に対しては、別途用意したラインルーチン(HLine/VLine)を利用しています。

トリプルステップでは、4ピクセル分を切り出してそのパターン毎に場合分けを行なうことになります。そのパターンは全部で 7個であり、ダブルステップよりさらに処理が複雑になります。さらに一般化した N-Stepの線分描画に関するアルゴリズムもあるようですが、内容の方は未確認です。

4) 性能評価

最後に、各ルーチンの性能を比較してみたいと思います。今まで紹介したものとは別に、座標値を直接算出して描画するテスト・プログラムも別途用意しました。

/*
  coordLine : 座標値を直接算出するラインルーチン

  Coord c0, c1 : 始点・終点の座標値
  unsigned int col : 色コード
*/
void coordLine( Coord c0, Coord c1, unsigned int col )
{
  int i;

  if ( clipping( &c0, &c1 ) < 0 ) return;

  Coord d; /* 二点間の距離 */
  d.x = c1.x - c0.x;
  d.y = c1.y - c0.y;
  if ( d.x == 0 ) {
    if ( d.y < 0 ) d.y *= -1;
    VLine( Coord( c0.x, ( c0.y < c1.y ) ? c0.y : c1.y ), d.y, col );
    return;
  }
  if ( d.y == 0 ) {
    if ( d.x < 0 ) d.x *= -1;
    HLine( Coord( ( c0.x < c1.x ) ? c0.x : c1.x, c0.y ), d.x, col );
    return;
  }

  Coord s; /* 二点の方向 */
  s.x = ( c1.x > c0.x ) ? 1 : -1;
  s.y = ( c1.y > c0.y ) ? 1 : -1;

  Coord c;

  /* 傾きが1より小さい場合 */
  if( d.x > d.y ) {
    double slope = (double)( d.y ) / (double)( d.x );
    for( i = c0.x ; i <= c1.x ; i += s.x ) {
      c.x = i;
      c.y = (int)( slope * ( (double)i - (double)( c0.x ) ) + 0.5 ) + c0.y;
      pset( c, col );
    }
  /* 傾きが1以上の場合 */
  } else {
    double slope = (double)( d.x ) / (double)( d.y );
    for( i = c0.y ; i <= c1.y ; i += s.y ) {
      c.y = i;
      c.x = (int)( slope * ( (double)i - (double)( c0.y ) ) + 0.5 ) + c0.x;
      pset( c, col );
    }
  }
}

今回は、1024 x 1024の画面内に 10万本のランダムな線分を描画する処理を各ラインルーチンに対して 10回ずつ実施して、処理時間の平均値を算出・比較しました。結果は次のようになりました(CPU : Intel Pentium4 3.00GHz)。

一番シンプルな実装である座標算出方式のアルゴリズムが最も早いという結果になっています。このままでは悔しいので、点描画部分(pset)を何も処理しない様にしてビルドしたプログラムでもう一度テストしてみました。この場合、純粋に描画位置の算出時間だけが計測されるようになります。今度は、ブレセンハム方式の方が早いという結果が得られています。

今回利用したテスト・プログラムでは点描画の処理がかなり重いため、それが影響したのではないかと考えられます。これは予想ですが、浮動小数点数の演算と整数演算が並列で処理されたために、このような結果となったのではないでしょうか。計算処理だけ見れば、ブレセンハムのアルゴリズムによって処理時間は短縮できるようです。しかし、その差はわずかなもので、整数演算のみで処理を行なうことによる効果はあまり大きくないとも言えます。現在では浮動小数点演算も専用のプロセッサで処理ができるため、昔のようにソフトウェアでエミュレートしていた頃に比べれば大した恩恵にはあずかることができないようです。
ちなみに、浮動小数点数演算を使ってブレセンハム方式を利用したところ、整数演算の場合よりも遅くなるという結果が得られました。通常であれば、今でも整数演算の方が浮動小数点数演算よりも早く、ブレセンハム方式を利用するのであれば、整数演算にしておいた方が有利です。

両端からの同時描画は効果があるようですが、残念ながら、ダブルステップによる効果は全くありませんでした。処理が複雑になった分、ループ回数が減っただけでは改善はできないようです。もちろん、全く利用できないというわけではなく、もっと低機能な(昔の)プロセッサを利用したり、ハードウェアによる実装を行なうような場面では有効な手段だと思います。

◎ 0≦m＜1の場合におけるダブルステップBresenhamアルゴリズムのサンプル・プログラムにコーディングのミスが見つかりました(2003-11-24)

◎ 内容を大幅に変更しました。特に、サンプル・プログラムは大幅に変わっています。

0≦m＜1/2の場合	a), b), c)
1/2≦m＜１の場合	b), c), d)

3-1)	Eに4dyを加える
3-2)	E<2dyならば、Hのパターンで2ピクセル描画する
3-3)	E≧2dyならば、Dのパターンで2ピクセル描画する
3-4)	x座標に2を加える
3-5)	E≧0ならば、Eから2dxを引いて、y座標に1を加える
3-6)	3-1)に戻って処理を繰り返す

4-1)	Eに4dy-2dxを加える
4-2)	E<2dy - 2dxならば、Hのパターンで2ピクセル描画する
4-3)	E≧2dy - 2dxならば、Dのパターンで2ピクセル描画する
4-4)	x座標に2、y座標に1を加える
4-5)	E≧0ならば、Eから2dxを引いて、y座標に1を加える
4-6)	4-1)に戻って処理を繰り返す

座標算出方式	1.52 sec.
ブレセンハム方式	2.39 sec.
両端からの同時描画	2.23 sec.
両端 + ダブルステップ	2.29 sec.

座標算出方式	0.60 sec.
ブレセンハム方式	0.51 sec.
両端からの同時描画	0.46 sec.
両端 + ダブルステップ	0.49 sec.

1)	x = x0、y = y0、誤差項E=0に初期化する。 dx = \| x1 - x0 \|、dy = \| y1 - y0 \|とおく。
2)	dy/dx≧1/2ならば4-1)へ

Eの増分	2dy
補正値	2dx