GPU: Thread safe index buffer builders.

Current index builder is designed to be used in a single thread.
This makes all index buffer extractions single threaded.
This patch adds a thread safe solution enabling multithreaded
building of index buffers.

To reduce locking the solution would provide a task/thread local
index buffer builder (called sub builder).
When a thread is finished this thread local index buffer builder
can be joined with the initial index buffer builder.

`GPU_indexbuf_subbuilder_init`: Initialized a sub builder. The
index list is shared between the parent and sub buffer, but the
counters are localized. Ensuring that updating counters would
not need any locking.

`GPU_indexbuf_subbuilder_finish`: merge the information of the
sub builder back to the parent builder. Needs to be invoked outside
the worker thread, or when sure that all worker threads have been
finished. Internal the function is not thread safe.

For testing purposes the extract_points extractor has been migrated to
the new API. Herefore changes to the mesh extractor were needed.

* When creating tasks, the task number of current task is stored in
  ExtractTaskData including the total number of tasks.
* Adding two functions  in `MeshExtract`.
** `task_init` will initialize the task specific userdata.
** `task_finish` should merge back the task specific userdata back.
* adding task_id parameter to the iteration functions so they can
  access the correct task data without any need for locking.

There is no noticeable change in end user performance.

Reviewed By: mano-wii

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

4 files changed, 82 insertions, 0 deletions

diff --git a/source/blender/gpu/CMakeLists.txt b/source/blender/gpu/CMakeLists.txt
index cf6009c2881..8468985309f 100644
--- a/source/blender/gpu/CMakeLists.txt
+++ b/source/blender/gpu/CMakeLists.txt
@@ -394,6 +394,8 @@ if(WITH_GTESTS)
   if(WITH_OPENGL_DRAW_TESTS)
     set(TEST_SRC
       tests/gpu_testing.cc
+
+      tests/gpu_index_buffer_test.cc
       tests/gpu_shader_test.cc
 
       tests/gpu_testing.hh
diff --git a/source/blender/gpu/GPU_index_buffer.h b/source/blender/gpu/GPU_index_buffer.h
index 4e8d854c7ce..03d60c60b4b 100644
--- a/source/blender/gpu/GPU_index_buffer.h
+++ b/source/blender/gpu/GPU_index_buffer.h
@@ -44,6 +44,7 @@ typedef struct GPUIndexBufBuilder {
   uint index_max;
   GPUPrimType prim_type;
   uint32_t *data;
+  const struct GPUIndexBufBuilder *parent;
 } GPUIndexBufBuilder;
 
 /* supports all primitive types. */
@@ -53,6 +54,19 @@ void GPU_indexbuf_init_ex(GPUIndexBufBuilder *, GPUPrimType, uint index_len, uin
 void GPU_indexbuf_init(GPUIndexBufBuilder *, GPUPrimType, uint prim_len, uint vertex_len);
 GPUIndexBuf *GPU_indexbuf_build_on_device(uint index_len);
 
+/*
+ * Thread safe sub builders.
+ *
+ * Note that `GPU_indexbuf_subbuilder_init` and `GPU_indexbuf_subbuilder_finish` are not thread
+ * safe and should be called when no threads are active. The pattern is to create a subbuilder for
+ * each thread/task. Each thread/task would update their sub builder. When all thread are completed
+ * the sub-builders can then be merged back to the parent builder.
+ */
+void GPU_indexbuf_subbuilder_init(const GPUIndexBufBuilder *parent_builder,
+                                  GPUIndexBufBuilder *sub_builder);
+void GPU_indexbuf_subbuilder_finish(GPUIndexBufBuilder *builder,
+                                    const GPUIndexBufBuilder *parent_builder);
+
 void GPU_indexbuf_add_generic_vert(GPUIndexBufBuilder *, uint v);
 void GPU_indexbuf_add_primitive_restart(GPUIndexBufBuilder *);
 
diff --git a/source/blender/gpu/intern/gpu_index_buffer.cc b/source/blender/gpu/intern/gpu_index_buffer.cc
index 9f283a3a944..3cdcaac5544 100644
--- a/source/blender/gpu/intern/gpu_index_buffer.cc
+++ b/source/blender/gpu/intern/gpu_index_buffer.cc
@@ -25,6 +25,7 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_math_base.h"
 #include "BLI_utildefines.h"
 
 #include "gpu_backend.hh"
@@ -56,6 +57,7 @@ void GPU_indexbuf_init_ex(GPUIndexBufBuilder *builder,
   builder->index_max = 0;
   builder->prim_type = prim_type;
   builder->data = (uint *)MEM_callocN(builder->max_index_len * sizeof(uint), "GPUIndexBuf data");
+  builder->parent = nullptr;
 }
 
 void GPU_indexbuf_init(GPUIndexBufBuilder *builder,
@@ -78,6 +80,23 @@ GPUIndexBuf *GPU_indexbuf_build_on_device(uint index_len)
   return elem_;
 }
 
+void GPU_indexbuf_subbuilder_init(const GPUIndexBufBuilder *parent_builder,
+                                  GPUIndexBufBuilder *sub_builder)
+{
+  BLI_assert(parent_builder->parent == nullptr);
+  memcpy(sub_builder, parent_builder, sizeof(GPUIndexBufBuilder));
+  sub_builder->parent = parent_builder;
+}
+
+void GPU_indexbuf_subbuilder_finish(GPUIndexBufBuilder *parent_builder,
+                                    const GPUIndexBufBuilder *sub_builder)
+{
+  BLI_assert(parent_builder == sub_builder->parent);
+  parent_builder->index_len = max_uu(parent_builder->index_len, sub_builder->index_len);
+  parent_builder->index_min = min_uu(parent_builder->index_min, sub_builder->index_min);
+  parent_builder->index_max = max_uu(parent_builder->index_max, sub_builder->index_max);
+}
+
 void GPU_indexbuf_add_generic_vert(GPUIndexBufBuilder *builder, uint v)
 {
 #if TRUST_NO_ONE
diff --git a/source/blender/gpu/tests/gpu_index_buffer_test.cc b/source/blender/gpu/tests/gpu_index_buffer_test.cc
new file mode 100644
index 00000000000..ebc110056e3
--- /dev/null
+++ b/source/blender/gpu/tests/gpu_index_buffer_test.cc
@@ -0,0 +1,47 @@
+/* Apache License, Version 2.0 */
+
+#include "testing/testing.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "GPU_index_buffer.h"
+
+#include "gpu_testing.hh"
+
+namespace blender::gpu::tests {
+
+TEST_F(GPUTest, gpu_index_buffer_subbuilders)
+{
+  const uint num_subbuilders = 10;
+  const uint verts_per_subbuilders = 100;
+  const uint vertex_len = num_subbuilders * verts_per_subbuilders;
+
+  GPUIndexBufBuilder builder;
+  GPU_indexbuf_init(&builder, GPU_PRIM_POINTS, vertex_len, vertex_len);
+
+  GPUIndexBufBuilder subbuilders[num_subbuilders];
+  for (int subbuilder_index = 0; subbuilder_index < num_subbuilders; subbuilder_index++) {
+    GPU_indexbuf_subbuilder_init(&builder, &subbuilders[subbuilder_index]);
+  }
+
+  for (int subbuilder_index = 0; subbuilder_index < num_subbuilders; subbuilder_index++) {
+    GPUIndexBufBuilder &subbuilder = subbuilders[subbuilder_index];
+    for (int subbuilder_vert_index = 0; subbuilder_vert_index < verts_per_subbuilders;
+         subbuilder_vert_index++) {
+      int vert_index_to_update = subbuilder_index * verts_per_subbuilders + subbuilder_vert_index;
+      GPU_indexbuf_set_point_vert(&subbuilder, vert_index_to_update, vert_index_to_update);
+    }
+  }
+
+  for (int subbuilder_index = 0; subbuilder_index < num_subbuilders; subbuilder_index++) {
+    EXPECT_EQ(builder.index_len, subbuilder_index * verts_per_subbuilders);
+    GPU_indexbuf_subbuilder_finish(&builder, &subbuilders[subbuilder_index]);
+    EXPECT_EQ(builder.index_len, (subbuilder_index + 1) * verts_per_subbuilders);
+  }
+
+  GPUIndexBuf *index_buffer = GPU_indexbuf_build(&builder);
+  EXPECT_NE(index_buffer, nullptr);
+  GPU_INDEXBUF_DISCARD_SAFE(index_buffer);
+}
+
+}  // namespace blender::gpu::tests