Work in progress, diagrams and media coming soon.
This research originally started with the dream of having a fluid
simulation that was both large enough to cover an area of at least 1
cubic kilometer, while still being small enough to simulate cells down
to the scale of a few centimeters. With a fixed grid size, this would
take hundreds of trillions of cells, which is obviously not feasible.
The key observations that allow this research to function are extremely
simple: most of a simulations volume is locally homogenous, and most of
it is too far away to see high frequency details.
By dynamically adjusting the size of our cells we can take advantage of
these two facts to only simulate areas in high detail if doing so will
have a meaningful visual impact. In practice, this means that the simulation
becomes more accurate when: local variance of advected attributes is high,
and cells are close to the camera.
This is conceptually simple, but practically hard, since non-uniform cell
size makes every aspect of fluid simulation more difficult. This is only
exacerbated by designing the algorithm to run on compute shaders, which
lack abstractions that would simplify design and implementation.
The general design of the algorithm is this:
At every timestep we perform projection and advection as normal, just with
much more complicated logic to access and average data coming from different
cell sizes.
Then, we peform an initial subdivision phase, which finds cells which have high
local variance, and marks them. This process may require the marking of
neighboring cells to avoid sharp transitions in size, which would cause problems
for parallelization and storage.
Then, cells are subdivided, which requires allocating new cells from a fixed
length array, and copying parent data to these new cells. In practice this is
done using a stack of indices to avoid unnecessary copying.
Since the algorithm must run in parallel, we cannot edit data in neighboring cells
without potential write conflicts, so this subdivision process will cause links
between cells to be broken. To fix this, a second phase is run on each cell
which checks for these broken links and restores them.
A similar process is then performed for merging cells which have low variance.