कयामत में बीएसपी का उपयोग वास्तव में एक सरल कदम है?

समय की तकनीक का शिखर।

1993 में, आईडी सॉफ्टवेयर ने कयामत को जारी किया, जो एक पहला व्यक्ति शूटर था जो जल्दी से एक घटना में बदल गया। आज यह माना जाता है कि यह उन खेलों में से एक है जिनका इतिहास में सबसे अधिक प्रभाव पड़ा है।

डूम की रिहाई के दस साल बाद, 2003 में, पत्रकार डेविड कॉउनर ने मास्टर्स ऑफ डूम नामक एक आईडी सॉफ्टवेयर बुक प्रकाशित की , जो तब से डूम निर्माण प्रक्रिया का एक विहित विवरण बन गया है। मैंने कुछ साल पहले कयामत के परास्नातक को पढ़ा और मुझे लगभग कुछ भी याद नहीं है, लेकिन लीड प्रोग्रामर जॉन कारमैक के बारे में एक पुस्तक की एक कहानी मेरी स्मृति में संरक्षित है। मेरा विवरण पूरी तरह से सटीक नहीं होगा (अधिक विवरण के लिए नीचे देखें), लेकिन संक्षेप में, डूम विकास के शुरुआती चरण में, कार्मैक ने महसूस किया कि गेम के लिए लिखे गए 3 डी रेंडरर ने कुछ स्तरों को प्रदान करते समय धीमा करना शुरू कर दिया। यह अस्वीकार्य था, क्योंकि डूम को एक सक्रिय और यहां तक ​​कि उन्मत्त खेल बनना था। यह समझते हुए कि रेंडरर समस्या इतनी मौलिक थी कि उसे एक अधिक इष्टतम रेंडरिंग एल्गोरिदम देखना होगा, कार्मैक ने शोध लेख पढ़ना शुरू किया। नतीजतन, उन्होंने बाइनरी स्पेस पार्टीशनिंग (बीएसपी) नामक एक तकनीक को लागू किया, जिसे पहले कभी भी वीडियो गेम में इस्तेमाल नहीं किया गया था, और इस तरह इसने डूम इंजन को काफी तेज कर दिया था।

कार्मैक ने वीडियो गेम के लिए अत्याधुनिक वैज्ञानिक अनुसंधान को कैसे लागू किया इसकी कहानी ने मुझे हमेशा प्रभावित किया है। मेरी राय में, यह इस बात के लिए धन्यवाद था कि कार्मैक इस तरह के एक महान व्यक्ति बन गए। वह कई कारणों से एक कट्टरपंथी जीनियस वीडियो गेम प्रोग्रामर के रूप में जाना जाता है, लेकिन मुख्य रूप से, मैं हमेशा वैज्ञानिक लेखों और अंतरिक्ष के द्विआधारी विभाजन के पढ़ने के साथ एपिसोड को याद करता हूं।

जाहिर है, यह कहानी प्रभावशाली है, क्योंकि शब्द "अंतरिक्ष का द्विआधारी विभाजन" न केवल कार्यान्वयन के लिए, बल्कि समझ के लिए भी कुछ जटिल लगता है। लंबे समय तक मैंने माना कि कार्मैक ने एक बौद्धिक छलांग लगाई है, लेकिन जब से मुझे नहीं पता था कि अंतरिक्ष का एक द्विआधारी विभाजन क्या है, और जब यह तकनीक का उपयोग करने का फैसला किया गया था तो यह तकनीक कितनी नई थी, मुझे पूरी तरह से यकीन नहीं था। होमर सिम्पसन से अल्बर्ट आइंस्टीन के पैमाने पर बाइनरी स्पेस विभाजन को कयामत के अलावा कितना सरल था?

मुझे यह भी आश्चर्य हुआ कि बीएसपी कहां से आया और कार्मैक को यह विचार कैसे मिला। इसलिए, यह पद न केवल जॉन कार्मैक और डूम को समर्पित होगा, बल्कि "बाइनरी स्पेस पार्टीशन ट्री" (या बीएसपी ट्री) की डेटा संरचना के इतिहास के लिए भी समर्पित होगा। यह पता चला कि बीएसपी का पेड़, कम्प्यूटेशनल विज्ञान के कई अन्य पहलुओं की तरह, सेना के लिए आयोजित शोध में उत्पन्न होता है।

हाँ, यह सही है: E1M1, पहला डूम स्तर, यूएस वायु सेना के लिए धन्यवाद प्रकट हुआ।

वीएसडी का कार्य

बीएसपी का पेड़ कंप्यूटर ग्राफिक्स में सबसे कठिन कार्यों में से एक है। तीन-आयामी दृश्य को प्रस्तुत करने के लिए, रेंडरर को यह निर्धारित करना होगा कि क्या दिखाई दे रहा है और जो वर्तमान बिंदु से दिखाई नहीं दे रहा है। यह विशेष रूप से मुश्किल नहीं है यदि आपके पास बहुत समय है, लेकिन एक स्वाभिमानी वास्तविक समय गेम इंजन को दुनिया के दृश्य और अदृश्य भागों को प्रति सेकंड कम से कम 30 बार निर्धारित करना चाहिए।

इस कार्य को अक्सर दृश्य सतह निर्धारण (वीएसडी) कार्य कहा जाता है। प्रोग्रामर माइकल अब्रैश, जिन्होंने कार्मैक ऑन क्वेक ( कयामत के बाद अगला आईडी सॉफ्टवेयर गेम) के साथ काम किया, ने अपनी प्रसिद्ध पुस्तक ग्राफिक्स प्रोग्रामिंग ब्लैक बुक में वीएसडी कार्य के बारे में लिखा:

मैं सबसे मुश्किल के बारे में बात करना चाहता हूं, मेरी राय में, 3 डी ग्राफिक्स कार्य: दृश्यमान सतहों का निर्धारण (प्रत्येक पिक्सेल में वांछित सतह को चित्रित करना) और इसके करीबी रिश्तेदार - दृश्यमान सतहों के निर्धारण को गति देने के लिए कलिंग कार्य (जितनी जल्दी संभव अदृश्य बहुभुज कास्टिंग)। संक्षिप्तता के लिए, मैं संक्षिप्त नाम VSD द्वारा दृश्यमान सतहों और क्लिपिंग दोनों की परिभाषा को निरूपित करूंगा।

मैं वीएसडी को सबसे कठिन 3 डी कार्य क्यों मानता हूं? हालांकि रस्टेराइज़ेशन समस्याएं, जैसे कि टेक्सचर मैपिंग, भी आश्चर्यजनक और महत्वपूर्ण कार्य हैं, ये काफी परिमित पैमाने के कार्य हैं, जिनका समाधान उपकरण पर 3 डी त्वरक की उपस्थिति में स्थानांतरित हो जाता है; इसके अलावा, वे केवल तभी बड़े पैमाने पर होते हैं, जब स्क्रीन रिज़ॉल्यूशन बढ़ जाता है, जो काफी मुस्कराता है।

इसके विपरीत, वीएसडी एक असीमित कार्य है, और अब इसे हल करने के लिए दर्जनों समाधानों का उपयोग किया जाता है। इससे भी महत्वपूर्ण बात, वीएसडी के भोले प्रदर्शन सीधे दृश्य की जटिलता के साथ होते हैं, जो आमतौर पर एक वर्ग या क्यूबिक फ़ंक्शन के रूप में बढ़ जाता है, इसलिए यह जल्दी से यथार्थवादी दुनिया का प्रतिपादन करने में सीमित कारक बन जाता है।

अब्रश ने 90 के दशक के उत्तरार्ध में वीएसडी समस्या की जटिलता के बारे में लिखा था, कयामत के कुछ वर्षों बाद यह साबित हुआ कि आम लोग अपने घर के कंप्यूटरों पर ग्राफिकल रूप से भारी गेम खेलने में सक्षम होना चाहते हैं। 90 के दशक की शुरुआत में, जब आईडी सॉफ्टवेयर सिर्फ गेम प्रकाशित करना शुरू कर रहा था, तो उन्हें अनुचित कंप्यूटरों पर प्रभावी ढंग से काम करना था: होम मशीनों को टेक्स्ट, स्प्रेडशीट और इसी तरह के अन्य अनुप्रयोगों के साथ काम करने के लिए डिज़ाइन किया गया था। इस लक्ष्य को प्राप्त करने के लिए, कंपनी को विशेष रूप से डूम से पहले आईडी सॉफ्टवेयर द्वारा प्रकाशित कई 3 डी गेम के मामले में, कल्पना से संपर्क करना पड़ा। इन खेलों में, वीएसडी समस्या के समाधान को सरल बनाने के लिए सभी स्तरों का डिज़ाइन इस तरह से सीमित था।

उदाहरण के लिए, वोल्फेंस्टीन 3 डी में , गेम जो कि आईडी सॉफ्टवेयर ने डूम से ठीक पहले जारी किया था, प्रत्येक स्तर में अक्षों के साथ संरेखित दीवारों से मिलकर बना था। दूसरे शब्दों में, वोल्फेंस्टीन ब्रह्मांड में उत्तर / दक्षिण की दीवारें या पूर्व / पश्चिम की दीवारें हो सकती हैं, और अन्य नहीं। इसके अलावा, दीवारों को ग्रिड में निश्चित दूरी पर रखा जा सकता है - सभी गलियारों में एक ग्रिड सेल, या दो, आदि की चौड़ाई होती है, लेकिन कभी भी 2.5 सेल नहीं होती है। हालांकि इसका मतलब था कि आईडी सॉफ्टवेयर टीम लगभग समान दिखने वाले स्तर बना सकती है, लेकिन इस प्रतिबंध ने कार्मैक के लिए वोल्फेंस्टीन के लिए रेंडरर लिखना बहुत आसान बना दिया।

वोल्फेंस्टीन रेंडरर ने स्क्रीन से आभासी दुनिया में किरणों (रे मार्चिंग) को स्थानांतरित करके वीएसडी की समस्या को हल किया। आमतौर पर, रे-रेंडर रेंडरर्स रेंडरिंग रेंडरर्स होते हैं - वे अक्सर धीमे होते हैं क्योंकि रेकास्टर में वीएसडी की समस्या को हल करने के लिए रे और दुनिया में कुछ ऑब्जेक्ट के बीच पहले चौराहे को खोजने की आवश्यकता होती है, जिसमें बहुत अधिक गणना की आवश्यकता होती है। लेकिन चूंकि वुल्फेंस्टीन में सभी दीवारें ग्रिड के साथ पंक्तिबद्ध हैं, केवल एक जगह जहां एक बीम दीवार को पार कर सकती है वह ग्रिड लाइनें होगी। इसलिए, रेंडरर के लिए इन प्रत्येक चौराहे के बिंदुओं की जांच करना पर्याप्त है। यदि रेंडरर खिलाड़ी के दृष्टिकोण के निकटतम चौराहे बिंदु की जांच करके शुरू होता है, तो निकटता में दूसरे की जांच करता है, और इसी तरह खत्म होता है और जब यह पहली दीवार का सामना करता है, तो वीएसडी समस्या को सबसे तुच्छ तरीके से हल किया जाता है। बीम बस प्रत्येक पिक्सेल से आगे बढ़ी जब तक कि यह कुछ में नहीं चला, जो प्रोसेसर घड़ी की गति के मामले में बहुत सस्ती है। और चूंकि सभी दीवारों की ऊंचाई समान है, इसलिए हमारे लिए प्रत्येक स्तंभ के लिए किरणों का उत्सर्जन करना पर्याप्त है।

जब कोई विशेष ग्राफिक्स कार्ड नहीं थे, उस समय के कमजोर घर के पीसी पर काम करने के लिए वुल्फेनस्टीन ने बहुत तेजी से प्रतिपादन के इस सरलीकरण को बनाया। लेकिन ऐसा कोई दृष्टिकोण डूम में काम नहीं करेगा, क्योंकि आईडी टीम ने फैसला किया कि उसके नए खेल में अलग-अलग ऊंचाइयों के साथ विकर्ण दीवारें, सीढ़ियां और छत जैसे नए तत्व होंगे। रे मार्चिंग अब उपयुक्त नहीं थी, इसलिए कार्मैक ने एक अलग प्रकार के रेंडरर लिखे। वोल्फेंस्टीन रेंडरर, जहां पिक्सेल के प्रत्येक कॉलम के लिए बीम का उपयोग किया गया था, छवि से हटा दिया गया था, और डूम रेंडरर को वस्तुओं से पुनर्प्रकाशित किया जाना था। इसका मतलब यह था कि स्क्रीन के पिक्चर्स को ट्रेस करने और उनके रंग का निर्धारण करने के बजाय, डूम रेंडरर को दृश्य में वस्तुओं पर चलना था और उनमें से प्रत्येक को स्क्रीन पर चालू करना था।

इस तरह के रेंडर में, वीएसडी समस्या को हल करने का एक सरल तरीका एक जेड-बफर का उपयोग करना है। हर बार जब हम स्क्रीन पर एक ऑब्जेक्ट प्रोजेक्ट करते हैं, तो प्रत्येक पिक्सेल के लिए एक चेक किया जाता है जिसे हम आकर्षित करना चाहते हैं। यदि खींची जाने वाली वस्तु का भाग पिक्सेल में पहले से खींची गई वस्तु की तुलना में खिलाड़ी के करीब है, तो हम इसकी जानकारी को फिर से लिख सकते हैं। अन्यथा, आपको पिक्सेल को अपरिवर्तित छोड़ने की आवश्यकता है। यह दृष्टिकोण सरल है, लेकिन z- बफर को बहुत अधिक मेमोरी की आवश्यकता होती है, और रेंडरर अभी भी प्रोसेसर क्लॉक का एक गुच्छा खर्च कर सकता है जो कि लेवलिंग ज्यामिति को प्रोजेक्ट करने पर है जो खिलाड़ी नहीं देखेगा।

1990 के दशक की शुरुआत में, z- बफर समाधान में एक और खामी थी: वीजीए नामक वीडियो एडेप्टर प्रणाली का उपयोग करके आईबीएम-संगत पीसी पर, आउटपुट फ्रेम बफर को लिखना एक महंगा ऑपरेशन था। इसलिए, पिक्सल को रेंडर करने में लगने वाला समय, जो तब बस ओवरराइट हो जाएगा, रेंडरर के प्रदर्शन को बहुत कम कर देगा।

चूंकि फ्रेम बफ़र को लिखना इतना महंगा था, आदर्श रेंडरर को खिलाड़ी के सबसे निकट की वस्तुओं को खींचकर शुरू करना था, फिर वस्तुओं को तुरंत उनके पीछे, और इसी तरह, जब तक कि स्क्रीन के प्रत्येक पिक्सेल पर लिखना पूरा नहीं हो जाता। इस स्तर पर, रेंडरर को यह समझना चाहिए कि यह रुकने का समय था, इस प्रकार हर समय बचत करने से वह दूर की वस्तुओं की खोज में खर्च कर सकता है जो खिलाड़ी ने नहीं देखी थी। लेकिन दृश्य वस्तुओं को इस तरह से क्रमबद्ध करना, निकटतम से सबसे दूर तक, वीएसडी समस्या को हल करने के लिए समान है। हमारे सामने फिर से सवाल उठता है: एक खिलाड़ी क्या देख सकता है?


सबसे पहले, कारमैक ने डूम स्तर योजना पर भरोसा करके इस समस्या को हल करने की कोशिश की। उसके रेंडरर ने उस कमरे की दीवारों को खींचना शुरू किया जिसमें खिलाड़ी स्थित है, और फिर उसने इन कमरों में दीवारों को खींचने के लिए पड़ोसी के कमरों में डाल दिया, जो वर्तमान कमरे से दिखाई दे सकता था। यदि प्रत्येक कमरा उत्तल था, तो यह वीएसडी समस्या को हल करेगा। गैर-उत्तल कमरों को उत्तल "क्षेत्रों" में विभाजित किया जा सकता है। आप देख सकते हैं कि इस रेंडरिंग तकनीक को ऊपर दिखाए गए वीडियो में एक मजबूत मंदी की तरह कैसे देखा जा सकता है, जहां बिस्किट उपनाम वाला एक YouTuber उपयोगकर्ता अपने स्वयं के रेंडरर को प्रदर्शित करता है जो समान सामान्य एल्गोरिदम के अनुसार काम करता है। ड्यूक के तीन साल बाद जारी किए गए ड्यूक नुकेम 3 डी गेम में इस एल्गोरिदम का सफलतापूर्वक उपयोग किया गया था, जब प्रोसेसर अधिक शक्तिशाली हो गए थे। लेकिन 1993 में, उस समय, इस एल्गोरिदम का उपयोग करने वाले डूम रेंडरर ने जटिल स्तरों के साथ समस्याओं का अनुभव किया। यह विशेष रूप से स्पष्ट था जब क्षेत्रों को एक दूसरे में बनाया गया था, और यह एकमात्र तरीका था, उदाहरण के लिए, परिपत्र सीढ़ियां। पहले से ही तैयार किए गए क्षेत्र में परिपत्र सीढ़ी को कई पुनरावर्ती वंशों की आवश्यकता होती है, जो इंजन की गति को काफी कम कर देता है।

लगभग उसी समय, जब आईडी टीम ने महसूस किया कि डूम इंजन बहुत धीमा हो सकता है, आईडी सॉफ्टवेयर को सुपर निनटेंडो को वोल्फेंस्टीन 3 डी पोर्ट करने के लिए कहा गया था। एसएनईएस उस समय के आईबीएम-संगत पीसी की तुलना में कम शक्तिशाली था, और यह पता चला कि रे-मार्च तकनीक के साथ वोल्फेंस्टीन रेंडरर, अपनी सादगी के बावजूद, सुपर निनटेंडो उपकरण पर पर्याप्त गति से नहीं चला। इसलिए, कार्मैक ने एक बेहतर एल्गोरिदम की तलाश शुरू की। वास्तव में, यह वुल्फेंस्टीन के सुपर निंटेंडो पोर्ट के लिए था जो कि कार्मैक ने पहली बार बाइनरी स्पेस विभाजन का पता लगाया और कार्यान्वित किया। वोल्फेंस्टीन में यह बहुत सरल था क्योंकि सभी दीवारें कुल्हाड़ियों के समानांतर थीं; कयामत कठिन बना देती है। लेकिन कार्मैक ने महसूस किया कि बसपा के पेड़ डूम में भी गति की समस्याओं को हल करेंगे ।

बाइनरी स्पेस स्प्लिट

द्विआधारी अंतरिक्ष विभाजन 3 डी दृश्य को पूर्व-विभाजित करके वीएसडी समस्या के समाधान को सरल करता है। अभी के लिए, आपके लिए यह समझना पर्याप्त है कि विभाजन क्यों उपयोगी है: यदि आप पूरे दृश्य के माध्यम से एक रेखा खींचते हैं (जो वास्तव में 3 डी में एक विमान है), तो यह जानने के लिए कि खिलाड़ी या कैमरा किस लाइन पर है, तो हमें यह भी पता चल जाएगा कि कुछ भी नहीं है पंक्ति का दूसरा भाग उस रेखा के किनारे से वस्तुओं को बाधित करने में सक्षम नहीं होगा जहां कैमरा स्थित है। यदि आप कई बार प्रक्रिया को दोहराते हैं, तो हमें कई खंडों में विभाजित एक 3D-दृश्य मिलता है। यह मूल दृश्य पर सुधार नहीं होगा, सिवाय इसके कि अब हम इस बारे में अधिक जानते हैं कि दृश्य के विभिन्न भाग कैसे ओवरलैप कर सकते हैं।

3 डी दृश्य के इस विभाजन के बारे में लिखने वाले पहले अमेरिकी वायु सेना के लिए यह पता लगाने की कोशिश कर रहे थे कि क्या कंप्यूटर ग्राफिक्स उड़ान सिमुलेटर में उपयोग के लिए पर्याप्त प्रगतिशील हैं। उन्होंने 1969 की रिपोर्ट में अपने निष्कर्षों को प्रकाशित किया, जिसका शीर्षक था, "दृश्य सिमुलेशन में कंप्यूटर जनित छवियों के उपयोग पर शोध।" रिपोर्ट ने निष्कर्ष निकाला कि पायलटों को प्रशिक्षित करने के लिए कंप्यूटर ग्राफिक्स का उपयोग किया जा सकता है; उसी समय, शोधकर्ताओं ने चेतावनी दी कि वीएसडी के कार्य से प्रणाली का कार्यान्वयन जटिल हो जाएगा:

वास्तविक समय में छवियों की गणना करते समय सबसे महत्वपूर्ण कार्यों में से एक को हल करना होगा प्राथमिकता कार्य, या छिपी हुई लाइनें हैं। हमारे आसपास की दुनिया की हमारी रोजमर्रा की दृश्य धारणा में, प्रकृति स्वयं इस समस्या को तुच्छ सादगी के साथ हल करती है; एक अपारदर्शी वस्तु का बिंदु अन्य सभी बिंदुओं को ओवरलैप करता है जो दृष्टि की एक ही रेखा के साथ स्थित हैं और आगे दूर हैं। कंप्यूटर के मामले में, यह कार्य बहुत कठिन है। प्राथमिकता निर्धारित करने के लिए आवश्यक गणना की मात्रा, सामान्य मामले में, पर्यावरण की बढ़ती जटिलता के साथ तेजी से बढ़ती है, और जल्द ही परिप्रेक्ष्य को ध्यान में रखते हुए वस्तुओं की छवियों की खोज से जुड़े कम्प्यूटेशनल बोझ से अधिक हो जाती है।

इन शोधकर्ताओं द्वारा उल्लिखित एक समाधान, जो उन्होंने कहा था कि पहले नासा परियोजना में इस्तेमाल किया गया था, मैं "ओवरलैप मैट्रिक्स" के नाम से जाना जाता है के निर्माण पर आधारित है। शोधकर्ताओं का कहना है कि एक दृश्य को दो भागों में विभाजित करने वाले विमान का उपयोग विमान के विपरीत पक्षों पर वस्तुओं के बीच "प्राथमिकताओं के किसी भी संघर्ष" को हल करने के लिए किया जा सकता है। सामान्य स्थिति में, आपको इन विमानों को स्पष्ट रूप से दृश्य में जोड़ना पड़ सकता है, लेकिन ज्यामिति की एक निश्चित संरचना के साथ, आप वस्तुओं के मौजूदा चेहरों पर भरोसा कर सकते हैं। शोधकर्ता नीचे दिए गए उदाहरण को प्रदर्शित करते हैं, जहां पी 1 , पी 2, और पी 3 सतहों को विभाजित कर रहे हैं। यदि कैमरे का दृष्टिकोण इन विमानों में से किसी एक के सामने या "सही" पक्ष पर है, तो पी 1 है। मैट्रिक्स तीन अलग-अलग विमानों के आधार पर तीन वस्तुओं के बीच संबंध और कैमरे के दृष्टिकोण के स्थान को दिखाता है - यदि वस्तु एआई ओवरऑल ऑब्जेक्ट ऑब्जेक्ट अंज है , तो मैट्रिक्स का तत्व aij 1 के बराबर होगा।


शोधकर्ताओं ने इस मैट्रिक्स को हार्डवेयर में लागू करने और प्रत्येक फ्रेम में इसे फिर से गणना करने का प्रस्ताव दिया है। वास्तव में, मैट्रिक्स को एक बड़े स्विच या एक प्रकार के अंतर्निहित जेड-बफर के रूप में कार्य करना चाहिए। वर्तमान वस्तु का प्रतिपादन करते समय, वीडियो वस्तु के हिस्सों के लिए आउटपुट नहीं होता है जब 1 ऑब्जेक्ट कॉलम में होता है, लेकिन संबंधित पंक्ति वस्तु खींची जाती है।

इस दृष्टिकोण का एक गंभीर दोष यह है कि n ² वस्तुओं के साथ एक दृश्य का वर्णन करने के लिए आकार n ^{2 के} एक मैट्रिक्स की आवश्यकता होती है। इसलिए, शोधकर्ताओं ने यह जांचने का फैसला किया कि क्या ओवरलैप मैट्रिक्स को "प्राथमिकताओं की सूची" के रूप में प्रस्तुत करना संभव है, जिसमें केवल n का आकार होगा और उस क्रम को निर्दिष्ट करना होगा जिसमें वस्तुओं को खींचा जाना चाहिए। उन्होंने तुरंत ध्यान दिया कि कुछ दृश्यों में, उदाहरण के लिए, ऊपर दिखाए गए एक में, आदेश को पूरा करना असंभव है (चूंकि एक ओवरलैप चक्र है), इसलिए उन्होंने "सही" और "गलत" दृश्यों की गणितीय परिभाषा के लिए बहुत समय समर्पित किया। अंत में, वे इस निष्कर्ष पर पहुंचे कि कम से कम "सही" दृश्यों के लिए (और दृश्य डिजाइनर "गलत" मामलों से आसानी से बच सकते हैं), प्राथमिकताओं की एक सूची उत्पन्न की जा सकती है। लेकिन उन्होंने सूची पीढ़ी को पाठक के लिए एक अभ्यास के रूप में छोड़ दिया। ऐसा लगता है कि इस 1969 के काम का मुख्य योगदान यह इंगित करना है कि कम से कम सैद्धांतिक रूप से दृश्य में वस्तुओं को व्यवस्थित करने के लिए विभाजित विमानों का उपयोग करने की संभावना होनी चाहिए।

और केवल 1980 के एक लेख में "ए प्रियोरी ट्री स्ट्रक्चर्स द्वारा विजिबल सर्फेस जनरेशन" शीर्षक था, इसके लिए प्रदर्शित एक विशिष्ट एल्गोरिदम था। हेनरी फुच्स, ज़वी केडेम और ब्रूस नायलोर द्वारा लिखे गए इस लेख में, बसपा के पेड़ का वर्णन किया गया था। लेखकों का कहना है कि उनकी नई डेटा संरचना "एक समाधान, एक वैकल्पिक दृष्टिकोण है, जिसका उपयोग दस साल पहले किया गया था, लेकिन कुछ कठिनाइयों के कारण इतना व्यापक नहीं हुआ," - इसलिए वे 1969 में अमेरिकी वायु सेना के लिए चुने गए निर्णय पर प्रतिक्रिया देते हैं। बीएसपी के पेड़ के निर्माण के बाद, यह आसानी से दृश्य में प्राथमिकता के साथ वस्तुओं को व्यवस्थित करने के लिए इस्तेमाल किया जा सकता है।

फुच, केडेम और नायलर ने बीएसपी के पेड़ के संचालन का काफी स्पष्ट विवरण दिया है, लेकिन मैं कम औपचारिक, लेकिन संक्षिप्त रूप देने की कोशिश करूंगा।

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

मान लीजिए कि हम दृश्य के ज्यामिति को वापस सामने प्रस्तुत करना चाहते हैं।(इसे "कलाकार का एल्गोरिथ्म" कहा जाता है, क्योंकि इसका मतलब है कि कैमरे से पॉलीगॉन को सही रेंडर बनाते हुए, कैमरे के करीब पॉलीगोन से भरा जाएगा।) ऐसा करने के लिए, हमें बस अपने बीएसपी पेड़ के चारों ओर जाने की आवश्यकता है; बाएं या दाएं सबट्री को तैयार किया जाना चाहिए, इस आधार पर निर्णय किया जाता है कि इस नोड से जुड़े डिवाइडिंग विमान के सामने या पीछे के आधे स्थान के आधार पर कैमरा का दृष्टिकोण कहां है। यही है, पेड़ के प्रत्येक नोड में, हम पहले सभी बहुभुज को विमान के "दूर" किनारे पर सौंप देते हैं, फिर पृथक्करण विमान पर बहुभुज, और फिर विमान के "निकट" किनारे पर बहुभुज। "निकट और" दूर "बहुभुज कैमरे के दृष्टिकोण के सापेक्ष परिभाषित किए गए हैं। यह VSD समस्या को हल करता है क्योंकि, जैसा कि हमने कुछ पैराग्राफ पहले सीखा था,जुदाई विमान के दूर पर बहुभुज सामने की तरफ कुछ भी ओवरलैप नहीं कर सकते हैं।

नीचे दिए गए आरेख में बीएसपी पेड़ के निर्माण और ट्रैवर्सल को दिखाया गया है जो एक सरल 2 डी दृश्य का वर्णन करता है। 2 डी में, विमानों को विभाजित करने के बजाय विभाजन रेखाओं का उपयोग किया जाता है, लेकिन मूल विचार एक ही रहता है।




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

फुच, केडेम और नायलर की रिपोर्ट है कि आगे के शोध के लिए "अच्छे" बीएसपी वृक्ष के निर्माण की आवश्यकता है। बीएसपी के पेड़ की गुणवत्ता इस बात पर निर्भर करती है कि आप किन पॉलीगनों को अलग करने वाले विमानों को परिभाषित करने के लिए चुनते हैं। इससे पहले, मैंने इस बिंदु को छोड़ दिया था, लेकिन यदि आप एक ऐसे विमान का उपयोग करते हैं जो बंटवारे के समय अन्य बहुभुजों को काटता है, तो बीएसपी एल्गोरिदम को काम करने के लिए, आपको पार किए गए बहुभुजों को दो में विभाजित करने की आवश्यकता है, ताकि एक आधा एक-स्थान को संदर्भित करता है और दूसरा दूसरे को। यदि यह अक्सर होता है, तो बीएसपी के पेड़ का निर्माण दृश्य में बहुभुज की संख्या में काफी वृद्धि करता है।

1980 के लेख के लेखकों में से एक, ब्रूस नायलर ने बाद में 1993 के अपने लेख कंस्ट्रक्टिंग गुड पार्टिशन ट्रीज़ में इस मुद्दे के बारे में लिखा था। कार्मैक के सहकर्मी और आईडी सॉफ्टवेयर के सह-संस्थापक जॉन रोमेरो के अनुसार, यह लेख कार्मैक द्वारा पढ़े गए कार्यों में से एक था जब उन्होंने डूम में बीएसपी के पेड़ों को लागू करने की कोशिश की ।

कयामत में बसपा के पेड़

स्मरण करो कि डूम रेंडरर के पहले ड्राफ्ट में, कार्मैक ने रेंडरर को उस कमरे से बाहर भरने के लिए स्तर के ज्यामिति के लिए रेंडरिंग ऑर्डर सेट करने का प्रयास किया , जहां खिलाड़ी पड़ोसी कमरों में है। बीएसपी के पेड़ इस आदेश को निर्धारित करने के लिए अधिक सुविधाजनक तरीका थे, क्योंकि वे रेंडरर की समस्या से बचने के लिए बार-बार एक कमरे (या सेक्टर) पर जाते हैं, जो प्रोसेसर चक्रों को बर्बाद करते हैं।

"बीएसपी के पेड़ों को कयामत में जोड़ना " व्यवहार में इसका मतलब है कि कयामत स्तर के संपादक में बीएसपी ट्री जनरेटर जोड़ना । कयामत स्तर के निर्माण को पूरा करने के बादबीएसपी का पेड़ स्तर ज्यामिति से उत्पन्न हुआ था। फेबियन संगलर के अनुसार, पीढ़ी की प्रक्रिया एक स्तर के लिए आठ सेकंड और पहले कयामत के सभी स्तरों के लिए 11 मिनट तक ले सकती है । पीढ़ी की प्रक्रिया आंशिक रूप से इस तथ्य के कारण इतनी लंबी थी कि कार्मैक बीएसपी पीढ़ी एल्गोरिथ्म विभिन्न उत्तराधिकारियों का उपयोग करके "अच्छा" बीएसपी पेड़ खोजने की कोशिश कर रहा है। खेल के दौरान आठ सेकंड की देरी अक्षम्य होगी, लेकिन प्रारंभिक पीढ़ी में यह काफी स्वीकार्य लग रहा था, प्रदर्शन में वृद्धि को देखते हुए कि बीएसपी पेड़ों को रेंडरर के लिए प्रदान किया गया था। एक व्यक्तिगत स्तर के उत्पन्न बीएसपी पेड़ को गेम में लोड किए गए स्तर के डेटा के भाग के रूप में सहेजा गया था जब इसे लॉन्च किया गया था।

कार्मैक ने 1980 के लेख में वर्णित बीएसपी ट्री एल्गोरिथ्म में एक महत्वपूर्ण बदलाव किया: कयामत के बादऔर वर्तमान-स्तरीय बीएसपी के पेड़ को स्मृति में पढ़ते हुए, रेंडरर इस पेड़ का उपयोग वस्तुओं को सामने से नहीं, बल्कि सामने से पीछे की ओर खींचने के लिए करता है। 1980 के एक लेख में, फुच्स, केडेम और नाइलर ने दिखाया कि कैसे एक बीएसपी के पेड़ को बैक-टू-बैक रेंडरिंग के साथ एक कलाकार के एल्गोरिदम को लागू करने के लिए इस्तेमाल किया जा सकता है, लेकिन कलाकार के एल्गोरिथ्म में बड़ी मात्रा में पुनरावृत्ति होती है, जो आईबीएम-संगत पीसी पर महंगा हो सकता है। इसलिए, डूम रेंडरर खिलाड़ी के साथ एक ज्यामिति के साथ शुरू होता है, और फिर सबसे दूर खींचता है। बीएसपी के पेड़ का उपयोग करके इस तरह के रिवर्स ऑर्डर को लागू करना आसान है, क्योंकि आप बस पेड़ के प्रत्येक नोड पर बैकट्रेस निर्णय ले सकते हैं। दूर की ज्यामिति को करीब से ऊपर खींचने से रोकने के लिए, कयामत रेंडरएक तरह के निहित z- बफर का उपयोग करता है, जो बहुत कम मेमोरी का उपभोग करते हुए, नियमित z- बफर के कई लाभ प्रदान करता है। एक सरणी है जो क्षैतिज आयाम में ओवरलैप को ट्रैक करती है, और दो अन्य सरणियां जो स्क्रीन के ऊपर और नीचे ऊर्ध्वाधर दिशा में ओवरलैप को ट्रैक करती हैं। Doom रेंडरर एक सच्चे z- बफर का उपयोग किए बिना कर सकता है, क्योंकि Doom , सख्ती से बोल रहा है, पूरी तरह से तीन-आयामी गेम नहीं था। कम खर्चीली डेटा संरचनाओं ने इसमें काम किया क्योंकि कुछ तत्व डूम में संभव नहीं थे: क्षैतिज ओवरलैप सरणी ने काम किया क्योंकि कोई ढलान वाली दीवारें नहीं थीं, और ऊर्ध्वाधर ओवरलैप सरणियों ने काम किया क्योंकि वहाँ कोई दीवारें नहीं थीं, उदाहरण के लिए, दो स्थित थे अन्य खिड़कियों के ऊपर एक।


कयामत II , अपने पूर्ववर्ती के रूप में जटिल है।


लेकिन किसी ने भी खून की पुनरावृत्ति की शिकायत नहीं की।


क्वेक टेक्नॉलॉजीज में एक नया शब्द

केवल मुश्किल काम बचा है कि कैसे चल रहे डूम पात्रों को बीएसपी के पेड़ के उपयोग से तैयार किए गए स्तरों के स्थिर ज्यामिति में एकीकृत किया जाए । डूम में दुश्मन बीएसपी के पेड़ का हिस्सा नहीं हो सकते थे क्योंकि वे आगे बढ़ रहे थे; बीएसपी का पेड़ केवल निश्चित ज्यामिति के साथ काम करता है। इसलिए, कयामत रेंडरपहले स्तर के स्थिर ज्यामिति को खींचता है, स्क्रीन के सेगमेंट (जिसमें एक और मेमोरी-कुशल डेटा संरचना का उपयोग करके) को आरेखित किया जाता है। फिर वह दुश्मनों को पीछे से आगे की ओर खींचता है, उन्हें स्क्रीन के उन हिस्सों के साथ काटता है जो उन्हें ओवरलैप करते हैं। यह प्रक्रिया बीएसपी के पेड़ के साथ प्रतिपादन के रूप में इष्टतम नहीं है, लेकिन चूंकि आमतौर पर ज्यामिति की तुलना में कम दुश्मन हैं, इसलिए गति यहां एक समस्या नहीं है। कयामत

में बीएसपी के पेड़ों का उपयोग करना एक बड़ी जीत थी। जाहिर है, कार्मैक को इस बात का अहसास था कि बीएसपी पेड़ आदर्श समाधान होगा। लेकिन क्या यह फैसला सरल था ? में खेल इंजन पर अपनी उत्कृष्ट पुस्तक कयामत

फेबियन संगलर ने जॉन रोमेरो के हवाले से कहा कि ब्रूस नयलर का लेख, "कंस्ट्रक्टिंग गुड पार्टिशनिंग ट्रीज़", मुख्य रूप से 3 डी मॉडल के पिछले चेहरों को ट्रिम करने के लिए बीएसपी पेड़ों का उपयोग करने के बारे में था। रोमेरो के अनुसार, कार्मैक ने सोचा कि एल्गोरिथम अभी भी डूम के लिए उपयोगी हो सकता है , इसलिए उन्होंने इसे लागू किया। कार्मैक के लिए यह काफी सराहनीय है क्योंकि उनका तात्पर्य है कि उन्होंने वास्तविक समय के वीडियो गेम में भी बीएसपी के पेड़ों की उपयोगिता देखी थी, जब अन्य लोग अभी भी इस तकनीक का इस्तेमाल स्थिर दृश्यों को प्रस्तुत करने के लिए करते थे। वही चापलूसी कहानी मास्टर्स ऑफ डूम में है: Kouchner ने सुझाव दिया कि केरमेक Naylor लेख को पढ़ने और सोचा: "अगर आप बसपा-वृक्ष का उपयोग कर सकते क्या न केवल एक 3 डी छवि, लेकिन यह भी आभासी दुनिया के पूरे बनाने के लिए?"

इन निष्कर्षों को बसपा-वृक्ष कहानी अनदेखी कर रहे हैं। जब अमेरिकी वायु सेना के शोधकर्ताओं ने पहली बार महसूस किया कि एक दृश्य को विभाजित करने से प्रतिपादन में तेजी लाने में मदद मिल सकती है, तो वे प्रतिपादन के वास्तविक समय त्वरण में रुचि रखते थे, क्योंकि अंत में उन्होंने एक उड़ान सिम्युलेटर बनाने की कोशिश की। 1980 के लेख में फ़्लाइट सिमुलेटर का उदाहरण फिर से दिया गया है। फुच, केडेम और नायलर लिखते हैं कि बीएसपी का पेड़ एक उड़ान सिम्युलेटर में उपयोगी हो सकता है जो पायलट एक ही हवाई अड्डे पर कई लैंडिंग बनाने के लिए उपयोग करते हैं। चूंकि हवाई अड्डे की ज्यामिति कभी नहीं बदलती है, बसपा का पेड़ केवल एक बार उत्पन्न हो सकता है। जाहिर है, वे वास्तविक समय सिमुलेशन के बारे में सोच रहे थे। लेख के परिचय में, वे 1/30 सेकंड से अधिक में छवियों को बनाने के लिए एक वास्तविक समय ग्राफिक प्रणाली का उपयोग करने की संभावना का परीक्षण करके अपने शोध की व्याख्या भी करते हैं।

यही है, वास्तविक समय ग्राफिकल सिमुलेशन में बीएसपी पेड़ों का उपयोग करने के बारे में सोचने के लिए कार्मैक पहले नहीं था। बेशक, यह अनुमान लगाने के लिए कि बीएसपी के पेड़ इस तरह से इस्तेमाल किए जा सकते हैं, और इसे लागू करने के लिए पूरी तरह से अलग चीजें हैं। लेकिन कार्यान्वयन के साथ भी, कार्मैक की पृष्ठभूमि की जानकारी अधिक हो सकती है, जो आमतौर पर सोचा जाता है। बसपा के पेड़ों पर विकिपीडिया लेख माना जाता है कि 1990 में केरमेक लेख 1991 चेन और गॉर्डन, साथ ही एक पाठ्यपुस्तक में बदल गया कंप्यूटर ग्राफिक्स: सिद्धांत और व्यवहार । हालांकि यह कथन एक उद्धरण द्वारा समर्थित नहीं है, यह सच हो सकता है। चेन और गॉर्डन के 1991 के एक लेख में बीएसपी पेड़ों का उपयोग करते हुए फ्रंट-टू-बैक रेंडर का वर्णन किया गया है, जो अनिवार्य रूप से डूम द्वारा उपयोग किया जाने वाला एक ही समाधान है, "निहित z- बफर" डेटा संरचना तक, जो पड़ोसी के शीर्ष पर दूर के बहुभुज को खींचने की अनुमति नहीं देता है। लेख बीएसपी पेड़ों का एक उत्कृष्ट अवलोकन प्रदान करता है, साथ ही एक पेड़ बनाने और प्रदर्शित करने के लिए छद्मकोड भी। (मेरे विश्वविद्यालय के अद्भुत पुस्तकालय के लिए धन्यवाद, मैं 1990 संस्करण के माध्यम से स्क्रॉल करने में सक्षम था।) कंप्यूटर ग्राफिक्स: सिद्धांत और अभ्यास पाठ्यपुस्तक कंप्यूटर ग्राफिक्स पर एक क्लासिक काम है, इसलिए कार्मैक भी एक हो सकता है।


सबस्क्राइबर-स्तर E1M1: हैंगर।

जैसा कि यह हो सकता है, कार्मैक ने एक नए कार्य का सामना किया - "मैं एक प्रथम-व्यक्ति शूटर कैसे बना सकता हूं जो कंप्यूटर पर एक प्रोसेसर के साथ चलता है जो फ्लोटिंग पॉइंट ऑपरेशन करने में भी सक्षम नहीं है?" - अपने स्वयं के शोध का संचालन किया, और साबित किया कि बीएसपी के पेड़ हैं? यह वास्तविक समय के वीडियो गेम के लिए एक उपयोगी डेटा संरचना है। मुझे अभी भी लगता है कि यह एक प्रभावशाली परिणाम है, भले ही बीएसपी के पेड़ का आविष्कार दस साल पहले किया गया था, और जब तक कार्मैक ने इसके बारे में पढ़ा तब तक सैद्धांतिक रूप से पर्याप्त विस्तार से अध्ययन किया गया है। शायद मुख्य उपलब्धि जिसकी हमें प्रशंसा करनी चाहिए, वह है समग्र रूप से डूम इंजन , जो कोड का एक बेहतरीन उदाहरण बन गया है। मैं पहले भी इस बारे में एक बार बात कर चुका हूं, लेकिन मैं इस बात को दोहराता हूं कि गेम इंजन के बारे में फैबियन संगलर की किताबकयामत ( गेम इंजन ब्लैक बुक: डीओओएम ) गेम इंजन के सभी विचारशील घटकों और उनके इंटरैक्शन का एक उत्कृष्ट अवलोकन है। हमें यह नहीं भूलना चाहिए कि वीएसडी कार्य केवल कई कार्यों में से एक था जिसे कारमैक को काम करने के लिए डूम इंजन के लिए हल करना था । और वह सक्षम था, सब कुछ के अलावा, अधिकांश प्रोग्रामर के लिए अज्ञात जटिल डेटा संरचना के बारे में पढ़ने के लिए, और इसे लागू करने के लिए। यह उनके तकनीकी ज्ञान के स्तर और आदर्श के प्रति प्रतिबद्धता के बारे में बहुत कुछ कहता है।