自作シミュレータの OneFiveCrowd で直線の描画にブレゼンハムのアルゴリズムを用いたところ、本家の描画結果と差が生じた。
 |
 |
本家の描画結果は、若干右下に寄っているようである。
そこで、座標の単純な線形補間 (小数点以下切り捨て) を試してみた。
10 A=5:B=40:C=27:D=30
20 FOR X=A TO C
30 Y=B+(D-B)*(X-A)/(C-A)
40 DRAW X+32,Y
50 NEXT
60 DRAW A,B,C,D
それっぽい結果が得られた。
座標だけを変更し、右肩下がりの描画も試してみよう。
10 A=5:B=25:C=27:D=42
それっぽい結果が得られた。
右から左への描画も試してみよう。
座標に加え、FOR文の更新方向も変更する。
10 A=27:B=40:C=5:D=27
20 FOR X=A TO C STEP -1
異なる結果になった。
本家の描画は、今度は上寄りになっている。
最初の座標のX座標より2番目の座標のX座標のほうが小さい (かつX座標の差の絶対値がY座標の差の絶対値以上の) ときは、2番目の座標から最初の座標に向かって描画が行われると推測できる。
20 FOR X=C TO A
30 Y=D+(B-D)*(X-C)/(A-C)
結果が一致した。
続いて、X座標の差の絶対値がY座標の差の絶対値より小さい場合を見てみよう。
今のままのアルゴリズムでは、線に欠けが生じてしまう。
10 A=15:B=45:C=22:D=30
20 FOR X=A TO C
30 Y=B+(D-B)*(X-A)/(C-A)
40 DRAW X+32,Y
50 NEXT
60 DRAW A,B,C,D
そこで、Y方向にFOR文を回すように変更する。
20 FOR Y=B TO D STEP -1
30 X=A+(C-A)*(Y-B)/(D-B)
これでは一致しなかった。
Y方向の場合も、座標の小さいほうから大きいほうに向かって描画するようだ。
20 FOR Y=D TO B
30 X=C+(A-C)*(Y-D)/(B-D)
左上から右下に描画する場合も、これでよさそうだ。
10 A=15:B=32:C=22:D=44
20 FOR Y=B TO D
30 X=A+(C-A)*(Y-B)/(D-B)
これらを組み合わせると、描画アルゴリズムは以下のように表現できる。
2個の座標が一致している場合、そのままだとゼロ除算になってしまうので、場合分けを行った。
10 'ｾﾝﾌﾞﾝ ﾋﾞｮｳｶﾞ ﾃｽﾄ
20 CLS
30 INPUT "X1=",A
40 INPUT "Y1=",B
50 INPUT "X2=",C
60 INPUT "Y2=",D
70 E=A:F=B:G=C:H=D
80 IF E=G AND F=H DRAW E,F:GOTO 210
90 IF ABS(E-G)<ABS(F-H) GOTO 160
100 IF E>G T=E:E=G:G=T:T=F:F=H:H=T
110 FOR X=E TO G
120 Y=F+(H-F)*(X-E)/(G-E)
130 DRAW X,Y
140 NEXT
150 GOTO 210
160 IF F>H T=E:E=G:G=T:T=F:F=H:H=T
170 FOR Y=F TO H
180 X=E+(G-E)*(Y-F)/(H-F)
190 DRAW X,Y
200 NEXT
210 IF INKEY()=0 GOTO 210
220 DRAW A,B,C,D,2
以下が実行結果の例である。
この状態でキーを押すと、220行目のXOR描画が実行される。
その結果、描画結果が一致していれば線がきれいに消える。
この入力では、本家ではきれいに消えたが、OneFiveCrowdでは以下のように図形が残った。
(「残った」には、「消えなかった」以外に「余計に描画された」場合もあることに注意すること)
さらにこれをランダムで繰り返しテストするようにしてみた。
10 'ｾﾝﾌﾞﾝ ﾋﾞｮｳｶﾞ ﾃｽﾄ (ﾗﾝﾀﾞﾑ)
20 A=RND(64)
30 B=RND(48)
40 C=RND(64)
50 D=RND(48)
60 CLS
70 E=A:F=B:G=C:H=D
80 IF E=G AND F=H DRAW E,F:GOTO 210
90 IF ABS(E-G)<ABS(F-H) GOTO 160
100 IF E>G T=E:E=G:G=T:T=F:F=H:H=T
110 FOR X=E TO G
120 Y=F+(H-F)*(X-E)/(G-E)
130 DRAW X,Y
140 NEXT
150 GOTO 210
160 IF F>H T=E:E=G:G=T:T=F:F=H:H=T
170 FOR Y=F TO H
180 X=E+(G-E)*(Y-F)/(H-F)
190 DRAW X,Y
200 NEXT
210 DRAW A,B,C,D,2
220 FOR I=#900 TO #BFF
230 P=PEEK(I)
240 IF P<>0 AND P<>#80 GOTO 280
250 NEXT
260 GOTO 20
270 END
280 ?"DRAW ";A;",";B;",";C;",";D
DRAW命令は画面外の座標も有効な入力として受け付けるが、今回は画面内の座標のみを対象にしている。
描画結果が一致しなかった場合、すなわち画面に点が残った場合、その時の座標を出力して終了する。
IchigoKamuy で1時間以上実行したが、描画結果の不一致は検出されなかった。
よって、IchigoJam で用いられている線分描画アルゴリズムは
- 始点と終点の座標が同じ場合、そこに点を打って終わる
- そうでない場合、
- X座標の差がY座標の差以上の場合、X座標の小さい方から大きい方へY座標の線形補間(小数点以下切り捨て)を行った位置に点を打っていく
- そうでない場合、Y座標の小さい方から大きい方へX座標の線形補間(小数点以下切り捨て)を行った位置に点を打っていく
であると推測できる。