इनसाइड क्वैक: ऑलवेज ऑल्टरनेटिव्स

प्रोग्रामर माइकल अब्रश, जिन्हें 90 के दशक के मध्य में पहले क्वेक के इंजन पर काम करने के लिए जॉन कार्मैक द्वारा आमंत्रित किया गया था, ने विकास प्रक्रिया के दौरान कई लेख लिखे। यह इस श्रृंखला का दूसरा स्तंभ है। पहले का अनुवाद यहाँ है ।

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

मैं यह सब इस तरह से बताता हूं क्योंकि जब मेरी बेटी और मैंने एक शाम कैफे से बाहर निकाल दिया, तो रेडियो स्टेशन "कोई विकल्प नहीं है" कार में पहली बार चालू किया गया था।

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

लेकिन यहाँ मुझे आश्चर्य हुआ: थोड़ी देर सुनने के बाद, उसने कहा: "आप जानते हैं, पिताजी, लेकिन यह वास्तव में दिलचस्प है।"

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

लेकिन क्वेक की बदलती प्रकृति को देखते हुए, मुझे वास्तव में इस तरह के अनुस्मारक की आवश्यकता नहीं होनी चाहिए।

रचनात्मक धारा

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

चलती हुई वस्तुओं को खींचना

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

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

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

उत्पादकता को समतल करना और बढ़ाना

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

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

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

और वह वास्तव में पाया गया था।

क्रमबद्ध अंतराल

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

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



इंटरवल जनरेशन

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

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

पसलियों बनाम अंतराल

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

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



चित्र 2: चित्र 1 से बहुभुज A के अंतरालों को हल किया जाता है और बहुभुज B से अंतराल द्वारा अलग किया जाता है, जबकि बहुभुज A Z अक्ष के साथ 100 की निरंतर दूरी पर होता है, और बहुभुज B Z के साथ 50 की निरंतर दूरी पर होता है (बहुभुज B कैमरे के करीब होता है। )।

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

प्रत्येक रेखापुंज रेखा के लिए, z द्वारा क्रमबद्ध एक सक्रिय बहुभुज सूची (APL) संग्रहीत की जाती है। यह x AEL द्वारा क्रमबद्ध क्रम में जाता है। प्रत्येक नए किनारे के साथ मिलने पर (यानी, जब प्रत्येक बहुभुज शुरू होता है या बाएं से दाएं चलते समय समाप्त होता है), इसके साथ जुड़ा बहुभुज सक्रिय होता है और एपीएल (एक प्रारंभिक छोर के मामले में) में क्रमबद्ध होता है, जैसा कि चित्र 3 में दिखाया गया है, या एपीएल (या से हटा दिया गया है और हटा दिया गया है) अनुगामी किनारे के मामले में), जैसा कि चित्र 4 में दिखाया गया है। यदि निकटतम बहुभुज बदल गया है (जो कि निकटतम एक नया बहुभुज है या निकटतम बहुभुज समाप्त हो गया है), बहुभुज के लिए जो अभी निकटतम है, समाप्त हो गया है, उस बिंदु से शुरू होने वाला अंतराल बनाया जाता है जहां बहुभुज नहीं होता है vym क्योंकि यह सबसे करीब और समाप्त होने के एक्स वर्तमान किनारों और वर्तमान का समन्वय है x- निर्देशांक लैंडफिल, जो अब करीब है में दर्ज की गई है। यह संग्रहीत समन्वय बाद में बनाए गए अंतराल की शुरुआत के रूप में उपयोग किया जाता है जब नया निकटतम बहुभुज सामने होना बंद हो जाता है।



चित्र 3: एईएल में एक शुरुआती बढ़त का पता चलने पर बहुभुज सक्रियण।



चित्र 4: एईईएल में एक अनुगामी किनारे का पता चलने पर बहुभुज निष्क्रिय हो जाता है।

यदि आप ऊपर पूरी तरह से नहीं समझते हैं, तो चिंता न करें; यह किनारों को छांटने का एक त्वरित अवलोकन है, ताकि बाकी कॉलम स्पष्ट हो। विस्तृत विवरण अगले कॉलम में होगा।

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

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

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

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

रिब सॉर्ट कुंजी

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

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

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

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

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

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

बेहतर होगा कि प्लेन के समीकरण से 1 / z और हमारे लिए पिक्सेल के स्क्रीन x और y की गणना करें। समीकरण का निम्न रूप है:

$$

$$1/z = (a/d)x' - (b/d)y' + c/d$$

जहाँ z स्क्रीन के निर्देशांक (x ', y') में प्रक्षेपित होने वाले समतल पर बिंदु के z- स्थान में समन्वय है (इन गणनाओं के लिए निर्देशांक की उत्पत्ति प्रक्षेपण केंद्र है, स्क्रीन बिंदु के ठीक सामने का बिंदु), [abc] है व्यूपोर्ट में प्लेन के लिए सामान्य है, और डी व्यूपोर्ट के मूल से प्लेन की सामान्य से दूरी है। प्रत्येक विमान के लिए केवल एक बार डिवीजन किया जाता है, क्योंकि ए, बी, सी और डी विमानों के लिए स्थिरांक हैं।

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

यदि आप रुचि रखते हैं, तो यहां 1 / z समीकरण का त्वरित व्युत्पन्न है। विमान के समतुल्य समीकरण के निम्नलिखित रूप हैं:

$$

$$ax + by + cz - d = 0$$

जहाँ x और y दृश्य स्थान के निर्देशांक हैं, a, b, c, d, और z को ऊपर परिभाषित किया गया है। अगर हम प्रतिस्थापन करते हैं$$$x=x'z$ और $$$y=-y'z$(परिप्रेक्ष्य प्रक्षेपण की परिभाषा से; वाई संकेत को बदलता है क्योंकि यह व्यूपोर्ट में बढ़ता है, लेकिन स्क्रीन स्पेस में नीचे)। क्रमपरिवर्तन करते हुए, हम प्राप्त करते हैं:

$$

$$z = d / (ax' - by' + c)$$

समीकरण प्राप्त करना और उसका विस्तार करना, हम प्राप्त करते हैं:

$$

$$1/z = ax'/d - by'/d + c/d$$

बाद में मैं एक्शन में 1 / z सॉर्टिंग दिखाऊंगा।

Qu और z द्वारा सॉर्ट करें

मैंने ऊपर उल्लेख किया है कि Quake अब बीएसपी ऑर्डर को एक सॉर्ट कुंजी के रूप में उपयोग नहीं करता है; वास्तव में, 1 / z अब कुंजी के रूप में लागू किया गया है। ढ़ाल के लालित्य के बावजूद, उनमें से 1 / z की गणना स्पष्ट रूप से बसपा आदेश कुंजी की तुलना में धीमी है, इसलिए हमने क्वेक में 1 / z का उपयोग करने के लिए स्विच क्यों किया?

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

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

चल रहा है

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

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