前言
游戲開發(fā)中的植被管理一直是個棘手的問題，因為植被數(shù)量龐大，對于剔除(CPU)和渲染(GPU)都存在很大的壓力。
UE4的植被有一套獨特的管理方式, 是基于 UHierarchicalInstancedStaticMeshComponent組件實現(xiàn)了植被的視椎體剔除和合批渲染。
UHierarchicalInstancedStaticMeshComponent原理分析
HISM類關(guān)系
UFoliageInstancedStaticMeshComponent下面簡稱FSM.
UHierarchicalInstancedStaticMeshComponent下面簡稱HISM.
InstancedStaticMeshComponent下面簡稱ISM.
在UE4里FSM，HISM，ISM是UE4最常用的對網(wǎng)格Instance合批渲染組件.
這三個組件的關(guān)系類圖如下所示
FSM在UE4進行植被編輯模式的時候產(chǎn)生(掛載在AFoliageActor上).而HISM得手動進行AddInstance的合批, 由于FSM的CPU剔除和GPU合批方式基本沿用HISM，而ISM是最基本的粗暴合批，沒有精妙的CPU剔除， 所以本文重點分析HISM。
CPU剔除實例
HISM管理著同一個StaticMesh的大量實例, 假設(shè)實例數(shù)量高達(dá)1萬個，當(dāng)然在提交drawcall前并非每個Instance都得被渲染，所以得進行視錐體剔除，按照傳統(tǒng)的CPU方式，暴力進行對每一個實例視錐體剔除，CPU壓力很大。
暴力遍歷Instance進行視錐體求交對CPU性能壓力很大，往往是瓶頸的所在，因此場景管理上出現(xiàn)了各種空間管理結(jié)構(gòu)，加速CPU的實例剔除。?典型的有BSP(二叉空間樹)，Octree(八叉樹), QuadTree(四叉樹)等等。UE4的HISM針對大量Instance也有獨特的空間管結(jié)構(gòu)，我稱其為基于Cluster的N叉樹?？臻g結(jié)構(gòu)和KD樹有些類似(Build)，剔除(Cull)的過程則和二叉，四叉樹等類似，都是從大空間開始剔除，依次遞歸往子空間進行剔除，最終得到和視錐體相交的所有Instance.
HISM的空間結(jié)構(gòu)和構(gòu)建過程
上面我簡稱HISM的空間結(jié)構(gòu)為N叉樹,是因為這個N是可控的，隨著某些因素的影響變化(比如StaticMesh的頂點數(shù)量，葉子節(jié)點最大頂點數(shù)量等等)
HISM的N叉樹原理
首先說下HISM的N叉樹的數(shù)據(jù)結(jié)構(gòu)是用索引數(shù)組而非鏈表構(gòu)成的。
首先TArray<FInstancedStaticMeshInstanceData>?PerInstanceSMData存在了所有實例的WorldTransform, 憑每個Instance在數(shù)組的索引我們就能在GPU上獲取相應(yīng)的Transfrom進行VertexShader從而合批渲染。
?TArray<FClusterNode> ClusterTree存儲了整個N叉樹的結(jié)構(gòu)。FClusterNode代表了每一個樹的節(jié)點。
FClusterNode的FirstChild指當(dāng)前節(jié)點在數(shù)組ClusterTree的第一個子節(jié)點的索引，而LastChild代表當(dāng)前節(jié)點在數(shù)組ClusterTree的最后一個子節(jié)點的索引，也就是說當(dāng)前節(jié)點存在
(LastChild - FirstChild + 1)子節(jié)點，而當(dāng)前節(jié)點的BoundMax, BoundMin指的是當(dāng)前節(jié)點包含的所有實例在世界空間形成的BoundBox，而當(dāng)前節(jié)點的FirstInstance和LastInstance指當(dāng)前節(jié)點包含所有實例的第一個Instance在PerInstanceSMData的索引，而LastInstance指的是所有實例的最后一個Instance在PerInstanceSMData的索引，也就是說當(dāng)前節(jié)點擁有實例數(shù)量等于(LastInstance - FirstInstance? + 1). 當(dāng)前節(jié)點和子節(jié)點各種變量的關(guān)系如圖下所示:
?可以這樣說, 當(dāng)前節(jié)點的所有子節(jié)點所有的Instance加起來就等于當(dāng)前節(jié)點所擁有的Instance,?當(dāng)前節(jié)點所有Instance形成的BoundBox和其所有子節(jié)點的Instance形成的BoundBox涵蓋的范圍總和是一樣的。說到這里，熟悉空間剔除結(jié)構(gòu)的人看到這里大體應(yīng)該明白了HISM N叉樹的基本原理，也就是大空間包含數(shù)個小空間，大空間的BoundBox如果與視錐體相交, 那遍歷其所有子空間的BoundBox和視錐體求交，反之大空間不與視錐體相交，則其所有子空間都不可能與視錐體相交，整個過程都在遞歸進行。可以大致參考下地形渲染之四叉樹(QuadTree)?來理解。
唯一的問題在于HISM的N叉樹具體是怎么構(gòu)建的，我簡單總結(jié)，HISM的N叉樹結(jié)構(gòu)和構(gòu)建過程和KD樹有些類似
?HISM的N叉樹構(gòu)建
第一步----構(gòu)建葉子節(jié)點:? 首先生成N叉樹的所有葉子節(jié)點，覆蓋了所有Instance的Index范圍, 并且每個節(jié)點的Index范圍不重疊。
比如我們存在90個實例，并假設(shè)一個FClusterNode葉子最多容納20個實例, 則生成5個葉子節(jié)點：
[0, 19], [20, 39], [40, 59], [60, 79],[80, 90], 當(dāng)然實際上不會分得那么均勻.
這個生成葉子節(jié)點的過程是怎么發(fā)生的:
假設(shè)我們有M個實例:
(1)將所有Instance的Transform組成一個數(shù)組為TArray<FTransfrom> Positions; 而所有Instance的索引則是為TArray<Index> InstanceIndexs;
(2)對[0, M-1] 口模型劃分?jǐn)?shù)量劃分
?
如果當(dāng)前范圍實例總數(shù)量小于等于BranchingFactor，則遞歸結(jié)束, 形成一個葉子節(jié)點
BranchingFactor = clamp(葉子節(jié)點可以容納最大頂點數(shù)量 / 實例StaticMesh 0級Lod的頂點數(shù)量, 1, 1024)
?可以看出葉子節(jié)點可以容納最大頂點數(shù)量的是個可控的量
如果當(dāng)前范圍實例總數(shù)量大于BranchingFactor?，對所有實例形成的BoundBox的最長軸(X或者Y或者Z)代表的Position分量進行距離排序，如下面X軸就是最長軸
然后對排序后進行數(shù)量上二分切分(類似二分查找)，回到第二步的初始一直遞歸下去.
?最后所有遞歸結(jié)束，形成 Q個葉子節(jié)點FClusterNode, 這Q個葉子節(jié)點各自代表的InstanceIndex范圍不存在重疊，并且總和數(shù)量剛好 = 總實例數(shù)量M
?
當(dāng)然遞歸二分法下得到的InstanceIndex的分布范圍不會這么均勻, 我這里只是一個假設(shè)的例子
第二步----由葉子節(jié)點從下往上構(gòu)建上層樹節(jié)點直到根節(jié)點為止
第一步我們得到包含了全InstanceIndex范圍的一些ClusterNode節(jié)點(看上面圖所示), 下面我們進一步把這些ClusterNode都分為視為一個位置點，?位置點為一個ClusterNode內(nèi)所有實例形成的BoundBox的中心點.? 所以上面90個實例下得到5個Cluster, 就是5個位置點，一個位置點有些類似一個Instance實例
?然后利用這些位置點類似上面的第一步那樣進行二分遞歸劃分，一直往上得到根節(jié)點，當(dāng)然這里和第一步不太一樣的是，節(jié)點自下往上過程得把子節(jié)點FCsluterNode的InstanceIndex范圍歸納到母FClusterNode里，并且這里二分遞歸的終結(jié)遞歸因子和第一步形成葉子節(jié)點的終結(jié)遞歸因子不一樣。這里的BranchingFactor 變?yōu)镃VarFoliageSplitFactor，也是可控變量，默認(rèn)情況是16，也就是每16個FClusterNode子節(jié)點才能形成一個母節(jié)點FClusterNode。
?
?
?
?經(jīng)過上面的步驟最終形成空間結(jié)構(gòu)N叉樹
?
?HISM的Runtime剔除和渲染過程
?上面我們分析了在編輯器下HISM針對Instance的空間數(shù)據(jù)結(jié)構(gòu)N叉樹的構(gòu)建過程。下面就是利用這個N叉樹進行剔除的過程。首先從上面的N叉樹構(gòu)建過程，我們可以知道TArray<FClusterNode> 樹節(jié)點數(shù)組的第一個節(jié)點為根節(jié)點，并且母節(jié)點和子節(jié)點的關(guān)系為：
母節(jié)點的InstanceIndex范圍 = 所有子節(jié)點InstnceIndex范圍總和
母節(jié)點的Instance構(gòu)成的BoundBox?= 所有子節(jié)點Instnce構(gòu)成的BoundBox總和
因此整個剔除的過程是從根節(jié)點開始，自上而下進行剔除，遵循大空間BoungBox和視錐體相交, 則其子空間BoungBox也可能與視錐體相交, 反之大空間BoungBox和視錐體不相交，則子空間BoungBox絕對不可能與視錐體相交。和四叉樹等等的剔除原理基本相似。
這個剔除過程發(fā)生在??FHierarchicalStaticMeshSceneProxy::GetDynamicMeshElements 提交MeshBatch之前
?
?
?這里有個小細(xì)節(jié)的是剔除用視錐體是根據(jù)你在編輯器設(shè)置的CullDistance(UserData_AllInstances.EndCullDistance)計算出來，如下所示:
?
?最終能渲染的ClusterNode的InstanceIndex的列表加入到一個分LOD管理的可渲染列表里
?
這里連續(xù)Index的Cluster節(jié)點會在AddRun后進行合并，比如[0, 31], [32, 50]合并成[0, 50]?
最后遍歷可渲染列表的InstanceIndex分段，比如[0, 19] [30, 59]等等，來進行提交MeshBatch
?
?這里的NumBatchs一般是1，而InstanceIndex分段數(shù)量意味著MeshBatch的Elements的數(shù)量，一個MeshBatchElement就是一次DrawIndexedInstance,? 上面所說的N叉樹的每個Cluster葉子節(jié)點代表可能存在的一次DrawIndexedInstance.
?
HISM的優(yōu)缺點
優(yōu)點
以Cluster為單位(每個Cluster存儲的Instance數(shù)量可控)，在CPU進行空間N叉樹的剔除，總體上效率還可以。
缺點
因為是以Cluster為單位來剔除，假設(shè)一個簇剛還只有一個Instance在視錐體內(nèi)，則造成Cluster其他Instance的繪制浪費，cluster粒度(包含Instanc總數(shù))越大，繪制浪費越大。如果Cluster粒度小，繪制浪費比較小, 但是可能造成Cluster總數(shù)量提高，潛在的DrawCall(DrawIndexedInstance)數(shù)量也會提高。文章來源：http://www.zghlxwxcb.cn/news/detail-488484.html
參考資料
[1] HierarchicalInstancedStaticMeshComponent.h 和?HierarchicalInstancedStaticMesh.cpp文章來源地址http://www.zghlxwxcb.cn/news/detail-488484.html
到了這里，關(guān)于(UE4 4.27) UHierarchicalInstancedStaticMesh(HISM)原理分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
