# Doing the Splits

## Circumscribing Bounding Sphere

Let’s start with a regular, symmetrical frustum that’s pointing along the $+z$ axis:

What we want to find is the circumscribing sphere, shown in grey. This reduces to finding the circumscribing circle of the maximal diagonal quadrangle of the frustum (as Michal observes in [2]):

Let’s define $A$ and $B$ as the positive corners of the frustum, plus $N$ and $F$, the centre points of the near and far planes. These can be expressed in terms of the FOV, aspect ratio and near and far depths ($n$ and $f$). We also have the centre point, $C$, and radius, $r$, of the circle.

$$\begin{array}{rcllr} A &=& [t_xn, & t_yn, & n] \\ B &=& [t_xf, & t_yf, & f] \\ N &=& [ 0, & 0, & n] \\ F &=& [ 0, & 0, & f] \\ C &=& [ 0, & 0, & c] \\ \end{array} \\ \begin{array}{rcl} \text{Where } t_x &=& \mathrm{tan}(\frac{fov}{2})*aspect \\ t_y &=& \mathrm{tan}(\frac{fov}{2}) \end{array}$$

If we rotate the frustum around the $z$ axis so that the MDQ lies on the $x-z$ plane, the coordinates of $A$ and $B$ are simply:

$$\begin{array}{rcllr} \\ A &=& [dn, & 0, & n] \\ B &=& [df, & 0, & f] \\ \end{array} \\ \text{Where } d = \sqrt{t_x^2 + t_y^2}$$

This will come in handy in a second. Next, using ‘Pythagoreas’, we have two equations for the radius:

$$\begin{array}{rcl} r^2 &=& \|\vec{NA}\|^2 + \|\vec{NC}\|^2 \\ r^2 &=& \|\vec{FB}\|^2 + \|\vec{FC}\|^2 \\ \end{array}$$

We can then equate these and solve for $c$:

$$\begin{array}{rcl} \|\vec{NA}\|^2 + \|\vec{NC}\|^2 &=& \|\vec{FB}\|^2 + \|\vec{FC}\|^2 \\ \|\vec{FC}\|^2 - \|\vec{NC}\|^2 &=& \|\vec{NA}\|^2 - \|\vec{FB}\|^2 \\ (c - f)^2 - (c - n)^2 &=& d^{2}n^2 - d^{2}f^2 \\ (c^{2} - 2fc + f^{2})-(c^{2} - 2nc + n^{2}) &=& d^2(n^{2} - f^{2}) \\ 2(n - f)c &=& d^2(n^{2} - f^{2}) + n^2 - f^2 \\ &=& (d^2 + 1)(n^2 - f^2) \\ &=& (d^2 + 1)(n + f)(n - f) \\ \therefore c &=& \frac{1}{2}(d^2 + 1)(n + f) \\ \end{array}$$

Finally, we can deduce $r$ by plugging $c$ back into one of the equations for $r^2$:

In code, all of this boils down to:

## References

[1] CSMs…
[2] Zhang, F., Sun, H., Nyman, O., “Parallel-Split Shadow Maps on Programmable GPUs”, GPU Gems 3, 2007.
[3] Valient, M., “Stable Rendering of Cascaded Shadow Maps”, ShaderX^6, 2008.
[4] Zhang, F., Zaprjagaev, A., Bentham, A., “Practical Cascaded Shadow Maps”, ShaderX^7, 2009.
[5] Andersson, J., “Shadows & Decals: D3D10 Techniques in Frostbite”, GDC 2009.