おちゃめくらぶ掲示板 - 1659321896

1476：御茶目菜子：2013/02/12(火) 23:59:56: プチコンによる塗りつぶし描画ルーチン
またあれば便利そうなルーチンをいくつか作ってみたにょ。
まず、1つ目は塗りつぶし円（楕円）描画ルーチンにょ。
ネット上でプチコン関係の書き込みを見ると塗りつぶし円や楕円が描けないということに
不満を持っている人がいるからね。
塗りつぶし円は簡単なんだけど実は落とし穴があるにょ。

　GCIRCLE 128,96,60,2
　GPAINT 128,96,2

これで(128,96)を中心とした半径60の赤色の円が描けるのでそれをGPAINTで塗れば赤色に
なるかというと必ずしも塗りつぶせるとは限らないにょ。
というのも円の下に何も描かれてないとは限らないためにょ。
したがって、GPAINTで中心点を指示したらそこからどこまで塗りつぶせばいいかを明確に
する必要があるにょ。
それさえ分かれば後は簡単で画面上で使ってない色を境界線に設定すればいいだけにょ。
GCOLOR 255を使ってないならばこれで塗りつぶせるにょ。

　GCIRCLE 128,96,60,255
　GPAINT 128,96,2,255

これではこの上からさらに描くことはできないので最後にGCIRCLE 128,96,60,2としておけば
完璧にょ。
では、塗りつぶし楕円はどうなのかというとそもそもプチコンでは楕円を描く命令がないため
自前で用意するしかないにょ。
楕円の前に円をGCIRCLEで描く方法を考えてみるとこれは正多角形を細かく描けば円に近くなる
ということを利用すれば簡単にできるにょ。
例えば時計の文字盤の12時の方向を0度として時計回りに描画していく場合には正180角形は次の
ように描けるにょ。（どのように描画されているかはNEXTの前にWAIT 3を置けばよく分かる）

　X=128:Y=96:R=60:C=2
　X1=0:Y1=R
　FOR I=0TO 360 STEP 2
　　X2=SIN(RAD(I))
　　Y2=COS(RAD(I))
　　GLINE X+X1,Y-Y1,X+X2,Y-Y2,C
　NEXT

これで円の描画ルーチンは完成したので上記のように境界色を変えて描いてGPAINTしてそして
描画色で描き直せば完了にょ。
楕円の場合はX座標、もしくはY座標に加える値に一定の比率で掛け合わせるといいだけにょ。
しかし、そんなことをしなくても塗りつぶし円は描けるにょ。
というのもY軸に平行な直線を用意してそれをX座標を1ずつ大きくしていき円と直線の交点の
座標を求めてその2点を繋げばいいだけにょ。
こうして書くと難しそうだけど実は簡単で半径10の円ならばX座標は描画座標の中心点を原点と
した相対座標で-10、-9、ｰ8・・・8、9、10と変化させていきX軸上との点と直線と円の交点と
原点を結んだ直角三角形で考えると斜辺は円の半径であるため交点のY座標は三平方の定理から
簡単に求めることができるにょ。
楕円の場合はその縦横比を変えただけなので簡単に求められるにょ。

　FOR I=-R TO R
　　A=F*SQR(R*R-I*I):GLINE X+I,Y-A,X+I,Y+A,C
　NEXT
http://ww5.tiki.ne.jp/~ochame/petitcom/tips/routine.htm#circle

次に考えたのは塗りつぶされた多角形にょ。
多角形は三角形さえ描ければ何とかなるので塗りつぶされた三角形を描くことにするにょ。
これは上記の塗りつぶされた円と同様に境界線の色を変えて三角形を描いてそしてGPAINTで
塗ったら終了にょ。
しかし、ここで厄介なのはどこを基準に塗るかということにょ。
GPAINTの場合はその領域の中の座標を指定しなければならないからね。

これは実は簡単にょ。
確実に三角形の中にある点を指定すればいいにょ。
例えば重心を基準にするならば三点の座標を合算して3で割ればいいので簡単にょ。
そしてできたのがこれにょ。

　FOR J=0TO 1
　　FOR I=0TO 2
　　　GLINE X(I),Y(I),X((I+1)%3),Y((I+1)%3),C*J+!J*255
　　NEXT
　　IF !J THEN GPAINT (X(0)+X(1)+X(2))/3+0.5,(Y(0)+Y(1)+Y(2))/3+0.5,C,255
　NEXT
　RETURN

本来ならば3本＋3本で6本のGLINEが必要になるけどFOR～NEXTを用いて1本のみの記述で
済むようにしているにょ。
これで概ね問題はないのだけどGPAINTだと細長い三角形の場合は隅の方が塗れないという
問題があるにょ。
それに加えて高さがほぼ0の三角形だと表示誤差によって重心の座標が画面上に描かれている
三角形の中には来ないという問題があるにょ。
要するに細長い三角形は塗れなかったり塗るのに失敗してしまうことがあるということにょ。

これではまずいので別のやり方を考えるにょ。
三角形でも上記の円のようにY軸に平行な直線をX座標を1ずつ大きくしながら変えるという
方法で描くことができるにょ。
ただ一律ではいかず両端の点との間にある頂点を挟んで左右の2回に分ける必要があるにょ。
この変化の割合は1次方程式なので簡単にょ。
できるだけ高速にするためループ内には増分だけ記述することにしたにょ。
ここで問題としてはX座標が同じ点が2つあったらどうなるのかということにょ。
2回に分けることなく1回で済むのだけどそうなると基点の座標も変わってくるためその修正が
必要になるにょ。（あとX座標が同じ2点があったら傾きが無限大、つまり、三角形の辺がY軸に
平行になるためその例外処理も行う必要がある）
そうしてできたのがこれにょ。

　SORT 0,3,X,Y
　X=X(0):Y=Y(0):Z=Y:Q=(Y(2)-Y(0))/(X(2)-X(0))
　FOR J=0TO 1
　　M=X(J)-X(J+1):P=(Y(J)-Y(J+1))/(M+!M):Y=Y+(Y(1)-Y(0))*!M
　　FOR I=X(J)TO X(J+1)-1
　　　GLINE I,Y,I,Z,C:Y=Y+P:Z=Z+Q
　　NEXT
　NEXT
　RETURN
http://ww5.tiki.ne.jp/~ochame/petitcom/tips/routine.htm#triangle

このルーチンでは上記のGPAINTにあるような塗りミスはなくなっているにょ。
塗りつぶし三角形が描画できればポリゴン表示が可能になるにょ。
もっとも、1回平均1.2フレームということで1秒間に平均50回しか実行できないのでこれで
まともにポリゴンゲームが作れるとは到底思えないけどね（笑）
これでも処理速度はほぼ限界に近いのであとは原理上X方向に広い（横長）三角形が遅い
ため横長に最適化したルーチン（Y座標方向に1ずつ大きくしていくようなルーチン）を作り
座標を調べて2者から高速な方を選択するということくらいしかここから大幅な速度向上は
ないにょ。
基本アルゴリズムさえわかればその使い回しがいくらでも効くのでいろいろ試してみるのが
一番だと思うにょ。（アルゴリズムによってキレイさが変わるだけではなく処理速度が数倍～
10倍変わる場合もあるのでいろいろ考えて比較してみると面白い）
もちろん、すでにできあがっているルーチンを利用するだけでもいいけどね。

《　2/13　追記　》

昨日作った塗りつぶし三角形の描画ルーチンをさらに高速化してみたにょ。
すでに書いているように縦横どちらに長いかを事前に判断してループ回数の短いものを選択
することにしたにょ。
そして、ループの初期値と終了値に使われていた配列変数を固定変数に変えて、不要な
コロンを省略などの方法をとることによって1回あたり平均1.24フレームだった処理を平均
0.72フレームへと約1.7倍高速化ができたにょ。

@TRI
SORT 0,3,X,Y:P=X(2)-X(0)
SORT 0,3,Y,X:Q=Y(2)-Y(0)
IF Q>P THEN @T
X=X(0)Y=Y(0)M=Y-Y(2)Q=(X(0)-X(2))/(M+!M)Z=X
FOR J=0TO 1
　M=Y(J)-Y(J+1)P=(X(J)-X(J+1))/(M+!M)
　X=X+(X(1)-X(0))*!M:A=Y(J)B=Y(J+1)-1
　FOR I=A TO B
　　GLINE X,I,Z,I,C:X=X+P:Z=Z+Q
　NEXT
NEXT
RETURN
@T
SORT 0,3,X,Y
X=X(0)Y=Y(0)M=X-X(2)Q=(Y(0)-Y(2))/(M+!M)Z=Y
FOR J=0TO 1
　M=X(J)-X(J+1)P=(Y(J)-Y(J+1))/(M+!M)
　Y=Y+(Y(1)-Y(0))*!M:A=X(J)B=X(J+1)-1
　FOR I=A TO B
　　GLINE I,Y,I,Z,C:Y=Y+P:Z=Z+Q
　NEXT
NEXT
RETURN
http://ww5.tiki.ne.jp/~ochame/petitcom/qr/triangle_h.png

まだ高速化するならば他に使われている配列変数をすべて固定変数に書き直すという方法も
考えられるけど内側のループではそれによる速度向上は大きいものの外側のループではその
速度向上はほとんどないにょ。
というのも、縦長、横長を判別してループ回数が短いものを選択しているものの内側の
ループは平均80回実行しているのに対して外側のループは2回しか実行していないためにょ。
処理時間でいえば内側のループが92％くらいで外側のループが8％くらいにょ。
そうすると配列変数を固定変数に書き直すことで3倍速くなったとしても8％かかっていた
時間が3％に減るだけであり、全体としては100％から95％へと5％程度の高速化しか見込め
ないにょ。
サイズの大きな三角形ばかり表示しているためこのようになっていてこれをポリゴン表示に
用いる場合にはそこまで大きな三角形を表示する機会は少ないということを考えると5％の
数倍の速度向上効果が見込めそうにょ。

では、1回あたり平均0.72フレームという現状の描画速度も画面の半分程度でいいのならば
ループ回数が半分になるのだけど実際に1/2画面でのランダム表示で試したところ1回あたり
平均0.36フレームとなりほぼ2倍速になったにょ。（本来ならばループ回数が半分に減っても
2倍速には満たないはずなのだけどGLINEで描画する長さも半分に減っているため）
さらに高速化すべく現状の1ドット単位での描画から2ドット単位での描画に変えたところ
1回あたり約0.24フレームとなったにょ。（当初と比べるとループ回数は1/4になっており
外側のループ処理の処理時間の割合が高くなるためそこを改善すればここからさらに1割
以上は高速化できそう）
昨日発表した段階と比べると5倍の速度にょ。（まぁ表示しているものが異なるため同一の
環境下だと最初の1.7倍速になるけど）
この速度ならば250ポリゴン/秒の描画が可能となるため1画面内で表示するポリゴン数を
20ポリゴン以下に抑えればジオメトリ演算込みでも10fpsを確保できそうな感じにょ。
ポリゴンゲームを作るには少々（というか、かなり）厳しいけどチャレンジ精神旺盛な人は
試してみるのもいいかもしれないにょ。