इनसाइड क्वैक: डिफाइनिंग विज़िबल सर्फर्स

तीन-आयामी ग्राफिक्स प्रोग्रामिंग अनुभवी माइकल अब्रैश, पहले क्वेक के विकास के उदाहरण का उपयोग करते हुए, प्रोग्रामिंग में रचनात्मक सोच की आवश्यकता के बारे में बात करते हैं।

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

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

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

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

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

समस्या, निश्चित रूप से, सीमाओं को कैसे दूर किया जाए, इसका अस्तित्व आप भी नहीं जानते हैं। सफलता के लिए कोई सूत्र नहीं है, लेकिन दो सिद्धांत इस उद्देश्य को अच्छी तरह से पूरा कर सकते हैं: पहला, सरल, दूसरा, लगातार कुछ नया करने की कोशिश करना।

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

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

अच्छा चित्रण: क्वेक 3 डी ग्राफिक्स इंजन का विकास।

दुनिया का सबसे जटिल 3 डी ग्राफिक्स कार्य

मैंने पिछले सात महीनों को Quake पर काम करते हुए, id Software से DOOM का उत्तराधिकारी बिताया, और मुझे लगता है कि तीन महीने बाद, जब तक आप इस लेख को पढ़ेंगे, तब तक Quake को शेयरवेयर के रूप में जारी किया जाएगा।

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

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

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

स्तर की संरचना

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


चित्र 1. क्वेक में, बहुभुज खाली पत्तियों में जमा होते हैं। अंधेरे क्षेत्र पत्तियों से भरे हुए हैं (भरे हुए खंड, जैसे कि दीवारों के आवरण)

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

दृश्य सतहों को कतरना और परिभाषित करना

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


चित्रा 2. आदर्श वीएसडी वास्तुकला दृश्य बहुभुज के केवल दृश्य भागों का प्रतिपादन करता है।

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

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

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

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


चित्र 3: नोड ई एक अंधेरे उप-वर्ग का वर्णन करता है जिसमें 5, 6, 7 और नोड एफ होते हैं।

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

यही है, दृश्यता के पिरामिड के साथ क्लिपिंग एक समस्या नहीं है, और आप पिछड़े को आकर्षित करने के लिए बीएसपी का उपयोग कर सकते हैं। तो समस्या क्या है?

पुनः बनाने

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

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

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

मेरे आने के तीन महीने बाद, मूल VSD संरचना का केवल एक तत्व इंजन में रहा, और "नई चीज़ों को आज़माने" के लिए जॉन की इच्छा इतनी दूर चली गई कि मैंने ऐसा पहले कभी नहीं देखा था।

बंच का पेड़

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


चित्रा 4. क्वेक बीम का पेड़ स्क्रीन को एक 2 डी क्षेत्र में प्रभावी रूप से विभाजित करता है


चित्र 5. क्वेक बीम के पेड़ में 3 डी सेक्टर या बीम होते हैं, जो कि दृष्टिकोण से बहुभुज के किनारों तक अनुमानित होते हैं।

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

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

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

हर दिन नया 3 डी इंजन

बीम के पेड़ ने काम करना शुरू करने के बाद, जॉन ने 3 डी इंजन को तेज करने के लिए अथक परिश्रम किया, लगातार कार्यान्वयन में बदलाव करने के बजाय, इसकी संरचना में सुधार करने की कोशिश की। , , : « , ...», , . , , , . , . , . . , , , FIFO- Paradise .

raycast : , 8x8, ; , , BSP-, , . , , , , ; , , . , , . : , .

: . . ( ), .

: z-, , , . , , , , . : , 256 0-8 ; x86 8 .

: , , . , . , ; , .

: , , . , , , . , .

, — , , BSP- , BSP- . , DOOM (2D), BSP- DOOM 2D- . 3D , . BSP , , . , , BSP.

, , , - . BSP, , , . 3:30 , , , , , , , .

: (potentially visible set, PVS) . PVS 1 . . BSP , . , , , , . , BSP , , PVS 20 .

20 ( PVS), (PVS , , , 50%, 150%). , PVS ; , VSD, . , — , , , .

, PVS , , «» . , , , , , «» , .

-

इसका क्या मतलब है? , : - . PVS , ( PVS — , ). , PVS — . , ?

बिलकुल नहीं। , , . , , .

, , . : — , . , , «» . , « »; . VSD, , . , « » , ( , ) PVS .

— , , . , , . , 3D- , ; , , .

.

,

, . , Dr. Dobb's Journal , — . , Tiny C , D-Flat , - DDJ . ( , .) — , DDJ .

id Software , Quake . id Wolfenstein 3D ftp.idsoftware.com/idstuff/source [. .: github ] ; , , ; wolfsrc.txt , , .

: , . , , , , , . ; — , . , !

संदर्भ सामग्री

Foley, James D., et al. , Computer Graphics: Principles and Practice , Addison Wesley, 1990, ISBN 0-201-12110-7 (, BSP-, VSD).

Teller, Seth, Visibility Computations in Densely Occluded Polyhedral Environments (), http://theory.lcs.mit.edu/~seth/ .

Teller, Seth, Visibility Preprocessing for Interactive Walkthroughs , SIGGRAPH 91 proceedings, pp. 61-69.