パソコン活用研究5番街(Visual Basic、Excel(VBA)、BASIC プログラミング研究)

グラフィックの基本2 (点で直線を描く&DDA補間)

グラフィックの基本では、psetによる点描で、円やサインカーブを描いてみました。直線や四角形のように
シンプルな図形はlineなどで簡単に描けますが、複雑な曲線の描画ではpsetで点描することが多くなります。
今回は、psetによる点描の基礎としてまず、直線を描いてみたいと思います。


1 直線を描く


直線を描くなら、BASICではlineという命令がありますので、lineを使うのが一番簡単です。
今回は、そこをあえてpsetの点描で直線を描いてみたいと思います。今後、グラフィックを扱うのに、今回
のようなテクニックも必要になってくると思いますので。

2点、(X1, Y1) (X2, Y2)を結んでできる線分の方程式は以下の通りになります。
どうして、そういう方程式になるかは、中学か高校かな?の数学の参考書みて下さい。



では、さっそく2点が与えられた時に点描で直線を描くプログラムを作ってみましょう。
この時に、線分の傾き Y2-Y1/X2-X1 によって2パターンに条件分岐させる必要があることに
注意して下さい。
線分の傾きが緩やか(すなわち傾きが1より小さい)な場合は、xを基準に描画。傾きが急な場合は
yを基準に描画します。そうしないと、ある条件では間隔のあいた点線になってしまいます。


    例えば、傾きが急(1以上)の線分を
    xを基準に1づつ増分して描くと、左の図
    のようにy方向はとびとびの点線となって
    しまいます。




直線を描くプログラム1

10 cls
20 input "X1,Y1 :";x1,y1
30 input "X2,Y2 :";x2,y2
40 if abs((y2-y1)/(x2-x1))>1 then goto 200
100 for x=x1 to x2 step sgn(x2-x1)
110 y=(y2-y1)*(x-x1)/(x2-x1)+y1
120 pset (x,y)
130 next
140 end
200 for y=y1 to y2 step sgn(y2-y1)
210 x=(x2-x1)*(y-y1)/(y2-y1)+x1
220 pset (x,y)
230 next
240 end

実行例




2 DDAによる直線補間

BASICで直線を描くなら、上で示した「直線を描くプログラム1」で十分です。
ただし、機械語で直線描画プログラムを作る場合、このアルゴリズムでは、小数点(浮動小数点)
の計算が含まれているため、高速になりません。機械語で直線を引く場合には、
(A) 計算は整数だけ (スクリーンの座標は整数なので、これでO.K.です)
(B) 割り算を使わない
アルゴリズムが高速になります。
この条件の下に考え出されたのがDDA(Degital Differential Analyser デジタル差分解析)補間という
方法です。

今、下の図のように点P1から点P2に直線を引くとします。
この時に、P1の次にドットをうつべき座標の候補は赤色の3点、t1,t2,t3 です。
この中で、真の値に一番近い座標を選んでドットをうつことにします。
座標が決まれば、以下同様の手順で更に次の座標を決めていきます。



では、この手順を式にまとめてみましょう。
まず、点P1(X1,Y1) P2(Xz,Yz) とし、傾きが緩やか(1以下)な場合で考えてみます。
Xに関しては以下の通り
X2 = X1 +1
X3 = X1+2
...........................
Xn = X1 + n

さて、傾きをd = (Yz-Y1)/(Xz-X1) とすると、2点P1,P2を結ぶ線分の方程式は
y = d(x-X1)+Y1 ですから、Yの式は以下の通りになります。
Yn = d(Xn-X1)+Y1

さてここで、dは少数ですので、Ynも少数です。このままでは、少数の計算がついてまわってしまいます。
そこで、こいつを整数部と小数部にわけてしまいます。ここからがDDA補間の本題です。
整数部をYIn, 小数部をYEnとすると
Yn =YIn + YEn
YE =0
YEn= YEn-1+d
ということになります。

ここで、小数部のYEn>=0.5 ならYInの座標をn-1の時より1個上にあげ、小数部からは1を引いて新たな
YEnとします。 すなわち、YIn =YIn-1+1 新しいYEn<== YEn-1
YEn<0.5 ならn-1の時と同じままで、
YIn =YIn-1 とします。
(すなわちYInはYnを四捨五入した値になります)

では、ここまでのルールをいったんまとめておきましょう。
Xn=X1+n
YE =0
YEn= YEn-1+d
YEn>=0.5 なら YIn =YIn-1+1   YEn <== YEn-1
YEn<0.5なら  YIn =YIn-1  

さて、ここでもまだYEnは少数です。全てを整数の計算にしたいので、YEnも整数にしてしまいます。
YEnのある式の両辺に2*(Xz-X1)を掛けて整理してみると、以下のようになります。
Xn=X1+n
YE =0
2*(Xz-X1)*YEn= (YEn-1+d)*2*(Xz-X1)
2*YEn*(Xz-X1)-(Xz-X1)>=0 なら YIn =YIn-1+1     2*YEn*(Xz-X1) <== 2*YEn*(Xz-X1)-2*(Xz-X1)
2*YEn*(Xz-X1)-(Xz-X1)<0なら YIn =YIn-1

なんかごちゃごちゃしてきましたので、2*YEn*(Xz-X1)-(Xz-X1) = En としてみます。
Xn=X1+n
YE =0
En+(Xz-X1) = En-1+(Xz-X1)
En>=0 なら YIn =YIn-1+1    En+(Xz-X1) <= En-(Xz-X1)
En<0 なら YIn =YIn-1

もう一息ですね。もう少しまとめてみましょう。
ちなみにE1= 2*YE1*(Xz-X1)-(Xz-X1) =Xz-X1 ですね。

Xn=X1+n
E1 =Xz-X1
En= En-1
En>=0 なら YIn =YIn-1+1 En <== En-2*(Xn-X1)
En<0 なら YIn =YIn-1

全て整数になり、割り算もなくなりルールがすっきりしましたね。これで、BASICのプログラムにできそうです。

DDA補間の直線描画プログラム

10 cls
20 input "X1,Y1 :";x1,y1
30 input "X2,Y2 :";x2,y2
40 dx=x2-x1:dy=y2-y1:x=x1:y=y1
50 if abs(dy)/abs(dx)>1 then goto 200
100 e=-abs(dx)
110 for i=0 to abs(dx)
120 pset(x,y)
130 x=x+sgn(dx)
140 e=e+2*abs(dy)
150 if e>=0 then y=y+sgn(dy):e=e-2*abs(dx)
160 next
170 end
200 e=-abs(dy)
210 for i=0 to abs(dy)
220 pset (x,y)
230 y=y+sgn(dy)
240 e=e+2*abs(dx)
250 if e>=0 then x=x+sgn(dx):e=e-2*abs(dy)
260 next
270 end


ちなみに、N88互換BASIC For Winで上記の2つのプログラムを実行すると、DDA補間の方が、1.5倍
ほど実行時間がかかります(遅い)。
DDA補間の方が、STEPが多いし、計算も多くなっているからでしょう。

おそらく、機械語で組みなおしたら、DDA補間の方が圧倒的に早くなると思います。
また、BASICのline命令も、機械語レベルではDDA補間による点描によって、直線を引いています。


TOP PAGE >Basic活用研究目次