मैंने टक्कर मान्यता प्रक्रियाओं का अध्ययन किया, और इसने मुझे गिल्बर्ट-जॉनसन-कीर्थी (GJK) एल्गोरिथ्म तक पहुँचाया।

पोस्ट के सभी कोड उदाहरण टाइपस्क्रिप्ट में लिखे गए हैं। उदाहरण मैं बनाई गई संरचनाओं का उपयोग करते हैं जो पोस्ट में विस्तार से चर्चा नहीं की जाती हैं। वे सरल हैं और GitHub रिपॉजिटरी में देखे जा सकते हैं:

• Vector
• IShape
• Collision

पोस्ट से सभी कोड GitHub रिपॉजिटरी में संग्रहीत हैं:

https://github.com/jthomperoo/gjk-ts-implementation

पोस्ट को इस लेख और उसमें सुझाए गए वीडियो के आधार पर लिखा गया था:

• http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
• http://mollyrocket.com/849

परिचय

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

आवश्यक जानकारी

मिन्कोवस्की योग

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


चित्र A (हरा):


चित्रा बी (बैंगनी):


आकृति A और आकृति B के मान लेते हुए, हम Minkowski राशि की गणना कर सकते हैं:

A + D = (0,1) + (0,-1) = (0,0)

A + E = (0,1) + (1,1) = (1,2)

A + F = (0,1) + (-1,1) = (-1,2)

B + D = (1,-1) + (0,-1) = (1,-2)

B + E = (1,-1) + (1,1) = (2,0)

B + F = (1,-1) + (-1,1) = (0,0)

C + D = (-1,-1) + (0,-1) = (-1,-2)

C + E = (-1,-1) + (1,1) = (0,0)

C + F = (-1,-1) + (-1,1) = (-2,0)

यदि हम इन मूल्यों को लेते हैं और उनसे एक ग्राफ बनाते हैं, तो हम देखेंगे कि कौन सा आंकड़ा परिणाम होगा।

आंकड़े ए और बी के लिए मिंकोव्स्की योग:

ध्यान दें कि तालिका और ग्राफ़ में AD A + D से मेल खाता है



मिंकोव्स्की राशि को बेहतर ढंग से समझने के लिए, हम कल्पना कर सकते हैं कि हम एक आकृति ए लेते हैं और इसे बी की रूपरेखा के साथ बायपास करते हैं। परिणामी आकृति मिन्कोवस्की योग होगी।

मिंकोव्स्की अंतर

GJK Minkowski राशि का भिन्नता का उपयोग करता है, जिसमें A + B नहीं लिया जाता है, लेकिन A - B. मेरे द्वारा पढ़े जाने वाले स्रोतों में, इसे "Minkowski अंतर" कहा जाता है। मिन्कोवस्की अंतर में एक दिलचस्प संपत्ति है: यदि दो आंकड़े ओवरलैप / इंटरसेक्ट करते हैं, तो परिणामस्वरूप मिन्कोवस्की अंतर में मूल शामिल होगा। और यह GJK एल्गोरिदम का आधार है।

आंकड़े ए और बी के मूल्यों को लेते हुए, हम मिंकोवस्की अंतर की गणना कर सकते हैं:

A - D = (0,1) - (0,-1) = (0,2)

A - E = (0,1) - (1,1) = (-1,0)

A - F = (0,1) - (-1,1) = (1,0)

B - D = (1,-1) - (0,-1) = (-1,0)

B - E = (1,-1) - (1,1) = (0,-2)

B - F = (1,-1) - (-1,1) = (2,-2)

C - D = (-1,-1) - (0,-1) = (-1,0)

C - E = (-1,-1) - (1,1) = (-2,-2)

C - F = (-1,-1) - (-1,1) = (0,-2)

यदि हम इन मूल्यों को लेते हैं और उन्हें ग्राफ पर डालते हैं, तो हम परिणामी आकृति देखेंगे।

आंकड़े ए और बी के लिए मिंकोव्स्की अंतर:

ध्यान दें कि तालिका में AD और ग्राफ A - D को संदर्भित करता है

एल्गोरिथ्म

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

हेल्पर कार्य

सहायक कार्य पूरे आंकड़े का निर्माण किए बिना मिंकोव्स्की अंतर के किनारे पर एक बिंदु का नमूना लेने का एक तरीका है। हेल्पर फ़ंक्शन को दो तुलनात्मक आंकड़े मिलते हैं, और जिस दिशा को जांचना आवश्यक है। तब सहायक फ़ंक्शन प्रत्येक आकृति से दो विपरीत दिशाओं से एक बिंदु दूर से प्राप्त करता है। इन दो सबसे दूर बिंदुओं का उपयोग करके, आप मिंकोव्स्की अंतर के आंकड़े पर सहायक बिंदु की गणना कर सकते हैं। हम विपरीत दिशाओं से अंक लेते हैं क्योंकि हमें मिंकोवस्की अंतर पर एक बिंदु मिलता है, जो हमें सबसे बड़ा क्षेत्र देगा, अर्थात्, एक उच्च संभावना होगी कि हम आंकड़े में मूल को घेर लेंगे। चूँकि Minkowski अंतर a - b , विपरीत दिशा से प्रतिरूपित b का बिंदु की उपस्थिति हमें एक सहायक बिंदु देगा जो इस दिशा में यथासंभव दूर है।

हेल्पर फ़ंक्शन का कार्यान्वयन काफी सरल है:

 function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

GJK के फायदों में से एक यह है कि FarthestPointInDirection को एब्स्ट्रैक्ट किया जा सकता है और इसे पॉलीगॉन और कर्व्स पर लागू किया जा सकता है। यहाँ बहुभुज के लिए FarthestPointInDirection का कार्यान्वयन है।

 class Polygon implements IShape { public points: Vector[]; ... public FarthestPointInDirection(direction: Vector): Vector { let farthestDistance = -Infinity; // If there are no points, just return point 0,0 let farthestPoint: Vector = new Vector(0,0); for (const point of this.points) { const distanceInDirection = point.Dot(direction); if (distanceInDirection > farthestDistance) { farthestPoint = point; farthestDistance = distanceInDirection; } } return farthestPoint; } } 

यदि आप यह देखना चाहते हैं कि अन्य आकृतियों को कैसे लागू किया जाएगा, तो इस पोस्ट के Git भंडार को देखें , जो Circle लिए कार्यान्वयन का परिचय देता है।

यहां बताया गया है कि ए (बी ) दिशा में सहायक बिंदु ( ए) और बी के आंकड़ों की गणना कैसे की जाएगी:

1. आकृति ए से सबसे दूर बिंदु ले लो; यह बिंदु बी (1, -1) निकला। (आप इसकी गणना कर सकते हैं, जैसा कि ऊपर दिखाया गया एल्गोरिदम करता है, या बस इसे ग्राफ को देखकर देखें)।
2. आकृति बी से सबसे दूर बिंदु ले लो; यह बिंदु F (-1, 1) निकला।
3. बी - एफ की गणना करें; यह बिंदु बीएफ (2, -2) निकला - यह सहायक होगा।

simplices

एक सिम्प्लेक्स, मिंकोव्स्की अंतर आकृति के साथ अंकों का एक नमूना है। सिम्प्लेक्स में तीन बिंदु तक हो सकते हैं। GJK उनका उपयोग करता है, एक टक्कर की घटना को निर्धारित करने के लिए मूल के चारों ओर एक त्रिकोण का निर्माण करने की कोशिश कर रहा है।

सिंप्लेक्स निर्माण

सिम्पलेक्स का निर्माण विभिन्न दिशाओं में सहायक बिंदुओं को जोड़कर पुनरावृति से किया जाता है। प्रत्येक सहायक बिंदु को एक नई दिशा में इंगित करना चाहिए, ताकि हम जितनी जल्दी हो सके एक मूल बिंदु वाले एक सिंप्लेक्स का निर्माण कर सकें। कठिनाई उस दिशा को चुनने में है जिसमें अगला सहायक बिंदु प्राप्त करना है।

टकराव का पता लगाने और दिशा चयन

मूल एल्गोरिथ्म बस एक सहायक फ़ंक्शन की सहायता से एक सिम्प्लेक्स बनाता है, जो आंकड़े में मूल के बिंदु को घेरने की कोशिश करता है। हम यह समझ सकते हैं कि गणना किए गए सहायक बिंदु मूल तक पहुँचते हैं या नहीं, यह जाँचने से कोई टकराव / चौराहा नहीं होता है, और यदि ऐसा नहीं होता है, तो मूल Minkowski अंतर के बाहर होना चाहिए; इसलिए, हम कह सकते हैं कि कोई टक्कर / चौराहा नहीं है।

 function Calculate(a: IShape, b: IShape): Collision | undefined { // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); } 

एल्गोरिथ्म की सभी जटिलता और आंतरिक ऑपरेशन simplex.CalculateDirection । simplex.CalculateDirection । यह फ़ंक्शन निर्धारित करता है कि मूल वर्तमान सिम्प्लेक्स में है - यदि हां, तो यह undefined वापस आ जाएगा; अन्यथा, यह एक सहायक बिंदु प्राप्त करने के लिए एक नई दिशा लौटाएगा, जिसे सिम्प्लेक्स में जोड़ा जाना चाहिए।

 class Simplex { private points: Vector[]; ... CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } return undefined; } // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; } } 

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

विस्तृत विवरण

हमें बहुत सारे कोड मिले, और यह भ्रामक लगता है। नीचे मैं ऊपर दिखाए गए आंकड़ों ए और बी के लिए एल्गोरिदम के चरणों का विश्लेषण करूंगा।

अंक ए और बी के अंक:

1. एल्गोरिदम की तैयारी; हम प्रारंभिक दिशा के रूप में (0,1) लेते हैं।
   
   

    // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); 

   
   
2. हमें पहला सहायक बिंदु मिलता है।
   
   

     // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); 

   
   हम बिंदु A से दिशा (0,1) और बिंदु B से दिशा (0,-1) में सबसे दूर का बिंदु प्राप्त करते हैं।
   
   aFar: (0,1) और bFar: (0,-1)
   
   सहायक बिंदु प्राप्त करने के लिए इन मूल्यों का उपयोग करें।
   
   समर्थन: aFar-bFar = (0,2)
   
   

     function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

   
   
3. हम अगले सहायक बिंदु के लिए दिशा फ्लिप करते हैं और नए सहायक बिंदु की गणना करते हुए पुनरावृत्ति शुरू करते हैं।
   
   समर्थन: (0,-3)
   
   

     // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); 

4. जांचें कि क्या सहायक बिंदु मूल तक पहुंच गया है; यदि नहीं, तो कोई चौराहा नहीं होना चाहिए। यदि वह मूल तक पहुंच गई, तो बिंदु को सिम्प्लेक्स में जोड़ें।
   
   इस मामले में, सहायक बिंदु मूल तक पहुंच गया है।
   
   दिशा: (0,-1)
   
   समर्थन: (0,-3)
   
   supportPoint.Dot (दिशा): 3
   
   

     // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); 

   
   
5. इस स्तर पर, सिम्प्लेक्स एक सेगमेंट है, इसलिए इसमें अंदर का मूल बिंदु नहीं हो सकता है; एक नई दिशा को परिभाषित करते हैं जिसमें सहायक बिंदु को देखना है।
   
   

     direction = simplex.CalculateDirection(); 

   
   
   1. हम सिम्प्लेक्स में जोड़े गए अंतिम बिंदु को लेते हैं और मूल की दिशा निर्धारित करते हैं, यह इस बिंदु का पारस्परिक होगा।
      
      a: (0,-3) ao: (0,3)
      
      

        CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { 

   2. चूंकि सिम्प्लेक्स एक खंड है, एक त्रिकोण नहीं है, हम सेगमेंट के दूसरे बिंदु को लेते हैं और सिम्प्लेक्स के सेगमेंट की गणना करते हैं।
      
      b: (0,2) ab: (0,5)
      
      

        // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); 

   3. हम इस सेगमेंट के लिए लंबवत गणना करते हैं और सत्यापित करते हैं कि यह मूल के लिए निर्देशित है। यह अगले सहायक बिंदु के लिए नई दिशा होगी।
      
      abPerp: (5, 0)
      
      abPerp.Dot (ao) 0
      
      abPerp: (-5, 0)
      
      
      
      
      

        // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; 

6. अब हमारे पास अगले सहायक बिंदु की खोज करने की दिशा है। हम चक्र की शुरुआत में लौटते हैं और इसे बाहर नहीं निकलते हैं, क्योंकि हमारे पास एक दिशा है, और चौराहा अभी तक नहीं मिला है।
   
   दिशा: (-5, 0)
   
   समर्थन: (-2,-2)
   
   supportPoint.Dot (दिशा): 10
   
   सहायक बिंदु मूल तक पहुंच गया है, इसलिए हम यह नहीं कह सकते कि कोई चौराहा नहीं है।
   
   

     while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } 

7. एक त्रिभुज बनाते हुए, सिम्प्लेक्स में एक नया सहायक बिंदु जोड़ें। इस त्रिकोण में मूल हो सकता है, और यदि ऐसा है, तो सिम्प्लेक्स undefined वापस आ जाएगा, और खोज के लिए नई दिशा नहीं।
   
   

     // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); 

   
   
   1. त्रिकोण के सिंप्लेक्स के बिंदुओं को लें।
      a: (-2,-2) b: (0,-3) c: (0,2) ao: (2,2)
      
      

        // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; 

   2. सेगमेंट ab और ac लें।
      
      ab: (2,-1) एसी: (2,4)
      
      

        // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); 

   3. हम सिम्पलेक्स से निर्देशित सेगमेंट एब के लिए लंबवत गणना करते हैं।
      
      abperp: (-1,-2)
      
      

        // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } 

   4. हम यह निर्धारित करते हैं कि मूल एबीसी से परे सिम्प्लेक्स के बाहर है।
      
      abPerp.Dot (ao): -6
      
      उत्पत्ति एब से परे सिम्प्लेक्स के बाहर नहीं होती है।
      
      
      
      
      

        if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } 

   5. हम सिम्प्लेक्स से निर्देशित सेगमेंट के लिए लंबवत गणना करते हैं।
      
      acPerp: (-4,2)
      
      

        // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } 

   6. निर्धारित करें कि मूल एसी से परे सिम्प्लेक्स के बाहर है या नहीं।
      
      acPerp.Dot (ao): -4
      
      मूल ab के परे सिंप्लेक्स के बाहर नहीं है।
      
      
      
      
      

        // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } 

   7. चूँकि इस पुनरावृत्ति में AB और AC की जाँच की गई थी, और हम जानते हैं कि BC की पिछली पुनरावृत्ति में जाँच की गई थी, मूल को सिम्प्लेक्स के अंदर होना चाहिए, इसलिए एक टक्कर / चौराहे का पता लगाया गया था - इस बारे में सूचित करते हुए, फ़ंक्शन undefined वापस आ जाएगा।
      
      
      
8. चूंकि एक टकराव का पता चला है, लूप बाहर निकल गया है और दो आंकड़ों के बीच टकराव के बारे में Collision जानकारी वापस आ गई है।
   
   

     direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); 

निष्कर्ष

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