GPencil: Update-on-write using update cache

This implements the update cache described in T95401.

The cache is currently only used for drawing strokes and
sculpting (using the push brush).
**Note: Making use of the cache throughout grease pencil will
have to be done incrementally in other patches. **

The update cache stores what elements have changed in the
original data-block since the last time the eval object
was updated. Additionally, the update cache can store multiple
updates to the data and minimizes the number of elements
that need to be copied.

Elements can be tagged using `BKE_gpencil_tag_full_update` and
`BKE_gpencil_tag_light_update`. A full update means that the element
itself will be copied but also all of the content inside. E.g. when a
layer is tagged for a full update, the layer, all the frames inside the
layer and all the strokes inside the frames will be copied.
A light update means that only the properties of the element are copied
without any of the content. E.g. if a layer is tagged with a light
update, it will copy the layer name, opacity, transform, etc.

When the update cache is in use (e.g. elements have been tagged) then
the depsgraph will not trigger a copy-on-write, but an update-on-write.
This means that the update cache will be used to determine what elements
have changed and then only those elements will be copied over to the
eval object.

If the update cache is empty or the data block was tagged with a full
update, we always fall back to a copy-on-write.

Currently, the update cache is only used by the active depsgraph. This
is because we need to free the update cache after an update-on-write so
it's reset and we need to make sure it is not freed or read by other
depsgraphs.

Co-authored-by: @yann-lty
This patch was contributed by The SPA Studios.

Reviewed By: sergey, antoniov, #dependency_graph, pepeland, mendio

Maniphest Tasks: T95401

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

1 files changed, 152 insertions, 0 deletions

diff --git a/source/blender/blenkernel/BKE_gpencil_update_cache.h b/source/blender/blenkernel/BKE_gpencil_update_cache.h
new file mode 100644
index 00000000000..3ac78267922
--- /dev/null
+++ b/source/blender/blenkernel/BKE_gpencil_update_cache.h
@@ -0,0 +1,152 @@
+/*
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2022, Blender Foundation
+ * This is a new part of Blender
+ */
+
+#pragma once
+
+/** \file
+ * \ingroup bke
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "BLI_sys_types.h" /* for bool */
+
+struct DLRBT_Tree;
+struct bGPdata;
+struct bGPDlayer;
+struct bGPDframe;
+struct bGPDstroke;
+struct GPencilUpdateCache;
+
+/* GPencilUpdateCache.flag */
+typedef enum eGPUpdateCacheNodeFlag {
+  /* Node is a placeholder (e.g. when only an index is needed). */
+  GP_UPDATE_NODE_NO_COPY = 0,
+  /* Copy only element, not the content. */
+  GP_UPDATE_NODE_LIGHT_COPY = 1,
+  /* Copy the element as well as all of its content. */
+  GP_UPDATE_NODE_FULL_COPY = 2,
+} eGPUpdateCacheNodeFlag;
+
+/**
+ *  Cache for what needs to be updated after bGPdata was modified.
+ *
+ *  Every node holds information about one element that was changed:
+ *    - the index of where that element is in the linked-list
+ *    - the pointer to the original element in bGPdata
+ *  Additionally, nodes also hold other nodes that are one "level" below them.
+ *  E.g. a node that represents a change on a bGPDframe could contain a set of
+ *  nodes that represent a change on bGPDstrokes.
+ *  These nodes are stored in a red-black tree so that they are sorted by their
+ *  index to make sure they can be processed in the correct order.
+ */
+typedef struct GPencilUpdateCache {
+  /* Mapping from index to a GPencilUpdateCache struct. */
+  struct DLRBT_Tree *children;
+  /* eGPUpdateCacheNodeFlag */
+  int flag;
+  /* Index of the element in the linked-list. */
+  int index;
+  /* Pointer to one of bGPdata, bGPDLayer, bGPDFrame, bGPDStroke. */
+  void *data;
+} GPencilUpdateCache;
+
+/* Node structure in the DLRBT_Tree for GPencilUpdateCache mapping. */
+typedef struct GPencilUpdateCacheNode {
+  /* DLRB tree capabilities. */
+  struct GPencilUpdateCacheNode *next, *prev;
+  struct GPencilUpdateCacheNode *left, *right;
+  struct GPencilUpdateCacheNode *parent;
+  char tree_col;
+
+  char _pad[7];
+  /* Content of DLRB tree node. */
+  GPencilUpdateCache *cache;
+} GPencilUpdateCacheNode;
+
+/**
+ * Callback that is called in BKE_gpencil_traverse_update_cache at each level. If the callback
+ * returns true, then the children will not be iterated over and instead continue.
+ * \param cache: The cache at this level.
+ * \param user_data: Pointer to the user_data passed to BKE_gpencil_traverse_update_cache.
+ * \returns true, if iterating over the children of \a cache should be skipped, false if not.
+ */
+typedef bool (*GPencilUpdateCacheIter_Cb)(GPencilUpdateCache *cache, void *user_data);
+
+typedef struct GPencilUpdateCacheTraverseSettings {
+  /* Callbacks for the update cache traversal. Callback with index 0 is for layers, 1 for frames
+   * and 2 for strokes. */
+  GPencilUpdateCacheIter_Cb update_cache_cb[3];
+} GPencilUpdateCacheTraverseSettings;
+
+/**
+ * Allocates a new GPencilUpdateCache and populates it.
+ * \param data: A data pointer to populate the initial cache with.
+ * \param full_copy: If true, will mark this update cache as a full copy
+ * (GP_UPDATE_NODE_FULL_COPY). If false, it will be marked as a struct copy
+ * (GP_UPDATE_NODE_LIGHT_COPY).
+ */
+GPencilUpdateCache *BKE_gpencil_create_update_cache(void *data, bool full_copy);
+
+/**
+ * Traverses an update cache and executes callbacks at each level.
+ * \param cache: The update cache to traverse.
+ * \param ts: The traversal settings. This stores the callbacks that are called at each level.
+ * \param user_data: Custom data passed to each callback.
+ */
+void BKE_gpencil_traverse_update_cache(GPencilUpdateCache *cache,
+                                       GPencilUpdateCacheTraverseSettings *ts,
+                                       void *user_data);
+
+/**
+ * Tags an element (bGPdata, bGPDlayer, bGPDframe, or bGPDstroke) and all of its containing data to
+ * be updated in the next update-on-write operation.
+ *
+ * The function assumes that when a parameter is NULL all of the following parameters are NULL too.
+ * E.g. in order to tag a layer (gpl), the parameters would *have* to be (gpd, gpl, NULL, NULL).
+ */
+void BKE_gpencil_tag_full_update(struct bGPdata *gpd,
+                                 struct bGPDlayer *gpl,
+                                 struct bGPDframe *gpf,
+                                 struct bGPDstroke *gps);
+
+/**
+ * Tags an element (bGPdata, bGPDlayer, bGPDframe, or bGPDstroke) to be updated in the next
+ * update-on-write operation. This function will not update any of the containing data, only the
+ * struct itself.
+ *
+ * The function assumes that when a parameter is NULL all of the following parameters are NULL too.
+ * E.g. in order to tag a layer (gpl), the parameters would *have* to be (gpd, gpl, NULL, NULL).
+ */
+void BKE_gpencil_tag_light_update(struct bGPdata *gpd,
+                                  struct bGPDlayer *gpl,
+                                  struct bGPDframe *gpf,
+                                  struct bGPDstroke *gps);
+
+/**
+ * Frees the GPencilUpdateCache on the gpd->runtime. This will not free the data that the cache
+ * node might point to. It assumes that the cache does not own the data.
+ */
+void BKE_gpencil_free_update_cache(struct bGPdata *gpd);
+
+#ifdef __cplusplus
+}
+#endif