داخل الزلزال: دائما النظر في البدائل

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

يجب أن أعترف: تعبت من موسيقى الروك الكلاسيكية. آخر مرة كنت سعيدًا بالاستماع إلى شيء من Cars أو Boston لفترة طويلة ، منذ حوالي 20 عامًا. بالإضافة إلى ذلك ، لم أكن منجذبًا بشكل خاص إلى Bob Seager and Queen ، ناهيك عن Elvis ، لم يتغير شيء يذكر. لكنني أدركت أن شيئًا ما تغير عندما أردت تبديل الراديو عندما سمعت ألمان براذرز أو ستيلي دان أو بينك فلويد ، أو الله ، سامحني ، البيتلز (لكن فقط على أشياء مثل "Hello Goodbye" و "I will like" أبكي بدلاً من ذلك ، ليس تذكرة ركوب أو يوم في الحياة ؛ لم أذهب إلى هذا الحد بعد). لم يستغرق الأمر وقتًا طويلاً للعثور على أسباب ذلك ؛ لقد استمعت إلى نفس الأغاني لمدة ربع قرن ، وتعبت منها.

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

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

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

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

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

تيار الإبداعي

في يناير ، وصفت دفقًا مبتكرًا قاد جون كارماك إلى اتخاذ قرار لاستخدام مضلعات مجموعة (PVS) محتملة مسبقًا محتملة لكل وجهة نظر محتملة في Quake (لعبة نقوم بتطويرها بشكل مشترك في برنامج id). يعني الحساب الأولي لـ PVS أنه بدلاً من قضاء الكثير من الوقت في البحث في قاعدة بيانات المضلعات المرئية من وجهة النظر الحالية في قاعدة البيانات العالمية ، يمكننا ببساطة سحب جميع المضلعات في PVS إلى الأمام (أخذ الترتيب من شجرة BSP في العالم ؛ مناقشة BSP- شاهد الأشجار في أعمدةنا لشهر مايو ويوليو ونوفمبر 1995) ، واحصل على المشهد بشكل صحيح تمامًا دون البحث ، مما يسمح بالرجوع إلى الخلف لإكمال الخطوة الأخيرة من إزالة السطح المخفي (HSR). لقد كانت فكرة رائعة ، ولكن بالنسبة إلى هندسة الزلزال ، لم يكتمل المسار بعد.

رسم الأجسام المتحركة

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

قام جون بحل مشكلة الفرز الخاصة بنماذج العفاريت والمضلعات بطريقة منخفضة التكنولوجيا بشكل مدهش: الآن نكتبها إلى z-buffer. (أي ، قبل رسم كل بكسل ، نقارن المسافة إليه ، أو z ، مع القيمة z للبكسل على الشاشة بالفعل. يتم رسم بكسل جديد فقط إذا كان أقرب من الواحد الموجود.) أولاً ، نرسم العالم الرئيسي - الجدران والسقوف وما إلى ذلك. مثل هذا. في هذه المرحلة ، لا يتم استخدام اختبار z-buffer (كما سنرى قريبًا ، يتم تنفيذ تعريف الأسطح المرئية في العالم بطريقة أخرى) ؛ ومع ذلك ، نحن نملأ z-buffer بقيم z (في الواقع قيم 1 / z ، كما هو موضح أدناه) لجميع وحدات البكسل في العالم. تعبئة Z-buffer هي عملية أسرع بكثير من z-buffing سيكون العالم بأسره ، لأنه لا توجد قراءة ، لا مقارنات ، فقط كتابة القيم z. بعد الانتهاء من الرسم والتعبئة في z-buffer في العالم ، يمكننا ببساطة رسم العفاريت والنماذج متعددة الأضلاع باستخدام z-buffering والحصول على الترتيب المثالي.

عند استخدام z-buffer ، تنشأ أسئلة لا محالة: كيف يؤثر ذلك على الذاكرة والأداء المشغولين؟ بدقة 320 × 200 ، تتطلب الذاكرة 128 كيلو بايت ، وهي ليست تافهة ، ولكنها لا تتطلب تشغيل لعبة تتطلب 8 ميغابايت. التأثير على الأداء: حوالي 10٪ عند ملء z-buffer في العالم ، وحوالي 20٪ (تختلف المؤشرات كثيرًا) عند تقديم العفاريت ونماذج المضلعات. بالمقابل ، نحصل على عالم مرتبة تمامًا ، بالإضافة إلى القدرة على إنشاء تأثيرات إضافية ، على سبيل المثال ، الانفجارات والدخان من الجزيئات ، لأن z-buffer يسمح لك بسهولة فرز هذه التأثيرات في العالم. بشكل عام ، أدى استخدام z-buffer إلى زيادة كبيرة في الجودة والمرونة المرئية لمحرك Quake ، بالإضافة إلى تبسيط التعليمات البرمجية بشكل كبير ، على حساب تكاليف وأداء الذاكرة المعقولين.

التسوية وزيادة الإنتاجية

كما قلت أعلاه ، تقوم بنية Quake أولاً برسم العالم نفسه ، دون قراءة أو مقارنة z-buffer ، فقط قم بملء z-buffer بقيم مضلعات العالم في z. بعد ذلك ، يتم رسم الكائنات المتحركة على قمة العالم باستخدام التخزين المؤقت الكامل. حتى الآن تحدثت فقط عن كيفية رسم الأشياء المتحركة. في بقية العمود ، سأتحدث عن جزء آخر من المعادلة التجسيدية - رسم العالم نفسه ، عندما يتم تخزين العالم كله كشجرة BSP واحدة ولا يتحرك أبدًا.

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

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

وقد وجد بالفعل.

فواصل مرتبة

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

يمكنك القيام بعمل أفضل إذا قمت بنقل الخطوة HSR الأخيرة من مستوى المضلع إلى مستوى الفاصل واستخدام الحل مع فواصل زمنية مرتبة. في جوهره ، يتكون هذا النهج من تحويل كل مضلع إلى مجموعة من الفواصل ، كما هو موضح في الشكل 1 ، متبوعًا بفرز وفصل الفواصل الزمنية بالنسبة لبعضها البعض حتى تبقى الأجزاء المرئية فقط من الفواصل المرئية للعرض ، كما هو مبين في الشكل 2. قد يبدو هذا يشبه إلى حد كبير التخزين المؤقت z (والذي ، كما قلت أعلاه ، بطيء جدًا في استخدامه في جعل العالم ، على الرغم من أنه مناسب للكائنات المتحركة الأصغر) ، ولكن هناك اختلافات مهمة. على عكس z-buffing ، يتم فحص الأجزاء المرئية فقط من الفواصل المرئية بالبكسل بالبكسل (على الرغم من أن جميع حواف المضلعات لا تزال بحاجة إلى تنقيط). والأفضل من ذلك ، أن الفرز الذي يتم تنفيذه بواسطة z-buffer لكل بكسل يصبح عملية فاصلة مع فواصل زمنية مصنفة ، وبما أن خاصية متكاملة قائمة الفاصل هي التوصيل ، يتم فرز كل حافة وفقًا لبعض الفواصل الزمنية في نفس الصف ، ويتم اقتطاعها فقط بفواصل زمنية قليلة عندما تراكب أفقي. على الرغم من أن المشاهد المعقدة لا تزال تستغرق وقتًا أطول من معالجة المشاهد البسيطة ، إلا أن الحالات الأسوأ لم تكن بنفس السوء عند استخدام أشعة الشعاع أو عند الفرز من الخلف إلى الأمام ، لأنه لا يوجد إعادة رسم ومسح للبكسلات المخفية ، فإن التعقيد محدود بدقة البكسل ، والاتصال الفاصل يحد من فرز الأسوأ الحالات في أي منطقة من الشاشة. على سبيل المكافأة ، يكون إخراج الفواصل التي تم فرزها بالشكل الذي يحتاجه أداة التنقيط ذات المستوى المنخفض: بتنسيق مجموعة من واصفات الفاصل ، كل منها يتكون من إحداثيات البداية والطول.



الجيل الفاصل

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

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

الأضلاع مقابل فترات

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

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



الشكل 2: يتم فرز الفواصل الزمنية من المضلع A من الشكل 1 ويتم اقتطاعها على فترات من المضلع B ، بينما يكون المضلع A على مسافة ثابتة تبلغ 100 على طول المحور Z ، ويكون المضلع B على مسافة ثابتة قدرها 50 على طول المحور Z (المضلع B أقرب إلى الكاميرا )

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

لكل سطر نقطي ، يتم تخزين قائمة مضلعات نشطة (APL) مرتبة حسب z. وغني بالترتيب حسب x AEL. عند الاجتماع مع كل حافة جديدة (أي عندما يبدأ كل مضلع أو ينتهي عند الانتقال من اليسار إلى اليمين) ، يتم تنشيط المضلع المرتبط به وترتيبه في APL (في حالة حافة البدء) ، كما هو موضح في الشكل 3 ، أو إلغاء تنشيطه وحذفه من APL ( في حالة حافة زائدة) ، كما هو موضح في الشكل 4. إذا تغير أقرب مضلع (أي ، يكون الأقرب هو مضلع جديد أو انتهى أقرب مضلع) ، بالنسبة للمضلع الذي توقف للتو ليكون الأقرب ، يتم إنشاء فاصل زمني يبدأ من النقطة التي لا يكون فيها المضلع لأنه هو الأقرب وتنتهي س تنسيق حواف الحالية والراهنة الإحداثي س يتم تسجيل vym في مكب النفايات، الذي هو الآن أقرب. يتم استخدام هذا الإحداثي المخزن فيما بعد كبداية للفاصل الزمني الذي تم إنشاؤه عندما لم يعد أقرب مضلع جديد في المقدمة.



الشكل 3: تنشيط المضلع عند اكتشاف حافة الانطلاق في AEL.



الشكل 4: إلغاء تنشيط المضلع عند اكتشاف حافة زائدة في AEL.

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

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

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

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

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

مفاتيح فرز الضلع

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

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

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

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

ومع ذلك ، فإن الحصول على مسافات على طول z يمكن أن يكون مهمة صعبة. لا تنس أننا نحتاج إلى أن نكون قادرين على حساب z في أي نقطة تعسفية على المضلع ، لأن الحافة يمكن أن تحدث وتتسبب في فرز المضلع في APL في أي مكان على الشاشة. يمكننا حساب z مباشرةً من إحداثيات الشاشة x و y ومعادلات مستوى المضلع ، لكن لسوء الحظ ، لا يمكن القيام بذلك بسرعة كبيرة ، لأن z للمستوى لا يتغير خطيًا في مساحة الشاشة ؛ ومع ذلك ، 1 / ​​z يختلف خطيا ، لذلك نحن نستخدم هذه القيمة. (للاطلاع على مناقشة الخطية في مساحة الشاشة والتدرجات ل 1 / z ، راجع سلسلة كريس هيكر حول رسم الخرائط في مجلة Game Developer العام الماضي.) ميزة أخرى لاستخدام 1 / z هي أن الدقة تزداد مع تناقص المسافة ، أي مع 1 / z سيكون لدينا دائمًا أفضل دقة عمق للكائنات القريبة الأكثر أهمية.

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

سيكون من الأفضل حساب 1 / z مباشرةً من معادلة الطائرة والشاشة x و y للبكسل الذي يهمنا. المعادلة لها الشكل التالي:

$$

$$1/z = (a/d)x' - (b/d)y' + c/d$$

حيث z هو الإحداثي في ​​الفضاء z الخاص بالنقطة على المستوى المسقطة في إحداثيات الشاشة (x '، y') (أصل إحداثيات هذه الحسابات هو مركز الإسقاط، النقطة على الشاشة مباشرة أمام نقطة العرض)، [abc] هي عادية إلى الطائرة في منفذ العرض ، و d هي المسافة من أصل منفذ العرض إلى الطائرة على طول المستوى الطبيعي. يتم تنفيذ القسمة مرة واحدة فقط لكل طائرة ، لأن أ ، ب ، ج ود د ثوابت للطائرات.

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

إذا كنت مهتمًا ، فإليك اشتقاق سريع لمعادلة 1 / z. معادلة المستوى للطائرة بالشكل التالي:

$$

$$ax + by + cz - d = 0$$

حيث x و y هما إحداثيات مساحة العرض ، a ، b ، c ، d ، و z معرّفة أعلاه. إذا فعلنا الاستبدال$$$x=x'z$ و $$$y=-y'z$(من تعريف الإسقاط المنظور ؛ y يتغير علامة لأنه يزيد في إطار العرض ، ولكن في مساحة الشاشة). أداء التقليب ، نحصل على:

$$

$$z = d / (ax' - by' + c)$$

عكس وتوسيع المعادلة ، نحصل على:

$$

$$1/z = ax'/d - by'/d + c/d$$

في وقت لاحق سوف تظهر 1 / z الفرز في العمل.

زلزال وفرز بواسطة z

ذكرت أعلاه أن الزلزال لم يعد يستخدم ترتيب BSP كمفتاح فرز ؛ في الواقع ، يتم تطبيق 1 / z الآن كمفتاح. على الرغم من أناقة التدرجات ، من الواضح أن حساب 1 / z منها أبطأ من مجرد المقارنة مع مفتاح ترتيب BSP ، فلماذا التبديل إلى استخدام 1 / z في Quake؟

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

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

المضي قدما

تحتوي المقالة ، بلا شك ، على كمية هائلة من المعلومات ، ولم يتم وضع الكثير منها بعد. الكود والشرح من المقال التالي سوف يساعدك ؛ إذا كنت ترغب في إلقاء نظرة مسبقة ، بحلول الوقت الذي تقرأ فيه هذه المقالة ، يجب أن يكون الرمز متاحًا على الموقع ftp.idsoftware.com/mikeab/ddjsort.zip. من الجدير أيضًا إلقاء نظرة على Computer Graphics Foley و Van Dam أو العناصر الإجرائية لـ Computer Graphics Rogers.

ليس من الواضح في الوقت الحالي كيف كانت نتيجة الزلزاليجب فرز الحواف - بترتيب BSP أو 1 / z. في الواقع ، ليس هناك ما يضمن أن الفواصل الزمنية المصنفة بأي شكل ستكون الحل النهائي. في بعض الأحيان يبدو أننا نغير محركات الرسومات بقدر ما نضع Elvis على محطات الراديو المخصصة لنجاحات الخمسينيات (ولكن ، على أمل ، مع نتائج أكثر جمالياً!) ، وسننظر بلا شك في بدائل حتى تاريخ الإصدار الألعاب.