शिखर

Question

से आधा किनारे डेटा संरचना शुरू करना मैं विभिन्न उपविभाग एल्गोरिदम (जैसे कि catmull-clark) को लागू करने पर काम कर रहा हूं; ऐसा करने के लिए कुशलतापूर्वक tesselated बहुभुज के एक ग्रिड के बारे में जानकारी स्टोर करने के लिए एक अच्छा तरीका की आवश्यकता है। मैंने outlined by flipcode के रूप में आधा किनारा डेटा संरचना लागू की, लेकिन अब मुझे यकीन नहीं है कि डेटा संरचना को चरम से कैसे पॉप्युलेट करना है!

मेरे प्रारंभिक प्रयास

के लिए गया था

• कोने बनाने के चेहरे
• चेहरे
प्रत्येक चेहरे के लिए
• (केन्द्रक के लिए अपने कोण रिश्तेदार का प्रयोग करके) के भीतर तरह कोने में
• समूह कोने, पहले हड़पने वर्टेक्स और फिर आधे किनारे की सूची बनाने के लिए क्रमबद्ध वर्टेक्स सूची के माध्यम से चलें।

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

आधे किनारों में शिखर (और चेहरे) के बारे में डेटा मोड़ने का सबसे अच्छा तरीका क्या है?

Answer 1

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

अब आपके सवाल का:

बहरहाल, यह एक (आधे किनारों के साथ) है कि आसन्न चेहरे के बारे में कोई जानकारी नहीं है चेहरों की सूची बनाता है! यह भी एक सा गलत लगता है, क्योंकि यह के रूप में अगर चेहरे वास्तव में प्रथम श्रेणी वस्तु हैं लगता है और किनारों सहायक जानकारी

मैं यह कुछ हद तक आधा बढ़त डेटा संरचना की बात याद करते हैं लगता है प्रदान करते हैं। आधे किनारे की संरचना में, यह आधा किनारों वाला है जो सबसे अधिक जानकारी लेता है!

OpenMesh documentation से बेशर्म का हवाला देते हुए (यह भी आंकड़ा वहाँ देखें):

• प्रत्येक शिखर का संदर्भ एक निवर्तमान halfedge, यानि कि एक halfedge है कि इस शिखर पर शुरू होता है।
• प्रत्येक चेहरा संदर्भित आधा किनारों में से एक का संदर्भ देता है।
• प्रत्येक halfedge,
  • शिखर यह की ओर इशारा करने के लिए एक संभाल प्रदान करता है
  • चेहरा यह
  • चेहरे के अंदर अगले halfedge (आदेश दिया वामावर्त) के अंतर्गत आता है,
  • विपरीत halfedge ,
  • (वैकल्पिक रूप से: चेहरे में पिछला आधा)।

जैसा कि आप देख, सबसे जानकारी आधा किनारों में संग्रहित है - इन प्राथमिक वस्तुओं रहे हैं। इस डेटा-स्ट्रक्चर में मेस पर इटरेट करना चतुरता से पॉइंटर्स के बारे में है।

हालांकि, यह चेहरों की एक सूची बनाता है (आधा किनारों के साथ) जिनके पास आसन्न चेहरे के बारे में कोई जानकारी नहीं है!

यह बिल्कुल ठीक है! जैसा कि आप ऊपर देखते हैं, एक चेहरा संदर्भ केवल एक बाध्य आधा किनारा है।

F -> halfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> nextHalfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> previousHalfEdge -> oppositeHalfEdge -> face

वैकल्पिक रूप से, आप का उपयोग कर सकते हैं: एक त्रिकोण जाल, संकेत की श्रृंखला आप किसी दिए गए चेहरे F को 3 आसन्न त्रिकोण प्राप्त करने के लिए का पालन करें मान लिया जाये कि पीछा कर रहा है nextHalfEdge -> nextHalfEdge यदि आप 'पिछले' पॉइंटर्स का उपयोग नहीं करते हैं। यह, ज़ाहिर है, आसानी से quads या उच्च आदेश बहुभुज के लिए सामान्यीकृत।

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

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

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

मुझे लगता है कि आधे किनारों को HalfEdge के structs के रूप में लागू किया गया है, जिसमें ऊपर सूचीबद्ध पॉइंटर्स शामिल हैं।

struct HalfEdge 
    { 
     HalfEdge * oppositeHalfEdge; 
     HalfEdge * nextHalfEdge; 
     Vertex * vertex; 
     Face * face; 
    } 

Let वास्तविक आधा बढ़त उदाहरणों, उदा की ओर इशारा करने के लिए शीर्ष पहचानकर्ता के जोड़े से एक नक्शा होना Edges

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges; 

सी ++ में।यहाँ निर्माण छद्म कोड (शीर्ष और चेहरे भाग के बिना) है:

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges; 

for each face F 
{ 
    for each edge (u,v) of F 
    { 
     Edges[ pair(u,v) ] = new HalfEdge(); 
     Edges[ pair(u,v) ]->face = F; 
    } 
    for each edge (u,v) of F 
    { 
     set Edges[ pair(u,v) ]->nextHalfEdge to next half-edge in F 
     if (Edges.find(pair(v,u)) != Edges.end()) 
     { 
     Edges[ pair(u,v) ]->oppositeHalfEdge = Edges[ pair(v,u) ]; 
     Edges[ pair(v,u) ]->oppositeHalfEdge = Edges[ pair(u,v) ]; 
     } 
    } 
} 

संपादित करें: कोड थोड़ा कम छद्म बने, Edges नक्शे और संकेत के बारे में अधिक स्पष्ट होना।