tmpvar.com wrench logo

Blur Based 2D Realtime Radiosity (CPU)

This experiment is an attempt to find a simple & parallel algorithm for lighting a scene with low-frequency light (read: global illumination, soft shadows). This approach stems from radiosity, so instead of shooting rays from every visible surface to each light we instead fill a grid with energy from each light.

A video of this approach, everything is fully dynamic (lights & occluders)

There is a ton of prior art for this approach:

Data Structures

Scene Updates

The following steps happen on a per frame basis.

Lower the energy over the entire grid by a small amount

Instead of clearing the energy grid on every frame, we want to keep the energy from the previous frame to avoid some amount of flickering as lights move.

1const float delta = 0.125;
2for (auto &cell : energy) {
3 cell.color = max(energy_cell.color - vec3(delta), vec3(0.0));
4 cell.value = max(energy_cell.value - delta, 0.0);
5}

Inject energy into a grid

From each light, emit rays in equally around a circle.

16 rays using 2D DDA

16 rays using 2D DDA

We don't need full coverage, but there is a balance between performance and flicker as lights move. If you had a static scene you could probably use fewer rays. Rays are painted into the energy grid using Bresenham / DDA (branchless 3D DDA implementation ).

As the ray moves further away from the light we attenuate it. In this experiment, attenuation is derived from the diameter of the energy grid (currently 64).

1float diameter = 64.0;
2// the energy available to this ray at the moment it was emitted
3// this changes based on light intensity for primary rays or the
4// energy level of primary rays when emitting bounce rays.
5float initial_energy = 1.0;
6while (1) {
7 // inside the raymarcher, cell is a reference to the
8 // cell under the end of the ray
9 EnergyCell &cell = energy.get(ray.pos.x, ray.pos.y);
10
11 float dist = distance(cell, light);
12 float attenuation = 1.0 / (1.0 + diameter * 0.75 * (dist * dist));
13
14 if (attenuation < 0.01) {
15 break;
16 }
17
18 ray.energy = initial_energy * attentuation;
19
20 // Currently mixing colors by via component-wise max, which is not completely
21 // accurate, but works well in this low dynamic range environment.
22 cell.color = max(cell.color, ray.color * ray.energy);
23 cell.energy = (cell.energy + ray.energy) * 0.5;
24 ray.step();
25}

Occluders

Terminating rays when they hit something is accomplished by looking at the occluder grid at every ray step - if the cell is fully opaque then we exit the ray march.

Red `occluder` cells cause rays to terminate.

Red occluder cells cause rays to terminate.

If the occluder cell is not opaque then we re-color the ray, ensuring that only the color of the occluder cell is propagated.

ray.color = ray.color * occluder_cell.color * (1.0 - occluder_cell.opacity);
Propagating semi-transparent occluder color

Propagating semi-transparent occluder color

First bounce

Much like how we fill the energy grid with primary rays emitting from lights, we can similarly approach occlusion hits and emit new rays in a circle.

Emitting 8 new rays from the surface of an `occluder` cell.

Emitting 8 new rays from the surface of an `occluder` cell.

1vec2 hit_center = floor(vec2(primary_ray.gridPos)) + 0.5f;
2float TAU = 3.1459 * 2.0;
3// 8 bounce rays
4float bounce_angle = TAU / 8.0f;
5for (float i = 0.0; i < TAU; i += bounce_angle) {
6 vec2 bounce_dir(sin(i), cos(i));
7
8 // color bleed based on occluder color
9 vec3 bounce_color = (occluder_cell.color * primary_ray.color);
10
11 // emit a new ray of `bounce_color` in `bounce_dir`
12 // Note: ensure you propagate the energy/attenuation from primary ray or the
13 // bounce will be brighter than the light!
14 emit_radiosity_ray(
15 // this could be offset from the surface normal to avoid self occlusion
16 hit_center,
17 bounce_dir,
18 bounce_color,
19 primary_ray.energy
20 );
21}

Propagate energy with multiple blur passes

Blurring brings this whole technique together while acting as a low-pass filter. What we are trying to achieve is subtle lighting effects where light flows gently around corners leaving soft shadows and colors are blended together smoothly.

multiple steps of blurring after 16 initial rays. If you look closely you should see 'fingers' at the extents of the light where the blur couldn't successfully join the rays together.

multiple steps of blurring after 16 initial rays. If you look closely you should see "fingers" at the extents of the light where the blur couldn't successfully join the rays together.

multiple steps of blurring after 16 initial rays with a single bounce of 8 rays off of an occluder.

multiple steps of blurring after 16 initial rays with a single bounce of 8 rays off of an occluder.

To achieve this I'm currently using a naive, occluder aware, blur:

1void blur(i32 src_x, i32 src_y, i32 dst_x, i32 dst_y) {
2 auto prev = energy.get(src_x, src_y, 0);
3 auto cur = energy.get(dst_x, dst_y, 0);
4
5 f32 ratio = 0.5f;
6 auto occ = occluders.get(src_x, src_y, 0);
7 if (occ && occ->opacity > 0.0) {
8 // occluders are skipped, otherwise we'll see light bleed
9 // through the walls
10 return;
11 }
12
13 cur->add = (cur->add + prev->add) * ratio;
14 cur->color = (cur->color + prev->color) * ratio;
15}

and then we run the blur pass multiple times, making discrete passes from left to right, right to left, top to bottom, and bottom to top.

1for (u32 step = 0; step < 20; step++) {
2 for (i32 y = 0; y < energy.height; y++) {
3 // left to right
4 for (i32 x = 1; x < energy.height; x++) {
5 blur(x, y, x - 1, y);
6 }
7
8 // right to left
9 for (i32 x = energy.height - 2; x >= 0; x--) {
10 blur(x, y, x + 1, y);
11 }
12 }
13
14 for (i32 x = 0; x < energy.width; x++) {
15 // bottom to top
16 for (i32 y = 1; y < energy.height; y++) {
17 blur(x, y, x, y - 1);
18 }
19
20 // top to bottom
21 for (i32 y = energy.height - 2; y >= 0; y--) {
22 blur(x, y, x, y + 1);
23 }
24 }
25}

This is acceptable at low resolutions, I'm currently working at 64x64, but will be slower at higher resolutions.