前言

开放世界游戏中植被和物件的数量往往是巨大,  而传统组织大量植被渲染的方式是利用QuadTree/Octree/Kd-Tree等数据结构对植被Intance数据进行预先生成一个个Cluster，然后在运行时进行FrustumCull,收集可视的所有Cluster，最后进行DrawInstance.

这种方式往往存在两个缺点: 

[1]Cluster粒度和DrawInstance渲染的粒度冲突,也就是单个Cluster粒度很大时，很多位于视椎体外的Instance是浪费的绘制(VS/PS上的浪费)。而当Cluster粒度比较小时, DrawInstance渲染批次可能会明显上升。

[2]第二个缺点是完全依赖CPU的剔除, 从效率上很难做到单个Instance的高效剔除。

 对于上面两点，基于GPU剔除的方案可以很好解决这个问题.

CPU Cull + GPU Cull

CPU Cull(QuadTree)

以四叉树组织Instance数据

static class QuadTreeUtil
{
    public const int QUAD_TREE_NODE_MAX_NUM = 128;
}

[Serializable]
public struct InstanceData
{
    public Vector4 instance;
    public InstanceData(Vector3 inPos, int clusterId)
    {
        instance = new Vector4(inPos.x, inPos.y, inPos.z, (float)clusterId);
    }
}


[Serializable]
public class QuadTree
{
    [NonSerialized]
    public Vector3[] alllTreePos;
    
    [HideInInspector]
    public InstanceData[] instanceDatas;
    private int[] treeCullFlags;
    public TreeNode rootNode;
    public int leafId;

    public QuadTree(Vector3[] inAllTreePos, Vector2 regionMin, Vector2 regionMax)
    {
        List<int> indices = inAllTreePos.Select((item, index) => index).ToList();
        alllTreePos = inAllTreePos;
        leafId = 0;
        rootNode = new TreeNode(this, indices, regionMin, regionMax);
        BuildTreeClusterData();
    }
}

 默认下每个叶子节点最大数量为128个Instance

 Instance数据得记录所在的Cluster(leafNodeId)

所以CPU阶段的QuadTree主要是两个作用：

[1]收集InstanceDatas

[2]在CPU每帧进行QuadTree的粗粒度Frustum剔除，求出可见的leafNode Id集合。这里的leafNode Id集合用固定大小数组int[] 来表示, 1代表被剔除，0代表可见，用于后续的GPU剔除。

GPU Cull

GPU Cull是利用ComputeShader针对单个Instance进行的剔除，主要分为三步:

[1]基于CPU的粗粒度QuadTree剔除的结果，在GPU可以直接进行第一轮剔除

 [2]在GPU针对Instance进行 SphereFrustumCull 进行第二轮剔除

 [3]基于HZB(Hierarchical Z-Buffering 分层 Z 缓冲)的遮挡剔除, 就是根据当前物体的渲染深度和它的在上一帧渲染的HZB的深度作对比来判断物体是否被遮挡。

 HZB的原理和生成推荐 这篇博客 Compute Shader 进阶应用:结合Hi-Z 剔除海量草渲染 - 知乎

文章介绍的HZB生成方法质量比较不错，HZB各级Mip 像素偏移和丢失的现象较少。

最终GPU 剔除的ComputeShader如下：

// Each #kernel tells which function to compile; you can have many kernels
#pragma kernel CSMain
#pragma enable_d3d11_debug_symbols
//#pragma use_dxc
// Create a RenderTexture with enableRandomWrite flag and set it
// with cs.SetTexture

StructuredBuffer<float4> instanceDatas;
StructuredBuffer<int> treeNodeCullFlag; // 1 mean culled, 0 mean visible
RWStructuredBuffer<float3> posVisibleBuffer;
RWStructuredBuffer<int> bufferWithArgs;

int allCount;
float4 bounds; // center + radius
float4 frustumPlanes[6];
float3 cameraWorldDirection;
float4x4 worldToViewProject;
Texture2D<float4> hizTexture;
float hizMapSize;
int maxHizMapLevel;


float GetDistance(float3 pos, float4 plane)
{
    return plane.x * pos.x + plane.y * pos.y +  plane.z * pos.z + plane.w;
}

int IsOutOfFrustum(float3 pos, float radius, float4 frustum[6])
{
    for(int i = 0; i < 6; i++)
    {
        float distance = GetDistance(pos, frustum[i]);
        if(distance >= radius)
        {
            return 1;
        }
    }

    return 0;
}


float3 TransformToNdc(float3 worldPos)
{
    float4 worldAlignPos = float4(worldPos, 1.0);
    float4 ndc = mul(worldToViewProject, worldAlignPos);
    ndc.xyz /= ndc.w;
    ndc.xy = ndc.xy * 0.5 + 0.5;
    return ndc.xyz;
}

int GetHizMapIndex(float2 boundMin, float2  boundMax)
{
    float2 uv = (boundMax - boundMin) * hizMapSize;
    uint2 coord = ceil(log2(uv));
    uint index =  max(coord.x, coord.y);
    return min((int)index, maxHizMapLevel);
}

bool IsCullByHizMap(float3 pos, float boxWidth)
{
    float3 offsetPos = pos;
    float3 ndc1 = TransformToNdc(pos + float3(boxWidth, boxWidth, boxWidth));
    float3 ndc2 = TransformToNdc(pos + float3(boxWidth, -boxWidth, boxWidth));
    float3 ndc3 = TransformToNdc(pos + float3(boxWidth, boxWidth, -boxWidth));
    float3 ndc4 = TransformToNdc(pos + float3(boxWidth, -boxWidth, -boxWidth));
    float3 ndc5 = TransformToNdc(pos + float3(-boxWidth, boxWidth, boxWidth));
    float3 ndc6 = TransformToNdc(pos + float3(-boxWidth, -boxWidth, boxWidth));
    float3 ndc7 = TransformToNdc(pos + float3(-boxWidth, boxWidth, -boxWidth));
    float3 ndc8 = TransformToNdc(pos + float3(-boxWidth, -boxWidth, -boxWidth));

    float3 min0 = min(min(ndc1, ndc2), min(ndc3, ndc4));
    float3 min1 = min(min(ndc5, ndc6), min(ndc7, ndc8));
    float3 boundsMin = min(min0, min1);

    float3 max0 = max(max(ndc1, ndc2), max(ndc3, ndc4));
    float3 max1 = max(max(ndc5, ndc6), max(ndc7, ndc8));
    float3 boundsMax = max(max0, max1);
    uint mip = GetHizMapIndex(boundsMin, boundsMax);

    float currentHizMapWidth = hizMapSize / pow(2, mip);
    float2 uv0 = min(currentHizMapWidth - 1, floor(boundsMin.xy * currentHizMapWidth));
    float2 uv1 = min(currentHizMapWidth - 1, floor(boundsMax.xy * currentHizMapWidth));

    float d0 = hizTexture.mips[mip][uv0].r;
    float d1 = hizTexture.mips[mip][uv1].r;
    return boundsMax.z < d0 && boundsMax.z < d1;
}


[numthreads(16, 16,1)]
void CSMain (uint3 id : SV_DispatchThreadID)
{
    uint instanceId = id.x * 1500 + id.y;
    if(instanceId >= allCount)
        return;
    
    float4 instance = instanceDatas[instanceId];
    int clusterId = (int)instance.w;
    if(treeNodeCullFlag[clusterId] == 1)
        return;

    float3 worldPos = instance.xyz;
    float3 pos =  worldPos + bounds.xyz;
    if(IsOutOfFrustum(pos, bounds.w, frustumPlanes) == 0 && (!IsCullByHizMap(pos, bounds.w)))
    {
        int currentIndex;
        InterlockedAdd(bufferWithArgs[0], 1, currentIndex);
        posVisibleBuffer[currentIndex] = worldPos;
    }
}

Draw Instance Indirect 

利用GPU剔除得到的RWStructuredBuffer<float3> posVisibleBuffer 和 RWStructuredBuffer<int> bufferWithArgs 进行DrawInstanceIndirect。

Graphics.DrawMeshInstancedIndirect(treeMesh, 0, treeMaterial, drawIndirectBounds, bufferWithArgs, 0, null, ShadowCastingMode.Off, false);

Demo效果：

CPU：AMD 锐龙7950X

GPU:  RTX3060Ti

植被数量：200W

Cpu cull + GPU Cull: 2ms左右

Draw Instance Indirect :4.5ms左右

项目Git链接

https://github.com/2047241149/GPUFoliageCull

参考资料

[1]Compute Shader 进阶应用:结合Hi-Z 剔除海量草渲染 - 知乎

[2]https://www.cnblogs.com/mmc1206x/p/15542745

[3]Hierarchical-Z map based occlusion culling – RasterGrid

[4]Mobile hierarchical z buffer occlusion culling - 知乎

[5]Mobile GpuCulling for Unreal - 知乎

[6]Unity中使用ComputeShader做视锥剔除（View Frustum Culling） - 知乎

[7]LearnOpenGL - Frustum Culling

[8]视锥体剔除AABB和OBB包围盒的优化方法 - 知乎

[9]有没有较完善高效的视锥剔除算法？ - 知乎

[10]AABB-Plane · 3DCollisions