DDAの整数化 - WebGLでレトロPCグラフィックスを楽しむ（２２）

前回に引き続き、線分描画に取り組む。

今回はブレゼンハム・アルゴリズムに取り組もうと思っていたが、私の認識が誤っていたことに気がついた。 私はこのポストに書いているものがブレゼンハム・アルゴリズムだと今の今まで思っていたようである。どうもこのアルゴリズムはDDAを整数化したものとなるようだ。なので、昔DDAで線分を描く記事を読んで、これはブレゼンハム・アルゴリズムではないか？と思っていたが、私が間違っていたようだ。

今回はそういうわけでDDAの整数化というタイトルにして、前回の線分描画コードを整数化することにする。

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

まず上記の式の中で、x,yの整数化に取り組む。xもしくはyにmずつ足していき、整数部分を取り出して描画座標としているのであるが、Dという変数を用意して、Dにmを加算し、D >= 1となったらxもしくはyにd加算し、Dから1減算するという形に変更する。つまりDはx,yにいつ加算するかのフラグ変数として使用するのである。これによって、xもしくはy座標が整数化される。それと、今回は切り捨てではなく四捨五入するためにDに初期値として0.5をセットする。そのほうがプロットすべき座標が理想的な直線に近くなるので。 変更後のコードは以下のとおりである。

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

次にm,Dの整数化に取り組む。mであるが、これはdyをdxで割った値であるが、これにdxを掛けて除算自体を除去し、整数化することにする。その分mの関連式の両辺にdxを掛けることになるので、コードを修正する。

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

結果mは整数化された。次にDは初期値としてmを0.5倍した値をセットしているが、これをmを2倍して整数化することにする。2倍はシフト演算で行うことにする。さらにコードを修正すると以下となる。

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

さらにコードを改良すると以下のコードとなる。

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;
      }
    }
  } 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;
      }
    }
  }
}

すべての演算は整数化され、さらには乗除算がなくなっている。

(2016/5/9訂正：コードにバグあり。修正を行った。）