دروس فيزياء ألعاب الفيديو - الجزء الثاني: كشف اصطدام الأجسام الصلبة

هذا هو الجزء الثاني من سلسلتنا المكونة من ثلاثة أجزاء حول فيزياء ألعاب الفيديو. لبقية هذه السلسلة ، انظر:

الجزء الأول: مقدمة لديناميكيات الجسم الصلب
الجزء الثالث: محاكاة مقيدة للجسم الصلب

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

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

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

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

فيزياء الاصطدام في ألعاب الفيديو

في سياق محاكاة الجسم الجامدة ، يحدث الاصطدام عندما يتقاطع شكلا جسمين صلبين ، أو عندما تقل المسافة بين هذين الشكلين عن تفاوت ضئيل.

إذا كان لدينا عدد n من الأجسام في محاكاتنا ، فإن التعقيد الحسابي لاكتشاف الاصطدامات مع الاختبارات الزوجية هو O ( n 2 ) ، وهو رقم يجعل علماء الكمبيوتر يرتعدون. يزداد عدد الاختبارات الزوجية بشكل تربيعي مع عدد الأجسام ، وتحديد ما إذا كان تصادم شكلين ، في مواضع واتجاهات عشوائية ، ليس رخيصًا بالفعل. من أجل تحسين عملية الكشف عن الاصطدام ، قمنا بتقسيمها بشكل عام إلى مرحلتين: مرحلة واسعة ومرحلة ضيقة .

المرحلة العريضة هي المسؤولة عن إيجاد أزواج من الأجسام الصلبة التي يحتمل أن تصطدم ، واستبعاد الأزواج التي لا تتصادم بالتأكيد ، من بين مجموعة الأجسام الموجودة في المحاكاة. يجب أن تكون هذه الخطوة قادرة على القياس جيدًا مع عدد الأجسام الصلبة للتأكد من بقائنا تحت التعقيد الزمني O ( n 2 ) . لتحقيق ذلك ، تستخدم هذه المرحلة عمومًا تقسيمًا للمساحة مقرونًا بأحجام إحاطة تحدد حدًا أعلى للتصادم.

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

سنتحدث في الأقسام التالية عن بعض الخوارزميات التي يمكن استخدامها في المرحلة الواسعة والمرحلة الضيقة.

مرحلة واسعة

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

بعض الأنواع الشائعة من الأحجام المحيطة هي مربعات إحاطة موجهة (OBB) ، ودوائر ثنائية الأبعاد ، ومجالات ثلاثية الأبعاد. لنلقِ نظرة على أحد أبسط الأحجام المحيطة: المربعات المحيطة بمحاذاة المحور (AABB) .

تحظى AABBs بالكثير من الحب من مبرمجي الفيزياء لأنها بسيطة وتقدم مقايضات جيدة. يمكن تمثيل AABB ثنائي الأبعاد بهيكل مثل هذا في لغة C:

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

يمثل حقل min موقع الزاوية اليسرى السفلية من المربع ويمثل الحقل max الزاوية اليمنى العليا.

لاختبار ما إذا كان يتقاطع اثنان من AABB ، علينا فقط معرفة ما إذا كانت إسقاطاتهم تتقاطع على جميع محاور الإحداثيات:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

هذا الرمز له نفس منطق وظيفة b2TestOverlap من محرك Box2D (الإصدار 2.3.0). تحسب الفرق بين الحد min والحد max لكلا AABBs ، في كلا المحورين ، في كلا الأمرين. إذا كانت أي من هذه القيم أكبر من الصفر ، فلا تتقاطع AABBs.

على الرغم من أن اختبار التداخل AABB رخيص ، إلا أنه لن يساعد كثيرًا إذا ما زلنا نجري اختبارات زوجية لكل زوج محتمل حيث لا يزال لدينا التعقيد الزمني غير المرغوب فيه O ( n 2 ) . لتقليل عدد اختبارات التداخل AABB ، يمكننا استخدام نوع من تقسيم المساحة ، والذي يعمل على نفس مبادئ فهارس قاعدة البيانات التي تسرع الاستعلامات. (قواعد البيانات الجغرافية ، مثل PostGIS ، تستخدم في الواقع هياكل وخوارزميات بيانات مماثلة لفهارسها المكانية.) في هذه الحالة ، على الرغم من أن AABBs سوف تتحرك باستمرار ، لذلك بشكل عام ، يجب علينا إعادة إنشاء المؤشرات بعد كل خطوة من خطوات المحاكاة.

هناك الكثير من خوارزميات تقسيم المساحة وهياكل البيانات التي يمكن استخدامها لهذا الغرض ، مثل الشبكات الموحدة ، ورباعيات في 2D ، وثمانية ثلاثية الأبعاد ، والتجزئة المكانية. دعونا نلقي نظرة فاحصة على خوارزميتين شائعتين للتقسيم المكاني: الفرز والمسح ، والتدرجات الهرمية للحجم المحيط (BVH).

خوارزمية الفرز والمسح

تعد طريقة الفرز والمسح (تُعرف أيضًا باسم المسح والتقليم ) أحد الخيارات المفضلة بين مبرمجي الفيزياء لاستخدامها في محاكاة الجسم الجامدة. محرك Bullet Physics ، على سبيل المثال ، لديه تنفيذ لهذه الطريقة في فئة btAxisSweep3 .

إن إسقاط أحد AABB على محور إحداثي واحد هو في الأساس فترة [ b ، e ] (أي البداية والنهاية). في المحاكاة لدينا ، سيكون لدينا العديد من الأجسام الصلبة ، وبالتالي العديد من AABBs ، وهذا يعني العديد من الفواصل الزمنية. نريد معرفة الفترات المتقاطعة.

في خوارزمية الفرز والمسح ، ندرج جميع قيم b و e في قائمة واحدة ونفرزها تصاعديًا حسب القيم العددية. ثم نقوم بمسح القائمة أو اجتيازها. عندما يتم العثور على قيمة b ، يتم تخزين الفاصل الزمني المقابل لها في قائمة منفصلة من الفترات النشطة ، وكلما تمت مصادفة قيمة e ، تتم إزالة الفاصل الزمني المقابل لها من قائمة الفترات النشطة. في أي لحظة ، تتقاطع جميع الفواصل الزمنية النشطة. (راجع أطروحة الدكتوراه لديفيد باراف ، ص 52 للحصول على التفاصيل. أقترح استخدام هذه الأداة عبر الإنترنت لعرض ملف التذييل.) يمكن إعادة استخدام قائمة الفواصل الزمنية في كل خطوة من خطوات المحاكاة ، حيث يمكننا إعادة الفرز بكفاءة هذه القائمة باستخدام فرز الإدراج ، وهو أمر جيد في فرز القوائم التي تم فرزها تقريبًا.

في بعدين وثلاثة أبعاد ، يؤدي تشغيل الفرز والمسح ، كما هو موضح أعلاه ، عبر محور إحداثي واحد إلى تقليل عدد اختبارات تقاطع AABB المباشرة التي يجب إجراؤها ، ولكن قد يكون المردود أفضل على محور إحداثيات واحد من الآخر. لذلك ، يتم تنفيذ اختلافات أكثر تعقيدًا من خوارزمية الفرز والاكتساح. في كتابه Real-Time Collision Detection (صفحة 336) ، يقدم Christer Ericson تباينًا فعالاً حيث يخزن جميع AABBs في مصفوفة واحدة ، ولكل تشغيل من الفرز والمسح ، يتم اختيار محور إحداثي واحد ويتم فرز المصفوفة حسب min قيمة لـ AABBs في المحور المختار ، باستخدام الترتيب السريع. بعد ذلك ، يتم اجتياز المصفوفة ويتم إجراء اختبارات التداخل AABB. لتحديد المحور التالي الذي يجب استخدامه للفرز ، يتم حساب تباين مركز AABBs ، ويتم اختيار المحور ذي التباين الأكبر للخطوة التالية.

الأشجار ذات الحجم الديناميكي المحيط

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

Dbvt عبارة عن شجرة ثنائية تحتوي كل عقدة فيها على AABB الذي يحد جميع AABBs لأبنائها. توجد AABBs للأجسام الصلبة نفسها في العقد الورقية. عادةً ، يتم "الاستعلام" عن Dbvt عن طريق إعطاء AABB الذي نرغب في اكتشاف التقاطعات فيه. هذه العملية فعالة لأن العناصر الفرعية للعقد التي لا تتقاطع مع AABB الذي تم الاستعلام عنه لا يحتاجون إلى اختبار التداخل. على هذا النحو ، يبدأ استعلام تصادم AABB من الجذر ، ويستمر بشكل متكرر من خلال الشجرة فقط لعقد AABB التي تتقاطع مع AABB الذي تم الاستعلام عنه. يمكن موازنة الشجرة من خلال دوران الأشجار ، كما هو الحال في شجرة AVL.

يحتوي Box2D على تطبيق متطور لـ Dbvt في فئة b2DynamicTree . تعتبر فئة b2BroadPhase مسؤولة عن تنفيذ المرحلة الواسعة ، وتستخدم مثيل b2DynamicTree لتنفيذ استعلامات AABB.

المرحلة الضيقة

بعد المرحلة الواسعة من فيزياء تصادم ألعاب الفيديو ، لدينا مجموعة من الأزواج من الأجسام الصلبة التي يحتمل أن تتصادم. وهكذا ، لكل زوج ، بالنظر إلى شكل وموضع واتجاه كلا الجسمين ، نحتاج إلى معرفة ما إذا كانا ، في الواقع ، متصادمين ؛ إذا كانت متقاطعة أو إذا كانت المسافة بينهما تقع ضمن قيمة تسامح صغيرة. نحتاج أيضًا إلى معرفة نقاط الاتصال بين الأجسام المتصادمة ، لأن هذا ضروري لحل الاصطدامات لاحقًا.

الأشكال المحدبة والمقعرة

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

في الشكل المحدب ، دائمًا ما يقع جزء خطي بين أي نقطتين داخل الشكل تمامًا داخل الشكل. ومع ذلك ، بالنسبة للشكل المقعر (أو "غير المحدب") ، فإن الشيء نفسه لا ينطبق على جميع مقاطع الخط الممكنة التي تربط النقاط في الشكل. إذا كان بإمكانك العثور على قطعة خطية واحدة على الأقل تقع خارج الشكل على الإطلاق ، فإن الشكل مقعر.

من الناحية الحسابية ، من المستحسن أن تكون جميع الأشكال محدبة في محاكاة ، نظرًا لأن لدينا الكثير من خوارزميات اختبار المسافة والتقاطع القوية التي تعمل مع الأشكال المحدبة. ومع ذلك ، لن تكون كل الأشياء محدبة ، وعادة ما نتعامل معها بطريقتين: الهيكل المحدب والتحلل المحدب.

بدن الشكل المحدب هو أصغر شكل محدب يحتوي عليه بالكامل. بالنسبة إلى المضلع المقعر ذي البعدين ، سيكون مثل دق مسمار على كل رأس ولف شريط مطاطي حول جميع المسامير. لحساب الهيكل المحدب لمضلع أو متعدد السطوح ، أو بشكل أكثر عمومًا ، لمجموعة من النقاط ، فإن الخوارزمية الجيدة لاستخدامها هي خوارزمية الهيكل السريع ، والتي لها متوسط ​​تعقيد زمني لـ O ( n log n ) .

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

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

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

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

اختبار التقاطعات - نظرية المحور الفاصل

تنص نظرية المحور الفاصل (SAT) على أن شكلين محدبين لا يتقاطعان إذا وفقط إذا كان هناك محور واحد على الأقل حيث لا تتقاطع الإسقاطات المتعامدة للأشكال على هذا المحور.

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

تحتوي محركات فيزياء اللعبة على عدد من الفئات المختلفة من الأشكال ، مثل الدوائر (المجالات ثلاثية الأبعاد) ، والحواف (جزء من خط واحد) ، والمضلعات المحدبة (الأشكال المتعددة السطوح ثلاثية الأبعاد). لكل زوج من أنواع الأشكال ، لديهم خوارزمية محددة لاكتشاف الاصطدام. ربما يكون أبسطها هو خوارزمية الدائرة:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

على الرغم من أن اختبار SAT ينطبق على الدوائر ، إلا أنه من الأسهل كثيرًا التحقق مما إذا كانت المسافة بين مراكزها أصغر من مجموع أنصاف أقطارها. لهذا السبب ، يتم استخدام SAT في خوارزمية اكتشاف الاصطدام لأزواج محددة من فئات الأشكال ، مثل المضلع المحدب مقابل المضلع المحدب (أو متعدد السطوح في 3D).

لأي زوج من الأشكال ، هناك عدد لا حصر له من المحاور يمكننا اختبارها للفصل. وبالتالي ، فإن تحديد أي محور يجب اختباره أولاً أمر بالغ الأهمية لتنفيذ SAT بكفاءة. لحسن الحظ ، عند اختبار اصطدام زوج من المضلعات المحدبة ، يمكننا استخدام قواعد الحواف كمحاور فصل محتملة. المتجه الطبيعي n للحافة يكون عموديًا على متجه الحافة ويشير خارج المضلع. لكل حافة من كل مضلع ، نحتاج فقط إلى معرفة ما إذا كانت جميع رءوس المضلع الآخر أمام الحافة.

إذا نجح أي اختبار - أي إذا كانت جميع رؤوس المضلع الآخر أمامه لأي حافة - فلا تتقاطع المضلعات. يقدم الجبر الخطي صيغة سهلة لهذا الاختبار: بإعطاء حافة على الشكل الأول مع الرؤوس a و b والرأس v على الشكل الآخر ، إذا كانت ( v - a ) · n أكبر من الصفر ، فإن الرأس يكون في المقدمة من الحافة.

بالنسبة إلى الأشكال المتعددة السطوح ، يمكننا استخدام القواعد القياسية للوجه وأيضًا حاصل الضرب العرضي لجميع تركيبات الحواف من كل شكل. هذا يبدو وكأنه الكثير من الأشياء للاختبار ؛ ومع ذلك ، لتسريع الأمور ، يمكننا تخزين آخر محور فصل استخدمناه مؤقتًا ومحاولة استخدامه مرة أخرى في الخطوات التالية من المحاكاة. إذا لم يعد المحور الفاصل المخزن مؤقتًا يفصل الأشكال بعد الآن ، فيمكننا البحث عن محور جديد يبدأ من الوجوه أو الحواف المجاورة للوجه أو الحافة السابقة. ينجح ذلك لأن الأجسام غالبًا لا تتحرك أو تدور كثيرًا بين الخطوات.

يستخدم Box2D SAT لاختبار ما إذا كان مضلعان محدبان يتقاطعان في خوارزمية اكتشاف التصادم متعدد الأضلاع في b2CollidePolygon.cpp.

مسافة الحوسبة - خوارزمية جيلبرت - جونسون - كيرثي

في العديد من حالات فيزياء التصادمات ، نريد اعتبار الأشياء متصادمة ليس فقط إذا كانت متقاطعة بالفعل ، ولكن أيضًا إذا كانت قريبة جدًا من بعضها البعض ، مما يتطلب منا معرفة المسافة بينهما. تحسب خوارزمية Gilbert-Johnson-Keerthi (GJK) المسافة بين شكلين محدبين وأيضًا أقرب نقاطهما. إنها خوارزمية أنيقة تعمل مع تمثيل ضمني للأشكال المحدبة من خلال وظائف الدعم ، ومجموع Minkowski ، والبساطة ، كما هو موضح أدناه.

وظائف الدعم

ترجع دالة الدعم s A ( d ) نقطة على حدود الشكل A والتي لها أعلى إسقاط على المتجه d . رياضياً ، يحتوي على أعلى ناتج نقطي مع d . وهذا ما يسمى نقطة الدعم ، وتعرف هذه العملية أيضًا باسم تخطيط الدعم . هندسيًا ، هذه النقطة هي أبعد نقطة على الشكل في اتجاه d .

من السهل نسبيًا العثور على نقطة دعم على مضلع. للحصول على نقطة دعم للمتجه d ، عليك فقط أن تدور عبر رؤوسها وتجد الذي يحتوي على أعلى حاصل ضرب نقطي مع d ، مثل هذا:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

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

للحصول على نقطة دعم للكرة تتمحور حول الأصل ، علينا فقط تسوية d (أي حساب d / || d || ، وهو متجه بطول 1 (طول الوحدة) لا يزال يشير في نفس الاتجاه من d ) ثم نضربها في نصف قطر الكرة.

تحقق من ورقة Gino van den Bergen للعثور على مزيد من الأمثلة لوظائف الدعم للأسطوانات والأقماع ، من بين الأشكال الأخرى.

بالطبع ، سيتم إزاحة كائناتنا وتدويرها من الأصل في فضاء المحاكاة ، لذلك نحتاج إلى أن نكون قادرين على حساب نقاط الدعم للشكل المحول. نستخدم التحويل التقريبي T ( x ) = R x + c لإزاحة كائناتنا وتدويرها ، حيث c هو متجه الإزاحة و R هي مصفوفة الدوران . يقوم هذا التحويل أولاً بتدوير الكائن حول الأصل ، ثم يترجمه. وظيفة الدعم للشكل المحول أ هي:

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

يتم تعريف مجموع مينكوفسكي لشكلين أ و ب على النحو التالي:

هذا يعني أننا نحسب مجموع جميع النقاط الواردة في A و B. والنتيجة مثل تضخيم أ مع ب .

وبالمثل ، نحدد اختلاف Minkowski على النحو التالي:

والتي يمكننا كتابتها أيضًا كمجموع Minkowski لـ A مع -B :

بالنسبة للمحدبين A و B ، يكون A⊕B محدبًا أيضًا.

إحدى الخصائص المفيدة لاختلاف Minkowski هي أنه إذا كان يحتوي على أصل الفضاء ، فإن الأشكال تتقاطع ، كما يتضح من الصورة السابقة. لماذا هذا؟ لأنه إذا تقاطع شكلان ، فلديهما نقطة مشتركة واحدة على الأقل ، والتي تقع في نفس المكان في الفضاء ، والفرق بينهما هو متجه الصفر ، وهو في الواقع الأصل.

ميزة أخرى لطيفة لاختلاف Minkowski هي أنه إذا لم يحتوي على الأصل ، فإن الحد الأدنى للمسافة بين الأصل وفرق Minkowski هو المسافة بين الأشكال.

يتم تحديد المسافة بين شكلين على النحو التالي:

بمعنى آخر ، المسافة بين A و B هي طول أقصر متجه يمتد من A إلى B. هذا المتجه موجود في A⊖B وهو ذو أصغر طول ، وهو بالتالي الأقرب إلى الأصل.

ليس من السهل عمومًا بناء مجموع Minkowski بشكل صريح من شكلين. لحسن الحظ ، يمكننا استخدام دعم الخرائط هنا أيضًا ، نظرًا لأن:

البسيط

تبحث خوارزمية GJK بشكل متكرر عن نقطة فرق Minkowski الأقرب إلى الأصل. يقوم بذلك عن طريق بناء سلسلة من المفردات التي تكون أقرب إلى الأصل في كل تكرار. البسيط - أو بشكل أكثر تحديدًا ، k-simplex لعدد صحيح k - هو الهيكل المحدب لـ k + 1 نقاط مستقلة بشكل وثيق في فضاء البعد k. أي ، إذا كانت هناك نقطتان ، فلا يجب أن تتطابق ، بالنسبة لثلاث نقاط ، يجب أيضًا ألا تقع على نفس الخط ، وإذا كانت لدينا أربع نقاط ، فيجب ألا تقع على نفس المستوى. ومن ثم ، فإن 0-simplex عبارة عن نقطة ، و 1-simplex عبارة عن مقطع خطي ، و 2-simplex مثلث ، و 3-simplex عبارة عن رباعي السطوح. إذا أزلنا نقطة من البسيط ، فإننا نقلل من أبعادها بمقدار واحد ، وإذا أضفنا نقطة إلى البسيط ، فإننا نزيد من أبعادها بمقدار واحد.

GJK في العمل

دعونا نجمع كل هذا معًا لنرى كيف يعمل GJK. لتحديد المسافة بين الشكلين A و B ، نبدأ بأخذ فرق Minkowski الخاص بهم A⊖B . نحن نبحث عن أقرب نقطة إلى الأصل على الشكل الناتج ، لأن المسافة إلى هذه النقطة هي المسافة بين الشكلين الأصليين. نختار نقطة ما v في A⊖B ، والتي ستكون تقريب المسافة لدينا. نحدد أيضًا مجموعة نقاط فارغة W ، والتي ستحتوي على النقاط الموجودة في الاختبار البسيط الحالي.

ثم ندخل في حلقة. نبدأ بالحصول على نقطة الدعم w = s A⊖B (- v ) ، النقطة على A⊖B التي يكون إسقاطها على v أقرب إلى نقطة الأصل.

إذا كان || ث || لا يختلف كثيرًا عن || ت || ولم تتغير الزاوية بينهما كثيرًا (وفقًا لبعض التفاوتات المحددة مسبقًا) ، فهذا يعني أن الخوارزمية قد تقاربت ويمكننا العودة || ت || مثل المسافة.

خلاف ذلك ، نضيف w إلى W. إذا كان الهيكل المحدب لـ W (أي البسيط) يحتوي على الأصل ، فإن الأشكال تتقاطع ، وهذا يعني أيضًا أننا انتهينا. بخلاف ذلك ، نجد النقطة في البسيط الأقرب إلى الأصل ثم نعيد ضبط v ليكون هذا التقريب الأقرب الجديد. أخيرًا ، نقوم بإزالة أي نقاط في W لا تساهم في حساب أقرب نقطة. (على سبيل المثال ، إذا كان لدينا مثلث ، وكانت أقرب نقطة إلى الأصل تقع في أحد حوافه ، فيمكننا إزالة النقطة من W التي ليست رأس هذه الحافة.) ثم نكرر هذه الخطوات نفسها حتى الخوارزمية يتقارب.

تُظهر الصورة التالية مثالاً لأربعة تكرارات لخوارزمية GJK. يمثل الكائن الأزرق اختلاف Minkowski A⊖B والمتجه الأخضر هو v . يمكنك أن ترى هنا كيف يتجه v إلى أقرب نقطة إلى نقطة الأصل.

للحصول على شرح مفصل ومتعمق لخوارزمية GJK ، راجع مقالة تنفيذ GJK السريع والقوي لاكتشاف الاصطدام للأجسام المحدبة ، بقلم جينو فان دن بيرغن. تحتوي المدونة الخاصة بمحرك الفيزياء dyn4j أيضًا على منشور رائع على GJK.

Box2D لديه تطبيق خوارزمية GJK في b2Distance.cpp ، في وظيفة b2Distance . إنه يستخدم GJK فقط خلال وقت حساب التأثير في خوارزمية الكشف عن الاصطدام المستمر (موضوع سنناقشه لاحقًا).

يستخدم محرك الفيزياء Chimpunk GJK لجميع عمليات اكتشاف الاصطدام ، ويتم تنفيذه في cpCollision.c ، في وظيفة GJK . إذا أبلغت خوارزمية GJK عن التقاطع ، فلا تزال بحاجة إلى معرفة نقاط الاتصال ، إلى جانب عمق الاختراق. للقيام بذلك ، تستخدم خوارزمية Polytope الموسعة ، والتي سنستكشفها بعد ذلك.

تحديد عمق الاختراق - توسيع خوارزمية Polytope

كما هو مذكور أعلاه ، إذا كان الشكلان A و B متقاطعين ، فسيقوم GJK بإنشاء حرف W بسيط يحتوي على الأصل ، داخل فرق Minkowski A⊖B . في هذه المرحلة ، نعلم فقط أن الأشكال تتقاطع ، ولكن في تصميم العديد من أنظمة الكشف عن الاصطدام ، من المستحسن أن نكون قادرين على حساب مقدار التقاطع الذي لدينا ، وما هي النقاط التي يمكننا استخدامها كنقاط اتصال ، بحيث نتعامل مع الاصطدام بطريقة واقعية. تسمح لنا خوارزمية Polytope الموسعة (EPA) بالحصول على تلك المعلومات ، بدءًا من النقطة التي توقفت عندها GJK: باستخدام بسيط يحتوي على الأصل.

عمق الاختراق هو طول الحد الأدنى لمتجه الترجمة (MTV) ، وهو أصغر متجه يمكننا من خلاله ترجمة شكل متقاطع لفصله عن الشكل الآخر.

عندما يتقاطع شكلان ، فإن اختلاف Minkowski الخاص بهما يحتوي على الأصل ، والنقطة الموجودة على حدود اختلاف Minkowski الأقرب إلى الأصل هي MTV. تجد خوارزمية وكالة حماية البيئة هذه النقطة من خلال توسيع البسيط الذي أعطتنا إياه GJK في شكل مضلع ؛ قسمة حوافه على التوالي برؤوس جديدة.

أولاً ، نجد حافة البسيط الأقرب إلى الأصل ، ونحسب نقطة الدعم في فرق Minkowski في اتجاه طبيعي للحافة (أي عمودي عليها ويشير خارج المضلع). ثم نقوم بتقسيم هذه الحافة بإضافة نقطة الدعم هذه إليها. نكرر هذه الخطوات حتى لا يتغير طول المتجه واتجاهه كثيرًا. بمجرد تقارب الخوارزمية ، لدينا MTV وعمق الاختراق.

باستخدام GJK بالاشتراك مع وكالة حماية البيئة ، نحصل على وصف تفصيلي للتصادم ، بغض النظر عما إذا كانت الكائنات متقاطعة بالفعل ، أو قريبة بما يكفي لاعتبارها تصادمًا.

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

كشف الاصطدام المستمر

تؤدي تقنيات فيزياء ألعاب الفيديو المقدمة حتى الآن الكشف عن الاصطدام للحصول على لقطة ثابتة للمحاكاة. وهذا ما يسمى الكشف عن الاصطدام المنفصل ، ويتجاهل ما يحدث بين الخطوتين السابقة والحالية. لهذا السبب ، قد لا يتم الكشف عن بعض الاصطدامات ، خاصة بالنسبة للأجسام سريعة الحركة. تُعرف هذه المشكلة بالنفق .

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

وقت الاصطدام (أو وقت التلامس) t c هو لحظة الزمن عندما تكون المسافة بين جسمين صفراً. إذا تمكنا من كتابة دالة للمسافة بين جسمين على طول الوقت ، فإن ما نريد إيجاده هو أصغر جذر لهذه الدالة. وبالتالي ، فإن وقت حساب التأثير هو مشكلة اكتشاف الجذر .

بالنسبة لوقت حساب التأثير ، فإننا نأخذ في الاعتبار حالة (الموضع والاتجاه) للجسم في الخطوة السابقة في الوقت t i -1 ، وفي الخطوة الحالية في الوقت t i . لتبسيط الأمور ، نفترض وجود حركة خطية بين الخطوات.

لنبسط المشكلة بافتراض أن الأشكال عبارة عن دوائر. بالنسبة لدائرتين C 1 و C 2 ، بنصف قطر r 1 و r 2 ، حيث يتطابق مركز كتلتهما x 1 و x 2 مع النقطتين الوسطى (أي أنهما يدوران بشكل طبيعي حول مركز كتلتهما) ، يمكننا كتابة دالة المسافة كما:

بالنظر إلى الحركة الخطية بين الخطوات ، يمكننا كتابة الوظيفة التالية لموضع C 1 من t i -1 إلى t i

إنه استكمال خطي من x 1 ( t i -1 ) إلى x 1 ( t i ) . يمكن فعل نفس الشيء مع x 2 . لهذه الفترة ، يمكننا كتابة دالة مسافة أخرى:

اجعل هذا المقدار مساويًا للصفر وستحصل على معادلة تربيعية على t . يمكن إيجاد الجذور مباشرة باستخدام الصيغة التربيعية. إذا لم تتقاطع الدوائر ، فلن يكون للصيغة التربيعية حل. إذا فعلوا ذلك ، فقد ينتج عنه جذر واحد أو جذران. إذا كان له جذر واحد فقط ، فهذه القيمة هي وقت التأثير. إذا كان له جذران ، فإن أصغرهما هو وقت التأثير والآخر هو الوقت الذي تنفصل فيه الدوائر. لاحظ أن وقت التأثير هنا هو رقم من 0 إلى 1. إنه ليس وقتًا بالثواني ؛ إنه مجرد رقم يمكننا استخدامه لاستيفاء حالة الجثث إلى الموقع الدقيق الذي حدث فيه الاصطدام.

كشف التصادم المستمر لغير الدوائر

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

تعمل خوارزمية التقدم المحافظة على تحريك الأجسام إلى الأمام (وتدويرها) بشكل متكرر. في كل تكرار يحسب حدًا أعلى للإزاحة. يتم تقديم الخوارزمية الأصلية في أطروحة الدكتوراه لبريان ميرتيش (القسم 2.3.2) ، والتي تتناول الحركة البالستية للأجسام. يقدم هذا البحث الذي أعده إروين كومانز (مؤلف محرك فيزياء الرصاص) نسخة أبسط تستخدم سرعات خطية وزاوية ثابتة.

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

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

حل الاصطدامات

بمجرد اكتشاف التصادم ، من الضروري تغيير حركات الأجسام المتصادمة بطريقة واقعية ، مثل التسبب في ارتدادها عن بعضها البعض. في الدفعة التالية والأخيرة من هذه النظريات ، سنناقش بعض الطرق الشائعة لحل الاصطدامات في ألعاب الفيديو.

مراجع

إذا كنت مهتمًا بالحصول على فهم أعمق لفيزياء الاصطدام مثل خوارزميات وتقنيات اكتشاف الاصطدام ، فإن كتاب Real-Time Collision Detection من تأليف Christer Ericson أمر لا بد منه.

نظرًا لأن اكتشاف التصادم يعتمد بشكل كبير على الهندسة ، فإن مقالة Toptal's الهندسة الحسابية في Python: من النظرية إلى التطبيق هي مقدمة ممتازة للموضوع.