Accelerated Ambient Occlusion Using Spatial Subdivision StructuresChris WasseniusAbstractAmbient Occlusion is a relatively new method that gives global illumination like results. This paper presents a method to accelerate ambient occlusion using the form factor method in Bunnel [2005] as well as utilizing the fact that ambient occlusion is a function of nearby geometry only. The proposed method combines existing ideas in order to accelerate ambient occlusion calculations by using a spatial subdivision structure (an octree) and selective sampling. Keywords: ambient occlusion, ambient obscurance, global illumination, shadowing techniques, spatial data structures1 IntroductionGlobal illumination in computer graphics is a key factor in producing realistic scenes. However, the complexity of a true radiosity approach is still too time consuming for modern technology. Ambient Occlusion is a technique that generates global illumination effects (soft shadowing, color bleeding) without taking into account an actual light source. Instead, the ambient term of the standard lighting equation is modified as a function of the local geometry of a scene. That is, the ambient term for a point on a surface is determined by how occluded that point is from other local surfaces in the scene [Iones et al. 2003]. Ambient Occlusion simulates global illumination fairly well considering its relative simplicity. Ambient Occlusion calculations for the most part have remained a non-real time process however. The technique presented accelerates the occlusion calculations by using a hierarchical spatial subdivision system. Hierarchical spatial subdivision systems have been used to speedup radiosity, ray tracing, occlusion culling, and many other graphics-based problems.2 Related WorkGoral et al. [1985] first introduced the concept of radiosity, and brought global illumination effects to computer graphics. Due to radiosity's complexity various acceleration methods were later introduced. One such method is to store patches in Figure One: Ambient occlusion and diffuse lighting.a hierarchy [Hanrahan et al. 1991]. The idea, for example, is that instead of calculating the amount of light coming from a distant wall in a room by finding the form factor for each patch that is far way, it is possible and nearly equivalent to group those distant patches together (average their radiosities) and compute the form factor between a large patch (the entire far wall) and the receiving patch in question. This significantly reduces the amount of form factor calculations between patches, yielding a linear solution, rather than a quadratic solution, to the problem. However, the radiosity method is still exceptionally time consuming, and thus other methods that attempt to mimic global illumination have been introduced.The idea of ambient occlusion was introduced by Zhukov et al. [1998] and as mentioned earlier gives global illumination-like effects at a much lesser computational cost. A patch's ambient term is modified based on how open that patch is with respect to other nearby patches. If a patch is fully open its ambient term is multiplied by 1, otherwise its ambient term is multiplied by a value between 0 and 1. Later, Iones et al. [2003] proposed storing the resulting ambient term computations in light maps rather than patch vertex attributes. This allows a scene to be rendered with only the original polygons, independent of the patches that were used in the occlusion calculation. Also,Méndez et al. [2003] added color bleeding support to ambient occlusion with no extra computational cost.In most production renderers, such as Renderman, ambient occlusion is now supported, and implemented by ray tracing [Christensen 2002]. As an extension the normal of a patch is bent based on the average direction that a patch is open or not occluded. This bent-normal is then used when looking up data from an environment map. This typically gives more interesting and realistic results.Recently, real-time, or close to real-time, ambient occlusion results have been achieved with the help of the latest graphics hardware [Bunnel 2005]. The idea is to create surface elements out of a scene 's polygonal data, and to compute the shadowing of these surface elements onto each other using a typical form factor-like equation. A Surface element is defined as an oriented disk, with a surface position, normal, and area. Every vertex in the polygonal scene, has a corresponding surface element. Similar to radiosity's hierarchical clustering technique [Hanrahan 1991], surface elements are stored in a hierarchy such that when computing the shadowing from far away elements, one large surface element may be used rather than computing the shadowing from every far away surface elements. Fragment shaders are used by the GPU with this method.The benefit of using the form factor approach, rather than ray tracing to determine the visibility of an element is that ray tracing requires many samples to sufficiently represent the total occlusion value. The form factor approach on the other hand mimics computing the visibility of an element by using the areas of the occluders. So while ray tracing could utilize a spatial structure for determining local visibility, the method suffers from the fact that many rays are required. 3 MethodThe proposed method is to accelerate the ambient occlusion calculation for a scene, by utilizing the fact that the ambient occlusion for an element is only a function of the nearby geometry in the scene with respect to that element. The method introduced uses Bunnel's [2005] idea of surface element discs and form factor-like shadowing ideology as well as Iones et al. 's [2003] idea of neighboring geometry. Ambient occlusion as first introduced by Zhukov [1998] was a function of just that, nearby geometry, however many ambient occlusion techniques, such as the real-time method introduced by Bunnel [2005], seem to neglect this fact to an extent. Shadows cast from distant elements on a receiving element are lessened considerably by how far the occlusion elements are from the receiving element in question. This is represented in the form-factor equation. Where the form-factor between one element and another is:A cos ӨE cos ӨR ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ (1) π r2 + AWhere A is the area of the occluder, £E is the angle between the occluder's normal and the