LineArt: Object loading optimization

This patch replaces BMesh conversion into index-based triangle adjacent
lookup method, and use multithread in many steps to speed up object
loading for line art.

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

Reviewed By: Sebastian Parborg (zeddb)

source/blender/gpencil_modifiers/CMakeLists.txt

@@ -68,12 +68,29 @@ set(SRC
   intern/lineart/lineart_cpu.c
   intern/lineart/lineart_ops.c
   intern/lineart/lineart_util.c
+  intern/lineart/lineart_cpp_bridge.cpp
 
   intern/lineart/MOD_lineart.h
   intern/lineart/lineart_intern.h
 
 )
 
+if(WITH_TBB)
+add_definitions(-DWITH_TBB)
+if(WIN32)
+  # TBB includes Windows.h which will define min/max macros
+  # that will collide with the stl versions.
+  add_definitions(-DNOMINMAX)
+endif()
+list(APPEND INC_SYS
+  ${TBB_INCLUDE_DIRS}
+)
+
+list(APPEND LIB
+  ${TBB_LIBRARIES}
+)
+endif()
+
 set(LIB
 )
 

source/blender/gpencil_modifiers/intern/MOD_gpencillineart.c

@@ -387,7 +387,6 @@ static void options_panel_draw(const bContext *UNUSED(C), Panel *panel)
 
   uiLayout *col = uiLayoutColumn(layout, true);
 
-  uiItemR(col, ptr, "use_remove_doubles", 0, NULL, ICON_NONE);
   uiItemR(col, ptr, "use_edge_overlap", 0, IFACE_("Overlapping Edges As Contour"), ICON_NONE);
   uiItemR(col, ptr, "use_object_instances", 0, NULL, ICON_NONE);
   uiItemR(col, ptr, "use_clip_plane_boundaries", 0, NULL, ICON_NONE);

source/blender/gpencil_modifiers/intern/lineart/MOD_lineart.h

@@ -132,7 +132,7 @@ typedef struct LineartEdge {
   char min_occ;
 
   /** Also for line type determination on chaining. */
-  unsigned char flags;
+  uint16_t flags;
   unsigned char intersection_mask;
 
   /**
@@ -171,7 +171,7 @@ typedef struct LineartEdgeChainItem {
   /** For restoring position to 3d space. */
   float gpos[3];
   float normal[3];
-  unsigned char line_type;
+  uint16_t line_type;
   char occlusion;
   unsigned char material_mask_bits;
   unsigned char intersection_mask;
@@ -189,6 +189,12 @@ typedef struct LineartChainRegisterEntry {
   char is_left;
 } LineartChainRegisterEntry;
 
+typedef struct LineartAdjacentEdge {
+  unsigned int v1;
+  unsigned int v2;
+  unsigned int e;
+} LineartAdjacentEdge;
+
 enum eLineArtTileRecursiveLimit {
   /* If tile gets this small, it's already much smaller than a pixel. No need to continue
    * splitting. */
@@ -396,7 +402,7 @@ typedef struct LineartObjectInfo {
 
 typedef struct LineartObjectLoadTaskInfo {
   struct LineartRenderBuffer *rb;
-  struct Depsgraph *dg;
+  int thread_id;
   /* LinkNode styled list */
   LineartObjectInfo *pending;
   /* Used to spread the load across several threads. This can not overflow. */

source/blender/gpencil_modifiers/intern/lineart/lineart_cpp_bridge.cpp

@@ -0,0 +1,19 @@
+#include "BLI_sort.hh"
+#include "BLI_vector.hh"
+#include "MOD_lineart.h"
+#include "lineart_intern.h"
+
+static bool cmp_adjacent_items(const LineartAdjacentEdge &p1, const LineartAdjacentEdge &p2)
+{
+  int a = p1.v1 - p2.v1;
+  int b = p1.v2 - p2.v2;
+  /* parallel_sort() requires cmp() to return true when the first element needs to appear before
+   * the second element in the sorted array, false otherwise (strict weak ordering), see
+   * https://en.cppreference.com/w/cpp/named_req/Compare. */
+  return a < 0 ? true : (a == 0 ? b < 0 : false);
+}
+
+void lineart_sort_adjacent_items(LineartAdjacentEdge *ai, int length)
+{
+  blender::parallel_sort(ai, ai + length - 1, cmp_adjacent_items);
+}

source/blender/gpencil_modifiers/intern/lineart/lineart_intern.h

@@ -121,3 +121,13 @@ void lineart_count_and_print_render_buffer_memory(struct LineartRenderBuffer *rb
 /* Initial bounding area row/column count, setting 4 is the simplest way algorithm could function
  * efficiently. */
 #define LRT_BA_ROWS 4
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void lineart_sort_adjacent_items(LineartAdjacentEdge *ai, int length);
+
+#ifdef __cplusplus
+}
+#endif

source/blender/makesdna/DNA_lineart_types.h

@@ -21,7 +21,7 @@ typedef enum eLineartMainFlags {
   LRT_ALLOW_DUPLI_OBJECTS = (1 << 2),
   LRT_ALLOW_OVERLAPPING_EDGES = (1 << 3),
   LRT_ALLOW_CLIPPING_BOUNDARIES = (1 << 4),
-  LRT_REMOVE_DOUBLES = (1 << 5),
+  /* LRT_REMOVE_DOUBLES = (1 << 5), Deprecated */
   LRT_LOOSE_AS_CONTOUR = (1 << 6),
   LRT_GPENCIL_INVERT_SOURCE_VGROUP = (1 << 7),
   LRT_GPENCIL_MATCH_OUTPUT_VGROUP = (1 << 8),
@@ -47,9 +47,16 @@ typedef enum eLineartEdgeFlag {
   LRT_EDGE_FLAG_MATERIAL = (1 << 3),
   LRT_EDGE_FLAG_INTERSECTION = (1 << 4),
   LRT_EDGE_FLAG_LOOSE = (1 << 5),
-  LRT_EDGE_FLAG_CHAIN_PICKED = (1 << 6),
-  LRT_EDGE_FLAG_CLIPPED = (1 << 7),
-  /** Limited to 8 bits, DON'T ADD ANYMORE until improvements on the data structure. */
+  /* LRT_EDGE_FLAG_FOR_FUTURE = (1 << 7), */
+  /* Limited to 8 bits for edge type flag, don't add anymore because BMEdge->head.eflag only has 8
+     bits. So unless we changed this into a non-single-bit flag thing, we keep it this way. */
+  /** Also used as discarded line mark. */
+  LRT_EDGE_FLAG_CHAIN_PICKED = (1 << 8),
+  LRT_EDGE_FLAG_CLIPPED = (1 << 9),
+  /** Limited to 16 bits for the entire thing. */
+
+  /** For object loading code to use only. */
+  LRT_EDGE_FLAG_INHIBIT = (1 << 14),
 } eLineartEdgeFlag;
 
 #define LRT_EDGE_FLAG_ALL_TYPE 0x3f

source/blender/makesrna/intern/rna_gpencil_modifier.c

@@ -3270,12 +3270,6 @@ static void rna_def_modifier_gpencillineart(BlenderRNA *brna)
   RNA_def_property_range(prop, 0.0f, 30.0f);
   RNA_def_property_update(prop, NC_SCENE, "rna_GpencilModifier_update");
 
-  prop = RNA_def_property(srna, "use_remove_doubles", PROP_BOOLEAN, PROP_NONE);
-  RNA_def_property_boolean_sdna(prop, NULL, "calculation_flags", LRT_REMOVE_DOUBLES);
-  RNA_def_property_ui_text(
-      prop, "Remove Doubles", "Remove doubles from the source geometry before generating stokes");
-  RNA_def_property_update(prop, NC_SCENE, "rna_GpencilModifier_update");
-
   prop = RNA_def_property(srna, "use_loose_as_contour", PROP_BOOLEAN, PROP_NONE);
   RNA_def_property_boolean_sdna(prop, NULL, "calculation_flags", LRT_LOOSE_AS_CONTOUR);
   RNA_def_property_ui_text(prop, "Loose As Contour", "Loose edges will have contour type");