قبل بضع سنوات ، قرر منتدى SQL.ru مقارنة تطبيقات التتبع بالأشعة بلغات البرمجة المختلفة. لسوء الحظ ، لا يمكن لطلبي المشاركة بسبب لا يعرض كلمة "PIXAR" ، لذلك أنا أنشرها هنا.

لنقاء التجربة ، كنت سكليتي دون ملحقات. اتضح أنه لا يوجد حتى وظيفة 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;

هنا يمكنك أن تدور المكعب

تحت كات خط تحليل الطلب. كالمعتاد ، معرفة أساسيات SQL والرياضيات المدرسية كافية.

إخلاء المسؤولية: أنا بعيد عن عالم قاعدة البيانات ، لذلك سأكون في الوقت المناسب للتعليقات في PM.

إصدار Postgres (UPD: بفضل الأعلام ، أصبح أسرع بترتيب ضخم ، UPD2: عدد من التحسينات ، والآن وقت التشغيل هو 150 مللي ثانية)

بفضل 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 × 29 صفًا (واحد لكل "بكسل") ، col أعمدة row والإحداثيات الخاصة بهم. يحتوي جدول iters على 81 × 29 × 15 صفًا (واحد لكل تكرار iters الشعاع لكل "بكسل"). رقم التكرار موجود في العمود.

يُنتج الاستعلام النهائي جدولًا يحتوي على صف واحد وأعمدة تحتوي على نص ، وجميع الجداول الأخرى تحتوي على أرقام حقيقية فقط ( row الأعمدة و col و عدد صحيح غير سالب).

اتضح ، إذا تجاهلنا الجداول المساعدة ، بنية استعلام بسيطة للغاية:

 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 يحتوي دائمًا على صف واحد مع الرقم السابق. في مرحلة ما ، 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$ . لذلك ، من الطبيعي أن تأخذ منتصف المقطع بين هذه الأرقام كتقريب.

هندسيا ، يمكن تمثيل ذلك على النحو التالي:

كل قيمة تالية تقرب الجذر وتقترب منه ، في خطوة واحدة ينخفض الخطأ مرتين على الأقل.

القيمة الأولية

د و ل ا

$x_0 دولا$ يمكن أن يكون أي رقم موجب ، على سبيل المثال 1. في لعبة Quake ، تم استخدام الثابت السحري 0x5f3759df لهذا الغرض (بتعبير أدق ، تم استخدامه من أجل الجذر التربيعي المقلوب ، ومع ذلك ، يمكن اختراع طريقة مماثلة للجذر العادي) ، ولكن لسوء الحظ ، في SQL هناك الوصول إلى التمثيل الثنائي لأرقام الفاصلة العائمة.

في هذه المقالة ، هناك حاجة إلى الجذر في مكانين:

عند تطبيع الموجهات التي تغادر الكاميرا: تعتمد مسيرات الشعاع اعتمادًا كبيرًا على المسافات ، ولكي تؤجلها ، تحتاج إلى متجه بطول 1.
عند حساب المسافة إلى حدود كرة مقطوعة من مربع.

في الحالة الأولى ، تكون القيم في نطاق ضيق

، د و ل ا

$[0.7 ، 1.5] دولا$ والتقريب الأولي من 1 هو الكمال. في الحالة الثانية ، وهي جمع إحصائيات عن المكالمات ، حصلت على متوسط القيمة

$inline$ التي اتخذت باعتبارها واحدة البداية.

اتضح أنه مع القيمة الأولية الصحيحة ، التكرار واحد يكفي ! وهذا هو ، في حالتنا ، يتم تقريب الجذر بواسطة دالة خطية:

$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 × 29 صفًا وتحسب 15 مرة.

ويرد كل ثلاثية الأبعاد في الصيغة

$SDF \ start {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 \ right) \ right) $$

وظيفة $\ كحد أقصى$ يعني تقاطع
$| x | - 0.3 ، | ذ | - 0.3 ، | ض | - 0.3 دولا$ تحديد ثلاثة أزواج من طائرات نصف تشكيل مكعب مع الجانب $0.3 دولار \ cdot 2 دولار$
$- \ left (sqrt_2 (x ^ 2 + y ^ 2 + z ^ 2) - 0.42 \ right)$ - الجزء الخارجي من دائرة نصف قطرها $inline$ . يتم أخذ نصف قطر أكبر من المرئي للتعويض عن عدم دقة تقريب الجذر التربيعي.

بعد ذلك ، نحتاج فقط إلى حساب التسلسل

، ، ،

$0 = v_0 ، v_1 ، v_2 \ ldots ، v_ {15}$ لكل بكسل وفقا للصيغة:

ا ل ي م ي ن

$v_ {n + 1} = v_n + SDF \ left (\ start {pmatrix} camX \\ camY \\ camZ \ end {pmatrix} + v_n \ start {pmatrix} x \\ y \\ z \ end {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:

$شدة $ = \ max \ left (0 ، \ min \ left (1 ، \ frac {v_ {15} - v_ {14}} {v_ {14} - v_ {13}} \ right) $$

لحسابها ، يجب عليك أولاً إعداد جدول يتضمن آخر ثلاث تكرارات من مسيرة الشعاع:

 ... 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 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 واحد. عند الإدخال ، يتلقى فقط جدول res يحتوي على أعمدة col و v .

group_concat(s, delim) هي دالة تجميع تقوم group_concat(s, delim) التعبير s لجميع السلاسل ، باستخدام سلسلة delim كمحدد.
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - البناء الشرطي ، التناظرية المشغل الثلاثي.
X'0A' هو حرف X'0A' الأسطر الذي تم إدراجه قبل الحرف الأول من كل سطر.
|| - سلسلة سلسلة المشغل.
substr(s, start, count) - دالة تقوم بإرجاع count الأحرف في السلسلة s ، بدءًا من الحرف مع 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