I took some time this weekend to experiment with a rendering technique called ambient occlusion. The method is meant to produce those soft shadows that are found in areas that are partly blocked from ambient light. Like the dark patch under a car.
The idea itself is a bit of a hack. There’s no such thing as “ambient occlusion” in the real world. There’s only photons that bounce around. More physical rendering methods can create the same effect as AO by simulating the irradiance of the scene by bouncing virtual photons around. The problem with these methods is that they take a hell of a lot of photons to make something that doesn’t look like a noisy mess. Photon mapping, as it’s called, can make some stunning imagery but you have to be willing to wait hours to see it for each frame…
So what exactly is AO? It’s a measure of what percentage of the hemisphere surrounding a given point is occluded by neighboring objects. And by occluded I mean the ambient light is being prevented from landing on that point from that direction. Closer objects will cover more of this hemisphere and thus occlude more ambient light. Remember ambient light is, by definition, light that comes from every direction. So when we’re calculating AO, we’re literally calculating a float value at each sample point that varies from 0 (fully occluded) to 1 (not occluded at all).
This occlusion value is then multiplied by our diffuse lighting to produce those beautiful soft shadows that we all like so much.
The method I implemented is based off of the GPU gems chapter by Michael Bunnel at Nvidia. His method is pretty exciting actually. Unlike previous techniques which relied on a somewhat naive and processor intensive ray-casting scheme, Bunnel proposes decomposing the scene into a series of discs. He then uses an approximate solid-angle calculation to figure out to what extent any given surface disk is occluded by all the others.
class Disc(): point = Vector3 normal = Vector3 area = float occulsion_factor = 1.0 surface_disks = GenerateDiscs( mesh ) for i in surface_disks : for j in surface_disks : if i != j: accumulateOcculusion(i,j)
So each disc checks every other disc to see how much it is occluded by it. The occlusion of disc i by disc j is a function of the distance between the discs and how much those discs are facing each other. The exact formula is given in Bunnel’s paper. I’m a bit fuzzy on it’s origins but it looks like a rough approximation of the solid angle calculation of a disc on a unit hemisphere. Regardless, it works.
This is an N^2 algorithm so it scales horribly as the number of vertices increases. Fortunately, we take advantage of the fact that AO captures low-frequency shadows which get fuzzier as the distance between the occluding and the receiving discs increases.
In my implementation, I quantized each disc into buckets. Then for each bucket, I generate a new disc which is the average of the positions and normals of the discs in that bucket and the sum of all their areas. You have to edit the nested for loop now so you test each disc against all the discs in the neighboring buckets and all the larger, averaged discs in the buckets that are further away. This gets you out of the O(n^2) trap and speeds things up significantly.
My implementation is just a rough prototype. I did it in an afternoon using Maya and python. But even so, the results are encouraging. And having implimented it, I can see there are a lot of ways this could be improved. Bunnel’s work has actually launched a mini renaissance in point-based rendering methods. This technique, or a variation of it now powers Pixar’s Renderman software. They use this point-based method to do a lot more than just AO. You can transfer not only occlusion, but color bleeding and fuzzy reflections. They’ve really turned it into a framework for all sorts of global illumination methods… and as a result, Bunnel et al won the Technical Oscar award for this in 2009.
One thing that would be nice to try is experimenting with different disc generation methods. I’m currently generating a disc per vertex and then interpolating in the interior of the face. I’d like to try a scattered poisson distribution of discs, on the interior of the faces. This would be great because you could decouple the relative density of the mesh from the AO. Larger faces would have more discs resulting in an even distribution. But perhaps most importantly, all the discs would have the same area which would greatly simplify the occlusion calculation. Something to test next week maybe…
Anyway, here’s a mesh I sculpted in 3d-coat to test with. It’s ~5000 vertices and the AO took 80 seconds to calculate using my hacked-together, un-optimized python implementation.