Over the holidays, I took a little break from my larger coding projects to have some fun with Fourier transforms.  Originally devised by Jean-Baptiste Joseph Fourier in 1822 to model heat dispersion, Fourier transforms turned out to be useful for a wide range of purposes. Today this math underpins digital radio communication, audio recording, image compression, and mass spectrometry to name just a few.

I became curious about Fourier transforms while tinkering with Unity’s Light Probe system. Light probe networks use a specialized Fourier transform called a spherical harmonic to efficiently compress lighting information at each probe. I did this project to see if there were other game programming applications for Fourier transforms.

How Do Fourier Transforms Work?

The youtube channel 3Blue1Brown has an excellent video explaining fourier series and transforms here. For the sake of brevity I’m only going to give the simplified explanation necessary to understand my experiment. 

A Fourier series is a way of storing a sequence of values as a function. Specifically, it takes an array of floating-point numbers, and describes it as a sum of multiple frequency functions. The end result is another array of floating point values, representing the amplitude of each frequency. Once you have this array of amplitudes, you can evaluate the function f(t) for any index in the original array or an arbitrary floating point number in between indices, and get a result that is very close to the original value.

The number of frequencies is arbitrary, with additional frequencies increasing the fidelity of the evaluation function. To compress the data, we simply discard most of the higher frequency coefficients. This reduces the fine details of the evaluation function, but the accuracy of the function actually remains quite good with only a small fraction of the original coefficients remaining. For example, Unity’s light-probes use just nine floats per color channel to store a lighting sample.

My Project: Visibility Probes

To get some hands on practice, I decided to make a system for precomputing point-to-point visibility data. This is similar to unity’s light-probe system, but instead of storing a spherical light map, each probe would store a 2D map of an area around the probe, recording which positions are visible from the probe’s position.

Normally you would check point-to-point visibility by casting a ray and checking for intervening collisions. Casting a single ray is not costly, and you can usually stagger a large number of raycasts over several frames to protect performance. For the sake of this project, let’s say that I can’t avoid the need to perform many point-to-point checks in a single frame, and the checks are for long distances across complex level geometry, conditions that make each raycast more expensive.

The structure of my system is essentially the same as a light-probe system, first I need to precompute my point-to-point data:

1. Create a mesh of probe positions. I just generate a grid automatically (represented in the images by the small blue spheres). Like light probes, hand positioned distributions and more sophisticated automated distributions will yield better results.
2. Sample the visibility of each probe. I do this by performing raycasts from the probe to a grid of sample points centered on the probe. Visible points are recorded as 1, while obstructed points are recorded as -1. The sample is a 2D grid, which is flattened into a 1D array. I experimented with both cardinal and radial sample distributions.
3. Perform the forward FFT operation on the sample array, then compress the data by discarding the higher frequency elements.

The end result is a collection of probes that store pre-computed visibility data as Fourier series. Once we have this data, we can make use of it at runtime.

1. Step One: Probe Interpolation
   1. During runtime, we want to check visibility from an arbitrary observer position. Request an interpolated probe for the observer position. This interpolated probe is just a weighted average of the array values of the surrounding probes based on their proximity to the observer.
   2. The result is an interpolated probe that approximated the visibility at its position. A stationary observer only needs to request an interpolated probe once, while a moving observer will want to request a probe periodically as their position changes.
2. Step Two: Query Point Visibility
1. The observer can use the interpolated probe to get the predicted visibility of a position within the probe’s sample area. Because our data is a 2D grid of samples, the target position will be somewhere between two rows of samples. For each adjacent row, we calculate the closest time (t) along that row, then plug that into our f(t) representing the sum of frequency waves:
2. The weighted average of the two outputs gives us a value between -1 (not visible) and 1 (visible). We can use a hard cutoff at 0 or a threshold of our choice to convert this to a binary visible/occluded result. 

Qualified Success

At this point I have a system that is capable of producing a visibility predictions with reasonable fidelity, but there are some outstanding issues. I have not yet done performance comparisons to conventional raytracing, but I’m  reasonably confident that under in a high volume, long distance, many colliders situation that I outlined above, this method would outperform a brute-force ray casting approach.

The problem lies with memory cost to fidelity trade off. Fourier transforms do well at preserving gradients and large shapes, making them ideal for something like lighting. My sampling process is likely to miss fine details like individual trees and windows, and even if it did catch them, they would likely be lost to compression smoothing. The probe grid itself needs to be quite dense to capture the occlusion of nearby objects accurately.

These issues can definitely be overcome or at least greatly mitigated. There are a lot of little upgrades that can be made to each step in the process. I see this approach working well in a hybrid solution with conventional ray casts. Ray casts would be used by default for all visibility checks under a minimum range. For more distant groups of queries, the visibility probe system could be used to filter out all the targets that are definitely occluded, then the rest could be tested with rays. The remainder could even be prioritized for ray casts based on how visible the probe system estimates them to be.

Other Applications

The smoothing caused by compression means that Fourier transforms might not be ideal for point-to-point visibility checks with a high accuracy requirement, but it can actually be a useful feature for other applications. For example, Let’s say that I want to gauge a position’s exposure from a general direction, i.e. how close does an observer in a given direction need to be to see me? This would be a much simpler 1-dimension Fourier transform, just a 360 degree ring of values that estimate the maximum distance at which the probe is visible from that direction.

Trying to reason about something like general visibility in a direction or arc is quite expensive via conventional means like ray tracing. This is where the compression smoothing  of Fourier transforms is actually beneficial. In fact, the broader the arc you want to evaluate, the faster the evaluation is (because you are skipping the evaluation of the higher frequencies). This approach could allow an AI entity to efficiently search for a good overwatch position, or plot a path that prefers cover against a general direction.

There are many applications and optimizations I would like to explore, so stay tuned for more experiments.