फ्लैटलैंड का तुलनात्मक अध्ययन
एडविन अबोट के फ्लैटलैंड (1884): दो-आयामी विमान के निवासी। वे लंबाई और चौड़ाई को समझते हैं। गहराई: तीसरा आयाम उनके ऊपर ऊंचा है, अवरुद्ध। वे इसे नहीं देख सकते, इसका उपयोग नहीं कर सकते, इसका निर्माण नहीं कर सकते। उनके विश्व की ज्यामिति में उन्होंने उस आयाम को संरचनात्मक रूप से छोड़ दिया है।
MOAD-0007 इसी तरह काम करता है। 3D स्थान में वस्तुएँ स्थान, घूर्णन और बाउंडिंग वॉल्यूम के साथ स्थित होती हैं: एक समृद्ध ज्यामितीय संरचना। एक लाइनर स्कैन को उन्हें एक स्तरीय सूची के रूप में मानता है। स्पेशियल स्ट्रक्चर: मौजूद, अनुपयोगी, छोड़ दिया। हर एक इंटरसेक्शन टेस्ट पूरी सूची को स्कैन करता है, जैसे कि वस्तियों के पास कोई भी ज्यामिति और स्थिति नहीं थी।
थ्री जेएस उदाहरण
थ्री जेएस Raycaster.intersectObjects(): एक रे (3D स्थान में एक स्थिति और दिशा) दिया गया, रे के साथ सभी वस्ताओं को ढूंढना जो रे का विरोध करते हैं। प्रति फ्रेम 60 बार होवर इवेंट हैंडलर कॉल करता है। N=100 स्कीन वस्तुओं के साथ: 6,000 इंटरसेक्शन टेस्ट प्रति सेकंड। N=10,000 वस्तुओं के साथ: 600,000 टेस्ट प्रति सेकंड। लागत: N के अनुपात में होती है, नहीं कि रे के साथ वास्तव में विरोध करती हैं।
N=100 पर: अवरुद्ध। फ्रेम बजट (60fps पर 16.7ms) लागत को स्वीकार करता है बिना शिकायत के।
N=10,000 पर: प्रमुख। 600,000 इंटरसेक्शन टेस्ट प्रति सेकंड मुख्य थ्रेड को संतुलित करता है। फ्रेम रेट गिर जाता है। N के संकेत को पार करते हुए, काम कर रहे सीन साइलेंट रूप से ध्वस्त हो जाता है।
स्ट्रक्चर जो लाइनर स्कैन छोड़ता है।
वस्तुएँ स्थान पर स्थित होती हैं। एक वस्तु (1000, 0, 0) के स्थान पर नहीं सकती है जो रे की दिशा (-1, 0, 0) से (-1, 0, 0) के स्थान (0, 0, 0) के विपरीत होती है। एक लाइनर स्कैन इसे किसी भी तरह से जाँच करता है।
वस्तुएँ बाउंडिंग वॉल्यूम के साथ होती हैं: वस्तु को कवर करने वाली गोलाई या बॉक्स। रे जो वस्तु के बाउंडिंग वॉल्यूम को नहीं छूता है, वस्तु को नहीं छूता। एक लाइनर स्कैन पूर्ण इंटरसेक्शन टेस्ट को किसी भी तरह से कंप्यूट करता है।
ज्यामिति उसे छोड़ देती है।
गे
क्या 'स्ट्रक्चर को छोड़ दें' मतलब है
फ्लैटलैंड का प्रतीक: अबट के निवासी डीप्थ को नहीं महसूस कर सके। एक फ्लैटलैंड डिफेक्ट डेटा में मौजूद ज्यामितीय संरचना को निकालता है लेकिन उसे एल्गोरिदम में कभी नहीं लेता।
क्यों हैश सेट MOAD-0007 को ठीक नहीं कर सकता है
MOAD-0001 फिक्स: एक सीक्वेंशियल मेम्बरशिप टेस्ट को हैश सेट से बदलें। list.contains(x): O(N)। set.has(x): O(1)। सदस्य प्रश्न: 'x इस कलेक्शन में है कि नह?' स्पेसियल ज्यामिति शामिल नहीं है।
MOAD-0007 फिक्स: एक लाइनर स्पेसियल स्कैन को स्पेसियल इंडेक्स (BVH, octree, k-d tree, R-tree) से बदलें। स्पेसियल प्रश्न: 'इस कलेक्शन के इस वस्तु के पास रे/स्फीयर/फ्रस्टम इंटरसेक्ट करते हैं?' स्पेसियल प्रॉक्सिमिटी की जरूरत होती है।
एक हैश सेट सदस्य का उत्तर देता है: 'इसी सटीक वस्तु मौजूद है कि नह?' O(1)। यह प्रॉक्सिमिटी का उत्तर नहीं दे सकता है: 'इस रे के पास की वस्तुएँ?' हैश सेट को दूरी या स्पेसियल विस्तार की समझ नहीं है। हैशिंग ज्यामिति को उसी तरह से निकालता है जैसे कि एक लाइनर स्कैन करता है।
एक BVH प्रॉक्सिमिटी का उत्तर देता है: 'स्पेसियल क्वेरी के भीतर की वस्तुएँ कौन सी हैं?' O(log N + k)। यह वस्तओं को स्थान के अनुसार संगठन करता है, इसलिए प्रॉक्सिमिटी क्वेरीज़ को ज्यामितीय रूप से दूर वस्तुएँ स्किप की जाती हैं।
| प्रश्न | सही संरचना | गलत संरचना |
|----------|------------------|-----------------|
| वस्तु X इस सेट में है कि नह? | HashSet (O(1)) | लाइनर लिस्ट (O(N)) |
| इस रे के साथ इंटरसेक्ट करने वाली वस्तुएँ कौन सी हैं? | BVH/octree/k-d tree (O(log N)) | लाइनर स्कैन या हैश सेट (O(N) या O(N)) |
MOAD-0001 & MOAD-0007: दोनों O(N) परिचालनों को तेज चीजों से बदल दिया गया। प्रश्नों के अनुसार अलग-अलग संरचनाएँ आवश्यक हैं।
कब बनाएँ, कब छोड़ दें
BVH बनाने में O(N log N) लगता है। खोज करने में O(log N + k) समय लगता है। बराबरी: जब सवालों की संख्या बनाने की संख्या से अधिक होती है कि खोज के बचत समय निर्माण लागत को पार करती है।
N=100 पर: लाइनर स्कैन माइक्रोसेकंड में होता है। BVH बनाने में ओवरहेड जोड़ता है। BVH बना लें और 60 बार प्रति सेकंड खोज करें।
N=10,000 पर 60Hz पर: लाइनर स्कैन फ्रेम बजट को नियंत्रित करता है। BVH सवाल 1/1,000वें भाग का लागत 60 बार प्रति सेकंड। एक बार BVH बनाकर 60 बार प्रति सेकंड खोजें। पहले फ्रेम से पहले बराबरी का लक्ष्य हासिल किया जाता है।
नियम: N * Q > N log N, जहां Q = पुनर्स्थापित चक्र प्रति सवाल। इंटरैक्टिव 3D सीन के लिए: Q = प्रति सेकंड 60, N संकेतक = कुछ सौ वस्तुएँ।
एक 3D सीन का निदान और सुधार
एक 3D विज़ुअलाइज़ेशन एप्लिकेशन जो 5,000 भौगोलिक वस्तुएँ रेंडर करता है। एक हॉवर हैंडलर 60 बार प्रति सेकंड फायर होता है। हर हॉवर इवेंट पर, हैंडलर कॉल करता है scene.intersectObjects(ray, objects) जो सभी 5,000 वस्तुओं पर परिक्रमा करता है और प्रत्येक को रे के खिलाफ परीक्षण करता है। फ्रेम रेट 60fps से 8fps तक गिर गया।
एक साथी सलाह देता है: 'सभी वस्तियों को एक सेट में रखें जिससे O(1) खोज हो सके।'