🛢️ 🚵🏾 🚠 गार्डेन के विकर्णों पर ब्रेसेनहम और यू 🥁 ✍️ 👨🏻‍🚀

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

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

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

यह एल्गोरिथ्म का सार था, वास्तव में, सब कुछ इस प्रकार दिखता है। सबसे पहले, कोणीय गुणांक (y1 - y0) / (X1 - x0) की गणना की जाती है। खंड (0,0) के शुरुआती बिंदु पर त्रुटि मान शून्य के बराबर लिया जाता है और पहला सेल भरा जाता है। अगले चरण में, कोणीय गुणांक को त्रुटि में जोड़ा जाता है और इसके मूल्य का विश्लेषण किया जाता है, यदि त्रुटि 0.5 से कम है, तो सेल (x0 + 1, 0) भरा है, यदि अधिक है, तो सेल (x0 + 1, 0 + 1) भर जाता है और इकाई को त्रुटि मान से घटा दिया जाता है । नीचे दी गई तस्वीर में, रेखांकन से पहले की रेखा को पीले, हरे और लाल रंग में दिखाया गया है - निकटतम कोशिकाओं की दूरी। कोणीय गुणांक एक छठे के बराबर है, पहले चरण में, त्रुटि कोणीय गुणांक के बराबर हो जाती है, जो 0.5 से कम है, जिसका अर्थ है कि समन्वय समान रहता है। रेखा के मध्य तक, त्रुटि सीमा पार करती है, एक इकाई को इससे घटाया जाता है, और नया पिक्सेल ऊपर उठता है। और इसलिए खंड के अंत तक।

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

गणनाओं को अनुकूलित करने के लिए, dx = (X1 - x0) द्वारा सभी भिन्न चर के गुणन के साथ एक चाल लागू की जाती है। फिर, प्रत्येक चरण पर, त्रुटि को = (y1 - y0) द्वारा कोणीय गुणांक के बजाय और एकता के बजाय dx द्वारा बदल दिया जाएगा। आप तर्क को थोड़ा बदल सकते हैं, त्रुटि को "स्थानांतरित" कर सकते हैं ताकि सीमा शून्य पर हो, और आप त्रुटि संकेत की जांच कर सकते हैं, यह तेज हो सकता है।

कुछ इस तरह से Bresenham कलन विधि का उपयोग कर रेखापुंज रेखा खींचने के लिए कोड की तरह लग सकता है। सी # के तहत विकिपीडिया से छद्म कोड से छद्म कोड।

void BresenhamLine(int x0, int y0, int x1, int y1) { var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); //           //    ,      if (steep) { Swap(ref x0, ref y0); //         Swap(ref x1, ref y1); } //      ,        if (x0 > x1) { Swap(ref x0, ref x1); Swap(ref y0, ref y1); } int dx = x1 - x0; int dy = Math.Abs(y1 - y0); int error = dx / 2; //       dx,      int ystep = (y0 < y1) ? 1 : -1; //     y int y = y0; for (int x = x0; x <= x1; x++) { DrawPoint(steep ? y : x, steep ? x : y); //       error -= dy; if (error < 0) { y += ystep; error += dx; } } }

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

C # में सैंपल सर्कल ड्राइंग कोड।

 void BresenhamCircle(int x0, int y0, int radius) { int x = radius; int y = 0; int radiusError = 1 - x; while (x >= y) { DrawPoint(x + x0, y + y0); DrawPoint(y + x0, x + y0); DrawPoint(-x + x0, y + y0); DrawPoint(-y + x0, x + y0); DrawPoint(-x + x0, -y + y0); DrawPoint(-y + x0, -x + y0); DrawPoint(x + x0, -y + y0); DrawPoint(y + x0, -x + y0); y++; if (radiusError < 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }

अब, चिकनी लाइनों को खींचने के लिए वू ज़ियाओलिन के एल्गोरिथ्म के बारे में। यह इस बात में भिन्न है कि प्रत्येक चरण में एक गणना रेखा के निकटतम दो पिक्सेल के लिए की जाती है, और उन्हें दूरी के आधार पर, विभिन्न तीव्रता के साथ चित्रित किया जाता है। पिक्सेल के मध्य का सटीक चौराहा 100% तीव्रता देता है, यदि पिक्सेल 0.9 पिक्सेल की दूरी पर है, तो तीव्रता 10% होगी। दूसरे शब्दों में, एक सौ प्रतिशत तीव्रता को पिक्सेल के बीच विभाजित किया जाता है जो दोनों तरफ वेक्टर रेखा को सीमाबद्ध करता है।

ऊपर की छवि में, दो आसन्न पिक्सेल की दूरी को लाल और हरे रंग में दिखाया गया है।

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

C # में वू शियाओलिन द्वारा स्मूद लाइन का उदाहरण कोड।

 private void WuLine(int x0, int y0, int x1, int y1) { var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (steep) { Swap(ref x0, ref y0); Swap(ref x1, ref y1); } if (x0 > x1) { Swap(ref x0, ref x1); Swap(ref y0, ref y1); } DrawPoint(steep, x0, y0, 1); //           steep DrawPoint(steep, x1, y1, 1); //   —     float dx = x1 - x0; float dy = y1 - y0; float gradient = dy / dx; float y = y0 + gradient; for (var x = x0 + 1; x <= x1 - 1; x++) { DrawPoint(steep, x, (int)y, 1 - (y - (int)y)); DrawPoint(steep, x, (int)y + 1, y - (int)y); y += gradient; } }

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

एकता वेब प्लेयर | विंडोज | लिनक्स | मैक | गिटहब स्रोत
बाएं माउस बटन - ब्रेसेनहम, राइट माउस बटन - Y, स्पेसबार - स्पष्ट, Esc - बाहर निकलें।
Linux उपयोगकर्ताओं के लिए: BresenhamWu फ़ाइल को "chmod + x BresenhamWu" के साथ निष्पादन योग्य बनाएं और इसे चलाएं।

रोसेटा कोड में ब्रेसेनहैम एल्गोरिथ्म और यू एल्गोरिथ्म के लिए विभिन्न भाषाओं में कोड है। वू ज़ियाओलिन के लेख का लिंक

गार्डेन के विकर्णों पर ब्रेसेनहम और यू

More articles: