Il y a quelques années, le forum SQL.ru a décidé de comparer les implémentations de ray tracer dans différents langages de programmation. Malheureusement, ma candidature ne peut pas participer car il n'affiche pas le mot "PIXAR", donc je le publie ici.

Pour la pureté de l'expérience, j'ai utilisé SQLite sans extensions. Il s'est avéré qu'il n'y avait même pas de fonction SQRT là-bas.

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;

Ici, vous pouvez faire tourner le cube

Analyse kat par ligne de la demande. Comme d'habitude, la connaissance des bases du SQL et des mathématiques scolaires est suffisante.

Avertissement: Je suis loin du monde de la base de données, je serai donc à temps pour les commentaires en PM.

Version pour Postgres (UPD: grâce aux indicateurs, elle est devenue plus rapide d'un ordre de grandeur, UPD2: un certain nombre d'améliorations, maintenant le temps d'exécution est de 150 ms)

Merci à XareH d' avoir optimisé la demande.

 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;

Pour comprendre la terminologie et le principe de l'algorithme, il est recommandé de lire l' article sur la marche des rayons pour Excel .

Structure générale

Liste des tables intermédiaires:

numbers (n) - contient des nombres de 0 à 89.
pixels (row, col) - contient le numéro de ligne et de colonne pour chaque "pixel".
rawRays (row, col, x, y, z) - contient des rayons anormaux de la caméra à l' écran .
norms (row, col, x, y, z, n) - contient les longueurs des rayons.
rays (row, col, x, y, z) - contient des rayons normalisés de la caméra à l' écran .
iters (row, col, it, v) - contient des itérations de défilement des rayons.
lastIters (row, col, v0, v1, v2) - contient les trois dernières itérations du tableau précédent pour chaque "pixel".
res (col, v) - contient la "luminosité" des pixels.

En ce qui concerne la façon dont ils dépendent les uns des autres, tout est simple: chaque table suivante utilise uniquement la précédente et la requête finale utilise uniquement la table res .

Tous les tableaux (à l'exception des numbers et des iters ) contiennent 81 x 29 lignes (une pour chaque «pixel»), les colonnes de row et de colonnes indexent leurs coordonnées. Le tableau des iters contient 81 x 29 x 15 lignes (une pour chaque itération de iters rayons pour chaque «pixel»). Le numéro d'itération est dans la colonne it .

La requête finale produit un tableau d'une ligne et des colonnes avec du texte, tous les autres tableaux ne contiennent que des nombres réels (la row colonnes, col et it sont des entiers non négatifs).

Il s'avère, si nous omettons les tables auxiliaires, une structure de requête très 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;

Requêtes récursives

Voici une façon standard d'obtenir un tableau contenant des nombres de 0 à 89:

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

Les requêtes récursives fonctionnent uniquement dans la construction WITH . Notez que le nom donné à la table est utilisé dans sa définition.
SELECT 0 as n est la ligne à laquelle la requête récursive commence.
UNION ALL signifie que toutes les lignes qui sont retournées en conséquence sont concaténées dans une table sans vérifications supplémentaires. Si vous écrivez simplement UNION , tous les doublons seront supprimés.
SELECT n+1 FROM numbers WHERE n<80 . Une nuance importante ici est que la table des numbers contient toujours une ligne avec le numéro précédent. À un certain point, la condition dans WHERE tronquera et la requête cessera de s'exécuter. Ce n'est qu'après cela que tous les états de table précédents seront connectés par l'opération UNION ALL .

Extraire la racine carrée

Nous utiliserons la méthode Heron (méthode babylonienne) pour calculer la racine. Disons que nous voulons calculer

$\ sqrt {S}$ . Nous construisons une série

$x_0, x_1, \ ldots$ selon la formule suivante:

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

La logique de la méthode est très simple:

$\ sqrt {S}$ se situe toujours entre

$x$ et

$\ frac {S} {x}$ pour n'importe quel nombre

$x$ . Par conséquent, il est naturel de prendre le milieu du segment entre ces nombres comme approximation.

Géométriquement, cela peut être représenté comme suit:

Chaque valeur suivante rapproche la racine de plus en plus, en une étape l'erreur diminue au moins deux fois.

Valeur initiale

$x_0$ peut être n'importe quel nombre positif, par exemple 1. Dans le jeu Quake, la constante magique 0x5f3759df a été utilisée pour cela (plus précisément, elle a été utilisée pour la racine carrée inversée, néanmoins, une méthode similaire peut être inventée pour la racine habituelle), mais, malheureusement, il n'y a pas de SQL accès à la représentation binaire des nombres à virgule flottante.

Dans cet article, la racine est nécessaire à deux endroits:

lors de la normalisation des vecteurs quittant la caméra: la marche des rayons dépend fortement des distances, et pour les reporter, vous avez besoin d'un vecteur de longueur 1.
lors du calcul de la distance à la limite d'une sphère découpée dans un carré.

Dans le premier cas, les valeurs sont dans une plage étroite

$[0,7, 1,5]$ et une approximation initiale de 1 est parfaite. Dans le deuxième cas, en collectant des statistiques sur les appels, j'ai obtenu la valeur moyenne

$inline$ qui a été pris comme point de départ.

Il s'est avéré qu'avec la valeur initiale correcte , une itération suffit ! Autrement dit, dans notre cas, la racine est approximée par une fonction linéaire:

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

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

Calculez les rayons de la caméra

La tâche des quatre premiers tableaux est d'associer chaque «pixel» à un vecteur tridimensionnel de longueur 1 sortant de la caméra et passant par le point correspondant sur l' écran .

Vous devez d'abord obtenir un tableau avec la structure souhaitée, c'est-à-dire avec des cellules pour lesquelles le numéro de ligne et le numéro de colonne sont indiqués. Pour cela, le produit cartésien d'un ensemble de nombres de 0 à 89 est pris et des lignes et colonnes vides en sont coupées:

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

Ensuite, nous trouvons les vecteurs non normalisés. En général, ils ont une longue formule de fonctions trigonométriques. Afin de ne pas compliquer la demande, j'ai réparé la caméra et calculé les 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 ), ...

Après cela, nous devons calculer les longueurs (approximatives) de ces vecteurs par la formule

$sqrt_1$ :

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

Il reste à diviser les coordonnées des vecteurs par leur longueur pour obtenir des vecteurs de longueur 1:

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

Itération des rayons marchant

Il utilise une construction de requête récursive légèrement plus complexe contenant JOIN . Nous voulons faire 15 itérations de l'algorithme de marche de rayons pour chaque pixel. Si lors du calcul récursif de la table des numbers chaque fois la table contenait une ligne, qui ont ensuite été combinées, ici les tables intermédiaires contiennent 81 x 29 lignes et sont calculées 15 fois.

Toute la géométrie tridimensionnelle est contenue dans la formule

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

fonction $\ max$ signifie intersection
$| x | - 0,3, | y | - 0,3, | z | - 0,3$ définir trois paires de demi-plans formant un cube avec côté $0,3 $ \ cdot 2 $$
$- \ gauche (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0,42 \ droite)$ - la partie extérieure de la sphère de rayon $inline$ . Le rayon est pris plus grand que le visible pour compenser l'inexactitude de l'approximation de la racine carrée.

Ensuite, nous avons juste besoin de calculer la séquence

$0 = v_0, v_1, v_2 \ ldots, v_ {15}$ pour chaque pixel selon la formule:

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

où

$x, y, z$ - coordonnées du vecteur normalisé. Étant donné que les coordonnées de la caméra sont répétées plusieurs fois, je les ai arrondies à une décimale.

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

Obtenez l'intensité des "pixels"

Ici, nous utilisons la même formule que dans Excel, qui se rapproche du composant diffus de l'ombrage Phong:

é

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

Pour le calculer, vous devez d'abord faire un tableau avec les trois dernières itérations de la marche des rayons:

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

Et, en fait, la formule elle-même (opérations

$\ max$ et

$\ min$ sera appliqué dans la demande finale):

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

Générer de l'art 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 tâche de la requête finale consiste à convertir une table avec des intensités de pixels en une seule ligne ascii. En entrée, il ne reçoit que la table res contenant les colonnes col et v .

group_concat(s, delim) est une fonction d'agrégation qui concatène l'expression s pour toutes les chaînes, en utilisant la chaîne delim comme délimiteur.
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - construction conditionnelle, analogue de l'opérateur ternaire.
X'0A' est le caractère de X'0A' ligne qui est inséré avant le premier caractère de chaque ligne.
|| - opérateur de concaténation de chaînes.
substr(s, start, count) - une fonction qui renvoie le count caractères de la chaîne s , en commençant par le caractère avec le numéro start . L'indexation des caractères vient de l'un.
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ' Est une chaîne contenant le" gradient "de" noir "( $ ) à "Blanc" (espace) en caractères ascii. Tiré du site http://paulbourke.net/dataformats/asciiart/ .
round(1 + max(0, min(66, v * 67))) - convertit les nombres réels de l'intervalle $[0, 1]$ en un entier dans la plage $[1, 67]$ pour prendre le personnage avec le numéro correspondant.

Moteur 3D dans la requête SQL