Doom פתר את סדר הציור באמצעות מאמר של מישהו אחר מ־1980, ושילם על כך בארכיטקטורת השלבים
ג'ון קרמאק לא יכול היה להרשות לעצמו מאגר עומק על מעבד של 1993. במקום זאת המנוע חותך את השלב לחלקים קמורים מראש, בעת הידור המפה. אותה עובדה מסבירה מדוע קירות ב־Doom לעולם אינם זזים.
הבעיה שהיה צריך לפתור עד דצמבר 1993 נשמעת משעממת וקובעת את כל השאר: באיזה סדר לצייר קירות כך שהקרובים יסתירו את הרחוקים.
הדרך המתבקשת היא מאגר עומק, השומר מרחק לכל נקודה במסך. במכונות של אותה תקופה משמעות הדבר הייתה מגה־בייט זיכרון נוסף והשוואה לכל פיקסל שמצויר; לא זה ולא זה היו זמינים. הדרך השנייה היא אלגוריתם הצייר: למיין מצולעים לפי מרחק ולצייר מהרחוק לקרוב. היא דורשת מיון בכל פריים, וגרוע מכך אינה תמיד עובדת: שלושה קירות יכולים להסתיר זה את זה במעגל, ואין להם סדר נכון כלל.
Wolfenstein 3D עקף ב־1992 את הבעיה כליל: העולם היה רשת של קוביות זהות והמנוע שיגר קרן אחת לכל טור מסך. סדר על רשת הוא טריוויאלי. אבל על רשת אי אפשר להציב קיר בזווית.
מה קרמאק לקח
שלבי Doom הם מצולעים שרירותיים בזוויות שרירותיות. עבורם יישם קרמאק חלוקת מרחב בינארית, BSP, שתוארה ב־1980 במאמר של הנרי פוקס, צבי קדם וברוס ניילור.
הרעיון נכנס לשלושה משפטים. קחו קיר והאריכו את קו המתאר שלו עד אינסוף: הוא מחלק את השלב ללפנים ולאחור. חזרו על כך רקורסיבית לכל מחצית, וחתכו כל קיר שנופל על הקו. בעלי העץ נותרות אזורים קמורים שבתוכם דבר אינו יכול להסתיר דבר.
בזמן ריצה אין צורך במיון כלל. עבור כל מיקום מצלמה המנוע יורד בעץ, ובכל צומת לוקח תחילה את הצד שבו נמצא השחקן. הסדר נכון מעצם הבנייה.
קרמאק לא זירז את המיון. הוא הוציא אותו מזמן המשחק אל זמן הידור המפה.
במה שולמה המהירות
העץ נבנה פעם אחת, כשהשלב מורכב בעורך, וזה לוקח שניות עד דקות. הוא מתאר את הגאומטריה לצמיתות.
מכאן נובע הדבר שמזהים ב־Doom במבט אחד. דלת יכולה לעלות, רצפה יכולה לרדת, פלטפורמה יכולה לנסוע מעלה — כל זה משנה גבהים אך לא את התוכנית. שום קיר ב־Doom אינו מסתובב ואינו מחליק אופקית, משום שזה היה פוסל את העץ, ולבנות אותו מחדש תוך כדי תנועה אי אפשר. הסגנון האדריכלי של המשחק, תוכנית סטטית עם רצפות ודלתות הנעות אנכית, אינו החלטה אמנותית אלא תוצאה ישירה של מבנה נתונים.
לכך מוסיף המנוע חיסכון שני: הוא עובר בעץ מהקרוב לרחוק ומנהל רשימה של טורי מסך שכבר כוסו. ברגע שטור נסגר, כל מה שמאחוריו מדולג בלי עיבוד. Doom כמעט אינו מצייר פיקסל פעמיים, נדירות באותה תקופה.
הכלל הכללי
Doom יצא ב־10 בדצמבר 1993 והפך לדוגמה הראשונה הידועה ברבים לעסקה שמגדירה את הגרפיקה מאז: להוציא עבודה מזמן הריצה אל זמן הבנייה. אותו קו עובר במפות תאורה אפויות, בחישוב נראות מראש ב־Quake, בתאורה גלובלית אפויה ובהיררכיות נפחים תוחמים של ימינו למעקב קרניים. זו עסקה אחת שחוזרת.
לכן השאלה המועילה לגבי כל אפקט יפה אינה כמה הוא עולה לפריים, אלא מה חושב לפני שהשחקן לחץ על התחל. ואחריה שאלה שנייה, שהתשובה לה היא בדרך כלל המחיר האמיתי: מה כבר אי אפשר להזיז בגללו.
מקור: en.wikipedia.org