Alembic procedural: deduplicate cached data accross frames

Currently the procedural will add an entry to the cache for every frame
even if the data only changes seldomly. This means that in some cases we
will have duplicate data accross frames.

The cached data is now stored separately from the time information, and
an index is used to retrieve it based on time. This decoupling allows
for multiple frames to point to the same data.

To check if two arrays are the same, we compute their keys using the
Alembic library's routines (which is based on murmur3), and tell the
cache to reuse the last data if the keys match.

This can drastically reduce memory usage at the cost of more processing
time, although processing time is only increased if the topology may
change.

2 files changed, 104 insertions, 42 deletions

diff --git a/intern/cycles/render/alembic.cpp b/intern/cycles/render/alembic.cpp
index e4f0690c401..1336f81896a 100644
--- a/intern/cycles/render/alembic.cpp
+++ b/intern/cycles/render/alembic.cpp
@@ -396,6 +396,10 @@ static void add_uvs(AlembicProcedural *proc,
 
   ccl::set<chrono_t> times = get_relevant_sample_times(proc, time_sampling, uvs.getNumSamples());
 
+  /* Keys used to determine if the UVs do actually change over time. */
+  ArraySample::Key previous_indices_key;
+  ArraySample::Key previous_values_key;
+
   foreach (chrono_t time, times) {
     if (progress.get_cancel()) {
       return;
@@ -422,21 +426,32 @@ static void add_uvs(AlembicProcedural *proc,
 
     float2 *data_float2 = reinterpret_cast<float2 *>(data.data());
 
-    const unsigned int *indices = uvsample.getIndices()->get();
-    const V2f *values = uvsample.getVals()->get();
+    const ArraySample::Key indices_key = uvsample.getIndices()->getKey();
+    const ArraySample::Key values_key = uvsample.getVals()->getKey();
 
-    for (const int3 &loop : *triangles_loops) {
-      unsigned int v0 = indices[loop.x];
-      unsigned int v1 = indices[loop.y];
-      unsigned int v2 = indices[loop.z];
+    if (indices_key == previous_indices_key && values_key == previous_values_key) {
+      attr.data.reuse_data_for_last_time(time);
+    }
+    else {
+      const unsigned int *indices = uvsample.getIndices()->get();
+      const V2f *values = uvsample.getVals()->get();
+
+      for (const int3 &loop : *triangles_loops) {
+        unsigned int v0 = indices[loop.x];
+        unsigned int v1 = indices[loop.y];
+        unsigned int v2 = indices[loop.z];
+
+        data_float2[0] = make_float2(values[v0][0], values[v0][1]);
+        data_float2[1] = make_float2(values[v1][0], values[v1][1]);
+        data_float2[2] = make_float2(values[v2][0], values[v2][1]);
+        data_float2 += 3;
+      }
 
-      data_float2[0] = make_float2(values[v0][0], values[v0][1]);
-      data_float2[1] = make_float2(values[v1][0], values[v1][1]);
-      data_float2[2] = make_float2(values[v2][0], values[v2][1]);
-      data_float2 += 3;
+      attr.data.add_data(data, time);
     }
 
-    attr.data.add_data(data, time);
+    previous_indices_key = indices_key;
+    previous_values_key = values_key;
   }
 }
 
@@ -736,6 +751,11 @@ void AlembicObject::load_all_data(AlembicProcedural *proc,
   ccl::set<chrono_t> times = get_relevant_sample_times(
       proc, *time_sampling, schema.getNumSamples());
 
+  /* Key used to determine if the triangles change over time, if the key is the same as the
+   * last one, we can avoid creating a new entry in the cache and simply point to the last
+   * frame. */
+  ArraySample::Key previous_key;
+
   /* read topology */
   foreach (chrono_t time, times) {
     if (progress.get_cancel()) {
@@ -747,22 +767,27 @@ void AlembicObject::load_all_data(AlembicProcedural *proc,
 
     add_positions(sample.getPositions(), time, cached_data);
 
-    /* Only copy triangles for other frames if the topology is changing over time as well.
-     *
-     * TODO(@kevindietrich): even for dynamic simulations, this is a waste of memory and
-     * processing time if only the positions are changing in a subsequence of frames but we
-     * cannot optimize in this current system if the attributes are changing over time as well,
-     * as we need valid data for each time point. This can be solved by using reference counting
-     * on the ccl::array and simply share the array across frames. */
+    /* Only copy triangles for other frames if the topology is changing over time as well. */
     if (schema.getTopologyVariance() != kHomogenousTopology || cached_data.triangles.size() == 0) {
-      /* start by reading the face sets (per face shader), as we directly split polygons to
-       * triangles
-       */
-      array<int> polygon_to_shader;
-      read_face_sets(schema, polygon_to_shader, iss);
-
-      add_triangles(
-          sample.getFaceCounts(), sample.getFaceIndices(), time, cached_data, polygon_to_shader);
+      const ArraySample::Key key = sample.getFaceIndices()->getKey();
+
+      if (key == previous_key) {
+        cached_data.triangles.reuse_data_for_last_time(time);
+        cached_data.triangles_loops.reuse_data_for_last_time(time);
+        cached_data.shader.reuse_data_for_last_time(time);
+      }
+      else {
+        /* start by reading the face sets (per face shader), as we directly split polygons to
+         * triangles
+         */
+        array<int> polygon_to_shader;
+        read_face_sets(schema, polygon_to_shader, iss);
+
+        add_triangles(
+            sample.getFaceCounts(), sample.getFaceIndices(), time, cached_data, polygon_to_shader);
+      }
+
+      previous_key = key;
     }
 
     if (normals.valid()) {
diff --git a/intern/cycles/render/alembic.h b/intern/cycles/render/alembic.h
index 0203475571e..d0c5856a353 100644
--- a/intern/cycles/render/alembic.h
+++ b/intern/cycles/render/alembic.h
@@ -128,12 +128,25 @@ template<typename T> class CacheLookupResult {
  * The data is supposed to be stored in chronological order, and is looked up using the current
  * animation time in seconds using the TimeSampling from the Alembic property. */
 template<typename T> class DataStore {
-  struct DataTimePair {
+  /* Holds information to map a cache entry for a given time to an index into the data array. */
+  struct TimeIndexPair {
+    /* Frame time for this entry. */
     double time = 0;
-    T data{};
+    /* Frame time for the data pointed to by `index`. */
+    double source_time = 0;
+    /* Index into the data array. */
+    size_t index = 0;
   };
 
-  vector<DataTimePair> data{};
+  /* This is the actual data that is stored. We deduplicate data across frames to avoid storing
+   * values if they have not changed yet (e.g. the triangles for a building before fracturing, or a
+   * fluid simulation before a break or splash) */
+  vector<T> data{};
+
+  /* This is used to map they entry for a given time to an index into the data array, multiple
+   * frames can point to the same index. */
+  vector<TimeIndexPair> index_data_map{};
+
   Alembic::AbcCoreAbstract::TimeSampling time_sampling{};
 
   double last_loaded_time = std::numeric_limits<double>::max();
@@ -157,17 +170,21 @@ template<typename T> class DataStore {
       return CacheLookupResult<T>::no_data_found_for_time();
     }
 
-    std::pair<size_t, Alembic::Abc::chrono_t> index_pair;
-    index_pair = time_sampling.getNearIndex(time, data.size());
-    DataTimePair &data_pair = data[index_pair.first];
+    const TimeIndexPair &index = get_index_for_time(time);
+
+    if (index.index == -1ul) {
+      return CacheLookupResult<T>::no_data_found_for_time();
+    }
 
-    if (last_loaded_time == data_pair.time) {
+    if (last_loaded_time == index.time || last_loaded_time == index.source_time) {
       return CacheLookupResult<T>::already_loaded();
     }
 
-    last_loaded_time = data_pair.time;
+    last_loaded_time = index.source_time;
 
-    return CacheLookupResult<T>::new_data(&data_pair.data);
+    assert(index.index < data.size());
+
+    return CacheLookupResult<T>::new_data(&data[index.index]);
   }
 
   /* get the data for the specified time, but do not check if the data was already loaded for this
@@ -178,22 +195,34 @@ template<typename T> class DataStore {
       return CacheLookupResult<T>::no_data_found_for_time();
     }
 
-    std::pair<size_t, Alembic::Abc::chrono_t> index_pair;
-    index_pair = time_sampling.getNearIndex(time, data.size());
-    DataTimePair &data_pair = data[index_pair.first];
-    return CacheLookupResult<T>::new_data(&data_pair.data);
+    const TimeIndexPair &index = get_index_for_time(time);
+
+    if (index.index == -1ul) {
+      return CacheLookupResult<T>::no_data_found_for_time();
+    }
+
+    assert(index.index < data.size());
+
+    return CacheLookupResult<T>::new_data(&data[index.index]);
   }
 
   void add_data(T &data_, double time)
   {
+    index_data_map.push_back({time, time, data.size()});
+
     if constexpr (is_array<T>::value) {
       data.emplace_back();
-      data.back().data.steal_data(data_);
-      data.back().time = time;
+      data.back().steal_data(data_);
       return;
     }
 
-    data.push_back({time, data_});
+    data.push_back(data_);
+  }
+
+  void reuse_data_for_last_time(double time)
+  {
+    const TimeIndexPair &data_index = index_data_map.back();
+    index_data_map.push_back({time, data_index.source_time, data_index.index});
   }
 
   bool is_constant() const
@@ -232,6 +261,14 @@ template<typename T> class DataStore {
     T value = result.get_data();
     node->set(*socket, value);
   }
+
+ private:
+  const TimeIndexPair &get_index_for_time(double time) const
+  {
+    std::pair<size_t, Alembic::Abc::chrono_t> index_pair;
+    index_pair = time_sampling.getNearIndex(time, index_data_map.size());
+    return index_data_map[index_pair.first];
+  }
 };
 
 /* Actual cache for the stored data.