From BlenderWiki

Adaptive Caching for Paged Particles

Overview

Janne Karhu has been working on a major point cache improvement, termed Adaptive Caching. Information about the basic idea can be found here.

This page describes the combination of adaptive caching with the new paged particle system. The difference between the previous particle implementation and the new buffer system are quite fundamental, so the current point cache system needs an upgrade too. Paged buffers allow a much more dynamic behavior of active particle count, total emission count and birth/death rates.

The current point cache basically iterates over all point indices and searches for valid cache frames in the possible range. This is feasible when the number of point indices is constant and limited, but it will fail for highly dynamic simulations. After some simulation time with high birth/death rates the number of dead particles can be several times larger than the number of active particles (only active particles are kept in memory). This means that the current cache reading procedure will gradually perform worse over time.

Example

Here is a random cache reading situation:

Cache loading example

Each column represents a frame, with the current frame (cfra) in the middle. We only need to look at a frame interval of (cfra-steps, cfra+steps), where steps is the maximum cache frame distance set by the user. For each particle that is alive, at least one valid cache frame will exist in both past and future frames.

Each dot in on the grid represents cached particle data in that frame column. The particle IDs are denoted on the vertical axis. A cache frame only stores as much data as needed, i.e. no dead particles are cached, except for the exact frame in which a particle dies. In the example, particle 4 does not have any data in the frame range, so it is either dead or unborn.

There are a number of possible cases depending on what valid cache frames can be found for a point:

• no valid frames: particle does not exist
• cfra is has data: exact match
• data in both at least one past and future frame: result is interpolated
• only past frame has data: particle is dead (skip)
• only future frame has data: particle is unborn (skip)

If more than one past/future frame exists, only the frame closest to cfra is used.

Note that unlike the current caching implementation, the amount of data to check for a particular frame does not depend on the total index/id range. Only the particles that are actually alive need to be written and read to/from the cache. This avoids the performance problems of the current implementation outlined above.

These are the steps to carry out in order to reconstruct particle data from the cache:

1. Clear particle buffer. Memory could stay allocated until final particle count is known. Algorithms are chosen for in-place behavior, so only a fixed amount of additional memory is needed.
2. 

   

   Add points from cfra
   Load the cfra cache frame into particle buffer. Particle dying on that frame are skipped.
   
3. 

   

   Add points from cfra-1
   

   

   Add points from cfra-2
   

   

   Add points from cfra-3
   For each past frame in range, starting backward from cfra:
   1. Append all new particles to the buffer. Particles already in the buffer are skipped. Finding existing particles in the buffer will require a search by particle id. This in turn requires sorted particles in the buffer (excluding new particles from the loading frame).
      => Each particle is stored at most once in the buffer at any time.
   2. After the previous step, the buffer is only partially sorted: both the old particles as well as the new particles from this frame are sorted locally, but need to be merged into one list in order to prepare for the next cache frame read. In-place merging is required here, multiplying the amount of particle data would seriously cripple scalability.
      
4. 

   

   Add points from cfra+1
   

   

   Add points from cfra+2
   

   

   Add points from cfra+3
   For each future frame in range, starting forward from cfra:
   1. For each point in the frame:
      • If point does not yet exist in the buffer: skip (unborn particle)
      • If existing point is exact (from cfra): skip
      • Otherwise: interpolate between existing point and frame data.