Simple Alternative to Clustered Shading for Thousands of Lights

Introduction
I recently spent some time experimenting with GPU ray traced shadows, and it gave me and idea for a way to handle thousands of dynamic lights in a very simple and easy to implement manner. I couldn’t find any references to anyone doing something similar, so I call it BVH Accelerated Shading. Like Clustered Shading, BVH Accelerated Shading will work with both forward and deferred renderers.

Compared to clustered shading, the idea is simple, both in concept and implementation. It should be very easy to add BVH Accelerated Shading to your engine’s renderer, as it does not require any additional passes or compute shaders. My main contribution is the observation that with the right data-structure you can forgo the costly clustering and light assignment steps, and cheaply cull the lights affecting each pixel directly in the fragment program while shading.

BVH Accelerated Shading can broadly be broken down into three parts, the first of which is already present in most engines:

1. Build and maintain a spatial hierarchy of lights. I have all my scene objects, including lights, in a single BVH – storing them in a separate tree might be a better idea.
2. Pack the visible lights from your scene into a BVH of spheres for stackless traversal on the GPU. I use the same tree topology as my scene BVH, but prune branches with no visible lights.
3. For every pixel, using it’s world position, traverse the BVH and gather the lighting.

1. Build and maintain a spatial hierarchy of lights
For building and maintaining the BVH of scene objects in my engine, I have extended the ideas from [1] to handle N-ary trees with a maximum branching factor of 8. This was done by modifying the direct insertion cost of nodes with less than 8 children.

In my implementation, the BVH is built and maintained on the CPU. This is fast enough in most cases, as most game engines are already doing this.

2. Pack the visible lights from your scene into a “Stackless BVH”
The following packing is also done on the CPU, as it is also generally very fast.

To pack the lights into an appropriate format for fast gpu traversal, I have implemented the ideas from [2]. I start by traversing the scene’s BVH and ignore any branches that are invisible or contain no lights. For each node encountered during traversal, I pack it’s data into a structured buffer for GPU traversal in a fragment program. The topology of the stackless BVH is identical to that of my scene’s BVH, barring any pruned branches. I use spheres for the stackless BVH, as this simplifies the GPU traversal algorithm.

The structure of the BVH nodes on the GPU looks like this:

struct sPackedBVHLight
{
    float4 mPositionRadius;
    uint mMissPointer;
    uint mColor;
};

StructuredBuffer gLightBVHNodeData;

Note that it might be more efficient to store your lights separately from your other scene objects, as this could lead to a better quality tree for GPU traversal.

Going with the ideas from [2], I bake the Miss-Index (this is the index of next node in the traversal if this node is outside of the query region) for each node into the packed BVH, but have noticed that the Hit-Index (this is the index of next node in the traversal if this node is inside of the query region) is always the current index plus one, so this is not baked, but rather calculated in the fragment shader during traversal. Baking the Hit and Miss pointer into the packed node data simplifies traversal, and removes the need for a stack.

3. For every pixel, traverse the BVH and gather the lighting.
After retrieving the world position of the pixel, I traverse the BVH, summing up the reflected light (based on material properties) for each light encountered.

The fragment shader traversal follows this structure:

struct sUnpackedBVHLight
{
    uint mHitPointer;
    uint mMissPointer;
    float4 mPositionRadius;
};

sUnpackedBVHLight UnPackLightNode(uint Index)
{
    sPackedBVHLight node = gLightBVHNodeData[Index];
    sUnpackedBVHLight ret = (sUnpackedBVHLight)0;

    ret.mHitPointer = Index + 1;
    ret.mMissPointer = node.mMissPointer;
    ret.mPositionRadius = node.mPositionRadius;

    return ret;
}

float3 UnPackLightColor(sPackedBVHLight Node)
{
    sPackedBVHLight node = gLightBVHNodeData[Index];
    float3 ret = (float3)0;

    ret.r = (node.mColor & 0x00ff0000);
    ret.g = (node.mColor & 0x0000ff00);
    ret.b = (node.mColor & 0x000000ff);

    ret /= float3(255 * 255 * 255, 255 * 255, 255);

    return ret;
}

float3 GatherLighting(float3 Position, float3 Normal)
{
    float3 lighting = (float3)0;
    uint index = 0;
    do
    {
        sUnpackedBVHLight node = UnPackLightNode(index);

        float3 V = node.mPositionRadius.xyz - Position;
        float d = dot(V, V);

        // Check if the Position is inside the bounding volume
        if (d < node.mPositionRadius.w*node.mPositionRadius.w)
        {
            // Check is this is a leaf node
            if (node.mHitPointer == node.mMissPointer)
            {
                lighting += BRDF(
                    Position, Normal,
                    node.mPositionRadius,
                    UnPackLightColor(index)
                );
            }
            index = node.mHitPointer;
        }
        else
        {
            index = node.mMissPointer;
        }

    } while (index != 0x0000ffff);

    return lighting;
}

Results:

Scene with 2700 3240 dynamic lights, most of them visible here.

So, I’ve implemented BVH Aceelerated Shading in my little engine. It hasn’t got a very efficient renderer, especially when it comes to drawing text and lines (there is no batching either). So I think there are a few bottlenecks in various places. My test scene has 2700 3240 dynamic lights and about 450 objects. The lighting pass also does IBL and uses GGX for the specular reflection on the lights.

In the above screenshot, rendered at 1280×720, most of the lights are visible. I’m using an ATI Radeon r9 280x. Given all that, according to AMD Perf studio, it takes about 22ms to fill my gbuffers (terrible, I know!), and about 5ms to calculate the lighting. Here you can download the .pro file from AMD PerfStudio that I captured just after taking the above screenshot, or see the screen-grabs here:

SB4 is filling the g-buffers and SB5 is doing the full screen lighting pass. I’m no expert, but that seems pretty fast to me, for very little effort in terms of implementation.

I know it’s not a direct comparison, but the results from the Necropolis test scene with 2500 lights using Clustered Shading, reports timings of 2.3ms for clustering view samples, 1.6ms for light assignment, and 5.6ms on shading. I’m not sure what GPU or shading model they are using.

Demo:
You can download the demo here. The demo requires DirectX 11 and is compiled for Shader Model 4. Run AppLoader_Win32.exe, the controls are WASD and right mouse button to rotate the view. The scroll wheel changes your movement speed. I apologize for it taking so long to load (about 30s), I’m working on that and will upload a fix soon.

Pros of BVH Accelerated Lighting:

• Very easy to implement, minimally invasive on your render pipeline
• Doesn’t suffer from inherent depth complexity issues as in 2d/3d tiled methods
• Doesn’t require a compute shader or and additional passes
• Can be used with Forward and Deferred renderers

Cons:

• Requires tree traversal which has logarithmic complexity in the number of lights, where clustered shading with a 3d texture is more or less a constant lookup time.

Ideas and Extensions:
The first thing that comes to mind is how to handle other light types, like a spot light? The simplest way would be to use the minimum bounding sphere of whatever light bounding volume you have – so the minimum bounding sphere of the sphere-capped-cone of the spotlight.

Other bounding volume types could also be used, or even other trees such as OcTrees or KDTrees. There are quite a few unused bits in the packed light node structure, so one could use them as flags for the node BV type.

You could use separate structures of arrays rather than arrays of structures to better pack the data when using multiple light types. You could have a separate array for each light type, using some flag bits to select one.

If you’re generating virtual point lights on the GPU, then you could also build your BVH on the GPU, there are many fast methods to do that.

References:
[1] Jirí Bittner, Michal Hapala and Vlastimil Havran – Fast Insertion-Based Optimization of Bounding Volume Hierarchies.
[2] Charles Lohr – GPU-Based Parallel Stackless BVH Traversal for Animated Distributed RayTracing.

 
Follow @LukeMamacos

Advertisement

Privacy Settings