Alguns anos atrás, o fórum SQL.ru decidiu comparar implementações de ray tracer em diferentes linguagens de programação. Infelizmente, meu aplicativo não pode participar porque não exibe a palavra "PIXAR", então eu a publico aqui.

Para a pureza do experimento, usei o SQLite sem extensões. Descobriu-se que não há sequer uma função SQRT lá.

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;

Aqui você pode girar o cubo

Sob análise kat linha a linha da solicitação. Como sempre, o conhecimento dos conceitos básicos de SQL e matemática da escola é suficiente.

Isenção de responsabilidade: estou longe do mundo do banco de dados, por isso chegarei a tempo de comentar no PM.

Versão para Postgres (UPD: graças a sinalizadores, tornou-se mais rápido em uma ordem de grandeza, UPD2: uma série de melhorias, agora o tempo de execução é de 150ms)

Agradecemos ao XareH por otimizar a solicitação.

 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 entender a terminologia e o princípio do algoritmo, é recomendável ler o artigo sobre marchas com raios no Excel .

Estrutura geral

Lista de tabelas de preparação:

numbers (n) - contém números de 0 a 89.
pixels (row, col) - contém o número da linha e da coluna de cada "pixel".
rawRays (row, col, x, y, z) - contém raios anormais da câmera para a tela .
norms (row, col, x, y, z, n) - contém os comprimentos dos raios.
rays (row, col, x, y, z) - contém raios normalizados da câmera para a tela .
iters (row, col, it, v) - contém iterações ray marching.
lastIters (row, col, v0, v1, v2) - contém as três últimas iterações da tabela anterior para cada "pixel".
res (col, v) - contém o "brilho" dos pixels.

Quanto a como eles dependem um do outro, tudo é simples: cada tabela a seguir usa apenas a anterior e a consulta final usa apenas a tabela res .

Todas as tabelas (exceto numbers e iters ) contêm 81 x 29 linhas (uma para cada "pixel"), as colunas de row e col indexam suas coordenadas. A tabela iters contém 81 x 29 x 15 linhas (uma para cada iteração de marchas de raio para cada "pixel"). O número da iteração está na coluna it .

A consulta final produz uma tabela de uma linha e colunas com texto; todas as outras tabelas contêm apenas números reais (a row colunas, col e são números inteiros não negativos).

Acontece que, se omitirmos as tabelas auxiliares, uma estrutura de consulta muito simples:

 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

Aqui está uma maneira padrão de obter uma tabela contendo números de 0 a 89:

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

Consultas recursivas funcionam apenas na construção WITH . Observe que o nome dado à tabela é usado em sua definição.
SELECT 0 as n é a linha na qual a consulta recursiva começa.
UNION ALL significa que todas as linhas retornadas como resultado são concatenadas em uma tabela sem verificações adicionais. Se você escrever simplesmente UNION , todas as duplicatas serão excluídas.
SELECT n+1 FROM numbers WHERE n<80 . Uma nuance importante aqui é que a tabela de numbers sempre contém uma linha com o número anterior. Em algum momento, a condição WHERE truncará e a consulta interromperá a execução. Somente depois disso, todos os estados da tabela anterior serão conectados pela operação UNION ALL .

Extraia a raiz quadrada

Usaremos o método Heron (método babilônico) para calcular a raiz. Digamos que queremos calcular

$\ sqrt {S}$ . Estamos construindo uma série

$x_0, x_1, \ ldots$ de acordo com a seguinte fórmula:

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

A lógica do método é muito simples:

$\ sqrt {S}$ sempre fica entre

$x$ e

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

$x$ . Portanto, é natural considerar o meio do segmento entre esses números como uma aproximação.

Geometricamente, isso pode ser representado da seguinte maneira:

Cada próximo valor aproxima a raiz cada vez mais; em uma etapa, o erro diminui pelo menos duas vezes.

Valor inicial

$x_0$ pode ser qualquer número positivo, por exemplo 1. No jogo Quake, a constante mágica 0x5f3759df foi usada para isso (mais precisamente, foi usada para a raiz quadrada invertida, no entanto, um método semelhante pode ser inventado para a raiz comum), mas, infelizmente, no SQL existe acesso à representação binária de números de ponto flutuante.

Neste artigo, a raiz é necessária em dois lugares:

ao normalizar vetores saindo da câmera: a marcha dos raios depende muito das distâncias e, para adiá-los, é necessário um vetor de comprimento 1.
ao calcular a distância até o limite de uma esfera cortada de um quadrado.

No primeiro caso, os valores estão em uma faixa estreita

$[0,7, 1,5]$ e uma aproximação inicial de 1 é perfeita. No segundo caso, coletando estatísticas de chamadas, obtive o valor médio

$inline$ que foi tomado como inicial.

Aconteceu que, com o valor inicial correto , uma iteração é suficiente ! Ou seja, no nosso caso, a raiz é aproximada por uma função linear:

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

$sqrt_2 (x) = \ frac {0,28 + \ frac {x} {0,28}} {2} = 0,14 + 1,78 x$

Calcular os raios da câmera

A tarefa das quatro primeiras tabelas é associar cada "pixel" a um vetor tridimensional de comprimento 1 saindo da câmera e passando pelo ponto correspondente na tela .

Primeiro, você precisa obter uma tabela com a estrutura desejada, ou seja, com células para as quais o número da linha e o número da coluna são indicados. Para isso, o produto cartesiano de um conjunto de números de 0 a 89 é obtido e linhas e colunas vazias são cortadas:

 ... 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 seguir, encontramos os vetores não normalizados. Em geral, eles têm uma longa fórmula de funções trigonométricas. Para não complicar a solicitação, consertei a câmera e calculei os 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 ), ...

Depois disso, devemos calcular os comprimentos (aproximados) desses vetores pela 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 ), ...

Resta dividir as coordenadas dos vetores pelo seu comprimento para obter vetores do comprimento 1:

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

Iterações ray marchando

Ele usa uma construção de consulta recursiva um pouco mais complexa que contém JOIN . Queremos fazer 15 iterações do algoritmo de marcação de raios para cada pixel. Se durante o cálculo recursivo da tabela de numbers cada vez que a tabela continha uma linha, que foi então combinada, aqui as tabelas intermediárias contêm 81 x 29 linhas e são calculadas 15 vezes.

Toda a geometria tridimensional está contida na 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 \ direita) \ direita)$

função $\ max$ significa interseção
$| x | - 0,3, | y | - 0,3, | z | - 0,3$ define três pares de semiplanos formando um cubo com lado $0,3 \ cdot 2$
$- \ left (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0,42 \ right)$ - a parte externa da esfera do raio $inline$ . O raio é maior que o visível para compensar a imprecisão da aproximação da raiz quadrada.

Em seguida, só precisamos calcular a sequência

$0 = v_0, v_1, v_2 \ ldots, v_ {15}$ para cada pixel de acordo com a 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)$

onde

$x, y, z$ - coordenadas do vetor normalizado. Como as coordenadas da câmera são repetidas várias vezes, as arredondei para uma casa 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 ), ...

Obtenha a intensidade dos "pixels"

Aqui usamos a mesma fórmula do Excel, que aproxima o componente difuso do sombreamento Phong:

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

Para calculá-lo, você deve primeiro criar uma tabela com as três últimas iterações do ray marching:

 ... 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 ), ...

E, de fato, a própria fórmula (operações

$\ max$ e

$\ min$ será aplicado na solicitação final):

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

Gerar 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;

A tarefa da consulta final é converter uma tabela com intensidades de pixel em uma linha ascii. Na entrada, ele recebe apenas a tabela res contém as colunas col e v .

group_concat(s, delim) é uma função de agregação que concatena a expressão s para todas as cadeias, usando a cadeia delim como um delimitador.
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - construção condicional, análoga ao operador ternário.
X'0A' é o caractere de X'0A' linha que é inserido antes do primeiro caractere de cada linha.
|| - operador de concatenação de strings.
substr(s, start, count) - uma função que retorna caracteres de count da string s , começando com o caractere com o número start . A indexação de caracteres vem de um.
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ' É uma sequência que contém o" gradiente "de preto ( $ ) para "Branco" (espaço) em caracteres ascii, retirado do site http://paulbourke.net/dataformats/asciiart/ .
round(1 + max(0, min(66, v * 67))) - converte números reais do intervalo $[0, 1]$ em um número inteiro no intervalo $[1, 67]$ para levar o caractere com o número correspondente.

Mecanismo 3D dentro da consulta SQL