数年前、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;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、キューブをスピンできます



katの要求の行ごとの分析。 いつものように、SQLの基礎と学校の数学の知識は十分です。





免責事項：私はデータベースの世界からは程遠いので、PMでのコメントに間に合います。





用語とアルゴリズムの原理を理解するには、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)
  
  
  
  -各「ピクセル」の前のテーブルからの最後の3回の反復が含まれます。
• res (col, v)
  
  
  
  -ピクセルの「明るさ」が含まれます。

それらが互いにどのように依存しているかについては、すべてが単純です。次の各テーブルは前のテーブルのみを使用し、最終クエリはres



テーブルのみを使用します。



すべてのテーブル（ numbers



とiters



を除く）には81 x 29行（「ピクセル」ごとに1行）が含まれ、 row



およびcol



列は座標にインデックスを付けます。 iters



テーブルには、81 x 29 x 15行（各「ピクセル」のレイマーチング反復ごとに1行）が含まれています。 反復番号はit



列にあります。



最後のクエリは、テキストを含む1行と1列のテーブルを生成し、他のすべてのテーブルには実数のみが含まれます（列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
  
  
  
  テーブルに常に前の数値を持つ1つの行が含まれることです。 ある時点で、 WHERE
  
  
  
  の条件WHERE
  
  
  
  切り捨てられ、クエリの実行が停止します。 その後のみ、以前のすべてのテーブル状態がUNION ALL
  
  
  
  操作によって接続されます。

平方根を抽出する

ルートの計算には、ヘロン法 （バビロン法）を使用します。 計算したいとしましょう $$$\ 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$ 。 したがって、これらの数値間のセグメントの中央を近似値として使用するのが自然です。



幾何学的には、これは次のように表すことができます。











次の値ごとにルートが近づき、1ステップでエラーが少なくとも2回減少します。



初期値 $$$x_0$ Quakeゲームでは、 マジック定数0x5f3759dfがこれに使用されました（より正確には、逆平方根に使用されましたが、通常のルートに同様の方法を発明できます ）が、残念ながらSQLはありません浮動小数点数のバイナリ表現へのアクセス。



この記事では、2つの場所にルートが必要です。

• カメラから出るベクトルを正規化する場合：レイマーチングは距離に大きく依存し、それらを延期するには長さ1のベクトルが必要です。
• 正方形から切り取られた球の境界までの距離を計算するとき。

最初のケースでは、値は狭い範囲にあります $$$[0.7、1.5]$ そして、1の初期近似は完全です。 呼び出しの統計を収集する2番目のケースでは、平均値を取得しました $$$0.28$ これは最初のものとして採用されました。



正しい初期値で、1回の反復で十分であることが判明しました。 つまり、この場合、ルートは線形関数で近似されます。

$$

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

$$

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

カメラからの光線を計算する

最初の4つのテーブルのタスクは、各「ピクセル」を、カメラから出て画面上の対応する点を通過する長さ1の3次元ベクトルに関連付けることです。



最初に、目的の構造、つまり行番号と列番号が示されているセルを持つテーブルを取得する必要があります。 これを行うには、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



テーブルの再帰的計算中に、テーブルに1行が含まれ、その行が結合された場合、中間テーブルには81 x 29行が含まれ、15回計算されます。



すべての3次元ジオメトリは式に含まれています

$$

$$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 \右）\右）$$

• 機能 $$$\ max$ 交差点を意味します
• $$$| x | -0.3、| y | -0.3、| z | -0.3ド$ 側面を持つ立方体を形成する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 \ left（\ begin {pmatrix} camX \\ camY \\ camZ \ end {pmatrix} + v_n \ begin {pmatrix} x \\ y \\ z \ end {pmatrix} \右）$$

どこで $$$x、y、z$ -正規化されたベクトルの座標。 カメラ座標は数回繰り返されるため、小数点以下1桁に丸めました。

 ... 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シェーディングからの拡散成分を近似します。

$$

$$強度= \ max \左（0、\ min \左（1、\ frac {v_ {15}-v_ {14}} {v_ {14}-v_ {13}} \右）\右）$$

計算するには、最初にレイマーチングの最後の3回の繰り返しでテーブルを作成する必要があります。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、実際には、式自体（操作 $$$\ max$ そして $$$\分$ 最終リクエストで適用されます）：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最後のクエリのタスクは、ピクセル強度を持つテーブルを1つのASCII行に変換することです。 入力では、 col



とv



列を含むres



テーブルのみを受け取ります。

• group_concat(s, delim)
  
  
  
  はgroup_concat(s, delim)
  
  
  
  文字列をdelim
  
  
  
  文字として使用して、すべての文字列の式s
  
  
  
  を連結する集約関数です。
• CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END
  
  
  
  条件付き構築、三項演算子の類似物。
• X'0A'
  
  
  
  は、各行の最初の文字の前に挿入されるX'0A'
  
  
  
  文字です。
• ||
  
  
  
  -文字列連結演算子。
• substr(s, start, count)
  
  
  
  -文字列s



count
  
  
  
  文字を返し、 start
  
  
  
  の番号の文字で始まる関数。 文字のインデックス付けは1つから行われます。
• '$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. '
  
  
  
  は、黒（ $
  
  
  
  ）からの「勾配」を含む文字列ですアスキー文字の「ホワイト」（スペース）。サイトhttp://paulbourke.net/dataformats/asciiart/から取得 。
• round(1 + max(0, min(66, v * 67)))
  
  
  
  -間隔から実数を変換します $$$[0、1]$ 範囲内の整数に $$$[1、67]$ 対応する番号のキャラクターを取得します。