Tiny_RayTracing.ps を読んでみた。

Obfuscated PostScript Contest 1993 の BEST OBFUSCATED ARTWORK で 1 位に選ばれた早川たかし氏の Tiny_RayTracing.ps を読んでみました。
プログラムは http://web.mit.edu/PostScript/obfuscated-1993/Tiny_RayTracing.ps を見てください。

一通り前から順に読む

/A/copy/p/floor/q/gt/S/add/n/exch/i/index/J/ifelse/r/roll/w/div

で、名前と使用する命令の名前をスタックに積み上げています。

/H{{loop}stopped Y}def

で、スタックトップにある実行可能配列をエラーになるまでループを繰り返すという手続きに H と名前をつけています。Y は後で pop と定義されます。

/t/and/C/neg/T/dup/h/exp/Y/pop/d/mul/s/cvi/e/sqrt/R/rlineto

も、名前と使用する命令の名前をスタックに積み上げます。

{load def}H

で、{load def} をエラーになるまで実行します。スタック上にある命令の名前から命令をロードし、1 文字の名前をつけます。

300 T translate

スクリーン座標の原点を (300,300) に移動させます。T は dup です。

(V2L&1i2A00053r45hNvQXz&vUX&UOvQXzFJ!FJ!J!O&Y43d9rE3IaN96r63rvx2dcaN
G&140N7!U&4C577d7!z&&93r6IQO2Z4o3AQYaNlxS2w!!f&nY9wn7wpSps1t1S!D&cjS5o32rS4oS3o
Z&blxC1SdC9n5dh!I&3STinTinTinY!B&V0R0VRVC0R!N&3A3Axe1nwc!l&993dC99Cc96raN!a&1CD
E&YYY!F&&vGYx4oGbxSd0nq&3IGbxSGY4Ixwca3AlvvUkbQkdbGYx4ofwnw!&vlx2w13wSb8Z4wS!J!
c&みj1idjoみid42rd!みX&4I3Ax52r8Ia3A3Ax65rTdCS4iw5o5IxnwTTd32rCST0q&eCST0q&D1!&EYE0!J
&EYEY0!J0q!x&jd5o32rd4odSS!K&WCVW!Q&31C85d4!k&X&E9!&1!J!v&6A!b&7o!o&1r!j&43r!W)

処理部をエンコードした文字列です。

{( )T 0 4 3 r put T(/)q{T(9)q{cvn}{s}J}{($)q{[}{]}J}J cvx}forall

1 文字の命令を元の命令に直すと

{
    ( ) dup 0 4 3 roll put
    dup (/) gt{
        dup (9) gt{
            cvn
        }{
            cvi
        }ifelse
    }{
        ($) gt{
            [
        }{
            ]
        }ifelse
    }ifelse
    cvx
}forall

です。文字列を 1 文字ずつ読み、命令列を作ってスタックに置いていきます。数字は数に、アルファベットは名前に、'&' は命令列の始まりに、'!' と改行文字は命令列の終わりになります。
デコードすると以下の様になります。

V 2
L { 1 i 2 A 0 0 0 5 3 r 4 5 h N v Q X z { v U X { U O v Q X z F J } F J } J }
O { Y 4 3 d 9 r E 3 I a N 9 6 r 6 3 r v x 2 d c a N }
G { 1 4 0 N 7 }
U { 4 C 5 7 7 d 7 }
z { { 9 3 r 6 I Q O 2 Z 4 o 3 A Q Y a N l x S 2 w } }
f { n Y 9 w n 7 w p S p s 1 t 1 S }
D { c j S 5 o 3 2 r S 4 o S 3 o}
Z { b l x C 1 S d C 9 n 5 d h }
I { 3 S T i n T i n T i n Y }
B { V 0 R 0 V R V C 0 R }
N { 3 A 3 A x e 1 n w c }
l { 9 9 3 d C 9 9 C c 9 6 r a N }
a { 1 C D}
E { Y Y Y }
F { { v G Y x 4 o G b x S d 0 n q { 3 I G b x S G Y 4 I x w c a 3 A l v v U k b
Q k d b G Y x 4 o f w n w } { v l x 2 w 1 3 w S b 8 Z 4 w S } J } }
c { j 1 i d j 2 i d 4 2 r d }
X { 4 I 3 A x 5 2 r 8 I a 3 A 3 A x 6 5 r T d C S 4 i w 5 o 5 I x n w T T d 3 2
 r C S T 0 q { e C S T 0 q { D 1 } { E Y E 0 } J} { E Y E Y 0 } J 0 q }
x { j d 5 o 3 2 r d 4 o d S S }
K { W C V W }
Q { 3 1 C 8 5 d 4 }
k { X { E 9 } { 1 } J }
v { 6 A }
b { 7 o }
o { 1 r }
j { 4 3 r }
W

次の 270 で 270 がスタックに置かれます。

{def}H

でスタックに置かれた名前に数値や命令列を定義していきます。
最後に

K{K{L setgray moveto B fill}for Y}for showpage

でレイトレーシングの計算と描画を行います。

エンコードされている命令の意味

単純な命令を元の名前に直し、コメントを加えてみました。

V 2   % V 刻みで描画
L {
    % y x => y x y B
    % スクリーン上の点 (x, y) の色 B を計算する
    1 index
    % 視点座標 (0,0,0) と
    % 視線方向((x,y,1024) 方向の単位ベクトル) の計算
    2 copy
    0 0 0
    5 3 roll 4 5 exp N
    % 視線方向上に球 Q があるか判定
    6 copy Q X
    {
        % 球 Q がある場合
        z
    } {
        % 球 Q がない場合
        % 視線方向上に球 U があるか判定
        6 copy U X
        {
            % 球 U がある場合
            % 球面での反射位置と反射方向計算
            U O
            % 反射方向上にした球 Q があるか判定
            6 copy Q X
            {
                % 球 Q がある場合球 Q 上の明るさ計算
                z
            } {
                % 球 Q がない場合床または空の明るさを計算
                F
            } ifelse 
        } {
            % 球 U がない場合床または空の明るさ計算
            F
        } ifelse 
    } ifelse 
}
O {
    % x1 y1 z1 x2 y2 z2 x3 y3 z3 x4 y4 z4 any => x3 y3 z3 nnx nny nnz
    % 反射光の計算
    % 点 (x1,y1,z1) から (x2,y2,z2) 方向に出た光が
    % 中心 (x4,y4,z4) の球上の点 (x3,y3,z3) で反射すると、
    % 点 (x3,y3,z3) から (nnx,nny,nnz) 方向に出た光になる
    %
    pop
    4 3 mul 9 roll E
    3 I a N
    9 6 roll 6 3 roll
    6 copy x
    2 mul c a N 
}
G {
    % => nx ny nz h
    % 地面を指定するパラメータ
    % 地面に対する法線ベクトル (nx,ny,nz) 
    % 点 (x,y,z) は nx*x+ny*y+ny*z+h=0 を満たすとき地面
    %
    % (nx,ny,nz)=(1/sqrt(17), 4/sqrt(17), 0)
    1 4 0 N
    % h=7
    7 
}
U {
    % => x y z r
    % 鏡面をもっている方の球の座標 (x,y,z) と半径 r
    4 neg 5 7 7 mul 7
}
z {
    % x1 y1 z1 z2 y2 z2 x3 y3 z3=> R
    %   球 Q 上の点 (x3,y3,z3) を (x2,y2,z2) 方向から見た時の明るさを求める
    %
    % 鏡面反射分の計算
    9 3 roll
    6 I Q O
    2 Z
    % ランバートの余弦則による明るさ計算
    4 1 roll 3 copy
    Q pop a N
    l
    x
    % 平均
    add 2 div 
}
f {
    % x y z => (int(floor(z/9+floor(x/7)))&1)+1
    % 床上の点 (x,y,z) の明るさが白の何分の一か
    exch pop
    9 div exch 7 div floor
    add floor cvi
    1 and 1 add 
}
D {
    % x1 y1 z1 x2 y2 z2 r => x1+x2*r y1+y2*r z1+z2*r
    % 三次元ベクトル演算 V1+V2*r
    %
    c
    4 3 roll add
    5 1 roll 3 2 roll add
    4 1 roll add
    3 1 roll
}
Z {
    % x1 y1 z1 x2 y2 z2 a => 9**(-5*a*(1-(x2*nx+y2*ny+z3*nz)))
    %   光源 (lx,ly,lz) から出て (x1,y1,z1) に来た光が (x2,y2,z2) 方向に
    %   反射される時の鏡面反射の計算
    %   a は光源の広がり具合のパラメータ? 大きいほど点に近い
    %
    %   (nx,ny,nz)=(lx-x1,ly-y1,lz-z1) 方向の単位ベクトル
    %
    7 1 roll l
    x
    neg 1 add mul neg
    9 exch 5 mul exp 
}
I {
    % any_n+3 any_n+2 any_n+1 ... any_2 any_1 n =>
    % any_n+3 any_n+2 any_n+1 ... any_2 any_1 any_n+3 any_n+2 any_n+1
    % スタックの n+1 から n+3 番目の要素をスタックのトップにコピー
    %
    3 add
    dup index exch
    dup index exch
    dup index exch
    pop 
}
B {
    % コの字に線を引く
    % 後で fill を実行すると、1辺 V の正方形を塗りつぶす
    V 0 rlineto
    0 V rlineto
    V neg 0 rlineto 
}
N {
    % x y z =>
    % x/sqrt(x*x+y*y+z*z) y/sqrt(x*x+y*y+z*z) z/sqrt(x*x+y*y+z*z)
    % 三次元単位ベクトルを計算
    %
    3 copy 3 copy x
    sqrt 1 exch div c 
}
l {
    % x1 y1 z1 x2 y2 z2 => x2 y2 z2 nx ny nz
    % 点 (x1,y1,z1) に対する光源 (lx, ly, lz) の方向の
    % 単位ベクトルを計算する
    %
    % 光源座標 (lx, ly, lz)=(-81 243 -81)
    9 9 3 mul neg 9 9 neg c
    % 単位ベクトル
    9 6 roll
    a N 
}
a {
    % x1 y1 z1 x2 y2 z2 => x1-x2 y1-y2 z1-z2
    % 3次元ベクトルの引き算
    %
    1 neg D
}
E {
    % any1 any2 any3 =>
    % スタックから 3 個取り出し捨てる
    %
    pop pop pop
}
F {
    % x1 y1 z1 x2 y2 z2 => Tf
    % 座標 (x1,y1,z1) から (x2,y2,z2) 方向の床または空を
    % 見たときの明るさ
    %
    % 視線方向が床の法線と同じ側を向いているか
    6 copy
    G pop x
    % 視点が床の法線側にあるか
    4 1 roll 
    G 7 1 roll
    x add mul
    0 exch gt {
        % 床を見ている場合
        % 見ている床の座標を計算
        3 I G
        7 1 roll
        x add
        G pop 4 I
        x div c
        a
        % 床が影になることによる明るさの変化
        3 copy l
        % 球 U の影で明るさが何分の一になるか
        6 copy 6 copy U k
        % 球 Q の影で明るさが何分の一になるか
        7 1 roll Q k
        mul
        % 床自体の明るさ
        % ランバートの余弦則
        7 1 roll G pop x
        % 床の模様の寄与
        4 1 roll f
        % 明るさ
        div exch div 
    } {
        % 空を見ている場合
        %
        % 視線方向と光源の方向の角度θのとき
        % cos(θ)/2+1/3
        6 copy l
        x
        2 div 1 3 div add
        % 視線方向に光源がある場合の明るさ
        7 1 roll
        8 Z
        4 div
        % 和
        add 
    } ifelse
}
c {
    % x y z r => x*r y*r z*r
    % 3次元ベクトルのスカラー倍
    %
    4 3 roll 1 index mul
    4 3 roll 2 index mul
    4 2 roll mul 
}
X {
    % x1 y1 z1 x2 y2 z2 x3 y3 z3 a => xs ys zs true
    % x1 y1 z1 x2 y2 z2 x3 y3 z3 a => false
    %  点 (x1,y1,z1) から (x2,y2,z2) の方向に出た直線が
    %  中心 (x3,y3,z3) 半径 a の球に交わる座標を計算する
    %  交わらないときは false
    %
    % X1=(x1,y1,z1), X2=(x2,y2,z2), X3=(x3,y3,z3) として
    % t の2次方程式 |X1+t*X2-X3|^2=a^2 を解く
    4 I 3 copy x
    5 2 roll
    8 I a
    3 copy 3 copy x
    6 5 roll
    dup mul neg add
    4 index div
    5 1 roll
    5 I x
    exch div
    dup dup mul
    3 2 roll
    neg add
    % 判別式の符号で分岐
    dup 0 gt {
        % 直線と球が交点を持つ場合
        sqrt neg add
        dup 0 gt {
            % 2 次方程式の解の小さい方が正の場合
            % (x2,y2,z2) 方向上に球がある
            %
            % X1+t*X2
            D 1 
        } {
            % 2 次方程式の解の小さい方が負の場合
            % (x1,y1,z1) が球の内部であるか
            % (x2,y2,z2) 方向の逆側に球がある
            E pop E 0 
        } ifelse
    } {
        % 直線と球が交点を持たない場合
        E pop E pop 0 
    } ifelse
    0 gt 
}
x {
    % x1 y1 z1 x2 y2 z2 => x1*x2+y2*y1+z2*z1
    % 3次元ベクトルの内積
    %
    4 3 roll mul
    5 1 roll 3 2 roll mul
    4 1 roll mul
    add add 
}
K {
    % => -W V W
    % 描画のループの上限、加減とステップ
    W neg V W 
}
Q {
    % => x y z r
    % 黒い球の座標 (x,y,z) と半径 r
    3 1 neg 8 5 mul 4
}
k {
    % x1 y1 z1 x2 y2 z2 x3 y3 z3 a => 1 or 9
    %  座標 (x1,y1,z1) から (x2,y2,z2) の方向に出た光が
    %  中心 (x3,y3,z3) 半径 a の球に遮られるなら 9
    %  遮られないときは 1
    X
    {
        E 9
    } {
        1
    } ifelse 
}
v {
    % a1 a2 a3 a4 a5 a6 =>
    % a1 a2 a3 a4 a5 a6 a1 a2 a3 a4 a5 a6
    % スタックの上から 6 個をコピーしてスタックに置く
    %
    6 copy
}
b {
    % a_7 ... a_1 n => a_1 a_7 ... a_2 
    % スタックの上から 7 個を回転させ、a_2 をスタックトップにする
    %
    7 o
}
o {
    % a_n ... a_1 n => a_1 a_n ... a_2 
    % スタックの上から n 個を回転させ、a_2 をスタックトップにする
    %
    1 roll
}
j {
    % a_4 ... a_1 n => a_3 ... a_1 a_4
    % スタックの上から 4 個を回転させ、a_4 をスタックトップにする
    %
    4 3 roll
}
% 描画範囲
% 縦横 -W から W までの領域を描画する
W 270