Grease Pencil: Add LineArt modifier

This adds the LineArt grease pencil modifier.

It takes objects or collections as input and generates various grease
pencil lines from these objects with the help of the active scene
camera. For example it can generate contour lines, intersection lines
and crease lines to name a few.

This is really useful as artists can then use 3D meshes to automatically
generate grease pencil lines for characters, enviroments or other
visualization purposes.

These lines can then be baked and edited as regular grease pencil lines.

Reviewed By: Sebastian Parborg, Antonio Vazquez, Matias Mendiola

Differential Revision: http://developer.blender.org/D8758

1 files changed, 980 insertions, 0 deletions

diff --git a/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c b/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c
new file mode 100644
index 00000000000..36115fa1027
--- /dev/null
+++ b/source/blender/gpencil_modifiers/intern/lineart/lineart_chain.c
@@ -0,0 +1,980 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2019 Blender Foundation.
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup editors
+ */
+
+#include "BLI_linklist.h"
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+
+#include "BKE_customdata.h"
+#include "BKE_object.h"
+
+#include "DEG_depsgraph_query.h"
+
+#include "DNA_camera_types.h"
+#include "DNA_lineart_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_scene_types.h"
+
+#include "MOD_lineart.h"
+
+#include "bmesh.h"
+
+#include "lineart_intern.h"
+
+#include <math.h>
+
+#define LRT_OTHER_RV(rl, rv) ((rv) == (rl)->l ? (rl)->r : ((rv) == (rl)->r ? (rl)->l : NULL))
+
+/* Get a connected line, only for lines who has the exact given vert, or (in the case of
+ * intersection lines) who has a vert that has the exact same position. */
+static LineartRenderLine *lineart_line_get_connected(LineartBoundingArea *ba,
+                                                     LineartRenderVert *rv,
+                                                     LineartRenderVert **new_rv,
+                                                     int match_flag)
+{
+  LISTBASE_FOREACH (LinkData *, lip, &ba->linked_lines) {
+    LineartRenderLine *nrl = lip->data;
+
+    if ((!(nrl->flags & LRT_EDGE_FLAG_ALL_TYPE)) || (nrl->flags & LRT_EDGE_FLAG_CHAIN_PICKED)) {
+      continue;
+    }
+
+    if (match_flag && ((nrl->flags & LRT_EDGE_FLAG_ALL_TYPE) & match_flag) == 0) {
+      continue;
+    }
+
+    *new_rv = LRT_OTHER_RV(nrl, rv);
+    if (*new_rv) {
+      return nrl;
+    }
+
+    if (nrl->flags & LRT_EDGE_FLAG_INTERSECTION) {
+      if (rv->fbcoord[0] == nrl->l->fbcoord[0] && rv->fbcoord[1] == nrl->l->fbcoord[1]) {
+        *new_rv = LRT_OTHER_RV(nrl, nrl->l);
+        return nrl;
+      }
+      if (rv->fbcoord[0] == nrl->r->fbcoord[0] && rv->fbcoord[1] == nrl->r->fbcoord[1]) {
+        *new_rv = LRT_OTHER_RV(nrl, nrl->r);
+        return nrl;
+      }
+    }
+  }
+
+  return NULL;
+}
+
+static LineartRenderLineChain *lineart_chain_create(LineartRenderBuffer *rb)
+{
+  LineartRenderLineChain *rlc;
+  rlc = lineart_mem_aquire(&rb->render_data_pool, sizeof(LineartRenderLineChain));
+
+  BLI_addtail(&rb->chains, rlc);
+
+  return rlc;
+}
+
+static bool lineart_point_overlapping(LineartRenderLineChainItem *rlci,
+                                      float x,
+                                      float y,
+                                      double threshold)
+{
+  if (!rlci) {
+    return false;
+  }
+  if (((rlci->pos[0] + threshold) >= x) && ((rlci->pos[0] - threshold) <= x) &&
+      ((rlci->pos[1] + threshold) >= y) && ((rlci->pos[1] - threshold) <= y)) {
+    return true;
+  }
+  return false;
+}
+
+static LineartRenderLineChainItem *lineart_chain_append_point(LineartRenderBuffer *rb,
+                                                              LineartRenderLineChain *rlc,
+                                                              float *fbcoord,
+                                                              float *gpos,
+                                                              float *normal,
+                                                              char type,
+                                                              int level,
+                                                              unsigned char transparency_mask,
+                                                              size_t index)
+{
+  LineartRenderLineChainItem *rlci;
+
+  if (lineart_point_overlapping(rlc->chain.last, fbcoord[0], fbcoord[1], 1e-5)) {
+    /* Because the new chain point is overlapping, just replace the type and occlusion level of the
+     * current point. This makes it so that the line to the point after this one has the correct
+     * type and level. */
+    LineartRenderLineChainItem *old_rlci = rlc->chain.last;
+    old_rlci->line_type = type;
+    old_rlci->occlusion = level;
+    return old_rlci;
+  }
+
+  rlci = lineart_mem_aquire(&rb->render_data_pool, sizeof(LineartRenderLineChainItem));
+
+  copy_v2_v2(rlci->pos, fbcoord);
+  copy_v3_v3(rlci->gpos, gpos);
+  rlci->index = index;
+  copy_v3_v3(rlci->normal, normal);
+  rlci->line_type = type & LRT_EDGE_FLAG_ALL_TYPE;
+  rlci->occlusion = level;
+  rlci->transparency_mask = transparency_mask;
+  BLI_addtail(&rlc->chain, rlci);
+
+  return rlci;
+}
+
+static LineartRenderLineChainItem *lineart_chain_prepend_point(LineartRenderBuffer *rb,
+                                                               LineartRenderLineChain *rlc,
+                                                               float *fbcoord,
+                                                               float *gpos,
+                                                               float *normal,
+                                                               char type,
+                                                               int level,
+                                                               unsigned char transparency_mask,
+                                                               size_t index)
+{
+  LineartRenderLineChainItem *rlci;
+
+  if (lineart_point_overlapping(rlc->chain.first, fbcoord[0], fbcoord[1], 1e-5)) {
+    return rlc->chain.first;
+  }
+
+  rlci = lineart_mem_aquire(&rb->render_data_pool, sizeof(LineartRenderLineChainItem));
+
+  copy_v2_v2(rlci->pos, fbcoord);
+  copy_v3_v3(rlci->gpos, gpos);
+  rlci->index = index;
+  copy_v3_v3(rlci->normal, normal);
+  rlci->line_type = type & LRT_EDGE_FLAG_ALL_TYPE;
+  rlci->occlusion = level;
+  rlci->transparency_mask = transparency_mask;
+  BLI_addhead(&rlc->chain, rlci);
+
+  return rlci;
+}
+
+void MOD_lineart_chain_feature_lines(LineartRenderBuffer *rb)
+{
+  LineartRenderLineChain *rlc;
+  LineartRenderLineChainItem *rlci;
+  LineartBoundingArea *ba;
+  LineartRenderLineSegment *rls;
+  int last_occlusion;
+  unsigned char last_transparency;
+  /* Used when converting from double. */
+  float use_fbcoord[2];
+  float use_gpos[3];
+
+#define VERT_COORD_TO_FLOAT(a) \
+  copy_v2fl_v2db(use_fbcoord, (a)->fbcoord); \
+  copy_v3fl_v3db(use_gpos, (a)->gloc);
+
+#define POS_TO_FLOAT(lpos, gpos) \
+  copy_v2fl_v2db(use_fbcoord, lpos); \
+  copy_v3fl_v3db(use_gpos, gpos);
+
+  LRT_ITER_ALL_LINES_BEGIN
+  {
+    if ((!(rl->flags & LRT_EDGE_FLAG_ALL_TYPE)) || (rl->flags & LRT_EDGE_FLAG_CHAIN_PICKED)) {
+      LRT_ITER_ALL_LINES_NEXT
+      continue;
+    }
+
+    rl->flags |= LRT_EDGE_FLAG_CHAIN_PICKED;
+
+    rlc = lineart_chain_create(rb);
+
+    /* One chain can only have one object_ref,
+     * so we assign it based on the first segment we found. */
+    rlc->object_ref = rl->object_ref;
+
+    LineartRenderLine *new_rl = rl;
+    LineartRenderVert *new_rv;
+    float N[3] = {0};
+
+    if (rl->tl) {
+      N[0] += rl->tl->gn[0];
+      N[1] += rl->tl->gn[1];
+      N[2] += rl->tl->gn[2];
+    }
+    if (rl->tr) {
+      N[0] += rl->tr->gn[0];
+      N[1] += rl->tr->gn[1];
+      N[2] += rl->tr->gn[2];
+    }
+    if (rl->tl || rl->tr) {
+      normalize_v3(N);
+    }
+
+    /*  Step 1: grow left. */
+    ba = MOD_lineart_get_bounding_area(rb, rl->l->fbcoord[0], rl->l->fbcoord[1]);
+    new_rv = rl->l;
+    rls = rl->segments.first;
+    VERT_COORD_TO_FLOAT(new_rv);
+    lineart_chain_prepend_point(rb,
+                                rlc,
+                                use_fbcoord,
+                                use_gpos,
+                                N,
+                                rl->flags,
+                                rls->occlusion,
+                                rls->transparency_mask,
+                                rl->l_obindex);
+    while (ba && (new_rl = lineart_line_get_connected(ba, new_rv, &new_rv, rl->flags))) {
+      new_rl->flags |= LRT_EDGE_FLAG_CHAIN_PICKED;
+
+      if (new_rl->tl || new_rl->tr) {
+        zero_v3(N);
+        if (new_rl->tl) {
+          N[0] += new_rl->tl->gn[0];
+          N[1] += new_rl->tl->gn[1];
+          N[2] += new_rl->tl->gn[2];
+        }
+        if (new_rl->tr) {
+          N[0] += new_rl->tr->gn[0];
+          N[1] += new_rl->tr->gn[1];
+          N[2] += new_rl->tr->gn[2];
+        }
+        normalize_v3(N);
+      }
+
+      if (new_rv == new_rl->l) {
+        for (rls = new_rl->segments.last; rls; rls = rls->prev) {
+          double gpos[3], lpos[3];
+          double *lfb = new_rl->l->fbcoord, *rfb = new_rl->r->fbcoord;
+          double global_at = lfb[3] * rls->at / (rls->at * lfb[3] + (1 - rls->at) * rfb[3]);
+          interp_v3_v3v3_db(lpos, new_rl->l->fbcoord, new_rl->r->fbcoord, rls->at);
+          interp_v3_v3v3_db(gpos, new_rl->l->gloc, new_rl->r->gloc, global_at);
+          POS_TO_FLOAT(lpos, gpos)
+          lineart_chain_prepend_point(rb,
+                                      rlc,
+                                      use_fbcoord,
+                                      use_gpos,
+                                      N,
+                                      new_rl->flags,
+                                      rls->occlusion,
+                                      rls->transparency_mask,
+                                      new_rl->l_obindex);
+          last_occlusion = rls->occlusion;
+          last_transparency = rls->transparency_mask;
+        }
+      }
+      else if (new_rv == new_rl->r) {
+        rls = new_rl->segments.first;
+        last_occlusion = rls->occlusion;
+        last_transparency = rls->transparency_mask;
+        rls = rls->next;
+        for (; rls; rls = rls->next) {
+          double gpos[3], lpos[3];
+          double *lfb = new_rl->l->fbcoord, *rfb = new_rl->r->fbcoord;
+          double global_at = lfb[3] * rls->at / (rls->at * lfb[3] + (1 - rls->at) * rfb[3]);
+          interp_v3_v3v3_db(lpos, new_rl->l->fbcoord, new_rl->r->fbcoord, rls->at);
+          interp_v3_v3v3_db(gpos, new_rl->l->gloc, new_rl->r->gloc, global_at);
+          POS_TO_FLOAT(lpos, gpos)
+          lineart_chain_prepend_point(rb,
+                                      rlc,
+                                      use_fbcoord,
+                                      use_gpos,
+                                      N,
+                                      new_rl->flags,
+                                      last_occlusion,
+                                      last_transparency,
+                                      new_rl->r_obindex);
+          last_occlusion = rls->occlusion;
+          last_transparency = rls->transparency_mask;
+        }
+        VERT_COORD_TO_FLOAT(new_rl->r);
+        lineart_chain_prepend_point(rb,
+                                    rlc,
+                                    use_fbcoord,
+                                    use_gpos,
+                                    N,
+                                    new_rl->flags,
+                                    last_occlusion,
+                                    last_transparency,
+                                    new_rl->r_obindex);
+      }
+      ba = MOD_lineart_get_bounding_area(rb, new_rv->fbcoord[0], new_rv->fbcoord[1]);
+    }
+
+    /* Restore normal value. */
+    if (rl->tl || rl->tr) {
+      zero_v3(N);
+      if (rl->tl) {
+        N[0] += rl->tl->gn[0];
+        N[1] += rl->tl->gn[1];
+        N[2] += rl->tl->gn[2];
+      }
+      if (rl->tr) {
+        N[0] += rl->tr->gn[0];
+        N[1] += rl->tr->gn[1];
+        N[2] += rl->tr->gn[2];
+      }
+      normalize_v3(N);
+    }
+    /*  Step 2: Adding all cuts from the given line, so we can continue connecting the right side
+     * of the line. */
+    rls = rl->segments.first;
+    last_occlusion = ((LineartRenderLineSegment *)rls)->occlusion;
+    last_transparency = ((LineartRenderLineSegment *)rls)->transparency_mask;
+    for (rls = rls->next; rls; rls = rls->next) {
+      double gpos[3], lpos[3];
+      double *lfb = rl->l->fbcoord, *rfb = rl->r->fbcoord;
+      double global_at = lfb[3] * rls->at / (rls->at * lfb[3] + (1 - rls->at) * rfb[3]);
+      interp_v3_v3v3_db(lpos, rl->l->fbcoord, rl->r->fbcoord, rls->at);
+      interp_v3_v3v3_db(gpos, rl->l->gloc, rl->r->gloc, global_at);
+      POS_TO_FLOAT(lpos, gpos)
+      lineart_chain_append_point(rb,
+                                 rlc,
+                                 use_fbcoord,
+                                 use_gpos,
+                                 N,
+                                 rl->flags,
+                                 rls->occlusion,
+                                 rls->transparency_mask,
+                                 rl->l_obindex);
+      last_occlusion = rls->occlusion;
+    }
+    VERT_COORD_TO_FLOAT(rl->r)
+    lineart_chain_append_point(rb,
+                               rlc,
+                               use_fbcoord,
+                               use_gpos,
+                               N,
+                               rl->flags,
+                               last_occlusion,
+                               last_transparency,
+                               rl->r_obindex);
+
+    /*  Step 3: grow right. */
+    ba = MOD_lineart_get_bounding_area(rb, rl->r->fbcoord[0], rl->r->fbcoord[1]);
+    new_rv = rl->r;
+    while (ba && (new_rl = lineart_line_get_connected(ba, new_rv, &new_rv, rl->flags))) {
+      new_rl->flags |= LRT_EDGE_FLAG_CHAIN_PICKED;
+
+      if (new_rl->tl || new_rl->tr) {
+        zero_v3(N);
+        if (new_rl->tl) {
+          N[0] += new_rl->tl->gn[0];
+          N[1] += new_rl->tl->gn[1];
+          N[2] += new_rl->tl->gn[2];
+        }
+        if (new_rl->tr) {
+          N[0] += new_rl->tr->gn[0];
+          N[1] += new_rl->tr->gn[1];
+          N[2] += new_rl->tr->gn[2];
+        }
+        normalize_v3(N);
+      }
+
+      /* Fix leading vertex type. */
+      rlci = rlc->chain.last;
+      rlci->line_type = new_rl->flags & LRT_EDGE_FLAG_ALL_TYPE;
+
+      if (new_rv == new_rl->l) {
+        rls = new_rl->segments.last;
+        last_occlusion = rls->occlusion;
+        last_transparency = rls->transparency_mask;
+        /* Fix leading vertex occlusion. */
+        rlci->occlusion = last_occlusion;
+        for (rls = new_rl->segments.last; rls; rls = rls->prev) {
+          double gpos[3], lpos[3];
+          double *lfb = new_rl->l->fbcoord, *rfb = new_rl->r->fbcoord;
+          double global_at = lfb[3] * rls->at / (rls->at * lfb[3] + (1 - rls->at) * rfb[3]);
+          interp_v3_v3v3_db(lpos, new_rl->l->fbcoord, new_rl->r->fbcoord, rls->at);
+          interp_v3_v3v3_db(gpos, new_rl->l->gloc, new_rl->r->gloc, global_at);
+          last_occlusion = rls->prev ? rls->prev->occlusion : last_occlusion;
+          POS_TO_FLOAT(lpos, gpos)
+          lineart_chain_append_point(rb,
+                                     rlc,
+                                     use_fbcoord,
+                                     use_gpos,
+                                     N,
+                                     new_rl->flags,
+                                     last_occlusion,
+                                     last_transparency,
+                                     new_rl->l_obindex);
+        }
+      }
+      else if (new_rv == new_rl->r) {
+        rls = new_rl->segments.first;
+        last_occlusion = rls->occlusion;
+        last_transparency = rls->transparency_mask;
+        rlci->occlusion = last_occlusion;
+        rls = rls->next;
+        for (; rls; rls = rls->next) {
+          double gpos[3], lpos[3];
+          double *lfb = new_rl->l->fbcoord, *rfb = new_rl->r->fbcoord;
+          double global_at = lfb[3] * rls->at / (rls->at * lfb[3] + (1 - rls->at) * rfb[3]);
+          interp_v3_v3v3_db(lpos, new_rl->l->fbcoord, new_rl->r->fbcoord, rls->at);
+          interp_v3_v3v3_db(gpos, new_rl->l->gloc, new_rl->r->gloc, global_at);
+          POS_TO_FLOAT(lpos, gpos)
+          lineart_chain_append_point(rb,
+                                     rlc,
+                                     use_fbcoord,
+                                     use_gpos,
+                                     N,
+                                     new_rl->flags,
+                                     rls->occlusion,
+                                     rls->transparency_mask,
+                                     new_rl->r_obindex);
+          last_occlusion = rls->occlusion;
+          last_transparency = rls->transparency_mask;
+        }
+        VERT_COORD_TO_FLOAT(new_rl->r)
+        lineart_chain_append_point(rb,
+                                   rlc,
+                                   use_fbcoord,
+                                   use_gpos,
+                                   N,
+                                   new_rl->flags,
+                                   last_occlusion,
+                                   last_transparency,
+                                   new_rl->r_obindex);
+      }
+      ba = MOD_lineart_get_bounding_area(rb, new_rv->fbcoord[0], new_rv->fbcoord[1]);
+    }
+    if (rb->fuzzy_everything) {
+      rlc->type = LRT_EDGE_FLAG_CONTOUR;
+    }
+    else {
+      rlc->type = (rl->flags & LRT_EDGE_FLAG_ALL_TYPE);
+    }
+  }
+  LRT_ITER_ALL_LINES_END
+}
+
+static LineartBoundingArea *lineart_bounding_area_get_rlci_recursive(
+    LineartRenderBuffer *rb, LineartBoundingArea *root, LineartRenderLineChainItem *rlci)
+{
+  if (root->child == NULL) {
+    return root;
+  }
+
+  LineartBoundingArea *ch = root->child;
+#define IN_BOUND(ba, rlci) \
+  ba.l <= rlci->pos[0] && ba.r >= rlci->pos[0] && ba.b <= rlci->pos[1] && ba.u >= rlci->pos[1]
+
+  if (IN_BOUND(ch[0], rlci)) {
+    return lineart_bounding_area_get_rlci_recursive(rb, &ch[0], rlci);
+  }
+  if (IN_BOUND(ch[1], rlci)) {
+    return lineart_bounding_area_get_rlci_recursive(rb, &ch[1], rlci);
+  }
+  if (IN_BOUND(ch[2], rlci)) {
+    return lineart_bounding_area_get_rlci_recursive(rb, &ch[2], rlci);
+  }
+  if (IN_BOUND(ch[3], rlci)) {
+    return lineart_bounding_area_get_rlci_recursive(rb, &ch[3], rlci);
+  }
+#undef IN_BOUND
+  return NULL;
+}
+
+static LineartBoundingArea *lineart_bounding_area_get_end_point(LineartRenderBuffer *rb,
+                                                                LineartRenderLineChainItem *rlci)
+{
+  if (!rlci) {
+    return NULL;
+  }
+  LineartBoundingArea *root = MOD_lineart_get_parent_bounding_area(rb, rlci->pos[0], rlci->pos[1]);
+  if (root == NULL) {
+    return NULL;
+  }
+  return lineart_bounding_area_get_rlci_recursive(rb, root, rlci);
+}
+
+/* Here we will try to connect geometry space chains together in image space. However we can't
+ * chain two chains together if their end and start points lie on the border between two bounding
+ * areas, this happens either when 1) the geometry is way too dense, or 2) the chaining threshold
+ * is too big that it covers multiple small bounding areas. */
+static void lineart_bounding_area_link_point_recursive(LineartRenderBuffer *rb,
+                                                       LineartBoundingArea *root,
+                                                       LineartRenderLineChain *rlc,
+                                                       LineartRenderLineChainItem *rlci)
+{
+  if (root->child == NULL) {
+    LineartChainRegisterEntry *cre = lineart_list_append_pointer_pool_sized(
+        &root->linked_chains, &rb->render_data_pool, rlc, sizeof(LineartChainRegisterEntry));
+
+    cre->rlci = rlci;
+
+    if (rlci == rlc->chain.first) {
+      cre->is_left = 1;
+    }
+  }
+  else {
+    LineartBoundingArea *ch = root->child;
+
+#define IN_BOUND(ba, rlci) \
+  ba.l <= rlci->pos[0] && ba.r >= rlci->pos[0] && ba.b <= rlci->pos[1] && ba.u >= rlci->pos[1]
+
+    if (IN_BOUND(ch[0], rlci)) {
+      lineart_bounding_area_link_point_recursive(rb, &ch[0], rlc, rlci);
+    }
+    else if (IN_BOUND(ch[1], rlci)) {
+      lineart_bounding_area_link_point_recursive(rb, &ch[1], rlc, rlci);
+    }
+    else if (IN_BOUND(ch[2], rlci)) {
+      lineart_bounding_area_link_point_recursive(rb, &ch[2], rlc, rlci);
+    }
+    else if (IN_BOUND(ch[3], rlci)) {
+      lineart_bounding_area_link_point_recursive(rb, &ch[3], rlc, rlci);
+    }
+
+#undef IN_BOUND
+  }
+}
+
+static void lineart_bounding_area_link_chain(LineartRenderBuffer *rb, LineartRenderLineChain *rlc)
+{
+  LineartRenderLineChainItem *pl = rlc->chain.first;
+  LineartRenderLineChainItem *pr = rlc->chain.last;
+  LineartBoundingArea *ba1 = MOD_lineart_get_parent_bounding_area(rb, pl->pos[0], pl->pos[1]);
+  LineartBoundingArea *ba2 = MOD_lineart_get_parent_bounding_area(rb, pr->pos[0], pr->pos[1]);
+
+  if (ba1) {
+    lineart_bounding_area_link_point_recursive(rb, ba1, rlc, pl);
+  }
+  if (ba2) {
+    lineart_bounding_area_link_point_recursive(rb, ba2, rlc, pr);
+  }
+}
+
+void MOD_lineart_chain_split_for_fixed_occlusion(LineartRenderBuffer *rb)
+{
+  LineartRenderLineChain *rlc, *new_rlc;
+  LineartRenderLineChainItem *rlci, *next_rlci;
+  ListBase swap = {0};
+
+  swap.first = rb->chains.first;
+  swap.last = rb->chains.last;
+
+  rb->chains.last = rb->chains.first = NULL;
+
+  while ((rlc = BLI_pophead(&swap)) != NULL) {
+    rlc->next = rlc->prev = NULL;
+    BLI_addtail(&rb->chains, rlc);
+    LineartRenderLineChainItem *first_rlci = (LineartRenderLineChainItem *)rlc->chain.first;
+    int fixed_occ = first_rlci->occlusion;
+    unsigned char fixed_mask = first_rlci->transparency_mask;
+    rlc->level = fixed_occ;
+    rlc->transparency_mask = fixed_mask;
+    for (rlci = first_rlci->next; rlci; rlci = next_rlci) {
+      next_rlci = rlci->next;
+      if (rlci->occlusion != fixed_occ || rlci->transparency_mask != fixed_mask) {
+        if (next_rlci) {
+          if (lineart_point_overlapping(next_rlci, rlci->pos[0], rlci->pos[1], 1e-5)) {
+            continue;
+          }
+        }
+        else {
+          /* Set the same occlusion level for the end vertex, so when further connection is needed
+           * the backwards occlusion info is also correct.  */
+          rlci->occlusion = fixed_occ;
+          /* No need to split at the last point anyway. */
+          break;
+        }
+        new_rlc = lineart_chain_create(rb);
+        new_rlc->chain.first = rlci;
+        new_rlc->chain.last = rlc->chain.last;
+        rlc->chain.last = rlci->prev;
+        ((LineartRenderLineChainItem *)rlc->chain.last)->next = 0;
+        rlci->prev = 0;
+
+        /* End the previous one. */
+        lineart_chain_append_point(rb,
+                                   rlc,
+                                   rlci->pos,
+                                   rlci->gpos,
+                                   rlci->normal,
+                                   rlci->line_type,
+                                   fixed_occ,
+                                   fixed_mask,
+                                   rlci->index);
+        new_rlc->object_ref = rlc->object_ref;
+        new_rlc->type = rlc->type;
+        rlc = new_rlc;
+        fixed_occ = rlci->occlusion;
+        fixed_mask = rlci->transparency_mask;
+        rlc->level = fixed_occ;
+        rlc->transparency_mask = fixed_mask;
+      }
+    }
+  }
+  LISTBASE_FOREACH (LineartRenderLineChain *, irlc, &rb->chains) {
+    lineart_bounding_area_link_chain(rb, irlc);
+  }
+}
+
+/* Note: segment type (crease/material/contour...) is ambiguous after this. */
+static void lineart_chain_connect(LineartRenderBuffer *UNUSED(rb),
+                                  LineartRenderLineChain *onto,
+                                  LineartRenderLineChain *sub,
+                                  int reverse_1,
+                                  int reverse_2)
+{
+  LineartRenderLineChainItem *rlci;
+  if (onto->type == LRT_EDGE_FLAG_INTERSECTION) {
+    if (sub->object_ref) {
+      onto->object_ref = sub->object_ref;
+      onto->type = LRT_EDGE_FLAG_CONTOUR;
+    }
+  }
+  else if (sub->type == LRT_EDGE_FLAG_INTERSECTION) {
+    if (onto->type != LRT_EDGE_FLAG_INTERSECTION) {
+      onto->type = LRT_EDGE_FLAG_CONTOUR;
+    }
+  }
+  if (!reverse_1) {  /*  L--R L-R. */
+    if (reverse_2) { /*  L--R R-L. */
+      BLI_listbase_reverse(&sub->chain);
+    }
+    rlci = sub->chain.first;
+    if (lineart_point_overlapping(onto->chain.last, rlci->pos[0], rlci->pos[1], 1e-5)) {
+      BLI_pophead(&sub->chain);
+      if (sub->chain.first == NULL) {
+        return;
+      }
+    }
+    ((LineartRenderLineChainItem *)onto->chain.last)->next = sub->chain.first;
+    ((LineartRenderLineChainItem *)sub->chain.first)->prev = onto->chain.last;
+    onto->chain.last = sub->chain.last;
+  }
+  else {              /*  L-R L--R. */
+    if (!reverse_2) { /*  R-L L--R. */
+      BLI_listbase_reverse(&sub->chain);
+    }
+    rlci = onto->chain.first;
+    if (lineart_point_overlapping(sub->chain.last, rlci->pos[0], rlci->pos[1], 1e-5)) {
+      BLI_pophead(&onto->chain);
+      if (onto->chain.first == NULL) {
+        return;
+      }
+    }
+    ((LineartRenderLineChainItem *)sub->chain.last)->next = onto->chain.first;
+    ((LineartRenderLineChainItem *)onto->chain.first)->prev = sub->chain.last;
+    onto->chain.first = sub->chain.first;
+  }
+}
+
+static LineartChainRegisterEntry *lineart_chain_get_closest_cre(LineartRenderBuffer *rb,
+                                                                LineartBoundingArea *ba,
+                                                                LineartRenderLineChain *rlc,
+                                                                LineartRenderLineChainItem *rlci,
+                                                                int occlusion,
+                                                                unsigned char transparency_mask,
+                                                                float dist,
+                                                                int do_geometry_space,
+                                                                float *result_new_len,
+                                                                LineartBoundingArea *caller_ba)
+{
+
+  LineartChainRegisterEntry *closest_cre = NULL;
+
+  /* Keep using for loop because cre could be removed from the iteration before getting to the
+   * next one. */
+  LISTBASE_FOREACH_MUTABLE (LineartChainRegisterEntry *, cre, &ba->linked_chains) {
+    if (cre->rlc->object_ref != rlc->object_ref) {
+      if (!rb->fuzzy_everything) {
+        if (rb->fuzzy_intersections) {
+          /* If none of those are intersection lines... */
+          if ((!(cre->rlc->type & LRT_EDGE_FLAG_INTERSECTION)) &&
+              (!(rlc->type & LRT_EDGE_FLAG_INTERSECTION))) {
+            continue; /* We don't want to chain along different objects at the moment. */
+          }
+        }
+        else {
+          continue;
+        }
+      }
+    }
+    if (cre->rlc->picked || cre->picked) {
+      continue;
+    }
+    if (cre->rlc == rlc || (!cre->rlc->chain.first) || (cre->rlc->level != occlusion) ||
+        (cre->rlc->transparency_mask != transparency_mask)) {
+      continue;
+    }
+    if (!rb->fuzzy_everything) {
+      if (cre->rlc->type != rlc->type) {
+        if (rb->fuzzy_intersections) {
+          if (!(cre->rlc->type == LRT_EDGE_FLAG_INTERSECTION ||
+                rlc->type == LRT_EDGE_FLAG_INTERSECTION)) {
+            continue; /* Fuzzy intersetions but no intersection line found. */
+          }
+        }
+        else { /* Line type different but no fuzzy. */
+          continue;
+        }
+      }
+    }
+
+    float new_len = do_geometry_space ? len_v3v3(cre->rlci->gpos, rlci->gpos) :
+                                        len_v2v2(cre->rlci->pos, rlci->pos);
+    if (new_len < dist) {
+      closest_cre = cre;
+      dist = new_len;
+      if (result_new_len) {
+        (*result_new_len) = new_len;
+      }
+    }
+  }
+
+  /* We want a closer point anyway. So using modified dist is fine. */
+  float adjacent_new_len = dist;
+  LineartChainRegisterEntry *adjacent_closest;
+
+#define LRT_TEST_ADJACENT_AREAS(dist_to, list) \
+  if (dist_to < dist && dist_to > 0) { \
+    LISTBASE_FOREACH (LinkData *, ld, list) { \
+      LineartBoundingArea *sba = (LineartBoundingArea *)ld->data; \
+      adjacent_closest = lineart_chain_get_closest_cre(rb, \
+                                                       sba, \
+                                                       rlc, \
+                                                       rlci, \
+                                                       occlusion, \
+                                                       transparency_mask, \
+                                                       dist, \
+                                                       do_geometry_space, \
+                                                       &adjacent_new_len, \
+                                                       ba); \
+      if (adjacent_new_len < dist) { \
+        dist = adjacent_new_len; \
+        closest_cre = adjacent_closest; \
+      } \
+    } \
+  }
+  if (!do_geometry_space && !caller_ba) {
+    LRT_TEST_ADJACENT_AREAS(rlci->pos[0] - ba->l, &ba->lp);
+    LRT_TEST_ADJACENT_AREAS(ba->r - rlci->pos[0], &ba->rp);
+    LRT_TEST_ADJACENT_AREAS(ba->u - rlci->pos[1], &ba->up);
+    LRT_TEST_ADJACENT_AREAS(rlci->pos[1] - ba->b, &ba->bp);
+  }
+  if (result_new_len) {
+    (*result_new_len) = dist;
+  }
+  return closest_cre;
+}
+
+/* This function only connects two different chains. It will not do any clean up or smart chaining.
+ * So no: removing overlapping chains, removal of short isolated segments, and no loop reduction is
+ * implemented yet. */
+void MOD_lineart_chain_connect(LineartRenderBuffer *rb, const bool do_geometry_space)
+{
+  LineartRenderLineChain *rlc;
+  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 dist_l, dist_r;
+  int occlusion, reverse_main;
+  unsigned char transparency_mask;
+  ListBase swap = {0};
+
+  if ((!do_geometry_space && rb->chaining_image_threshold < 0.0001) ||
+      (do_geometry_space && rb->chaining_geometry_threshold < 0.0001)) {
+    return;
+  }
+
+  swap.first = rb->chains.first;
+  swap.last = rb->chains.last;
+
+  rb->chains.last = rb->chains.first = NULL;
+
+  while ((rlc = BLI_pophead(&swap)) != NULL) {
+    rlc->next = rlc->prev = NULL;
+    if (rlc->picked) {
+      continue;
+    }
+    BLI_addtail(&rb->chains, rlc);
+
+    occlusion = rlc->level;
+    transparency_mask = rlc->transparency_mask;
+
+    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_l,
+                                                    rlc,
+                                                    rlci_l,
+                                                    occlusion,
+                                                    transparency_mask,
+                                                    dist,
+                                                    do_geometry_space,
+                                                    &dist_l,
+                                                    NULL);
+      closest_cre_r = lineart_chain_get_closest_cre(rb,
+                                                    ba_r,
+                                                    rlc,
+                                                    rlci_r,
+                                                    occlusion,
+                                                    transparency_mask,
+                                                    dist,
+                                                    do_geometry_space,
+                                                    &dist_r,
+                                                    NULL);
+      if (closest_cre_l && closest_cre_r) {
+        if (dist_l < dist_r) {
+          closest_cre = closest_cre_l;
+          reverse_main = 1;
+        }
+        else {
+          closest_cre = closest_cre_r;
+          reverse_main = 0;
+        }
+      }
+      else if (closest_cre_l) {
+        closest_cre = closest_cre_l;
+        reverse_main = 1;
+      }
+      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->picked = 1;
+      closest_cre->rlc->picked = 1;
+      if (closest_cre->is_left) {
+        lineart_chain_connect(rb, rlc, closest_cre->rlc, reverse_main, 0);
+      }
+      else {
+        lineart_chain_connect(rb, rlc, closest_cre->rlc, reverse_main, 1);
+      }
+      BLI_remlink(&swap, closest_cre->rlc);
+      rlci_l = rlc->chain.first;
+      rlci_r = rlc->chain.last;
+    }
+    rlc->picked = 1;
+  }
+}
+
+/* Length is in image space. */
+float MOD_lineart_chain_compute_length(LineartRenderLineChain *rlc)
+{
+  LineartRenderLineChainItem *rlci;
+  float offset_accum = 0;
+  float dist;
+  float last_point[2];
+
+  rlci = rlc->chain.first;
+  copy_v2_v2(last_point, rlci->pos);
+  for (rlci = rlc->chain.first; rlci; rlci = rlci->next) {
+    dist = len_v2v2(rlci->pos, last_point);
+    offset_accum += dist;
+    copy_v2_v2(last_point, rlci->pos);
+  }
+  return offset_accum;
+}
+
+void MOD_lineart_chain_discard_short(LineartRenderBuffer *rb, const float threshold)
+{
+  LineartRenderLineChain *rlc, *next_rlc;
+  for (rlc = rb->chains.first; rlc; rlc = next_rlc) {
+    next_rlc = rlc->next;
+    if (MOD_lineart_chain_compute_length(rlc) < threshold) {
+      BLI_remlink(&rb->chains, rlc);
+    }
+  }
+}
+
+int MOD_lineart_chain_count(const LineartRenderLineChain *rlc)
+{
+  int count = 0;
+  LISTBASE_FOREACH (LineartRenderLineChainItem *, rlci, &rlc->chain) {
+    count++;
+  }
+  return count;
+}
+
+void MOD_lineart_chain_clear_picked_flag(LineartRenderBuffer *rb)
+{
+  if (rb == NULL) {
+    return;
+  }
+  LISTBASE_FOREACH (LineartRenderLineChain *, rlc, &rb->chains) {
+    rlc->picked = 0;
+  }
+}
+
+/* This should always be the last stage!, see the end of
+ * MOD_lineart_chain_split_for_fixed_occlusion().*/
+void MOD_lineart_chain_split_angle(LineartRenderBuffer *rb, float angle_threshold_rad)
+{
+  LineartRenderLineChain *rlc, *new_rlc;
+  LineartRenderLineChainItem *rlci, *next_rlci, *prev_rlci;
+  ListBase swap = {0};
+
+  swap.first = rb->chains.first;
+  swap.last = rb->chains.last;
+
+  rb->chains.last = rb->chains.first = NULL;
+
+  while ((rlc = BLI_pophead(&swap)) != NULL) {
+    rlc->next = rlc->prev = NULL;
+    BLI_addtail(&rb->chains, rlc);
+    LineartRenderLineChainItem *first_rlci = (LineartRenderLineChainItem *)rlc->chain.first;
+    for (rlci = first_rlci->next; rlci; rlci = next_rlci) {
+      next_rlci = rlci->next;
+      prev_rlci = rlci->prev;
+      float angle = M_PI;
+      if (next_rlci && prev_rlci) {
+        angle = angle_v2v2v2(prev_rlci->pos, rlci->pos, next_rlci->pos);
+      }
+      else {
+        break; /* No need to split at the last point anyway.*/
+      }
+      if (angle < angle_threshold_rad) {
+        new_rlc = lineart_chain_create(rb);
+        new_rlc->chain.first = rlci;
+        new_rlc->chain.last = rlc->chain.last;
+        rlc->chain.last = rlci->prev;
+        ((LineartRenderLineChainItem *)rlc->chain.last)->next = 0;
+        rlci->prev = 0;
+
+        /* End the previous one. */
+        lineart_chain_append_point(rb,
+                                   rlc,
+                                   rlci->pos,
+                                   rlci->gpos,
+                                   rlci->normal,
+                                   rlci->line_type,
+                                   rlc->level,
+                                   rlci->transparency_mask,
+                                   rlci->index);
+        new_rlc->object_ref = rlc->object_ref;
+        new_rlc->type = rlc->type;
+        new_rlc->level = rlc->level;
+        new_rlc->transparency_mask = rlc->transparency_mask;
+        rlc = new_rlc;
+      }
+    }
+  }
+}