私はこれをブレゼンハム・アルゴリズムと同じだと思っていたけど、違っていた。
昔のPCはグラフィックプリミティブの描画が遅かったので、曲線は線分で近似していた。
例えば下の絵の顔の輪郭は曲線に見えるが、実際は線分である。
(http://85data-blog.cocolog-nifty.com/blog/2011/12/200-c236.html より)
このように、初期のPCのグラフィックにおける線分の重要性は高かったが、昔のPCのBASICで提供されるLINE命令（線分を描画する命令）は、処理が遅いものが多かった。なので機械語で線分を高速描画するという記事が雑誌によく載っていて、Digital Differential Analyzer（DDA）による線分動画アルゴリズムが紹介されていた。が、当時の記事は実は、ブレゼンハム・アルゴリズムををDDAと混同していたものも多かったようだ。私が読んだ記事もDDAによる線分描画という記事であったが、アルゴリズム自体はブレゼンハム・アルゴリズムであった。ブレゼンハム・アルゴリズムはDDAによる線分描画を整数のみで行えるようにアルゴリズムを工夫したものである。
DDAはデジタル微分解析という名前がついていてなんだかややこしそうだけど、アルゴリズム的には大したことはない。
線分の2点間の座標から傾きを求める。 線分の傾きは、で求めることができる。この傾きをとする。この傾きの値は実数で、小数点を含む。
座標を→まで1ずつ進め、に を加算し、の整数分を取り出して画面にプロットする。
これを私が作った環境において、キャラクタで線分を描画するコードは以下のとおりである。
// キャラクターによる線分描画
function cline(x1,y1,x2,y2,char = String.fromCharCode(0xef),color = 7,bgcolor = 0,attr = 0){
let m = (y2 - y1)/(x2 - x1);
for(let x = x1,y = y1;x <= x2;++x,y += m){
printDirect(x,Math.floor(y),char,color,bgcolor,attr);
}
}
がそれぞれの実行結果は以下のとおり。
ただこのままでは２つ問題がある。
1つ目は、、つまりであった場合である。 例えばがそれぞれで実行結果すると以下の通りとびとびの線になる。
これはの場合はを→まで1ずつ進め、をに加算し、の整数分を取り出して画面にプロットするようにコードを書き換える。
// キャラクターによる線分描画
function cline(x1,y1,x2,y2,char = String.fromCharCode(0xef),color = 7,bgcolor = 0,attr = 0){
let m = (y2 - y1)/(x2 - x1);
if(m <= 1){
for(let x = x1,y = y1;x <= x2;++x,y+=m){
printDirect(x,Math.floor(y),char,color,bgcolor,attr);
}
} else {
m = 1/m;
for(let x = x1,y = y1;y <= y2;++y,x+=m){
printDirect(Math.floor(x),y,char,color,bgcolor,attr);
}
}
}
描画結果は以下の通りである。
もう1つの問題は、もしくはの場合である。この場合は加算方向などを逆転したり、傾きを絶対値で評価する必要がある。それを考慮したコードは以下となる。
// キャラクターによる線分描画
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);
}
}
}
DDAでは傾きは実数で保持するので、小数点の計算が必要である。これを改良して整数のみの演算としたのがブレゼンハム・アルゴリズムであるが、その解説は次回としよう。