# Parallel-Split Shadow Mapping

- Algorithm
- step 1: calculate each $C_i$ and split the view frustum $V$ into $m$ parts.
- step 2: for each $V_i$, calculate the special
*crop matrix*using the view-projection matrix of the light. - step 3: generate the depth map from the light view using the crop matrix.
- step 4: render the scene by the depth range of $V_i$.

- References
- Code

The parallel-split shadow maps allow each map to sample a smaller area by increasing the sampling frequency in texture space. This technique requires how to determine the split positions when splitting the view frustum. In this project, scene-independent proejction is only considered.

## Algorithm

Let $m$ be the number of split, then the view frustum $V$ is split into $\{V_i | 0 \leq i \leq m - 1\}$ and the clip plane $C$ is into $\{C_i | 0 \leq i \leq m\}$. Especially, $C_0 = n$ (near plane position of the main camera) and $C_m = f$ (far plane position of the main camera). The overview of this algorithm is as follows:

- calculate each $C_i$ and split the view frustum $V$ into $m$ parts.
- for each $V_i$, calculate the special
*crop matrix*using the view-projection matrix of the light. - generate the depth map from the light view using the crop matrix.
- render the scene by the depth range of $V_i$.

### step 1: calculate each $C_i$ and split the view frustum $V$ into $m$ parts.

Note that the range of the normalized shadow plane is

[-1, 1]not [0, 1]. NDC ranges from -1.0 to 1.0 in OpenGL system.

To determine the proper split positions, consider the shadow map aliasing error $\frac{dp}{ds}$ which is divided into *perspective aliasing* and *projection aliasing*. The above figure shows that the small red edge on an object is projected on the view plane and normalized shadow plane. Let the length of this red edge be $L$. Then, $\begin{aligned} dz &= L \cdot \cos\beta \\ dy &= L \cdot \cos\alpha = \frac{dz}{\cos\beta}\cos\alpha \end{aligned}$

By triangle similarity, the shadow map aliasing error can be written as follows: $\begin{aligned} n : dp &= z : dy \\ dp &= \frac{n}{z}dy \\ \frac{dp}{ds} &= \frac{n}{z}\frac{dy}{ds} = \frac{n}{z}\frac{dz \cos\alpha}{ds \cos\beta} \end{aligned}$

In this situation, *perspective aliasing* happens when $\frac{dz}{z ds}$ is large and *projection aliasing* when $\frac{\cos\alpha}{cos\beta}$ is large. Projection aliasing occurs usually for sufaces almost parallel to the light direction, which means $\beta$ is close to $90\degree$ and $\cos\beta$ is almost zero. So this aliasing depends on local geometry details and requires an expensive scene analysis to reduce errors. Perspective aliasing, on the other hand, is caused by the viewer’s perspective projection matrix, which means that this aliasing can be imporved using a perspective projection transformation. Theoretically the optimal distribution of perspective aliasing makes the error constant over the entire depth range. So let this aliasing be a constant $c$. $\begin{aligned} \frac{dz}{z ds} &= c \\ \frac{dz}{z} &= c ds \\ \int_{-1}^{s} c ds &= c(s + 1) = \int_{n}^{z} \frac{1}{z}dz = \ln\frac{z}{n} \end{aligned}$

Considering $s = 1$ when $z = f$, the constant $c$ can be calculated. $\begin{aligned} c &= \frac{1}{2} \ln\frac{f}{n} \end{aligned}$

For finding the $i$-th clip plane position $C_i$, $s_i = 2i/m - 1$ as the resolution allocated for each split should be $1/m$ of the overall texture resolution. $\begin{aligned} \frac{s_i + 1}{2} \ln\frac{f}{n} &= \ln\frac{C_i}{n} \\ \frac{i}{m} \ln\frac{f}{n} &= \ln\frac{C_i}{n} \\ C_i &= n \left(\frac{f}{n}\right)^\frac{i}{m} \end{aligned}$

This is called *the logarithmic split scheme*. Without this, *the uniform split scheme* can be used to find $C_i$. $\begin{aligned} C_i &= n + (f - n) \frac{i}{m} \end{aligned}$

However, [1] suggests that the weighted combined version of logarithmic and uniform split schemes. So these two $C_i$ values can be mixed with linear interpolation.

### step 2: for each $V_i$, calculate the special *crop matrix* using the view-projection matrix of the light.

Once the view frustum is split, all the vertices for each $V_i$ are transformed to NDC using the view-projection matrix of the light. Note that the minimum $z$-value among the transformed vertices is set to be $-1$ so that the near plane position remains unchanged. After that, the crop matrix is calculated to effectively *zoom-in* the light’s frucstum. Note that a matrix is stored in column-major to send to OpenGL.

Note that the range of the normalized shadow plane is

[-1, 1]not [0, 1]. NDC ranges from -1.0 to 1.0 in OpenGL system.

```
glm::mat4 crop(1.0f);
crop[0][0] = 2.0f / (max_point.x - min_point.x);
crop[1][1] = 2.0f / (max_point.y - min_point.y);
crop[2][2] = 2.0f / (max_point.z - min_point.z);
crop[3][0] = -0.5f * (max_point.x + min_point.x) * crop[0][0];
crop[3][1] = -0.5f * (max_point.y + min_point.y) * crop[1][1];
crop[3][2] = -0.5f * (max_point.z + min_point.z) * crop[2][2];
```

### step 3: generate the depth map from the light view using the crop matrix.

At first, generate the depth map from the light view. In this situation, the crop matrix should be multiplied after the projection matrix of the light.

### step 4: render the scene by the depth range of $V_i$.

With the depth map from step 3, the scene can be rendered finally. However, for each $V_i$, the depth range should be adjusted considering $C_i$ and near/far plane positions.

## References

[1] Chapter 10. Parallel-Split Shadow Maps on Programmable GPUs

[2] Wimmer, Michael et al. “Light Space Perspective Shadow Maps.” Rendering Techniques (2004).