"¡Lo hizo de nuevo!": Esto es lo que se me ocurrió cuando miré la parte posterior del folleto de Pixar
[1] , completamente lleno de código. Un grupo de construcciones y expresiones fue firmado en la esquina inferior derecha por nada menos que Andrew Kensler. Para aquellos que no lo conocen, diré: Andrew es un programador que inventó un
rastreador de rayos del tamaño de una tarjeta de negocios de 1337 bytes en 2009.
Esta vez, a Andrew se le ocurrió algo más voluminoso, pero con un resultado visual mucho más interesante. Desde que terminé de escribir los Libros negros de Game Engine sobre
Wolf3D y
DOOM , tuve tiempo de aprender el interior de su código críptico. Y casi de inmediato, me fascinaron literalmente las técnicas descubiertas en él. Eran muy diferentes del trabajo anterior de Andrew, basado en un trazador de rayos "estándar". Estaba interesado en aprender sobre la marcha de rayos, las características de la geometría volumétrica constructiva, el trazado de trazado / trazado de Monte Carlo, así como muchos otros trucos que utilizó para comprimir el código en un trozo de papel tan pequeño.
Código fuente
El frente del volante es un anuncio para el departamento de reclutamiento de Pixar. En el reverso, se imprimen 2,037 bytes de código C ++, ofuscados para ocupar la superficie más pequeña posible.
#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
¿Él incluso trabaja?
Con el código hay una instrucción para su lanzamiento. La idea es redirigir la salida estándar a un archivo. Por extensión, podemos suponer que el formato de salida es un formato de imagen de texto llamado NetPBM
[2] .
$ clang -o card2 -O3 raytracer.cpp
$ time ./card> pixar.ppm
2m58.524s reales
usuario 2m57.567s
sys 0m0.415s
Después de dos minutos y cincuenta y ocho segundos
[3] , se genera la siguiente imagen. Es sorprendente la poca cantidad de código que se requiere para ello.
Puedes extraer mucho de la imagen de arriba. El grano es un signo obvio de un "trazador de ruta". Este tipo de renderizador difiere del trazado de rayos en que los rayos no se remontan a las fuentes de luz. En este método, se emiten miles de rayos por píxel desde las fuentes y el programa los monitorea, esperando que encuentren la fuente de luz. Esta es una técnica interesante que, mucho mejor que el trazado de rayos, puede manejar la representación de oclusión ambiental, sombras suaves, cáusticos y radiosidad.
Romperemos el código en partes
Pasar la entrada a CLion formatea el código (vea la salida
aquí ) y lo divide en partes / tareas más pequeñas.
#include <stdlib.h> // card> pixar.ppm
#include <stdio.h>
#include <math.h>
#define R return
#define el operador 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% * esto)
);}};
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 "; para (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)}; para (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; para (; 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)); para (I b = 3; b -;) {I m = M (o, d, h, n); si (! M) se rompe ; 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) ; descanso;}}
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); para (I y = h; y -;) para (I x = w; x -;) {V c; para (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
Cada una de las secciones se describe en detalle en el resto del artículo:
■ - trucos ordinarios,
■ - clase de vector,
■ - código auxiliar,
■ - base de datos,
■ - marcha de rayos,
■ - muestreo,
■ - código principal.
Trucos comunes con #define y typedef
Los trucos comunes están usando #define y typedef para reducir significativamente la cantidad de código. Aquí denotamos F = float, I = int, R = return y O = operator. La ingeniería inversa es trivial.
Clase v
Luego viene la clase V, que renombré a Vec (aunque, como veremos a continuación, también se usa para almacenar canales RGB en formato flotante).
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); }
Tenga en cuenta que no hay operador de resta (-), por lo que en lugar de escribir "X = A - B", se utiliza "X = A + B * -1". La raíz cuadrada inversa es útil más adelante para normalizar los vectores.
Función principal
main () es el único carácter que no puede ofuscarse porque es invocado por la función _start de la biblioteca libc. Por lo general, vale la pena comenzar con él, porque será más fácil trabajar de esta manera. Me tomó un tiempo entender el significado de las primeras letras, pero aun así logré crear algo legible.
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);
Tenga en cuenta que los literales flotantes no contienen la letra "f", y la parte fraccionaria se descarta para ahorrar espacio. El mismo truco se usa a continuación, donde se cae la parte entera (flotante x = .5). También es inusual la construcción "for" con una expresión de iteración insertada dentro de la condición de interrupción.
Esta es una función principal bastante estándar para un rayo / trazado de ruta. Aquí se establecen vectores de cámara y se emiten rayos para cada píxel. La diferencia entre el trazador de rayos y el trazador de ruta es que se emiten varios rayos por píxel en el TP, que se desplazan ligeramente al azar. Luego, el color obtenido para cada rayo en un píxel se acumula en tres canales flotantes R, B, G. Al final, se realiza la corrección tonal del resultado del método Reinhardt.
La parte más importante es sampleCount, que teóricamente se puede establecer en 1 para acelerar el renderizado y la iteración. Aquí hay representaciones de muestra con valores de muestra de 1 a 2048.
Encabezado de spoiler
1

2

4 4

8

16

32

64

128

256

512

1024

2048
Código de ayuda
Otra pieza simple de código son las funciones auxiliares. En este caso, tenemos una función trivial min (), un generador de valores aleatorios en el intervalo [0,1] y una prueba mucho más interesante boxTest (), que forma parte del sistema Constructive Solid Geometry (CSG) utilizado para cortar el mundo. CSG se discute en la siguiente sección.
float min(float l, float r) { return l < r ? l : r; } float randomVal() { return (float) rand() / RAND_MAX; }
Funciones de geometría volumétrica constructiva.
No hay vértices en el código. Todo se hace usando las funciones CSG. Si no está familiarizado con ellos, simplemente diga que se trata de funciones que describen si la coordenada está dentro o fuera del objeto. Si la función devuelve una distancia positiva, entonces el punto está dentro del objeto. Una distancia negativa indica que el punto está fuera del objeto. Hay muchas funciones para describir diferentes objetos, pero en aras de la simplificación, tomemos por ejemplo una esfera y dos puntos, A y B.
La función testSphere () devuelve -1 para el punto A (es decir, está afuera) y 1 para B (es decir, está adentro). Las señales a distancia son solo un truco, que le permite obtener dos piezas de información en lugar de una en el caso de un solo valor. También se puede escribir un tipo de función similar para describir un paralelogramo (esto es exactamente lo que se realiza en la función BoxTest).
Ahora veamos qué sucede si voltea el signo del valor de retorno.
Ahora no describimos un objeto sólido, sino que declaramos que todo el mundo es sólido y cortamos el espacio vacío en él. Las funciones se pueden usar como ladrillos de construcción, que cuando se combinan pueden describir formas más complejas. Usando el operador de suma lógica (función min) podemos cortar un par de rectángulos uno encima del otro y el resultado se verá así.
Si lo piensas bien, se parece a la habitación que estamos estudiando, porque la habitación inferior se expresa exactamente de esta manera, con la ayuda de dos paralelogramos cortados.
Ahora, habiendo dominado el poderoso conocimiento de CSG, podemos volver al código y considerar la función de la base de datos, que es la más difícil de manejar.
#define HIT_NONE 0 #define HIT_LETTER 1 #define HIT_WALL 2 #define HIT_SUN 3
Puede ver aquí la función de "cortar" el paralelogramo, en el que solo se utilizan dos rectángulos para construir toda la habitación (nuestro cerebro hace el resto, representa las paredes). La escalera horizontal es una función CSG un poco más compleja que utiliza la división del resto. Y finalmente, las letras de la palabra PIXAR están formadas por 15 líneas con un par “origen / delta” y dos casos especiales para curvas en las letras P y R.
Rayo marchando
Con una base de datos de funciones CSG que describe el mundo, es suficiente para omitir todos los rayos emitidos en la función main (). La marcha de rayos usa la función de distancia. Esto significa que la posición de muestreo se desplaza una distancia hacia el obstáculo más cercano.
La idea de la marcha de rayos basada en la distancia es avanzar una distancia hasta el objeto más cercano. Al final, el haz se acercará tanto a la superficie que puede considerarse un punto de incidencia.
Tenga en cuenta que la marcha de rayos no devuelve una verdadera intersección con la superficie, sino una aproximación. Es por eso que la marcha se detiene en el código cuando d <0.01f.
Poniendo todo junto: muestreo
La investigación del trazado de ruta está casi completa. Nos falta un puente que conecte la función main () con el rayo marcher. Esta última parte, a la que renombré "Trace", es el "cerebro" en el que los rayos rebotan o se detienen, dependiendo de lo que encuentren.
Vec Trace(Vec origin, Vec direction) { Vec sampledPosition, normal, color, attenuation = 1; Vec lightDirection(!Vec(.6, .6, 1));
Experimenté un poco con esta función para cambiar el número máximo de reflejos de haz permitidos. El valor "2" le da a las letras un color Vantablack lacado sorprendentemente hermoso
[4] .
1234 4Código fuente completamente limpio
Para poner todo junto, creé un
código fuente completamente limpio.
Referencias
[1] Fuente:
publicación de Twitter de lexfrench el 8 de octubre de 2018.[2] Fuente:
Wikipedia: formato de imagen NetPBM[3] Fuente:
visualización realizada en el MacBook Pro más potente, 2017[4] Fuente:
Wikipedia: Vantablack