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) | プチコン講座 | このブログの読者になる | 更新情報をチェックする
人気記事