This is maybe the easiest way to manage the objects in a scene and is also often a very good choice. It’s a simple uniform grid with equally sized cells/buckets/patches (or whatever you want to call it). When rendering, all that is needed for culling is to check the view frustum against these cells to determine which ones are visible. This grid can most of the time be in only 2D but can of course in special cases be 3D if necessary. This spatial data structure works well with both static and dynamic objects.

These are the different levels culling algorithms can work on.

Triangle Level

Description: Determine for each triangle if it should be culled or not.
Primary goal: Minimize triangle count.
Culling technique example: BSP 
Usage: Not used anymore, cost to much CPU.

Object Level

Description: Check each object (a group of triangles in one buffer) if they should be culled or not.
Primary goal: Minimize triangle count and keep state changes low.
Culling technique example: View Frustum Culling of Bounding Box Hierarchies
Usage: Often used.

Batch Level

Description: Will check whole batches (a group of objects in one buffer)  if they should be culled or not.
Primary goal: Minimize draw calls and triangle count.
Culling technique example:  Uniform Grid Culling
Usage: Often used.

The triangle is the basic geometry that is used when rendering. All other shapes of geometry you want to draw must be divided into triangles.

The triangle parts:

1. Face, the triangle itself, the area is what is gonna be rasterized (with normal fill mode at least).
2. Face normal, the normal to the plane which the triangle is parallell too. It is mostly used for calculating the vertex normal.
3. Vertex, a triangle has three vertices with x,y,z coordinates, they are located in the triangle corners. All transformations apply to these ones.
4. Edge, the line between vertices are called edges, a triangle has three edges. Are used for example shadow volumes.
5. Vertex normal, each vertex has a normal which decides the smoothness of the geometry.

Other data often used per vertex:

• Tangent and Binormal for per pixel lighting
• Texture coordinates (uvw-coords), sometimes more than one per vertex

Tutorial to render a triangle in DirectX10
http://msdn.microsoft.com/en-gb/library/bb172486(VS.85).aspx

Tutorial to render a triangle in OpenGL
 http://60hz.csse.uwa.edu.au/workshop/workshop0/workshop1.html

Tutorial to render a triangle in XNA
http://www.riemers.net/eng/Tutorials/XNA/Csharp/Series1/The_first_triangle.php

Tutorial to render a triangle in OpenGL ES 2.0
http://www.webreference.com/programming/opengl_es/

This is a technique for making softer shadows when doing shadow mapping. It works by filtering the result of the depth comparison. So when comparing a depth, some depths around should also be compared and the result should be averaged. This will give a softer look on the shadow edges.

It can be implemented as simple as this in a the pixel shader:

float result;
result = shadow2DProj(shadowMap,texCoord+offset[0]);
result += shadow2DProj(shadowMap,texCoord+offset[1]);
result += shadow2DProj(shadowMap,texCoord+offset[2]);
result += shadow2DProj(shadowMap,texCoord+offset[3]);
result /= 4.0; // now result will hold the average shading

The samples are often either taken in a grid-based square around the original sample location or randomly scattered around it.

Optimization:

NVIDIA has built in hardware support for doing bilinear interpolation between four samples.

ATI has fetch4 which will fetch four texture samples at the same time.  

The original paper for PCF:
http://graphics.pixar.com/library/ShadowMaps/paper.pdf

A technique that is similar (percentage-closer soft shadows)
http://developer.download.nvidia.com/shaderlibrary/docs/shadow_PCSS.pdf

A paper including lot’s of shadow mapping information, including different ways to do PCF (the image in this article is borrowed from this presentation):
http://developer.amd.com/media/gpu_assets/Isidoro-ShadowMapping.pdf

A very fast technique to render clouds as imposters which are only updated when the viewport has changed enough to make a visible error. Here’s the abstract from the paper:

“This paper presents a method for realistic real-time rendering of clouds for flight simulators and games. It describes a cloud illumination algorithm that approximates multiple forward scattering in a preprocess, and first order anisotropic scattering at runtime. Impostors are used to accelerate cloud rendering by exploiting frame-to-frame coherence in an interactive flight simulation. Impostors are particularly well suited to clouds, even in circumstances under which they cannot be applied to the rendering of polygonal geometry. The method allows hundreds of clouds with hundreds of thousands of particles to be rendered at high frame rates, and improves interaction with clouds by reducing artifacts introduced by direct particle rendering.”

Link to a webpage with much more information about this technique:
http://www.markmark.net/clouds/

Link to the paper:
http://www.markmark.net/PDFs/RTCloudsForGames_HarrisGDC2002.pdf

These are two types of regression test that might be good to do when working on a renderer and you want to be sure that the new code won’t break something else. When doing refactoring, these tests are very important too.

The easy way to do testing is to make some test scenes and manually run them all and look for errors after each change. But this will be cumbersome so more automation is needed.

Regression testing (functionality)

Create a couple of tests with scenes that contains all that should be tested. Run them and manually control so they are working. When running, the test should save a screen shot of the perfect rendered scene for later comparison.

Then a new feature has been added, the test scenes should be automatically run again and new screen shots should be rendered and compared against the original ones. Some sources suggests that the comparison can be a simple bit to bit comparison and that any difference should be noted and reported as a failure.

Regression testing (performance)

Save the fps for all performance tests and whenever a feature has been added. It should automatically run all tests again and report if any performance has changed. It’s most important if performance has decreased, but increased performance might be good to know too if your working on optimizations.

Information about how Unity does testing of their graphics code
http://aras-p.info/blog/2007/07/31/testing-graphics-code/

Some info about how to compare images in these kinds of tests:
http://www.tilander.org/aurora/2008/03/comparing-images.html

A link to information about all kinds of automated testing in games:
http://www.gamasutra.com/features/20050329/roken_pfv.htm

These developers uses a “monkey” to test their code, which seems to work good for them:
http://powerof2games.com/node/25

Some info about what regression testing is and why it is needed:
http://en.wikipedia.org/wiki/Regression_testing

How to take the samples is a big concern as it will impact what will occlude and how much. The currently best implementations takes random samples in a hemisphere in the direction of the normal. This limits the amount of self occlusion. Another problem is that if you only take the depth into consideration then a flat surface might occlude itself because of the perspective. By also comparing the normal when calculating the AO, this problem will go away.

One of the hard parts of implementing SSAO is to choose the correct smoothing technique. Because of the big cost of taking occlusion samples you want to take as few samples as possible but this will give much noise in the SSAO so the result needs smoothing. Just doing a simple gaussian blur will not be good as the blur will make the SSAO bleed. Instead a blur that considers the depth and/or normals is needed. One of those is the bilateral filter which often is used in combination with SSAO.

The steps of a simple SSAO implementation:

1. Render the scene. Save the linear depth in a texture. Save the normals in eye space in a texture.
2. Render a full screen quad with the SSAO shader. Save the result to a texture.
3. Blur the result in X
4. Blur the result in Y
5. Blend the blurred SSAO texture with the scene, or use it directly when rendering the scene.

An optimization is to render the SSAO in a lower resolution than the screen and upsample it when blurring. Another optimization is to store both the normals and the depth in a single texture.

SSAO in the NVIDIA SDK

Probably one of the best implementations of SSAO is this one by NVIDIA (although it’ rather slow). The SDK 10 has a paper about the technique and also source code!
http://developer.download.nvidia.com/SDK/10.5/direct3d/samples.html

And here’s three papers/presentations from NVIDIA describing their SSAO in detail:
http://developer.download.nvidia.com/presentations/2008/GDC/GDC08_Ambient_Occlusion.pdf
http://developer.download.nvidia.com/presentations/2008/SIGGRAPH/HBAO_SIG08b.pdf
http://developer.download.nvidia.com/SDK/10.5/direct3d/Source/ScreenSpaceAO/doc/ScreenSpace AO.pdf

SSAO in Starcraft II

Some information of how Starcraft II will use SSAO is included in this paper ( see chapter 5.5 ):
http://ati.amd.com/developer/SIGGRAPH08/Chapter05-Filion-StarCraftII.pdf

SSAO in Two Worlds

A link to a description of the SSAO implementation in the game Two Worlds:
http://www.drobot.org/pub/GCDC_SSAO_RP_29_08.pdf

SSAO in Crysis

The paper and game that started it all (look in the chapter 8.5.4.3):
http://delivery.acm.org/10.1145/1290000/1281671/p97-mittring.pdf?key1=1281671&key2=9942678811&coll=ACM&dl=ACM&CFID=15151515&CFTOKEN=6184618

Hardware Accelerated Ambient Occlusion

One of the papers that probably inspired the Crysis team:
http://perumaal.googlepages.com/

Kindernoiser SSAO

A simple but smart SSAO implementation, here with well commented shader source code:
http://rgba.scenesp.org/iq/computer/articles/ssao/ssao.htm

A gamedev.net thread with lots of discussion about SSAO
http://www.gamedev.net/community/forums/topic.asp?topic_id=463075

A different approach to deferred lighting in which the lights are rendered before the actual geometry is rendered. Here’s the abstract from the paper describing this technique:

The best optimization when rendering is to not render anything unnecessary. And that is what culling is about, to find out what can be skipped when rendering because it cannot be visible anyway.  Below are the basic culling techniques which most renderers’ implements. The image is from a course slide.

Back Face Culling

Faces that faces away from the camera can not be visible on the screen so they don’t need to be drawn. This is so often used that it’s implemented by the hardware. It roughly cuts the amount of faces drawn in half. Just remember to turn it on!

View frustum Culling

The faces that is outside the view frustum can not be visible on the screen (we don’t bother about reflections now) so they can be culled. This check is done by checking if the geometries bounding volume is outside the view frustum volume or not. So the check will not be done on every face, as that would cost to much. Sometimes, the view frustum culling can cost more than what is gain ( for example when doing instancing). One way to speed up view frustum culling is to use a suitable spatial structure for the scene (octree, BSP or so).

All kind of bounding volume test that you can imagine can be found on this page:
http://www.realtimerendering.com/intersections.html

Info about frustum culling:
http://www.flipcode.com/archives/Frustum_Culling.shtml

Portal Culling

A technique that divides the scene into cells with portals between. When rendering, the camera will be in one of the rooms and that room will be rendered normally. But for each portal that is visible in the room a view frustum is set up for the size of the portal and then the room behind it is rendered. This will work recursively. The result will be that a lot of geometry can be culled by view frustum culling when rendering the other rooms. A very useful technique for indoor scenes.

Detail Culling

When a geometry is so far away that it’s not visible then there is no need to draw it at all so it can safely be culled. A more advanced scheme of detail culling that decreases the amount of details with the distance is LOD (level of detail).

Occlusion Culling

The hardest culling technique to implement. Geometry that is occluded by other geometry does not need to be rendered. One solution is to use the Z-buffer and sort the geometry in a front to back order. But this does not always work and all pixels needs to be checked against the Z-buffer so it will be costly for big scenes. Better occlusion culling techniques culls the geometry before it’s even sent to the GPU.

A good link to a couple of occlusion culling techniques
http://www.gamasutra.com/features/19991109/moller_haines_01.htm