前言
作為一個先看了《DOOM啟示錄》才邁進遊戲行業的人來說，聽了重輕老師《遊戲帝國 第二季》中講id software的部分真的感觸很多。因此這周決定就從節目中提到的BSP開始，簡單講講遊戲中空間劃分（Spatial Partitioning）的脈絡和應用。
遊戲中的空間劃分思想往往由加速數據結構和遍歷算法兩部分構成，兩者配合得當時就可以得到以空間換效率的效果，一定程度上突破當時畫面渲染物體數的上限。一般來說加速結構是基於預計算的，因此會對動態物體有諸多限制——動態物體較多時每幀需要重算的數據量較大，甚至可能無法通過加速結構來優化，這往往意味著整體畫質會下降。（*前一期有一個評論說戰地遊戲裡的場景破壞要素少了，可能就是精度上去了反而破壞不動了）
由於最早應用到遊戲中已經是90年代，那還是一個前顯卡時代，本文介紹的有些技術現在已經是時代的眼淚了，隨著硬件的發展僅保留了部分思路或者產生了全新的做法；新時代的加速設計更多是面向GPU的並行計算特性。
本文最後一節會介紹的Clustered Forward Rendering雖然也會對空間做劃分，但這種運行時的劃分更多是基於並行計算了（中間仍可以採用預計算的空間劃分加速結構，兩者不矛盾）。介紹這一課題時會節選一小段《Siggraph2016 - The Devil is in the Details: idTech 666》的內容，帶大家一起看看一下新DOOM中對於這項技術的應用，作為對寫本篇初衷的一個呼應。（原文標題就有 idTech 666，具體不知是什麼梗）
1 BSP——Binary Space Partitioning
關於如何劃分二維空間可以去聽機核《遊戲帝國 第二季 EP4》中重輕老師的講解，或者是參照我後面提供的Wiki地址或其它網絡資料。例如第一步切割的時候，結果如下圖：
作為這裡的平面切割的例子，每個被完整切割的節點都包含一個線段及其方向。理論上得到的二叉樹儘量左右平衡最好，如何選取開始切的這條邊在Games101系列課中也有論述，有興趣也可以去看看。
以圖中切割完畢的結果為例，左側節點為後，右側為前，線段對應雙面多邊形。這裡簡單的把對應的遍歷方案來過一遍：
針對已經劃分好的樹，從V點遍歷
基本的遍歷算法可以描述如下：
1）如果當前是葉子節點，則渲染其多邊形
2）如果V在當前節點前面：
3）如果V在當前節點後面：
渲染右側節點對應的多邊形——渲染當前節點對應的多邊形——渲染左側節點對應的多邊形
4）否則V點一定在當前節點的相關平面上，那麼:
渲染左側節點對應的多邊形——渲染右側節點對應的多邊形
下面來推演執行一下。假設視點為V，從樹的根節點A開始（遞歸進行）：
- A——V在A前面，類型2，進入B1；
- B1——V在B1後，類型3，進入D1；
- D1——葉子節點直接渲染；
- （回上一級）B1——渲染B1，繼續類型3，進入C1；
- C1——葉子節點直接渲染
...
按這種遞歸思路，最後得到的渲染順序是 (D1, B1, C1, A, D2, B2, C2, D3) 。當然實際運作時也可以先排序再考慮渲染的問題。
*再聯動一下《遊戲帝國 第二季 EP2》，其中有提到當時某個加速卡Z-Buffer過慢導致動態物體閃爍的問題，當時之所以靜態物體不需要Z-Buffer就是被BSP解決了場景排序。
常見的三維BSP劃分有兩種：基於多邊形表面的劃分和基於軸對齊的劃分。基於多邊形表面的劃分，這樣劃分完後每一段是可以嚴格落入一個葉子節點的；而基於軸對齊的劃分是一類比較粗略的劃分，但好處是有更快的計算性能（少用或不用除法）。
其它還有一些遊戲中常用的基於軸對齊的劃分方式，如：KD樹、四叉樹、八叉樹等，分別有其不同的劃分方式和遍歷方式，這裡就不展開了。（*其中KD樹可以認為是一種特殊的軸對齊BSP樹）
軸對齊BSP
對於一個物體落在兩個區域的情況（圖中黃色三角），劃分時要麼使其存儲在上一級節點中，要麼使其分別存儲在多個子節點中。前者有精度不足影響效率的問題，後者有如何規避計算渲染兩次同一個物體的問題。所以實際各種劃分方式都在盡力規避這種情況。
2 PVS——Potentially Visible Set
在3D引擎蓬勃發展的過程中，很長一段時間內場景渲染最好的加速方式就是算好遮擋剔除（之前有一篇文章簡單介紹過）。某一段時間，對於分房間的室內場景人們提出了Portal方式渲染和PVS（最小可見集）加速結構，簡單來說就是分房間，並提前確定房間之間的可見性。
一個簡單的房間關係的例子
其中portal渲染指的是計算當前視錐體內再額外劃分出的一些小的視覺通道（如門、窗等），PVS則可以為這個思路額外排除一些確定看不到的房間及物體。
以圖中A房間為例，即使A房間內視錐體可以覆蓋到E房間，但經過3個portal和對應的PVS也排除了E房間。
不過這個方案侷限性也很明顯，除了明顯需要更多存儲和內存以外：
- 必須是以房間為主的場景
- 房間的關係需要一定的人為定製來保證
- 不支持無限破壞房間增加不可預期的portal出口，不支持完全動態的場景
3 BVH——Bounding Volume Hierarchy
BVH（包圍盒層級）是對空間中物體的另一種劃分方式，主要用來解決可見性問題（通過求是否相交）。如果說BSP、KD-Tree之類都是空間劃分（Space Partitioning），BVH則是一種物體樹狀層次結構——下面簡稱物體劃分。
BVH遍歷的例子
BVH遍歷的基本思路是：如果和父節點（大包圍盒）相交或包含，逐步檢測子節點是否相交或包含；可以略過完全不相交的節點及其子節點。
考慮到遊戲中物體多邊形複雜度逐漸提高等原因，如果仍沿用軸對齊的空間劃分會有很多落入多個空間的物體，因此也有越來越多使用BVH方式作為加速結構的遊戲。
比較空間劃分和物體劃分，可以想到兩者的區別如下：
- 空間劃分——劃分的空間子集是不重疊的，但物體有可能落入多個子集
- 物體劃分——劃分的空間子集是可能重疊的，但物體僅屬於一個子集
BVH相比早期的空間劃分更多的是一種權衡而不是替代，它的提出晚於空間劃分，雖不復雜但是也很有效。實時光線追蹤的運算中也仍在使用BVH。
4 Clustered Forward Rendering
終於來到本文的“硬菜”，讓我們還是回到Doom——《Siggraph2016 - The Devil is in the Details: idTech 666》結合《DOOM (2016) - Graphics Study》。原文其實很多段落展示了渲染的方方面面，我會以翻譯原文再加上個人評述的方式來展示其中Clustered Forward Rendering的部分。
為光照和著色準備數據結構
- 起源自（後面的兩個論文，名字不翻譯了）
- 一些提升與優勢：透明表面不需要額外的pass或處理了、獨立的深度緩衝、避免了深度不連續性上的誤差（false positives 假陽性，表示一種錯判）、更多Just Works見下一頁
*這裡Just Works TM應該就是梗的陶德的那句有名的“It just works”，似乎這已經稱為遊戲行業分享中的一個名梗了，大概意思就是說一些莫名好使的東西。
準備集群數據結構
1）視錐體素化、光柵化處理流程——在CPU上每一個Job執行一個深度切片
2）對數的深度分佈——擴展了的遠平面與近平面（公式就不翻了，可以看到切片不是軸向均勻的）
3）以體塊的方式來準備物體（Voxelize是一個生造詞，這裡不完全是體素化）
- 一個物體可能是：光源、環境探針或一個貼花（decal及其原理沒提到過，有機會再說）
- 物體的形狀可能是：物體空間的包圍盒或一個錐體
- 光柵化的邊界是屏幕空間的最小xy、最大xy以及深度的邊界
準備集群數據結構
圖中包含了300個光源，1200個貼花。
下面再引一些《DOOM (2016) - Graphics Study》的段落作為補充解析（不完全是翻譯）：
基於視錐體的劃分方式
The depth test function is set to EQUAL to avoid any useless overdraw computation, thanks to the previous depth pre-pass we know exactly which depth value each pixel is supposed to have.
*之前的步驟已經進行了深度預運算，後續的分塊運算都可以基於這個深度緩衝。
In DOOM the camera frustum is divided into 3072 clusters (a 16 x 8 x 24 subdivision), the depth slices being positioned in a logarithmic way along the Z axis.
*劃分的集群數量是3072個，深度上的劃分是延Z軸以對數的方式進行。
Each cluster can hold up to 256 lights, 256 decals and 256 cubemaps.
*每一個Cluster的上限，燈光、貼花和CubeMap都是256個。（劃分這些的方式就大量用到了BVH）
the code loops over all the decals / lights of the cluster, calculating and adding their contribution.
*代碼循環一個集群中的光照和貼花，計算並彙總它們對總光照的影響。
Clustered-forward rendering is getting some attention recently: it has the nice property of handling more lights than basic forward while being faster than deferred which has to write to / read from several G-Buffers.
Clustered-forward rendering近年來得到了更多的關注。它比起傳統的前向渲染可以處理更多光源，同時又不需要像延遲渲染那樣需要頻繁訪問G Buffers，對帶寬的壓力更小。
*最後是一幀整體的性能開銷分佈。介於篇幅原因沒有再介紹與Cluster方案結合的緩衝區設計，有興趣可以去看資料。
結語
雖然這裡的新Doom不再是那個引擎技術的引領者了，不過他們在當時的idTech引擎中加入了Cluster Rendering來讓畫面有了很精細的表現，這在當時的一眾3A遊戲中仍然是很超前的。給我的感覺是即使id software被收購了，但在引擎技術和畫面質量與性能的平衡上他們還是領先的；能看出畫面質量確實大幅領先了其父公司的Bethesta的另一個引擎做出的遊戲。（後來他們的《DOOM Enternal》也發了SIG分享）
這裡還有一個題外話，就是我發現Clustered Rendering在某些場合被定義為“不同渲染機器一起協同聯網渲染”的一種技術情況，我個人不確定這個技術當前的實用度和商業前景如何，但它確實混淆了這裡Clustered Rendering的提法。我個人還是更願意把Clustered Rendering接受為一個圖形學意義上的，基於實時空間劃分，組合了延遲渲染和前向渲染的技術。
如果對於詳細計算有了解需求，可以去看看Games101系列課的光追部分，裡面包含了BSP和BVH，以及分別怎麼生成和求交點。本文主要是以我個人的理解來串了一下，主要還是想說說DOOM相關的技術，細節很多資料中都介紹了。
*下週五一期間會鴿一週，後面繼續更別的話題。
下面是一些資料的鏈接：
BSP的Wiki
PVS的Wiki
BVH的Wiki
Siggraph2016 - The Devil is in the Details: idTech 666下載地址
DOOM (2016) - Graphics Study