تضاريس فوكسل: الفيزياء

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

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

النموذج الأولي

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

على الرغم من أن محرك الفيزياء الخاص بنا مخصص، إلا أننا نستخدم بعض مكونات Bullet Physics للمرحلة الواسعة/المرحلة الضيقة (على وجه التحديد للأجسام المحدبة المعقدة والتفكيك المحدب، بالاعتماد على تطبيق GJK الخاص بـ Bullet وبعض الخوارزميات الأخرى)، لذا كان من المنطقي البدء بتصميم نموذج أولي للحل الذي سيعتمد بشكل كبير على Bullet.

وعلى غرار تخزين الفوكسل، نقسم العالم بأكمله إلى أجزاء ونمثل كل جزء ككائن تصادم؛ وهذا التقسيم أمر بالغ الأهمية لأن كل جزء يصبح وحدة تحديث لبيانات الفيزياء. ونظرًا لأن التضاريس يمكن تغييرها في أي وقت، فإن حجم الجزء يمثل توازنًا بين تكلفة التحديث (إذا كان الجزء كبيرًا جدًا، فسيتعين علينا في كل مرة نقوم فيها بتحديث فوكسل في ذلك الجزء أن ندفع تكلفة عالية لتحديث الجزء بأكمله. نفترض حاليًا أن التحديثات التراكمية معقدة للغاية بحيث يتعذر تنفيذها، حيث إن تغييرات الفوكسل يمكن أن تؤدي إلى تغييرات في طوبولوجيا الشبكة الناتجة) وتكلفة المقطع (إذا كان المقطع يتكون من 2^3 فوكسل، فسنحتاج إلى إنفاق الكثير من الوقت/الذاكرة لإدارة المقاطع). اتفقنا على 8^3 قطعة (للتذكير، الشخصية أطول بقليل من فوكسل واحد، مما يمنحك فكرة عن الحجم) كحل وسط بين هذه العوامل.

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

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

على الرغم من أن هذا النموذج الأولي ساعدنا على البدء، إلا أنه سلط الضوء على عدة مجالات رئيسية تحتاج إلى تحسين:

• بيانات المرحلة الواسعة غير دقيقة للغاية: كلما تقاطع أي كائن مع كتلة فوكسل 8^3، نحتاج إلى تشغيل خوارزمية المرحلة الضيقة على نقطة التلامس؛ وهذا يؤدي إلى الكثير من نقاط التلامس الزائدة التي لا تولد أي نقاط تلامس، خاصة في الكهوف حيث يمكن أن يتداخل كائن معلق في الهواء مع صندوق حدودي كبير نسبيًا دون أن يلامس أي شكل هندسي.
• بيانات المرحلة الضيقة كبيرة جدًا: بالنسبة لكل كتلة، ينتهي بنا الأمر بتخزين شبكة المثلثات التي تكون أقل إحكامًا من بيانات الفوكسل (نظرًا لأننا نحتاج إلى تخزين مواقع/مؤشرات الرؤوس) وبنية BVH الخاصة بـ Bullet والتي تُستخدم لتسريع التصادم، وهي أيضًا كبيرة جدًا.
• إن إنشاء بيانات المرحلة الضيقة بطيء للغاية: في حين أن خوارزمية الشبكة الخاصة بنا مُحسّنة بشكل كبير، فإن معالجة Bullet للشبكة الناتجة بطيئة نسبيًا (أبطأ بما يصل إلى 3 أضعاف من إنشاء الشبكة).

يشير هذا إلى أننا بحاجة إلى تغيير نهجنا لكل من المرحلة الواسعة والمرحلة الضيقة. دعونا نلقي نظرة على ما انتهينا به هناك.

المرحلة العريضة: البناء

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

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

من الضروري أن نتمكن من إنشاء هذا القناع دون الاعتماد على خوارزمية التشبيك (نظرًا لأن تشغيل خوارزمية التشبيك على التضاريس بأكملها يستغرق وقتًا طويلاً للغاية، وبسبب طريقة هيكلة كودنا، يجب أن تكون بيانات المرحلة الواسعة متاحة للعالم بأكمله)، لذلك نقوم بتقريب ذلك بالقول إنه إذا كان الفوكسل صلبًا، فيمكنه نظريًا إنشاء هندسة داخل أي من الفوكسلات المجاورة له (بما في ذلك الجيران المائلون، بإجمالي 3^3=27 فوكسل)، وملء كل هذه الفوكسلات بالرقم 1 في القناع؛ وتسمى هذه العملية بالتوسيع. يتطلب هذا أيضًا أن ننظر إلى الفوكسلات المجاورة للقطعة، لذا فإن مدخلاتنا هي صندوق فوكسل 10^3 ومخرجاتنا هي قناع بتات 8^3.

أخيرًا، لدينا نوعان من التلامس: الصلب والماء (نستخدم التلامس بين العناصر الأولية والماء لحساب الطفو)، لذلك ننشئ قناعين من البتات. تعمل العملية بشكل تقريبي على النحو التالي (لاحظ أن الصور في هذه المقالة تفترض 4^3 قطع بدلاً من 8^3):

لجعل هذه العملية سريعة، نقوم بالتوسيع باستخدام عمليات البتات. نبدأ أولاً بإنشاء قناع البتات 10^3 ونخزنه في مصفوفة من 10^2 عدد صحيح من 16 بت، ثم نقوم بتوسيع كل عدد صحيح أفقياً على النحو التالي:

data[y][z] = (data[y][z] &lt;&lt; <span style="color: #ff0000;">1</span>) | data[y][z] | (data[y][z] &gt;&gt; <span style="color: #ff0000;">1</span>);

ثم نقوم بالتوسيع على طول المحورين الآخرين في مرحلتين كما يلي:

temp[y][z] = data[y][z - <span style="color: #ff0000;">1</span>] | data[y][z] | (data[y][z + <span style="color: #ff0000;">1</span>];

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

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

المرحلة الواسعة للبتات: اختبار التداخل

الآن بعد أن قمنا بإنشاء بيانات المرحلة الواسعة (يتم ذلك عند تحميل المستوى ويتم إعادة إنشاء بيانات المرحلة الواسعة لكل قطعة كلما تغير أي فوكسل في القطعة)، يمكننا النظر في كيفية استخدامها.

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

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

تذكر أن لدينا 8^3 بت في كل قطعة؛ نقوم بتخزين كل شريحة Y (Y تشير لأعلى) من هذه القطعة في عدد صحيح 64 بت، حيث تحدد كل مجموعة متتالية من 8 بتات البيانات الخاصة بصف X. وبالتالي، فإن كل قناع هو مصفوفة بسيطة، ونقوم بتخزين قناع واحد للصلب وقناع واحد للماء:

<span style="color: #007788;">uint64_t</span> solid[<span style="color: #ff0000;">8</span>];
<span style="color: #007788;">uint64_t</span> water[<span style="color: #ff0000;">8</span>];

الآن نأخذ AABB للكائن، ونقوم بإسقاطه على مساحة القطعة ونحدد الحدود في مساحة الفوكسل. بعد ذلك، ننظر إلى امتدادات XZ للكائن حيث يتقاطع مع القطعة وننشئ قناعًا من 64 بت يحتوي على أرقام 1 حيث يتقاطع الكائن مع الفوكسلات على طول المستوى XZ:

ثم نكرر عبر جميع شرائح Y التي يغطيها الكائن ونجري اختبار بت بسيط لكل شريحة:

<span style="color: #006699;">if</span> (chunk.solid[y] &amp; mask)
     touchesSolid = <span style="color: #336666;">true</span>;

وهذا يتيح لنا فحص شريحة XZ الكاملة لقطعة ما — حتى 64 فوكسل! — بحثًا عن التداخل باستخدام تعليمة بسيطة (في البنى المعمارية ذات 32 بت، يستغرق هذا الاختبار حوالي 3 تعليمات)، مما يجعل إجراء استعلامات دقيقة على كائنات كبيرة الحجم أمرًا فعالًا للغاية. لتحسين الحمل الزائد للكائنات الصغيرة، نتأكد من إنشاء القناع لنطاقات XZ بأسرع ما يمكن. في حين أنه يمكننا القيام بذلك عن طريق التكرار عبر نطاقات XZ وتعيين البتات، نلاحظ أن القناع الذي لدينا هو في الواقع تقاطع قناعين يمثلان شريطًا رأسيًا وشريطًا أفقيًا؛ لكل اتجاه، نحتفظ بجدول بحث وندمج نتائج البحث للحصول على القناع الناتج:

<span style="color: #007788;">uint64_t&nbsp;<span style="color: #000000;">mask = masksVer[cmin.x][cmax.x] &amp; masksHor[cmin.z][cmax.z];
</span></span>

المرحلة الضيقة: التحليل والخطة

الآن بعد أن أصبحت بيانات المرحلة الواسعة في حالة جيدة، دعونا نلقي نظرة على المرحلة الضيقة. على مستوى عالٍ، كانت طريقة عمل المرحلة الضيقة القائمة على Bullet كما يلي:

• يخزن كل جزء مصفوفة من الرؤوس (كل رأس يحتوي على 3 أرقام عائمة للموضع و1 بايت للمادة)، ومصفوفة من الفهارس (كل مثلث يحتوي على 3 فهارس 16 بت)، وBVH (وهي شجرة AABB).
• عند إنشاء الشجرة، يتم تقسيم قائمة المثلثات بشكل متكرر إلى عقد حتى تحتوي العقد الطرفية على مثلث واحد فقط
• عند إجراء الكشف عن التصادم، يتم استخراج مجموعة من المثلثات من الشجرة باستخدام استعلام AABB بسيط؛ يتصادم كل مثلث مع الشكل الأساسي المستهدف باستخدام إما خوارزمية متخصصة لهذا الزوج (مثل المثلث-الكرة) أو خوارزمية GJK/EPA عامة. يتم إدخال النقاط الناتجة عن هذه التصادمات في بنية سيمبلكس تحتفظ بما يصل إلى 4 نقاط تلامس وتحاول تعظيم مساحة التلامس.
• عند إجراء عمليات إرسال الأشعة، يتم تشغيل استعلام بسيط لشجرة الأشعة-AABB؛ حيث تتقاطع كل عقدة ورقة مطابقة مع الشعاع. يتم الاحتفاظ بالنقطة الأقرب وإرجاعها كنتيجة.

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

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

تبلغ تكلفة الذاكرة الأساسية للشبكة الأولية حوالي 13 بايت لكل ركن (3 إحداثيات ذات نقطة عائمة و1 بايت للمادة) وحوالي 6 بايت لكل مثلث (لـ 3 مؤشرات 16 بت)، مما يصل إلى حوالي 12.5 بايت لكل مثلث نظرًا لوجود ضعف عدد المثلثات مقارنة بأعداد الأركان في المتوسط.

يستهلك Bullet BVH غير المقيس 64 بايت لكل عقدة، مما يصل إلى حوالي 128 بايت لكل مثلث (تحتاج بنية العقدة إلى 44 بايت فقط، ولكن يتم ملؤها إلى 64 بايت)، وهو ما يعادل حوالي 10 أضعاف تكلفة ذاكرة بيانات المثلث. كما يستغرق إنشاء الشجرة حوالي 3 أضعاف الوقت الذي يستغرقه إنشاء الشبكة (باستخدام تطبيقنا الذي يحول بيانات الفوكسل إلى بيانات مثلثات).

يستهلك Bullet BVH المقيس 16 بايت لكل عقدة، مما يصل إلى حوالي 32 بايت لكل مثلث. (وهو ما يعادل حوالي 2.5 ضعف تكلفة ذاكرة بيانات المثلث). ويستغرق إنشاؤه وقتًا أطول مقارنة بالإصدار غير المقيس؛ حوالي 5 أضعاف الوقت الذي يستغرقه إنشاء الشبكة.

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

شجرة kD فضفاضة: البناء

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

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

<span style="color: #006bb8;">union</span> KDNode {
 <span style="color: #006bb8;">&nbsp; &nbsp;    struct</span> {
 <span style="color: #007788;">&nbsp; &nbsp; &nbsp; &nbsp;    float</span> splits[<span style="color: #ff0000;">2</span>];
 <span style="color: #007788;">&nbsp; &nbsp; &nbsp; &nbsp;    unsigned int</span> axis: <span style="color: #ff0000;">2</span>; <span style="color: #999999;">// 0=X, 1=Y, 2=Z</span>
 <span style="color: #007788;">&nbsp; &nbsp; &nbsp; &nbsp;    unsigned int</span> childIndex: <span style="color: #ff0000;">30</span>; <span style="color: #999999;">// children are at childIndex+0,1</span>
        } branch;


&nbsp; &nbsp;     <span style="color: #006bb8;">struct</span> {
 <span style="color: #007788;">&nbsp; &nbsp; &nbsp;    &nbsp; unsigned int</span> triangles[<span style="color: #ff0000;">2</span>]; <span style="color: #999999;">// up to two triangles per leaf</span>
 <span style="color: #007788;">&nbsp; &nbsp; &nbsp;    &nbsp; unsigned int</span> axis: <span style="color: #ff0000;">2</span>;<span style="color: #999999;"> // must be 3; same offset as branch.axis&nbsp; &nbsp;</span>
 <span style="color: #007788;">&nbsp; &nbsp; &nbsp; &nbsp;    unsigned int</span> triangleCount: <span style="color: #ff0000;">30</span>;
        } leaf;
   };

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

لاحظ أن العقدة تبلغ 12 بايت. نظرًا لأننا نخزن مثلثين في كل عقدة ورقة، فإننا نحتاج إلى عدد إجمالي من العقد يماثل عدد المثلثات التي لدينا، وبالتالي فإن تكلفة الذاكرة تبلغ 12 بايت لكل مثلث. وهناك بالتأكيد مجال أكبر للتحسين هنا أيضًا. يمكننا تقليل تكلفة الذاكرة لبيانات الرؤوس عن طريق حزم المواقع باستخدام أعداد صحيحة ذات 16 بت وتحسين عقدة شجرة kD بطريقة مماثلة، للوصول إلى ~6 بايت لكل عقدة kD، مما ينتج عنه تأثير إجمالي للمثلث يبلغ 3.5 بايت للرؤوس + 6 بايت للمؤشر + 6 بايت للشجرة = 15.5 بايت، لكن النتيجة الحالية البالغة ~24.5 بايت لكل مثلث كانت جيدة بما يكفي للتسليم.

عملية بناء الشجرة قياسية نسبيًا. نبدأ بمصفوفة من المثلثات ونقسمها بشكل متكرر، مما يؤدي إلى إنشاء عقد فروع في العملية (وتوقف التكرار بمجرد وصولنا إلى مثلثين لكل عقدة أو أقل). لكل تقسيم، نختار المحور بأخذ أطول محور في AABB الحالي، ونضع نقطة التقسيم عند متوسط نقاط منتصف المثلثات على طول هذا المحور، ونصفي المثلثات إلى اليسار/اليمين من ذلك المستوى باستخدام نقاط منتصفها كعامل قرار، ثم نعيد حساب مستويي التقسيم الأيمن والأيسر باستخدام جميع رؤوس المثلثات الثلاثة. إذا كان التوزيع الناتج منحرفًا جدًا من حيث عدد المثلثات (يُعرَّف هذا حاليًا بأن <25٪ من المثلثات تنتهي في إحدى العقدتين)، فإننا نعيد التقسيم ونضع نصف المثلثات في شجرة فرعية ونصفها في شجرة فرعية أخرى (من القائمة المرتبة حسب نقاط الوسط). يحافظ هذا على التوازن بين التماسك المكاني وعمق الشجرة، ويحد من عمق الشجرة، ويضمن انتهاء العملية.

تكون عملية البناء في النهاية أبسط قليلاً ويتم ترميزها بكفاءة أكبر من عملية Bullet، وبالتالي فهي أسرع بحوالي 3-4 مرات من أسرع خوارزمية لبناء الشجرة في Bullet. ينتج عن ذلك أن تكون بيانات الشبكة والشجرة متكافئة تقريبًا في الحجم ومتكافئة تقريبًا في وقت الإنشاء، وهو توازن جيد (أو بالأحرى، هذا يعني أنه لإجراء تحسينات كبيرة في العملية الإجمالية، تحتاج إلى تحسين كليهما بشكل كبير :D).

شجرة kD فضفاضة: الاستعلامات

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

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

<span style="color: #006699;">if</span> (node.branch.splits[<span style="color: #ff0000;">1</span>] &lt;= aabbMax[axis])
    buffer[offset++] = childIndex + <span style="color: #ff0000;">1</span>; <span style="color: #999999;">// push right child</span>


<span style="color: #006699;">if</span> (node.branch.splits[<span style="color: #ff0000;">0</span>] &gt;= aabbMin[axis])
    buffer[offset++] = childIndex + <span style="color: #ff0000;">0</span>; <span style="color: #999999;">// push left child

</span>

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

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

<span style="color: #007788;">float</span> sa = raySource[axis];
<span style="color: #007788;">float</span> da = rayDir[axis];


<span style="color: #007788;">float</span> t0 = (node.branch.splits[i0] - sa) / da;
<span style="color: #007788;">float</span> t1 = (node.branch.splits[i1] - sa) / da;


<span style="color: #006699;">if</span> (t1 &lt;= rn.tmax)
    buffer[offset++] = { childIndex + i1, max(t1, rn.tmin), rn.tmax };


<span style="color: #006699;">if</span> (t0 &gt;= rn.tmin)
    buffer[offset++] = { childIndex + i0, rn.tmin, min(t0, rn.tmax) };

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

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

وبذلك، نحصل على استعلامات شجرة فعالة لكل من AABB وraycasts. أداء استعلام AABB يوازي أداء تطبيق Bullet، لكن استعلام raycast أسرع؛ وذلك لأننا نقوم بعمل أقل لكل فرع (تقاطع مستويين فقط مع شعاع) ولأننا نستطيع إنهاء عملية التصفح مبكرًا إذا وجدنا نقطة تقاطع مناسبة.

الأعمال المستقبلية

على الرغم من أن الخوارزميات الناتجة التي قمنا ببنائها تعمل بشكل جيد، إلا أنه يمكن بلا شك تحسينها أكثر. يمكن تحسين استهلاك الذاكرة في المرحلة الضيقة؛ بالإضافة إلى ذلك، نقوم حاليًا بتخزين المثلثات في شجرة kD. اقترح Christer Ericson أنه إذا قمت بتخزين المربعات كعناصر أولية من الدرجة الأولى، يمكن أن تكون عمليات إرسال الأشعة أكثر كفاءة بمقدار يصل إلى ضعفين نظرًا لأن خوارزمية Möller-Trumbore يمكنها التعامل مع المربعات بأقل قدر من الحسابات الإضافية (تم بناء تضاريسنا باستخدام المربعات وبعضها مستوي، لذا قد يكون هذا ممكنًا).

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

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