Outliner: Show parenting hierarchy in view layer view

If the "Object Children" filter is enabled, we nest the object children inside
the object. If the child itself is not in the collection, it is grayed out,
connected by a dash line, and its restriction flags and contents are not shown.

If "Object Children" filter is disabled, it works as before.

Note: This is not super fast, but at least we traverse the tree only once to get the
children of an object. That said, there is a lot of loops going on here.

Task T63526.

Development notes:
I could use the GPU_SHADER_2D_LINE_DASHED_UNIFORM_COLOR shader, but
that would mean I would need to iterate over the tree twice (once for
each shader) - or do some bigger refactor.

Also I could not get that shader to work. This shader expects float
vertices while the current one is using integers, so converting the code
would make the dash line drawing to diverge from the regular lines even
further.

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

3 files changed, 176 insertions, 11 deletions

diff --git a/source/blender/editors/space_outliner/outliner_draw.c b/source/blender/editors/space_outliner/outliner_draw.c
index 9dbea3c5b1b..545e31c8b4a 100644
--- a/source/blender/editors/space_outliner/outliner_draw.c
+++ b/source/blender/editors/space_outliner/outliner_draw.c
@@ -627,6 +627,10 @@ static void outliner_draw_restrictbuts(uiBlock *block,
         UI_but_flag_enable(bt, UI_BUT_DRAG_LOCK);
         UI_but_drawflag_enable(bt, UI_BUT_ICON_REVERSE);
       }
+      else if ((tselem->type == 0 && te->idcode == ID_OB) &&
+               (te->flag & TE_CHILD_NOT_IN_COLLECTION)) {
+        /* Don't show restrict columns for children that are not directly inside the collection. */
+      }
       else if (tselem->type == 0 && te->idcode == ID_OB) {
         PointerRNA ptr;
         Object *ob = (Object *)tselem->id;
@@ -2074,7 +2078,10 @@ static void outliner_draw_tree_element(bContext *C,
   tselem = TREESTORE(te);
 
   if (*starty + 2 * UI_UNIT_Y >= ar->v2d.cur.ymin && *starty <= ar->v2d.cur.ymax) {
-    const float alpha_fac = ((te->flag & TE_DISABLED) || draw_grayed_out) ? 0.5f : 1.0f;
+    const float alpha_fac = ((te->flag & TE_DISABLED) || (te->flag & TE_CHILD_NOT_IN_COLLECTION) ||
+                             draw_grayed_out) ?
+                                0.5f :
+                                1.0f;
     const float alpha = 0.5f * alpha_fac;
     int xmax = ar->v2d.cur.xmax;
 
@@ -2338,17 +2345,28 @@ static void outliner_draw_hierarchy_lines_recursive(unsigned pos,
                                                     bool draw_grayed_out,
                                                     int *starty)
 {
-  TreeElement *te, *te_vertical_line_last = NULL;
-  int y1, y2;
+  TreeElement *te, *te_vertical_line_last = NULL, *te_vertical_line_last_dashed = NULL;
+  int y1, y2, y1_dashed, y2_dashed;
 
   if (BLI_listbase_is_empty(lb)) {
     return;
   }
 
+  struct {
+    int steps_num;
+    int step_len;
+    int gap_len;
+  } dash = {
+      .steps_num = 4,
+  };
+
+  dash.step_len = UI_UNIT_X / dash.steps_num;
+  dash.gap_len = dash.step_len / 2;
+
   const unsigned char grayed_alpha = col[3] / 2;
 
   /* For vertical lines between objects. */
-  y1 = y2 = *starty;
+  y1 = y2 = y1_dashed = y2_dashed = *starty;
   for (te = lb->first; te; te = te->next) {
     bool draw_childs_grayed_out = draw_grayed_out || (te->flag & TE_DRAGGING);
     TreeStoreElem *tselem = TREESTORE(te);
@@ -2360,16 +2378,31 @@ static void outliner_draw_hierarchy_lines_recursive(unsigned pos,
       immUniformColor4ubv(col);
     }
 
-    /* Horizontal Line? */
-    if (tselem->type == 0 && (te->idcode == ID_OB || te->idcode == ID_SCE)) {
-      immRecti(pos, startx, *starty, startx + UI_UNIT_X, *starty - 1);
+    if ((te->flag & TE_CHILD_NOT_IN_COLLECTION) == 0) {
+      /* Horizontal Line? */
+      if (tselem->type == 0 && (te->idcode == ID_OB || te->idcode == ID_SCE)) {
+        immRecti(pos, startx, *starty, startx + UI_UNIT_X, *starty - 1);
 
-      /* Vertical Line? */
-      if (te->idcode == ID_OB) {
-        te_vertical_line_last = te;
-        y2 = *starty;
+        /* Vertical Line? */
+        if (te->idcode == ID_OB) {
+          te_vertical_line_last = te;
+          y2 = *starty;
+        }
+        y1_dashed = *starty - UI_UNIT_Y;
       }
     }
+    else {
+      BLI_assert(te->idcode == ID_OB);
+      /* Horizontal line - dashed. */
+      int start = startx;
+      for (int i = 0; i < dash.steps_num; i++) {
+        immRecti(pos, start, *starty, start + dash.step_len - dash.gap_len, *starty - 1);
+        start += dash.step_len;
+      }
+
+      te_vertical_line_last_dashed = te;
+      y2_dashed = *starty;
+    }
 
     *starty -= UI_UNIT_Y;
 
@@ -2391,6 +2424,18 @@ static void outliner_draw_hierarchy_lines_recursive(unsigned pos,
   if ((te != NULL) && (te->parent || lb->first != lb->last)) {
     immRecti(pos, startx, y1 + UI_UNIT_Y, startx + 1, y2);
   }
+
+  /* Children that are not in the collection are always in the end of the subtree.
+   * This way we can draw their own dashed vertical lines. */
+  te = te_vertical_line_last_dashed;
+  if ((te != NULL) && (te->parent || lb->first != lb->last)) {
+    const int steps_num = ((y1_dashed + UI_UNIT_Y) - y2_dashed) / dash.step_len;
+    int start = y1_dashed + UI_UNIT_Y;
+    for (int i = 0; i < steps_num; i++) {
+      immRecti(pos, startx, start, startx + 1, start - dash.step_len + dash.gap_len);
+      start -= dash.step_len;
+    }
+  }
 }
 
 static void outliner_draw_hierarchy_lines(SpaceOutliner *soops,
diff --git a/source/blender/editors/space_outliner/outliner_intern.h b/source/blender/editors/space_outliner/outliner_intern.h
index d382384076b..d532a1cbbb8 100644
--- a/source/blender/editors/space_outliner/outliner_intern.h
+++ b/source/blender/editors/space_outliner/outliner_intern.h
@@ -130,6 +130,7 @@ enum {
   TE_FREE_NAME = (1 << 3),
   TE_DISABLED = (1 << 4),
   TE_DRAGGING = (1 << 5),
+  TE_CHILD_NOT_IN_COLLECTION = (1 << 6),
 };
 
 /* button events */
diff --git a/source/blender/editors/space_outliner/outliner_tree.c b/source/blender/editors/space_outliner/outliner_tree.c
index 69449f46677..a2f332b0795 100644
--- a/source/blender/editors/space_outliner/outliner_tree.c
+++ b/source/blender/editors/space_outliner/outliner_tree.c
@@ -48,6 +48,7 @@
 #include "DNA_linestyle_types.h"
 
 #include "BLI_blenlib.h"
+#include "BLI_listbase.h"
 #include "BLI_utildefines.h"
 #include "BLI_mempool.h"
 #include "BLI_fnmatch.h"
@@ -1477,6 +1478,108 @@ static void outliner_make_object_parent_hierarchy(ListBase *lb)
   }
 }
 
+static void outliner_make_object_parent_hierarchy_recursive(SpaceOutliner *soops,
+                                                            GHash *parent_children_hash,
+                                                            TreeElement *te_parent,
+                                                            ListBase *tree_to_remove_objects_from)
+{
+  if (tree_to_remove_objects_from == NULL) {
+    tree_to_remove_objects_from = &te_parent->subtree;
+  }
+
+  /* Build hierarchy. */
+  for (TreeElement *te = te_parent->subtree.first; te; te = te->next) {
+    TreeStoreElem *tselem = TREESTORE(te);
+
+    if (tselem->type == TSE_LAYER_COLLECTION) {
+      outliner_make_object_parent_hierarchy_recursive(soops, parent_children_hash, te, NULL);
+    }
+    else if (tselem->type == 0 && te->idcode == ID_OB) {
+      Object *ob = (Object *)tselem->id;
+      ListBase *children = BLI_ghash_lookup(parent_children_hash, ob);
+
+      if (children) {
+        TreeElement *te_last_element_in_object_tree = te->subtree.last;
+        for (LinkData *link = children->first; link; link = link->next) {
+          Object *child = link->data;
+          TreeElement *te_child = NULL;
+
+          /* Check if the child is in the layer collection / tree. */
+          for (TreeElement *te_iter = tree_to_remove_objects_from->first; te_iter;
+               te_iter = te_iter->next) {
+            TreeStoreElem *tselem_iter = TREESTORE(te_iter);
+            if ((tselem_iter->type == 0 && te_iter->idcode == ID_OB) &&
+                (tselem_iter->id == &child->id)) {
+              te_child = te_iter;
+              break;
+            }
+          }
+
+          if (te_child) {
+            BLI_remlink(tree_to_remove_objects_from, te_child);
+            /* We group the children that are in the collection before the ones that are not.
+             * This way we can try to draw them in a different style altogether.
+             * We also have to respect the original order of the elements in case alphabetical
+             * sorting is not enabled. This keep object data and modifiers before its children. */
+            BLI_insertlinkafter(&te->subtree, te_last_element_in_object_tree, te_child);
+            te_child->parent = te;
+            continue;
+          }
+
+          /* If not see if it is already nested under its parent.
+           * This happens depending on the order of the evaluation. */
+          for (TreeElement *te_iter = te->subtree.first; te_iter; te_iter = te_iter->next) {
+            TreeStoreElem *tselem_iter = TREESTORE(te_iter);
+            if ((tselem_iter->type == 0 && te_iter->idcode == ID_OB) &&
+                (tselem_iter->id == &child->id)) {
+              te_child = te_iter;
+              break;
+            }
+          }
+
+          if (te_child == NULL) {
+            te_child = outliner_add_element(soops, &te->subtree, child, te, 0, 0);
+            outliner_free_tree(&te_child->subtree);
+            te_child->flag |= TE_CHILD_NOT_IN_COLLECTION;
+          }
+        }
+        outliner_make_object_parent_hierarchy_recursive(
+            soops, parent_children_hash, te, tree_to_remove_objects_from);
+      }
+    }
+  }
+}
+
+static void outliner_build_parent_children_tree_create(Main *bmain, GHash *parent_children_hash)
+{
+  ListBase *children = NULL;
+
+  for (Object *ob = bmain->objects.first; ob; ob = ob->id.next) {
+    if (!ob->parent) {
+      continue;
+    }
+
+    children = BLI_ghash_lookup(parent_children_hash, ob->parent);
+    if (children == NULL) {
+      children = MEM_callocN(sizeof(ListBase), __func__);
+      BLI_ghash_insert(parent_children_hash, ob->parent, children);
+    }
+
+    BLI_addtail(children, BLI_genericNodeN(ob));
+  }
+}
+
+static void outliner_build_parent_children_tree_free(Main *bmain, GHash *parent_children_hash)
+{
+  for (Object *ob = bmain->objects.first; ob; ob = ob->id.next) {
+    ListBase *children = BLI_ghash_lookup(parent_children_hash, ob);
+    if (children) {
+      BLI_freelistN(children);
+      MEM_freeN(children);
+    }
+  }
+}
+
 /* Sorting ------------------------------------------------------ */
 
 typedef struct tTreeSort {
@@ -1505,6 +1608,13 @@ static int treesort_alpha_ob(const void *v1, const void *v2)
     return -1;
   }
   else if (comp == 3) {
+    /* Among objects first come the ones in the collection, followed by the ones not on it.
+     * This way we can have the dashed lines in a separate style connecting the former. */
+    if ((x1->te->flag & TE_CHILD_NOT_IN_COLLECTION) !=
+        (x2->te->flag & TE_CHILD_NOT_IN_COLLECTION)) {
+      return (x1->te->flag & TE_CHILD_NOT_IN_COLLECTION) ? 1 : -1;
+    }
+
     comp = strcmp(x1->name, x2->name);
 
     if (comp > 0) {
@@ -2191,6 +2301,15 @@ void outliner_build_tree(
 
       bool show_objects = !(soops->filter & SO_FILTER_NO_OBJECT);
       outliner_add_view_layer(soops, &ten->subtree, ten, view_layer, show_objects);
+
+      if ((soops->filter & SO_FILTER_NO_CHILDREN) == 0) {
+        GHash *parent_children_hash = BLI_ghash_new(
+            BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, __func__);
+        outliner_build_parent_children_tree_create(mainvar, parent_children_hash);
+        outliner_make_object_parent_hierarchy_recursive(soops, parent_children_hash, ten, NULL);
+        outliner_build_parent_children_tree_free(mainvar, parent_children_hash);
+        BLI_ghash_free(parent_children_hash, NULL, NULL);
+      }
     }
   }