[Bf-blender-cvs] [cf365828d85] lanpr-under-gp: LineArt: double point chaining algorithm

[YimingWu]

Commit: cf365828d8595f6ea465ab0c198037b7930300a2
Author: YimingWu
Date:   Sat Jul 25 17:56:54 2020 +0800
Branches: lanpr-under-gp
https://developer.blender.org/rBcf365828d8595f6ea465ab0c198037b7930300a2

LineArt: double point chaining algorithm

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

M	source/blender/editors/lineart/lineart_chain.c

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

diff --git a/source/blender/editors/lineart/lineart_chain.c b/source/blender/editors/lineart/lineart_chain.c
index 6c6d8e27927..b5e38fe3873 100644
--- a/source/blender/editors/lineart/lineart_chain.c
+++ b/source/blender/editors/lineart/lineart_chain.c
@@ -679,8 +679,8 @@ LineartChainRegisterEntry *lineart_chain_get_closest_cre(LineartRenderBuffer *rb
         continue;
       }
     }
-    if (cre->rlc->picked) {
-      BLI_remlink(&ba->linked_chains, cre);
+    if (cre->rlc->picked || cre->picked) {
+      // BLI_remlink(&ba->linked_chains, cre);
       continue;
     }
     if (cre->rlc == rlc || (!cre->rlc->chain.first) || (cre->rlc->level != occlusion)) {
@@ -718,12 +718,12 @@ LineartChainRegisterEntry *lineart_chain_get_closest_cre(LineartRenderBuffer *rb
 void ED_lineart_chain_connect(LineartRenderBuffer *rb, const int do_geometry_space)
 {
   LineartRenderLineChain *rlc;
-  LineartRenderLineChainItem *rlci, *rlci_guard;
-  LineartBoundingArea *ba, *ba_guard;
-  LineartChainRegisterEntry *closest_cre_l, *closest_cre_r;
+  LineartRenderLineChainItem *rlci_l, *rlci_r;
+  LineartBoundingArea *ba_l, *ba_r;
+  LineartChainRegisterEntry *closest_cre_l, *closest_cre_r, *closest_cre;
   float dist = do_geometry_space ? rb->chaining_geometry_threshold : rb->chaining_image_threshold;
-  float new_len;
-  int occlusion;
+  float dist_l, dist_r;
+  int occlusion, reverse_main;
   ListBase swap = {0};
 
   if ((!do_geometry_space && rb->chaining_image_threshold < 0.0001) ||
@@ -743,79 +743,51 @@ void ED_lineart_chain_connect(LineartRenderBuffer *rb, const int do_geometry_spa
     }
     BLI_addtail(&rb->chains, rlc);
 
-    rlc->picked = 1;
-
     occlusion = ((LineartRenderLineChainItem *)rlc->chain.first)->occlusion;
 
-    rlci = rlc->chain.last;
-    rlci_guard = rlc->chain.first;
-    if (rlci_guard) {
-      ba_guard = lineart_bounding_area_get_end_point(rb, rlci_guard);
-    }
-    while (rlci && ((ba = lineart_bounding_area_get_end_point(rb, rlci)) != NULL)) {
-      closest_cre_l = NULL;
-      if (ba->linked_chains.first == NULL) {
-        break;
-      }
+    rlci_l = rlc->chain.first;
+    rlci_r = rlc->chain.last;
+    while ((ba_l = lineart_bounding_area_get_end_point(rb, rlci_l)) &&
+           (ba_r = lineart_bounding_area_get_end_point(rb, rlci_r))) {
       closest_cre_l = lineart_chain_get_closest_cre(
-          rb, ba, rlc, rlci, occlusion, dist, do_geometry_space, &new_len);
-      if (closest_cre_l) {
-        if (ba_guard == ba) {
-          /* Technically shouldn't do bounding areas here, but the looping bug can only possibly
-           * occur when ba_guard==ba*/
-          /* Todo in the future: robust chaining with near-bounding area implementation would get
-           * rid of this hack */
-          float guard_len = do_geometry_space ?
-                                len_v3v3(rlci_guard->gpos, closest_cre_l->rlci->gpos) :
-                                len_v2v2(rlci_guard->pos, closest_cre_l->rlci->pos);
-          if (guard_len < new_len) {
-            /* The point is actually closet to the other end of this line, thus do not chain right
-             * now. */
-            break;
-          }
-        }
-        closest_cre_l->picked = 1;
-        closest_cre_l->rlc->picked = 1;
-        BLI_remlink(&ba->linked_chains, closest_cre_l);
-        if (closest_cre_l->is_left) {
-          lineart_chain_connect(rb, rlc, closest_cre_l->rlc, 0, 0);
+          rb, ba_l, rlc, rlci_l, occlusion, dist, do_geometry_space, &dist_l);
+      closest_cre_r = lineart_chain_get_closest_cre(
+          rb, ba_r, rlc, rlci_r, occlusion, dist, do_geometry_space, &dist_r);
+      if (closest_cre_l && closest_cre_r) {
+        if (dist_l < dist_r) {
+          closest_cre = closest_cre_l;
+          reverse_main = 1;
         }
         else {
-          lineart_chain_connect(rb, rlc, closest_cre_l->rlc, 0, 1);
+          closest_cre = closest_cre_r;
+          reverse_main = 0;
         }
-        BLI_remlink(&swap, closest_cre_l->rlc);
       }
-      else {
-        break;
+      else if (closest_cre_l) {
+        closest_cre = closest_cre_l;
+        reverse_main = 1;
       }
-      rlci = rlc->chain.last;
-    }
-
-    rlci = rlc->chain.first;
-    while (rlci && ((ba = lineart_bounding_area_get_end_point(rb, rlci)) != NULL)) {
-      closest_cre_r = NULL;
-      if (ba->linked_chains.first == NULL) {
+      else if (closest_cre_r) {
+        closest_cre = closest_cre_r;
+        BLI_remlink(&ba_r->linked_chains, closest_cre_r);
+        reverse_main = 0;
+      }
+      else {
         break;
       }
-      closest_cre_r = lineart_chain_get_closest_cre(
-          rb, ba, rlc, rlci, occlusion, dist, do_geometry_space, NULL);
-      if (closest_cre_r) {
-        closest_cre_r->picked = 1;
-        closest_cre_r->rlc->picked = 1;
-        BLI_remlink(&ba->linked_chains, closest_cre_r);
-        if (closest_cre_r->is_left) {
-          lineart_chain_connect(rb, rlc, closest_cre_r->rlc, 1, 0);
-        }
-        else {
-          lineart_chain_connect(rb, rlc, closest_cre_r->rlc, 1, 1);
-        }
-        BLI_remlink(&swap, closest_cre_r->rlc);
+      closest_cre->picked = 1;
+      closest_cre->rlc->picked = 1;
+      if (closest_cre->is_left) {
+        lineart_chain_connect(rb, rlc, closest_cre->rlc, reverse_main, 0);
       }
       else {
-        break;
+        lineart_chain_connect(rb, rlc, closest_cre->rlc, reverse_main, 1);
       }
-      rlci = rlc->chain.first;
+      BLI_remlink(&swap, closest_cre->rlc);
+      rlci_l = rlc->chain.first;
+      rlci_r = rlc->chain.last;
     }
+    rlc->picked = 1;
   }
 }