ग्राफिक्स अनुकूलन। दिलचस्प अवतल हल

एक बिंदु पर, खेल के विकास के दौरान, मुझे आधुनिक पीसी पर प्रदर्शन के मुद्दे का सामना करना पड़ा। हमारे मॉडलर के पास काफी शक्तिशाली आधुनिक रेड असेंबली कंप्यूटर है। लेकिन हमारे पास हमारी परियोजना बहुत धीमी थी, एक प्रोसेसर कोर लोड हो रहा था।

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



औसत गेम मैप पर, अधिकतम दूरी के साथ और ताड़ के पेड़ों के एक बड़े समूह के साथ - 15 824 756 त्रिकोण! लगभग 16 मिलियन! एक बड़ी संख्या।

नक्शा जनरेटर के साथ थोड़ा खेलने के बाद, मैं 16.75 मिलियन के साथ एक जगह खोजने में कामयाब रहा:



हालांकि, यहां, क्रिसमस के पेड़ों के साथ एक समान स्थान ने केवल 8.5 मिलियन त्रिकोण दिए:



औसत दृश्य में ~ 4 मिलियन शामिल थे:



सामान्य तौर पर, मुझे खुशी थी कि मेरा रेंडर इतनी बड़ी संख्या में त्रिकोण का मुकाबला कर रहा था, लेकिन उनकी संख्या अत्यधिक थी। समाधान सतह पर था:

1. मॉडल में बहुभुज की संख्या का अनुकूलन करें।
2. परिदृश्य के बहुभुज जाल का अनुकूलन करें।
3. बहु-थ्रेडेड रेंडरिंग का कार्यान्वयन।

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

1. मॉडल में बहुभुज की संख्या का अनुकूलन

हमारे इंजन में, वनस्पति "पैक" में खींची गई है, पूरे परिदृश्य को टाइल और उप-टाइल में विभाजित किया गया है, न्यूनतम पैक एक उप-टाइल है।



एक पैक एक जाली है, क्योंकि मेष की संख्या को कम करने से सीपीयू-> जीपीयू कॉल की संख्या में काफी कमी आती है।



प्रारंभ में, हमारे पेड़ों में कांटेदार शंकु शामिल थे, जो पूर्ण शंकु पर जा रहे थे, हम कुछ अतिरिक्त तरंगों को हटाने में कामयाब रहे:



केक पर चेरी पेड़ों से चड्डी को हटाने का निर्णय था, क्योंकि हमारे कैमरा कोण के साथ वे बस दिखाई नहीं दे रहे थे।

नतीजतन, हम क्रिसमस के पेड़ों के एक पैक पर, 40% की औसत से, बहुभुज की संख्या को कम करने में कामयाब रहे। अंतर लगभग अदृश्य हैं:



ताड़ के पेड़ों के साथ यह अधिक कठिन था, लेकिन 5000 - 6000 बहुभुजों के पैक को ठीक करने की आवश्यकता थी। जंगल की गतिशीलता और घनत्व कैसे प्राप्त करें? ताड़ के पेड़ों की बड़ी संख्या के कारण जंगल का उच्च घनत्व प्राप्त किया गया था:



हमने हथेलियों को सरल बनाने और वनस्पति के एक दूसरे स्तर का परिचय देने का फैसला किया, जिससे हमें दृश्य घनत्व बनाए रखने और प्रति पैक वांछित 600 - 700 बहुभुज प्राप्त करने की अनुमति मिली।



बहुभुजों की संख्या को 10 गुना कम करना एक उत्कृष्ट परिणाम है।

2. बहुभुज जाल परिदृश्य का अनुकूलन

प्रारंभ में, परिदृश्य ग्रिड था:



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



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



दिए गए उदाहरण में, यह निकला: 1 सरणी के त्रिकोण जिन्हें बदला नहीं जा सकता है, क्योंकि वे सभी अलग-अलग ऊंचाइयों (लाल त्रिकोण) के थे और एक सूची जिसमें ऊंचाई के साथ त्रिकोण के दो सरणियों होते हैं (सरणियों को रंग से भरा जाता है)।

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

मैंने त्रिकोण के कोने के सेट से एक समोच्च बनाने की कोशिश की, अर्थात्। मैंने त्रिभुज के सरणी को लंबवत सरणी में अनुवादित किया और पहले से ही उन पर एक शेल बनाया। लेकिन मेरे कार्य के लिए यह आवश्यक नहीं था। मेरे निष्कर्ष के अनुसार, त्रिकोण से सीधे एक शेल बनाना आसान था, और अवतल पतवार की सटीकता 100% थी।

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

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







सब कुछ ठीक निकला:



लेकिन अंत में, मैं परिणाम से परेशान था। मैंने जो एल्गोरिथ्म विकसित किया है वह एक दृश्य को प्रस्तुत करते समय प्रदर्शन में एक ठोस वृद्धि देता है, क्योंकि औसतन बहुभुज की संख्या 60 - 70% कम हो गई थी। लेकिन एक ही समय में, कार्ड जेनरेशन 10 गुना धीमा होने लगा। एल्गोरिथ्म बहुत समय लेने वाला निकला।

परिदृश्य के बहुभुज जाल के अनुकूलन के लिए एल्गोरिथ्म के एक हल्के संस्करण पर विचार करने में तीन दिन लग गए, जिससे ये परिणाम मिले:



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

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