🥫 🔶 👩🏿‍🤝‍👩🏾 उलटा कीनेमेटीक्स: सरल और तेज एल्गोरिथ्म 👔 🖲️ 🔫

उलटा काइनेमेटिक्स क्या है?

व्युत्क्रम कीनेमेटीक्स का कार्य संयुक्त कॉन्फ़िगरेशन के ऐसे सेट की खोज करना है जो दिए गए बिंदुओं को सबसे नरम, तेज़ और सटीक आंदोलन प्रदान करेगा। हालांकि, कई मौजूदा तरीके उच्च कम्प्यूटेशनल जटिलता और परिणामी पोज़ की अस्वाभाविकता जैसी कमियों से ग्रस्त हैं। इस लेख में एक नया ( संभवतः लेखन के समय, 2010 ) के बारे में वर्णन किया गया है, जिसे भावात्मक पद्धति ने फॉरवर्ड एंड बैकवर्ड रीचिंग इनवर्स किनेमैटिक्स कहा जाता है (इसके बाद बस FABRIK),

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

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

1. कृत्रिम शरीर मॉडल

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

कंकाल आमतौर पर किनारों से जुड़े ठोस खंडों के पदानुक्रम के रूप में तैयार किया जाता है, जिनमें से प्रत्येक को लंबाई, आकार, मात्रा और द्रव्यमान जैसे गुणों द्वारा परिभाषित किया जाता है। मैनिपुलेटर, एक रोबोट बांह या एक एनिमेटेड चरित्र के तरीके में, एक श्रृंखला के रूप में तैयार किया जाता है, जो किनारों से एक दूसरे के साथ संयुग्मित ठोस समुद्री मील से इकट्ठा होता है। सूचकांक के साथ हड्डी के प्रत्येक आंदोलन और / या रोटेशन श्रृंखला के सभी बाद के तत्वों को प्रभावित करता है। एक श्रृंखला को इस प्रकार औपचारिक रूप दिया जा सकता है: बच्चों के बिना प्रत्येक नोड को एक समापन बिंदु कहा जाना चाहिए; प्रत्येक अंतिम बिंदु के लिए, श्रृंखला कंकाल के साथ वापस चलती है, माता-पिता से माता-पिता तक बनाई जा सकती है, जब तक कि श्रृंखला के रूट नोड को पूरा नहीं किया जाता है (श्रृंखला की शुरुआत)। परिभाषा के अनुसार, IK कार्य एक स्थिर रूट नोड मानता है। हालाँकि, विधियाँ आमतौर पर रूट मूवमेंट को संभालती हैं।

FABRIK एल्गोरिथ्म पूर्ण चक्र एल्गोरिथ्म (छद्म कोड, सूचकांक 1 के तहत पहला सरणी तत्व)

 :    p[i]  i = 1...n,   t      . d[i] = | p[i+1] - p[i] | for i = 1, ... , n-1  :   p[i], i = 1...n //     dist = | p[1] - t | //   if dist > d[1] + d[2] + ... + d[n-1] { //  for i = 1, ..., n-1 do { //  r[i]   t   p[i] r[i] = | t - p[i] | lambda[i] = d[i] / r[i] //    p[i] p[i+1] = (1 - lambda[i]) * p[i] + lambda[i] * t } } else { // ; .. b     p[1] b = p[1] //,        p[n]  //  t   (tolerance) DIFa = | p[n] - t | while DIFa > tol do { // 1 :   //   p[n]    (,   "   " - . .) p[n] = t for i=n -1 , ..., 1 do { //  r[i]   p[i]    p[i+1] r[i] = | p[i+1] - p[i] | lambda[i] = d[i] / r[i] //    p[i] p[i] = ( 1 - lambda[i]) * p[i+1] + lambda[i] * p[i] } // 2:   //   p[1]   p[i] = b for i=1 ,..., n - 1 do { //  r[i]   p[i+1]   p[i] r[i] = | p[i+1] - p[i] | lambda[i] = d[i] / r[i] //   p[i] p[i+1] = (1-lambda[i]) * p[i] + lambda[i] * p[i+1] } DIFa = | p[n] - t | } }

2. फेब्रिक - आईके समस्या का एक नया हेयुरिस्टिक समाधान

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

a - मैनिपुलेटर और लक्ष्य के प्रारंभिक स्थान।
b - हम अंतिम नोड p [4] को लक्ष्य पर ले जाते हैं।
c - हम स्थिति p '[3] की स्थिति p' [4] और p [3] के बीच की रेखा पर लेटते हैं, बिंदु p '[4] से कुछ दूरी d [3] पर।
डी - सभी नोड्स के लिए दोहराएं।
ई - एल्गोरिथ्म का दूसरा चरण: हम रूट तत्व को स्थिति पी '[1] से इसकी प्रारंभिक स्थिति में ले जाते हैं।
f - सभी नोड्स के लिए दोहराएं, लेकिन इस बार हम आधार से शुरू करते हैं और अंतिम नोड तक जाते हैं। एल्गोरिथ्म को दोहराया जाता है जब तक कि अंतिम तत्व की स्थिति पर्याप्त दूरी पर लक्ष्य तक नहीं पहुंचती।

अधिक जानकारी:

सबसे पहले, नोड्स के बीच स्थितियां मानी जाती हैं (सरणी डी ), जिसके बाद यह देखने के लिए एक चेक बनाया जाता है कि क्या लक्ष्य बिंदु उपलब्ध है; रूट नोड और लक्ष्य ( डिस्ट ) के बीच की दूरी को माना जाता है, और यदि यह दूरी नोड्स के बीच की दूरी के कुल योग से कम है, तो लक्ष्य प्राप्त करने योग्य है, अन्यथा नहीं। यदि लक्ष्य प्राप्य है, तो पूर्ण चक्र दो चरणों तक सीमित है। पहले चरण में, एल्गोरिथ्म प्रत्येक नोड की प्रारंभिक स्थिति का अनुमान लगाता है, जो परिमित तत्व p [n] से शुरू होकर मैनिप्युलेटर p [1] के आधार पर जा रहा है। इस प्रकार, लक्ष्य स्थिति को अंतिम नोड, p '[n] = t की स्थिति बताएं । हम बिंदु l [ n-1] और p '[n] पर पड़ी लाइन l [n-1] प्राप्त करते हैं। सूचकांक n-1 , p '[n-1] के साथ नोड की नई स्थिति, इस रेखा पर p [[n] से d [n-1] की दूरी पर स्थित है। इसी तरह, सूचकांक n-2 , p '[n-2] के साथ नोड की नई स्थिति, कुछ दूरी p [n-2] और p' [n-1] दूरी पर स्थित लाइन l [n-2] का उपयोग करके गणना की जा सकती है। d [n-2] p से [n-2] । एल्गोरिथ्म को दोहराया जाता है जब तक कि अंतिम एक सहित सभी नोड्स के लिए सभी नए पदों की गणना नहीं की जाती है। ऐसे मामलों में जहां रूट तत्व आवश्यक स्थिति में जाता है, FABRIK वर्णित के रूप में काम करता है, एकमात्र अंतर यह है कि रूट नोड की नई स्थिति p '[1] वांछित स्थिति होगी, न कि प्रारंभिक।

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

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

3. कई परिमित नोड्स वाला एक मॉडल

एक अंत नोड के साथ मामले में, एल्गोरिथ्म दो चरणों में विभाजित है:

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

4. सीमा

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

a - प्रारंभिक जोड़तोड़ और लक्ष्य विन्यास।
बी - हम अंतिम नोड पी [4] को लक्ष्य पर ले जाते हैं और इसे ओर उन्मुख करते हैं।
c - हम स्थिति p '[3] की स्थिति p' [4] और p [3] के बीच की रेखा पर लेटते हैं, बिंदु p '[4] से कुछ दूरी d [3] पर।
d - स्थिति p '[3] के लिए नोड को फिर से बनाएँ ताकि यह p' [3] और p '[4] को जोड़ने वाले किनारे पर लगे।
ई - बाउंडिंग दीर्घवृत्त की गणना: अनुमत स्थान छायांकित क्षेत्र में हैं। इस स्तर की कोई भी चोटियां कहीं भी नहीं जाती हैं।
f - नोड p [2] स्थिति p ^ [2] पर जाता है , जो कि छायांकित दीर्घवृत्त पर निकटतम स्थिति है, यह सुनिश्चित करता है कि नई स्थिति p ^ [2] स्वीकार्य सीमा के भीतर होगी।
g - किनारे की लंबाई को संरक्षित करने के लिए नोड p ^ [2] को बिंदु p '[2] पर ले जाएं।
h - पुन: रोगी p '[2] अभिविन्यास की सीमा को संतुष्ट करने के लिए।

यह प्रक्रिया सभी नोड्स के लिए दोहराई जाती है, प्रत्यक्ष और रिवर्स ऑर्डर में, उसी तरह जैसे कि बिना किसी प्रतिबंध के संस्करण में किए गए थे। एक ही समय में, "दीर्घवृत्त" बाधा शायद एक किनारे की विशेषता है, एक नोड नहीं है, जो है, दूसरे चरण में, नोड p [3] को दीर्घवृत्त - लगभग जाना चाहिए। ट्रांस।

उलटा कीनेमेटीक्स: सरल और तेज एल्गोरिथ्म

1. कृत्रिम शरीर मॉडल

2. फेब्रिक - आईके समस्या का एक नया हेयुरिस्टिक समाधान

3. कई परिमित नोड्स वाला एक मॉडल

4. सीमा

More articles: