「彼はもう一度やった！」-それは私がピクサーのチラシ[1]の背面を見たときに最初に起こったもので、完全にコードで満たされています。 右下隅にある構造と表現のクラスターは、アンドリューケンスラー以外は署名しませんでした。 彼を知らない人のために、アンドリューは2009年に1337バイトの名刺サイズのレイトレーサーを発明したプログラマーです。
今回、Andrewはもっとボリュームのあるものを思いつきましたが、視覚的な結果はもっと興味深いものでした。 Wolf3DとDOOMに関するGame Engine Black Booksの執筆を終えてから、その暗号コードの内部を学ぶ時間がありました。 そしてほとんどすぐに、私は彼で発見された技術に文字通り魅了されました。 「標準」レイトレーサーに基づいたAndrewの以前の作品とは非常に異なっていました。 レイマーチング、建設的な体積ジオメトリの機能、モンテカルロレンダリング/パストレーシング、および彼がコードをこのような小さな紙に詰め込むために使用した他の多くのトリックについて学ぶことに興味がありました。
ソースコード
チラシの前面は、ピクサー採用部門の広告です。 裏面には、2,037バイトのC ++コードが印刷されており、難読化されて可能な限り小さい表面を占めています。
#include <stdlib.h> // card > pixar.ppm #include <stdio.h> #include <math.h> #define R return #define O operator typedef float F;typedef int I;struct V{F x,y,z;V(F v=0){x=y=z=v;}V(F a,F b,F c=0){x=a;y=b;z=c;}V O+(V r){RV(x+rx,y+ry,z+rz);}VO*(V r){RV(x*rx,y*r. y,z*rz);}FO%(V r){R x*r.x+y*r.y+z*rz;}VO!(){R*this*(1/sqrtf(*this%*this) );}};FL(F l,F r){R l<r?l:r;}FU(){R(F)rand()/RAND_MAX;}FB(V p,V l,V h){l=p +l*-1;h=h+p*-1;RL(L(L(lx,hx),L(ly,hy)),L(lz,hz));}FS(V p,I&m){F d=1\ e9;V f=p;fz=0;char l[]="5O5_5W9W5_9_COC_AOEOA_E_IOQ_I_QOUOY_Y_]OWW[WaOa_aW\ eWa_e_cWiO";for(I i=0;i<60;i+=4){V b=V(l[i]-79,l[i+1]-79)*.5,e=V(l[i+2]-79,l [i+3]-79)*.5+b*-1,o=f+(b+e*L(-L((b+f*-1)%e/(e%e),0),1))*-1;d=L(d,o%o);}d=sq\ rtf(d);V a[]={V(-11,6),V(11,6)};for(I i=2;i--;){V o=f+a[i]*-1;d=L(d,ox>0?f\ absf(sqrtf(o%o)-2):(o.y+=oy>0?-2:2,sqrtf(o%o)));}d=powf(powf(d,8)+powf(pz, 8),.125)-.5;m=1;F r=L(-L(B(p,V(-30,-.5,-30),V(30,18,30)),B(p,V(-25,17,-25),V (25,20,25))),B(V(fmodf(fabsf(px),8),py,pz),V(1.5,18.5,-25),V(6.5,20,25))) ;if(r<d)d=r,m=2;F s=19.9-py;if(s<d)d=s,m=3;R d;}IM(V o,V d,V&h,V&n){I m,s= 0;F t=0,c;for(;t<100;t+=c)if((c=S(h=o+d*t,m))<.01||++s>99)R n=!V(S(h+V(.01,0 ),s)-c,S(h+V(0,.01),s)-c,S(h+V(0,0,.01),s)-c),m;R 0;}VT(V o,V d){V h,n,r,t= 1,l(!V(.6,.6,1));for(I b=3;b--;){I m=M(o,d,h,n);if(!m)break;if(m==1){d=d+n*( n%d*-2);o=h+d*.1;t=t*.2;}if(m==2){F i=n%l,p=6.283185*U(),c=U(),s=sqrtf(1-c), g=nz<0?-1:1,u=-1/(g+nz),v=nx*ny*u;d=V(v,g+ny*ny*u,-ny)*(cosf(p)*s)+V( 1+g*nx*nx*u,g*v,-g*nx)*(sinf(p)*s)+n*sqrtf(c);o=h+d*.1;t=t*.2;if(i>0&&M(h +n*.1,l,h,n)==3)r=r+t*V(500,400,100)*i;}if(m==3){r=r+t*V(50,80,100);break;}} R r;}I main(){I w=960,h=540,s=16;V e(-22,5,25),g=!(V(-3,4,0)+e*-1),l=!V(gz, 0,-gx)*(1./w),u(gy*lz-gz*ly,gz*lx-gx*lz,gx*ly-gy*lx);printf("P\ 6 %d %d 255 ",w,h);for(I y=h;y--;)for(I x=w;x--;){V c;for(I p=s;p--;)c=c+T(e ,!(g+l*(xw/2+U())+u*(yh/2+U())));c=c*(1./s)+14./241;V o=c+1;c=V(cx/ox,c. y/oy,cz/oz)*255;printf("%c%c%c",(I)cx,(I)cy,(I)cz);}}// Andrew Kensler
彼は働いていますか？
コードには、起動の指示があります。 アイデアは、標準出力をファイルにリダイレクトすることです。 拡張により、出力形式はNetPBM [2]と呼ばれるテキスト画像形式であると想定できます。
$ clang -o card2 -O3 raytracer.cpp $ time ./card> pixar.ppm 実2m58.524s ユーザー2m57.567s sys 0m0.415s
2分58秒[3]後に、次の画像が生成されます。 それに必要なコードがどれほど少ないかは驚くべきことです。
上記の画像から多くを抽出できます。 グリットは「パストレーサー」の明らかな兆候です。 このタイプのレンダラーは、光線が光源までさかのぼらないという点でレイトレーシングとは異なります。 この方法では、ピクセルごとに数千の光線が光源から放出され、プログラムは光源を見つけることを期待してそれらを監視します。 これは、レイトレーシングよりはるかに優れた、アンビエントオクルージョン、ソフトシャドウ、コースティクス、ラジオシティのレンダリングを処理できる興味深い手法です。
コードを部分に分割します
入力をCLionに渡すと、コードがフォーマットされ（ ここの出力を参照 ）、小さなパーツ/タスクに分割されます。
#include <stdlib.h> // card> pixar.ppm #include <stdio.h> #include <math.h>
#define Rリターン #define O演算子 typedef float F; typedef int I;
struct V {F x、y、z; V（F v = 0）{x = y = z = v;} V（F a、F b、F
c = 0）{x = a; y = b; z = c;} V O +（V r）{RV（x + rx、y + ry、z + rz）;} VO *（V r）{RV（ x * rx、y * r。
y、z * rz）;} FO％（V r）{R x * r.x + y * r.y + z * rz;} VO！（）{R * this *（1 / sqrtf（* this％ *これ）
）;}}; FL（F l、F r）{R l <r？L：r;} FU（）{R（F）rand（）/ RAND_MAX;} FB（V p、V l、V h）{l = p
+ l * -1; h = h + p * -1; RL（L（L（L（lx、hx）、L（ly、hy））、L（lz、hz））;} FS（V p、I＆m）{F d = 1 \
e9; V f = p; fz = 0; char l [] = "5O5_5W9W5_9_COC_AOEOA_E_IOQ_I_QOUOY_Y_] OWW [WaOa_aW \
eWa_e_cWiO "; for（I i = 0; i <60; i + = 4）{V b = V（l [i] -79、l [i + 1] -79）*。5、e = V（l [ i + 2] -79、l
[i + 3] -79）*。5 + b * -1、o = f +（b + e * L（-L（（b + f * -1）％e /（e％e）、0）、 1））*-1; d = L（d、o％o）;} d = sq \
rtf（d）; V a [] = {V（-11.6）、V（11.6）}; for（I i = 2; i-;）{V o = f + a [i] * -1; d = L（d、ox> 0？F \
absf（sqrtf（o％o）-2）:( o.y + = oy> 0？-2：2、sqrtf（o％o）））;} d = powf（powf（d、8）+ powf（pz 、
8）,. 125）-。5; m = 1; F r = L（-L（B（p、V（-30、-。5、-30）、V（30,18,30））、B （p、V（-25.17、-25）、V
（25、20、25）））、B（V（fmodf（fabsf（px）、8）、py、pz）、V（1.5、18.5、-25）、V（6.5、20、25）））
; if（r <d）d = r、m = 2; F s = 19.9-py; if（s <d）d = s、m = 3; R d;} IM（V o、V d、V＆h、V＆n）{I m、s =
0; F t = 0、c; for（; t <100; t + = c）if（（c = S（h = o + d * t、m））<。01 || ++ s> 99）R n =！V（S（h + V（.01,0
）、s）-c、S（h + V（0、.01）、s）-c、S（h + V（0,0、.01）、s）-c）、m; R 0;} VT（V o、V d）{V h、n、r、t =
1、l（！V（.6、.6,1））; for（I b = 3; b-;）{I m = M（o、d、h、n）; if（！M）break ; if（m == 1）{d = d + n *（
n％d * -2）; o = h + d * .1; t = t * .2;} if（m == 2）{F i = n％l、p = 6.283185 * U（）、c = U（）、s = sqrtf（1-c）、
g = nz <0？-1：1、u = -1 /（g + nz）、v = nx * ny * u; d = V（v、g + ny * ny * u、-ny）*（cosf （p）* s）+ V（
1 + g * nx * nx * u、g * v、-g * nx）*（sinf（p）* s）+ n * sqrtf（c）; o = h + d * .1; t = t *。 2; if（i> 0 && M（h
+ n * .1、l、h、n）== 3）r = r + t * V（500,400,100）* i;} if（m == 3）{r = r + t * V（50,80,100） ; break;}}
R r;} I main（）{I w = 960、h = 540、s = 16; V e（-22,5,25）、g =！（V（-3,4,0）+ e * -1）、l =！V（gz、
0、-gx）*（1./w)、u（gy * lz-gz * ly、gz * lx-gx * lz、gx * ly-gy * lx）; printf（ "P \
6％d％d 255 "、w、h）; for（I y = h; y-;）for（I x = w; x-;）{V c; for（I p = s; p- -;）c = c + T（e
、！（g + l *（xw / 2 + U（））+ u *（yh / 2 + U（））））; c = c *（1./s）+ 14./241; V o = c + 1; c = V（cx / ox、c。
y / oy、cz / oz）* 255; printf（ "％c％c％c"、（I）cx、（I）cy、（I）cz）;}} //アンドリューケンスラー
各セクションについては、記事の残りの部分で詳しく説明します。
■ -通常のトリック、 ■ -クラスベクトル、 ■ -補助コード、 ■ -データベース、 ■ -レイマーチング、 ■ -サンプリング、 ■ -メインコード。
#defineとtypedefの一般的なトリック
一般的なトリックは、＃defineとtypedefを使用してコードの量を大幅に削減することです。 ここでは、F = float、I = int、R = return、およびO =演算子を示します。 リバースエンジニアリングは簡単です。
グレードV
次はクラスVで、これをVecに名前変更しました（以下で説明するように、RGBチャネルをfloat形式で保存するためにも使用されます）。
struct Vec { float x, y, z; Vec(float v = 0) { x = y = z = v; } Vec(float a, float b, float c = 0) { x = a; y = b; z = c;} Vec operator+(Vec r) { return Vec(x + rx, y + ry, z + rz); } Vec operator*(Vec r) { return Vec(x * rx, y * ry, z * rz); } // dot product float operator%(Vec r) { return x * rx + y * ry + z * rz; } // inverse square root Vec operator!() {return *this * (1 / sqrtf(*this % *this) );} };
減算演算子（-）がないため、「X = A-B」と記述する代わりに、「X = A + B * -1」が使用されます。 逆平方根は、後でベクトルを正規化するのに役立ちます。
主な機能
main（）は、libcライブラリの_start関数によって呼び出されるため、難読化できない唯一の文字です。 通常、この方法で作業する方が簡単になるため、最初から始める価値があります。 最初の文字の意味を理解するにはしばらく時間がかかりましたが、それでもなんとか読みやすいものを作成することができました。
int main() { int w = 960, h = 540, samplesCount = 16; Vec position(-22, 5, 25); Vec goal = !(Vec(-3, 4, 0) + position * -1); Vec left = !Vec(goal.z, 0, -goal.x) * (1. / w); // Cross-product to get the up vector Vec up(goal.y * left.z - goal.z * left.y, goal.z * left.x - goal.x * left.z, goal.x * left.y - goal.y * left.x); printf("P6 %d %d 255 ", w, h); for (int y = h; y--;) for (int x = w; x--;) { Vec color; for (int p = samplesCount; p--;) color = color + Trace(position, !(goal + left * (x - w / 2 + randomVal())+ up * (y - h / 2 + randomVal()))); // Reinhard tone mapping color = color * (1. / samplesCount) + 14. / 241; Vec o = color + 1; color = Vec(color.x / ox, color.y / oy, color.z / oz) * 255; printf("%c%c%c", (int) color.x, (int) color.y, (int) color.z); } }
floatリテラルには文字「f」が含まれておらず、スペースを節約するために小数部分は破棄されることに注意してください。 以下では、同じトリックが使用され、整数部分が削除されます（float x = .5）。 また、ブレーク条件内に反復式が挿入された「for」コンストラクトも珍しいです。
これは、レイ/パストレーサーの非常に標準的なメイン関数です。 ここでカメラベクトルを指定し、各ピクセルに対して光線を放出します。 レイトレーサーとパストレーサーの違いは、TPではピクセルごとにいくつかのレイが放出され、それらがわずかにランダムにシフトされることです。 次に、ピクセル内の各光線に対して取得された色は、3つのフロートチャネルR、B、Gに蓄積されます。 最後に、ラインハルト法の結果の色調補正が実行されます。
最も重要な部分はsampleCountで、理論的には1に設定してレンダリングと反復を高速化できます。 1〜2048のサンプル値を使用したサンプルレンダリングを次に示します。
ネタバレ見出し 
1
2
4
8
16
32
64
128
256
512
1024
2048
1
2
4
8
16
32
64
128
256
512
1024
2048
ヘルパーコード
もう1つの簡単なコードは、ヘルパー関数です。 この場合、単純な関数min（）、区間[0,1]のランダム値ジェネレーター、および世界を切り取るために使用される構成的固体ジオメトリ（CSG）システムの一部である、より興味深いboxTest（）があります。 CSGについては、次のセクションで説明します。
float min(float l, float r) { return l < r ? l : r; } float randomVal() { return (float) rand() / RAND_MAX; } // Rectangle CSG equation. Returns minimum signed distance from // space carved by lowerLeft vertex and opposite rectangle // vertex upperRight. float BoxTest(Vec position, Vec lowerLeft, Vec upperRight) { lowerLeft = position + lowerLeft * -1; upperRight = upperRight + position * -1; return -min( min( min(lowerLeft.x, upperRight.x), min(lowerLeft.y, upperRight.y) ), min(lowerLeft.z, upperRight.z)); }
建設的な体積幾何学の機能
コードには頂点がありません。 すべてはCSG機能を使用して行われます。 それらに慣れていない場合は、これらが座標がオブジェクトの内側か外側かを記述する関数であると単純に言います。 関数が正の距離を返す場合、ポイントはオブジェクト内にあります。 負の距離は、ポイントがオブジェクトの外側にあることを示します。 さまざまなオブジェクトを記述するための多くの関数がありますが、簡単にするために、たとえば球と2つのポイントAとBを取り上げます。
// Signed distance point(p) to sphere(c,r) float testSphere(Vec p, Vec c, float r) { Vec delta = c - p; float distance = sqrtf(delta%delta); return radius - distance; } Vec A {4, 6}; Vec B {3, 2}; Vec C {4, 2}; float r = 2.; testSphere(A, C, r); // == -1 (outside) testSphere(B, C, r); // == 1 (inside)
testSphere（）関数は、ポイントA（つまり、外側）に対して-1を返し、B（つまり、内側）に対して1を返します。 距離の標識は単なるトリックであり、1つの値の場合、1つではなく2つの情報を取得できます。 同様のタイプの関数を記述して、平行四辺形を記述することができます（これは、まさにBoxTest関数で実行されるものです）。
// Signed distance point(p) to Box(c1,c2) float testRectangle(Vec p, Vec c1, Vec c2) { c1 = p + c1 * -1; c2 = c2 + position * -1; return min( min( min(c1.x, c2.x), min(c1.y, c2.y)), min(c1.z, c2.z)); } Vec A {3, 3}; Vec B {4, 6}; Vec C1 {2, 2}; Vec C2 {5, 4}; testRectangle(A, C1, C2); // 1.41 (inside) testRectangle(B, C1, C2); // -2.23 (outside)
次に、戻り値の符号を反転させた場合に何が起こるかを見てみましょう。
// Signed distance point(p) to carved box(c1,c2) float testCarveBox(Vec p, Vec c1, Vec c2) { c1 = p + c1 * -1; c2 = c2 + position * -1; return -min( min( min(c1.x, c2.x), min(c1.y, c2.y)), min(c1.z, c2.z)); } Vec A {3, 3}; Vec B {4, 6}; Vec C1 {2, 2}; Vec C2 {5, 4}; testCarveBox(A, C1, C2); // == -1.41 (outside) testCarveBox(B, C1, C2); // == 2.23 (inside)
ここでは、ソリッドオブジェクトを説明しませんが、全世界をソリッドとして宣言し、その中の空のスペースを切り取ります。 関数は、構築ブリックとして使用できます。これを組み合わせて、より複雑なフォームを記述できます。 論理加算演算子（min関数）を使用して、長方形のペアを上下にカットすると、結果は次のようになります。
// Signed distance point to room float testRoom(Vec p) { Vec C1 {2, 4}; Vec C2 {5, 2}; // Lower room Vec C3 {3, 5}; Vec C4 {4, 4}; // Upper room // min() is the union of the two carved volumes. return min(testCarvedBox(p, C1, C2), testCarvedBox(p, C3, C4)); } Vec A {3, 3}; Vec B {4, 6}; testRoom(A, C1, C2); // == -1.41 (outside) testRoom(B, C1, C2); // == 1.00 (inside)
考えてみると、下の部屋は2つの平行四辺形の助けを借りてこのように表現されているので、勉強している部屋のように見えます。
これで、CSGの強力な知識を習得したので、コードに戻って対処が最も難しいデータベース機能を検討できます。
#define HIT_NONE 0 #define HIT_LETTER 1 #define HIT_WALL 2 #define HIT_SUN 3 // Sample the world using Signed Distance Fields. float QueryDatabase(Vec position, int &hitType) { float distance = 1e9; Vec f = position; // Flattened position (z=0) fz = 0; char letters[15*4+1] = // 15 two points lines "5O5_" "5W9W" "5_9_" // P (without curve) "AOEO" "COC_" "A_E_" // I "IOQ_" "I_QO" // X "UOY_" "Y_]O" "WW[W" // A "aOa_" "aWeW" "a_e_" "cWiO"; // R (without curve) for (int i = 0; i < sizeof(letters); i += 4) { Vec begin = Vec(letters[i] - 79, letters[i + 1] - 79) * .5; Vec e = Vec(letters[i + 2] - 79, letters[i + 3] - 79) * .5 + begin * -1; Vec o = f + (begin + e * min(-min((begin + f * -1) % e / (e % e), 0), 1) ) * -1; distance = min(distance, o % o); // compare squared distance. } distance = sqrtf(distance); // Get real distance, not square distance. // Two curves (for P and R in PixaR) with hard-coded locations. Vec curves[] = {Vec(-11, 6), Vec(11, 6)}; for (int i = 2; i--;) { Vec o = f + curves[i] * -1; distance = min(distance, ox > 0 ? fabsf(sqrtf(o % o) - 2) : (oy += oy > 0 ? -2 : 2, sqrtf(o % o)) ); } distance = powf(powf(distance, 8) + powf(position.z, 8), .125) - .5; hitType = HIT_LETTER; float roomDist ; roomDist = min(// min(A,B) = Union with Constructive solid geometry //-min carves an empty space -min(// Lower room BoxTest(position, Vec(-30, -.5, -30), Vec(30, 18, 30)), // Upper room BoxTest(position, Vec(-25, 17, -25), Vec(25, 20, 25)) ), BoxTest( // Ceiling "planks" spaced 8 units apart. Vec(fmodf(fabsf(position.x), 8), position.y, position.z), Vec(1.5, 18.5, -25), Vec(6.5, 20, 25) ) ); if (roomDist < distance) distance = roomDist, hitType = HIT_WALL; float sun = 19.9 - position.y ; // Everything above 19.9 is light source. if (sun < distance)distance = sun, hitType = HIT_SUN; return distance; }
ここで、平行四辺形を「切り取る」機能を見ることができます。この機能では、部屋全体を構成するのに2つの長方形だけが使用されます（残りの部分は脳が行い、壁を表します）。 水平ラダーは、剰余除算を使用したやや複雑なCSG関数です。 最後に、PIXARという単語の文字は、「オリジン/デルタ」のペアと文字PとRの曲線の2つの特別な場合を含む15行で構成されています。
レイマーチング
世界を記述するCSG関数のデータベースがあれば、main（）関数で放出されるすべての光線をスキップするだけで十分です。 レイマーチングは距離関数を使用します。 これは、サンプリング位置が最も近い障害物まで前方に移動することを意味します。
// Perform signed sphere marching // Returns hitType 0, 1, 2, or 3 and update hit position/normal int RayMarching(Vec origin, Vec direction, Vec &hitPos, Vec &hitNorm) { int hitType = HIT_NONE; int noHitCount = 0; float d; // distance from closest object in world. // Signed distance marching for (float total_d=0; total_d < 100; total_d += d) if ((d = QueryDatabase(hitPos = origin + direction * total_d, hitType)) < .01 || ++noHitCount > 99) return hitNorm = !Vec(QueryDatabase(hitPos + Vec(.01, 0), noHitCount) - d, QueryDatabase(hitPos + Vec(0, .01), noHitCount) - d, QueryDatabase(hitPos + Vec(0, 0, .01), noHitCount) - d) , hitType; // Weird return statement where a variable is also updated. return 0; }
距離に基づいたレイマーチングのアイデアは、最も近いオブジェクトまで距離を移動することです。 最終的に、ビームは表面に近づき、入射点と見なすことができます。
レイマーチングは、サーフェスとの真の交点ではなく、近似値を返すことに注意してください。 それが、d <0.01fのときにコードでマーチングが停止する理由です。
すべてをまとめる：サンプリング
パストレーサの調査はほぼ完了しています。 main（）関数とレイマーチャーを接続するブリッジがありません。 「トレース」と名前を変更したこの最後の部分は、光線が反射または停止する「脳」です。
Vec Trace(Vec origin, Vec direction) { Vec sampledPosition, normal, color, attenuation = 1; Vec lightDirection(!Vec(.6, .6, 1)); // Directional light for (int bounceCount = 3; bounceCount--;) { int hitType = RayMarching(origin, direction, sampledPosition, normal); if (hitType == HIT_NONE) break; // No hit. This is over, return color. if (hitType == HIT_LETTER) { // Specular bounce on a letter. No color acc. direction = direction + normal * ( normal % direction * -2); origin = sampledPosition + direction * 0.1; attenuation = attenuation * 0.2; // Attenuation via distance traveled. } if (hitType == HIT_WALL) { // Wall hit uses color yellow? float incidence = normal % lightDirection; float p = 6.283185 * randomVal(); float c = randomVal(); float s = sqrtf(1 - c); float g = normal.z < 0 ? -1 : 1; float u = -1 / (g + normal.z); float v = normal.x * normal.y * u; direction = Vec(v, g + normal.y * normal.y * u, -normal.y) * (cosf(p) * s) + Vec(1 + g * normal.x * normal.x * u, g * v, -g * normal.x) * (sinf(p) * s) + normal * sqrtf(c); origin = sampledPosition + direction * .1; attenuation = attenuation * 0.2; if (incidence > 0 && RayMarching(sampledPosition + normal * .1, lightDirection, sampledPosition, normal) == HIT_SUN) color = color + attenuation * Vec(500, 400, 100) * incidence; } if (hitType == HIT_SUN) { // color = color + attenuation * Vec(50, 80, 100); break; // Sun Color } } return color; }
許可されたビーム反射の最大数を変更するために、この関数を少し試しました。 値「2」は、文字に驚くほど美しい漆塗りのVantablack色を与えます[4] 。
1
2
3
4
完全にクリーン化されたソースコード
すべてをまとめるために、完全にクリーンなソースコードを作成しました。
参照資料
[1]出典： lexfrenchのTwitter投稿、2018年10月8日。
[2]出典： ウィキペディア：NetPBM画像形式
[3]出典： 最も強力なMacBook Pro、2017で実行された視覚化
[4]出典： ウィキペディア：Vantablack