DIY voxel ग्राफिक्स - पहले चरण

पेश है वोक्सल ग्राफिक्स

GameDev वेबसाइट पर टकराव की गणना एल्गोरिदम की खोज की प्रक्रिया में, मैं idTech 6 इंजन के बारे में एक छोटा सा लेख भर आया और वोक्सल ग्राफिक्स में रुचि रखने लगा, जो कि बहुभुज ग्राफिक्स के साथ विपरीत हैं, जिस पर लगभग सभी कंप्यूटर ग्राफिक्स अब आधारित हैं।
सामान्य तौर पर, एक वॉक्सेल "वॉल्यूमेट्रिक पिक्सेल" के लिए खड़ा होता है, लेकिन अब एक वॉक्सल मूल रूप से एक आदिम है, सबसे अधिक बार एक क्यूब या आयताकार बॉक्स होता है, जिसमें एक निश्चित आकार और रंग होता है। IdTech 6 में और केन सिल्वरमैन वोक्सलैप इंजन में, वे एक विरल वोक्सल ऑक्ट्री (SVO) में संग्रहित होते हैं, जो मेमोरी को बचाता है और "विस्तार के स्तर" को लागू करना आसान बनाता है।

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

पहले प्रयास

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

आयतन में परिवर्तन

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

मेमोरी अनुकूलन

ऑक्ट्री में, अक्सर नए / हटाए गए ऑपरेटरों का उपयोग करना आवश्यक होता है, जो डायनेमिक मेमोरी (हीप) में पॉइंटर के लिए जगह आवंटित करते हैं। डायनेमिक मेमोरी स्टैटिक (स्टैक) की तुलना में धीमी है, और नए / डिलीट फंक्शंस खुद भी मेरे लिए बहुत धीमे थे। इस वजह से, हमारे अपने MemoryPool वर्ग और mem_pool_tree टेम्पलेट लिखे गए थे।
mem_pool_tree एक BST ट्री की छाप के तहत लिखा गया था, जो मुझे T. Corman की पुस्तक "Algorithms। बिल्डिंग एंड एनालिसिस" से मिला था, और यह सीधे मेमोरी के साथ काम नहीं करता है, लेकिन केवल संख्याओं के साथ काम करता है, जो बाद में सरणी की शुरुआत से पॉइंटर को शिफ्ट करने के लिए उपयोग किया जाता है। स्थिर स्मृति क्षेत्र। विलोपन की भविष्यवाणी करना संभव नहीं था, लेकिन स्मृति के "सही" टुकड़ों का चयन करना वास्तविक था, यही कारण है कि मैंने बीएसएस के पेड़ से विचार और मोड़ लिया और "अवरुद्ध" जोड़ दिया - मेम_पुल_ट्री स्टोर नोड्स जिसमें ब्लॉक की शुरुआत और अंत में स्टोर होता है। और दो और चर - कब्जे वाले स्थान की शुरुआत और अंत। यदि कब्जे वाली जगह के बीच में एक टुकड़े को हटाने का प्रयास किया जाता है, तो नोड को विभाजित किया जाता है, यदि किसी टुकड़े को चुनने के लिए फ़ंक्शन को कहा जाता है, तो एल्गोरिथ्म ऐसे ब्लॉक की खोज करता है जहां अंतरिक्ष का आवंटन इसे पड़ोसी ब्लॉक के साथ विलय करने की अनुमति देगा। और संतुलन समारोह को समय-समय पर कहा जाता है।

बहु सूत्रण

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

class Octree { class Node { Node * son; void Optimize(); }; void Optimize() { #pragma omp parallel { #pragma omp for for(int n = 0; n<8; ++n) { son[n].Optimize(); } } } }; 

चूंकि बच्चे के नोड्स किसी भी तरह से आपस में जुड़े हुए नहीं हैं, ऐसे ऑपरेशन में म्यूटेक्स की आवश्यकता नहीं होती है, जो उन स्थितियों में बहुत अच्छा होता है जब न्यूनतम स्मृति लागत की आवश्यकता होती है।

लोड हो रहा है और स्वर की बचत

एक लंबे समय के लिए मुझे एक फ़ाइल में स्वरों के भंडारण की इष्टतम विधि तलाशनी थी - क्योंकि ऐसी परिस्थितियों में जब रैम मूल्यवान है, रैम में अतिरिक्त स्वरों को संग्रहीत करना एक अस्वीकार्य लक्जरी है। बहुत खोज के बाद, पसंद SQLite3 था, जिसमें कैशिंग है, साथ ही केवल उन स्वरों को डाउनलोड करने की क्षमता है जो "विस्तार के स्तर" के मूल्यों के आधार पर आवश्यक हैं। SQLite3 डेटाबेस के साथ सबसे तेज़ काम प्रोजेक्ट और आत्म-संकलन में sqlite3 स्रोत कोड एम्बेड करते समय हुआ (मुझे सटीक संख्या याद नहीं है, लेकिन 200-250 एमएस के लिए आधा मिलियन चर और इंटेल एटम के साथ नेटबुक पर कुछ ऐसा है)। स्वाभाविक रूप से, SQLite3 "शुरुआती लेनदेन?", "प्रतिबद्ध लेन-देन;", "PRAGMA journal_mode = MEMORY;", "PRAGMA सिंक्रोनस = ऑफ़;" आदि

स्क्रीनशॉट

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

वर्तमान चुनौतियां और निष्कर्ष

बहुरूपता

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

RayCasting

ऑक्ट्री ट्री रे कास्टिंग , "कास्टिंग किरणों" एल्गोरिथ्म की अनुमति देता है जिसके साथ मैं अब एक रैस्टराइज़र लिख रहा हूं। इसके अलावा, एल्गोरिथ्म के कार्यान्वयन का उपयोग ओपनजीएल द्वारा किया जाता है (सरणी से बनावट पीढ़ी और बहुभुज पर इसका प्रदर्शन), "समूह अनुरेखण" और सी ++ एएमपी । सामान्य तौर पर, इस विषय को अच्छी तरह से r-tracing.ru पर बताया जाता है ।

निष्कर्ष

सामान्य तौर पर, विषय दिलचस्प है, और आप इस पर बहुत सारी दिलचस्प चीजें पा सकते हैं। उदाहरण के लिए: एटमॉन्टेज इंजन के बारे में हब पर एक लेख और एसआईजीआरएपीएच 2012 के साथ एसवीओ तकनीक की प्रस्तुति ।

युपीडी

स्मृति आबंटन वर्ग जिसे मैंने स्थिर मेमोरी में एक सरणी का उपयोग करके लिखा था, माप के बाद, निम्नलिखित डेटा का उत्पादन किया:

• 100 बाइट्स की 20 मिलियन वस्तुओं को हटाना (कुल मिलाकर, यह सब 220 एमबी से अधिक हो गया) 2-3 सेकंड लगे (बेशक, वस्तुओं को यादृच्छिक रूप से हटा दिया गया था)
• मैंने स्मृति के आवंटन को मापने में एक लंबा समय बिताया, लेकिन अंतिम परिणाम 4-5 सेकंड में 8 बाइट्स के 50 मिलियन ऑब्जेक्ट प्रतीत हुए
• पढ़ना तेज है, क्योंकि स्टैक मेमोरी ढेर मेमोरी से तेज है, लेकिन अब मैं औसत गति अंतर जानने के लिए विभिन्न हार्डवेयर पर परीक्षण कर रहा हूं
• जब मैंने 50 मिलियन ऑब्जेक्ट्स के लिए डायनेमिक मेमोरी से सामान्य नए ऑपरेटर के साथ मेमोरी आवंटित करने की कोशिश की, तो प्रोग्राम ने मुझे अपवाद std :: bad_alloc फेंक दिया, और जब मैंने उन्हें प्रोसेस करने के लिए ट्राई-कैच लिखा, तो प्रोग्राम ने मेमोरी लोड कर दी ताकि कंप्यूटर पर लगभग सभी रनिंग एप्लिकेशन क्रैश हो गए ।