एक क्षेत्र के लिए 3 डी पिक्सल (voxels)

Question

आप एक एल्गोरिथ्म का उपयोग कर 3 डी अंतरिक्ष में एक क्षेत्र आकर्षित कर सकते हैं सुझाव दे सकते हैं का उपयोग कर ड्रा केवल बुनियादी plot(x,y,z) आदिम (जो एक एकल वॉक्सेल आकर्षित होता है)?

मैं Bresenham's circle algorithm को कुछ इसी तरह की उम्मीद थी, लेकिन 3 डी के बजाय 2 डी के लिए।

एफवाईआई, मैं एक हार्डवेयर प्रोजेक्ट पर काम कर रहा हूं जो कि एलईएस के 3-आयामी मैट्रिक्स का उपयोग करके कम-रेज 3 डी डिस्प्ले है, इसलिए मुझे वास्तव में केवल 2 डी प्रोजेक्शन (यानी सर्कल) नहीं, बल्कि एक क्षेत्र को आकर्षित करने की आवश्यकता है।

परियोजना बहुत ही इस के समान है:

... या कार्रवाई here में इसे देख।

• डंडे (त्रिज्या दिया) के वाई निर्देशांक की गणना (एक क्षेत्र मूल में केंद्रित के लिए, इन -r और +r होगा)
• :

  एक संभावना यह मैं मन में है यह है क्षेत्र को टुकड़ा करें: प्रत्येक क्षैतिज विमान p _i इन निर्देशांकों के बीच, क्षेत्र =>r _i के साथ विमान को छेड़छाड़ करके प्राप्त सर्कल के त्रिज्या की गणना करें।

• विमान p _मैं पर त्रिज्या r _मैं की वास्तविक वृत्त Bresenham के कलन विधि का उपयोग।

Fwiw, मैं एक .NET micro-framework microprocessor उपयोग कर रहा हूँ, इसलिए प्रोग्रामिंग सी # है, लेकिन मैं जवाब की जरूरत नहीं है सी # में किया जाना है।

Answer 1

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

इष्टतम, निश्चित से बहुत दूर। लेकिन दिखाए गए 8x8x8 ग्रिड पर, आपको प्रति ऑपरेशन 512 बार इस ऑपरेशन को करने की आवश्यकता होगी। यदि गोलाकार केंद्र ग्रिड पर है, और इसका त्रिज्या एक पूर्णांक है, तो आपको केवल पूर्णांक गणित की आवश्यकता है। डॉट उत्पाद 3 गुणा और 2 जोड़ता है। गुण धीमा हैं; मान लीजिए कि वे प्रत्येक 4 निर्देश लेते हैं। इसके अलावा आपको तुलना की आवश्यकता है। लोड और स्टोर्स में जोड़ें, मान लें कि प्रति वोक्सल में 20 निर्देश हैं। यह प्रति क्षेत्र 10240 निर्देश है।

16 मेगाहट्र्ज पर चलने वाला एक आर्डिनो प्रति सेकंड 1562 क्षेत्रों को धक्का दे सकता है। जब तक आप कई अन्य गणित और I/O नहीं कर रहे हैं, यह एल्गोरिदम पर्याप्त होना चाहिए।

Answer 2

मान लिया जाये कि आप पहले से ही एक साजिश समारोह है कि जैसे आप ने कहा:

public static void DrawSphere(double r, int lats, int longs) 
    { 
     int i, j; 
     for (i = 0; i <= lats; i++) 
     { 
      double lat0 = Math.PI * (-0.5 + (double)(i - 1)/lats); 
      double z0 = Math.Sin(lat0) * r; 
      double zr0 = Math.Cos(lat0) * r; 

      double lat1 = Math.PI * (-0.5 + (double)i/lats); 
      double z1 = Math.Sin(lat1) * r; 
      double zr1 = Math.Cos(lat1) * r; 

      for (j = 0; j <= longs; j++) 
      { 
       double lng = 2 * Math.PI * (double)(j - 1)/longs; 
       double x = Math.Cos(lng); 
       double y = Math.Sin(lng); 

       plot(x * zr0, y * zr0, z0); 
       plot(x * zr1, y * zr1, z1); 
      } 
     } 
    } 

कि समारोह निर्दिष्ट अक्षांश और देशांतर संकल्प के साथ मूल में एक क्षेत्र साजिश चाहिए (अपने घन द्वारा पहचानने आप शायद कुछ चारों ओर चाहते हैं 40 या एक मोटा अनुमान के रूप में 50)। यह एल्गोरिदम हालांकि क्षेत्र को "भरने" नहीं देता है, इसलिए यह केवल एक रूपरेखा प्रदान करेगा, लेकिन त्रिज्या के साथ खेलना आपको अंतराल को भरने देना चाहिए, संभवत: लेट्स और लम्बे समय के साथ संकल्प को कम करना।

Answer 3

बस एक क्षेत्र मेष पैदा करने के बारे में एक पुरानी क्ष & एक पाया है, लेकिन शीर्ष जवाब वास्तव में आप अपने एक्स, वाई और जेड उत्पन्न करने के लिए छद्म कोड के एक छोटे टुकड़े देता है:

(x, y, z) = (sin(Pi * m/M) cos(2Pi * n/N), sin(Pi * m/M) sin(2Pi * n/N), cos(Pi * m/M))

चेक इस क्यू & एक के लिए विवरण :) procedurally generate a sphere mesh

Answer 4

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

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

• y0 + y1 और y0 - y1 पर मानक चक्र एल्गोरिथ्म अंक ड्रा: x0 +/- x, z0 +/- z, y0 +/- y1, x0 +/- z, z0 +/- x, y0 +/- y1, कुल 16 अंक। यह गोलाकार के लंबवत का बड़ा रूप बनाता है।
• इसके अतिरिक्त अंक x0 +/- y1, z0 +/- x, y0 +/- z और x0 +/- x, z0 +/- y1, y0 +/- z, कुल 16 अंक, जो क्षेत्र के लिए ध्रुवीय कैप्स बनाएंगे।

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

---

निम्नलिखित कोड विकिपीडिया के Midpoint circle algorithm से संशोधित किया गया है। DrawCircle एल्गोरिदम में xz-plane में संचालित करने के लिए नामकरण बदल गया है, तीसरा प्रारंभिक बिंदु y0, वाई ऑफसेट y1, और प्रारंभिक त्रुटि error0 के अतिरिक्त। DrawSphere तीसरे प्रारंभिक बिंदु y0 लेने के लिए एक ही समारोह से संशोधित और कॉल DrawCircle बल्कि DrawPixel

public static void DrawCircle(int x0, int y0, int z0, int y1, int radius, int error0) 
{ 
    int x = radius, z = 0; 
    int radiusError = error0; // Initial error state passed in, NOT 1-x 

    while(x >= z) 
    { 
    // draw the 32 points here. 
    z++; 
    if(radiusError<0) 
    { 
     radiusError+=2*z+1; 
    } 
    else 
    { 
     x--; 
     radiusError+=2*(z-x+1); 
    } 
    } 
} 

public static void DrawSphere(int x0, int y0, int z0, int radius) 
{ 
    int x = radius, y = 0; 
    int radiusError = 1-x; 

    while(x >= y) 
    { 
    // pass in base point (x0,y0,z0), this algorithm's y as y1, 
    // this algorithm's x as the radius, and pass along radius error. 
    DrawCircle(x0, y0, z0, y, x, radiusError); 
    y++; 
    if(radiusError<0) 
    { 
     radiusError+=2*y+1; 
    } 
    else 
    { 
     x--; 
     radiusError+=2*(y-x+1); 
    } 
    } 
} 

---

त्रिज्या 4 (जो वास्तव में 9x9x9 की आवश्यकता है) के एक क्षेत्र के लिए की तुलना में, इस के तीन पुनरावृत्तियों चल पाएंगे था DrawCircle दिनचर्या, पहली बार एक सामान्य त्रिज्या 4 सर्कल (तीन चरणों) को चित्रित करने के साथ, दूसरा त्रिज्या 4 सर्कल को 0 की प्रारंभिक त्रुटि (तीन चरणों) के साथ चित्रित करता है, और फिर तीसरा ड्राइंग त्रिज्या 3 सर्कल प्रारंभिक त्रुटि 0 के साथ (भी तीन कदम)। यह 9 गणना अंकों के साथ समाप्त होता है, प्रत्येक 32 पिक्सल ड्राइंग करता है। जो 32 (प्रति सर्कल अंक) x 3 बनाता है (प्रति बिंदु संचालन जोड़ें या घटाएं) + 6 (प्रतिवर्तन, घटाना, प्रति पुनरावृत्ति प्रति संचालन) = 102 प्रति गणना बिंदु को जोड़ना, घटाना या स्थानांतरित करना। इस उदाहरण में, प्रत्येक सर्कल = 306 संचालन प्रति परत के लिए यह 3 अंक है।त्रिज्या एल्गोरिदम भी प्रति परत 6 ऑपरेशंस जोड़ता है और 3 बार पुनरावृत्त करता है, इसलिए 306 + 6 * 3 = 936 4.के उदाहरण त्रिज्या के लिए मूल अंकगणितीय परिचालन। यहां लागत यह है कि आप अतिरिक्त स्थिति जांच के बिना बार-बार कुछ पिक्सल सेट करेंगे (यानी x = 0, y = 0, या z = 0), इसलिए यदि आपका I/O धीमा है तो आप स्थिति जांच जोड़ने से बेहतर हो सकते हैं। मानते हैं कि सभी एल ई डी शुरू होने पर मंजूरी दे दी गई थी, उदाहरण सर्कल 288 एल ई डी सेट करेगा, जबकि कई कम एल ई डी हैं जो दोहराने वाले सेटों के कारण वास्तव में जलाए जाएंगे।

ऐसा लगता है कि यह 8x8x8 ग्रिड में फिट होने वाले सभी क्षेत्रों के लिए ब्रूटफोर्स विधि से बेहतर प्रदर्शन करेगा, लेकिन ब्रूटफोर्स विधि में त्रिज्या के बावजूद लगातार समय होगा, जबकि यह विधि बड़े त्रिज्या के क्षेत्र को चित्रित करते समय धीमा हो जाएगी केवल एक हिस्सा प्रदर्शित किया जाएगा। चूंकि डिस्प्ले क्यूब रिज़ॉल्यूशन में बढ़ता है, हालांकि, यह एल्गोरिदम समय लगातार रहेगा जबकि ब्रूटफोर्स बढ़ेगा।