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




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

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


बहुभुज प्रतिनिधित्व को एक सीमा में परिवर्तित करने की योजना

B- प्रतिनिधि में रूपांतरण प्रक्रिया शुरू करने से पहले, कुछ मामलों में, मूल बहुभुज जाल की गुणवत्ता में सुधार करना आवश्यक है: पड़ोसी बहुभुज पर मानदंडों की दिशाओं का समन्वय करें, "छेद" को खत्म करें, मूल जाल में शोर की उपस्थिति में स्मूथिंग एल्गोरिदम लागू करें।

बहुभुज विभाजन

पहले चरण में, मेष बहुभुजों के प्रारंभिक सेट को सबसेट (खंडों) में वर्गीकृत किया गया है। मेष के कोने पर स्थित मानदंडों के बारे में जानकारी पहले-क्रम विभाजन की अनुमति देती है और इस तरह प्रारंभिक मेष विभाजन सुनिश्चित करती है, साथ ही साथ फ्लैट या दृढ़ता से घुमावदार क्षेत्रों को वर्गीकृत करती है।

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

द्वितीय-क्रम विभाजन अपने मुख्य वक्रताओं के अनुसार ग्रिड का विश्लेषण करता है, जो प्राथमिक सतहों के वर्गीकरण के लिए पर्याप्त आधार प्रदान करता है। ग्रिड के कोने पर वक्रता की गणना करने में, हमने असतत अंतर को निर्धारित करने के लिए मेयर (मार्क मेयर, माथेरू डेसब्रन, पीटर श्रोडर, और एलन एच। बर, डिस्क्रिट डिफरेंशियल-जियोमेट्री ऑपरेटर्स ट्राइंगुलेटेड 2-मैनिफोल्ड्स, विज़ुअलाइज़ेशन और मैथमेटिक्स III, 2003) के परिणामों का उपयोग किया। त्रिकोणीय क्षेत्रों के लिए ऑपरेटर: मूल जाल के प्रत्येक शीर्ष के लिए, हम एक किनारे के माध्यम से दिए गए शीर्ष के साथ जुड़े पड़ोसी कोने का एक सेट मानते हैं। फिर, एक असतत ऑपरेटर K की गणना किसी दिए गए शीर्ष के लिए की जाती है, जिसके आधार पर ग्रिड के शीर्ष पर औसत सामान्य, औसत K _H, और Gaussian K _G वक्रता निर्धारित की जाती है।


त्रिकोणीय डोमेन के लिए असतत अंतर ऑपरेटर की परिभाषा पर

इस प्रकार, ग्रिड के प्रत्येक शीर्ष के लिए वक्रता टेंसर की गणना की जाती है, जिनमें से eigenvalues ​​वांछित मुख्य वक्रता K ₁ और K _{2 हैं} , और eigenvectors वक्रता परिवर्तन की मुख्य दिशाएं हैं।

इसके बाद, मेष वर्टिकल को प्रमुख वक्रता K ₁ और K ₂ के मानों के अनुसार वर्गीकृत किया जाता है। वर्टेक्स वर्गीकरण एल्गोरिदम k- साधन विधि पर आधारित है, अर्थात्, इन समूहों के केंद्रों से क्लस्टर बिंदुओं के कुल द्विघात विचलन को कम करने पर। नतीजतन, एल्गोरिदम के आउटपुट पर, ग्रिड के प्रत्येक शीर्ष को एक निश्चित क्लस्टर के साथ जोड़ा जाता है $$$सि$और वक्रता (क्लस्टर सेंटर) (L. Guillaume, "वक्रता सेंसर आधारित सीमा निर्धारण के साथ त्रिभुज मेष विभाजन", प्रोसीडिंग्स कंप्यूटर ग्राफिक्स इंटरनेशनल (CGI), 2004) की एक जोड़ी।


वक्रता के स्थान में एक बहुभुज जाल के कोने का वर्गीकरण

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

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


बहुभुज जाल विभाजन तंत्र

खंड गठन प्रक्रिया के अंत में, प्रश्न में मेष के अत्यधिक विभाजन को समाप्त करने के लिए आसन्न खंडों को सिलाई के लिए एक विशेष एल्गोरिथ्म किया जाता है।

सतह की पहचान

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

• विमान: के _१ = के _२ = ०
• गोला: के _१ = के _२ = के > ०
• सिलेंडर: k ₁ = K > 0, k ₂ = 0
• शंकु: के _१ ∈ [ ए , बी ], के _२ = ०
• torus: k ₁ = K , k _2: [ a , b ]

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

बिंदुओं के एक सेट में सरल ज्यामितीय वस्तुओं को फिट करने के तरीकों का उपयोग करके प्राथमिक सतहों का निर्माण किया जाता है। तो, सर्कल और गोले को फिट करने के लिए, विमान को फिट करने के लिए सबसे कम वर्ग विधि का उपयोग किया जाता है - प्रमुख घटक विधि। प्रत्येक पुनर्निर्मित सतह को किसी दिए गए मान्यता सटीकता के लिए एक खंड के अनुपालन के लिए जाँच की जाती है।

स्पष्टता के लिए, हमने अलग-अलग रंगों में मान्यता प्राप्त सतहों को चित्रित किया: विमान - नीला, सिलेंडर - लाल, गोल - हरा, शंकु - पीला, तोरी - बैंगनी।


मूल बहुभुज जाल (बाएं) और खंडों पर मान्यता प्राप्त सतहों के साथ खंडित मेष (दाएं)

B- प्रतिनिधि मॉडल का निर्माण

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

रूपांतरण के पिछले चरणों के विपरीत, बी-रेप असेंबली को पूरी तरह से स्वचालित मोड में किया जाता है: आसन्न पुनर्निर्मित सतहों की चौराहे की लाइनें पाई जाती हैं, चेहरे के किनारों को उन पर बनाया जाता है, चेहरे खुद को और, आखिरकार, बी-रेप शेल को इकट्ठा किया जाता है।




मूल बहुभुज जाल (बाएं) और बी-प्रतिनिधि मॉडल (दाएं)

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

बहुभुज मॉडल के प्रकार और रूपांतरण मोड की पसंद

आज, बहुभुज प्रतिनिधित्व में मॉडल के कई मुख्य स्रोत हैं:

• ऑनलाइन कैटलॉग, बहुभुज प्रारूप (STL, VRML, OBJ) में 3D मॉडल के डेटाबेस, उदाहरण के लिए 3D वेयरहाउस, Cults 3D, आदि।
• 3 डी स्कैन के परिणाम
• सीएई-एल्गोरिदम द्वारा टोपोलॉजिकल मॉडल अनुकूलन के परिणाम।

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

दूसरे समूह के मॉडल के बहुभुज ग्रिड उपयोगकर्ता के साथ एक सघन इंटरैक्टिव बातचीत करते हैं। इसलिए, शुरू में हमने सी 3 डी बी-शेपर में दो ऑपरेटिंग मोड रखे - पूरी तरह से स्वचालित और इंटरैक्टिव।

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

C3D B-Shaper स्वचालित रूपांतरण इंटरफ़ेस निम्नलिखित कार्यों द्वारा दर्शाया गया है, जो इनपुट ग्रिड और रूपांतरण सेटिंग्स को इनपुट के रूप में स्वीकार करते हैं:

MbResultType ConvertMeshToShell( MbMesh & mesh, MbFaceShell *& shell, const MbMeshProcessorValues & params ); MbResultType ConvertCollectionToShell( MbCollection & collection, MbFaceShell *& shell, const MbMeshProcessorValues & params ); 

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

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

 class MbMeshProcessor { .. public: // “” . void SetUseMeshSmoothing( bool useSmoothing ); //   . const MbCollection & GetSegmentedMesh(); MbResultType SegmentMesh( bool createSurfaces = true ); void ResetSegmentation(); void UniteSegments( size_t firstSegmentIdx, size_t secondSegmentIdx ); MbResultType SegmentMeshBySeparators( const std::vector<std::vector<uint>> & sep ); //   . void FitSurfaceToSegment( size_t idxSegment ); void FitSurfaceToSegment( size_t idxSegment, MbeSpaceType surfaceType ); const MbSurface * GetSegmentSurface( size_t idxSegment ) const; //  B-rep . MbResultType CreateBRepShell( MbFaceShell *& pShell ); .. } 

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

अभी क्या हो रहा है

जुलाई में, हमने घटक का पहला संस्करण जारी किया और अब इसे कई क्षेत्रों में विकसित करना जारी है: स्वचालित विभाजन एल्गोरिदम, विभाजन संपादन उपकरण, एक सेगमेंट पर आधारित फ्री-फॉर्म सरफेस (NURBS) का निर्माण, और B- रेप शेल के निर्माण की गुणवत्ता में सुधार।

इच्छुक डेवलपर्स C3D B-Shaper का परीक्षण कर सकते हैं। घटक हमारी वेबसाइट पर अनुरोध पर तीन महीने के लिए नि: शुल्क प्रदान किया जाता है।

लेखक - एंड्री ट्यूमनिन, पीएचडी, सी 3 डी लैब्स के गणितज्ञ-प्रोग्रामर