هل استخدام BSP في Doom حقًا حركة بارعة؟

قمة التكنولوجيا في ذلك الوقت.

في عام 1993 ، أصدرت id Software Doom ، مطلق النار من أول شخص تحول بسرعة إلى ظاهرة. اليوم يعتقد أن هذه واحدة من الألعاب التي كان لها أكبر تأثير في التاريخ.

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

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

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

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

نعم ، هذا صحيح: ظهر E1M1 ، المستوى الأول من الموت ، بفضل سلاح الجو الأمريكي.

مهمة VSD

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

غالبًا ما تسمى هذه المهمة مهمة تحديد السطح المرئي (VSD). كتب المبرمج مايكل أبراش ، الذي عمل مع Carmack on Quake (لعبة برمجيات الهوية التالية بعد Doom ) ، عن مهمة VSD في كتابه الشهير Graphics Programming Black Book :

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

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

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

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

على سبيل المثال ، في لعبة Wolfenstein 3D ، اللعبة التي تم إصدار معرف البرنامج لها قبل Doom ، كان كل مستوى يتكون من جدران محاذاة على طول المحاور. بمعنى آخر ، في عالم Wolfenstein يمكن أن يكون هناك جدران بين الشمال والجنوب أو جدران من الشرق / الغرب ، ولا توجد جدران أخرى. بالإضافة إلى ذلك ، يمكن وضع الجدران على مسافات ثابتة في الشبكة - كل الممرات لها عرض إما خلية شبكة واحدة ، أو خليتين ، وما إلى ذلك ، ولكن لا تحتوي أبدًا على 2.5 خلية. على الرغم من أن ذلك كان يعني أن فريق البرمجيات id يمكنه إنشاء مستويات تبدو متشابهة تقريبًا ، إلا أن هذا التقييد جعل من السهل جدًا على Carmack كتابة عارض لـ Wolfenstein .

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

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

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

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

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


في البداية ، حاول كارماك حل هذه المشكلة من خلال الاعتماد على مخطط مستوى الموت . بدأ عارضه برسم جدران الغرفة التي يقع فيها اللاعب ، ثم سكب في الغرف المجاورة لرسم الجدران في هذه الغرف ، والتي يمكن أن تكون مرئية من الغرفة الحالية. إذا كانت كل غرفة محدبة ، فهذا من شأنه أن يحل مشكلة VSD. يمكن تقسيم الغرف غير المحدبة إلى "قطاعات" محدبة. يمكنك أن ترى كيف يمكن أن تبدو تقنية العرض هذه تباطؤًا قويًا في الفيديو أعلاه ، حيث يوضح مستخدم YouTuber يحمل اللقب Bisqwit عارضه الخاص الذي يعمل وفقًا لنفس الخوارزمية العامة. تم استخدام هذه الخوارزمية بنجاح في لعبة Duke Nukem 3D ، التي صدرت بعد ثلاث سنوات من الموت ، عندما أصبحت المعالجات أكثر قوة. لكن في عام 1993 ، في ذلك الوقت ، واجه عارض الموت الذي يستخدم هذه الخوارزمية مشكلات ذات مستويات معقدة. كان هذا واضحًا بشكل خاص عندما تم دمج القطاعات في بعضها البعض ، وكانت هذه هي الطريقة الوحيدة لإنشاء ، على سبيل المثال ، السلالم الدائرية. تتطلب السلالم الدائرية نزولًا متكررًا متعددًا إلى القطاع المرسوم بالفعل ، مما يقلل بشكل كبير من سرعة المحرك.

في الوقت نفسه تقريبًا ، عندما أدرك فريق id أن محرك Doom قد يكون بطيئًا جدًا ، طُلب من id Software نقل Wolfenstein 3D إلى Super Nintendo. كانت SNES أقل قوة من أجهزة الكمبيوتر المتوافقة مع IBM في ذلك الوقت ، واتضح أن عارض Wolfenstein المزود بتقنية مسيرة الشعاع ، على الرغم من بساطته ، لم يعمل على أجهزة Super Nintendo بسرعة كافية. لذلك ، بدأ Carmack في البحث عن خوارزمية أفضل. في الواقع ، كانت Carmack تستكشف وتنفذ تقسيم الفضاء الثنائي لأول مرة في ميناء Wolfenstein في Super Nintendo. في ولفنشتاين كان الأمر بسيطًا جدًا لأن جميع الجدران كانت موازية للمحاور. الموت يجعل الأمر أكثر صعوبة. لكن Carmack أدركت أن أشجار BSP ستحل مشاكل السرعة في Doom أيضًا .

سبليت الفضاء الثنائي

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

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

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

أحد الحلول التي ذكرها هؤلاء الباحثون ، والتي قالوا إنها استخدمت سابقًا في مشروع ناسا ، تستند إلى إنشاء ما أسميه "المصفوفة المتداخلة". يشير الباحثون إلى أنه يمكن استخدام طائرة تقسم مشهدًا إلى جزأين لحل "أي تعارض في الأولويات" بين الكائنات الموجودة على جانبي الطائرة. في الحالة العامة ، قد تحتاج إلى إضافة هذه الطائرات إلى المشهد بشكل صريح ، ولكن مع بنية معينة للهندسة ، يمكنك الاعتماد على الوجوه الحالية للكائنات. يوضح الباحثون المثال التالي ، حيث تقسم p1 و p2 و p3 الأسطح. إذا كانت وجهة نظر الكاميرا في المقدمة أو في الجانب "الحقيقي" لإحدى هذه الطائرات ، فإن pi هي 1. توضح المصفوفة العلاقة بين الكائنات الثلاثة اعتمادًا على مستويات الفصل الثلاثة وموقع وجهة نظر الكاميرا - إذا تداخل الكائن a مع كائن aj ، عنصر aij في المصفوفة سيكون مساويًا 1.


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

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

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

قدم Fuchs و Kedem و Naylor وصفًا واضحًا إلى حد ما لتشغيل شجرة BSP ، لكنني سأحاول تقديم وصف رسمي أقل ، ولكنه موجز.

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

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

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




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

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

كتب بروس نايلور ، أحد مؤلفي مقالة 1980 ، فيما بعد عن هذه المسألة في مقالته عام 1993 ، بعنوان "بناء أشجار جيدة التقسيم". وفقًا لزميل كارماك ومؤسس البرامج المعرف جون روميرو ، كانت هذه المقالة واحدة من الأعمال التي قرأها كارماك عندما حاول تنفيذ أشجار BSP في دووم .

أشجار BSP في الموت

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

"إضافة أشجار BSP إلى الموت " في الممارسة العملية إضافة مولد شجرة BSP إلى محرر مستوى Doom . بعد الانتهاء من إنشاء مستوى الموتتم إنشاء شجرة BSP من هندسة المستوى. وفقًا لـ Fabien Sanglar ، قد تستغرق عملية التوليد ما يصل إلى ثماني ثوان لمستوى واحد و 11 دقيقة لجميع مستويات Doom الأولى . كانت عملية التوليد طويلة جدًا ويرجع ذلك جزئيًا إلى حقيقة أن خوارزمية توليد Carmack BSP تحاول العثور على شجرة BSP "جيدة" باستخدام طرق البحث المختلفة. سيكون التأخير لمدة ثماني ثوانٍ أمرًا لا يُغتفر خلال اللعبة ، ولكن خلال الجيل التمهيدي بدا الأمر مقبولًا تمامًا ، نظرًا للزيادة في الأداء التي قدمتها أشجار BSP للعارض. تم حفظ شجرة BSP التي تم إنشاؤها من مستوى فردي كجزء من بيانات المستوى المحملة في اللعبة عند إطلاقها.

قام Carmack بإجراء تغيير مهم على خوارزمية شجرة BSP الموضحة في مقال 1980: بعد إطلاق Doomوقراءة شجرة BSP الحالية إلى ذاكرة ، يستخدم العارض هذه الشجرة لرسم الكائنات ليس من الأمام إلى الأمام ، ولكن من الأمام إلى الخلف. في مقال 1980 ، أوضح كل من Fuchs و Kedem و Naylor كيف يمكن استخدام شجرة BSP لتنفيذ خوارزمية فنان مع عرض متتالي ، ولكن قد يحدث قدر كبير من إعادة الطلاء في خوارزمية الفنان ، والتي قد تكون مكلفة على أجهزة الكمبيوتر المتوافقة مع IBM. لذلك ، يبدأ عارض Doom بهندسة أقرب إلى اللاعب ، ثم يرسم البعد. مثل هذا الترتيب العكسي سهل التنفيذ باستخدام شجرة BSP ، لأنه يمكنك ببساطة اتخاذ قرار تراجع في كل عقدة من الشجرة. لمنع الرسم الهندسي الأبعد من الأقرب إلى الأعلى ، عارض الموتيستخدم نوعًا من المخزن المؤقت z الضمني الذي يوفر العديد من فوائد المخزن المؤقت z العادي ، بينما يستهلك ذاكرة أقل بكثير. هناك صفيف واحد يتتبع التداخل في البعد الأفقي ، وهناك صفيفان آخران يتعقبان التداخل في الاتجاه الرأسي أعلى وأسفل الشاشة. كان بإمكان عارض Doom الاستغناء عن استخدام z-buffer حقيقي ، لأن Doom ، بالمعنى الدقيق للكلمة ، لم يكن لعبة ثلاثية الأبعاد تمامًا. عملت بهياكل البيانات الأقل تكلفة في ذلك لأن بعض العناصر لم تكن ممكنة في Doom : عملت المصفوفة الأفقية بسبب عدم وجود جدران مائلة ، وكانت المصفوفات المتداخلة الرأسية تعمل بسبب عدم وجود جدران فيها ، على سبيل المثال ، كان هناك اثنان واحد فوق النوافذ الأخرى.


الموت الثاني ، معقدة مثل سابقتها.


لكن لا أحد اشتكى من تكرار الدم.


كلمة جديدة في تقنيات الزلزال

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

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

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

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

أي أن Carmack لم يكن أول من فكر في استخدام أشجار BSP في محاكاة رسومية في الوقت الفعلي. بالطبع ، للتنبؤ بأن أشجار BSP يمكن استخدامها بهذه الطريقة ، ولتنفيذ هذه الأمور كلها مختلفة تمامًا. لكن حتى مع التنفيذ ، يمكن أن يكون لدى Carmack معلومات خلفية أكثر مما يعتقد عادة. تشير مقالة WSP حول أشجار BSP إلى أن Carmack أشار إلى مقال 1991 الذي أعده تشن و Gordon ، وكذلك كتاب رسومات الحاسوب لعام 1990 : المبادئ والممارسة . على الرغم من أن هذا البيان لا يدعمه عرض أسعار ، فقد يكون صحيحًا. وصف مقال نشر عام 1991 لشين وجوردون التقديم الأمامي باستخدام أشجار BSP ، وهو في الأساس نفس الحل الذي تستخدمه Doom، حتى بنية البيانات "ضمنية z-buffer" ، التي لا تسمح برسم المضلعات البعيدة أعلى المجاورين. توفر المقالة نظرة عامة ممتازة على أشجار BSP ، وكذلك الكود الكاذب لبناء وعرض شجرة. (بفضل المكتبة الرائعة في جامعتي ، تمكنت من التمرير خلال طبعة عام 1990). كتاب الكمبيوتر للرسومات: المبادئ والممارسة هو عمل كلاسيكي على رسومات الكمبيوتر ، لذلك يمكن أن يكون لدى Carmack واحدة أيضًا.


القطاع الفرعي E1M1: حظيرة الطائرات.

بصرف النظر عن ذلك ، واجهت Carmack مهمة جديدة - "كيف يمكنني إنشاء أداة إطلاق نار من منظور الشخص الأول يتم تشغيلها على جهاز كمبيوتر بمعالج لا يستطيع حتى إجراء عمليات الفاصلة العائمة؟" - أجرت أبحاثها الخاصة ، وأثبتت أن أشجار BSP هي هذا بنية بيانات مفيدة لألعاب الفيديو في الوقت الفعلي. ما زلت أعتقد أن هذه نتيجة رائعة ، على الرغم من أن شجرة BSP تم اختراعها قبل عشر سنوات ، وقد تمت دراستها من الناحية النظرية بتفاصيل كافية بحلول الوقت الذي قرأت فيه Carmack عنها. ربما كان الإنجاز الرئيسي الذي يجب أن نثني عليه هو محرك Doom ككل ، والذي أصبح مثالًا رائعًا على الكود. لقد تحدثت بالفعل عن هذا مرة واحدة ، لكنني أكرر ذلك كتاب فابيان سانجلار حول محرك اللعبةDoom ( Game Engine Black Book: DOOM ) هي نظرة عامة ممتازة على جميع المكونات المدروسة لمحرك اللعبة وتفاعلها. يجب ألا ننسى أن مهمة VSD كانت واحدة من العديد من المهام التي كان على Carmack حلها حتى يعمل محرك Doom . وقد تمكن ، بالإضافة إلى كل شيء ، من قراءة بنية البيانات المعقدة غير المعروفة لمعظم المبرمجين ، وتنفيذها. هذا يقول الكثير عن مستوى معرفته التقنية والسعي لتحقيق المثالي.