September 14, 2010 |  by  |  Tech

So, I’ve talked about how we render the balls in Hustle Kings, and how we achieve most of the lighting. The remaining thing that gels everything together are the shadows that the balls cast onto the table. We could have quite simply implemented these with drop shadows, small quads in the x-z plane rendered slightly above the table, with a radial alpha gradient. However, this would really not have looked anywhere near as good as we wanted, and this would not have allowed us to cast shadows onto the cushions. I also wanted each ball to cast shadows correctly onto other balls – although we ended up disabling this feature in Hustle Kings, the algorithm I’m about to describe does support this, but we were limited by z-cull requirements of the PlayStation hardware to get maximum performance.

As I mentioned in my last post, our light sources are luminous surfaces modelled by the artists, area lights effectively. I’m only really interested in the shadows caused by the light above the table, as this is far stronger than other lights in the scene, and a global solution would have introduced only subtle differences. I figured that if I treated the light above the table as a 2D rectangle positioned in 3D space, then given that the balls are perfect spheres, a simple bit of maths should give us incredibly accurate shadows.

The first step I take is to render an invisible box around the ball, using stencil masking to mask the pixels on the surface of the table that are potentially affected by the shadow. In the vertex shader, I set the extents of this box such that I clamp to the edge of the shadow as closely as possible, by projecting the light through the extents of the ball. Then, I render the front faces of this box again, only rendering to pixels that are in the stencil mask, and this time use the depth buffer to back transform into world space. Each pixel is shaded black, setting the alpha value to be equal to the proportion of the rectangular light that is occluded by the ball.

So how do I compute the proportion of the light occluded by the ball? Well, time for a bit of math. Lets say we know what point in world space we want to figure out the shadow value for, call this $T$, then set each of the following values relative to that point:-

$B = \mbox{Position of ball, relative to } T\newline R = \mbox{Radius of ball}\newline L_0 = \mbox{Position of one corner of light source, relative to } T\newline L_x = \mbox{Vector along shortest edge of light source}\newline L_z = \mbox{Vector along longest edge of light source}$

Now, let’s define a function $V(P)$, which is the visibility of a single point $P$ on the light source. This is effectively a binary function, giving a value of one if $P$ is visible, or zero otherwise. Then the total proportion of the light that is not occluded is:-

$S = \int_{x=0}^1 \int_{z=0}^1 V(L_0+xL_x+zL_z)\,dz \,dx$

Note that if $V = 1$, i.e. all points visible, then $S = 1$, as expected.

Now we want to figure out how to express $V(P)$. Consider the line $\lambda P$, we want to figure out if this intersects the ball:-

$|\lambda P - B| = R\newline \mbox{or, }(\lambda P - B).(\lambda P - B) = R^2\newline \mbox{expanding, }\lambda^2P.P - 2\lambda P.B + B.B - R^2 = 0$

This is now a standard quadratic of the form $a\lambda^2 + b\lambda + c = 0$ with:-

$a = P.P\newline b = -2P.B\newline c = B.B - R^2$

Since the table and light are always disjoint, $P$ is never zero length, assuring us that $a>0$ always. So, remembering the standard formula for solving quadratics:-

$\ \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

We don’t actually care where exactly the points of intersection occur, only whether or not this particular line intersects the sphere. So if this equation has any solutions at all, then an intersection does exist. The only way a solution would not exist would be if the expression under the square root were negative. Recall that if a solution does not exist, then there is a clear, un-occluded path to the light, and therefore $V(P)=1$. So,

$V(P) = b^2 - 4ac < 0\newline V(P) = 4(P.B)^2 - 4(P.P)(B.B - R^2) < 0\newline V(P) = (P.B)^2 < (P.P)(B.B - R^2)$

The easiest way to integrate a binary function such as this is to find the size of the interval over which the function holds true. Let’s fix a particular value for $x$ and let $L = L_0 + xL_x$. Concentrating for now just on the inner integral we have:-

$S_x = \int_{z=0}^1 V(L + zL_z) \,dz$

So set:-

$P = L + zL_z$

Recall that:-

$V(P) = (P.B)^2 < (P.P)(B.B - R^2)$

Let:-

$H = B.B - R^2$

And now expand the components of $V(P)$:-

$(P.B)^2 = (L.B + zL_z.B)^2\newline \indent= (L.B)^2 + 2z(L.B)(L_z.B) + z^2(L_z.B)^2\newline P.P = (L + zL_z).(L + zL_z)\newline \indent= L.L + 2z(L.L_z) + z^2(L_z.L_z)$

If we let:-

$K(P) = (P.B)^2 - H(P.P)$

Then:-

$V(P) = K(P) < 0$

So:-

$K = z^2[(L_z.B)^2 - H(L_z.L_z)]\newline\indent+ z[2(L.B)(L_z.B) - 2H(L.L_z)]\newline\indent+ (L.B)^2 - H(L.L)$

This is a standard quadratic equation again, this time with:-

$a = (L_z.B)^2 - H(L_z.L_z)\newline b = 2(L.B)(L_z.B) - 2H(L.L_z)\newline c = (L.B)^2 - H(L.L)$

So now we can find the roots and use this to help us to work out the size of the interval in the range $z = (0, 1)$ where $K$ is negative, which gives us the result to the inner visibility integral $S_x$. We must take care here when $a$ is close to zero, as here we need to instead solve for $bz + c < 0$.

The outer integral is more difficult to solve analytically, but it turns out we don’t need to. Notice that I chose $L_x$ to be the shortest edge of the light? Well, my solution in Hustle Kings is to integrate along $z$ as described, but then sample along $x$ and average the results. In fact, as most of the above math is scalar, after the initial dot products, using the vector pipeline of the fragment shader allows us to evaluate four samples at the same time, and it turns out that for Hustle Kings, four samples is all we need.

Conclusion

This does turn out to give us really nice shadows, but even though they look quite accurate and natural, they are still far from correct. For starters, as explained previously, we ignore all other lights in the scene except for the one above the pool table. Rather than subtracting the light contributed by this light in shadow, we simply modulate whatever the overall light level is by a visibility factor. We also don’t take light colour into account, though this doesn’t matter too much as the table light is always white. Surface normals are not considered in the evaluation of the shadow factor either.

Another more subtle point is that we weight every point in the area light above the table equally. In actual fact, the points in the light directly above the point we are evaluating (or more precisely, in the direction of the surface normal), will contribute more to the lighting, and therefore should have a greater effect on the shadow. Resolving this would involve applying a cosine falloff weighting factor to our visibility function $V(P)$, and then rescaling the result of the integral to normalise the case where $V(P) = 1$.

Despite these omissions from the algorithm, we do get much better results than we would have been able to achieve with old fashioned drop shadows, and the basis of the idea of real time analytic solutions to shadowing is there, and something I’m looking forward to exploring further.