LineArt: Use array instead of lists for edges pending occusion query

It turns out there's no practical use for separating different edge types
before final occlusion stage, also using an array should be faster overall.
So changed those lists into one pending array, it also made the
iteration and occlusion task scheduling simpler.

Reviewed By: Sebastian Parborg (zeddb)

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

3 files changed, 97 insertions, 202 deletions

diff --git a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
index 12c1e9cf563..06738ef6a12 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
+++ b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
@@ -204,6 +204,12 @@ enum eLineArtTileRecursiveLimit {
 #define LRT_TILE_SPLITTING_TRIANGLE_LIMIT 100
 #define LRT_TILE_EDGE_COUNT_INITIAL 32
 
+typedef struct LineartPendingEdges {
+  LineartEdge **array;
+  int max;
+  int next;
+} LineartPendingEdges;
+
 typedef struct LineartRenderBuffer {
   struct LineartRenderBuffer *prev, *next;
 
@@ -248,15 +254,9 @@ typedef struct LineartRenderBuffer {
 
   int triangle_size;
 
-  /* Although using ListBase here, LineartEdge is single linked list.
-   * list.last is used to store worker progress along the list.
-   * See lineart_main_occlusion_begin() for more info. */
-  ListBase contour;
-  ListBase intersection;
-  ListBase crease;
-  ListBase material;
-  ListBase edge_mark;
-  ListBase floating;
+  /* Note: Data inside #pending_edges are allocated with MEM_xxx call instead of in pool. */
+  struct LineartPendingEdges pending_edges;
+  int scheduled_count;
 
   ListBase chains;
 
@@ -362,14 +362,9 @@ typedef struct LineartRenderTaskInfo {
 
   int thread_id;
 
-  /* These lists only denote the part of the main edge list that the thread should iterate over.
-   * Be careful to not iterate outside of these bounds as it is not thread safe to do so. */
-  ListBase contour;
-  ListBase intersection;
-  ListBase crease;
-  ListBase material;
-  ListBase edge_mark;
-  ListBase floating;
+  /* #pending_edges here only stores a refernce to a portion in LineartRenderbuffer::pending_edges,
+   * assigned by the occlusion scheduler. */
+  struct LineartPendingEdges pending_edges;
 
 } LineartRenderTaskInfo;
 
@@ -387,14 +382,8 @@ typedef struct LineartObjectInfo {
 
   bool free_use_mesh;
 
-  /* Threads will add lines inside here, when all threads are done, we combine those into the
-   * ones in LineartRenderBuffer. */
-  ListBase contour;
-  ListBase intersection;
-  ListBase crease;
-  ListBase material;
-  ListBase edge_mark;
-  ListBase floating;
+  /* Note: Data inside #pending_edges are allocated with MEM_xxx call instead of in pool. */
+  struct LineartPendingEdges pending_edges;
 
 } LineartObjectInfo;
 
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
index 08a8aed41c0..fe1bbc3fc23 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
@@ -97,7 +97,7 @@ static bool lineart_triangle_edge_image_space_occlusion(SpinLock *spl,
                                                         double *from,
                                                         double *to);
 
-static void lineart_add_edge_to_list(LineartRenderBuffer *rb, LineartEdge *e);
+static void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e);
 
 static LineartCache *lineart_init_cache(void);
 
@@ -412,38 +412,26 @@ static void lineart_occlusion_single_line(LineartRenderBuffer *rb, LineartEdge *
 
 static int lineart_occlusion_make_task_info(LineartRenderBuffer *rb, LineartRenderTaskInfo *rti)
 {
-  LineartEdge *data;
-  int i;
   int res = 0;
+  int starting_index;
 
   BLI_spin_lock(&rb->lock_task);
 
-#define LRT_ASSIGN_OCCLUSION_TASK(name) \
-  if (rb->name.last) { \
-    data = rb->name.last; \
-    rti->name.first = (void *)data; \
-    for (i = 0; i < LRT_THREAD_EDGE_COUNT && data; i++) { \
-      data = data->next; \
-    } \
-    rti->name.last = data; \
-    rb->name.last = data; \
-    res = 1; \
-  } \
-  else { \
-    rti->name.first = rti->name.last = NULL; \
-  }
-
-  LRT_ASSIGN_OCCLUSION_TASK(contour);
-  LRT_ASSIGN_OCCLUSION_TASK(intersection);
-  LRT_ASSIGN_OCCLUSION_TASK(crease);
-  LRT_ASSIGN_OCCLUSION_TASK(material);
-  LRT_ASSIGN_OCCLUSION_TASK(edge_mark);
-  LRT_ASSIGN_OCCLUSION_TASK(floating);
-
-#undef LRT_ASSIGN_OCCLUSION_TASK
+  starting_index = rb->scheduled_count;
+  rb->scheduled_count += LRT_THREAD_EDGE_COUNT;
 
   BLI_spin_unlock(&rb->lock_task);
 
+  if (starting_index >= rb->pending_edges.next) {
+    res = 0;
+  }
+  else {
+    rti->pending_edges.array = &rb->pending_edges.array[starting_index];
+    int remaining = rb->pending_edges.next - starting_index;
+    rti->pending_edges.max = MIN2(remaining, LRT_THREAD_EDGE_COUNT);
+    res = 1;
+  }
+
   return res;
 }
 
@@ -453,28 +441,8 @@ static void lineart_occlusion_worker(TaskPool *__restrict UNUSED(pool), LineartR
   LineartEdge *eip;
 
   while (lineart_occlusion_make_task_info(rb, rti)) {
-
-    for (eip = rti->contour.first; eip && eip != rti->contour.last; eip = eip->next) {
-      lineart_occlusion_single_line(rb, eip, rti->thread_id);
-    }
-
-    for (eip = rti->crease.first; eip && eip != rti->crease.last; eip = eip->next) {
-      lineart_occlusion_single_line(rb, eip, rti->thread_id);
-    }
-
-    for (eip = rti->intersection.first; eip && eip != rti->intersection.last; eip = eip->next) {
-      lineart_occlusion_single_line(rb, eip, rti->thread_id);
-    }
-
-    for (eip = rti->material.first; eip && eip != rti->material.last; eip = eip->next) {
-      lineart_occlusion_single_line(rb, eip, rti->thread_id);
-    }
-
-    for (eip = rti->edge_mark.first; eip && eip != rti->edge_mark.last; eip = eip->next) {
-      lineart_occlusion_single_line(rb, eip, rti->thread_id);
-    }
-
-    for (eip = rti->floating.first; eip && eip != rti->floating.last; eip = eip->next) {
+    for (int i = 0; i < rti->pending_edges.max; i++) {
+      eip = rti->pending_edges.array[i];
       lineart_occlusion_single_line(rb, eip, rti->thread_id);
     }
   }
@@ -492,15 +460,6 @@ static void lineart_main_occlusion_begin(LineartRenderBuffer *rb)
                                            "Task Pool");
   int i;
 
-  /* The "last" entry is used to store worker progress in the whole list.
-   * These list themselves are single-direction linked, with list.first being the head. */
-  rb->contour.last = rb->contour.first;
-  rb->crease.last = rb->crease.first;
-  rb->intersection.last = rb->intersection.first;
-  rb->material.last = rb->material.first;
-  rb->edge_mark.last = rb->edge_mark.first;
-  rb->floating.last = rb->floating.first;
-
   TaskPool *tp = BLI_task_pool_create(NULL, TASK_PRIORITY_HIGH);
 
   for (i = 0; i < thread_count; i++) {
@@ -836,7 +795,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
     e->object_ref = ob; \
     e->t1 = ((old_e->t1 == tri) ? (new_tri) : (old_e->t1)); \
     e->t2 = ((old_e->t2 == tri) ? (new_tri) : (old_e->t2)); \
-    lineart_add_edge_to_list(rb, e); \
+    lineart_add_edge_to_array(&rb->pending_edges, e); \
   }
 
 #define RELINK_EDGE(e_num, new_tri) \
@@ -922,7 +881,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
         INCREASE_EDGE
         if (allow_boundaries) {
           e->flags = LRT_EDGE_FLAG_CONTOUR;
-          lineart_prepend_edge_direct(&rb->contour.first, e);
+          lineart_add_edge_to_array(&rb->pending_edges, e);
         }
         /* NOTE: inverting `e->v1/v2` (left/right point) doesn't matter as long as
          * `tri->edge` and `tri->v` has the same sequence. and the winding direction
@@ -971,7 +930,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
         INCREASE_EDGE
         if (allow_boundaries) {
           e->flags = LRT_EDGE_FLAG_CONTOUR;
-          lineart_prepend_edge_direct(&rb->contour.first, e);
+          lineart_add_edge_to_array(&rb->pending_edges, e);
         }
         e->v1 = &vt[0];
         e->v2 = &vt[1];
@@ -1012,7 +971,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
         INCREASE_EDGE
         if (allow_boundaries) {
           e->flags = LRT_EDGE_FLAG_CONTOUR;
-          lineart_prepend_edge_direct(&rb->contour.first, e);
+          lineart_add_edge_to_array(&rb->pending_edges, e);
         }
         e->v1 = &vt[1];
         e->v2 = &vt[0];
@@ -1087,7 +1046,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
         INCREASE_EDGE
         if (allow_boundaries) {
           e->flags = LRT_EDGE_FLAG_CONTOUR;
-          lineart_prepend_edge_direct(&rb->contour.first, e);
+          lineart_add_edge_to_array(&rb->pending_edges, e);
         }
         e->v1 = &vt[1];
         e->v2 = &vt[0];
@@ -1139,7 +1098,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
         INCREASE_EDGE
         if (allow_boundaries) {
           e->flags = LRT_EDGE_FLAG_CONTOUR;
-          lineart_prepend_edge_direct(&rb->contour.first, e);
+          lineart_add_edge_to_array(&rb->pending_edges, e);
         }
         e->v1 = &vt[1];
         e->v2 = &vt[0];
@@ -1188,7 +1147,7 @@ static void lineart_triangle_cull_single(LineartRenderBuffer *rb,
         INCREASE_EDGE
         if (allow_boundaries) {
           e->flags = LRT_EDGE_FLAG_CONTOUR;
-          lineart_prepend_edge_direct(&rb->contour.first, e);
+          lineart_add_edge_to_array(&rb->pending_edges, e);
         }
         e->v1 = &vt[1];
         e->v2 = &vt[0];
@@ -1753,75 +1712,52 @@ static void loose_data_sum_reduce(const void *__restrict UNUSED(userdata),
   lineart_join_loose_edge_arr(final, loose_chunk);
 }
 
-static void lineart_add_edge_to_list(LineartRenderBuffer *rb, LineartEdge *e)
+static void lineart_add_edge_to_array(LineartPendingEdges *pe, LineartEdge *e)
 {
-  switch (e->flags) {
-    case LRT_EDGE_FLAG_CONTOUR:
-      lineart_prepend_edge_direct(&rb->contour.first, e);
-      break;
-    case LRT_EDGE_FLAG_CREASE:
-      lineart_prepend_edge_direct(&rb->crease.first, e);
-      break;
-    case LRT_EDGE_FLAG_MATERIAL:
-      lineart_prepend_edge_direct(&rb->material.first, e);
-      break;
-    case LRT_EDGE_FLAG_EDGE_MARK:
-      lineart_prepend_edge_direct(&rb->edge_mark.first, e);
-      break;
-    case LRT_EDGE_FLAG_INTERSECTION:
-      lineart_prepend_edge_direct(&rb->intersection.first, e);
-      break;
-    case LRT_EDGE_FLAG_LOOSE:
-      lineart_prepend_edge_direct(&rb->floating.first, e);
-      break;
+  if (pe->next >= pe->max || !pe->max) {
+    if (!pe->max) {
+      pe->max = 1000;
+    }
+
+    LineartEdge **new_array = MEM_mallocN(sizeof(LineartEdge *) * pe->max * 2,
+                                          "LineartPendingEdges array");
+    if (LIKELY(pe->array)) {
+      memcpy(new_array, pe->array, sizeof(LineartEdge *) * pe->max);
+      MEM_freeN(pe->array);
+    }
+    pe->max *= 2;
+    pe->array = new_array;
   }
+  pe->array[pe->next] = e;
+  pe->next++;
 }
 
-static void lineart_add_edge_to_list_thread(LineartObjectInfo *obi, LineartEdge *e)
+static void lineart_add_edge_to_array_thread(LineartObjectInfo *obi, LineartEdge *e)
 {
+  lineart_add_edge_to_array(&obi->pending_edges, e);
+}
 
-#define LRT_ASSIGN_EDGE(name) \
-  lineart_prepend_edge_direct(&obi->name.first, e); \
-  if (!obi->name.last) { \
-    obi->name.last = e; \
-  }
-  switch (e->flags) {
-    case LRT_EDGE_FLAG_CONTOUR:
-      LRT_ASSIGN_EDGE(contour);
-      break;
-    case LRT_EDGE_FLAG_CREASE:
-      LRT_ASSIGN_EDGE(crease);
-      break;
-    case LRT_EDGE_FLAG_MATERIAL:
-      LRT_ASSIGN_EDGE(material);
-      break;
-    case LRT_EDGE_FLAG_EDGE_MARK:
-      LRT_ASSIGN_EDGE(edge_mark);
-      break;
-    case LRT_EDGE_FLAG_INTERSECTION:
-      LRT_ASSIGN_EDGE(intersection);
-      break;
-    case LRT_EDGE_FLAG_LOOSE:
-      LRT_ASSIGN_EDGE(floating);
-      break;
+/* Note: For simplicity, this function doesn't actually do anything if you already have data in
+ * #pe.  */
+static void lineart_finalize_object_edge_array_reserve(LineartPendingEdges *pe, int count)
+{
+  if (pe->max || pe->array) {
+    return;
   }
-#undef LRT_ASSIGN_EDGE
+
+  pe->max = count;
+  LineartEdge **new_array = MEM_mallocN(sizeof(LineartEdge *) * pe->max,
+                                        "LineartPendingEdges array final");
+  pe->array = new_array;
 }
 
-static void lineart_finalize_object_edge_list(LineartRenderBuffer *rb, LineartObjectInfo *obi)
+static void lineart_finalize_object_edge_array(LineartPendingEdges *pe, LineartObjectInfo *obi)
 {
-#define LRT_OBI_TO_RB(name) \
-  if (obi->name.last) { \
-    ((LineartEdge *)obi->name.last)->next = rb->name.first; \
-    rb->name.first = obi->name.first; \
-  }
-  LRT_OBI_TO_RB(contour);
-  LRT_OBI_TO_RB(crease);
-  LRT_OBI_TO_RB(material);
-  LRT_OBI_TO_RB(edge_mark);
-  LRT_OBI_TO_RB(intersection);
-  LRT_OBI_TO_RB(floating);
-#undef LRT_OBI_TO_RB
+  memcpy(&pe->array[pe->next],
+         obi->pending_edges.array,
+         sizeof(LineartEdge *) * obi->pending_edges.next);
+  MEM_freeN(obi->pending_edges.array);
+  pe->next += obi->pending_edges.next;
 }
 
 static void lineart_triangle_adjacent_assign(LineartTriangle *tri,
@@ -2209,7 +2145,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend
       BLI_addtail(&la_edge->segments, la_seg);
       if (usage == OBJECT_LRT_INHERIT || usage == OBJECT_LRT_INCLUDE ||
           usage == OBJECT_LRT_NO_INTERSECTION) {
-        lineart_add_edge_to_list_thread(ob_info, la_edge);
+        lineart_add_edge_to_array_thread(ob_info, la_edge);
       }
 
       if (edge_added) {
@@ -2236,7 +2172,7 @@ static void lineart_geometry_object_load(LineartObjectInfo *ob_info, LineartRend
       BLI_addtail(&la_edge->segments, la_seg);
       if (usage == OBJECT_LRT_INHERIT || usage == OBJECT_LRT_INCLUDE ||
           usage == OBJECT_LRT_NO_INTERSECTION) {
-        lineart_add_edge_to_list_thread(ob_info, la_edge);
+        lineart_add_edge_to_array_thread(ob_info, la_edge);
       }
       la_edge++;
       la_seg++;
@@ -2551,6 +2487,17 @@ static void lineart_main_load_geometries(
    * lineart_triangle_share_edge() can work properly from the lack of triangle adjacent info. */
   int global_i = 0;
 
+  int edge_count = 0;
+  for (int i = 0; i < thread_count; i++) {
+    for (LineartObjectInfo *obi = olti[i].pending; obi; obi = obi->next) {
+      if (!obi->v_eln) {
+        continue;
+      }
+      edge_count += obi->pending_edges.next;
+    }
+  }
+  lineart_finalize_object_edge_array_reserve(&rb->pending_edges, edge_count);
+
   for (int i = 0; i < thread_count; i++) {
     for (LineartObjectInfo *obi = olti[i].pending; obi; obi = obi->next) {
       if (!obi->v_eln) {
@@ -2567,7 +2514,7 @@ static void lineart_main_load_geometries(
        * same numeric index to come close together. */
       obi->global_i_offset = global_i;
       global_i += v_count;
-      lineart_finalize_object_edge_list(rb, obi);
+      lineart_finalize_object_edge_array(&rb->pending_edges, obi);
     }
   }
 
@@ -3272,7 +3219,7 @@ static LineartEdge *lineart_triangle_intersect(LineartRenderBuffer *rb,
   result->flags = LRT_EDGE_FLAG_INTERSECTION;
   result->intersection_mask = (tri->intersection_mask | testing->intersection_mask);
 
-  lineart_prepend_edge_direct(&rb->intersection.first, result);
+  lineart_add_edge_to_array(&rb->pending_edges, result);
 
   return result;
 }
@@ -3360,13 +3307,6 @@ static void lineart_destroy_render_data(LineartRenderBuffer *rb)
     return;
   }
 
-  memset(&rb->contour, 0, sizeof(ListBase));
-  memset(&rb->crease, 0, sizeof(ListBase));
-  memset(&rb->intersection, 0, sizeof(ListBase));
-  memset(&rb->edge_mark, 0, sizeof(ListBase));
-  memset(&rb->material, 0, sizeof(ListBase));
-  memset(&rb->floating, 0, sizeof(ListBase));
-
   BLI_listbase_clear(&rb->chains);
   BLI_listbase_clear(&rb->wasted_cuts);
 
@@ -3378,6 +3318,10 @@ static void lineart_destroy_render_data(LineartRenderBuffer *rb)
   BLI_spin_end(&rb->lock_cuts);
   BLI_spin_end(&rb->render_data_pool.lock_mem);
 
+  if (rb->pending_edges.array) {
+    MEM_freeN(rb->pending_edges.array);
+  }
+
   lineart_mem_destroy(&rb->render_data_pool);
 }
 
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h b/source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h
index b1aa81322a8..1a197c8b4b7 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h
@@ -67,49 +67,11 @@ int lineart_count_intersection_segment_count(struct LineartRenderBuffer *rb);
 void lineart_count_and_print_render_buffer_memory(struct LineartRenderBuffer *rb);
 
 #define LRT_ITER_ALL_LINES_BEGIN \
-  LineartEdge *e, *next_e; \
-  void **current_head; \
-  e = rb->contour.first; \
-  if (!e) { \
-    e = rb->crease.first; \
-  } \
-  if (!e) { \
-    e = rb->material.first; \
-  } \
-  if (!e) { \
-    e = rb->edge_mark.first; \
-  } \
-  if (!e) { \
-    e = rb->intersection.first; \
-  } \
-  if (!e) { \
-    e = rb->floating.first; \
-  } \
-  for (current_head = &rb->contour.first; e; e = next_e) { \
-    next_e = e->next;
-
-#define LRT_ITER_ALL_LINES_NEXT \
-  while (!next_e) { \
-    if (current_head == &rb->contour.first) { \
-      current_head = &rb->crease.first; \
-    } \
-    else if (current_head == &rb->crease.first) { \
-      current_head = &rb->material.first; \
-    } \
-    else if (current_head == &rb->material.first) { \
-      current_head = &rb->edge_mark.first; \
-    } \
-    else if (current_head == &rb->edge_mark.first) { \
-      current_head = &rb->intersection.first; \
-    } \
-    else if (current_head == &rb->intersection.first) { \
-      current_head = &rb->floating.first; \
-    } \
-    else { \
-      break; \
-    } \
-    next_e = *current_head; \
-  }
+  LineartEdge *e; \
+  for (int i = 0; i < rb->pending_edges.next; i++) { \
+    e = rb->pending_edges.array[i];
+
+#define LRT_ITER_ALL_LINES_NEXT ; /* Doesn't do anything now with new array setup. */
 
 #define LRT_ITER_ALL_LINES_END \
   LRT_ITER_ALL_LINES_NEXT \