[Bf-blender-cvs] [d336e4d9b23] temp-lineart-contained: LineArt: Use array for ba->linked_triangles.

[YimingWu]

Commit: d336e4d9b23be9337e4ca2a72f6637a0b144f50c
Author: YimingWu
Date:   Wed Apr 21 13:51:15 2021 +0800
Branches: temp-lineart-contained
https://developer.blender.org/rBd336e4d9b23be9337e4ca2a72f6637a0b144f50c

LineArt: Use array for ba->linked_triangles.

===================================================================

M	source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
M	source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c

===================================================================

diff --git a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
index 72e3fd2b8e4..4825e4e8cfa 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
+++ b/source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h
@@ -443,8 +443,11 @@ typedef struct LineartBoundingArea {
   ListBase bp;
 
   short triangle_count;
+  short max_triangle_count;
+
+  /* Use array for speeding up multiple accesses. */
+  struct LineartTriangle **linked_triangles;
 
-  ListBase linked_triangles;
   ListBase linked_lines;
 
   /** Reserved for image space reduction && multi-thread chaining. */
diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
index 1f2195925ef..083c8681263 100644
--- a/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_cpu.c
@@ -317,6 +317,20 @@ BLI_INLINE bool lineart_occlusion_is_adjacent_intersection(LineartEdge *e, Linea
           (v2->base.flag && v2->intersecting_with == rt));
 }
 
+static void lineart_bounding_area_triangle_add(LineartRenderBuffer *rb,
+                                               LineartBoundingArea *ba,
+                                               LineartTriangle *rt)
+{
+  if (ba->triangle_count >= ba->max_triangle_count) {
+    LineartTriangle **new_array = lineart_mem_aquire(
+        &rb->render_data_pool, sizeof(LineartTriangle *) * ba->max_triangle_count * 2);
+    memcpy(new_array, ba->linked_triangles, ba->max_triangle_count);
+    ba->max_triangle_count *= 2;
+  }
+  ba->linked_triangles[ba->triangle_count] = rt;
+  ba->triangle_count++;
+}
+
 static void lineart_occlusion_single_line(LineartRenderBuffer *rb, LineartEdge *e, int thread_id)
 {
   double x = e->v1->fbcoord[0], y = e->v1->fbcoord[1];
@@ -337,8 +351,8 @@ static void lineart_occlusion_single_line(LineartRenderBuffer *rb, LineartEdge *
 
   while (nba) {
 
-    LISTBASE_FOREACH (LinkData *, lip, &nba->linked_triangles) {
-      rt = lip->data;
+    for (int i = 0; i < nba->triangle_count; i++) {
+      rt = (LineartTriangleThread *)nba->linked_triangles[i];
       /* If we are already testing the line in this thread, then don't do it. */
       if (rt->testing_e[thread_id] == e || (rt->base.flags & LRT_TRIANGLE_INTERSECTION_ONLY) ||
           lineart_occlusion_is_adjacent_intersection(e, (LineartTriangle *)rt)) {
@@ -2684,7 +2698,6 @@ static void lineart_triangle_intersect_in_bounding_area(LineartRenderBuffer *rb,
    * See definition of LineartTriangleThread for more info. */
   LineartTriangle *testing_triangle;
   LineartTriangleThread *rtt;
-  LinkData *lip, *next_lip;
 
   double *G0 = rt->v[0]->gloc, *G1 = rt->v[1]->gloc, *G2 = rt->v[2]->gloc;
 
@@ -2698,9 +2711,8 @@ static void lineart_triangle_intersect_in_bounding_area(LineartRenderBuffer *rb,
   }
 
   /* If this _is_ the smallest subdiv bounding area, then do the intersections there. */
-  for (lip = ba->linked_triangles.first; lip; lip = next_lip) {
-    next_lip = lip->next;
-    testing_triangle = lip->data;
+  for (int i = 0; i < ba->triangle_count; i++) {
+    testing_triangle = ba->linked_triangles[i];
     rtt = (LineartTriangleThread *)testing_triangle;
 
     if (testing_triangle == rt || rtt->testing_e[0] == (LineartEdge *)rt) {
@@ -2917,6 +2929,11 @@ static void lineart_main_bounding_area_make_initial(LineartRenderBuffer *rb)
       ba->cx = (ba->l + ba->r) / 2;
       ba->cy = (ba->u + ba->b) / 2;
 
+      /* Init linked_triangles array. */
+      ba->max_triangle_count = LRT_TILE_SPLITTING_TRIANGLE_LIMIT;
+      ba->linked_triangles = lineart_mem_aquire(
+          &rb->render_data_pool, sizeof(LineartTriangle *) * LRT_TILE_SPLITTING_TRIANGLE_LIMIT);
+
       /* Link adjacent ones. */
       if (row) {
         lineart_list_append_pointer_pool(
@@ -3131,7 +3148,15 @@ static void lineart_bounding_area_split(LineartRenderBuffer *rb,
 
   lineart_bounding_areas_connect_new(rb, root);
 
-  while ((rt = lineart_list_pop_pointer_no_free(&root->linked_triangles)) != NULL) {
+  /* Init linked_triangles array. */
+  for (int i = 0; i < 4; i++) {
+    ba[i].max_triangle_count = LRT_TILE_SPLITTING_TRIANGLE_LIMIT;
+    ba[i].linked_triangles = lineart_mem_aquire(
+        &rb->render_data_pool, sizeof(LineartTriangle *) * LRT_TILE_SPLITTING_TRIANGLE_LIMIT);
+  }
+
+  for (int i = 0; i < root->triangle_count; i++) {
+    rt = root->linked_triangles[i];
     LineartBoundingArea *cba = root->child;
     double b[4];
     b[0] = MIN3(rt->v[0]->fbcoord[0], rt->v[1]->fbcoord[0], rt->v[2]->fbcoord[0]);
@@ -3252,13 +3277,12 @@ static void lineart_bounding_area_link_triangle(LineartRenderBuffer *rb,
     return;
   }
   if (root_ba->child == NULL) {
-    lineart_list_append_pointer_pool(&root_ba->linked_triangles, &rb->render_data_pool, rt);
-    root_ba->triangle_count++;
+    lineart_bounding_area_triangle_add(rb, root_ba, rt);
     /* If splitting doesn't improve triangle separation, then shouldn't allow splitting anymore.
      * Here we use recursive limit. This is especially useful in orthographic render,
      * where a lot of faces could easily line up perfectly in image space,
      * which can not be separated by simply slicing the image tile. */
-    if (root_ba->triangle_count > LRT_TILE_SPLITTING_TRIANGLE_LIMIT && recursive &&
+    if (root_ba->triangle_count >= LRT_TILE_SPLITTING_TRIANGLE_LIMIT && recursive &&
         recursive_level < rb->tile_recursive_level) {
       lineart_bounding_area_split(rb, root_ba, recursive_level);
     }