在《毀滅戰士》中應用二叉空間分割（BSP）是何等天才之舉？

1993 年，遊戲開發公司 id Software 發行了一款第一人稱射擊遊戲 《 毀滅戰士 DOOM 》，遊戲一經發行迅速爆火。在今天看來，《毀滅戰士》可謂有史以來最具影響力的遊戲之一。

《毀滅戰士》發行之後的第十年（2003 年），記者 大衛·庫什納 David Kushner 出版了一本關於 id Software 的書，書名為《 Doom 啟示錄 Masters of Doom 》，後被奉為記錄毀滅戰士創作史的典範讀物。幾年前我曾讀過這本書，如今內容已記得不太真切了，但是書中有一個關於 id Software 首席程序員 約翰·卡馬克 John Carmack 的故事，我印象特別深刻。這裡只對故事做粗略描述（具體情節請往下閱讀）。實際上，早在《毀滅戰士》開發前期，卡馬克就發現自己為這款遊戲編寫的 3D 渲染器在渲染某些關卡時慢得像爬一樣。對於《毀滅戰士》這一對動感和速度有著相當高要求的射擊遊戲來說，這是一個非常嚴重的問題。意識到了這一問題的嚴重性，卡馬克需要一個更加有效的渲染演算法，於是他開始閱讀相關論文。最後，他實現了一種叫做「 二叉空間分割 binary space partitioning （BSP）」的技術，極大地提升了《毀滅戰士》遊戲引擎的運行速度，而這項技術此前從未用於電子遊戲當中。

一直以來，我對這個故事的印象十分深刻。卡馬克將學術前沿研究運用於電子遊戲之中，我覺得這正是他之所以成為傳奇人物的原因。無論從哪個角度來看，卡馬克都應該是電子遊戲行業中人盡皆知的典型的天才程序員，只不過上面這個故事是我最先能夠想到的理由。

顯而易見，「二叉空間分割」這個術語聽起來就是難度相當高的課題，能夠自行閱讀論文並將其付諸實施實屬不易，所以這個故事給我留下了深刻的印象。我一直認為卡馬克的做法十分具有創見性，不過由於我既不懂二叉空間分割到底是怎樣的一項技術，也不曉得這項技術在當時究竟有多麼革新，所以我也並不確定自己的觀點是否正確。如果按照從 霍默·辛普森 Homer Simpson （LCTT 譯註：《辛普森一家人》中的那個老爹）到 阿爾伯特·愛因斯坦 Albert Einstein 的順序為天才列出一套級別體系，那麼卡馬克將二叉空間分割技術運用於《毀滅戰士》的做法究竟屬於什麼級別的天才之舉呢？

同時，我也在想，二叉空間分割這個概念最初是從哪兒來的，又是怎樣吸引到卡馬克的？因此，本篇文章不僅僅會講述約翰·卡馬克和《毀滅戰士》的故事，也會探討二叉空間分割樹（BSP 樹）數據結構的發展歷史。有意思的是，BSP 樹和計算機科學領域其他許多技術一樣，最初都起源於軍事研究領域。

沒錯，《毀滅戰士》的第一關卡 E1M1 就受到了美國空軍的啟發。

VSD 難題

BSP 樹是計算機圖形領域最具挑戰性難題的解決方案之一。舉個例子，為了渲染出三維場景，渲染器必須能夠區分在一個特定角度下的可見物體和不可見物體。如果渲染時間比較充足，這一要求也算不上大問題；但是就理想情況來說，實時遊戲引擎在 1 秒內至少需要完成 30 次區分任務。

這一問題有時被稱為 可見面檢測 visible surface determination （VSD）問題。後來與卡馬克合作開發《 雷神之錘 Quake 》（id Software 繼《毀滅戰士》之後開發的遊戲）的程序員 邁克爾·亞伯拉什 Michael Abrash ，在自己的著作《 圖形程序開發人員指南 Graphics Programming Black Book 》 中寫道：

我想探討一下在我看來 3D 中最棘手的一個問題：可見面檢測問題（在每個像素點上繪製合適的表面）以及與之密切相關的隱面消除問題（迅速去除不可見的多邊形，用於加快可見表面檢測速度）。簡略起見，我將在下文採用縮寫 VSD 來表示可見面檢測和隱面消除。

為什麼我會認為 VSD 是 3D 中最棘手的問題呢？儘管紋理映射等光柵化問題更讓人感興趣而且也更重要，但是相對而言，它們是範圍相對有限的任務。隨著 3D 加速器的出現，它們逐漸被轉移到硬體中。同時，它們只隨著屏幕解析度的增加而增加，而解析度的增加是相對溫和的。

相反，VSD 卻像是一個無底洞，目前應對方案也有很多。但實際上，在採用簡單的方法處理 VSD 時，其性能會直接受到場景複雜程度的影響，而場景的複雜程度通常會以平方級或立方級的形式增大。所以在渲染過程中，VSD 很快就會成為制約因素。 ^[1]

亞伯拉什是在上個世紀九十年代末寫的關於 VSD 問題的這些困難，這是在《毀滅戰士》之後數年，這款遊戲證明了普通人盼望著能用自家電腦玩很吃圖形配置的遊戲。九十年代早期，id Software 成立後發行了一些遊戲。儘管當時的計算機還只是用來處理文字與表格或者執行其他任務，未嘗想過要在上面運行遊戲，id Software 必須對發行的遊戲進行編程，使其能在計算機上流暢運行。為了實現這一飛躍，尤其是為了能讓在《毀滅戰士》之前 id Software 發行的少數 3D 遊戲在電腦上運行，id Software 必須做出革新。在這些遊戲中，所有的關卡在設計時都受到了一定限制，以便更容易解決 VSD 問題。

例如，在《毀滅戰士》之前，id Software 發行了《 德軍總部 3D 版 Wolfenstein 3D 版 》，該遊戲的每一個關卡都是由與坐標軸平齊的牆壁組成。換言之，在《德軍總部 3D 版》的遊戲畫面里，你看到的只有南北方向或者東西方向的牆壁。在遊戲中，牆壁與牆壁之間有著固定的間隔，所有過道的寬度或是一個方格，或是兩個方格等等，但絕不會出現 2.5 個方格。如此一來，儘管 id Software 團隊只能設計出外觀十分相似的關卡，但這也讓卡馬克為 《德軍總部 3D 版》 編寫渲染器的工作簡單了不少。

通過將屏幕上的光線「齊射」入虛擬遊戲世界，《德軍總部 3D 版》的渲染器解決了 VSD 問題。通常來說，使用光線的渲染器叫做「光線投射」渲染器。這種渲染器的速度一般較慢，因為解決內部的 VSD 問題涉及到在光線和遊戲中的物體之間找到第一個交點，這通常需要進行大量的計算。但在 《德軍總部 3D 版》，由於所有的牆壁都與網格平齊，所以光線與牆壁相交的位置只能在網格線上。如此一來，渲染器只需逐個檢查這些交點即可。如果渲染器先從離玩家視角最近的交點開始檢查，接著檢查下一個最近的交點，以此類推，最後遇到第一面牆壁時停止檢查。這樣，VSD 問題便輕而易舉地得到了解決。光線從每一個像素點向前投射，與畫面物體接觸時停止，這一方法是可行的。因為從 CPU 資源來看，投射的成本很低。事實上，由於每面牆壁高度相同，因此針對同列的像素點，投射的光線只需一條。

儘管當時還沒有專業的圖形顯卡，《德軍總部 3D 版》憑藉這一取巧之法得以在配置較低的個人電腦上正常運行起來。然而，這個辦法並不適用於《毀滅戰士》。因為 id Software 為這款新遊戲增添了許多新元素 —— 傾斜的牆面、樓梯以及高低不一的天花板。光線投射的辦法自然也就不好用了，於是卡馬克編寫出了一個新的渲染器。《德軍總部 3D 版》的渲染器關注的是圖像，將光線投射到屏幕像素表示的列上，而 《毀滅戰士》 關注的則是物體。換句話說，《毀滅戰士》 的渲染器會記錄遊戲場景中的所有物體，繼而將其投射到屏幕當中；而非記錄屏幕上的像素點，判斷每個像素點的顏色。

對於強調物體的渲染器來說，可以使用 Z 緩衝區來解決 VSD 問題，比較簡單。每次將物體投射到屏幕上時，需要對每個用於繪製的像素點進行檢查。如果你想繪製出的物體的部分和已經繪製在目標像素點上的物體相比更加靠近玩家，可以將其覆蓋。否則，必須保持像素不變。儘管辦法很簡單，但是 Z 緩衝區對內存的要求較高，而且渲染器可能仍然要花費大量的 CPU 資源來投射玩家永遠不會看到的水平幾何體。

在 20 世紀 90 年代，使用 Z 緩衝區的方法還存在著其他缺陷：IBM 兼容機（PC）搭載的是一種叫 VGA 的顯示適配器系統，在這類電腦上，將圖像寫入幀緩衝區的成本非常之高。因此，在只會以後被覆蓋的像素上繪製花費的時間拖慢了渲染器的性能。

考慮到將圖像寫入幀緩衝區的成本非常之高，理想的渲染器需要首先繪製離玩家最近的物體，接著是比較近的物體，以此類推，直到屏幕上每個像素點都寫入了信息。這時，渲染器會停止運行，大幅縮短遠處不可見物體的渲染時間。這種由近及遠對物體進行排序的方法也可以解決 VSD 問題。那麼問題又來了：什麼才是玩家可以看到的？

最初，卡馬克打算依靠《毀滅戰士》的關卡布局來解決 VSD 問題。首先用渲染器繪製出玩家目前所在房間的牆壁，之後玩家衝進隔壁房間，再繪製出隔壁房間的牆壁。由於每個房間互不遮擋，這一辦法也能解決 VSD 問題。而互相遮擋的房間可以分割成若干互不遮擋的「區域」。在 YouTube 上的一個 視頻 中，Bisqwit 展示了自己製作出來的使用了相同演算法的渲染器。可以看到，如果以超慢的速度運行，便能一睹渲染的具體過程。這一演算法同樣運用到了《毀滅公爵 3D 版》當中，這款遊戲在 《毀滅戰士》 推出三年之後發行，當時 CPU 的性能也更加強大了。1993 年，儘管在硬體上已經可以運行遊戲了，但是使用這一演算法的《毀滅戰士》渲染器在複雜的層級結構上依舊錶現吃力，尤其是在房間分割出來的各部分相互嵌套的情況下。不巧的是，這類層級結構正是構造環形樓梯等物體的唯一辦法。沿著環形樓梯走下去，直到走入已經繪製好的區域，由於這其中涉及多次循環下降運動，導致遊戲引擎的運行速度大幅降低。

在 id Software 團隊意識到《毀滅戰士》遊戲引擎的速度可能過慢時，公司還面臨著其他任務：將《德軍總部 3D 版》移植到超級任天堂遊戲機（簡稱「超任」）上。那時，超任的性能比 IBM 兼容機還要差。結果表明，儘管光線投射渲染器非常簡單，但是想要在超任上快速運行是不可能的。於是，卡馬克著手研究更為高效的演算法。事實上，也正是為了順利將《德軍總部》移植到超任，卡馬克首次研究了二叉空間分割技術，並將其付諸應用。由於《德軍總部 3D 版》的牆壁與坐標軸平齊，所以二叉空間分割技術應用起來也比較簡單直接；但是《毀滅戰士》的情況則比較複雜。不過，卡馬克發現，二叉空間分割樹同樣可以用來解決《毀滅戰士》速度過慢的問題。

二叉空間分割

二叉空間分割 binary space partitioning （BSP）會提前將 3D 場景分割為若干部分，使 VSD 問題易於解決。講到這裡，你需要先了解一下為什麼分割場景可以奏效：如果你在場景上畫條線（對應三維空間里的一個平面），你就可以指出玩家或者攝像機視角在這條線的哪一側，在這條線另一側的物體無法遮擋玩家所在一側的物體。如果多次重複這一操作，該三維場景最終會被分割為多個區域，這並不是對原始場景的改進，只是現在你知道了更多關於場景的不同部分會如何相互阻擋。

首次闡述上述三維場景分割的是美國空軍的研究員，他們曾嘗試向美國空軍證明計算機圖形已經非常先進，可以應用到飛行模擬器領域。1969 年，他們將研究發現發表在一份題為《計算機生成圖像在圖形模擬中的應用研究》的報告中。該報告的總結部分指出，計算機圖形可用於訓練飛行員，但也警告說，其實際應用可能會受制於 VSD 問題：

實時圖像處理需要解決的一個關鍵問題就是優先順序問題，或稱隱藏線問題。在我們平時用眼睛觀察外界時，大自然替我們輕易地解決了這一問題：不透明物體上的一個點，掩蓋了同一視覺方向上、且距離較遠的所有其它物體。但在計算機中，這項任務卻非常困難。圖像處理需要解決的優先順序問題，隨著環境複雜程度的增加，計算量會呈指數級增長，隨即就會超過繪製物體透視圖所需的計算負載。 ^[2]

他們在報告中提出了一項基於構造「遮擋矩陣」的方案，這一方案據說早些時候曾被應用於 NASA 的項目當中。研究員指出，平面將場景一分為二，可用來解決平面兩側物體之間存在的「任何優先順序問題」。通常情況下，可能需要明確將這些平面添加到場景中，但對某些幾何體，只需藉助你已經擁有的幾何體的表面即可。他們舉了一個例子，如下圖：p ₁、p ₂ 以及 p ₃ 是三個不同的平面，如果攝像機視角位於其中一個平面的前方，即「正」面，p _i 的值就等於 1。這種矩陣展示出基於三個不同平面和攝像機視角位置的三個物體之間的關係 —— 如果物體 a _i 遮擋了物體 a _j，那麼 a _ij 在此矩陣中的數值等於 1。

研究人員指出，這種矩陣可以應用到硬體中，對每一幀進行重新評估。該矩陣基本上可以用作大型的開關，或者一種預置的 Z 緩衝區。在繪製給定的物體時，如果在物體所在列上得出數值 1，並且所在行已經在繪製中，那麼物體被遮擋的部分就不會繪製出來。

不過，該矩陣方法的主要缺點在於，為了在場景中表示出 n 個物體，你需要一個尺寸為 n ² 的矩陣。於是，研究人員們繼續深入，探究將遮擋矩陣表示為「優先順序列表」的可行性，該列表的尺寸是 n，可確定物體繪製的順序。他們隨即發現，諸如上圖此類場景根本無法確定順序（因為它存在循環阻塞的現象）。因此，他們花了很多時間來闡明「合適」與「不合適」場景之間的數學區別。最後，他們得出了一個結論：至少對於「合適的」場景下，優先順序列表是可以製作出來的；而對場景設計師來說，避免設計出「不合適」的場景也不是一件難事。但是，他們並沒有說明如何生成該列表。可以說，這份 1969 年的研究的首要貢獻在於提出了：至少，在 理論上，可以採用平面分割的方法，對場景中的物體進行渲染排序。

直到 1980 年，一份題為《基於優先順序樹結構的可見表面生成》的論文提出了解決該問題的具體演算法。在這份論文中，作者 亨利·福克斯 Henry Fuchs 、 澤維·凱德姆 Zvi Kedem 以及 布魯斯·內勒 Bruce Naylor 介紹了 BSP 樹。他們指出，這種新的數據結構「可以替代十年前首次使用，但由於一些問題未得到廣泛發展的方案」（即前文 1969 年美國空軍相關研究中的方案）。 ^[3] BSP 樹一經生成，即可用於確定場景中物體的優先順序順序。

三人在論文中對 BSP 樹的工作原理給出了相當可讀的解釋。但在本文，我將嘗試使用更加通俗的語言，介紹給大家。

首先，在場景中選定一個多邊形，將該多邊形所在的平面作為分割平面。同時，該多邊形充當樹的根節點。場景中剩下的多邊形會分散在分割平面的兩側。位於分割表面「前方」或者與分割平面相交後位於「前」半部分的多邊形落在了根節點左側的左子樹上；位於分割表面「後方」或者與分割平面相交後位於「後」半部分的多邊形落在了右子樹上。接著，遞歸重複這一過程：在左子樹和右子樹上各選定一個多邊形，作為各自空間新的分割平面，繼而二分出來更多的子空間和子樹。等到全部的多邊形均選定之後，二叉空間分割也就結束了。

假設你想由後向前將場景中的幾何圖形進行渲染。（這就是所謂的「 畫家演算法 painter's algorithm 」。因為在繪製時，距離攝像機較遠的多邊形會被距離攝像機較近的多邊形所覆蓋，藉此正確進行渲染任務。）如果想要實現這一演算法，必須按順序遍歷 BSP 樹，左右子樹的渲染順序由攝像機視角與節點所在分割平面的位置關係決定的。因此，針對樹上的每個節點，首先渲染距離分割平面較「遠」一側的所有多邊形，接著是位於平面上的多邊形，最後是距離平面較「近」一側的所有多邊形 —— 「遠」與「近」相對於攝像機視角而言。根據前文，距離分割平面較遠一側的多邊形無法遮擋近側的物體，所以這種方法可以解決 VSD 問題。

下圖表示一個簡單的二維場景的 BSP 樹的構造與遍歷過程。在二維中，分割平面變成了分割線，但就基本原理而言，與複雜的三維場景並無二致。

第一步：根分割線落在 D 牆上，將剩下的幾何圖形分為兩組。

第二步：繼續分割位於 D 牆兩側的空間。C 牆是其中一側的唯一一堵牆壁，因此無需再分。另一側，B 牆形成新的分割平面。因為 A 牆與新的分割平面相交，所以必須將其分割為兩堵牆。

第三步：參照右上方視角，由後向前對牆壁進行排序，對執行畫家演算法很有幫助。這就是樹的順序遍歷過程。

福克斯、凱德姆以及內勒多次強調了 BSP 樹的優勢：它只需構建一次。可能有些難以置信，但實際上無論攝像機視角位於何處，同一棵 BSP 樹都可以用來渲染一個場景。只要場景中的多邊形沒有移動，BSP 樹就不會失效。因此，BSP 樹在實時渲染任務中非常實用 —— 構建樹時的所有艱巨任務都可以在渲染工作開展之前完成。

同時，三人也提到了一項需要進一步深入研究的問題：究竟怎樣才能構建出一棵 「高質量的」 BSP 樹？BSP 樹的質量取決於用作分割平面的多邊形的選擇。我在前文跳過了這一問題，不過如果用作分割平面的多邊形與其他多邊形相交，那麼為了讓 BSP 演算法發揮作用，必須將相交的多邊形一分為二，這樣兩部分就可以分在不同的空間。但是如果這種現象反覆出現，BSP 樹的構建勢必會大幅增加場景中多邊形的數量。

內勒後來在其 1993 年的論文《構建高質量的分割樹》中提及這一問題。卡馬克的同事，id Software 的共同創始人 約翰·羅梅洛 John Romero 指出，這篇論文是卡馬克在《毀滅戰士》中引入 BSP 樹時讀到的論文之一。 ^[4]

《毀滅戰士》中的 BSP 樹

別忘了，卡馬克首次為《毀滅戰士》設計渲染器時，通過讓渲染器渲染玩家所在房間之外的臨近房間，試圖為關卡幾何圖形建立一套渲染順序。對此，BSP 樹是個不錯的選擇，因為在玩家進入之前的房間（區域）時，BSP 樹能夠避免讓渲染器重複勞動，從而節省 CPU 資源。

實際上，「將 BSP 樹引入《毀滅戰士》」意味著將 BSP 樹生成器引入《毀滅戰士》的關卡編輯器中。當完成一個《毀滅戰士》的關卡的製作時，BSP 樹就會在關卡幾何圖形的基礎上生成。根據程序員 法比安·桑格勒德 Fabien Sanglard 的說法，在原版《毀滅戰士》中，一個關卡的 BSP 樹生成時間需要 8 秒，全部關卡合計共需 11 分鐘 ^[5] 。之所以生成時間較長，部分原因在於卡馬克所用的 BSP 生成演算法，該演算法嘗試使用各種啟發式方法找出 「高質量」 BSP 樹。在運行時，8 秒的延時可能讓人無法接受；但是離線等 8 秒，時間並不算長，尤其是考慮到 BSP 樹提升了渲染器的性能。為每個關卡生成的 BSP 樹將在遊戲啟動時作為關卡數據載入。

卡馬克對 1980 年論文中提出的 BSP 樹演算法進行了改造，因為在《毀滅戰士》開始運行時，當前關卡的 BSP 樹就會讀取到內存中，渲染器通過 BSP 樹由前向後繪製物體，而非由後向前進行繪製。福克斯三人在那篇論文中演示了 BSP 樹可用於執行由後向前的畫家演算法，但是畫家演算法會造成許多重複的繪製任務，對於 IBM 兼容機來說負擔較大。因此，《毀滅戰士》的渲染器換了個方向，首先繪製距離玩家較近的圖形，之後再繪製離玩家較遠的。這種反向排序很容易通過 BSP 樹來實現，因為你可以在樹的每個節點都進行反向遍歷。為了避免繪製出來的遠處圖形遮擋到近處的圖形，《毀滅戰士》的渲染器使用了一種隱式 Z 緩衝區，這種緩衝區不僅具備普通 Z 緩衝區的優勢，而且對內存的要求也較低。這種 Z 緩衝區有兩組數組，一組記錄水平方向的遮擋關係，另兩組記錄自屏幕頂部和底部的垂直方向的遮擋關係。《毀滅戰士》的渲染器就算不使用實際的 Z 緩衝區也無傷大雅，因為從技術上來看它並不是真正的 3D 遊戲。BSP 樹數據結構的成本雖然不高，但卻能夠起作用，其原因在於《毀滅戰士》不會發生以下問題：水平方向的遮擋數組能夠發揮作用，是因為該遊戲中沒有傾斜的牆體；垂直方向的遮擋數組能夠發揮作用，是因為該遊戲不存在有著一上一下兩扇窗戶的牆體。

剩下比較棘手的問題是如何將《毀滅戰士》中處於運動中的角色融入到藉助 BSP 樹繪製的靜止的關卡幾何圖形中。該遊戲中的敵人不可能納入 BSP 樹之中，因為他們會移動，而 BSP 樹只對靜止的幾何形狀起作用。所以渲染器首先繪製靜止的關卡幾何圖形，同時與另一個內存使用效率較高的數據結構協作，記錄屏幕上分割出來用於繪製的區域。之後，渲染器按照由後往前的順序繪製敵人，並消除被屏幕上的區域遮擋住的敵人。這一過程與使用 BSP 樹進行渲染相比，效果稍差一些。但是由於關卡中能看到的敵人的數量少於幾何圖形的數量，所以速度並不是一個嚴重的問題。

將 BSP 樹應用到《毀滅戰士》中可謂一大成功。卡馬克能夠想到 BSP 樹是解決 VSD 問題的最佳方案，無疑非常高明。但是這可以稱得上是天才之舉嗎？

桑格勒德在其關於《毀滅戰士》遊戲引擎的書中引用了羅梅洛的話：內勒的論文《構建高質量的分割樹》主要講述使用 BSP 樹消除 3D 模型的背面。 ^[6] 根據羅梅洛所言，卡馬克認為這種演算法對《毀滅戰士》依然有效，所以他放手一試，將 BSP 技術應用到了該遊戲中。不過這話說得有些奉承的意味 —— 意在暗示卡馬克在別人仍然使用 BSP 樹渲染靜止的場景時，發現該技術可以用於實時遊戲領域。在《Doom 啟示錄》中也有給卡馬克戴高帽的故事。該書作者庫什納認為，卡馬克在閱讀內勒的論文之後，問了自己，「如果使用 BSP 技術創造一整個虛擬世界，而不僅僅是一張 3D 圖像，會怎麼樣呢？」 ^[7] 。

這些「片面之詞」忽視了 BSP 樹的發展歷史。當美國空軍研究人員開始意識到場景分割可能會加快渲染任務的時候，他們就對提升 實時 渲染的速度產生了興趣，畢竟他們當時試圖創建一個飛行模擬器。1980 年，同樣的案例再次出現在了福克斯等人的論文中，他們探討了 BSP 樹如何應用于飛行模擬器中，幫助飛行員進行訓練：飛行員用它來反覆練習將飛機降至同一空港。由於空港的地形不會發生改變，BSP 樹只需生成一次，即可一勞永逸。很明顯，他們考慮的是實時模擬。在論文的引言部分，福克斯等人還談到實時圖形系統必須在至少 1/30 秒內生成一張圖像，由此激勵了他們的研究。

因此，卡馬克不是第一個想到在實時圖形模擬中應用 BSP 樹的人。誠然，設想與付諸實踐是兩碼事。但是即使在實施的過程中，卡馬克受到的幫助與指導可比人們想像的要多得多。至少是到這篇文章寫成之時，BSP 樹的 維基百科詞條 頁面顯示，卡馬克參考了 1991 年 陳 Chen 和 戈登 Gordon 的一篇論文，以及 1990 年的一本教材《計算機圖形學：原理及實踐》。儘管該頁面並未提供引用信息，但可信度沒什麼問題。陳和戈登的論文介紹了運用 BSP 樹由前向後的渲染方法，這種方法與《毀滅戰士》中用到的方法基本一致，還包括了我稱之為「隱式 Z 緩衝區」的數據結構，可用於防止遠處的圖形在繪製時遮擋近處的圖形。《計算機圖形學：原理及實踐》詳細介紹了 BSP 樹，以及一些構建並展示 BSP 樹的偽代碼（非常感謝我大學的圖書館，讓我能夠一睹這本教材 1990 年的版本）。因為這本書是計算機圖形學的經典之作，所以卡馬克很可能也有一本。

然而，卡馬克發現自己遇到一個新問題：如何讓第一人稱射擊遊戲在一台 CPU 甚至都無法進行浮點操作的電腦上運行呢？通過調查研究，他證明了 BSP 樹的數據結構非常適用於實時電子遊戲渲染。儘管 BSP 樹早已提出，而且到了卡馬克的時代，相關理論已經非常成熟了，但我始終認為，卡馬克的做法可謂驚人之壯舉。也許，得到人們稱譽的應該是整個《毀滅戰士》的遊戲引擎，它的確非常精緻。我在前文也提及過，但是桑格勒德的《 遊戲引擎黑皮書：毀滅戰士 Game Engine Black Book: DOOM 》 很好地講解了這款遊戲引擎的非凡之處，以及這些優勢相互契合之法。要明白，VSD 問題只是卡馬克在編寫《毀滅戰士》遊戲引擎時需要解決的諸多問題之一。不得不說，面對不為大多數程序員所知的複雜的數據結構，卡馬克能夠查閱相關文獻，將其付諸實踐，僅此一點就足以說明其技術之精湛、匠心之獨到。

如果你喜歡這篇文章，歡迎關注推特 @TwoBitHistory，也可通過 RSS feed 訂閱，獲取最新文章（每四周更新一篇）。

1. Michael Abrash, 「Michael Abrash』s Graphics Programming Black Book,」 James Gregory, accessed November 6, 2019, http://www.jagregory.com/abrash-black-book/#chapter-64-quakes-visible-surface-determination. ↩︎
2. R. Schumacher, B. Brand, M. Gilliland, W. Sharp, 「Study for Applying Computer-Generated Images to Visual Simulation,」 Air Force Human Resources Laboratory, December 1969, accessed on November 6, 2019, https://apps.dtic.mil/dtic/tr/fulltext/u2/700375.pdf. ↩︎
3. Henry Fuchs, Zvi Kedem, Bruce Naylor, 「On Visible Surface Generation By A Priori Tree Structures,」 ACM SIGGRAPH Computer Graphics, July 1980. ↩︎
4. Fabien Sanglard, Game Engine Black Book: DOOM (CreateSpace Independent Publishing Platform, 2018), 200. ↩︎
5. Sanglard, 206. ↩︎
6. Sanglard, 200. ↩︎
7. David Kushner, Masters of Doom (Random House Trade Paperbacks, 2004), 142. ↩︎

via: https://twobithistory.org/2019/11/06/doom-bsp.html

作者：Two-Bit History 選題：lujun9972 譯者：aREversez 校對：wxy

本文由 LCTT 原創編譯，Linux中國 榮譽推出

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive