ブレゼンハム・アルゴリズムによる線分描画を原典にそこそこ忠実に実装してみる - PCグラフィックスを懐かしむ。楽しむ。(24)

公開:2016-05-07 14:19
更新:2017-09-18 05:24
カテゴリ:PCグラフィックス,javascript,webgl,html5,古典的グラフィック技術を懐かしむ

今回はブレゼンハム・アルゴリズムをJSで実装してみる。

前回の記事にそこそこ忠実に実装してみたのが下のコードである。もうちょっと最適化できるような気もするけど、とりあえずということで。

 // ブレゼンハム・アルゴリズムによる線分描画
  var clineB0 = (()=>{
    // 移動方向定義
    var M = [
      {dx:1,dy:0}, // M1
      {dx:1,dy:1}, // M2
      {dx:0,dy:1}, // M3
      {dx:-1,dy:1}, // M4
      {dx:-1,dy:0}, // M5
      {dx:-1,dy:-1}, // M6
      {dx:0,dy:-1}, // M7
      {dx:1,dy:-1} // M8
    ];

    return (x1,y1,x2,y2,char = String.fromCharCode(0xef),color = 7,bgcolor = 0,attr = 0 )=>{

      let dx = (x2 - x1) | 0;// Δx
      let dy = (y2 - y1) | 0;// Δy

      // X Y Z
      let X = dx >= 0? 1 : 0;
      let Y = dy >= 0? 1 : 0;
      let Z = ((Math.abs(dx) - Math.abs(dy)) >= 0 ? 1 : 0) | 0;
      let da,db,m1,m2;// Δa,Δb,m1,m2

      // (2)の決定
      if(Z == 1){
        da = Math.abs(dx) | 0;
        db = Math.abs(dy) | 0;
      } else {
        da = Math.abs(dy) | 0;
        db = Math.abs(dx) | 0;
      }

      // (4)の決定
      // F(X,Y,Z) 
      let f = [X & Z, (Y & (~Z & 1)),((~X & 1) & Z),((~Y & 1)&(~Z & 1))];

      if(f[0]) {
        m1 = M[0]; // F(X,Y,Z)
      } else if(f[1]){
        m1 = M[2];
      } else if(f[2]){
        m1 = M[4];
      } else if(f[3]){
        m1 = M[6];
      }

      // G(X,Y)
      let g = [X & Y,((~X & 1) & Y),((~X & 1) & (~Y & 1)),X & (~Y & 1)];

      if(g[0]) {
        m2 = M[1];
      } else if(g[1]){
        m2 = M[3];
      } else if(g[2]){
        m2 = M[5];
      } else if(g[3]){
        m2 = M[7];
      }

      let da2 = da << 1;// 2 * Δa
      let db2 = db << 1;// 2 * Δb 
      let t = db2 - da; // ▽1 = 2 * Δb - Δa 
      let i = 0;
      let x = x1,y = y1;
      printDirect(x,y,char,color,bgcolor,attr);
      while (i++ <= da){// 0 ... i ... Δa
        if(t >= 0){
          t += db2 -  da2;// ▽i = ▽(i-1) + 2Δb - 2Δa

          // execute m2          
          x += m2.dx;
          y += m2.dy;  
        } else {
          t += db2; // ▽i = ▽(i-1) + 2Δb

          // execute m1          
          x += m1.dx;
          y += m1.dy;
        } 
        printDirect(x,y,char,color,bgcolor,attr);
      }
    };
  })();

このコードで描画してみた結果が以下の画面である。

https://sfpgmr.github.io/images/2016/05/2016050702.png

前々回のDDAで整数化したコードで描画したものは以下である。描画結果が若干異なる。

https://sfpgmr.github.io/images/2016/05/2016050703.png

重ね合わせてみると違いがよりわかると思う。ブレゼンハム・アルゴリズムで描いたほうがきれいに思える。DDAのほうはいくつかポイントの選択を誤っているように見える。

https://sfpgmr.github.io/images/2016/05/2016050701.png

ていうか、DDAのコードがバグっているだけかもしれないけどね(2016/5/8追記:やっぱりバグっていた。下に内容を追記した)。 ちなみにDDAのコードは以下の通り。

   function cline4(x1,y1,x2,y2,char = String.fromCharCode(0xef),color = 7,bgcolor = 0,attr = 0){
    let dy = (y2 - y1) << 1,dx = (x2 - x1) <<1 ;
    let ady = Math.abs(dy) | 0,adx = Math.abs(dx) | 0;
    let m = ady;
    if(m <= adx){
      for(let x = x1,y = y1,i = 0,e = adx >> 1,d = (dx >= 0 ? 1 | 0 : -1 | 0),d1 = (dy >= 0 ? 1 | 0 : -1 | 0),D = (m >> 1);i <= e;++i,x+=d){
        printDirect(x,y,char,color,bgcolor,attr);
        D = D + m;
        if(D >= adx){
          D -= adx;
          y += d1;
        }
      }
    } else {
      m = adx;
      for(let x = x1,y = y1,i = 0,e = ady >> 1,d = (dy >= 0 ? 1 | 0 : -1 | 0),d1 = (dx >= 0 ? 1 | 0 : -1 | 0),D = (m >> 1);i <= e;++i,y+=d){
        printDirect(x,y,char,color,bgcolor,attr);
        D = D + m;
        if(D >= ady){
          D -= ady;
          x += d1;
        }
      }
    }
  }

ラインルーチンはブレゼンハム・アルゴリズムを採用することにしよう。

(2016/5/8 追記)

DDAの線分描画コードはやはりバグっていた。申し訳ない。正しくは以下のコードであった。

function cline5(x1, y1, x2, y2, char = String.fromCharCode(0xef), color = 7, bgcolor = 0, attr = 0) {
  let dy = (y2 - y1) << 1, dx = (x2 - x1) << 1;
  let ady = Math.abs(dy) | 0, adx = Math.abs(dx) | 0;
  let m = ady;
  if (m <= adx) {
    for (let x = x1, y = y1, i = 0, e = adx >> 1, d = (dx >= 0 ? 1 | 0 : -1 | 0), d1 = (dy >= 0 ? 1 | 0 : -1 | 0), D = (adx >> 1) /* ここを修正 */; i <= e; ++i, x += d) {
      this.printDirect(x, y, char, color, bgcolor, attr);
      D = D + m;
      if (D >= adx) {
        D -= adx;
        y += d1;
      }
      //printDirect(x,y,char,color,bgcolor,attr);
    }
  } else {
    m = adx;
    for (let x = x1, y = y1, i = 0, e = ady >> 1, d = (dy >= 0 ? 1 | 0 : -1 | 0), d1 = (dx >= 0 ? 1 | 0 : -1 | 0), D = (ady >> 1)/* ここを修正 */; i <= e; ++i, y += d) {
      this.printDirect(x, y, char, color, bgcolor, attr);
      D = D + m;
      if (D >= ady) {
        D -= ady;
        x += d1;
      }
      //        printDirect(x,y,char,color,bgcolor,attr);
    }
  }
}

結果は以下の通り。ブレゼンハムの実行結果と同じになった。むむう。コードの内容は違うけど、理屈は同じような気がしてきたな。。

https://sfpgmr.github.io/images/2016/05/2016050802.png