GJK एल्गोरिद्म: साधारण कामों को अजीब और खूबसूरती से हल करने का तरीका

 (computerwebsite.net)
2 पॉइंट द्वारा GN⁺ 2024-06-13 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • GJK एल्गोरिद्म यह जांचने का एक तरीका है कि क्या दो आकृतियाँ एक-दूसरे पर ओवरलैप करती हैं
  • यह जांचने के लिए कि आकृति A और आकृति B ओवरलैप करती हैं या नहीं, यह देखना होता है कि क्या दोनों आकृतियों के बिंदुओं में से कोई एक भी एक-दूसरे से मेल खाता है

Minkowski अंतर समुच्चय

  • दो आकृतियों के सभी बिंदुओं को घटाकर एक नया समुच्चय बनाया जाता है।
  • अगर इस नए समुच्चय में मूलबिंदु शामिल हो, तो इसका मतलब है कि दोनों आकृतियाँ ओवरलैप करती हैं।
  • इसे Minkowski अंतर समुच्चय कहा जाता है।

एल्गोरिद्म का मूल विचार

  • यह जांचना कि A और B का Minkowski अंतर समुच्चय मूलबिंदु को शामिल करता है या नहीं।
  • अगर अंतर समुच्चय में मूलबिंदु शामिल है, तो दोनों आकृतियाँ ओवरलैप करती हैं।

एल्गोरिद्म के चरण

  1. आरंभ: एक मनमाना दिशा वेक्टर d सेट किया जाता है और पहला बिंदु p खोजा जाता है।
  2. बिंदु खोजना: d और p का डॉट प्रोडक्ट निकाला जाता है; अगर यह धनात्मक हो तो प्रक्रिया जारी रहती है, और ऋणात्मक हो तो समाप्त हो जाती है।
  3. नया बिंदु जोड़ना: p से मूलबिंदु की दिशा में एक नया बिंदु खोजा जाता है।
  4. सरलीकरण: पहले दो बिंदुओं के आधार पर नया बिंदु जोड़कर simplex को अपडेट किया जाता है।
  5. मूलबिंदु शामिल है या नहीं, इसकी जांच: यह देखा जाता है कि सरलीकृत आकृति में मूलबिंदु शामिल है या नहीं।
  6. दोहराव: जब तक मूलबिंदु शामिल न हो जाए, या यह प्रमाण न मिल जाए कि वह शामिल नहीं है, तब तक प्रक्रिया दोहराई जाती है।

GN⁺ की राय

  • दिलचस्प बात: GJK एल्गोरिद्म इस बात का एक अच्छा उदाहरण है कि जटिल समस्या को सरल गणितीय रूपांतरण से कैसे हल किया जा सकता है।
  • यह उपयोगी क्यों है: real-time graphics में collision detection जैसे कामों में इसका बहुत उपयोग होता है।
  • आलोचनात्मक दृष्टिकोण: एल्गोरिद्म का implementation जटिल हो सकता है, और इसे सही तरह से समझना जरूरी है।
  • संबंधित तकनीक: अन्य collision detection एल्गोरिद्म में SAT(Separating Axis Theorem) आदि शामिल हैं।
  • ध्यान देने योग्य बात: GJK एल्गोरिद्म का उपयोग करते समय आकृतियों की जटिलता और computation cost को ध्यान में रखना चाहिए।

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-06-13
Hacker News की राय

  • 1990 के दशक में GJK की वजह से लगभग एक साल तक जूझना पड़ा था
    यह 3D collision detection में उपयोगी है, और nearest-point algorithm के रूप में भी इस्तेमाल किया जा सकता है। मूल विचार समझना आसान है। जब दो convex ठोस हों, तो हर ठोस से एक-एक मनमाना बिंदु चुनकर उन दोनों बिंदुओं के बीच की दूरी निकाली जाती है, फिर मौजूदा बिंदु से हर किनारे के साथ आगे बढ़कर दूरी बेहतर करने की कोशिश की जाती है, और नया nearest point चुना जाता है
    लेकिन जब nearest point अब vertex नहीं रहता, तो यह तरीका टूट जाता है, और तब simplex की अवधारणा की ज़रूरत पड़ती है। nearest-point संयोजन vertex-vertex, vertex-edge, vertex-face, edge-edge, edge-face (एकमात्र हल नहीं), face-face (एकमात्र हल नहीं) में बंटते हैं, और simplex हैंडलिंग असल में इन मामलों का विश्लेषण करने के काफ़ी करीब है
    व्यवहार में बहुत दिक्कतें आती हैं। physics engine में objects अक्सर face-face contact की स्थिति में स्थिर होते हैं, और single-point collision model कंपन या गलत movement पैदा कर सकता है। इसके अलावा, जब स्थिति face-face contact की ओर converge करती है, तो GJK बड़े मानों के बीच छोटे अंतर संभालता है और floating-point की effective precision पूरी तरह खो सकता है। termination condition भी infinite loop पैदा कर सकती है
    सिद्धांत में यह elegant है, लेकिन व्यवहार में यह कठिन numerical analysis की समस्या है। फिर भी, शायद इस समस्या के लिए यह सबसे तेज़ तरीकों में से एक है। सामान्य मामले में O(log N) है, और अगर पिछली स्थिति तथा सबसे नज़दीकी हालात में last solution को starting point बनाया जाए तो O(1) के क़रीब हो सकता है
    Oxford के दिवंगत प्रोफेसर Steven Cameron ने GJK को सही तरह से काम कराने में बहुत काम किया था, और 1990 के दशक के उत्तरार्ध में पहले commercial 3D ragdoll system "Falling Bodies" में GJK का इस्तेमाल किया गया था

    • एक बार contact मिल जाए, तो लगभग हमेशा उसके साथ कुछ न कुछ करना पड़ता है, और ज़्यादातर उपयोगी processing के लिए असली overlap information जानना ज़रूरी होता है
      इसे निकालना संख्यात्मक रूप से और भी खराब है। GJK द्वारा बनाए गए simplex से शुरू करके बाहर की ओर expand करना पड़ता है, और इस प्रक्रिया में triangulation करनी होती है। इसे अच्छा performance देते हुए implement करना लगभग दुःस्वप्न जैसा है
    • https://www.youtube.com/watch?v=5lHqEwk7YHs
      सोच रहा हूँ कि patent अब expire हो चुका है या नहीं, और क्या code सार्वजनिक करने का कोई इरादा है। ऐतिहासिक रूप से इसका महत्व है और यह Doom source पढ़ने जैसी दिलचस्प सामग्री हो सकती है

  • मुझे GJK collision detection algorithm को सहज रूप से समझाने वाला लेख नहीं मिला, इसलिए मैंने दोपहर का समय निकालकर खुद इसे लिखा
    अगर इसे और स्पष्ट या अधिक कुशल बनाने के तरीके हों तो बताइएगा। और हाँ, यह भी ध्यान में रखें कि यह गणित से जुड़ी बातों को समझाने की कोशिश कर रहे 11वीं कक्षा के छात्र की लिखी हुई चीज़ है

    • लेख बहुत स्पष्ट है। अगर आप ऐसे काम करते रहे तो कभी न कभी एक शानदार पाठ्यपुस्तक लिख सकने लायक प्रतिभा दिखती है
      यह अभी भी अच्छा है, लेकिन इसे और बेहतर बनाने के लिए कुछ चीज़ें जोड़ी जा सकती हैं। सबसे खराब स्थिति में time complexity पर एक छोटा विवरण, termination condition पर अलग section, और बीच-बीच में pseudocode अच्छा रहेगा
      अभी जो गणितीय नज़रिए से समझाने का तरीका है, वह बहुत अच्छा बैठता है और उसे बनाए रखना चाहिए। बस हर चरण के बाद S(•) जैसे helper function परिभाषित करते हुए यह दिखाने वाला छोटा pseudocode जोड़ दिया जाए कि algorithm कहाँ तक पहुँचा है, तो और अच्छा होगा
      OpenAI के hidden model पर लिखा आपका लेख भी अच्छा था। किसी प्रभावशाली काम के पीछे उसी व्यक्ति ने और क्या किया है, यह देखने में लगाया गया समय लगभग हमेशा सार्थक होता है
    • एक गणितज्ञ के रूप में कहूँ तो, अगर यह गणित के पाठकों के लिए लिखा जाता, तो मैं बस कुछ अभिव्यक्तियाँ बहुत मामूली तौर पर अलग रखता — यही मेरी सबसे कड़ी आलोचना है
      शीर्षक "as simply as possible" होना चाहिए। मुझे GJK algorithm का पता नहीं था, लेकिन अगर मैं अभी Calculus III पढ़ा रहा होता, तो इसे कक्षा में शामिल करने का तरीका ज़रूर खोजता। व्याख्या इतनी अच्छी है
    • मैं सोच रहा हूँ कि क्या इस algorithm में termination की guarantee है
      लेख के अंत में smooth rounded rectangle वाले उदाहरण में क्या चीज़ इसे सिर्फ़ उत्तर के और पास जाते रहने से रोकती है और सच में वहाँ पहुँचा देती है, यह साफ़ नहीं है। बेशक, वास्तविक computing में practical precision limit के बाद आगे बढ़ते रहने की कोई वजह नहीं होती, यह मैं जानता हूँ
    • दूसरी तस्वीर में तीन sets A, B, A-B थोड़ा भ्रमित करते हैं
      पहले मुझे लगा कि A और B पर कोई transformation लगाकर A-B आकार बनाया गया है। कई बार दोबारा पढ़ने पर अब ऐसा लगता है कि A-B बाईं ओर के दो sets नहीं, बल्कि किसी दूसरे A और B का intersection दिखाता है, और महत्वपूर्ण बात यह है कि वह intersection origin या 0,0 पर overlap करता है। जानना चाहता हूँ कि क्या मैं सही समझा हूँ

  • इसी algorithm पर एक video presentation: https://www.youtube.com/watch?v=ajv46BSqcK4

  • लेख बहुत स्पष्ट और दिलचस्प है
    दो convex sets के intersection की जाँच करने का एक दूसरा तरीका यह है कि पहले convex set के किसी बिंदु और दूसरे convex set के किसी बिंदु के अंतर के norm को न्यूनतम करने वाली convex optimization समस्या हल की जाए। अगर optimal value 0 हो, तो दोनों sets intersect करते हैं
    GJK algorithm और convex optimization की तुलना करना दिलचस्प होगा। कौन बेहतर रहेगा, यह मुझे नहीं पता

    • दिलचस्प सवाल है। अगर overlap काफ़ी बड़ा हो, तो interior-point method जल्दी खत्म हो सकता है। कुछ चतुर early-termination conditions भी जोड़ी जा सकती हैं

  • पहली image non-convex shape का intersection दिखाती है, लेकिन यह बात कि algorithm सिर्फ़ convex shapes पर काम करता है, बहुत बाद में आती है, इसलिए यह थोड़ा भ्रामक हो सकता है

    • समझाया गया है कि non-convex shapes को convex shapes में बाँटकर संभाला जाता है

  • मैं कुछ समय से openSCAD में Minkowski function इस्तेमाल कर रहा था, यह जानकर अच्छा लगा कि वह वास्तव में क्या है

  • चूँकि इसे उम्मीद से ज़्यादा ध्यान मिल गया है, शायद यह बता देना चाहिए कि मेरी personal website असल में काफ़ी हद तक बारीक inside jokes का संग्रह है
    अगर संपर्क करना हो या कुछ काम हो तो reply में बता सकते हैं

    • अगर research project mentoring में रुचि हो तो ईमेल कर सकते हैं: bersub@cmu.edu
    • साइट अच्छी है और आप भी अच्छे इंसान लगते हैं। उम्मीद है आप ऐसी शानदार चीज़ें बनाते रहेंगे

  • लगभग 10 साल पहले मैंने Casey की शानदार व्याख्या के आधार पर GJK implement किया था: https://www.youtube.com/watch?v=Qupqu1xe7Io

  • मैंने Minkowski geometry से जुड़ी एक पोस्ट लिखी थी: https://nickp.svbtle.com/asteroid-intersections