Vor einigen Jahren hat das SQL.ru-Forum beschlossen, Ray-Tracer-Implementierungen in verschiedenen Programmiersprachen zu vergleichen . Leider kann meine Bewerbung da nicht teilnehmen Das Wort "PIXAR" wird nicht angezeigt, daher veröffentliche ich es hier.

Für die Reinheit des Experiments habe ich SQLite ohne Erweiterungen verwendet. Es stellte sich heraus, dass es dort nicht einmal eine SQRT-Funktion gibt.

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;

Hier können Sie den Würfel drehen

Unter kat Zeile für Zeile Analyse der Anfrage. Wie üblich sind ausreichende Kenntnisse der Grundlagen von SQL und Schulmathematik ausreichend.

Haftungsausschluss: Ich bin weit von der Welt der Datenbank entfernt, daher werde ich rechtzeitig für Kommentare in PM sein.

Version für Postgres (UPD: Dank Flags wurde es um eine Größenordnung schneller, UPD2: eine Reihe von Verbesserungen, jetzt beträgt die Ausführungszeit 150 ms)

Vielen Dank an XareH für die Optimierung der Anfrage.

 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;

Um die Terminologie und das Prinzip des Algorithmus zu verstehen, wird empfohlen, den Artikel über Ray Marching für Excel zu lesen.

Allgemeine Struktur

Liste der Staging-Tabellen:

numbers (n) - enthält Zahlen von 0 bis 89.
pixels (row, col) - enthält die Zeilen- und Spaltennummer für jedes "Pixel".
rawRays (row, col, x, y, z) - enthält abnormale Strahlen von der Kamera zum Bildschirm .
norms (row, col, x, y, z, n) - enthält die Länge der Strahlen.
rays (row, col, x, y, z) - enthält normalisierte Strahlen von der Kamera zum Bildschirm .
iters (row, col, it, v) - enthält Iterationen Ray Marching.
lastIters (row, col, v0, v1, v2) - enthält die letzten drei Iterationen aus der vorherigen Tabelle für jedes "Pixel".
res (col, v) - enthält die "Helligkeit" der Pixel.

In Bezug darauf, wie sie voneinander abhängen, ist alles einfach: Jede nächste Tabelle verwendet nur die vorherige, und die letzte Abfrage verwendet nur die res Tabelle.

Alle Tabellen (außer numbers und iters ) enthalten 81 x 29 Zeilen (eine für jedes „Pixel“), die row und col indizieren ihre Koordinaten. Die iters Tabelle enthält 81 x 29 x 15 Zeilen (eine für jede Ray-Marching-Iteration für jedes „Pixel“). Die Iterationsnummer befindet sich in der Spalte it .

Die letzte Abfrage erzeugt eine Tabelle mit einer Zeile und Spalten mit Text. Alle anderen Tabellen enthalten nur reelle Zahlen (die Spalten row , col und nicht negative Ganzzahlen).

Es stellt sich heraus, wenn wir die Hilfstabellen weglassen, eine sehr einfache Abfragestruktur:

 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;

Rekursive Abfragen

Hier ist eine Standardmethode, um eine Tabelle mit Zahlen von 0 bis 89 zu erhalten:

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

Rekursive Abfragen funktionieren nur im WITH Konstrukt. Beachten Sie, dass der Name der Tabelle in ihrer Definition verwendet wird.
SELECT 0 as n ist die Zeile, in der die rekursive Abfrage beginnt.
UNION ALL bedeutet, dass alle Zeilen, die als Ergebnis zurückgegeben werden, ohne zusätzliche Überprüfungen zu einer Tabelle verkettet werden. Wenn Sie einfach UNION schreiben, werden alle Duplikate gelöscht.
SELECT n+1 FROM numbers WHERE n<80 . Eine wichtige Nuance dabei ist, dass die numbers immer eine Zeile mit der vorherigen Nummer enthält. Irgendwann wird die Bedingung in WHERE abschneiden und die Abfrage wird nicht mehr ausgeführt. Erst danach werden alle vorherigen Tabellenzustände durch die Operation UNION ALL .

Extrahieren Sie die Quadratwurzel

Wir werden die Heron-Methode (babylonische Methode) zur Berechnung der Wurzel verwenden. Nehmen wir an, wir wollen berechnen

$\ sqrt {S}$ . Wir bauen eine Serie

$x_0, x_1, \ ldots$ nach folgender Formel:

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

Die Logik der Methode ist sehr einfach:

$\ sqrt {S}$ liegt immer dazwischen

$x$ und

$\ frac {S} {x}$ für eine beliebige Anzahl

$x$ . Daher ist es natürlich, die Mitte des Segments zwischen diesen Zahlen als Annäherung zu nehmen.

Geometrisch kann dies wie folgt dargestellt werden:

Jeder nächste Wert bringt die Wurzel näher und näher, in einem Schritt verringert sich der Fehler mindestens zweimal.

Anfangswert

$x_0$ kann eine beliebige positive Zahl sein, zum Beispiel 1. Im Quake-Spiel wurde dafür die magische Konstante 0x5f3759df verwendet (genauer gesagt, sie wurde für die invertierte Quadratwurzel verwendet, dennoch kann eine ähnliche Methode für die übliche Wurzel erfunden werden ), aber leider gibt es kein SQL Zugriff auf die binäre Darstellung von Gleitkommazahlen.

In diesem Artikel wird die Wurzel an zwei Stellen benötigt:

Wenn Sie Vektoren normalisieren, die die Kamera verlassen: Das Marschieren von Strahlen hängt stark von den Entfernungen ab. Um sie zu verschieben, benötigen Sie einen Vektor der Länge 1.
bei der Berechnung des Abstands zur Grenze einer Kugel, die aus einem Quadrat herausgeschnitten ist.

Im ersten Fall liegen die Werte in einem engen Bereich

$[0,7, 1,5]$ und eine anfängliche Annäherung von 1 ist perfekt. Im zweiten Fall, beim Sammeln von Statistiken zu Anrufen, erhielt ich den Durchschnittswert

$0,28$ was als Start genommen wurde.

Es stellte sich heraus, dass mit dem richtigen Anfangswert eine Iteration ausreicht ! Das heißt, in unserem Fall wird die Wurzel durch eine lineare Funktion angenähert:

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

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

Berechnen Sie die Strahlen der Kamera

Die Aufgabe der ersten vier Tabellen besteht darin, jedes "Pixel" einem dreidimensionalen Vektor der Länge 1 zuzuordnen, der aus der Kamera kommt und durch den entsprechenden Punkt auf dem Bildschirm läuft .

Zuerst müssen Sie eine Tabelle mit der gewünschten Struktur erhalten, dh mit Zellen, für die die Zeilennummer und die Spaltennummer angegeben sind. Dazu wird das kartesische Produkt einer Reihe von Zahlen von 0 bis 89 genommen und leere Zeilen und Spalten daraus herausgeschnitten:

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

Als nächstes finden wir die nicht normalisierten Vektoren. Im Allgemeinen haben sie eine lange Formel trigonometrischer Funktionen. Um die Anfrage nicht zu komplizieren, habe ich die Kamera repariert und die Koeffizienten berechnet:

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

Danach müssen wir die (ungefähren) Längen dieser Vektoren nach der Formel berechnen

$sqrt_1$ ::

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

Es bleibt, die Koordinaten der Vektoren durch ihre Länge zu teilen, um Vektoren der Länge 1 zu erhalten:

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

Iterationen strahlen marschieren

Es wird ein etwas komplexeres rekursives Abfragekonstrukt verwendet, das JOIN . Wir wollen 15 Iterationen des Ray-Marching-Algorithmus für jedes Pixel durchführen. Wenn während der rekursiven Berechnung der numbers jedes Mal die Tabelle eine Zeile enthielt, die dann kombiniert wurden, enthalten die Zwischentabellen hier 81 x 29 Zeilen und werden 15 Mal berechnet.

Die gesamte dreidimensionale Geometrie ist in der Formel enthalten

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

Funktion $\ max$ bedeutet Kreuzung
$| x | - 0,3, | y | - 0,3, | z | - 0,3$ Definieren Sie drei Paare von Halbebenen, die einen Würfel mit einer Seite bilden $0.3 \ cdot 2$
$- \ left (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0,42 \ right)$ - der äußere Teil der Kugel mit dem Radius $0,42$ . Der Radius wird größer als der sichtbare genommen, um die Ungenauigkeit der Quadratwurzelnäherung auszugleichen.

Als nächstes müssen wir nur die Sequenz berechnen

$0 = v_0, v_1, v_2 \ ldots, v_ {15}$ für jedes Pixel nach der Formel:

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

$x, y, z$ - Koordinaten des normalisierten Vektors. Da die Kamerakoordinaten mehrmals wiederholt werden, habe ich sie auf eine Dezimalstelle gerundet.

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

Holen Sie sich die Intensität der "Pixel"

Hier verwenden wir dieselbe Formel wie in Excel, die die diffuse Komponente aus der Phong-Schattierung approximiert:

ä

$Intensität = \ max \ links (0, \ min \ links (1, \ frac {v_ {15} - v_ {14}} {v_ {14} - v_ {13}} \ rechts) \ rechts)$

Um es zu berechnen, müssen Sie zuerst eine Tabelle mit den letzten drei Iterationen des Strahlenmarschierens erstellen:

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

Und in der Tat die Formel selbst (Operationen

$\ max$ und

$\ min$ wird in der endgültigen Anfrage angewendet):

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

Generieren Sie ASCII-Kunst

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

Die Aufgabe der letzten Abfrage besteht darin, eine Tabelle mit Pixelintensitäten in eine ASCII-Zeile umzuwandeln. Bei der Eingabe erhält es nur die res Tabelle, die die Spalten col und v .

group_concat(s, delim) ist eine Aggregationsfunktion, die den Ausdruck s für alle Zeichenfolgen verkettet und die Zeichenfolge delim als Trennzeichen verwendet.
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - Bedingte Konstruktion, analog zum ternären Operator.
X'0A' ist das Zeilenumbruchzeichen, das vor dem ersten Zeichen jeder Zeile eingefügt wird.
|| - String-Verkettungsoperator.
substr(s, start, count) - eine Funktion, die Zählzeichen der Zeichenfolge s zurückgibt, beginnend mit dem Zeichen mit der Zahl start . Die Zeichenindizierung kommt von einem.
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ' Ist eine Zeichenfolge, die den" Farbverlauf "von Schwarz ( $ ) bis enthält "Weiß" (Leerzeichen) in ASCII-Zeichen. Entnommen von der Website http://paulbourke.net/dataformats/asciiart/ .
round(1 + max(0, min(66, v * 67))) - konvertiert reelle Zahlen aus dem Intervall $[0, 1]$ in eine ganze Zahl im Bereich $[1, 67]$ das Zeichen mit der entsprechenden Nummer zu nehmen.

3D-Engine in SQL-Abfrage