Help understand frustum calculation for tile based shading

Hello, I am trying to implement tiled based forward shading in my engine but am having trouble understanding how the frustum is calculated for each tile. I have been reading about this topic on the internet and have found a few code samples but none explain the math behind the frustum plane calculation and I have been trying to wrap my head around it but have been unsuccessful so far. For now I was following this code here. I cant really understand how the following code calculates the plane equations

    minDepth = uintBitsToFloat(minDepthInt);
	maxDepth = uintBitsToFloat(maxDepthInt);

	// Steps based on tile sale
	vec2 negativeStep = (2.0 * vec2(tileID)) / vec2(tileNumber);
	vec2 positiveStep = (2.0 * vec2(tileID + ivec2(1, 1))) / vec2(tileNumber);

	// Set up starting values for planes using steps and min and max z values
	frustumPlanes[0] = vec4(1.0, 0.0, 0.0, 1.0 - negativeStep.x); // Left
	frustumPlanes[1] = vec4(-1.0, 0.0, 0.0, -1.0 + positiveStep.x); // Right
	frustumPlanes[2] = vec4(0.0, 1.0, 0.0, 1.0 - negativeStep.y); // Bottom
	frustumPlanes[3] = vec4(0.0, -1.0, 0.0, -1.0 + positiveStep.y); // Top
	frustumPlanes[4] = vec4(0.0, 0.0, -1.0, -minDepth); // Near
	frustumPlanes[5] = vec4(0.0, 0.0, 1.0, maxDepth); // Far

	// Transform the first four planes
	for (uint i = 0; i < 4; i++) {
		frustumPlanes[i] *= viewProjection;
		frustumPlanes[i] /= length(frustumPlanes[i].xyz);
	}

	// Transform the depth planes
	frustumPlanes[4] *= view;
	frustumPlanes[4] /= length(frustumPlanes[4].xyz);
	frustumPlanes[5] *= view;
	frustumPlanes[5] /= length(frustumPlanes[5].xyz);

Following the plane generation the authours multiply it by the view projection matrix which makes me think that the generation is happening in world space. Can someone help me understand the math behind this or point me to somewhere where this is explained ? Thanks !

The planes are being generated in clip space, then transformed by the inverse of the projection*view matrix to get them in world space.

In clip space, the view frustum is the region which satisfies the inequalities:
-w≤x≤w
-w≤y≤w
-w≤z≤w
So e.g. the left clip is -w≤x <=> x+w≥0 <=> x/w+1≥0 <=> x/w≥-1.
It’s probably simplest to arrange these so that they always have the form …≥0, leading to:
-w≤x => x+w≥0
x≤w => -x+w≥0
Similarly for y and z.
In each case, the left-hand size can be expressed as a dot product between the vector [x,y,z,w] and a vector defining the plane, e.g. dot(vec4(1,0,0,1), vec4(x,y,z,w)) = x+w.

Note that when tileID.x=0, negativeStep.x=0 and 1-negativeStep.x=1 (so the left plane matches the frustum’s left plane), and when tileID.x=tileNumber.x-1, positiveStep.x = 2 and -1+positiveStep.x = 1 (so the right plane matches the frustum’s right plane).

In the general case, you want to constrain x to f(i)≤x/w≤f(i+1) where i=tileID.x and f() satisfies:

  1. f(i)=a*i+b
  2. f(0)=-1
  3. f(n)=1

where n=tileNumber.x.

(2) => b=-1, (3) => a*n+b=1 => a*n-1=1 => a*n=2 => a=2/n
=> f(i)=(2*i/n)-1

So for the left plane:
f(i)≤x/w => f(i)*w≤x => x-f(i)*w≥0 => x+(1-2*i/n)*w≥0
And for the right plane:
x/w≤f(i+1) => x≤f(i+1)*w => -x+f(i+1)*w≥0 => -x+(2*(i+1)/n-1)*w≥0
Similarly for y. This gives you the calculation of negativeStep and positiveStep and of the first four planes.

Hey @GClements Thanks for the detailed response. And although, I do understand the math that you posted, I am having difficulty relating it to the code. Also I feel that my linear algebra skills are not up to the mark so I’m sorry in advance if some of the questions below sound too obvious.

Firstly, Im a little unsure, how a vec4 is used to represent a plane. are the values the coefficients a,b,c,d
in the plane equation ax + by + cz = d. If that’s true, how is then just changing the last component ( the one that is changed using the positive and negative step value) enough to calculate planes for different tiles. shouldn’t the first three component which represent the normal to the plane also change ?

Secondly, you point out that the planes are being calculated in the clip space and being transformed to the world space, which makes sense. But in the code here

frustumPlanes[i] *= viewProjection;

They are being multiplied by the view projection matrix instead of the inverse view projection matrix.

Thirdly, The planes equations here

frustumPlanes[0] = vec4(1.0, 0.0, 0.0, 1.0 - negativeStep.x); // Left
frustumPlanes[1] = vec4(-1.0, 0.0, 0.0, -1.0 + positiveStep.x); // Right
frustumPlanes[2] = vec4(0.0, 1.0, 0.0, 1.0 - negativeStep.y); // Bottom
frustumPlanes[3] = vec4(0.0, -1.0, 0.0, -1.0 + positiveStep.y);

Have normals that are parallel to the axes, this would indicate that the planes are also parallel. Eg the firs plane with normal (1.0, 0.0, 0.0) is normal to the x axis and parallel to the yz plane. but as far as I know frustum planes are not parallel to the axes but titled based on the cameras Fov. Am i missing something here.

Not quite; the equation is ax+by+cz+dw=0, which is equivalent to a(x/w)+b(y/w)+c(z/w)=-d. IOW, homogeneous w is taken into account and the “constant” coefficient is negated. Thus the equation is the dot product dot([a,b,c,d],[x,y,z,w]); this formulation allows the plane [a,b,c,d] to be transformed by the inverse view/projection matrices like a homogeneous vector.

ax+dw≥0 => (a/d)x+w≥0 => (a/d)x≥-w
IOW, you can change either a or d to obtain the same result. Similarly for y.

Are you sure about that? The code makes perfect sense if viewProjection is the inverse matrix; it would make no sense if it’s the forward matrix.

The clipping planes form a cuboid in NDC. Transforming them by the inverse projection matrix results in a frustum (truncated pyramid) in eye space.

Thanks, This really clears things up. However, one thing I don’t understand is the plane transformation. I checked the code and the planes are indeed being transformed using the view projection matrix and not the inverse view projection matrix.