🉐 👩🏿‍✈️ 🎅🏿 गामेदेव में मठ सरल है। एकता में त्रिकोणासन और त्रिभुज.नेट 📴 🎫 🐎

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

त्रिकोणासन क्या है?

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

त्रिकोणासन अलग-अलग हैं, लेकिन सबसे लोकप्रिय प्रकार के त्रिभुजों में से एक है डेलुनाय त्रिभुज। इस प्रकार के त्रिकोणासन को उस गुण द्वारा प्रतिष्ठित किया जाता है, जो प्रत्येक त्रिभुज के चारों ओर परिधि में होता है, इस त्रिभुज के केवल कोने ही होते हैं।

उनकी आवश्यकता क्यों है?

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

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

इसके अलावा, विवश Delaunay triangulation और Chew के दूसरे एल्गोरिथ्म और Ruppert के एल्गोरिथ्म जैसे एल्गोरिदम का उपयोग करके, आप tirrains के लिए और भी बेहतर मेष उत्पन्न कर सकते हैं और एक और अनुप्रयोग के लिए अच्छा meshes उत्पन्न कर सकते हैं - परिमित विधि विधि।

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

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

Gamedev triangulations के अलावा नेटवर्क, कंप्यूटर विज़न, विभिन्न विश्लेषणात्मक एल्गोरिदम, साथ ही कम्प्यूटेशनल ज्यामिति की क्या समस्याएं हैं, जैसे कि एक दूसरे से बहुभुज का संयोजन और उन्मूलन (जो कि अक्सर खेलों के विकास में उत्पन्न होने वाली समस्याओं में उपयोगी होता है) में उपयोग किया जाता है।

होल्स के साथ कान की कतरन

शायद सरल त्रिभुज एल्गोरिदम में से एक। यह सबसे अच्छा ग्रिड नहीं देता है और सबसे खराब कम्प्यूटेशनल जटिलता ओ (एन ^ 2) सबसे खराब स्थिति में है।

आप इस लेख में इसके बारे में अधिक पढ़ सकते हैं।

बाउयर - वाटसन एल्गोरिथम

एक एल्गोरिथ्म जो अंकों के एक सेट पर Delaunay त्रिभुज उत्पन्न करता है। सामान्य तौर पर, अधिकांश डेलॉनाय एल्गोरिदम के साथ, यदि सही तरीके से लागू किया जाता है, तो एल्गोरिथम जटिलता ओ (एन लॉग एन) है, जहां एन कोने की संख्या है। लेकिन कुछ मामलों में यह O (n ^ 2) लग सकता है।

कान कतरन के बारे में नुकसान यह है कि यह एल्गोरिथ्म उत्तल त्रिकोणीय बनाता है और बुनियादी कार्यान्वयन में परिणामी ग्रिड में छेद शामिल नहीं करता है।

Delaunay परिशोधन प्रसंस्करण

च्यू का दूसरा एल्गोरिथ्म और रूपर्ट का एल्गोरिदम एल्गोरिदम है जो आपको डेलौना त्रिकोण में बाधाओं को दर्ज करने और ग्रिड में त्रिकोण के न्यूनतम कोण को सेट करने की अनुमति देता है। एल्गोरिदम का एक महत्वपूर्ण विवरण यह है कि वे एक अनंत लूप में जा सकते हैं और लगभग 20.7 डिग्री और 29 डिग्री के बीच के कोणों पर परिणाम देने की गारंटी है। ऊपर वर्णित समस्याओं को हल करने में न्यूनतम कोण सेट करने की क्षमता महत्वपूर्ण है।

Chew का दूसरा एल्गोरिथ्म नि: शुल्क पैकेज www.cs.cmu.edu/~quake/triangle.html और इसके पोर्ट .Net संग्रह . codeplex.com/?p=triangle पर लागू किया गया है

एकता के लिए Triangle.Net

खैर, चूंकि त्रिकोणासन की मदद से आप इतने शांत कार्यों को हल कर सकते हैं, छुट्टियों में मैं एकता के लिए अपने आवरण को लागू करना चाहता था, ताकि मेरे पास हमेशा एक आसान उपकरण हो। इस कार्यान्वयन में, त्रिकोणीय एल्गोरिथ्म ओ (एन) के लिए औसतन काम करता है, और ओ (एन * लॉग एन) के लिए सबसे खराब स्थिति में, जहां एन कोने की संख्या है। उदाहरण के लिए, जब एक वर्ग में 1kk बेतरतीब ढंग से बिखरे हुए परीक्षण के लिए, इंटेल कोर i7-8700 पर संपादक की इकाइयों ने औसतन 7.56 सेकंड में एक ग्रिड का निर्माण किया।

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

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

उदाहरण का उपयोग करें

public void GenerateMesh() { if(_CurrentState != MeshDrawerState.Nothing) return; Polygon poly = new Polygon(); poly.Add(_Contour); foreach (var hole in _Holes) { poly.Add(hole, true); } var triangleNetMesh = (TriangleNetMesh) poly.Triangulate(); GameObject go = new GameObject("Generated mesh"); var mf = go.AddComponent<MeshFilter>(); var mesh = triangleNetMesh.GenerateUnityMesh(); mesh.uv = GenerateUv(mesh.vertices); mf.mesh = mesh; var mr = go.AddComponent<MeshRenderer>(); mr.sharedMaterial = _MeshMaterial; var collider = go.AddComponent<PolygonCollider2D>(); collider.points = _Contour.ToArray(); var rb = go.AddComponent<Rigidbody2D>(); rb.mass = triangleNetMesh.Triangles.Sum(tris => tris.Area); Clear(); }

प्रदर्शन और उपयोग के उदाहरण के लिए, मेश खींचने की क्षमता के साथ एक विशेष डेमो दृश्य बनाया गया था। आप इसके साथ परिचित हो सकते हैं और जीथब परियोजना में पुस्तकालय का बंदरगाह ।

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