Analytical Shadows: Still Too Early?

The not-so-recent introduction of Shader Storage Buffer Object in OpenGL 4.3 (2012) opened a great variety of potential applications. It’s finally possible to do work on big data, like vertex arrays. Not that it was completely impossible before, but fortunately, we can forget about legacy tricks and workarounds that used to be  required and go straight to writing shader code.

Pre-requisites

This article assumes that the reader is familiar with 3D computer graphics concepts and techniques, such as shadows, shaders, noise, frame blending.

Exposure

3D shadows implementation, as smooth and casual as it looks in any of your video games, has been a source of controversy, pain, and confusion for all 3D programmers for generations. Countless proposals have been made, building on top of each other, and all have one point in common - make the next shadow implementation a little less ugly and buggy than the current one.

For sheer fun, how many Shadow Mapping algorithms can you remember off the top of your head? SSM, PCF, PCSS, CSM, VSM, …? They all have cool names and look great on their original PDF proposal screenshots, but somehow after a little time  another, even more advanced algo comes up - rinse and repeat. Not mentioning the shadow volumes, having enjoyed their moment of fame in 2004 before departing into oblivion.

At some point you get to the question: are shadows inherently impossible to get right? How hard is it to test if a point in space receives light or is occluded? Let’s find out.

Idea

A simple and reliable algorithm only takes a few hours of web search to develop, assuming you have a little previous experience with OpenGL. All we need is

• The light source position in 3D space
• A list of occluders, as an array of triangles
• The point position to test whether it’s occluded or lit
• A routine to test if the ray from light to point intersects any of the occluders

Obviously this needs to happen on the per-pixel basis, so the code goes into the fragment shader. The test function is easy to find on the web:

I’m omitting the function body code here as it may hurt your eyes if your linear algebra skill is not advanced enough. Anyway, it’s the foundation the rest of the experiment is built upon. All we need to know for now is whether the given triangle casts a shadow on the current fragment.

We can now call this function for every occluder triangle in the list and we have a mathematically precise answer for the problem. 

It works

With a little trial and error the simple shadow test does not take long to complete:

So all good then? Expectedly, no. This approach can’t handle more than a handful of occluder triangles in real time. The benchmarked low-power Radeon 550 (64-bit) can barely do a hundred triangles at 60FPS. Surely, a high-end GPU can do much more than this, and you can optimize the calculation and get another 2x-3x boost, but that goes out of scope of this experiment.

Hardship

What’s more important at this stage, the rendering result is not any better than e.g. shadow volumes. For reference, the latter are also pixel-perfect, but they suffer from the fact that their native output is strictly hard shadows with no half-tones. Screen space approximation filters exist, but they tend to give unrealistic, sometimes plain wrong results.

Still shadow volumes are a great deal faster than what we came up with so far. Maybe we can get soft shadows to compensate for that? 

Well, the common approach for soft shadows would be to average multiple samples, but that’s based on the fact that a single shadow test, as ugly and buggy it has been, is quite fast and you can fit multiples of them in your render cost budget.

Single analytical shadow test is very expensive, so averaging multiples of these is already a bad idea.

Still, we do have a couple of tricks up our sleeve here.

Noise

To soften the shadow edges we will use a noise function. For each fragment on the screen we will take a random point on the light source surface and use it instead of the single light source position above. The noise function is different for every frame so the pixels on the screen flicker with time.

To workaround the pixel flickering we will now apply frame blending.

At this point we finally have accurate soft shadows. The only visible downside is when the light is moving the shadows become hard until the movement stops but for moving lights it’s not critical.

Conclusion

While analytical shadows are obviously slow (while accurate), it’s interesting to test how they fare on current graphics hardware. At the same time in a short list of situations, when occluders are actually low-poly shapes (e.g. room walls), they can be even used directly with little or no modification. Curiously, it also supports partially-translucent occluder materials, unlike shadow maps or shadow volumes.

Source code available here.

Author:

Anton Duzenko

Software Architect

Anton is a co-founder of Binary Studio and an important member of Binary Studio’s executive team. He helps drive substantial growth in both the size of the business and the company’s market value. He still loves writing high quality code and is passionate about programming and engineering in general.