Ambient Occlusion

Ambient Occlusion is a cheap and simple way to add global illumination effect to an rendered image, especially for a ray tracer. This adds depth and realism to the image. The sample below shows the difference.

An image rendered with ambient occlusion.

An image rendered without ambient occlusion.

The technique is as fake as it is straight forward, but if it's good enough for Pixar should be good enough for most purposes. Ambient occlusion for certain surface point is calculated by measuring how much light is blocked by it's surroundings. In a ray tracer this is done by casting rays from the surface point in all directions and counting how many hit the scene. In the following implementation we can also limit the radius if needed and the amount of shadowing due to occlusion.

int smp = Tracer.ambientOcclusionSamples;
int c = smp;
for(int i = 0; i < smp; i++) {    
   Vec3 dir = Vec3.randomOnHemisphere(nearestHit.normal);
   dir = dir.times(Tracer.occlusionRadius);
   Vec3 org = nearestHit.location;
   Ray feeler = new Ray(org, dir);
   if( feeler.hit( nearestHit.object ) )
      c--;
}
color = color.times(1.0f - Tracer.occlusionAmount) .add( color.times((c * Tracer.occlusionAmount) / (float)smp) );

Most of the code should be staright forward and easy to understand only the Vec3.randomOnHemisphere(nearestHit.normal); function requires some explanation. As the name states, this function returns a vector, uniformly distributed on the unit hemisphere above the given vector. This is achieved by trail and error; we create random vectors in a unit cube and discard the corers to get uniform distribution on a unit sphere and than discard all the vectors not facing the same way as the given vector using a dot product test.

public static Vec3 randomOnHemisphere(Vec3 direction) {
   // Cut off the corners of the cube
   Vec3 v;
   do {
   v = new Vec3(
      2 * (float)Math.random() - 1,
      2 * (float)Math.random() - 1,
      2 * (float)Math.random() - 1);
   } while(v.length() > 1.0f && v.dot(direction)
   v.normalize();
   return v;
}

On average, no more than two thirds of the vectors are discarded. This might not be the most efficient method, but it does not require any vector transformations and matrix multiplication. Another way to achieve the same effect is to use a precalculated set of vectors distributed on the vertices of a regular polyhedron and transform it to face in the given direction. In a addition a random rotation around the main axis will remove the artifacts of using the same set of vectors.
UPDATE: It seams that this article is getting a lot more attention during the semester, so what better date to make a small correction than beginning of September.
The above method treats all rays shoot from the a certain point equally, while actually they don't contribute to the illumination of that point equally. Instead their contribution needs to be weighted by the dot product of the ray direction with the normal at that point, according to the cosine law.
I have the original sources for the tracer, but have lost the scene files. If I find them and find some time I might post an updated version of the code and a better looking image.