कुछ साल पहले, 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 लाइन-बाय-लाइन विश्लेषण के तहत। हमेशा की तरह, एसक्यूएल और स्कूल गणित की मूल बातों का ज्ञान पर्याप्त है।

अस्वीकरण: मैं डेटाबेस की दुनिया से बहुत दूर हूं, इसलिए मैं पीएम में टिप्पणियों के लिए समय पर पहुंचूंगा।

Postgres के लिए संस्करण (UPD: झंडे के लिए धन्यवाद यह परिमाण के एक क्रम से तेज हो गया, UPD2: कई सुधार, अब रनटाइम 150ms है)

अनुरोध को अनुकूलित करने के लिए 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;

शब्दावली के सिद्धांत और सिद्धांत को समझने के लिए, एक्सेल के लिए किरण मार्चिंग के बारे में लेख पढ़ने की सिफारिश की गई है।

सामान्य संरचना

स्टेजिंग टेबल की सूची:

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 x 29 पंक्तियाँ होती हैं (प्रत्येक "पिक्सेल" के लिए एक), row और col कॉलम अपने निर्देशांक को अनुक्रमित करते हैं। iters टेबल में 81 x 29 x 15 पंक्तियाँ हैं (प्रत्येक "पिक्सेल" के लिए प्रत्येक किरण मार्चिंग पुनरावृत्ति के लिए एक)। पुनरावृति संख्या इस कॉलम में है।

अंतिम क्वेरी पाठ के साथ एक पंक्ति और स्तंभों की एक तालिका तैयार करती है, अन्य सभी तालिकाओं में केवल वास्तविक संख्याएं होती हैं (कॉलम 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 ) ...

पुनरावर्ती प्रश्न केवल निर्माण में काम करते हैं। ध्यान दें कि तालिका में दिए गए नाम का उपयोग इसकी परिभाषा में किया गया है।
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}

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

विधि का तर्क बहुत सरल है:

$\ sqrt {S}$ के बीच हमेशा झूठ

$x$ और

$\ frac {S} {x}$ किसी भी संख्या के लिए

$x$ । इसलिए, इन संख्याओं के बीच के खंड के मध्य को एक अनुमान के रूप में लेना स्वाभाविक है।

ज्यामितीय रूप से, इसे निम्नानुसार दर्शाया जा सकता है:

प्रत्येक अगला मान रूट को करीब और करीब लाता है, एक चरण में त्रुटि कम से कम दो बार कम हो जाती है।

प्रारंभिक मूल्य

$x_0$ उदाहरण के लिए कोई भी सकारात्मक संख्या हो सकती है। 1. क्वेक गेम में, जादू निरंतर 0x5f3759df का उपयोग इसके लिए किया गया था (अधिक सटीक रूप से, इसका उपयोग उल्टे वर्गमूल के लिए किया गया था, फिर भी, एक समान विधि को नियमित रूट के लिए आविष्कार किया जा सकता है ), लेकिन, दुर्भाग्य से, SQL में वहां फ्लोटिंग पॉइंट नंबरों के बाइनरी प्रतिनिधित्व तक पहुंच।

इस लेख में, जड़ को दो स्थानों पर रखने की आवश्यकता है:

जब कैमरे को छोड़ने वाले वैक्टर को सामान्य करते हैं: किरण मार्चिंग अत्यधिक दूरी पर निर्भर करती है, और उन्हें स्थगित करने के लिए, आपको लंबाई 1 के वेक्टर की आवश्यकता होती है।
जब एक वर्ग से बाहर काट दिया जाता है कि एक क्षेत्र की सीमा के लिए दूरी की गणना।

पहले मामले में, मान एक संकीर्ण सीमा में हैं

$[0.7, 1.5]$ और 1 का प्रारंभिक सन्निकटन एकदम सही है। दूसरे मामले में, कॉल पर आंकड़े एकत्र करना, मुझे औसत मूल्य मिला

$0.28$ जिसे एक शुरुआत के रूप में लिया गया था।

यह पता चला कि सही प्रारंभिक मूल्य के साथ , एक पुनरावृत्ति पर्याप्त है ! अर्थात्, हमारे मामले में, जड़ एक रैखिक फ़ंक्शन द्वारा अनुमानित है:

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

Iterations किरण मार्चिंग

यह JOIN युक्त थोड़े अधिक जटिल पुनरावर्ती क्वेरी निर्माण का उपयोग करता है। हम प्रत्येक पिक्सेल के लिए किरण मार्चिंग एल्गोरिदम के 15 पुनरावृत्तियों को करना चाहते हैं। यदि हर बार numbers तालिका की पुनरावर्ती गणना के दौरान तालिका में एक पंक्ति होती है, जो तब संयुक्त होती थी, तो मध्यवर्ती तालिका में 81 x 29 पंक्तियाँ होती हैं और 15 बार गणना की जाती है।

सभी तीन आयामी ज्यामिति सूत्र में निहित है

$SDF \ start {pmatrix} x \\ y \\ z \ end {pmatrix} = \ max \ / (| 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, | y | - 0.3, | z | - 0.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 (\ start {pmatrix} camX \\ CAMY \\ camZ \ end {pmatrix} + v_n \ start {pmatrix} x \\ \\ z \ end {pmatrix} \ n)$

जहाँ

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

"पिक्सेल" की तीव्रता प्राप्त करें

यहां हम एक्सेल के समान सूत्र का उपयोग करते हैं, जो फोंग शेडिंग से फैलाना घटक का अनुमान लगाता है:

त ी व ् र त ा म ै क ् स ल े फ ् ट म ि न ल े फ ् ट फ ् र ा क

$तीव्रता = \ मैक्स \ लेफ्ट (0, \ मिन \ लेफ्ट (1, \ फ्राक {v_ {15} - v_ {14}} {v_ {14} - v_ {13}} \ right) \ 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 ), ...

और, वास्तव में, सूत्र ही (संचालन)

\ _

$\ _$ और

$\ min$ अंतिम अनुरोध में लागू किया जाएगा):

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

अंतिम क्वेरी का कार्य पिक्सेल तीव्रता वाली एक तालिका को एक एससीआई-पंक्ति में बदलना है। इनपुट पर, यह केवल res तालिका प्राप्त करता है जिसमें col और v कॉलम होते हैं।

group_concat(s, delim) एक एकत्रीकरण फ़ंक्शन है जो सभी स्ट्रिंग्स के लिए delim स्ट्रिंग को सीमांकक के रूप में उपयोग करके अभिव्यक्त करता है।
CASE WHEN cond1 THEN val1 WHEN cond2 THEN val2 ... ELSE valN END - सशर्त निर्माण, टर्नरी ऑपरेटर का एनालॉग।
X'0A' लाइन X'0A' कैरेक्टर है जिसे प्रत्येक लाइन के पहले कैरेक्टर से पहले डाला जाता है।
|| - स्ट्रिंग संघनन ऑपरेटर।
substr(s, start, count) - एक फ़ंक्शन जो स्ट्रिंग s वर्णों की count करता है, जो संख्या start साथ चरित्र के साथ start । चरित्र अनुक्रमण एक से आता है।
'$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ' एक स्ट्रिंग है जिसमें" ब्लैक "( $ ) से" ग्रेडिएंट "है। एससी-पात्रों में "व्हाइट" (स्पेस)। साइट http://paulbourke.net/dataformats/asciiart/ से लिया गया।
round(1 + max(0, min(66, v * 67))) - अंतराल से वास्तविक संख्याओं को परिवर्तित करें $[0, 1]$ सीमा में एक पूर्णांक में $[1, 67]$ इसी संख्या के साथ चरित्र लेने के लिए।

SQL क्वेरी के अंदर 3D इंजन