今回はブレゼンハム・アルゴリズムを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);
}
};
})();
このコードで描画してみた結果が以下の画面である。
前々回のDDAで整数化したコードで描画したものは以下である。描画結果が若干異なる。
重ね合わせてみると違いがよりわかると思う。ブレゼンハム・アルゴリズムで描いたほうがきれいに思える。DDAのほうはいくつかポイントの選択を誤っているように見える。
ていうか、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);
}
}
}
結果は以下の通り。ブレゼンハムの実行結果と同じになった。むむう。コードの内容は違うけど、理屈は同じような気がしてきたな。。