Hace unos años, el foro SQL.ru decidió comparar las implementaciones de trazado de rayos en diferentes lenguajes de programación. Lamentablemente, mi solicitud no puede participar porque no muestra la palabra "PIXAR", así que la publico aquí.

Para la pureza del experimento, utilicé SQLite sin extensiones. Resultó que ni siquiera hay una función SQRT allí.

WITH RECURSIVE numbers AS (SELECT 0 AS n UNION ALL SELECT n+1 FROM numbers WHERE n<89), pixels AS (SELECT rows.n as row, cols.n as col FROM numbers as rows CROSS JOIN numbers as cols WHERE rows.n > 4 AND rows.n < 38 AND cols.n > 9 AND cols.n < 89), rawRays AS (SELECT row, col, -0.9049 + col * 0.0065 + row * 0.0057 as x, -0.1487 + row * -0.0171 as y, 0.6713 + col * 0.0045 + row * -0.0081 as z FROM pixels), norms AS (SELECT row, col, x, y, z, (1 + x * x + y * y + z * z) / 2 as n FROM rawRays), rays AS (SELECT row, col, x / n AS x, y / n AS y, z / n AS z FROM norms), iters AS (SELECT row, col, 0 as it, 0 as v FROM rays UNION ALL SELECT rays.row, rays.col, it + 1 AS it, v + MAX(ABS(0.7+v*x) - 0.3, ABS(0.7+v*y) - 0.3, ABS(-1.1+v*z) - 0.3, -((0.7+v*x) * (0.7+v*x) + (0.7+v*y) * (0.7+v*y) + (-1.1+v*z) * (-1.1+v*z)) * 1.78 + 0.28) AS v FROM iters JOIN rays ON rays.row = iters.row AND rays.col = iters.col WHERE it < 15), lastIters AS (SELECT it0.row, it0.col, it0.v AS v0, it1.v AS v1, it2.v AS v2 FROM iters as it0 JOIN iters AS it1 ON it0.col = it1.col AND it0.row = it1.row JOIN iters AS it2 ON it0.col = it2.col AND it0.row = it2.row WHERE it0.it = 15 AND it1.it = 14 AND it2.it = 13), res AS (SELECT col, (v0 - v1) / (v1 - v2) as v FROM lastIters) SELECT group_concat( substr('$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ', round(1 + max(0, min(66, v * 67))), 1) || CASE WHEN col=88 THEN X'0A' ELSE '' END, '') FROM res;

Aquí puedes girar el cubo

Bajo kat análisis línea por línea de solicitud. Como de costumbre, el conocimiento de los conceptos básicos de SQL y las matemáticas escolares es suficiente.

Descargo de responsabilidad: estoy lejos del mundo de la base de datos, por lo que llegaré a tiempo para comentarios en PM.

Versión para Postgres (UPD: gracias a las banderas se hizo más rápido en un orden de magnitud, UPD2: una serie de mejoras, ahora el tiempo de ejecución es de 150 ms)

Gracias a XareH por optimizar la solicitud.

 SET ENABLE_NESTLOOP TO OFF; WITH RECURSIVE numbers AS (SELECT n FROM generate_series(0,89) gs(n) ), pixels AS (SELECT rows.n as row, cols.n as col FROM numbers as rows CROSS JOIN numbers as cols WHERE rows.n > 4 AND rows.n < 38 AND cols.n > 9 AND cols.n < 89), rawRays AS (SELECT row, col, -0.9049::double precision + col * 0.0065 ::double precision + row * 0.0057::double precision as x, -0.1487::double precision + row * -0.0171::double precision as y, 0.6713::double precision + col * 0.0045::double precision + row * -0.0081::double precision as z FROM pixels), norms AS (SELECT row, col, x, y, z, (1 + x * x + y * y + z * z) / 2 as n FROM rawRays), rays AS (SELECT row, col, x / n AS x, y / n AS y, z / n AS z FROM norms), iters AS (SELECT row, col, 0 as it, 0.0::double precision as v FROM rays UNION ALL SELECT rays.row, rays.col, it + 1 AS it, v + GREATEST(ABS(0.7 +v*x) - 0.3 , ABS(0.7 +v*y) - 0.3 , ABS(-1.1 +v*z) - 0.3 , -(0.28 + ((0.7 +v*x) * (0.7 +v*x) + (0.7 +v*y) * (0.7 +v*y) + (-1.1 +v*z) * (-1.1 +v*z)) / 0.28 ) / 2.0 + 0.42 ) AS v FROM iters JOIN rays ON rays.row = iters.row AND rays.col = iters.col WHERE it < 15), lastIters AS (SELECT it0.row, it0.col, it0.v AS v0, it1.v AS v1, it2.v AS v2 FROM iters as it0 JOIN iters AS it1 ON it0.col = it1.col AND it0.row = it1.row JOIN iters AS it2 ON it0.col = it2.col AND it0.row = it2.row WHERE it0.it = 15 AND it1.it = 14 AND it2.it = 13), res AS (SELECT row,col, (v0 - v1) / (v1 - v2) as v FROM lastIters) SELECT string_agg(substring('$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. '::text FROM round(1 + GREATEST(0, LEAST(66, v * 67)))::integer FOR 1) || CASE WHEN col=88 THEN E'\n' ELSE '' END, ''::text order by row,col) FROM res; SET ENABLE_NESTLOOP TO ON;

Para comprender la terminología y el principio del algoritmo, se recomienda leer el artículo sobre la marcha de rayos para Excel .

Estructura general

Lista de tablas de preparación:

numbers (n) : contiene números del 0 al 89.
pixels (row, col) : contiene el número de fila y columna para cada "píxel".
rawRays (row, col, x, y, z) : contiene rayos anormales de la cámara a la pantalla .
norms (row, col, x, y, z, n) : contiene las longitudes de los rayos.
rays (row, col, x, y, z) : contiene rayos normalizados desde la cámara a la pantalla .
iters (row, col, it, v) : contiene iteraciones de marcha de rayos.
lastIters (row, col, v0, v1, v2) : contiene las últimas tres iteraciones de la tabla anterior para cada "píxel".
res (col, v) : contiene el "brillo" de los píxeles.

En cuanto a cómo dependen unos de otros, todo es simple: cada tabla siguiente usa solo la anterior, y la consulta final usa solo la tabla res .

Todas las tablas (excepto numbers e iters ) contienen 81 x 29 filas (una para cada "píxel"), las columnas de row y columnas indexan sus coordenadas. La tabla de iters contiene 81 x 29 x 15 filas (una para cada iteración de marcha de rayos para cada "píxel"). El número de iteración está en la columna it .

La consulta final produce una tabla de una fila y columnas con texto, todas las demás tablas contienen solo números reales (la row columnas, col y son enteros no negativos).

Resulta que, si omitimos las tablas auxiliares, una estructura de consulta muy simple:

 WITH RECURSIVE numbers AS (SELECT ...), pixels AS (SELECT ...), rawRays AS (SELECT ...), normsSq AS (SELECT ...), norms AS (SELECT ...), rays AS (SELECT ...), iters AS (SELECT ...), lastIters AS (SELECT ...), res AS (SELECT ...) SELECT group_concat(substr('$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ', round(1 + max(0, min(66, v * 67))), 1) || CASE WHEN col=88 THEN X'0A' ELSE '' END, '') FROM res;

Consultas recursivas

Aquí hay una forma estándar de obtener una tabla que contenga números del 0 al 89:

 WITH RECURSIVE numbers AS ( SELECT 0 AS n UNION ALL SELECT n+1 FROM numbers WHERE n<89 ) ...

Las consultas recursivas solo funcionan en la construcción WITH . Tenga en cuenta que el nombre dado a la tabla se utiliza en su definición.
SELECT 0 as n es la línea en la que comienza la consulta recursiva.
UNION ALL significa que todas las filas que se devuelven como resultado se concatenan en una tabla sin verificaciones adicionales. Si escribe simplemente UNION , se eliminarán todos los duplicados.
SELECT n+1 FROM numbers WHERE n<80 . Un matiz importante aquí es que la tabla de numbers siempre contiene una fila con el número anterior. En algún momento, la condición en WHERE cortará y la consulta dejará de ejecutarse. Solo después de eso, todos los estados de la tabla anterior se conectarán mediante la operación UNION ALL .

Extrae la raíz cuadrada

Usaremos el método Heron (método babilónico) para calcular la raíz. Digamos que queremos calcular

$\ sqrt {S}$ . Estamos construyendo una serie

$x_0, x_1, \ ldots$ de acuerdo con la siguiente fórmula:

$x_ {n + 1} = \ frac {x_n + \ frac {S} {x_n}} {2}$

La lógica del método es muy simple:

$\ sqrt {S}$ siempre se encuentra entre

$x$ y

$\ frac {S} {x}$ para cualquier número

$x$ . Por lo tanto, es natural tomar la mitad del segmento entre estos números como una aproximación.

Geométricamente, esto se puede representar de la siguiente manera:

Cada valor siguiente acerca la raíz cada vez más, en un paso el error disminuye al menos dos veces.

Valor inicial

$x_0$ puede ser cualquier número positivo, por ejemplo 1. En el juego Quake, se usó la constante mágica 0x5f3759df para esto (más precisamente, se usó para la raíz cuadrada invertida, sin embargo, se puede inventar un método similar para la raíz regular), pero, desafortunadamente, en SQL existe Acceso a la representación binaria de números de coma flotante.

En este artículo, la raíz se necesita en dos lugares:

al normalizar los vectores que salen de la cámara: la marcha de los rayos depende en gran medida de las distancias, y para posponerlos, necesita un vector de longitud 1.
al calcular la distancia al límite de una esfera que se corta de un cuadrado.

En el primer caso, los valores están en un rango estrecho

$[0.7, 1.5]$ y una aproximación inicial de 1 es perfecta. En el segundo caso, al recopilar estadísticas sobre llamadas, obtuve el valor promedio

$0.28$ que fue tomada como una de partida.

Resultó que con el valor inicial correcto , ¡una iteración es suficiente ! Es decir, en nuestro caso, la raíz se aproxima mediante una función lineal:

$sqrt_1 (x) = \ frac {1 + x} {2}$

$sqrt_2 (x) = \ frac {0.28 + \ frac {x} {0.28}} {2} = 0.14 + 1.78 x$

Calcular los rayos de la cámara

La tarea de las primeras cuatro tablas es asociar cada "píxel" con un vector tridimensional de longitud 1 que sale de la cámara y pasa por el punto correspondiente en la pantalla .

Primero debe obtener una tabla con la estructura deseada, es decir, con celdas para las que se indican el número de fila y el número de columna. Para esto, se toma el producto cartesiano de un conjunto de números del 0 al 89 y se cortan filas y columnas vacías:

 ... pixels AS ( SELECT rows.n as row, cols.n as col FROM numbers as rows CROSS JOIN numbers as cols WHERE rows.n >= 5 AND rows.n < 38 AND cols.n >= 10 AND cols.n < 89 ), ...

A continuación encontramos los vectores no normalizados. En general, tienen una fórmula larga de funciones trigonométricas. Para no complicar la solicitud, arreglé la cámara y calculé los coeficientes:

 ... rawRays AS ( SELECT row, col, -0.9049 + col * 0.0065 + row * 0.0057 as x, -0.1487 + row * -0.0171 as y, 0.6713 + col * 0.0045 + row * -0.0081 as z FROM pixels ), ...

Después de eso, debemos calcular las longitudes (aproximadas) de estos vectores mediante la fórmula

$sqrt_1$ :

 ... norms AS ( SELECT row, col, x, y, z, (1 + x * x + y * y + z * z) / 2.0 AS n FROM rawRays ), ...

Queda dividir las coordenadas de los vectores por su longitud para obtener vectores de longitud 1:

 ... rays AS (SELECT row, col, x / n AS x, y / n AS y, z / n AS z FROM norms), ...

Iteraciones de marcha de rayos

Utiliza una construcción de consulta recursiva un poco más compleja que contiene JOIN . Queremos hacer 15 iteraciones del algoritmo de marcha de rayos para cada píxel. Si durante el cálculo recursivo de la tabla de numbers cada vez que la tabla contenía una fila, que luego se combinaron, aquí las tablas intermedias contienen 81 x 29 filas y se calculan 15 veces.

Toda la geometría tridimensional está contenida en la fórmula.

$SDF \ begin {pmatrix} x \\ y \\ z \ end {pmatrix} = \ max \ left (| x | - 0.3, | y | - 0.3, | z | - 0.3, - \ left (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0.42 \ right) \ right)$

funcion $\ max$ significa intersección
$| x | - 0,3, | y | - 0,3, | z | - 0.3$ definir tres pares de semiplanos formando un cubo con lado $0.3 \ cdot 2$
$- \ left (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0.42 \ right)$ - la parte exterior de la esfera de radio $0.42$ . El radio se toma más grande que el visible para compensar la inexactitud de la aproximación de la raíz cuadrada.

Luego, solo necesitamos calcular la secuencia

$0 = v_0, v_1, v_2 \ ldots, v_ {15}$ para cada píxel de acuerdo con la fórmula:

$v_ {n + 1} = v_n + SDF \ left (\ begin {pmatrix} camX \\ camY \\ camZ \ end {pmatrix} + v_n \ begin {pmatrix} x \\ y \\ z \ end {pmatrix} \ right)$

donde

$x, y, z$ - coordenadas del vector normalizado. Como las coordenadas de la cámara se repiten varias veces, las redondeé a un decimal.

 ... iters AS ( SELECT row, col, 0 as it, 0 as v FROM rays UNION ALL SELECT rays.row, rays.col, it + 1 AS it, v + MAX( ABS(0.7+v*x) - 0.3, ABS(0.7+v*y) - 0.3, ABS(-1.1+v*z) - 0.3, -( (0.7+v*x) * (0.7+v*x) + (0.7+v*y) * (0.7+v*y) + (-1.1+v*z) * (-1.1+v*z) ) * 1.78 + 0.28 ) AS v FROM iters JOIN rays ON rays.row = iters.row AND rays.col = iters.col WHERE it < 15 ), ...

Obtenga la intensidad de los "píxeles"

Aquí usamos la misma fórmula que en Excel, que se aproxima al componente difuso del sombreado de Phong:

$intensidad = \ max \ left (0, \ min \ left (1, \ frac {v_ {15} - v_ {14}} {v_ {14} - v_ {13}} \ right) \ right)$

Para calcularlo, primero debe hacer una tabla con las últimas tres iteraciones de marcha de rayos:

 ... lastIters AS ( SELECT it0.row, it0.col, it0.v AS v0, it1.v AS v1, it2.v AS v2 FROM iters as it0 JOIN iters AS it1 ON it0.col = it1.col AND it0.row = it1.row JOIN iters AS it2 ON it0.col = it2.col AND it0.row = it2.row WHERE it0.it = 15 AND it1.it = 14 AND it2.it = 13 ), ...

Y, de hecho, la fórmula en sí (operaciones

$\ max$ y

$\ min$ se aplicará en la solicitud final):

 ... res AS (SELECT row, col, (v0 - v1) / (v1 - v2) as v FROM lastIters) ...

Generar arte ascii

 ... SELECT group_concat( substr( '$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ', round(1 + max(0, min(66, v * 67))), 1 ) || CASE WHEN col=88 THEN X'0A' ELSE '' END, '') FROM res;

La tarea de la consulta final es convertir una tabla con intensidades de píxeles en una fila de ascii. En la entrada, recibe solo la tabla res contiene las columnas col y v .

group_concat(s, delim) es una función de agregación que concatena la expresión s para todas las cadenas, utilizando la cadena delim como delimitador.
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - construcción condicional, análogo del operador ternario.
X'0A' es el carácter de X'0A' línea que se inserta antes del primer carácter de cada línea.
|| - operador de concatenación de cadenas.
substr(s, start, count) : una función que devuelve los caracteres de count de la cadena s , comenzando con el carácter con el start número. La indexación de caracteres proviene de uno.
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ' Es una cadena que contiene el" gradiente "de negro ( $ ) a "Blanco" (espacio) en caracteres ascii. Tomado del sitio http://paulbourke.net/dataformats/asciiart/ .
round(1 + max(0, min(66, v * 67))) - convierte números reales del intervalo $[0, 1]$ en un entero en el rango $[1, 67]$ tomar el personaje con el número correspondiente.

Motor 3D dentro de la consulta SQL