Tuesday, 25 April 2017

Real Time Global Illumination

In keeping with a lot of the older posts on this blog I thought I'd write about the realtime GI system I'm using in a project I'm working on. It's a complete fresh start from the GI stuff I've written about previously. Previous efforts were based on volume textures but dealing with the sampling issues is a pain in the ass so I've switched to good old fashioned lightmaps. This is all a lot of effort to go to so why bother? The short answer is I love the way it looks. As a bonus it simplifies the lighting process and there's a subtlety to the end results that is very hard to achieve without some sort of physically based light transport. A single light can illuminate an entire scene and the bounce light helps ground and bind all the elements together.
The process can be divided into five stages, lightmap UVs, surfel creation, surfel clustering, visibility sampling and realtime update.The clustering method was inspired by this JCGT article however I'm not using spherical harmonics and I generate surfels and form factor weights differently. The JCGT article is fantastic and well worth a read.

Before you run off, here it is in action.

 Lightmap UVs

The lighting result is stored in a lightmap so the first step is a good set of UVs. These lightmaps are small and every pixel counts so you have to be pretty fussy about how the UVs are laid out. UV verts are snapped to pixel centers and there needs to be at least one pixel between all charts in order to prevent bilinear sampling from sampling incorrect charts. The meshes are unwrapped in Blender then packed via a custom command line tool. This uses a brute force method that simply tests each potential chart position in turn, for simple scenes and pack regions up to 256x256 the performance is acceptable.


Surfels and Clustering

Next up we have to divide the scene into surfels (surface elements) and then cluster those surfels into a hierarchy. At runtime these surfels are lit and the lighting results are propagated up the hierarchy. This lighting information is then used to update the lightmap.

Surfel placement plays a big part in the quality of the illumination and I've been through a few iterations. Initially I tried random placement with rejection if a surfel was too close to it's neighbours but this was hellishly slow. I also tried a 3D version of this which was much faster but looking at the results I felt the coverage could be better. Particularly around edges and on thin objects, the neighbour rejection techniques would often leave gaps that I felt could be filled. This seemed like it could be addressed by relaxing the points but I wanted to try something else.

I decided to try working in 2D using the UV's which in this case are stretch free, uniformly scaled and much easier to work with. The technique I settled on first generates a high density, evenly distributed set of points on each UV chart. N points are selected from this set and used as initial surfel locations and these locations are then refined via k-means clustering.

This results in a set of well spaced surfels that accurately approximate the scene geometry and makes it easy to specify the desired number of surfels. For each chart N is simply 

(chart_area / total_area) * total_surfel_count

The initial high density point distribution.
Surfel creation via k-means clustering of the high density point distribution.

These surfels are then clustered via hierarchical agglomerative clustering which repeatedly pairs nearby surfels until the entire surfel set is contained in a binary tree. Distance, normal, UV chart and tree balancing metrics help tune how the hierarchy is constructed. I'm still experimenting with these factors.

Hierarchical agglomerative clustering in action.

Lightmap visibility sampling

Influencing clusters for the highlighted lightmap texel.
Once the surfel hierarchy has been constructed each lightmap texel needs to locate the surfels that most contribute to it's illumination. Initially I used an analytic form factor but this would sometimes cause lighting flareouts if a texel and surfel were too close. Clamping the distance worked but felt like a bit of a hack so I switched to simply casting a bunch of cosine weighted rays about the hemisphere. Each ray hit locates the nearest surfel and the final form factor weight for each surfel is simply

 num_hits / total_rays

Once all rays have been cast the form factor weights are propagated up the hierarchy. The hierarchy is then refined by successively selecting the children of the highest weighted cluster. At each iteration the highest weighted cluster is removed and it's two children are selected in it's place. This process repeats until a maximum number of clusters is selected or no further subdivision can take place. The texel then has a set of clusters and weights that best approximate it's lighting environment.

Lighting update

The realtime lighting phase consists of several stages. First the surfels direct lighting is evaluated for each direct light source, visibility is accounted for by tracing a single ray from the surfels position to the light source. The lighting result from the previous frame is also added to the current frames direct lighting to simulate multiple bounces. There's a bit of a lag here but it's barely noticeable. Lighting values for each cluster are then updated by summing the lighting of it's two children.

Each active texel in the lightmap is then updated by accumulating the lighting from it's set of influencing clusters. The lightmap is then ready to be used.

Direct light only.
Direct light with one light bounce.

Direct light with multiple light bounces.
Timings for each stage (i7-6700k @ 4.0ghz)

  Surfel illumination (1008 surfels):               0.36ms
  Sum Clusters (2015 clusters):                     0.08ms
  Sum Lightmap texels (6453 texels * 90 clusters):  0.64ms

Environmental Lighting

Environment lighting is provided by surfels positioned in a sphere around the scene. These are treated identically to geometry surfels except for the lighting update where a separate illumination function is used. Currently it's a simple two colour blend but could just as easily be a fancy sky illumination technique or an environment map.

To finish up here are some more examples without any debug overlay. These were taken with an accumulation technique that allows for soft shadows and nice anti-aliasing.


Patapom said...


huwb said...

Really nice results! I've played around a bit in the past with lightmap-space GI in a shadertoy (, but this takes it to a new level!

how do you store the set of influencing clusters? is there a global array of clusters for all LODs, and the set is indices into that array. are these in textures with all runtime computation on the GPU? finally, do you have rough numbers for performance and what your gpu is? sorry for all the questions! really curious to learn more :).

Unknown said...

What's the large scale performance like though? Most GI stuff with precalculated lightmap influence simply don't scale to large areas, so far as I've seen. Or is the project all small and enclosed spaces anyway?

Unknown said...

Hi Stefan, this looks really nice. thanks for sharing.
I think I understand what you are doing.
However, I would think that your lighting resolution would be limited by the density of the surfels, but we can see that you have fairly crisp shadows. In that last comment, are you refering to using a more conventional solution (shadow maps) for your first bounce, and then your technique for subsequent bounces?


Alex said...

Hi Stefan, thank you for a great post!
How do you determine and albedo of a surfel? Is it filtered based on the size of a surfel? Do normal maps influence a direction of a surfel?

skg said...


Unknown said...

Amazing, any plans on further developing it, or maybe comercializing it in the future?

efi said...

Beautiful and believable images - nice work!

Stefan said...

Thanks Adriano, I'm using this in a game I'm working on but don't have immediate plans to commercialize it at the moment.

Stefan said...

Hi Alex, surfels have a UV based on the source geometry. They could sample a texture map at the UV location but all my textures are basically monochrome so I just use an average colour per surface. The UV is also used to read the previous GI result to create a multi bounce effect. In terms of normals the original geometry normal averaged over the area of the surfel is used, I'm not really using normal maps to any great degree.

Stefan said...

Hi Phil,

Lighting resolution is mostly governed by light map resolution but the number of surfels does play a part. That said you can get away with surprisingly few surfels and things still look pretty good.

That last comment is a bit confusing after all the talk about GI. It's referring to traditional shadow map rendering, completely separate to the GI system. Those screenshots are the result of combining lots of slightly different images, each one with a tiny positional adjustment to the camera and light sources. This creates the nice hard to soft shadow you see on the white wall in the second to last image. It also creates a depth of field effect on the preceding images showing the sky surfels.

Stefan said...

Hi Sora,

The project this is for uses fairly small, self contained areas so I haven't tested it at larger scales yet. It seems to hold up quite nicely as texels get bigger and surfels increase in size though. Detail is lost but you still get a nice wash of colour through the scene.

Stefan said...

Hi Huw,

That shadertoy is ace!

In terms of clusters there's a single hierarchy for the entire scene and each texel has a list of indices and weights into this hierarchy. The runtime update is all done on the CPU at the moment, I haven't tried GPU yet but I imagine it will be faster. There are some CPU timings in the post, just before the section on environment lights. To flesh those out a bit more...

The illumination stage is un-optimized and involves tracing a ray per surfel to each light it recieves any illumination from.

Once the surfels are lit the results are propogated up the hierarchy which is simply cluster.flux = cluster.child_a.flux + cluster.child_b.flux. This step uses SSE.

Each lightmap texel then sums the radiosity of each cluster it has a weight for, this step also uses SSE but memory access is all over the place :(

Post a Comment