सपाट भूमि का सादृश्य
एडविन एबट की Flatland (1884): द्वि-आयामी समतल के निवासी। वे लंबाई और चौड़ाई को समझते हैं। गहराई: उनके ऊपर तीसरा आयाम, अदृश्य। वे इसे समझ नहीं सकते, इसका उपयोग नहीं कर सकते, इसके साथ निर्माण नहीं कर सकते। उनकी दुनिया की ज्यामिति में एक आयाम है जिसे वे संरचनात्मक रूप से त्याग देते हैं।
MOAD-0007 ठीक उसी तरह काम करता है। 3D स्पेस में ऑब्जेक्ट्स में स्थिति, घूर्णन और बाउंडिंग वॉल्यूम होता है: एक समृद्ध ज्यामितीय संरचना। एक रैखिक स्कैन उन्हें एक सपाट सूची के रूप में मानता है। स्पेशियल संरचना: मौजूद, अप्रयुक्त, त्याग दी गई। हर इंटरसेक्शन टेस्ट पूरी सूची को स्कैन करता है, मानो ऑब्जेक्ट्स में कोई ज्यामिति और कोई स्थिति ही न हो।
Three.js उदाहरण
Three.js Raycaster.intersectObjects(): एक रे (3D स्पेस में एक पोज़िशन और डायरेक्शन) दिए जाने पर, उन सभी ऑब्जेक्ट्स को ढूंढना जो रे से इंटरसेक्ट करते हैं। इम्प्लीमेंटेशन: सभी N सीन ऑब्जेक्ट्स पर इटरेट करना, हर एक को रे के विरुद्ध टेस्ट करना। हर कॉल पर O(N)।
एक हॉवर इवेंट हैंडलर 60 फ्रेम प्रति सेकंड पर हर फ्रेम intersectObjects() को एक बार कॉल करता है। N=100 ऑब्जेक्ट्स के साथ: प्रति सेकंड 6,000 इंटरसेक्शन टेस्ट। N=10,000 ऑब्जेक्ट्स के साथ: प्रति सेकंड 600,000 टेस्ट। कॉस्ट: N के अनुपात में, न कि उन ऑब्जेक्ट्स की संख्या के अनुपात में जिन्हें रे वास्तव में इंटरसेक्ट करती है।
N=100 पर: अदृश्य। फ्रेम बजट (60fps पर 16.7ms) बिना शिकायत के कॉस्ट को अवशोषित कर लेता है।
N=10,000 पर: प्रमुख। प्रति सेकंड 600,000 इंटरसेक्शन टेस्ट मुख्य थ्रेड को संतृप्त कर देते हैं। फ्रेम रेट गिर जाता है। वह सीन जो N=100 पर काम कर रहा था, जैसे ही N थ्रेशोल्ड को पार करता है, चुपचाप ढह जाता है।
वह स्ट्रक्चर जिसे लीनियर स्कैन डिस्कार्ड करता है
ऑब्जेक्ट्स स्पेस में पोज़िशन रखते हैं। पोज़िशन (1000, 0, 0) पर स्थित एक ऑब्जेक्ट पोज़िशन (0, 0, 0) से (-1, 0, 0) दिशा में पॉइंटिंग वाली रे से इंटरसेक्ट नहीं कर सकता: ऑब्जेक्ट विपरीत दिशा में स्थित है। एक लीनियर स्कैन फिर भी इसे चेक करता है।
ऑब्जेक्ट्स में बाउंडिंग वॉल्यूम होते हैं: एक स्फीयर या बॉक्स जो पूरे ऑब्जेक्ट को घेरता है। एक रे जो किसी ऑब्जेक्ट के बाउंडिंग वॉल्यूम से इंटरसेक्ट नहीं करती, उस ऑब्जेक्ट से भी इंटरसेक्ट नहीं कर सकती। एक लीनियर स्कैन फिर भी पूर्ण इंटरसेक्शन टेस्ट की गणना करता है।
ज्योमेट्री एन्कोड करती है कि किन ऑब्जेक्ट्स को स्किप करना है। लीनियर स्कैन ज्योमेट्री को नज़रअंदाज़ कर देता है। यही डिस्कार्ड है।
'संरचना को त्यागना' का अर्थ
Flatland सादृश्य: एबट के निवासी गहराई को समझ नहीं पाते थे। एक Flatland दोष उस ज्यामितीय संरचना को त्याग देता है जो डेटा में मौजूद होती है लेकिन कभी एल्गोरिदम में प्रवेश नहीं करती।
Why a Hash Set Cannot Fix MOAD-0007
MOAD-0001 fix: एक अनुक्रमिक सदस्यता परीक्षण को हैश सेट से बदलें। list.contains(x): O(N)। set.has(x): O(1)। सदस्यता प्रश्न: 'क्या x इस संग्रह में है?' कोई स्थानिक ज्यामिति शामिल नहीं।
MOAD-0007 fix: एक रैखिक स्थानिक स्कैन को स्थानिक सूचकांक (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)) | रैखिक स्कैन OR HashSet (O(N) या O(N)) |
MOAD-0001 & MOAD-0007: दोनों O(N) ऑपरेशन हैं जिन्हें कुछ तेज़ चीज़ से बदला गया। अलग संरचनाएँ इसलिए जरूरी हैं क्योंकि प्रश्न अलग-अलग हैं।
कब बनाएँ, कब छोड़ें
BVH बनाने में O(N log N) खर्च होता है। क्वेरी करने में O(log N + k) लगता है। ब्रेक-ईवन: जब क्वेरी की संख्या इतनी हो कि क्वेरी बचत, निर्माण लागत से अधिक हो जाए।
N=100 पर: लीनियर स्कैन माइक्रोसेकंड में पूरा होता है। BVH निर्माण अतिरिक्त ओवरहेड जोड़ता है। BVH छोड़ दें।
N=10,000 पर 60Hz पर: लीनियर स्कैन फ्रेम बजट पर हावी हो जाता है। BVH क्वेरी लीनियर स्कैन की 1/1,000वीं लागत पर आती है। 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) लुकअप के लिए Set में रखें।'