Enhanced Face Cluster Global Illumination Introduction
This short, not mathematical, introduction written in 2005, explains why I worked on a Global Illumination System and what it is.
When I started to work on Global Illumination theories, I did not realize how many issues were related to it, although I was sure that the once called radiosity was going to be one of the most interesting research fields applicable on videogames.
It is hard to guess how many papers and thesis have been available on this argument since 1984, when at the Cornell University, the first radiosity application on computer was written by Goral et al.(1)
The original radiosity theory is not so difficult to understand, it is based on optic physic where words like Solid Angle, Radiance, Irradiance, Form Factor, Stoke Integral are used to explain how two bodies exchange energy.
However there are a lot of tedious problems to solve in order to create a good global illumination system and after twenty years, not all of them have been solved yet. All these issues are related to the following arguments:
These three main problems are the reason why, in these years, an incredible amount of different solutions have been written.
The first radiosity system was built upon the Finite Element Method theory. The GI on lambertian surfaces is "view independent", while the "Finite Elements" are the polygons of the scene. This approach seemed the best.
Finite Element Methods passed through several enhancements until when the Hierarchical Radiosity System theory was formulated (2).
The Hierarchical Radiosity was the first method to allow to render more sophisticate environments, thanks the fact that the solution is linear on the number of iterations, although it is still quadratic on the number of scene polygons or O(P^2 + NlogN) where P is the number of input polygons and N are the number hierarchical sub polygons generated in run-time.
It certainly was a good step forward, but the solution was not fast enough to manage environments containing thousands of polygons. This algorithm also introduces the concept of Oracle Refinement, where the oracle is the condition used to choose if to add new sub polygons in the scene based on error boundings (and there are several different oracle methods).
Successively, a new method was introduced in order to try to achieve a linear solution on the number of input polygons as well. This method was called Volume Clustering Method (3) and it consists on subdividing the space (with an octree data structure for example) and finding a method to model the exchanging energy first between volumes, next between volumes and surfaces and then between the surfaces. With this new way of thinking of a Global Illumination system, finally it was possible to achieve fast solutions on large environments, although new problems were introduced: first, 70%-80% of the time is consumed by the occlusion term evaluation (and again a lot of new algorithms born to accelerate this process), second it is quite hard to have satisfactory results.
At the same time, not finite element approaches started to gain ground, like The Photon Mapping Theory (son of Monte Carlo Radiosity systems) which could model BRDF and caustic as well (4). Surely Photon Mapping is a good technique (it is extensively used by the modern CG tools) and nowadays this approach could give better results than a classic FEM (but new FEM theories are still under development).
Personally my goal was to research on a solution that could have been applied in real-time environments and that is why I started to study the Face Clustering Radiosity Theory.
Face Clustering Radiosity
Luckily when I started, Andrew Willmott, in collaboration with Michael Garland, already completed his thesis on "Hierarchical Radiosity With MultiResolution Meshes" (5). The intuition that high defined models could have been substituted by the relative low-res models to get faster solution was previously already proposed (6), but Willmott was the first to use an automatic system based on Garland's Face Clustering theory to build an efficient LOD system. Face Clustering Radiosity is today the "state of the art" FEM GI system without using Photon Mapping and can be coupled with Volume Clustering Method as well. However pure Volume Clustering based methods are probably more suitable for real-time global illumination on dynamic scenes (with static lights)(26,27).
What Face Clustering is
Face clustering should be explained in a dedicated article. It is a very powerful tool, not only for Global Illumination, but also to solve a wide range of other CG problems. Garland is the father of the famous Quadratic Error Vertex LOD (7) and in his master thesis, he writes about how to cluster polygons that follow a specific topology. He called this method Face Clustering. Face Clustering is an hierarchical representation of a mesh built on clustered surfaces that best approximate a plane using a quadric error metric.
An example of face clustered model (built with my engine) is the following:
Illustration : the faces are clustered according their distance to the best fit plane
Face Clustering is a greedy algorithm with linear complexity; it works starting from a data structure called Dual Edge list. In a triangulated mesh the DE list is the list of edges of each triangle with the topology information of the triangles connected to them.
The DE must be manifold, so only two triangles are attached to every DE. The algorithm starts assigning an error value to each DE computed with the quadratic distance of every vertex from the orientated plane approximating the group of triangles. The best plane is computed either with a covariance matrix algorithm or with the Willmott's sum area weight normal theory.
Next the algorithm builds a Face Cluster Binary Tree , with a bottom-up approach, grouping the DE with least error and reevaluating the DE error for the new clusters. Once understood how the quadratic error metrics and a greedy algorithm work, the implementation is not so hard to develop.
My personal implementation, together with other improvements, uses Gottschalk (8) intuition to compute the covariance matrix. With this new approach, I could compute better face clusters and, on all my test scenes, the volume of the bounding boxes of the face clusters converged faster into a plane than the Willmott original algorithm.
Face Clustering applications
Face clustering is probably the best method to build up an Oriented Bounding Box Tree using at the best both Covariance Matrix and Rotating Callipers (9) methods. Moreover, since the algorithm clusters the mesh subdividing the surface and not the volume, the OBB tree converges faster into the surfaces than a classic OBB tree implementation.
Illustration : how face clustering can be used to make an optimal OBB tree
Face Clustering can be also used as a LOD system. Alan D. Kalvin (10) was the first to investigate on it with his SuperFaces theory (a theory very similar to face cluster).
FC LOD has some very useful features since the LOD meshes do not loose topological information and the vertices are always a subset of the original mesh vertices (so the same index buffer can be shared).
Illustration : how superfaces can be used to create LOD surfaces
For my implementation I thought about using a Douglas-Peucker(11) polygon algorithm, not only to simplify the boundary of the single face cluster, but also to create a dual clustering structure for the edges.
Illustration : how my face clustering system does LODs
Face clustering has been used also for (or is related to):
What Face Cluster Radiosity is
In Willmott's FC study, most of the latest hierarchical radiosity theories were inspected. The first Willmott's goal was to get a solution with sublinear complexity on input level polygons. He reached successfully this goal using Face Clustered meshes. The classic bounding error driven radiosity was enhanced by Willmott starting from Stamminger's Area Projected theory (16). With a L1 norm (17) (also called BFA oracle).
Willmott proposed a really good conservative bounding error procedure to compute the resulting error of the approximation of the face clusters into planar patches. Following this way the radiosity is almost never computed on the single input polygon (if it is quite refined), since most of the time, it is enough to calculate the radiosity on a clustered, plane approximated, group of polygons.
This means that a very complex scene could be computed in few minutes (or seconds!) with a lot of light bounces.
Another very important feature of Willmott's Global Illumination System is the use of the concept of Vector Irradiance (18). Since a group of polygons is approximated into a patch, it would not be accurate enough to use a constant irradiance rgb value over the entire cluster, because each polygon in the patch has its normal orientation.
Vector Irradiance (called also light vector) is the irradiance incident to the surface before being projected on the surface normal. Therefore it is a vector and it can be used to get an average vector light intensity arriving on the cluster summing up all the vectors irradiance generated by all lights in the scene.
Illustration : Adding face clusters to the hierarchy, notice how many input polygons are untouched by the iterations with face clusters (c)
Illustration : difference by using vector irradiance and not. On the right the polygons inside the patches gets the final irradiance rgb value by doing dot product between vector irradiance and the polygon normal.
Vector Irradiance is very powerful and widely used by today radiosity systems. Vector Irradiance can be precomputed as result of all the lights iterations in the scene and used to generate real time solutions.
In my implementation I planned to make the Volumes interact with Hierarchical Face Cluster interact with Hierarchical scene polygons, but eventually I had the time to implement only the hierarchical face cluster against hierarchical polygons interaction. Face Cluster Radiosity, by itself, is not enough to manage a general complex scene. It is useful for very refined, high-density meshes, but not for large input polygons (think of a wall) or large number of unconnected meshes. In order to solve these problems it is necessary to implement a hierarchical volume clustering system above the face clustering hierarchy and a hierarchical refinement on input polygons (so below the FCH). I implemented the input polygons refinement process both with a quadtree system and a dual polygon splitting system.
Illustration : Dual polygon refinement interaction between large input polygons and face clusters (94647 input polys, rendering in 0.95s with 4 bounces of light on a PIV 1.7 GHZ
I investigated on some bounding error procedure variations studying the original Stamminger theory and I have optimized the ray shooting for the form factor calculus (based on a simple monte carlo integration without pdf) using an adaptive function to compute the best number of rays to shoot. Moreover, to reduce the interaction between face clusters, I also implemented a b-link system (19).
Surely the biggest problem in a Global Illumination system is the occlusion checking, it takes most of the computation time and should be quite accurate to give a good final rendering. Visibility occlusion is a geometric process so it helps using a space partition system.
A very good optimization is given by the use of the Shaft Culling theory (20), it is a really interesting feature used in several other visibility evaluation/culling applications. Shaft Culling works very well and it is the only method to achieve conservative guaranteed full visibility and occlusion detection. Shaft culling has been also used to check guaranteed full occlusion (21) but I never implemented it.
Illustration : shadowing with shaft culling 1.47s with 3 bounces
Since the Global illumination is view-independent (because we are working on lambertian surfaces), after having pre-computed the solution, we can run the lit scene in real-time.
Illustration : How shaft culling approach works with a bad occluder
Unluckily my implementation had the big limitation to compute the Vector Irradiance as constant value over the entire surface of the incoming light hemisphere on the patch. This is a big approximation and Willmott (and I) cheated recalculating the constant vector irradiance on the corners of the patches interpolating it with a bilinear function. However it is just a cheat and it is not a good solution indeed leading toward blocky rendering. Willmott suggested to use a Final Gather approach (22), but it's really expensive and not so feasible in a real-time perspective.
Honestly my implementation could have still been improved in many ways. In order to complete the system and make it capable of managing all type of scenes, a volume clustering system should have been developed on top of the face clustering system.
Face clustering is definitely a good choice to make the complexity of the algorithm sub-linear on input polygons, but it remains quadratic on not merged face clusters and since the face clustering does not work on disconnected meshes, scenes with many objects suffer by this.
With a volume clustering interaction above the face clusters it could have been possible to achieve very fast rendering solution in every kind of environment with the quality of the vector irradiance approach.
About improving the quality of the rendering, I found several answers in the researches published by CRS4 (where I worked in a different period) Gobbetti’s team. Luckily, Enrico Gobbetti and his team (24), found a solution using high order basis functions to integrate the vector irradiance. High order basis interpolation gives a function in the domain of the entire hemisphere and not a constant vector, so it is possible to have a good solution without using Final Gathering approach. It is moreover possible (as Gobbetti's paper shows) manage BRDF in real time through the use of vertex and pixel shaders!
Illustration : The results of Gobbetti et al.. With a Face Cluster Radiosity system based on High Order Basis integration, it is possible to avoid the ugly constant vector irradiance interpolation and doing BRDF, in real time with the GI data solution using a simple vertex shader
Using precomputed vector irradiance and pixel shader it is possibile to render BRDF and normal mapping with the data gathered from Global Illumination and not from the lights of the scene.
These researches were made in 2005 and the implementation ran on a Pentium IV 1.7ghz. Nowadays GPU and multi-core processor could be powerful enough to implement a quite accurate real-time global illumination system, mostly if shadowing is not computed but simulated with ambient occlusion and local shadowing.
Face clustering could be used for several interesting application as explained. Vector Irradiance is a very important concept often ignored. Shaft Culling is a very good approach and should be taken in consideration.
 Goral, C.M., K.E. Torrance, D.P. Greenberg, and B. Battaile. 1984. Modelling the interaction of light between diffuse surfaces. Association for Computer Machinery Computer Graphics (3): 213–222.
 Hanrahan, P. M., Salzman, D.: A Rapid Hierarchical Radiosity Algorithm for Unoccluded Environments. Eurographics Workshop on Photosimulation, Realism and Physics in Computer Graphics, June 1990.
 F. Sillion. Clustering and volume scattering for hierarchical radiosity calculations. In Fifth Eurographics Workshop on Rendering, pages 105--117, June 1994.
 Henrik Wann Jensen. Global illumination using photon maps. In Rendering Techniques '96: 7th Eurographics Workshop on Rendering, pages 21-30, 1996.
 A. J. Willmott, Hierarchical Radiosity with Multiresolution Meshes. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, (Nov. 2000).
 Holly Rushmeier, Charles Patterson, and Aravindan Veerasamy. Geometric simplification for indirect illumination calculations. Graphics Interface ’93, pages 227–236, May 1993.
 M. Garland and P. S. Heckbert, “Surface simplification using quadric error metrics”, in SIGGRAPH 97 Conference Proceedings (T. Whitted, ed.), Annual Conference Series, pp. 209–216, ACM SIGGRAPH, (Aug. 1997).
 S. Gottschalk, M. Lin, and D. Manocha. OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM Siggraph’96, pages 171–180, 1996.
 Godfried T. Toussaint. "Solving Geometric Problems with the Rotating Calipers." In Proceedings of IEEE MELECON '83, pp. A10.02/1-4. Los Alamitos, CA: IEEE Press, 1983.
 Kalvin, A. D. and Taylor, R. H. (1996). Superfaces: Polygonal Mesh Simplification with bounded error. In IEEE Computer Graphics and Applications, volume 15, number 3, May 1996.
 D.H. Douglas and T.K. Peucker. Algorithms for the reduction of the number of points required to represent a line or its caricature. The Canadian Cartographer, 10(2):112-122, 1973,
 Decoret, Xavie et al. 2003. Billboard Clouds for Extreme Model Simplification, Proceedings of SIGGRAPH 2003.
 Budirijanto Purnomo, Jonathan D. Cohen and Subodh Kumar. Seamless Texture Atlases, Eurographics/ACM SIGGRAPH Symposium on Geometry Processing 2004
 C. Soler, M.-P. Cani, and A. Angelidis. Hierarchical pattern mapping. In SIGGRAPH 2002 Conference Proceedings, July 2002.
 Inoue, Keisuke, Takayuki Itoh, Atsushi Yamada, Tomotake Furuhata, Kenji Shimada. Face clustering of a large-scale CAD model for surface mesh generation. Computer Aided Design, Elsevier, Vol 33, Num 3, pp.251-261, March 2001
 M. Stamminger et al. Bounded clustering - finding good bounds on clustered light transport. In Proc. Pacific Graphics '98. IEEE Computer Society Press, 1998
 Dani Lischinski, Brian Smits, and Donald P. Greenberg. Bounds and error estimates for radiosity. Proceedings of SIGGRAPH 94, pages 67–74, July 1994.
 James Arvo and Andrew Glassner. The irradiance jacobian for partially occluded polyhedral sources. Proceedings of SIGGRAPH 94, pages 343–350, July 1994.
 François X. Sillion, G. Drettakis, and Cyril Soler. A clustering algorithm for radiance calculation in general environments. Eurographics Rendering Workshop 1995, pages 196–205, June 1995.
 E. Haines and J. Wallace. Shaft Culling for Efficient Ray-traced Radiosity. 2nd Eurographics Workshop on Rendering Proceedings, pages 122-138, 1991.
 Luc Leblanc, Pierre Poulin: Guaranteed Occlusion and Visibility in Cluster Hierarchical Radiosity. Rendering Techniques 2000, 89-100
 Simon Gibson. Efficient Radiosity for Complex Environments. M.Sc. thesis, Manchester, UK, 1995.
 François X. Sillion, A Unified Hierarchical Algorithm for Global Illumination with Scattering Volumes and Object Clusters, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.240-254, September 1995
 Enrico Gobbetti, Leonardo Spanò, and Marco Agus. Hierarchical Higher Order Face Cluster Radiosity for Global Illumination Walkthroughs of Complex Non-Diffuse Environments. Computer Graphics Forum, 22(3): 563-572, September 2003.
 Gene Greger, Peter Shirley, Philip M. Hubbard, and Donald P. Greenberg. The irradiance volume. IEEE Computer Graphics & Applications, 18(2):32–43, March-April 1998.
 Cyril Crassin, Fabrice Neyret, Miguel Sainz, Simon Green, Elmar Eisemann.. Interactive Indirect Illumination Using Voxel-Based Cone Tracing : An Insight, Siggraph 2011.
 Sinje Thiedemann, Niklas Henrich, Thorsten Groschy, Stefan Müller. Voxel-based Global Illumination. 3D 2011.
Some results achieved with my Global Illumination Engine: