几年前，SQL.ru论坛决定比较不同编程语言中的ray tracer实现。不幸的是，我的申请无法参加，因为它不显示单词“ 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;

在这里您可以旋转立方体

根据kat逐行分析请求。像往常一样，对SQL和学校数学的基础知识已经足够了。

免责声明：我与数据库世界相去甚远，因此我将及时在PM中发表评论。

适用于Postgres的版本（UPD：由于标志，它的速度提高了一个数量级，UPD2：许多改进，现在执行时间为150ms）

感谢XareH来优化请求。

 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;

要了解算法的术语和原理，建议阅读有关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) -包含光线行进的迭代。
lastIters (row, col, v0, v1, v2) -包含上一个表格中每个“像素”的最后三个迭代。
res (col, v) -包含像素的“亮度”。

关于它们如何相互依赖，一切都很简单：每个下一个表仅使用前一个表，而最终查询仅使用res表。

所有表（ numbers和iters除外）都包含81 x 29行（每个“像素”一个）， row和col列索引其坐标。 iters表包含81 x 29 x 15行（每个“像素”的每次光线行进迭代一次）。迭代编号在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表始终包含前一个numbers一行。在某个时候， WHERE的条件WHERE截断它，并且查询将停止执行。只有在那之后，所有先前的表状态才会通过UNION ALL操作连接。

提取平方根

我们将使用Heron方法（巴比伦方法）来计算根。假设我们要计算

$\ sqrt {S}$ 。我们正在建立一个系列

， ，

$x_0，x_1，\ ldots$ 根据以下公式：

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

该方法的逻辑非常简单：

$\ sqrt {S}$ 总是介于

$x$ 和

$\ frac {S} {x}$ 对于任何数量

$x$ 。因此，很自然地将这些数字之间的线段中间作为近似值。

在几何上，这可以表示为：

每个下一个值使根越来越近，一步之内误差至少减小两次。

初始值

$x_0$ 可以是任何正数，例如1。在Quake游戏中，魔术常数0x5f3759df用于此操作（更确切地说，它用于倒数平方根，但是，可以为正则根发明类似的方法），但是不幸的是，在SQL中访问浮点数的二进制表示形式。

在本文中，在两个地方都需要根目录：

在对离开相机的矢量进行归一化时：光线行进高度依赖于距离，为了推迟它们，您需要一个长度为1的矢量。
当计算到切成正方形的球体边界的距离时。

在第一种情况下，值在狭窄范围内

，

$[0.7，1.5]$ 初始近似值为1是完美的在第二种情况下，收集通话统计信息，我得到了平均值

$0.28$ 这被视为一个开始。

事实证明，使用正确的初始值，一次迭代就足够了 ！也就是说，在我们的例子中，根由线性函数近似：

（ ）

$sqrt_1（x）= \ frac {1 + x} {2}$

（ ）

$sqrt_2（x）= \ frac {0.28 + \ frac {x} {0.28}} {2} = 0.14 + 1.78 x$

计算相机发出的光线

前四个表的任务是将每个“像素”与从相机出来并经过屏幕上相应点的长度为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 ), ...

之后，我们必须通过以下公式计算这些向量的（大约）长度

$sqrt_1$ ：

 ... 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个射线行进算法迭代。如果在每次递归计算numbers表的过程中，该表每次包含一行，然后将其合并，则此处的中间表包含81 x 29行，并计算15次。

公式中包含所有三维几何

开 始 结 束 （ ， ， ， （ （ ） 正 确 ） 正 确 ）

$SDF \开始{pmatrix} x \\ y \\ z \结束{pmatrix} = \ max \ left（| x |-0.3，| y |-0.3，| z |-0.3，-\ left（sqrt_2（x ^ 2 + y ^ 2 + z ^ 2）-0.42 \正确）\正确）$

机能 $\最大$ 指路口
$| x | -0.3，| y | -0.3，| z | -0.3$ 定义三对半平面，与边形成一个立方体 $0.3 \ cdot 2$
$-\左（sqrt_2（x ^ 2 + y ^ 2 + z ^ 2）-0.42 \右）$ -半径球的外部 $0.42$ 。取半径大于可见半径以补偿平方根近似值的不准确性。

接下来，我们只需要计算序列

， ， ，

$0 = v_0，v_1，v_2 \ ldots，v_ {15}$ 对于每个像素，根据公式：

左 （ 开 始 结 束 开 始 结 束 正 确 ）

$v_ {n + 1} = v_n + SDF \左（\开始{pmatrix} camX \\ camY \\ camZ \结束{pmatrix} + v_n \开始{pmatrix} x \\ y \\ z \结束{pmatrix} \正确）$

在哪里

， ，

$x，y，z$ -归一化向量的坐标。由于相机坐标重复了几次，因此我将它们四舍五入到小数点后一位。

 ... 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中相同的公式，该公式从Phong着色中近似了漫反射分量：

强 度 最 大 值 左 （ ， 最 小 值 左 （ ， 断 面 右 ） 右 ）

$强度= \最大值\左（0，\最小值\左（1，\断面{v_ {15}-v_ {14}} {v_ {14}-v_ {13}} \右）\右）$

要计算它，必须首先创建一个表，其中包含光线行进的最后三个迭代：

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

产生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;

最终查询的任务是将具有像素强度的表转换为一个ascii行。在输入处，它仅接收包含col和v列的res表。

group_concat(s, delim)是一个聚合函数，它将所有字符串的表达式s连接起来，并使用delim字符串作为分隔符。
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END条件构造，类似于三元运算符。
X'0A'是在每行的第一个字符之前插入的换行符。
|| -字符串串联运算符。
substr(s, start, count) -一个返回字符串s count字符的函数，该函数以数字start 。字符索引来自一个。
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. '是一个包含从黑色（ $ ）到“渐变”的字符串ascii字符中的“白色”（空格），取自http://paulbourke.net/dataformats/asciiart/ 。
round(1 + max(0, min(66, v * 67))) -从区间转换实数 $[0，1]$ 到范围内的整数 $[1，67]$ 以带相应编号的字符。

SQL查询中的3D引擎