3D engine inside SQL query

Several years ago, at the SQL.ru forum, we decided to compare the implementations of ray tracers in different programming languages. Unfortunately, my application can not participate because it does not display the words "PIXAR", so I publish it here.

For the purity of the experiment, I used SQLite with no extensions. It turned out that there is not even a function 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;

')
Here you can spin the cube

Under the cut line analysis of the request. As usual, knowledge of the basics of SQL and school math is enough.

Disclaimer: I am far from the world of the database, so I will be remarks in lichku.

Postgres version (UPD: thanks to the flags it began to work an order of magnitude faster, UPD2: a number of improvements, now the runtime is 150ms)

Thank you XareH for query optimization.

 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;

To understand the terminology and the principle of the algorithm, it is recommended to read the article about ray marching for Excel .

General structure

List of intermediate tables:

numbers (n) - contains numbers from 0 to 89.
pixels (row, col) - contains the number of the row and column for each "pixel".
rawRays (row, col, x, y, z) - contains unnormalized rays from camera to screen .
norms (row, col, x, y, z, n) - contains the lengths of the rays.
rays (row, col, x, y, z) - contains normalized rays from camera to screen .
iters (row, col, it, v) - contains ray marching iterations.
lastIters (row, col, v0, v1, v2) - contains the last three iterations from the previous table for each "pixel".
res (col, v) - contains the "brightness" of pixels.

Regarding how they depend on each other, everything is simple: each following table uses only the previous one, and the final query uses only the res table.

All tables (except for numbers and iters ) contain 81 x 29 lines (one for each "pixel"), the columns row and col index their coordinates. The iters table contains 81 x 29 x 15 rows (one for each iteration of ray marching for each “pixel”). The iteration number is in the it column.

The final query produces a table from a single row and a column with text, all other tables contain only real numbers (the row , col and it columns are non-negative integers).

It turns out, if you omit the auxiliary tables, a very simple query structure:

 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;

Recursive queries

Here is the standard way to get a table containing numbers from 0 to 89:

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

Recursive queries work only in the WITH construct. Note that the name given to the table is used in its definition.
SELECT 0 as n is the string from which the recursive query begins.
UNION ALL means that all the resulting rows are concatenated into one table without additional checks. If you write just UNION , all duplicates will be deleted.
SELECT n+1 FROM numbers WHERE n<80 . The important caveat here is that the numbers table always contains one row with the previous number. At some point, the condition in WHERE cut and it and the query will stop. Only after this, all previous table states will be joined by the UNION ALL operation.

Extract the square root

We will use the method of Heron (Babylonian method) to calculate the root. Let's say we want to compute

$\ sqrt {S}$ . We are building a row

$x_0, x_1, \ ldots$ according to the following formula:

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

The logic of the method is very simple:

$\ sqrt {S}$ always lies between

$x$ and

$\ frac {S} {x}$ for any number

$x$ . Therefore, it is natural to take the middle of the segment between these numbers as an approximation.

Geometrically, this can be represented as:

Each following value brings the root closer and better, in one step the error decreases at least twice.

Initial value

$x_0$ can be any positive number, for example 1. In the Quake game, the magic constant 0x5f3759df was used for this (more precisely, it was used for the inverted square root, however a similar method can be invented for a normal root), but, unfortunately, there is no SQL access to the binary representation of floating-point numbers.

In this article, the root is needed in two places:

when normalizing vectors leaving the camera: ray marching strongly depends on distances, and in order to postpone them, a vector of length 1 is needed.
when calculating the distance to the border of the sphere, which is cut from the square.

In the first case, the values are in a narrow range.

$[0.7, 1.5]$ and the initial approximation 1 is perfect. In the second case, collecting statistics on calls, got the average value

$0.28$ which was taken as initial.

It turned out that with the correct initial value , one iteration is enough ! That is, in our case, the root is approximated by a linear function:

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

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

We calculate the rays from the camera

The task of the first four tables is to associate each “pixel” with a three-dimensional vector of length 1 that leaves the camera and passes through the corresponding point on the screen .

First you need to get a table with the desired structure, that is, with cells for which the row number and column number are indicated. For this, the Cartesian product of a set of numbers from 0 to 89 is taken and empty lines and columns are cut from it:

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

Next we find unnormalized vectors. In general, they have a long formula of trigonometric functions. In order not to complicate the request, I fixed the camera and predicted the coefficients:

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

After that we must calculate the (approximate) lengths of these vectors by the formula

$sqrt_1$ :

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

It remains to divide the coordinates of the vectors by their length to obtain vectors of length 1:

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

Ray marching iterations

It uses a slightly more complex construct with recursive queries, containing a JOIN . We want to perform 15 iterations of the ray marching algorithm for each pixel. If the recursive calculation of the numbers table each time the table contained one row, which were then combined, here the intermediate tables contain 81 x 29 rows and are calculated 15 times.

All three-dimensional geometry is contained in the formula

$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)$

function $\ max$ means intersection
$| x | - 0.3, | y | - 0.3, | z | - $ 0.$ three pairs of half-planes are defined, forming a cube with a side $0.3 \ cdot 2$
$- \ left (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0.42 \ right)$ - the outer part of the sphere radius $0.42$ . The radius is larger than the visible to compensate for the inaccuracy of the square root approximation.

Next we just need to calculate the sequence.

$0 = v_0, v_1, v_2 \ ldots, v_ {15}$ for each pixel by the formula:

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

Where

$x, y, z$ - coordinates of the normalized vector. Since the camera coordinates are repeated several times, I rounded them to one decimal place.

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

We get the intensity of "pixels"

It uses the same formula as Excel, which approximates the diffuse component from Phong shading:

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

To calculate it, you must first make a table with the last three iterations of 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 ), ...

And, actually, the formula itself (operations

$\ max$ and

$\ min$ will be applied in the final request):

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

We generate "ascii-art"

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

The task of the final query is to convert the table with the intensities of pixels into one ascii line. At the input, it receives only the res table, which contains the columns col and v .

group_concat(s, delim) is an aggregation function that concatenates the expression s for all rows, using the delim string as a separator.
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - conventional design, an analogue of the ternary operator.
X'0A' is a newline character that is inserted before the first character of each line.
|| - string concatenation operator.
substr(s, start, count) is a function that returns the count characters of the string s , starting with the character number start . The indexing of characters comes from one.
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ' Is a string containing a“ gradient ”from“ black ”( $ ) to "White" (space) in ascii-symbols. Taken from the site http://paulbourke.net/dataformats/asciiart/ .
round(1 + max(0, min(66, v * 67))) - convert real numbers from the interval $[0, 1]$ to an integer in the interval $[1, 67]$ to take the character with the corresponding number.

Source: https://habr.com/ru/post/435390/

All Articles