Constructing Tile Frustums for Tiled Light Culling

Contents

• Introduction
• Tile Frustum
• Deriving Equation for Left Plane
• Deriving Equation for Right Plane
• Deriving Equation for Bottom Plane
• Deriving Equation for Top Plane
• Point-Frustum Test
• Implementation

Introduction

Tiled light culling is an optimization technique in rendering used in forward+ and tiled deferred rendering pipelines. It involves splitting the screen into tiles, constructing a frustum for each tile, and testing them for intersection with light bounding volumes. Only the lights that intersect with a tile frustum will be processed in the shading of the pixel within that tile. This reduces the shading complexity, and enable the rendering pipeline to handle scenes with large number of lights, while maintaining interactive frame-rate.

This blog article discusses the derivation and the implementation of the left, right, top, and bottom planes of the tile frustum. The derivation of the near and the far plane of the tile frustum will be discussed in a seperate blog post, since it involves the addition of a depth prepass in the rendering pipeline, as well as the parallel reduction of the depth values of each pixel within a tile.

Tile Frustum

Let \(W \times H\) be the screen resolution. Suppose the screen is dissected into \(N_x \times N_y\) tiles \(T_{ij}\) with equal resolution \(R_x \times R_y\), where

A frustum consists of \(6\) planes: top, bottom, right, left, near, and far. The equation of a plane \(P\) is defined as the points \(Q\) such that:

We want to construct the view-space frustum \(F_{ij} = \{ \pi_{ij}^L, \pi_{ij}^R, \pi_{ij}^T, \pi_{ij}^B, \pi_{ij}^N, \pi_{ij}^F \}\) of the tile \(T_{ij}\). We know that the range of screen coordinates of tile \(T_{ij}\) is

Since the ndc coordinates are in the range of \([-1, 1]\), then each tile has ndc resolution of \(\frac{2}{N_x} \times \frac{2}{N_y}\). This means that the range of ndc coordinates of tile \(T_{ij}\) is,

Deriving Equation for Left Plane \(\pi_{ij}^L\)

Now, let’s start by deriving the equation for the left plane \(\pi_{ij}^L\) of the frustum \(F_{ij}\). The points that lie on the plane \(\pi_{ij}^L\) are the set of points \(q_{view}\) in view-space such that when converted to ndc, their x-coordinates is equal to \(x^{ij}_{ndc, min}\). More formally,

We know that

We also know that

Hence,

This means that the equation of the left plane \(\pi_{ij}^L\) of the frustum \(F_{ij}\) is

Deriving Equation for Right Plane \(\pi_{ij}^R\)

Next, let’s derive the equation of the right plane \(\pi_{ij}^R\) of the frustum \(F_{ij}\). The points that lie on the plane \(\pi_{ij}^R\) are the set of points \(q_{view}\) in view-space such that when converted to ndc, their x-coordinates is equal to \(x^{ij}_{ndc, max}\). More formally,

We know that

We also know that

Hence,

This means that the equation of the right plane \(\pi_{ij}^R\) of the frustum \(F_{ij}\) is

Deriving Equation for Bottom Plane \(\pi_{ij}^B\)

Now, let’s start by deriving the equation of the bottom plane \(\pi_{ij}^B\) of the frustum \(F_{ij}\). The points that lie on the plane \(\pi_{ij}^B\) are the set of points \(q_{view}\) in view-space such that when converted to ndc, their y-coordinates is equal to \(y^{ij}_{ndc, min}\). More formally,

We know that

We also know that

Hence,

This means that the equation of the bottom plane \(\pi_{ij}^B\) of the frustum \(F_{ij}\) is

Deriving Equation for Top Plane \(\pi_{ij}^T\)

Next, let’s derive the equation of the top plane \(\pi_{ij}^T\) of the frustum \(F_{ij}\). The points that lie on the plane \(\pi_{ij}^T\) are the set of points \(q_{view}\) in view-space such that when converted to ndc, their y-coordinates is equal to \(y^{ij}_{ndc, max}\). More formally,

We know that

We also know that

Hence,

This means that the equation of the top plane \(\pi_{ij}^T\) of the frustum \(F_{ij}\) is

Point-Frustum Test

Consider an arbitrary plane \(P\) and a point \(q\). We know that the equation

gives the signed distance \(d\) between the point \(q\) and the plane \(P\). If \(d \geq 0\), then \(q\) is on the side of the plane to where normal vector of the plane points; or in other words, \(q\) is on the positive side of the plane. On the other hand, if \(d \leq 0\), then \(q\) is on the side of the plane opposite to where the normal vector of the plane points; or in other words, \(q\) is on the negative side of the plane.

Now, to be able to test whether the point \(q_{view}\) is inside frustum \(F_{ij}\), the following conditions must be true:

• \(q_{view}\) is on the positive side of the plane \(\pi_{ij}^L\)

• \(q_{view}\) is on the negative side of the plane \(\pi_{ij}^R\)

• \(q_{view}\) is on the positive side of the plane \(\pi_{ij}^B\)

• \(q_{view}\) is on the negative side of the plane \(\pi_{ij}^T\)

More formally,

To simplify the test of whether the point \(q_{view}\) is inside the frustum \(F_{ij}\) or not, we are going to flip the normal of the right plane \(\pi_{ij}^R\) and the top plane \(\pi_{ij}^T\), so that they are in the opposite directions to the normal of the left plane \(\pi_{ij}^L\) and bottom plane \(\pi_{ij}^B\) respectively. Hence, the equations of the right plane and the top plane becomes:

As a result, the point \(q_{view}\) is inside the frustum \(F_{ij}\) if all of the following conditions are true:

• \(q_{view}\) is on the positive side of the plane \(\pi_{ij}^L\)

• \(q_{view}\) is on the positive side of the plane \(\pi_{ij}^R\)

• \(q_{view}\) is on the positive side of the plane \(\pi_{ij}^B\)

• \(q_{view}\) is on the positive side of the plane \(\pi_{ij}^T\)

or more formally,

Below are the updated equations of for the left, right, top, and bottom planes of the frustum of the tile.

Implementation

Below is the code for a function that computes the left, right, top, and bottom planes of the frustum of all tiles.

std::vector<glm::vec4> ComputeTileFrustums(glm::uvec2 numTiles, glm::mat4 projectionMatrix)
{
    std::vector<glm::vec4> tileFrustums(numTiles.x * numTiles.y * 4);
    
    glm::vec4 row1 = glm::vec4(projectionMatrix[0][0], projectionMatrix[1][0], projectionMatrix[2][0], projectionMatrix[3][0]);
    glm::vec4 row2 = glm::vec4(projectionMatrix[0][1], projectionMatrix[1][1], projectionMatrix[2][1], projectionMatrix[3][1]);
    glm::vec4 row4 = glm::vec4(projectionMatrix[0][3], projectionMatrix[1][3], projectionMatrix[2][3], projectionMatrix[3][3]);
    
    float stepX = 2.0f / (float)numTiles.x;
    float stepY = 2.0f / (float)numTiles.y;
        
    for(int x = 0; x < numTiles.x; x++){
        for(int y = 0; y < numTiles.y; y++){
            float offsetX = (float)x * stepX;
            float xMin = -1.0f + offsetX;
            float xMax = xMin + stepX;
            float offsetY = (float)y * stepY;
            float yMin = -1.0f + offsetY;
            float yMax = yMin + stepY;
                        
            std::array<glm::vec4, 4> frustum;
            frustum[0] = row1 - (row4 * xMin);
            frustum[1] = (xMax * row4) - row1;
            frustum[2] = row2 - (row4 * yMin);
            frustum[3] = (yMax * row4) - row2;
            
            for(int i = 0; i < 4; i++)
                frustum[i] /= glm::length(glm::vec3(frustum[i]));
                
            int baseIndex = (y * numTiles.x * 4) + (x * 4);
            for(int i = 0; i < 4; i++)
                tileFrustums[baseIndex + i] = frustum[i];
        }
    }
        
    return tileFrustums;
}