Трехмерный движок внутри запроса SQL
Несколько лет назад на форуме SQL.ru решили провести сравнение реализаций трассировщиков лучей на разных языках программирования. К сожалению, моя заявка не может участвовать т.к. она не выводит надпись «PIXAR», поэтому публикую ее здесь.
Для чистоты эксперимента я использовал SQLite без расширений. Оказалось, что там нет даже функции SQRT.
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;
:++++I _________________________" ------/jucYJLQ0OZmwwwwwwwmmZO0QCUXcnj---------- ???????:<}/nzJQOwqdbkhao***####**o LUcx|[<;???????????????? ]]]]]]]]][[[ !{xu; o#MW&8%BB@@@@@ -ct[l ]]]]]]]]]]]??- U[[[[[[[}}}}}}}}} ;1X] $$$$$$$$$$ cx[" [[[[[[[[]]]?? UUJJJCCCLLL{{{{{{{{{{ :|QZzffB$$$$$$ |Qu? {{{{{{}}}[[]]??- YUUJJJCCCLLLQQ000OOO111111111 ,l!!; 111111111111{{}}[[]]??- YUUJJJCCCLLLQQQ00OOOZZZmmmwww(((((((((((((((((((()))))))))))))11{{ i]??- YYUUUJJCCCLLL ?fuv| ZZZmmmwwwqqqpppd||||||||||||||||||((())11{ i++i;??-- YYYUUUJJJ i Cmmwwwqqqppppdddbbbbk///////||(())11 }czfYuf{_-- XYYUUU Wwwwqqqpppddddbbbbkkkk/||(())) |j :zr)-- XXYYY; $$wqqqqpppddddbbbbk/|||(()) ^X Jcf- XXXY $$$$xwqqqppppddddbbb/||(()) v LX-_ zXX! $$$$$$$nqqqqppppdddbb||(()) q mQX- zzX> $$$$$$$$$$$$qqqqppppddd|(()) k dmL-_ zzl $$$$$$$$$$$$$$wqqqqppppd((() o W*kqOJ__ czz? $$$$$$$$$$$$$$$$$ wqqqqpp|(() O $$BadmQ__ ccc!1x $$$$$$$$ wwqqqq(() {$$$$$$$Babw0___ vcc<)xXQm W%@$$$$$$ mwwwwq()) %$$$$$@%W#adwQ___ vvcc>1rzCZqkoM&B$$ bmmwww)) )o$$$$B&MokpZL-__+ uvvvcc]tuUQmpkoM Zmmmm)1 J- &MohdmQU-__++ uuvvvcc{jvUQmp ZZZm)11 J: kpmQUc-__; nuuuvvvcc}fuYL nOOZZ11 /| .0CXu}-_ nuuvvvccc-)jv !00OOO11{ ;/zvzvxt1-- vvvcccz+{ }QQ000O1{{ !~+~>?- ccczz:<] : LQQQQ00{{}}[ ]?? zzzzXX ";I;" JCCCLLLLQQQ{}}[[]]]? zzXXXYYYUUUUJJJCCCCLLL{}}[[]]] XXYYYYUUUJJJJCCCC}}[[]] YYYUUUUJJJJC}[[] YUUUUJJ[[ UU
Здесь можно покрутить кубик
Под катом построчный разбор запроса. Как обычно, достаточно знания основ SQL и школьной математики.
Disclaimer: я далек от мира БД, поэтому буду раз замечаниям в личку.
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.0 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 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) FROM res;
Для понимания терминологии и принципа работы алгоритма рекомендуется ознакомиться со статьей про ray marching для Excel.
Список промежуточных таблиц:
numbers (n)
— содержит числа от 0 до 89.pixels (row, col)
— содержит номер строки и столбца для каждого «пикселя».rawRays (row, col, x, y, z)
— содержит ненормализованные лучи из камеры к экрану.norms (row, col, x, y, z, n)
— содержит длины лучей.rays (row, col, x, y, z)
— содержит нормализованные лучи из камеры к экрану.iters (row, col, it, v)
— содержит итерации ray marching.lastIters (row, col, v0, v1, v2)
— содержит три последние итерации из предыдущей таблицы для каждого «пикселя».res (col, v)
— содержит «яркости» пикселей.
Относительно того, как они друг от друга зависят все просто: каждая следующая таблица использует только предыдущую, а финальный запрос использует только таблицу res
.
Все таблицы (за исключением numbers
и iters
) содержат по 81×29 строк (по одной на каждый «пиксель»), колонки row
и col
индексируют их координаты. Таблица iters
содержит 81×29 x 15 строк (по одной на каждую итерацию ray marching для каждого «пикселя»). Номер итерации содержится в колонке it
.
Финальный запрос выдает таблицу из одной строки и колонки с текстом, все остальные таблицы содержат только вещественные числа (при этом колонки row
, col
и it
— целые неотрицательные).
Получается, если опустить вспомогательные таблицы, очень простая структура запроса:
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;
Вот стандартный способ получить таблицу, содержащую числа от 0 до 89:
WITH RECURSIVE numbers AS (
SELECT 0 AS n
UNION ALL
SELECT n+1
FROM numbers
WHERE n<89
) ...
- Рекурсивные запросы работают только в конструкции
WITH
. Обратите внимание, что имя, даваемое таблице, используется в ее определении. SELECT 0 as n
— это строка, с которой начинается рекурсивный запрос.UNION ALL
означает, что все строки, получаемые в результате, конкатенируются в одну таблицу без дополнительных проверок. Если написать простоUNION
, будут удалены все дубликаты.SELECT n+1 FROM numbers WHERE n<80
. Важный нюанс здесь состоит в том, что таблицаnumbers
всегда содержит одну строку с предыдущим числом. В какой-то момент условие вWHERE
обрежет и ее и выполнение запроса прекратится. Только после этого, все предыдущие состояния таблицы будут соединены операциейUNION ALL
.
Мы будем использовать метод Герона (вавилонский метод) вычисления корня. Допустим, мы хотим вычислить . Мы строим ряд по следующей формуле:
Логика метода очень простая: всегда лежит между и для любого числа . Поэтому естественно взять середину отрезка между этими числами как приближение.
Геометрически это можно изобразить так:
Каждое следующее значение все лучше приближает корень, за один шаг погрешность уменьшается как минимум в два раза.
Начальное значение может быть любым положительным числом, например 1. В игре Quake для этого использовалась магическая константа 0×5f3759df (точнее, она использовалась для инвертированного квадратного корня, тем не менее аналогичный метод может быть придуман и для обычного корня), но, к сожалению, в SQL нет доступа к двоичному представлению чисел с плавающей запятой.
В этой статье корень нужен в двух местах:
- при нормировании векторов, выходящих из камеры: ray marching сильно зависит от расстояний, а для того, чтобы их откладывать, нужен вектор длины 1.
- при вычислении расстояния до границы сферы, которая вырезается из квадрата.
В первом случае значения находятся в узком диапазоне и начальное приближение 1 идеально подходит. Во втором случае, собрав статистику по вызовам, получил среднее значение , которое было взято в качестве начального.
Оказалось, что при правильном начальном значении, достаточно одной итерации! То есть в нашем случае корень приближается линейной функцией:
Задача первых четырех таблиц — каждому «пикселю» сопоставить трехмерный вектор длины 1, выходящий из камеры и проходящий через соответствующую точку экрана.
Сначала необходимо получить таблицу с нужной структурой, то есть с ячейками, для которых указаны номер строки и номер столбца. Для этого берется декартово произведение набора чисел от 0 до 89 и из него вырезаются пустые строки и столбцы:
...
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
),
...
Далее мы находим ненормированные вектора. В общем виде у них длинная формула из тригонометрических функций. Чтобы не усложнять запрос, я зафиксировал камеру и предрассчитал коэффициенты:
...
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.0 AS n
FROM rawRays
),
...
Осталось разделить координаты векторов на их длину для получения векторов длины 1:
...
rays AS (SELECT row, col, x / n AS x, y / n AS y, z / n AS z FROM norms),
...
Здесь используется чуть более сложная конструкция с рекурсивными запросами, содержащая JOIN
. Мы хотим произвести 15 итераций алгоритма ray marching для каждого пикселя. Если при рекурсивном вычислении таблицы numbers
каждый раз таблица содержала по одной строке, которые потом объединялись, здесь промежуточные таблицы содержат по 81×29 строк и вычисляются 15 раз.
Вся трехмерная геометрия содержится в формуле
Далее нам надо просто вычислить последовательность для каждого пикселя по формуле:
где — координаты нормированного вектора. Так как координаты камеры повторяются несколько раз, я округлил их до одного десятичного знака.
...
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
),
...
Здесь используется та же формула, что и в Excel, которая аппроксимирует компоненту diffuse из затенения по Фонгу:
Чтобы ее вычислить, необходимо предварительно сделать таблицу с тремя последними итерациями 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
),
...
И, собственно, сама формула (операции и будут применены в финальном запросе):
...
res AS (SELECT row, 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;
Задача финального запроса состоит в том, чтобы конвертировать таблицу с интенсивностями пикселей в одну ascii-строку. На вход он получает только таблицу res
, содержащую колонки col
и v
.
group_concat(s, delim)
— агрегирующая функция, конкатенирующая выражениеs
для всех строк, используя строкуdelim
в качестве разделителя.CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END
— условная конструкция, аналог тернарного оператора.X'0A'
— символ переноса строки, который вставляется перед первым символом каждой строки.||
— оператор конкатенации строк.substr(s, start, count)
— функция, возвращающаяcount
символов строкиs
, начиная с символа с номеромstart
. Индексация символов идет с единицы.'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. '
— строка, содержащая «градиент» от «черного» ($
) к «белому» (пробел) в ascii-символах. Взято с сайта http://paulbourke.net/dataformats/asciiart/.round(1 + max(0, min(66, v * 67)))
— преобразуем вещественные числа из интервала в целое число в интервале чтобы взять символ с соответствующим номером.