Beberapa tahun yang lalu, forum SQL.ru memutuskan untuk membandingkan implementasi ray tracer dalam berbagai bahasa pemrograman. Sayangnya, aplikasi saya tidak dapat berpartisipasi karena itu tidak menampilkan kata "PIXAR", jadi saya menerbitkannya di sini.

Untuk kemurnian percobaan, saya menggunakan SQLite tanpa ekstensi. Ternyata bahkan tidak ada fungsi SQRT di sana.

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;

Di sini Anda dapat memutar kubus

Di bawah analisis permintaan baris demi baris. Seperti biasa, pengetahuan tentang dasar-dasar SQL dan matematika sekolah sudah cukup.

Penafian: Saya jauh dari dunia basis data, jadi saya akan tepat waktu untuk komentar di PM.

Version for Postgres (UPD: berkat flag, ia menjadi lebih cepat dengan urutan besarnya, UPD2: sejumlah perbaikan, sekarang runtime 150ms)

Terima kasih kepada XareH untuk mengoptimalkan permintaan.

 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;

Untuk memahami terminologi dan prinsip algoritma, disarankan untuk membaca artikel tentang ray marching untuk Excel .

Struktur umum

Daftar tabel pementasan:

numbers (n) - berisi angka dari 0 hingga 89.
pixels (row, col) - berisi nomor baris dan kolom untuk setiap "piksel".
rawRays (row, col, x, y, z) - berisi sinar abnormal dari kamera ke layar .
norms (row, col, x, y, z, n) - berisi panjang sinar.
rays (row, col, x, y, z) - berisi sinar yang dinormalisasi dari kamera ke layar .
iters (row, col, it, v) - berisi iterasi ray marching.
lastIters (row, col, v0, v1, v2) - berisi tiga iterasi terakhir dari tabel sebelumnya untuk setiap "pixel".
res (col, v) - berisi "kecerahan" piksel.

Mengenai bagaimana mereka saling bergantung, semuanya sederhana: setiap tabel berikutnya hanya menggunakan yang sebelumnya, dan permintaan akhir hanya menggunakan tabel res .

Semua tabel (kecuali numbers dan numbers ) berisi 81 x 29 baris (satu untuk setiap "pixel"), row dan col kolom mengindeks koordinat mereka. Tabel iters berisi 81 x 29 x 15 baris (satu untuk setiap iterasi marching sinar untuk setiap "pixel"). Nomor iterasi ada di kolomnya.

Kueri akhir menghasilkan tabel satu baris dan kolom dengan teks, semua tabel lainnya hanya berisi bilangan real ( row kolom, col dan it bilangan bulat non-negatif).

Ternyata, jika kita menghilangkan tabel tambahan, struktur kueri yang sangat sederhana:

 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;

Kueri Rekursif

Berikut adalah cara standar untuk mendapatkan tabel yang berisi angka dari 0 hingga 89:

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

Kueri rekursif hanya berfungsi dalam konstruk WITH . Perhatikan bahwa nama yang diberikan ke tabel digunakan dalam definisinya.
SELECT 0 as n adalah baris di mana permintaan rekursif dimulai.
UNION ALL berarti bahwa semua baris yang dikembalikan sebagai hasilnya disatukan ke dalam satu tabel tanpa pemeriksaan tambahan. Jika Anda hanya menulis UNION , semua duplikat akan dihapus.
SELECT n+1 FROM numbers WHERE n<80 . Nuansa penting di sini adalah bahwa tabel numbers selalu berisi satu baris dengan angka sebelumnya. Pada titik tertentu, kondisi di WHERE memotongnya dan kueri akan berhenti dieksekusi. Hanya setelah itu, semua status tabel sebelumnya akan terhubung oleh operasi UNION ALL .

Ekstrak akar kuadrat

Kami akan menggunakan metode Heron (metode Babel) untuk menghitung root. Katakanlah kita ingin menghitung

s q r t S

$\ sqrt {S}$ . Kami sedang membangun seri

x_{0}, x_{1}, l d o t s

$x_0, x_1, \ ldots$ sesuai dengan rumus berikut:

x_{n + 1} = f r a c x_{n} + f r a c S x_{n} 2

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

Logika metode ini sangat sederhana:

s q r t S

$\ sqrt {S}$ selalu ada di antara

x

$x$ dan

f r a c S x

$\ frac {S} {x}$ untuk nomor berapa pun

x

$x$ . Oleh karena itu, wajar untuk mengambil tengah segmen antara angka-angka ini sebagai perkiraan.

Secara geometris, ini dapat direpresentasikan sebagai berikut:

Setiap nilai berikutnya membawa root lebih dekat dan lebih dekat, dalam satu langkah kesalahan berkurang setidaknya dua kali.

Nilai awal

x_{0}

$x_0$ dapat berupa angka positif, misalnya 1. Dalam permainan Gempa, konstanta ajaib 0x5f3759df digunakan untuk ini (lebih tepatnya, itu digunakan untuk akar kuadrat terbalik, namun, metode serupa dapat ditemukan untuk root biasa), tetapi, sayangnya, di SQL ada akses ke representasi biner nomor floating point.

Dalam artikel ini, root diperlukan di dua tempat:

ketika menormalkan vektor yang meninggalkan kamera: ray marching sangat tergantung pada jarak, dan untuk menunda mereka, Anda memerlukan vektor dengan panjang 1.
ketika menghitung jarak ke batas bola yang dipotong dari kotak.

Dalam kasus pertama, nilainya berada dalam kisaran sempit

[0, 7, 1, 5]

$[0,7, 1,5]$ dan perkiraan awal 1 sempurna. Dalam kasus kedua, mengumpulkan statistik panggilan, saya mendapat nilai rata-rata

0, 28

$0,28$ yang diambil sebagai yang mulai.

Ternyata dengan nilai awal yang benar , satu iterasi sudah cukup ! Artinya, dalam kasus kami, root diperkirakan dengan fungsi linier:

s q r t_{1} (x) = f r a c 1 + x 2

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

s q r t_{2} (x) = f r a c 0.28 + f r a c x 0.28 2 = 0.14 + 1.78 x

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

Hitung sinar dari kamera

Tugas dari empat tabel pertama adalah untuk mengasosiasikan setiap "pixel" dengan vektor tiga dimensi panjang 1 yang keluar dari kamera dan melewati titik yang sesuai pada layar .

Pertama, Anda perlu mendapatkan tabel dengan struktur yang diinginkan, yaitu, dengan sel yang menunjukkan nomor baris dan nomor kolom. Untuk ini, produk Cartesian dari serangkaian angka dari 0 hingga 89 diambil dan baris dan kolom yang kosong dipotong darinya:

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

Selanjutnya kita menemukan vektor yang tidak dinormalisasi. Secara umum, mereka memiliki rumus panjang fungsi trigonometri. Agar tidak mempersulit permintaan, saya memperbaiki kamera dan menghitung koefisien:

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

Setelah itu, kita harus menghitung panjang (perkiraan) vektor-vektor ini dengan rumus

s q r t_{1}

$sqrt_1$ :

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

Tetap membagi koordinat vektor dengan panjangnya untuk mendapatkan vektor dengan panjang 1:

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

Iterasi sinar berbaris

Ini menggunakan konstruksi kueri rekursif yang sedikit lebih kompleks yang berisi JOIN . Kami ingin melakukan 15 iterasi dari algoritma marching ray untuk setiap piksel. Jika selama perhitungan rekursif tabel numbers setiap kali tabel berisi satu baris, yang kemudian digabungkan, di sini tabel perantara berisi 81 x 29 baris dan dihitung 15 kali.

Semua geometri tiga dimensi terkandung dalam rumus

S D F b e g i n p m a t r i x x y z e n d p m a t r i x = m a k s k i r i (| x | - 0, 3, | y | - 0, 3, | z | - 0, 3, - k i r i (s q r t_{2} (x^{2} + y^{2} + z^{2}) - 0, 42 k a n a n) k a n a n)

$SDF \ begin {pmatrix} x \\ y \\ z \ end {pmatrix} = \ maks \ kiri (| x | - 0,3, | y | - 0,3, | z | - 0,3, - \ kiri (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0,42 \ kanan) \ kanan)$

fungsi $\ maks$ berarti persimpangan
$| x | - 0,3, | y | - 0,3, | z | - 0,3$ tentukan tiga pasang bidang setengah membentuk kubus dengan sisi $0,3 \ cdot 2$
$- \ kiri (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0,42 \ kanan)$ - bagian luar dari lingkup jari-jari $0,42$ . Jari-jari diambil lebih besar daripada yang terlihat untuk mengkompensasi ketidakakuratan perkiraan akar kuadrat.

Selanjutnya, kita hanya perlu menghitung urutannya

0 = v_{0}, v_{1}, v_{2} l d o t s, v_{15}

$0 = v_0, v_1, v_2 \ ldots, v_ {15}$ untuk setiap piksel sesuai dengan rumus:

v_{n + 1} = v_{n} + S D F k i r i (b e g i n p m a t r i x c a m X c a m Y c a m Z e n d p m a t r i x + v_{n} b e g i n p m a t r i x x y z e n d p m a t r i x b e n a r)

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

dimana

x, y, z

$x, y, z$ - koordinat vektor yang dinormalisasi. Karena koordinat kamera diulang beberapa kali, saya membulatkannya ke satu tempat desimal.

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

Dapatkan intensitas "piksel"

Di sini kami menggunakan rumus yang sama seperti di Excel, yang mendekati komponen difus dari Phong shading:

i n t e n s i t a s = m a k s k i r i (0, m i n k i r i (1, f r a c v_{15} - v_{14} v_{14} - v_{13} k a n a n) k a n a n)

$intensitas = \ maks \ kiri (0, \ min \ kiri (1, \ frac {v_ {15} - v_ {14}} {v_ {14} - v_ {13}} \ kanan) \ kanan)$

Untuk menghitungnya, Anda harus terlebih dahulu membuat tabel dengan tiga iterasi marching ray terakhir:

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

Dan, pada kenyataannya, formula itu sendiri (operasi

m a k s

$\ maks$ dan

m i n

$\ min$ akan diterapkan dalam permintaan akhir):

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

Hasilkan seni 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;

Tugas kueri terakhir adalah mengubah tabel dengan intensitas piksel menjadi satu baris ascii. Pada input, hanya menerima tabel res berisi col dan v .

group_concat(s, delim) adalah fungsi agregasi yang menggabungkan ekspresi s untuk semua string, menggunakan string delim sebagai pembatas.
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - konstruksi kondisional, analog dengan operator ternary.
X'0A' adalah karakter X'0A' baris yang dimasukkan sebelum karakter pertama dari setiap baris.
|| - operator rangkaian string.
substr(s, start, count) - fungsi yang mengembalikan count karakter string s , dimulai dengan karakter dengan angka start . Pengindeksan karakter berasal dari satu.
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ' Adalah string yang berisi" gradien "dari hitam ( $ ) ke "Putih" (spasi) dalam ascii-karakter. Diambil dari situs http://paulbourke.net/dataformats/asciiart/ .
round(1 + max(0, min(66, v * 67))) - mengonversi bilangan real dari interval $[0, 1]$ menjadi bilangan bulat dalam jangkauan $[1, 67]$ untuk mengambil karakter dengan nomor yang sesuai.

Mesin 3D di dalam query SQL