ذهبت إلى دراسة عمليات التعرف على الاصطدام ، وهذا قادني إلى خوارزمية جيلبرت جونسون كيرثي (GJK).

تتم كتابة جميع أمثلة التعليمات البرمجية في المنشور في TypeScript. تستخدم الأمثلة الهياكل التي قمت بإنشائها والتي لم تتم مناقشتها بالتفصيل في المنشور. إنها بسيطة ويمكن عرضها في مستودع جيثب:

• Vector
• IShape
• Collision

يتم تخزين كل الشفرة من المنشور في مستودع جيثب:

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

تم كتابة المنشور على أساس هذا المقال والفيديو الموصى به فيه:

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

مقدمة

GJK هي خوارزمية مصممة لتحديد تقاطع شكلين محدب. إنها بسيطة ويتم تنفيذها بمساعدة من "وظيفة مساعدة" معممة تتيح لك استخدام نهج أكثر عمومية - بنفس الطريقة ، يمكنك معالجة المضلعات والأشكال التي تتكون من منحنيات ، على سبيل المثال ، الحذف.

المعلومات المطلوبة

مينكوفسكي المبلغ

يستخدم GJK مفهوم يسمى مجموع Minkowski. يتم حساب SM عن طريق إضافة كل النقاط المكونة من رقمين. على سبيل المثال ، خذ الشكلين الموضحين أدناه:


الشكل أ (الأخضر):


الشكل ب (الأرجواني):


بأخذ قيم الشكل 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)

إذا أخذنا هذه القيم وقمنا بعمل رسم بياني منها ، فسوف نرى الشكل الذي سيكون النتيجة.

مبلغ مينكوفسكي للأرقام A و B:

لاحظ أن AD في الجدول والرسم البياني يتوافق مع A + D



لفهم مبلغ Minkowski بشكل أفضل ، يمكننا أن نتخيل أننا نأخذ الشكل A ونتجاوزه مع الخطوط العريضة لـ B. وسيكون الرقم الناتج هو مجموع Minkowski.

فرق مينكوفسكي

يستخدم GJK مجموعة متنوعة من مبلغ Minkowski ، حيث لا يتم أخذ A + B ، ولكن A - B. في المصادر التي قرأتها ، يسمى هذا "Minkowski Difference". يحتوي الفرق Minkowski على خاصية مثيرة للاهتمام: إذا تداخل / يتقاطع الرقمان ، فسيحتوي الفرق Minkowski الناتج على الأصل. وهذا هو أساس خوارزمية GJK.

بأخذ قيم الأشكال A و B ، يمكننا حساب فرق Minkowski:

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)

إذا أخذنا هذه القيم ووضعناها على الرسم البياني ، فسوف نرى الشكل الناتج.

فرق مينكوفسكي للأرقام A و B:

لاحظ أن AD في الجدول والرسم البياني يشير إلى A - D

خوارزمية

بناءً على هذه المفاهيم ، تعمل خوارزمية GJK على تحسينها. قد يستغرق حساب مجموع Minkowski الكثير من الوقت ، خاصةً إذا قمت بالتحقق من تقاطع رقمين يتكونان من عدة نقاط. لتجنب هذا ، يستخدم GJK مفهومين رئيسيين: وظائف المساعد والبسيطة.

وظائف المساعد

الوظائف الإضافية هي طريقة لأخذ نقطة على حافة الفرق Minkowski دون إنشاء الشكل بأكمله. وظيفة المساعد تحصل على رقمين مقارنة ، والاتجاه الذي يجب التحقق منه. ثم تستقبل الوظيفة المساعدة من كل شخصية نقطة أبعد من اتجاهين متعاكسين. باستخدام هاتين النقطتين الأكثر بعدًا ، يمكنك حساب النقطة الإضافية على شكل فرق Minkowski. نأخذ نقاطًا من اتجاهين متعاكسين لأننا نحصل على نقطة في فرق Minkowski ، الأمر الذي سيمنحنا أكبر مساحة ، أي أنه سيكون هناك احتمال أكبر بأن نرفق الأصل في الشكل. نظرًا لأن الفرق 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،0) للشكلين A و B:

1. خذ النقطة الأكثر بعدًا من الشكل أ ؛ اتضح أن النقطة ب (1 ، -1) . (يمكنك حسابها ، كما تفعل الخوارزمية الموضحة أعلاه ، أو مجرد رؤيتها من خلال النظر إلى الرسم البياني).
2. خذ النقطة الأكثر بعدًا من الشكل B ؛ اتضح أن تكون النقطة F (-1 ، 1) .
3. احسب B - F ؛ اتضح أن تكون النقطة BF (2 ، -2) - ستكون مساعدة .

simplices

البسيط هو عينة من النقاط على طول الرقم الفرق Minkowski. يمكن للسمبلكس أن يحتوي على ثلاث نقاط. يستخدمهم 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 الحالي - إذا كان الأمر كذلك ، فسوف تُرجع undefined ؛ وإلا ، فسوف يُرجع اتجاهًا جديدًا للحصول على نقطة مساعدة ، والتي يجب إضافتها إلى simplex.

 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; } } 

قد تتساءل: لماذا لا نتحقق من شريحة BC؟ لأننا يمكن أن نستبعد دون قيد أو شرط أن الأصل على طول عمودي. نظرًا لأن النقطتين B و C موجودة بالفعل في simplex ، ولم تتم إضافتها فقط ، فنحن نعرف أنه تم تسجيلهما في التكرار السابق. يمكن التحقق منها إما كجزء من مثلث ، أو كقطعة من النقطتين الأوليين في simplex - لا يهم. لذلك ، يمكننا تخطي فحص شريحة BC بأمان.

شرح مفصل

لقد حصلنا على الكثير من التعليمات البرمجية ، ويبدو الأمر مربكًا. أدناه سوف أقوم بتحليل خطوات الخوارزمية للأشكال A و B الموضحة أعلاه.

النقاط من الشكلين A و B:

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. تحقق مما إذا كانت النقطة المساعدة قد وصلت إلى الأصل ؛ إن لم يكن ، لا ينبغي أن يكون هناك تقاطع. إذا وصلت إلى الأصل ، فقم بإضافة النقطة إلى simplex.
   
   في هذه الحالة ، وصلت النقطة المساعدة إلى الأصل.
   
   الاتجاه: (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. في هذه المرحلة ، يكون simplex جزءًا ، لذلك لا يمكن أن يحتوي على نقطة أصل بداخله ؛ تحديد اتجاه جديد للبحث عن نقطة مساعدة.
   
   

     direction = simplex.CalculateDirection(); 

   
   
   1. نأخذ النقطة الأخيرة التي أضيفت إلى simplex ونحدد الاتجاه إلى الأصل ، وسيكون هذا هو المعاملة بالمثل لهذه النقطة.
      
      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. نظرًا لأن simplex عبارة عن قطعة ، وليست مثلثًا ، فإننا نأخذ النقطة الثانية من المقطع ونحسب قطعة simplex.
      
      ب: (0,2) أب: (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. أضف نقطة مساعدة جديدة إلى simplex ، وخلق مثلثًا. قد يحتوي هذا المثلث على الأصل ، وإذا كان الأمر كذلك ، فسوف يعود البسيط 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) ac: (2,4)
      
      

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

   3. نحسب العمودي على الجزء ab ، الموجه من simplex.
      
      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. نحدد ما إذا كان الأصل خارج simplex وراء ab.
      
      abPerp.Dot (ao): -6
      
      الأصل لا يكمن خارج البسيط وراء أب.
      
      
      
      
      

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

   5. نحسب عمودي على الجزء ac الموجهة من البسيط.
      
      acPerp: (-4,2) -4.2 (-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
      
      الأصل ليس خارج البسيط وراء أب.
      
      
      
      
      

        // 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 على روابط بموارد جيدة في خوارزميات التعرف على التصادم / الاستجابة المختلفة ؛ إذا كنت ترغب في توسيع GJK ، فعليك دراستها.