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.

Let’s say you want to round a floating point number to the nearest multiple of 5.

0   -> 0
2   -> 0
2.5 -> 5
11  -> 10
458 -> 460
etc...

On it’s own, Python’s round() function works only on values after the decimal.

So instead you need something like this function:

def RoundToNearestMultiple( value, multiple=5 ):
    return float(multiple) * round(float(value) / float(multiple))
 
print RoundToNearestMultiple(456.789, 5)
print RoundToNearestMultiple(456.789, 10)
print RoundToNearestMultiple(2, 5)
print RoundToNearestMultiple(2.5, 5)
 
>>455.0
>>460.0
>>0.0
>>5.0

As you can see, it simply finds the number of multiple‘s that go into value and rounds that to the nearest integer. It then multiplies this result by multiple to return a float that is value rounded to the nearest multiple.

So when might you want to do this?

It’s not uncommon that you have a continuous signal/function represented as a real value which needs to be discretized. Maybe you want to reduce the precision of a set of data for memory reasons. Or perhaps you want to put a set of vectors into buckets. Quantization of a vector can be used to yield grid coordinates for spatial partitioning. Basically anytime you want to down-sample a function of any kind you’re going to need something like this function.

Consider the following code snippet:

class A():
    def __init__(self):
        self.m = 1
 
a = A()
l = []
l.append(a)
l.append(a)
l[1].m = 2
 
print l[0].m
print l[1].m
 
>>2
>>2

Clearly, l contains two elements, but they are referencing the same memory. Changing the state of l[0] also changes l[1], because they are one and the same. But what if you actually want two copies of a?

import copy
 
class A():
    def __init__(self):
        self.m = 1
 
a = A()
l = []
l.append( copy.copy(a) )
l.append(a)
l[1].m = 2
 
print l[0].m
print l[1].m
print a.m
 
>>1
>>2
>>2

Now you’ve created a brand new copy of a and stored it in l[0]. Notice that changing the state of l[1] no longer affects l[0], but still changes the state of a. So a and l[1] refer to the same memory, while l[0] is a completely separate chunk of new memory.

Parenting is made much more difficult than it needs to be thanks to our specie’s spectacular failure at intrinsic value judgements and rationality. At least, that’s the only conclusion you can draw if you buy the modern theory of infant behavior.

Continue reading →

Maya’s OpenMaya module has an MScriptUtil class which allows a python programmer to pass references and pointers into various OpenMaya functions.

The process is definitely a bit painful, but at least you now have access to the functionality that would otherwise be accessible only from C++.

Here’s how you create a double and pass it by reference to a Maya API class:

 
util = om.MScriptUtil()
util.createFromDouble(0)
double_ptr = util.asDoublePtr()
 
#now you can pass this to a function that 
#takes a reference to a double
#ie someAPIFunction( double_ptr );
 
#now after the function returns, your reference
#will contain a return value which you can access like so
print om.MScriptUtil().getDouble(double_ptr)

Here’s a working example showing how to query the parameter domain of a NURBS curve:

import maya.OpenMaya as om
 
#get a MDagPath from an object name
sel_list = om.MSelectionList()
sel_list.add( "nurbsCircle1" )
dag_path = om.MDagPath()
sel_list.getDagPath(0,dag_path)
 
#create a NURBS curve function set
curve_fn = om.MFnNurbsCurve(dag_path)
 
#here's a 'normal' function call that 
#doesn't need any MScriptUtil funkiness
point = om.MPoint()
curve_fn.getPointAtParam(0.5, point, om.MSpace.kWorld)
 
#uh, oh this next function takes two doubles by REFERENCE (ie &double),
#so lets jump through some hoops to make two of them...
 
min_util = om.MScriptUtil()
min_util.createFromDouble(0)
min_ptr = min_util.asDoublePtr()
 
max_util = om.MScriptUtil()
max_util.createFromDouble(0)
max_ptr = max_util.asDoublePtr()
 
#and now we can call our function...
curve_fn.getKnotDomain( min_ptr, max_ptr )
 
#and get the actual value out of the pointer
print om.MScriptUtil().getDouble(min_ptr), om.MScriptUtil().getDouble(max_ptr)

I find excessive nesting to be one of the most common annoyances when deciphering someone else’s code. Nobody wants to work on a function that’s nested 10 levels deep and lost in if/else hell. Every additional level of nesting makes your code more tightly coupled and less modular.
Continue reading →

How to distribute wealth amongst the citizens in an economy is the most important question in economics. In a sense, that’s really all that economics is about. If you get this question right, you can maximise prosperity and personal freedoms. Get it wrong, and you have crime, poverty and war.

The coming decades are going to completely break our current method of wealth distribution.

The labour-for-wealth exchange is disappearing, and along with it, our ability to survive. If we don’t transition smoothly into a post-labour society, the Occupation in Wall Street is going to spill into main street.

Continue reading →

Having spent nearly two years out of the AAA game development world, I’m excited and eager to get back into a dynamic studio environment.

Capcom Vancouver (previously Blue Castle Games) make great games, with an emphasis on fun (Dead Rising 2). Perhaps more importantly, for me, they put a lot of emphasis on having great technology (including a custom game engine) and a top-notch toolset to support it. I’ve never seen such a large and talented crew of programmers on any game project. It’s quite the spectacle.

On a more personal note, I’ve taken a bit of a new career path. For the first time in my career, I’m a full-on programmer. I will still be straddling the art side of things to the extent that I have to in order to understand their needs; but my day-to-day work will be to create content-creation toolsets.

Making tools used to make art. Awesome.