2015年05月09日

プチコン3号 32日目 球を描く(2)

pc32-1.jpg

今回は、前回の続きで、上の画面のような前回よりもリアルな球を描いてみます。

前回は球を正面から光で照らした場合の陰影を描画しました。
しかし、球を正面から光で照らすシーンは、日常ではあまり出会いません。
もっとも一般的なのは、満月でしょうか・・・


今回は日常的に目にする、斜め上からの光で照らされている球を描画します。
また、光が物体の表面で鏡面反射されて生じる、ハイライトも描き込みます。

前回説明した「光の当たる角度」と「環境光」、さらに今回の「ハイライト」という3つの成分の合成でシェーディングを表現する手法は、「フォンの反射モデル」と呼ばれる古典的な手法です。
(ちなみに「フォン」は発明者の名前です。)


今回のプログラムでは、光のあたる角度は、球の正面から照らす場合を回転角0、球の真上から照らす場合を回転角π/2(90度)とし、X軸の周りの回転角だけで表します。左右へは傾けません。
これによって、画像が左右対称になり、全ピクセルの半分の計算で描画を終えることができます。
(左右に傾けても、対称軸が傾くだけで対称にはなりますが、ピクセルの位置を計算しづらくなります。)

光を斜め上方向に移動するには、25日目で解説した回転の座標変換を使います。

下図では、図左は前回のプログラムのように上(Z軸方向)から光が当たっています。
図右は、光が角度θだけ傾いています。
このとき、球面で一番明るくなるのは、真上からθだけ傾いた点Bになります。
では点Aの明るさはどうなるかというと、図左で真上から−θだけ傾いた点Cの明るさと同じになります。
pc32-3.jpg

以上は、球の中心の周りに、球も光も含めた全体が角度θだけ回転したと考えれば、直観的にも理解できると思います。


また、ハイライトはその強さのみを、0から1の範囲で与えることにします。

ハイライトの出現位置は、球の最も明るい場所ではなく、光の角度の半分の角度の位置に出ます。
たとえば

・光の方向が0度のときはハイライトの位置も0度(円の中心)
・光の方向が90度(上方)のときは、ハイライトの位置は45度(下図参照)

となります。
pc32-4.jpg

ハイライトの光の分布にもいろいろなモデルがありますが、要は鋭いピークがありつつ滑らかに変化していればもっともらしく見えます。
今回は「半分の角度で光を当てたときの明るさ」を500乗して作っています(Phong分布相当)。
また、反射光の色は物体の色ではなく、白色としました。


次の図は、今回のプログラムで角度とハイライトのパラメータをいろいろ変えてみた画像です。
上段は光の角度を左から0度(正面)、30度、60度、90度(真上)の4通りに変えています。
下段は、角度は60度のまま、ハイライトの係数を0.1、0.3、0.5、0.7と変えています。

pc32-2.jpg


プログラムは以下の通りです。
傾いた光に関する部分を紫、ハイライトに関する部分をオレンジにしています。
CLS:GCLS
T=MAINCNT
DRAWSPHERE 100,20,170,192,192,128,0.2,PI()/4,0.4
PRINT (MAINCNT-T)/60;" SECONDS ELAPSED"

DEF DRAWSPHERE X0,Y0,SIZE,R0,G0,B0,GL,T,SP
VAR R,RR,X,XX,Y,YY,Z,ZZ,YMAX,NZ,NY,C,R1,G1,B1
R=SIZE/2+0.5
RR=R*R
X0=X0+R
Y0=Y0+R
X=-0.1
WHILE R>=X
Y=-0.1
XX=X*X
YY=Y*Y
YMAX=RR-XX
ZZ=YMAX-YY
WHILE ZZ > 0
Z=SQR(ZZ)
ROTATE Y/R,Z/R,T OUT NY,NZ
NZ=MAX(0,NZ)
C=SHADING(NZ,1-GL,GL)
RGB_ADD 0,0,0,C,R0,G0,B0 OUT R1,G1,B1

ROTATE Y/R,Z/R,T/2 OUT NY,NZ
NZ=MAX(0,NZ)
C=SPECULAR(NZ,SP,0.002)
RGB_ADD R1,G1,B1,C,255,255,255 OUT R1,G1,B1

C=RGB2(255,R1,G1,B1)
GPSET X0-X,Y0-Y,C
GPSET X0+X,Y0-Y,C

ROTATE -Y/R,Z/R,T OUT NY,NZ
NZ=MAX(0,NZ)
C=SHADING(NZ,1-GL,GL)
RGB_ADD 0,0,0,C,R0,G0,B0 OUT R1,G1,B1

ROTATE -Y/R,Z/R,T/2 OUT NY,NZ
NZ=MAX(0,NZ)
C=SPECULAR(NZ,0.4,0.002)
RGB_ADD R1,G1,B1,C,255,255,255 OUT R1,G1,B1

C=RGB2(255,R1,G1,B1)
GPSET X0+X,Y0+Y,C
GPSET X0-X,Y0+Y,C
Y=Y+1
YY=Y*Y
ZZ=YMAX-YY
WEND
X=X+1
WEND
END

DEF SHADING(VAL,DIF,AMB)
RETURN AMB+DIF*VAL
END

DEF SPECULAR(VAL,SP_I,SP_SIZE)
RETURN SP_I*POW(VAL,1/SP_SIZE)
END

DEF RGB_ADD R0,G0,B0,K,R1,G1,B1 OUT R2,G2,B2
R2=MIN(255,R0+K*R1)
G2=MIN(255,G0+K*G1)
B2=MIN(255,B0+K*B1)
END

DEF RGB2(A,R,G,B)
IF RND(8) < (R AND 7) THEN R=R+8
IF RND(8) < (G AND 7) THEN G=G+8
IF RND(8) < (B AND 7) THEN B=B+8
RETURN RGB(A,R,G,B)
END

DEF ROTATE X,Y,T OUT X1,Y1
X1=COS(T)*X - SIN(T)*Y
Y1=SIN(T)*X + COS(T)*Y

END

回転角は変数Tに入っています。
回転の処理(手続きROTATE)は25日目に使ったものと同じです。

ハイライトの計算については、まず光がT/2の角度で入ってきた場合のピクセルの反射の強さを求めます。
そして、反射の強さを関数SPECULARでハイライトに変換します。
ハイライトは強さのパラメータが変数SPに入っています。
SPECULARは、反射の強さをVAL、ハイライトの強さをSP_I、ハイライトの広がり具合をSP_SIZEで与えます。
最後のSP_SIZEは小さくするほどハイライトも小さくなります。
ただし、実際にハイライト部分のピクセル数などを指定しているわけではなく、VALを1/SP_SIZE乗するだけです。
値としては、0.01以下が良いでしょう。
今回は0.002にしています。

画像の明暗は左右対称になりますが、形状自体は上下にも対象です。
そこで、ループの1回ごとに、上半分のピクセルの明るさと下半分のピクセルの明るさの計算を行っています。
ほぼ同じコードがループの前半と後半にありますが、前半が上半分、後半が下半分に関する計算です。

このプログラムで前回と同じ大きさの球(直径170ピクセル)を描くのに3.5秒かかります。
前回は全体の1/8のピクセルの明るさだけを計算すれば済みましたが、今回は全体の半分の計算が必要で、かつ計算自体も増えているためです。
posted by boochow at 22:24| Comment(0) | プチコン講座 | このブログの読者になる | 更新情報をチェックする

2015年05月04日

プチコン3号 31日目 球を描く(1)

pc31-1.jpg

前回紹介したレイトレーシングの手法は、時間がかかりすぎるのでゲームの画像表示に使うには向いていません。
今回は、球を一つだけ、レイトレーシングよりも高速に描画するプログラムを作ってみます。
上の画面が実行結果で、直径170ピクセルの球を0.6秒弱で描画しています。
アニメーションに使うのは難しいですが、スプライトやBGの作成には使うことができるでしょう。

球を球らしく見せるには、陰影が重要です。
光の方向や強さなどに応じてピクセルの明るさを決めることを「シェーディング」と言います。

下図は球面が上方から来る光に照らされている様子を示しています。
(以下、球面の光の当たらない下半分は無視します。)
地球が太陽に照らされている様子を思い浮かべれば分かりやすいでしょう。
このときシェーディングは基本的には以下のようにして行えます。

まず、球面のごく小さな一部を考えます。
これは、ある傾きを持った平面にほぼ等しいと考えられます。
この小さな平面の明るさは、光が来る方向(図では垂直方向)に対して平面が直角(図では水平)になっているとき、最大になります。
平面が傾くにつれて暗くなっていき、面が垂直になったときに明るさはゼロになります。
この明るさは、ある長さの棒を平面に対して垂直に立てるとき、その棒の両端の座標のZ値の差分(図の赤い矢印)に比例します。
pc31-2.jpg

プログラムにするために、上記を数式に直してみます。
図では上から光が来ていますが、この上方向をZ軸とします。
そして、球面の中心を原点とします。
球面上の点は、半径をrとすると

 x2+y2+z2=r2

を満たします。

このとき、シェーディングに必要な値である赤い矢印の長さは、実は球の半径とzの値だけで決まります。
直感的にはちょっとわかりにくいかもしれませんが、zが最大となるのは図の球面の一番高い部分(中央部分)で、このときx=y=0でz=rとなり、図の球面の両端部分ではz=0となるのはすぐわかると思います。

球面に垂直に棒を立てると、その棒は必ず球の中心を指します。
従って

・棒を斜辺とし、水平および垂直な辺を持つ直角三角形
・球面の中心から棒を立てた点までの線分を斜辺とし、水平および垂直な辺を持つ直角三角形

は相似の関係になります。
すると、

・棒の長さと、赤い矢印の長さの比
・球面の半径と、棒を立てた点のZ座標値の比

が等しいことが言えるので、棒の長さが1のとき、赤い矢印の長さは(棒を立てた点のZ座標値/球面の半径)となります。

以上を用いて、球を光源側から見た場合(図では上方向から見た場合)の画像を描いてみます。
先に書いたとおり、球面の方程式は

 x2+y2+z2=r2

です。
従って半径rの球面を描くには、x,yを変化させて、それに対応するzの値を

 z=SQR(r2-x2-y2)

で求め、zの値に応じて(x,y)のピクセルの明るさを変化させます。

プログラムは以下のようになります。

CLS:GCLS
T=MAINCNT
DRAWSPHERE 100,20,170,255,255,176,0.2
PRINT (MAINCNT-T)/60;" SECONDS ELAPSED"

DEF DRAWSPHERE X0,Y0,SIZE,R0,G0,B0,GL
VAR R,RR,X,XX,Y,YY,Z,ZZ,YMAX,NZ,NY,C,R1,G1,B1
R=SIZE/2+0.5
RR=R*R
X0=X0+R
Y0=Y0+R
X=-0.08
WHILE R>=X
Y=X
XX=X*X
YY=XX
YMAX=RR-XX
ZZ=YMAX-YY
WHILE ZZ > 0
Z=SQR(ZZ)
NZ=Z/R
C=SHADING(NZ,1-GL,GL)
RGB_ADD 0,0,0,C,R0,G0,B0 OUT R1,G1,B1
C=RGB2(255,R1,G1,B1)
GPSET X0+X,Y0+Y,C
GPSET X0-X,Y0+Y,C
GPSET X0+X,Y0-Y,C
GPSET X0-X,Y0-Y,C
GPSET X0+Y,Y0+X,C
GPSET X0-Y,Y0+X,C
GPSET X0+Y,Y0-X,C
GPSET X0-Y,Y0-X,C
Y=Y+1
YY=Y*Y
ZZ=YMAX-YY
WEND
X=X+1
WEND
END

DEF SHADING(VAL,DIF,AMB)
RETURN AMB+DIF*VAL
END

DEF RGB_ADD R0,G0,B0,K,R1,G1,B1 OUT R2,G2,B2
R2=MIN(255,R0+K*R1)
G2=MIN(255,G0+K*G1)
B2=MIN(255,B0+K*B1)
END

DEF RGB2(A,R,G,B)
IF RND(8) < (R AND 7) THEN R=R+8
IF RND(8) < (G AND 7) THEN G=G+8
IF RND(8) < (B AND 7) THEN B=B+8
RETURN RGB(A,R,G,B)
END


手続きDRAWSPHEREが描画処理の本体です。
パラメータは

・左端のX座標
・上端のY座標
・直径
・色(R,G,B)
・環境光係数

となっています。

球のサイズは半径ではなく直径で指定しています。
球は一辺が直径に等しい正方形の領域に描画されます。

最後のパラメータ「環境光係数」には、通常0.1〜0.2程度を指定します。
このパラメータは球全体の明るさを底上げします。
1.0を指定すると、陰影のない塗りつぶした円が描画されます。

DRAWSPHEREの中身は2重のループになっています。
外側のループがX座標を1ずつ増やし、内側のループがY座標を1ずつ増やします。
(X0,Y0)が中心の座標です。

内側のループの中で、GPSETを8回連続して行っています。
今回描画する球では、明るさの値は原点を中心とした同心円上で同じ値になります。
従って下図のように、座標を入れ替えたり符号を反転することによって、一度の計算で8か所のピクセルの値が決まります。
全体の1/8を計算すれば十分なので、ループは図の網掛けした部分だけをカバーしています。
pc31-3.jpg

RGB_ADD手続きは、その名の通り色の加算(と定数倍)を行う手続きです。
色(R0,G0,B0)に色(R1,G1,B1)をK倍したものを加算し、結果を(R2,G2,B2)に代入します。

RGB2関数は前回も説明しましたが、疑似的に中間色を生成して色の変化を滑らかに見せます。

なお、ピクセルが球の内部か外部かを判定する際、境界値付近での判定を意図的に制御するために、変数の初期値等を小数点以下のオーダーで幾何学的な値よりも大きくしたり小さくしたりしています。
たとえば

・半径Rが直径の1/2よりも0.5大きい
・Xの初期値が0ではなく-0.08

などです。
いずれも幾何学的には、0.5や-0.1は不要ですが、特に径が小さい円を描くとき、形状に微妙な違いが出てきます。
掲載したプログラムは、直径が16ピクセルや14ピクセルの形状が私の好みのもの(下図)になるように調整しています。
(その代わり、直径15ピクセルを指定しても16ピクセルになってしまいますが・・・)
PC31-4.png


今回のプログラムは、球を正面から光で照らした場合の陰影を計算しています。
ちょうど、満月のようなものです。

次回はこのプログラムを少し拡張して、前回のレイトレーシングの例で示したような、斜め方向から照らした場合の陰影を計算してみます。
posted by boochow at 10:58| Comment(6) | プチコン講座 | このブログの読者になる | 更新情報をチェックする

2015年04月15日

プチコン3号 30日目 レイトレーシングでCGを描いてみる

pc30-1.jpg

今回は、コンピュータグラフィックスの古典的な手法であるレイトレーシング法のプログラムを紹介します。
これは、下記のリンク先にある、"Tiny Raytracer"というJavaScriptで書かれたプログラムをプチコン3号用に書き直したものです。

Gabriel Gambetta - Tiny Raytracer

レイトレーシングの原理は、物体から視点に届く光を計算するために、視点への光の通り道を逆算していくというものです。
そして、通り道の先に物体があったら、その物体に光が反射していると考えて、反射の先の通り道をさらに辿って行きます。
下の図はWikipediaの引用ですが、イメージがわきやすいと思います。

Ray trace diagram.svg
"Ray trace diagram" by Henrik - Own work. Licensed under GFDL via Wikimedia Commons.



プログラムは140行あまりと短いので、まずは全体を掲載します。
なお今回は移植ですので、Miiverseへのアップロードは行いません。
OPTION STRICT

DEF READ_ARRAY A,SZ,LBL
VAR I
RESTORE LBL
FOR I=0 TO SZ
READ A[I]
NEXT
END

DEF DOT(A,B)
RETURN A[0]*B[0]+A[1]*B[1]+A[2]*B[2]
END

DEF A_MINUS_BK A,B,K,C
C[0]=A[0]-B[0]*K
C[1]=A[1]-B[1]*K
C[2]=A[2]-B[2]*K
END

VAR W=240 'IMAGE SIZE
VAR T,C

DIM SPHERES[36]
VAR SPECULAR=6
VAR REFLECT=7
@SPHERES
'IF YOU EDIT W VALUE, CHANGE "240" TO NEW W
DATA 240, 0,-240,0, 9,9,0, 240,2
DATA 1, 0, 0,3, 9,0,0, 240,3
DATA 1,-2, 1,4, 0,9,0, 9,4
DATA 1, 2, 1,4, 0,0,9, 240,5
READ_ARRAY SPHERES,35,"@SPHERES"

VAR AMBIENT_LIGHT=2

DIM LIGHTS[4]
@LIGHTS
DATA 8,2,2,0
READ_ARRAY LIGHTS,3,"@LIGHTS"

DEF CLOSEST_INTERSECTION(B,D,TMIN,TMAX)
VAR _A,_V,_Q,_B,_D,_R,_F,_9Q
DIM J[3], SC[3]'SPHERE CENTER
T=W
_A=2*DOT(D,D)
_V=0
FOR _Q=0 TO 3 'NUM OF SPHERES
_9Q=_Q*9
_R =SPHERES[_9Q]
SC[0]=SPHERES[_9Q+1]
SC[1]=SPHERES[_9Q+2]
SC[2]=SPHERES[_9Q+3]
A_MINUS_BK B,SC,1,J
_B=-2*DOT(J,D)
_D=_B*_B - 2*_A*(DOT(J,J)-_R*_R)
IF _D > 0 THEN
_D=SQR(_D)

_F=(_B-_D)/_A
IF TMIN<_F && _F<TMAX && _F<T THEN
_V=_9Q+1
T=_F
ENDIF

_F=(_B+_D)/_A
IF TMIN<_F && _F<TMAX && _F<T THEN
_V=_9Q+1
T=_F
ENDIF
ENDIF
NEXT
RETURN _V
END

DEF TRACE_RAY(B,D,TMIN,TMAX,DEPTH)
VAR I,_S,_N,_I,_L,_U,_K,_4I
DIM N[3],X[3],SC[3],L[3],LC[3],M[3]
_S=CLOSEST_INTERSECTION(B,D,TMIN,TMAX)
IF _S == 0 THEN RETURN 0
SC[0]=SPHERES[_S]
SC[1]=SPHERES[_S+1]
SC[2]=SPHERES[_S+2]

A_MINUS_BK B,D,-T,X
A_MINUS_BK X,SC,1,N
_N=DOT(N,N)
_I=AMBIENT_LIGHT
FOR I=0 TO 0 'NUM OF LIGHTS-1
_4I=I*4
_U =LIGHTS[_4I]
LC[0]=LIGHTS[_4I+1]
LC[1]=LIGHTS[_4I+2]
LC[2]=LIGHTS[_4I+3]
A_MINUS_BK LC,X,1,L
_K=DOT(N,L)
A_MINUS_BK L,N,2*_K/_N,M
IF CLOSEST_INTERSECTION(X,L,1/W,1)== 0 THEN
_I = _I + _U * ( MAX(0, _K/SQR(DOT(L,L)*_N)) + MAX(0,
POW(DOT(M,D)/SQR(DOT(M,M)*DOT(D,D)),SPHERES[_S+SPECULAR])))
ENDIF
NEXT

VAR LOCAL_COLOR=SPHERES[_S+3+C]*_I*2.8
VAR REF=SPHERES[_S+REFLECT]/9
VAR P[3]
DEPTH=DEPTH-1
IF DEPTH < 0 THEN
RETURN LOCAL_COLOR
ELSE
A_MINUS_BK D,N,2*DOT(N,D)/_N,P
RETURN TRACE_RAY(X,P,1/W,W,DEPTH)*REF + LOCAL_COLOR*(1-REF)
ENDIF
END

GCLS:CLS
VAR X,Y,H
VAR TSTART=MAINCNT
DIM CAM[3],POS[3]
DIM PX[3]
CAM[0]=0:CAM[1]=1:CAM[2]=0
H=W/2
FOR Y=H TO -H STEP -1
FOR X=-H TO H
FOR C=0 TO 2
POS[0]=X/W
POS[1]=Y/W
POS[2]=1
PX[C]=TRACE_RAY(CAM,POS,1,W,2)
NEXT
GPSET 80+X+H,H-Y,RGB2(255,PX[0],PX[1],PX[2])
LOCATE 0,0:?X+H,H-Y
NEXT
NEXT
?(MAINCNT-TSTART)/60;" SECONDS ELAPSED"

DEF RGB2(A,R,G,B)
IF RND(8) < (R AND 7) THEN R=R+8
IF RND(8) < (G AND 7) THEN G=G+8
IF RND(8) < (B AND 7) THEN B=B+8
RETURN RGB(A,R,G,B)
END

移植はなるべくオリジナルの変数名等を変えずに行いました。
ただ、JavaScriptは変数名等で大文字と小文字を区別しますので、移植にあたっては小文字の変数名は先頭に"_"を付けて区別しています。

このプログラムの中身については、以下に概略を書いておきますが、きちんと理解するには高校程度の幾何(ベクトル)の知識が必要です。
オリジナルのほうの解説も参考にしてください(英語ですが)。


変数Wは、生成する画像の一辺のピクセル数です。
小さくすれば、画像も小さくなりますが、計算時間も短くなります。
この数値を変更する場合は、後述の球のデータ中の"240"という部分も、Wの値に一致させてください。


関数DOTは、2つのベクトルの内積(dot product)を計算します。
2つのベクトルa, bの内積は、|a||b| cosθ(|v|はvの長さ、θは2つのベクトルがなす角)になります。
しかし、実際には三角関数を使わずに計算することができます。(プログラムリストを見てください。)

内積は、方向の一致度合いを計算していると考えてください。
長さ1のベクトル同士では、完全に一致したとき1、直角の関係にあるとき0、完全に逆向きのとき-1になります。


配列SPHERESは、球に関するデータです。
1つの球について9つのパラメータがあります。
その内訳は、

・半径
・中心座標(X,Y,Z)
・色(R,G,B)
・輝き
・反射率

となっています。
色および反射率は、それぞれ0…9の範囲で指定してください。


光源の情報は配列LIGHTSに入っています。
1つの光源のパラメータは4つで、強度と光源の座標X,Y,Zです。
他に、環境光を表すAMBIENT_LIGHTというパラメータもあります。
光源の強度とAMBIENT_LIGHTは、合計して10になるように設定してください。


関数CLOSEST_INTERSECTIONは、点Bから方向Dへ向かう直線が最初にぶつかる球と、その交点を求めます。
どの球にもぶつからない場合は0、ぶつかる場合は正の数Sを返します(SPHERES[S]が、ぶつかった球の中心のX座標になります)。
交点を表すパラメータはグローバル変数Tに入ります。
交点は、B+D*Tになります。
TMINとTMAXは、ぶつかる点を探す範囲(Tの最小値と最大値)を指定します。


レイトレーシングの本体である関数TRACE_RAYは、各変数の意味を下図に示します。
pc30-4.jpg


一番最後にある関数RGB2は、プチコン3号の標準のRGB関数の代わりに使います。
プチコン3号では、RGBにそれぞれ8ビットの値を指定できますが、実際には上位5ビットしか使われません。
そのため、球面のようになめらかに階調が変化する画像では、色数が少ないことによる縞模様(バンディング)が目立ってしまいます。

RGB2は、乱数によって擬似的に中間色を生成します。
通常は、下位3ビットが0〜7のどの値でも同じ色になってしまいますが、RGB2では(下位3ビットの値/8)の確率で1階調明るい色を出力します。
少ない階調で擬似的に中間色を表現する方法はディザリングといい、今回のものは超簡易版ですが、誤差拡散法などより高画質なアルゴリズムが各種提案されています。

次の図は、上が標準のRGB関数を使った場合、下がRGB2関数を使った場合です。
pc30-2.jpg
pc30-3.jpg
posted by boochow at 01:12| Comment(0) | プチコン講座 | このブログの読者になる | 更新情報をチェックする

2015年03月29日

プチコン3号 29日目 擬似3D(6) 迷路の中を動く敵を隠面消去つきで描画する

pc29-1.jpg

前回は隠面消去のアルゴリズムを使って迷路の壁を表示しました。
しかし、表示できるものが壁だけでは寂しいですね。
今回は前回のプログラムを拡張して、3D迷路の中に敵を表示しました。
これで、11日目の迷路探検ゲームの3D版ができます。

今回のプログラムは長いので、全体は掲載しません。
動かしてみたい方はMiiverseからダウンロードしてください。
公開キーは【BKEYX39J】です。
操作はスライドパッドで移動、L/Rで方向転換です。
敵とぶつかると目が回ってしまいます。
ゴールの黄色い壁を目指して進んでください。


この記事では、3D迷路の中に敵を表示する場合の描画処理方法について解説します。
その前にまず、迷路の中をカメラが移動する場合の処理について、簡単に解説しておきます。
迷路の中を移動する場合の処理については、7日目に記事を書きました。

プチコン3号 7日目 ドラクエ風に迷路の中を歩き回る: 楽しくやろう。

今回のプログラムでも、基本的な処理は全く同じです。
ただ、迷路の部屋やマップに割り当てるピクセル数が違います。

7日目の記事では、迷路が32×32ピクセルの部屋をつなぎ合わせたもので、その中を16×16ピクセルのスプライトを動かしていました。
今回のプログラムはスプライトは使いませんが、その代わりに3DSのスクリーンが迷路の中を向きを変えながら動くと考えます。
スクリーンの幅は400ピクセルですので、スクリーンの向きが変わることも考慮すると、400×400ピクセルのオブジェクトが迷路の中を動き回っていることになります。

従って、迷路の通路の幅は少なくとも400ピクセル以上必要です。
また、カメラの座標はスクリーンの中心だとすると、その座標は迷路の壁から少なくとも200ピクセルは離さないと、下図に示すようにスクリーンに壁の向こう側が映ってしまいます。
pc29-2.jpg

こういったことを考慮して、今回のプログラムでは、大きさに関する数値を7日目のプログラムの16倍にしました。
下図のように、迷路の1部屋は1024×1024ピクセルになります。
カメラの中心点は常に壁から256ピクセル以上離れており、スクリーンに壁の向こうが写ることはありません。
pc29-3.jpg

処理内容自体は7日目と大きく変わるところはなく、1部屋がマップで4×4マスになる点も同じです。
ただし、スプライトでは座標値はスプライトの左上の点の座標値でしたが、今回のプログラムではカメラや敵の座標は中心の点の座標値になっています。


それでは、本題の敵の表示の話に戻ります。

グラフィックスで敵を描画する際、壁の向こうに居る敵は、壁で隠さなければなりません。

前回は壁だけの描画でしたので、遠くの壁を先に、近くの壁を後に描画することで隠面消去を実現していました。
敵の描画を行う場合も基本は同じです。
敵よりも遠い壁を描いた後に、敵を描き、敵より近い壁はその後に描いていくことになります。

このためには、敵と壁を区別することなく、Z座標の大きい順に並べ替える必要があります。

前回のプログラムでは、壁の遠近の判定において、壁の中心のZ座標で壁全体を表すことで計算を簡略化しました。
簡略化の条件として、迷路の壁が「碁盤目状に配置されている」という条件がありました。
これはより詳しく言うと、壁同士が交差しない(壁の前後関係が途中で変化しない)こと、壁の大きさが全て同一であること、という条件になります。
pc29-6.gif

敵と壁を同列に扱うために、敵のZ値も、敵の中心のZ座標で敵全体を現すことにします。

敵や壁のZ値を、中心の座標だけで管理するということは、ポリゴンの向きによらず中心の座標だけで、敵と壁の前後関係が判断できなければなりません。

次の図のような状態の、敵とその手前の壁について考えます。
これは迷路を上から見た状態で、敵の形状は円柱で近似しています。
Z軸は下から上、つまり下にあるものほど手前にあるものとします。

このとき、壁が手前になるためには「壁の中央のZ値」が「敵の中心のZ値」よりも常に小さくなければなりません。
ところが実際には、敵の位置によっては壁が敵よりも遠くにあると判定されてしまいます。
pc29-4.jpg

図では青の線が壁のZ値なので、緑の円柱は壁の向こうですが、赤の円柱は壁の手前にあるという判定になります。
その結果、図右下のように、間違った前後関係で描画されてしまいます。
壁の手前半分のZ値は、壁の中央のZ値よりも実際には小さい(手前にある)のに、それが考慮されていないためにこのようなことが起こります。

これを回避するには、敵のZ値が壁のZ値より小さい時に、上の図で黄色で示したエリアに敵のポリゴンが重ならないようにします。
黄色の領域は前後関係の判定に用いる壁のZ値よりも実際のZ値のほうが小さいために、遠近が正しく判定できない領域だからです。

この条件を満たすには敵のポリゴンの「位置」と「大きさ」の制限が必要です。
pc29-5.jpg

上の図にあるように、

・敵の中心が通路の中央であること
・敵の幅が通路の幅の1/2未満であること

の2つを両方満たしている場合(緑の円)、黄色の領域と重なることはありません。
一方、赤の円柱は2番目の条件よりもサイズが大きいため、間違った前後関係で描画されてしまいます。


というわけで、だいぶ長い解説になってしまいましたが、前回のプログラムに敵の描画を追加したプログラムを以下に示します。
まずはZバッファの処理の部分です。
FOR I=0 TO 399+NUM_E+1
ZBUF[I]=POW(2,31)
W_VISIBLE[I]=-9999
NEXT

FOR I=0 TO LEN(W_BGN)-1
(略)
NEXT

FOR I=0 TO NUM_E
ZBUF[I+400]=E_RW[I]
W_VISIBLE[I+400]=-1-I
NEXT

敵のデータは以下のようになっています。

 ・NUM_E ・・・敵の数-1
 ・E_RW ・・・敵のZ座標値(スクリーン中央を原点とした座標系に変換済み)

ZBUFとW_VISIBLEのサイズは、本来はスクリーンの横方向のピクセル数に等しいのですが、これを敵の数の分だけ大きくしています。
そして、敵については、壁で隠されているか否かに関わらず、すべて「見えている」(ただし壁は隠していない)ことにして、ZBUFとW_VISIBLEに追加しています。

W_VISIBLEには「壁の番号」を記録しますので、敵0が-1、敵1が-2、敵2が-3、、、というように、敵は負の数で表して壁と区別が付くようにしています。

続いて描画処理の部分です。
GCLS

RSORT ZBUF,W_VISIBLE
W_LAST=-9999
FOR I=0 TO LEN(W_VISIBLE)-1
IF W_VISIBLE[I]==W_LAST THEN CONTINUE
W_LAST=W_VISIBLE[I]
IF W_LAST==-9999 THEN CONTINUE
IF W_LAST<0 THEN DRAW_ENEMY W_LAST:CONTINUE
P1=W_BGN[W_LAST]
P2=W_END[W_LAST]
L[0]=R_X[P1]:L[1]=R_Z[P1]
L[2]=R_X[P2]:L[3]=R_Z[P2]
IF CLIPLINE(L,X_MIN,Z_MIN,X_MAX,Z_MAX) THEN
(以下略)

RSORTによって、壁も敵も区別なく、Z値によってソートされます。
そして、スクリーンから遠い壁または敵から順に描画していきます。
見て分かるように、W_VISIBLE[I]が負の数だったら、敵の描画を行うユーザ手続きを呼び出しているだけです。

このDRAW_ENEMY関数は、中身は省略しますが、下図のように上から見ると「半径256ピクセルの円の内部」に納まるように敵を描画しています。

また、上で述べた条件を満たすように、敵は通路の中央、図の青い線の上を移動します。
pc29-7.jpg


最後に、敵との当たり判定です。
これは2点間の距離の公式

 距離=√(dx^2 + dy^2)

を使います。dxはX座標の差分、dyはY座標の差分です。
FOR I=0 TO NUM_E
D=(E_U[I]-U)*(E_U[I]-U)+(E_W[I]-W)*(E_W[I]-W)
IF D < E_R*E_R THEN
SPANIM 0,"C",1,&H00000000,-60,&HFFFF0000,-45,&H00000000,-45,1
BEEP 107,-600,96
ATTACKED=TRUE
BREAK
ENDIF
NEXT

IF ATTACKED THEN
T=T+.3
IF SPCHK(0) == 0 THEN ATTACKED=FALSE
ENDIF

変数は、

 プレイヤー: X座標 U, Z座標 W, 向き T
 敵(配列): X座標 E_U, Z座標 E_W, 半径 E_R

です。
距離の2乗を計算し(変数D)、半径の2乗より小さければ、敵とぶつかったと判定して変数ATTACKEDをTRUEにします。

スプライト0はスクリーン全体を覆う白地の図形で、通常は透明にしています。
ぶつかった場合には、このスプライトを赤い色にフェードイン/フェードアウトさせます。

フェードイン・フェードアウトのアニメーションを実行中は、プレイヤーの向きTを変化させて視点を強制的に回転させています。


以上で3D版 迷路探検ゲームの解説は終わりにします。
プログラムを作るより解説を書くほうが大変でした・・・。
posted by boochow at 00:13| Comment(0) | プチコン講座 | このブログの読者になる | 更新情報をチェックする

2015年03月14日

プチコン3号 28日目 擬似3D(5) 隠面消去

pc28-1.jpg

前回、ワイヤーフレームで3D空間を表現しましたが、今回からは11日目で作成した迷路探検ゲームの3D版を作ってみます。

プチコン3号 11日目 当たり判定を追加して迷路探検ゲーム完成!: 楽しくやろう。

前回のプログラムでは、線画で碁盤目状の地面を表示しました。
迷路の3Dでの表示は、この碁盤目に沿って垂直に壁を立てれば実現できます。

具体的には、まず迷路を二次元で作ってから、前回同様に視点からの距離に応じて縮小してやると、地面に迷路を描くことができます。(下図の青のライン)
次に、画面の下半分を鏡に映すように画面上半分に反転して表示します。(下図の緑のライン)
最後に、下半分と上半分の対応する点同士を垂直線で結んでやれば出来上がりです。(下図の赤のライン)
pc28-6.jpg


もちろんこれだけでは不十分で、壁の向こう側が見えないように、迷路の壁は塗りつぶさなければなりません。
これには、プチコン3号の3.1.0へのバージョンアップで追加された、塗りつぶした三角形の描画命令GTRIが使えます。

ただしGTRI命令で描けるのは、二次元の三角形です。
三次元ポリゴンの描画では、ポリゴン同士の重なり具合が座標のZ値を正しく反映していなければなりません。
具体的には、ポリゴンが重なる時は、Z値が小さいもの(視点により近いもの)が上になる必要があります。

例えば立方体を描く場合、下図のように色々な見え方があります。
どの見え方になるかは、立方体の各面と視点との位置関係に依存しています。
視点の移動や回転によってZ値は変化しますので、重なる順序も時々刻々変化します。
pc28-2.jpg

上の図の下半分は、左側がいろいろな壁が立っている様子を上空から眺めた図で、スクリーンは赤い位置にあります。
右側が、スクリーンからの見え方です。
手前の壁が後の壁を隠しています。

このように、重なりなどの影響を考慮して、見えている部分だけを画面に描画する処理を「隠面消去」といいます。
陰面消去には様々な方法がありますが、遠方のものから順に描画する「Zソート法」もその一つです。
この方法では、全てのポリゴンをZ軸の値の大きさで並べ替えてから、Z値が大きい順に描画します。
上の図で言えば、

  緑→オレンジ→青→ピンク

の順にポリゴンを描けば、右のような画像が得られます。
ただ、この方法は面同士が交差する場合は利用できません。

一方、三次元グラフィックスのハードウェアで広く用いられているのが「Zバッファ法」です。
これは、スクリーンの各ピクセルについて、描画時のZ値をバッファに保持しておくものです。
新しい3次元のピクセルを描画する際に、Zバッファの対応する値と、描こうとするピクセルのZ値を比較します。
そして、Zバッファの値のほうが大きければ、スクリーンを新しいピクセルで、ZバッファをそのピクセルのZ値で、それぞれ上書きします。

例えば、下図の画面中央の赤いラインに対応するZバッファは、図の下のような値を取ります。
pc28-3.jpg


前置きが長くなりましたが、上で述べたのは(擬似でない)三次元グラフィックスの一般論です。
迷路を三次元で描くことに限定すると、一般論よりも手抜きができます。
迷路の壁のポリゴンには、以下のような非常に強い制約条件があるからです。

 ・XZ平面に対して垂直である
 ・全ての壁で、幅や高さが同一である
 ・規則正しく配置されており、交差はしない

これらの制約条件を前提にすると、
「全ての壁の重なり具合は
  ・ある特定のY(ただし0<Y<壁の高さ)の場合について
  ・各壁のZ値の最大値(あるいは最小値、平均値など1つの値)を調べれば十分」
であることが分かります。

壁が垂直、かつ全ての壁の高さが同じなので、Yの値が変わっても重なり具合は変わりません。
壁が碁盤目状に配置されているので、2つの壁のどちらが手前にあるかも代表点の座標比較だけで決まります。

ちなみに碁盤目状でない場合は、垂直な壁であっても、Z値だけではどちらの壁が手前か判定できません。
下図の2つのパターンは、どちらも各壁のZ値の最大値、最小値は同じですが、壁の重なり方は異なっています。
pc28-7.jpg

今回は、以下のようなアルゴリズムで隠面消去を行っています。

 (1)全ての壁を、高さ1ピクセル横400ピクセルのZバッファに描画する
    (ただしZ値はまじめに計算せず、壁の2つの端点の平均値を採用)
 (1’)描画時に、各ピクセルが表示している壁の番号を、長さ400の配列に記録する
 (2)壁の番号の配列を、Z値が大きい順に並べ替える
 (3)壁の番号の配列の順に壁を描く

このアルゴリズムは、表示すべきポリゴンの抽出を(1)でZバッファ法で行い、抽出したポリゴンの描画は(2)でZソート法で行っていることになります。

今回のアルゴリズムは、隠れている壁を描画しなくて済むので、描画処理を大幅に短縮できます。
このような処理をせずに、迷路の壁を普通に全てワイヤーフレームで描くと、例えば以下のようになります。
これをすべて遠い順にGTRI命令で描画すると、さすがにアニメーションさせるのは困難です。
pc28-4.jpg


上記のアルゴリズムを使って、「見える壁」だけを抽出すると、以下のようになります。
この場合は、壁の枚数は10枚ですので、GTRI命令20回で描画することができます。
この程度の回数であれば、プチコン3号でも、何とかアニメーションができる程度の時間で描画できます。
pc28-5.jpg

遠くの壁から順に描画すると、以下のような画像ができます。
pc28-1.jpg

プログラムですが、全体はMiiverseにアップロードしてあります。
公開キーは4R2EP4K3です。
サイズが大きいので、今回は上記の隠面処理の部分だけを抜き出して掲載します。

FOR I=0 TO 399
ZBUF[I]=POW(2,31)
W_VISIBLE[I]=-9999
NEXT


FOR I=0 TO LEN(W_BGN)-1
P1=W_BGN[I]
P2=W_END[I]
L[0]=R_X[P1]:L[1]=R_Z[P1]
L[2]=R_X[P2]:L[3]=R_Z[P2]
IF !CLIPLINE(L,X_MIN,Z_MIN,X_MAX,Z_MAX) THEN CONTINUE
X1=FLOOR(L[0]*SCALE_Z(L[1])+200)
X2=FLOOR(L[2]*SCALE_Z(L[3])+200)
IF X1>X2 THEN SWAP X1,X2
X1=MAX(X1,0)
X2=MIN(X2,399)
ZVAL=(R_Z[P1]+R_Z[P2])/2
FOR J=X1 TO X2
IF ZBUF[J]>ZVAL THEN
ZBUF[J]=ZVAL
W_VISIBLE[J]=I
ENDIF
NEXT
NEXT

pc28-8.jpg

リストで使われている変数の意味は上の図を参照してください。
壁は始点と終点で表します。始点と終点は、図の左にあるように、格子の交差点につけた番号です。
図では、0番の壁の始点・終点はp0とp1です。1番の壁の始点・終点はp1とp(w+1)です。
壁の始点と終点は図右の表のように、始点が配列W_BGN、終点が配列W_ENDに格納されています。
点pの座標は、配列R_XとR_Zに格納されています。

最初のFOR...NEXTループは、2つの配列を初期化しています。
配列ZBUFはZバッファで、視点からの距離(Z値)を格納します。
Zバッファの各要素の初期値は無限大…としたいところですが、実際は十分大きな値(2の31乗=約20億)にしています。
W_VISIBLE[I]は、ZBUF[I]に表示される壁の番号が入ります。
初期値-9999は、「壁が表示されていない」ことを示すために使います。

次のFOR...NEXTループで、I番目の壁の処理を行います。

壁の端点のXZ座標は(R_X[P1], R_Z[P1])と(R_X[P2], R_Z[P2])です。
これを配列Lに設定し、Z>0の空間でクリッピングします。
これによって、視点よりも後方の壁は消去されます。
(クリッピングについては前回の記事を参照してください。)
表示される部分が無ければ、次の壁の処理に移ります。

表示される部分があった場合は、配列Lにクリッピング処理後の座標が入っています。
L[1]とL[3]がZ値で、これを元に縮小率を求め、画面上で壁が表示される範囲のX座標X0とX1を求めます。

そして、ZBUF[X0]..ZBUF[X1]にこの壁のZ値を代入します。
ただし、元からZBUFに入っていた値のほうがZ値よりも小さい場合には何もしません。

Z値は実際にはL[1]〜L[3]まで変化しますが、先に書いたように壁が規則正しく並んでいるので、壁の中点(下図左上の緑色の点)のZ座標で代用します。
また、W_VISIBLE[X0]..W_VISIBLE[X1]には、この壁の番号Iを代入します。
pc28-9.jpg

次に、壁の描画処理です。

まず、作成したZバッファの値の大きい順に、W_VISIBLEをソート(並べ替え)します。
プチコン3号は、このための命令RSORTがあります。
RSORTは第一引数の配列を降順でソートしますが、第二引数以降の配列が与えられた場合は、それらの配列も同じ順序でソートします。

ソートした結果のW_VISIBLEは、表示されるピクセル数の分だけ、壁の番号が連続して並んでいます。
描画処理ではW_VISIBLEの先頭から順に、指定された番号の壁を描画していきます。
直前と同じ番号の壁はもう描画する必要が無いので、飛ばします。

緑色の部分が壁を1つ描くためのコードです。
壁は台形になるので、GTRI命令を2回使います。
また、壁の輪郭の縦線の部分をGLINEで描いています。
GCLS
RSORT ZBUF,W_VISIBLE
W_LAST=-9999
FOR I=0 TO LEN(W_VISIBLE)-1
IF W_VISIBLE[I]==W_LAST THEN CONTINUE
W_LAST=W_VISIBLE[I]
IF W_LAST==-9999 THEN CONTINUE
P1=W_BGN[W_LAST]
P2=W_END[W_LAST]
L[0]=R_X[P1]:L[1]=R_Z[P1]
L[2]=R_X[P2]:L[3]=R_Z[P2]
IF CLIPLINE(L,X_MIN,Z_MIN,X_MAX,Z_MAX) THEN
S1=SCALE_Z(L[1])
L[0]=L[0]*S1+200
L[1]=V*S1+120
S2=SCALE_Z(L[3])
L[2]=L[2]*S2+200
L[3]=V*S2+120
C=(S1+S2)/2*128+8
C=RGB(C,C,C)
GTRI L[0],L[1],L[2],L[3],L[2],-L[3]+240,C
GTRI L[0],L[1],L[0],-L[1]+240,L[2],-L[3]+240,C
C=MAX(S1,S2)*128+32
C=RGB(C,C,C)
GLINE L[0],L[1],L[0],-L[1]+240,C
GLINE L[2],L[3],L[2],-L[3]+240,C

ENDIF
NEXT


以上で迷路の3D表示は終わりです。

次回は、3D迷路の中に敵を追加してみたいと思います。

posted by boochow at 19:48| Comment(0) | プチコン講座 | このブログの読者になる | 更新情報をチェックする
人気記事