Image: Partial Update Redesign.

This patch reimplements the image partial updates. Biggest design motivation for the redesign
is that currently GPUTextures must be owned by the image. This reduces flexibility and adds
complexity to a single component especially when we want to have different structures.

The new design is not limited to GPUTextures and can also be used by reducing overhead in image
operations like scaling. Or partial image updating in Cycles.

The usecase in hand is that we want to support virtual images in the image editor so we can
work with images that don't fit in a single GPUTexture.

Using `BKE_image_partial_update_mark_region` or `BKE_image_partial_update_mark_full_update`
a part of an image can be marked as dirty. These regions are stored per ImageTile (UDIM).

When a part of the code wants to receive partial changes it needs to construct a `PartialUpdateUser`
by calling `BKE_image_partial_update_create`. As long as this instance is kept alive the changes can
be received.

When a user wants to update its own data it will call `BKE_image_partial_update_collect_changes`
This will collect the changes since the last time the user called this function. When the partial changes
are available the partial change can be read by calling `BKE_image_partial_update_get_next_change`

It can happen that the introduced mechanism doesn't have the data anymore to construct the
changes since the last time a PartialUpdateUser requested it. In this case it will get a request
to perform a full update.

Maniphest Tasks: T92613

Differential Revision: https://developer.blender.org/D13238

1 files changed, 598 insertions, 0 deletions

diff --git a/source/blender/blenkernel/intern/image_partial_update.cc b/source/blender/blenkernel/intern/image_partial_update.cc
new file mode 100644
index 00000000000..7e187c2014e
--- /dev/null
+++ b/source/blender/blenkernel/intern/image_partial_update.cc
@@ -0,0 +1,598 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Copyright 2021, Blender Foundation.
+ */
+/**
+ * \file image_gpu_partial_update.cc
+ * \ingroup bke
+ *
+ * To reduce the overhead of image processing this file contains a mechanism to detect areas of the
+ * image that are changed. These areas are organized in chunks. Changes that happen over time are
+ * organized in changesets.
+ *
+ * A common usecase is to update GPUTexture for drawing where only that part is uploaded that only
+ * changed.
+ *
+ * Usage:
+ *
+ * ```
+ * Image *image = ...;
+ * ImBuf *image_buffer = ...;
+ *
+ * // Partial_update_user should be kept for the whole session where the changes needs to be
+ * // tracked. Keep this instance alive as long as you need to track image changes.
+ *
+ * PartialUpdateUser *partial_update_user = BKE_image_partial_update_create(image);
+ *
+ * ...
+ *
+ * switch (BKE_image_partial_update_collect_changes(image, image_buffer))
+ * {
+ * case ePartialUpdateCollectResult::FullUpdateNeeded:
+ *  // Unable to do partial updates. Perform a full update.
+ *  break;
+ * case ePartialUpdateCollectResult::PartialChangesDetected:
+ *  PartialUpdateRegion change;
+ *  while (BKE_image_partial_update_get_next_change(partial_update_user, &change) ==
+ *         ePartialUpdateIterResult::ChangeAvailable){
+ *  // Do something with the change.
+ *  }
+ *  case ePartialUpdateCollectResult::NoChangesDetected:
+ *    break;
+ * }
+ *
+ * ...
+ *
+ * // Free partial_update_user.
+ * BKE_image_partial_update_free(partial_update_user);
+ *
+ * ```
+ */
+
+#include <optional>
+
+#include "BKE_image.h"
+#include "BKE_image_partial_update.hh"
+
+#include "DNA_image_types.h"
+
+#include "IMB_imbuf.h"
+#include "IMB_imbuf_types.h"
+
+#include "BLI_vector.hh"
+
+namespace blender::bke::image::partial_update {
+
+/** \brief Size of chunks to track changes. */
+constexpr int CHUNK_SIZE = 256;
+
+/**
+ * \brief Max number of changesets to keep in history.
+ *
+ * A higher number would need more memory and processing
+ * to calculate a changeset, but would lead to do partial updates for requests that don't happen
+ * every frame.
+ *
+ * A to small number would lead to more full updates when changes couldn't be reconstructed from
+ * the available history.
+ */
+constexpr int MAX_HISTORY_LEN = 4;
+
+/**
+ * \brief get the chunk number for the give pixel coordinate.
+ *
+ * As chunks are squares the this member can be used for both x and y axis.
+ */
+static int chunk_number_for_pixel(int pixel_offset)
+{
+  int chunk_offset = pixel_offset / CHUNK_SIZE;
+  if (pixel_offset < 0) {
+    chunk_offset -= 1;
+  }
+  return chunk_offset;
+}
+
+struct PartialUpdateUserImpl;
+struct PartialUpdateRegisterImpl;
+
+/**
+ * Wrap PartialUpdateUserImpl to its C-struct (PartialUpdateUser).
+ */
+static struct PartialUpdateUser *wrap(PartialUpdateUserImpl *user)
+{
+  return static_cast<struct PartialUpdateUser *>(static_cast<void *>(user));
+}
+
+/**
+ * Unwrap the PartialUpdateUser C-struct to its CPP counterpart (PartialUpdateUserImpl).
+ */
+static PartialUpdateUserImpl *unwrap(struct PartialUpdateUser *user)
+{
+  return static_cast<PartialUpdateUserImpl *>(static_cast<void *>(user));
+}
+
+/**
+ * Wrap PartialUpdateRegisterImpl to its C-struct (PartialUpdateRegister).
+ */
+static struct PartialUpdateRegister *wrap(PartialUpdateRegisterImpl *partial_update_register)
+{
+  return static_cast<struct PartialUpdateRegister *>(static_cast<void *>(partial_update_register));
+}
+
+/**
+ * Unwrap the PartialUpdateRegister C-struct to its CPP counterpart (PartialUpdateRegisterImpl).
+ */
+static PartialUpdateRegisterImpl *unwrap(struct PartialUpdateRegister *partial_update_register)
+{
+  return static_cast<PartialUpdateRegisterImpl *>(static_cast<void *>(partial_update_register));
+}
+
+using TileNumber = int32_t;
+using ChangesetID = int64_t;
+constexpr ChangesetID UnknownChangesetID = -1;
+
+struct PartialUpdateUserImpl {
+  /** \brief last changeset id that was seen by this user. */
+  ChangesetID last_changeset_id = UnknownChangesetID;
+
+  /** \brief regions that have been updated. */
+  Vector<PartialUpdateRegion> updated_regions;
+
+#ifdef NDEBUG
+  /** \brief reference to image to validate correct API usage. */
+  const void *debug_image_;
+#endif
+
+  /**
+   * \brief Clear the list of updated regions.
+   *
+   * Updated regions should be cleared at the start of #BKE_image_partial_update_collect_changes so
+   * the
+   */
+  void clear_updated_regions()
+  {
+    updated_regions.clear();
+  }
+};
+
+/**
+ * \brief Dirty chunks of an ImageTile.
+ *
+ * Internally dirty tiles are grouped together in change sets to make sure that the correct
+ * answer can be built for different users reducing the amount of merges.
+ */
+struct TileChangeset {
+ private:
+  /** \brief Dirty flag for each chunk. */
+  std::vector<bool> chunk_dirty_flags_;
+  /** \brief are there dirty/ */
+  bool has_dirty_chunks_ = false;
+
+ public:
+  /** \brief Width of the tile in pixels. */
+  int tile_width;
+  /** \brief Height of the tile in pixels. */
+  int tile_height;
+  /** \brief Number of chunks along the x-axis. */
+  int chunk_x_len;
+  /** \brief Number of chunks along the y-axis. */
+  int chunk_y_len;
+
+  TileNumber tile_number;
+
+  void clear()
+  {
+    init_chunks(chunk_x_len, chunk_y_len);
+  }
+
+  /**
+   * \brief Update the resolution of the tile.
+   *
+   * \returns true: resolution has been updated.
+   *          false: resolution was unchanged.
+   */
+  bool update_resolution(const ImBuf *image_buffer)
+  {
+    if (tile_width == image_buffer->x && tile_height == image_buffer->y) {
+      return false;
+    }
+
+    tile_width = image_buffer->x;
+    tile_height = image_buffer->y;
+
+    int chunk_x_len = tile_width / CHUNK_SIZE;
+    int chunk_y_len = tile_height / CHUNK_SIZE;
+    init_chunks(chunk_x_len, chunk_y_len);
+    return true;
+  }
+
+  void mark_region(const rcti *updated_region)
+  {
+    int start_x_chunk = chunk_number_for_pixel(updated_region->xmin);
+    int end_x_chunk = chunk_number_for_pixel(updated_region->xmax - 1);
+    int start_y_chunk = chunk_number_for_pixel(updated_region->ymin);
+    int end_y_chunk = chunk_number_for_pixel(updated_region->ymax - 1);
+
+    /* Clamp tiles to tiles in image. */
+    start_x_chunk = max_ii(0, start_x_chunk);
+    start_y_chunk = max_ii(0, start_y_chunk);
+    end_x_chunk = min_ii(chunk_x_len - 1, end_x_chunk);
+    end_y_chunk = min_ii(chunk_y_len - 1, end_y_chunk);
+
+    /* Early exit when no tiles need to be updated. */
+    if (start_x_chunk >= chunk_x_len) {
+      return;
+    }
+    if (start_y_chunk >= chunk_y_len) {
+      return;
+    }
+    if (end_x_chunk < 0) {
+      return;
+    }
+    if (end_y_chunk < 0) {
+      return;
+    }
+
+    mark_chunks_dirty(start_x_chunk, start_y_chunk, end_x_chunk, end_y_chunk);
+  }
+
+  void mark_chunks_dirty(int start_x_chunk, int start_y_chunk, int end_x_chunk, int end_y_chunk)
+  {
+    for (int chunk_y = start_y_chunk; chunk_y <= end_y_chunk; chunk_y++) {
+      for (int chunk_x = start_x_chunk; chunk_x <= end_x_chunk; chunk_x++) {
+        int chunk_index = chunk_y * chunk_x_len + chunk_x;
+        chunk_dirty_flags_[chunk_index] = true;
+      }
+    }
+    has_dirty_chunks_ = true;
+  }
+
+  bool has_dirty_chunks() const
+  {
+    return has_dirty_chunks_;
+  }
+
+  void init_chunks(int chunk_x_len_, int chunk_y_len_)
+  {
+    chunk_x_len = chunk_x_len_;
+    chunk_y_len = chunk_y_len_;
+    const int chunk_len = chunk_x_len * chunk_y_len;
+    const int previous_chunk_len = chunk_dirty_flags_.size();
+
+    chunk_dirty_flags_.resize(chunk_len);
+    /* Fast exit. When the changeset was already empty no need to re-init the chunk_validity. */
+    if (!has_dirty_chunks()) {
+      return;
+    }
+    for (int index = 0; index < min_ii(chunk_len, previous_chunk_len); index++) {
+      chunk_dirty_flags_[index] = false;
+    }
+    has_dirty_chunks_ = false;
+  }
+
+  /** \brief Merge the given changeset into the receiver. */
+  void merge(const TileChangeset &other)
+  {
+    BLI_assert(chunk_x_len == other.chunk_x_len);
+    BLI_assert(chunk_y_len == other.chunk_y_len);
+    const int chunk_len = chunk_x_len * chunk_y_len;
+
+    for (int chunk_index = 0; chunk_index < chunk_len; chunk_index++) {
+      chunk_dirty_flags_[chunk_index] = chunk_dirty_flags_[chunk_index] |
+                                        other.chunk_dirty_flags_[chunk_index];
+    }
+    has_dirty_chunks_ |= other.has_dirty_chunks_;
+  }
+
+  /** \brief has a chunk changed inside this changeset. */
+  bool is_chunk_dirty(int chunk_x, int chunk_y) const
+  {
+    const int chunk_index = chunk_y * chunk_x_len + chunk_x;
+    return chunk_dirty_flags_[chunk_index];
+  }
+};
+
+/** \brief Changeset keeping track of changes for an image */
+struct Changeset {
+ private:
+  Vector<TileChangeset> tiles;
+
+ public:
+  /** \brief Keep track if any of the tiles have dirty chunks. */
+  bool has_dirty_chunks;
+
+  /**
+   * \brief Retrieve the TileChangeset for the given ImageTile.
+   *
+   * When the TileChangeset isn't found, it will be added.
+   */
+  TileChangeset &operator[](const ImageTile *image_tile)
+  {
+    for (TileChangeset &tile_changeset : tiles) {
+      if (tile_changeset.tile_number == image_tile->tile_number) {
+        return tile_changeset;
+      }
+    }
+
+    TileChangeset tile_changeset;
+    tile_changeset.tile_number = image_tile->tile_number;
+    tiles.append_as(tile_changeset);
+
+    return tiles.last();
+  }
+
+  /** \brief Does this changeset contain data for the given tile. */
+  bool has_tile(const ImageTile *image_tile)
+  {
+    for (TileChangeset &tile_changeset : tiles) {
+      if (tile_changeset.tile_number == image_tile->tile_number) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /** \brief Clear this changeset. */
+  void clear()
+  {
+    tiles.clear();
+    has_dirty_chunks = false;
+  }
+};
+
+/**
+ * \brief Partial update changes stored inside the image runtime.
+ *
+ * The PartialUpdateRegisterImpl will keep track of changes over time. Changes are groups inside
+ * TileChangesets.
+ */
+struct PartialUpdateRegisterImpl {
+  /** \brief changeset id of the first changeset kept in #history. */
+  ChangesetID first_changeset_id;
+  /** \brief changeset id of the top changeset kept in #history. */
+  ChangesetID last_changeset_id;
+
+  /** \brief history of changesets. */
+  Vector<Changeset> history;
+  /** \brief The current changeset. New changes will be added to this changeset. */
+  Changeset current_changeset;
+
+  void update_resolution(const ImageTile *image_tile, const ImBuf *image_buffer)
+  {
+    TileChangeset &tile_changeset = current_changeset[image_tile];
+    const bool has_dirty_chunks = tile_changeset.has_dirty_chunks();
+    const bool resolution_changed = tile_changeset.update_resolution(image_buffer);
+
+    if (has_dirty_chunks && resolution_changed && !history.is_empty()) {
+      mark_full_update();
+    }
+  }
+
+  void mark_full_update()
+  {
+    history.clear();
+    last_changeset_id++;
+    current_changeset.clear();
+    first_changeset_id = last_changeset_id;
+  }
+
+  void mark_region(const ImageTile *image_tile, const rcti *updated_region)
+  {
+    TileChangeset &tile_changeset = current_changeset[image_tile];
+    tile_changeset.mark_region(updated_region);
+    current_changeset.has_dirty_chunks |= tile_changeset.has_dirty_chunks();
+  }
+
+  void ensure_empty_changeset()
+  {
+    if (!current_changeset.has_dirty_chunks) {
+      /* No need to create a new changeset when previous changeset does not contain any dirty
+       * tiles. */
+      return;
+    }
+    commit_current_changeset();
+    limit_history();
+  }
+
+  /** \brief Move the current changeset to the history and resets the current changeset. */
+  void commit_current_changeset()
+  {
+    history.append_as(std::move(current_changeset));
+    current_changeset.clear();
+    last_changeset_id++;
+  }
+
+  /** \brief Limit the number of items in the changeset. */
+  void limit_history()
+  {
+    const int num_items_to_remove = max_ii(history.size() - MAX_HISTORY_LEN, 0);
+    if (num_items_to_remove == 0) {
+      return;
+    }
+    history.remove(0, num_items_to_remove);
+    first_changeset_id += num_items_to_remove;
+  }
+
+  /**
+   * /brief Check if data is available to construct the update tiles for the given
+   * changeset_id.
+   *
+   * The update tiles can be created when changeset id is between
+   */
+  bool can_construct(ChangesetID changeset_id)
+  {
+    return changeset_id >= first_changeset_id;
+  }
+
+  /**
+   * \brief collect all historic changes since a given changeset.
+   */
+  std::optional<TileChangeset> changed_tile_chunks_since(const ImageTile *image_tile,
+                                                         const ChangesetID from_changeset)
+  {
+    std::optional<TileChangeset> changed_chunks = std::nullopt;
+    for (int index = from_changeset - first_changeset_id; index < history.size(); index++) {
+      if (!history[index].has_tile(image_tile)) {
+        continue;
+      }
+
+      TileChangeset &tile_changeset = history[index][image_tile];
+      if (!changed_chunks.has_value()) {
+        changed_chunks = std::make_optional<TileChangeset>();
+        changed_chunks->init_chunks(tile_changeset.chunk_x_len, tile_changeset.chunk_y_len);
+        changed_chunks->tile_number = image_tile->tile_number;
+      }
+
+      changed_chunks->merge(tile_changeset);
+    }
+    return changed_chunks;
+  }
+};
+
+static PartialUpdateRegister *image_partial_update_register_ensure(Image *image)
+{
+  if (image->runtime.partial_update_register == nullptr) {
+    PartialUpdateRegisterImpl *partial_update_register = MEM_new<PartialUpdateRegisterImpl>(
+        __func__);
+    image->runtime.partial_update_register = wrap(partial_update_register);
+  }
+  return image->runtime.partial_update_register;
+}
+
+ePartialUpdateCollectResult BKE_image_partial_update_collect_changes(Image *image,
+                                                                     PartialUpdateUser *user)
+{
+  PartialUpdateUserImpl *user_impl = unwrap(user);
+#ifdef NDEBUG
+  BLI_assert(image == user_impl->debug_image_);
+#endif
+
+  user_impl->clear_updated_regions();
+
+  PartialUpdateRegisterImpl *partial_updater = unwrap(image_partial_update_register_ensure(image));
+  partial_updater->ensure_empty_changeset();
+
+  if (!partial_updater->can_construct(user_impl->last_changeset_id)) {
+    user_impl->last_changeset_id = partial_updater->last_changeset_id;
+    return ePartialUpdateCollectResult::FullUpdateNeeded;
+  }
+
+  /* Check if there are changes since last invocation for the user. */
+  if (user_impl->last_changeset_id == partial_updater->last_changeset_id) {
+    return ePartialUpdateCollectResult::NoChangesDetected;
+  }
+
+  /* Collect changed tiles. */
+  LISTBASE_FOREACH (ImageTile *, tile, &image->tiles) {
+    std::optional<TileChangeset> changed_chunks = partial_updater->changed_tile_chunks_since(
+        tile, user_impl->last_changeset_id);
+    /* Check if chunks of this tile are dirty. */
+    if (!changed_chunks.has_value()) {
+      continue;
+    }
+    if (!changed_chunks->has_dirty_chunks()) {
+      continue;
+    }
+
+    /* Convert tiles in the changeset to rectangles that are dirty. */
+    for (int chunk_y = 0; chunk_y < changed_chunks->chunk_y_len; chunk_y++) {
+      for (int chunk_x = 0; chunk_x < changed_chunks->chunk_x_len; chunk_x++) {
+        if (!changed_chunks->is_chunk_dirty(chunk_x, chunk_y)) {
+          continue;
+        }
+
+        PartialUpdateRegion region;
+        region.tile_number = tile->tile_number;
+        BLI_rcti_init(&region.region,
+                      chunk_x * CHUNK_SIZE,
+                      (chunk_x + 1) * CHUNK_SIZE,
+                      chunk_y * CHUNK_SIZE,
+                      (chunk_y + 1) * CHUNK_SIZE);
+        user_impl->updated_regions.append_as(region);
+      }
+    }
+  }
+
+  user_impl->last_changeset_id = partial_updater->last_changeset_id;
+  return ePartialUpdateCollectResult::PartialChangesDetected;
+}
+
+ePartialUpdateIterResult BKE_image_partial_update_get_next_change(PartialUpdateUser *user,
+                                                                  PartialUpdateRegion *r_region)
+{
+  PartialUpdateUserImpl *user_impl = unwrap(user);
+  if (user_impl->updated_regions.is_empty()) {
+    return ePartialUpdateIterResult::Finished;
+  }
+  PartialUpdateRegion region = user_impl->updated_regions.pop_last();
+  *r_region = region;
+  return ePartialUpdateIterResult::ChangeAvailable;
+}
+
+}  // namespace blender::bke::image::partial_update
+
+extern "C" {
+
+using namespace blender::bke::image::partial_update;
+
+// TODO(jbakker): cleanup parameter.
+struct PartialUpdateUser *BKE_image_partial_update_create(const struct Image *image)
+{
+  PartialUpdateUserImpl *user_impl = MEM_new<PartialUpdateUserImpl>(__func__);
+
+#ifdef NDEBUG
+  user_impl->debug_image_ = image;
+#else
+  UNUSED_VARS(image);
+#endif
+
+  return wrap(user_impl);
+}
+
+void BKE_image_partial_update_free(PartialUpdateUser *user)
+{
+  PartialUpdateUserImpl *user_impl = unwrap(user);
+  MEM_delete<PartialUpdateUserImpl>(user_impl);
+}
+
+/* --- Image side --- */
+
+void BKE_image_partial_update_register_free(Image *image)
+{
+  PartialUpdateRegisterImpl *partial_update_register = unwrap(
+      image->runtime.partial_update_register);
+  if (partial_update_register) {
+    MEM_delete<PartialUpdateRegisterImpl>(partial_update_register);
+  }
+  image->runtime.partial_update_register = nullptr;
+}
+
+void BKE_image_partial_update_mark_region(Image *image,
+                                          const ImageTile *image_tile,
+                                          const ImBuf *image_buffer,
+                                          const rcti *updated_region)
+{
+  PartialUpdateRegisterImpl *partial_updater = unwrap(image_partial_update_register_ensure(image));
+  partial_updater->update_resolution(image_tile, image_buffer);
+  partial_updater->mark_region(image_tile, updated_region);
+}
+
+void BKE_image_partial_update_mark_full_update(Image *image)
+{
+  PartialUpdateRegisterImpl *partial_updater = unwrap(image_partial_update_register_ensure(image));
+  partial_updater->mark_full_update();
+}
+}