Outliner Filtering System + Cleanup

User notes:

The outliner so far was a great system to handle the object oriented workflow
we had in Blender prior to 2.8. However with the introduction of collections
the bloated ammount of data we were exposed at a given time was eventually
getting on the way of fully utilizing the outliner to manage collections and
their objects.

We hope that with this filtering system the user can put together the outliner
with whichever options he or she seem fit for a given task.

Features:
* Collection filter: In case users are only focused on objects.
* Object filter: Allow users to focus on collections only.
* (Object) content filter: Modifiers, mesh, contrainst, materials, ...
* (Object) children filter: Hide object children [1].
* Object State (visible, active, selected).
* Compact header: hide search options under a search toggle.
* Preserve scrolling position before/after filtering [2].

[1] - Note we still need to be able to tell if a children of an object is in a
      collection, or if the parent object is the only one in the collection.
      This in fact was one of the first motivations for this patch. But it is to
      be addressed separately now that we can at least hide children away.

[2] - We look at the top-most collection in the outliner, and try to find it again
      after the filtering and make sure it is in the same position as before.
      This works nice now. But to work REALLY, REALLY nice we need to also store
      the previous filter options to be sure the element we try to keep on top
      was valid for both old and new filters. I would rather do this later though
      since this smell a lot like feature creeping ;)

Remove no longer needed display options:
 * Current Scene (replaced by View Layer/Collections)
 * Visible (replaced by filter)
 * Selected (same)
 * Active (same)
 * Same Type (same-ish)

How about All Scenes? I have a patch that will come next to replace the current
behaviour and focus only on compositing. So basically stop showing the objects
and show only view layers, their passes and collections, besides freestyle.

Also, while at this I'm also reorganizing the menu to keep View Layer and
Collections on top.

Developer notes:

* Unlike the per-object filtering, for collections we need to filter at tree
creation time, to prevent duplication of objects in the outliner.

Acknowledgements:

Thanks Pablo Vazquez for helping testing, thinking some design questions
together and pushing this to its final polished state as you see here.

Thanks Sergey Sharybin and Julian Eisel for code review. Julian couldn't do a
final review pass after I addressed his concerns. So blame is on me for any
issue I may be introducing here. Sergey was the author of the "preserve
scrolling position" idea. I'm happy with how it is working, thank you.

Reviewers: sergey, Severin, venomgfx
Subscribers: lichtwerk, duarteframos

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

1 files changed, 374 insertions, 73 deletions

diff --git a/source/blender/editors/space_outliner/outliner_tree.c b/source/blender/editors/space_outliner/outliner_tree.c
index c8f38e5282b..851e19a3650 100644
--- a/source/blender/editors/space_outliner/outliner_tree.c
+++ b/source/blender/editors/space_outliner/outliner_tree.c
@@ -82,6 +82,8 @@
 
 #include "RNA_access.h"
 
+#include "UI_interface.h"
+
 #include "outliner_intern.h"
 
 #ifdef WIN32
@@ -1751,6 +1753,305 @@ static void outliner_sort(ListBase *lb)
 
 /* Filtering ----------------------------------------------- */
 
+typedef struct OutlinerTreeElementFocus {
+	TreeStoreElem *tselem;
+	int ys;
+} OutlinerTreeElementFocus;
+
+/**
+ * Bring the outliner scrolling back to where it was in relation to the original focus element
+ * Caller is expected to handle redrawing of ARegion.
+ */
+static void outliner_restore_scrolling_position(SpaceOops *soops, ARegion *ar, OutlinerTreeElementFocus *focus)
+{
+	View2D *v2d = &ar->v2d;
+	int ytop;
+
+	if (focus->tselem != NULL) {
+		outliner_set_coordinates(ar, soops);
+
+		TreeElement *te_new = outliner_find_tree_element(&soops->tree, focus->tselem);
+
+		if (te_new != NULL) {
+			int ys_new, ys_old;
+
+			ys_new = te_new->ys;
+			ys_old = focus->ys;
+
+			ytop = v2d->cur.ymax + (ys_new - ys_old) -1;
+			if (ytop > 0) ytop = 0;
+
+			v2d->cur.ymax = (float)ytop;
+			v2d->cur.ymin = (float)(ytop - BLI_rcti_size_y(&v2d->mask));
+		}
+		else {
+			return;
+		}
+
+		soops->storeflag |= SO_TREESTORE_REDRAW;
+	}
+}
+
+static bool test_collection_callback(TreeElement *te)
+{
+	TreeStoreElem *tselem = TREESTORE(te);
+	return ELEM(tselem->type, TSE_LAYER_COLLECTION, TSE_SCENE_COLLECTION);
+}
+
+static bool test_object_callback(TreeElement *te)
+{
+	TreeStoreElem *tselem = TREESTORE(te);
+	return ((tselem->type == 0) && (te->idcode == ID_OB));
+}
+
+/**
+ * See if TreeElement or any of its children pass the callback_test.
+ */
+static TreeElement *outliner_find_first_desired_element_at_y_recursive(
+        const SpaceOops *soops,
+        TreeElement *te,
+        const float limit,
+        bool (*callback_test)(TreeElement *))
+{
+	if (callback_test(te)) {
+		return te;
+	}
+
+	if (TSELEM_OPEN(te->store_elem, soops)) {
+		TreeElement *te_iter, *te_sub;
+		for (te_iter = te->subtree.first; te_iter; te_iter = te_iter->next) {
+			te_sub = outliner_find_first_desired_element_at_y_recursive(soops, te_iter, limit, callback_test);
+			if (te_sub != NULL) {
+				return te_sub;
+			}
+		}
+	}
+
+	return NULL;
+}
+
+/**
+ * Find the first element that passes a test starting from a reference vertical coordinate
+ *
+ * If the element that is in the position is not what we are looking for, keep looking for its
+ * children, siblings, and eventually, aunts, cousins, disntant families, ...
+ *
+ * Basically we keep going up and down the outliner tree from that point forward, until we find
+ * what we are looking for. If we are past the visible range and we can't find a valid element
+ * we return NULL.
+ */
+static TreeElement *outliner_find_first_desired_element_at_y(
+        const SpaceOops *soops,
+        const float view_co,
+        const float view_co_limit)
+{
+	TreeElement *te, *te_sub;
+	te = outliner_find_item_at_y(soops, &soops->tree, view_co);
+
+	bool (*callback_test)(TreeElement *);
+	if (soops->filter & SO_FILTER_NO_COLLECTION) {
+		callback_test = test_object_callback;
+	}
+	else {
+		callback_test = test_collection_callback;
+	}
+
+	while (te != NULL) {
+		te_sub = outliner_find_first_desired_element_at_y_recursive(soops, te, view_co_limit, callback_test);
+		if (te_sub != NULL) {
+			/* Skip the element if it was not visible to start with. */
+			if (te->ys + UI_UNIT_Y > view_co_limit) {
+				return te_sub;
+			}
+			else {
+				return NULL;
+			}
+		}
+
+		if (te->next) {
+			te = te->next;
+			continue;
+		}
+
+		if (te->parent == NULL) {
+			break;
+		}
+
+		while (te->parent) {
+			if (te->parent->next) {
+				te = te->parent->next;
+				break;
+			}
+			te = te->parent;
+		}
+	}
+
+	return NULL;
+}
+
+/**
+ * Store information of current outliner scrolling status to be restored later
+ *
+ * Finds the top-most collection visible in the outliner and populates the OutlinerTreeElementFocus
+ * struct to retrieve this element later to make sure it is in the same original position as before filtering
+ */
+static void outliner_store_scrolling_position(SpaceOops *soops, ARegion *ar, OutlinerTreeElementFocus *focus)
+{
+	TreeElement *te;
+	float limit = ar->v2d.cur.ymin;
+
+	outliner_set_coordinates(ar, soops);
+
+	te = outliner_find_first_desired_element_at_y(soops, ar->v2d.cur.ymax, limit);
+
+	if (te != NULL) {
+		focus->tselem = TREESTORE(te);
+		focus->ys = te->ys;
+	}
+	else {
+		focus->tselem = NULL;
+	}
+}
+
+static int outliner_exclude_filter_get(SpaceOops *soops)
+{
+	int exclude_filter = soops->filter & ~(SO_FILTER_OB_STATE_VISIBLE |
+	                                       SO_FILTER_OB_STATE_SELECTED |
+	                                       SO_FILTER_OB_STATE_ACTIVE);
+
+	if (soops->filter & SO_FILTER_SEARCH) {
+		if (soops->search_string[0] == 0) {
+			exclude_filter &= ~SO_FILTER_SEARCH;
+		}
+	}
+
+	/* Let's have this for the collection options at first. */
+	if (!SUPPORT_FILTER_OUTLINER(soops)) {
+		return (exclude_filter & SO_FILTER_SEARCH);
+	}
+
+	if ((exclude_filter & SO_FILTER_NO_OB_ALL) == 0) {
+		exclude_filter &= ~SO_FILTER_OB_TYPE;
+	}
+
+	if (exclude_filter & SO_FILTER_OB_STATE) {
+		switch (soops->filter_state) {
+			case SO_FILTER_OB_VISIBLE:
+				exclude_filter |= SO_FILTER_OB_STATE_VISIBLE;
+				break;
+			case SO_FILTER_OB_SELECTED:
+				exclude_filter |= SO_FILTER_OB_STATE_SELECTED;
+				break;
+			case SO_FILTER_OB_ACTIVE:
+				exclude_filter |= SO_FILTER_OB_STATE_ACTIVE;
+				break;
+		}
+	}
+
+	if ((exclude_filter & SO_FILTER_ANY) == 0) {
+		exclude_filter &= ~(SO_FILTER_OB_STATE);
+	}
+
+	return exclude_filter;
+}
+
+static bool outliner_element_visible_get(ViewLayer *view_layer, TreeElement *te, const int exclude_filter)
+{
+	if ((exclude_filter & SO_FILTER_ENABLE) == 0) {
+		return true;
+	}
+
+	TreeStoreElem *tselem = TREESTORE(te);
+	if ((tselem->type == 0) && (te->idcode == ID_OB)) {
+		if ((exclude_filter & SO_FILTER_NO_OBJECT)) {
+			return false;
+		}
+
+		Object *ob = (Object *)tselem->id;
+		Base *base = (Base *)te->directdata;
+		BLI_assert((base == NULL) || (base->object == ob));
+
+		if (exclude_filter & SO_FILTER_OB_TYPE) {
+			switch (ob->type) {
+				case OB_MESH:
+					if (exclude_filter & SO_FILTER_NO_OB_MESH) {
+						return false;
+					}
+					break;
+				case OB_ARMATURE:
+					if (exclude_filter & SO_FILTER_NO_OB_ARMATURE) {
+						return false;
+					}
+					break;
+				case OB_EMPTY:
+					if (exclude_filter & SO_FILTER_NO_OB_EMPTY) {
+						return false;
+					}
+					break;
+				case OB_LAMP:
+					if (exclude_filter & SO_FILTER_NO_OB_LAMP) {
+						return false;
+					}
+					break;
+				case OB_CAMERA:
+					if (exclude_filter & SO_FILTER_NO_OB_CAMERA) {
+						return false;
+					}
+					break;
+				default:
+					if (exclude_filter & SO_FILTER_NO_OB_OTHERS) {
+						return false;
+					}
+					break;
+			}
+		}
+
+		if (exclude_filter & SO_FILTER_OB_STATE) {
+			if (base == NULL) {
+				base = BKE_view_layer_base_find(view_layer, ob);
+
+				if (base == NULL) {
+					return false;
+				}
+			}
+
+			if (exclude_filter & SO_FILTER_OB_STATE_VISIBLE) {
+				if ((base->flag & BASE_VISIBLED) == 0) {
+					return false;
+				}
+			}
+			else if (exclude_filter & SO_FILTER_OB_STATE_SELECTED) {
+				if ((base->flag & BASE_SELECTED) == 0) {
+					return false;
+				}
+			}
+			else {
+				BLI_assert(exclude_filter & SO_FILTER_OB_STATE_ACTIVE);
+				if (base != BASACT(view_layer)) {
+					return false;
+				}
+			}
+		}
+
+		if ((te->parent != NULL) &&
+		    (TREESTORE(te->parent)->type == 0) && (te->parent->idcode == ID_OB))
+		{
+			if (exclude_filter & SO_FILTER_NO_CHILDREN) {
+				return false;
+			}
+		}
+	}
+	else if (te->parent != NULL &&
+	    TREESTORE(te->parent)->type == 0 && te->parent->idcode == ID_OB)
+	{
+		if (exclude_filter & SO_FILTER_NO_OB_CONTENT) {
+			return false;
+		}
+	}
+
+	return true;
+}
+
 static bool outliner_filter_has_name(TreeElement *te, const char *name, int flags)
 {
 	int fn_flag = 0;
@@ -1761,31 +2062,25 @@ static bool outliner_filter_has_name(TreeElement *te, const char *name, int flag
 	return fnmatch(name, te->name, fn_flag) == 0;
 }
 
-static int outliner_filter_tree(SpaceOops *soops, ListBase *lb)
+static int outliner_filter_subtree(
+        SpaceOops *soops, ViewLayer *view_layer, ListBase *lb, const char *search_string, const int exclude_filter)
 {
-	TreeElement *te, *ten;
+	TreeElement *te, *te_next;
 	TreeStoreElem *tselem;
-	char search_buff[sizeof(((struct SpaceOops *)NULL)->search_string) + 2];
-	char *search_string;
 
-	/* although we don't have any search string, we return true 
-	 * since the entire tree is ok then...
-	 */
-	if (soops->search_string[0] == 0)
-		return 1;
+	for (te = lb->first; te; te = te_next) {
+		te_next = te->next;
 
-	if (soops->search_flags & SO_FIND_COMPLETE) {
-		search_string = soops->search_string;
-	}
-	else {
-		/* Implicitly add heading/trailing wildcards if needed. */
-		BLI_strncpy_ensure_pad(search_buff, soops->search_string, '*', sizeof(search_buff));
-		search_string = search_buff;
-	}
+		if ((outliner_element_visible_get(view_layer, te, exclude_filter) == false)) {
+			outliner_free_tree_element(te, lb);
+			continue;
+		}
+		else if ((exclude_filter & SO_FILTER_SEARCH) == 0) {
+			/* Filter subtree too. */
+			outliner_filter_subtree(soops, view_layer, &te->subtree, search_string, exclude_filter);
+			continue;
+		}
 
-	for (te = lb->first; te; te = ten) {
-		ten = te->next;
-		
 		if (!outliner_filter_has_name(te, search_string, soops->search_flags)) {
 			/* item isn't something we're looking for, but...
 			 *  - if the subtree is expanded, check if there are any matches that can be easily found
@@ -1794,35 +2089,60 @@ static int outliner_filter_tree(SpaceOops *soops, ListBase *lb)
 			 *		so these can be safely ignored (i.e. the subtree can get freed)
 			 */
 			tselem = TREESTORE(te);
-			
+
 			/* flag as not a found item */
 			tselem->flag &= ~TSE_SEARCHMATCH;
 			
-			if ((!TSELEM_OPEN(tselem, soops)) || outliner_filter_tree(soops, &te->subtree) == 0) {
+			if ((!TSELEM_OPEN(tselem, soops)) ||
+			    outliner_filter_subtree(soops, view_layer, &te->subtree, search_string, exclude_filter) == 0)
+			{
 				outliner_free_tree_element(te, lb);
 			}
 		}
 		else {
 			tselem = TREESTORE(te);
-			
+
 			/* flag as a found item - we can then highlight it */
 			tselem->flag |= TSE_SEARCHMATCH;
-			
+
 			/* filter subtree too */
-			outliner_filter_tree(soops, &te->subtree);
+			outliner_filter_subtree(soops, view_layer, &te->subtree, search_string, exclude_filter);
 		}
 	}
-	
+
 	/* if there are still items in the list, that means that there were still some matches */
 	return (BLI_listbase_is_empty(lb) == false);
 }
 
+static void outliner_filter_tree(SpaceOops *soops, ViewLayer *view_layer)
+{
+	char search_buff[sizeof(((struct SpaceOops *)NULL)->search_string) + 2];
+	char *search_string;
+
+	const int exclude_filter = outliner_exclude_filter_get(soops);
+
+	if (exclude_filter == 0) {
+		return;
+	}
+
+	if (soops->search_flags & SO_FIND_COMPLETE) {
+		search_string = soops->search_string;
+	}
+	else {
+		/* Implicitly add heading/trailing wildcards if needed. */
+		BLI_strncpy_ensure_pad(search_buff, soops->search_string, '*', sizeof(search_buff));
+		search_string = search_buff;
+	}
+
+	outliner_filter_subtree(soops, view_layer, &soops->tree, search_string, exclude_filter);
+}
+
 /* ======================================================= */
 /* Main Tree Building API */
 
 /* Main entry point for building the tree data-structure that the outliner represents */
 // TODO: split each mode into its own function?
-void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, SpaceOops *soops)
+void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, SpaceOops *soops, ARegion *ar)
 {
 	TreeElement *te = NULL, *ten;
 	TreeStoreElem *tselem;
@@ -1844,6 +2164,9 @@ void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, Spa
 	if (soops->tree.first && (soops->storeflag & SO_TREESTORE_REDRAW))
 		return;
 
+	OutlinerTreeElementFocus focus;
+	outliner_store_scrolling_position(soops, ar, &focus);
+
 	outliner_free_tree(&soops->tree);
 	outliner_storage_cleanup(soops);
 	
@@ -1921,27 +2244,6 @@ void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, Spa
 			FOREACH_SCENE_OBJECT_END
 		}
 	}
-	else if (soops->outlinevis == SO_CUR_SCENE) {
-		
-		outliner_add_scene_contents(soops, &soops->tree, scene, NULL);
-
-		FOREACH_SCENE_OBJECT(scene, ob)
-		{
-			outliner_add_element(soops, &soops->tree, ob, NULL, 0, 0);
-		}
-		FOREACH_SCENE_OBJECT_END
-		outliner_make_hierarchy(&soops->tree);
-	}
-	else if (soops->outlinevis == SO_VISIBLE) {
-		FOREACH_VISIBLE_BASE(view_layer, base)
-		{
-			ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
-			ten->directdata = base;
-
-		}
-		FOREACH_VISIBLE_BASE_END
-		outliner_make_hierarchy(&soops->tree);
-	}
 	else if (soops->outlinevis == SO_GROUPS) {
 		Group *group;
 		for (group = mainvar->group.first; group; group = group->id.next) {
@@ -1949,28 +2251,6 @@ void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, Spa
 			outliner_make_hierarchy(&te->subtree);
 		}
 	}
-	else if (soops->outlinevis == SO_SAME_TYPE) {
-		Object *ob_active = OBACT(view_layer);
-		if (ob_active) {
-			FOREACH_SCENE_OBJECT(scene, ob)
-			{
-				if (ob->type == ob_active->type) {
-					outliner_add_element(soops, &soops->tree, ob, NULL, 0, 0);
-				}
-			}
-			FOREACH_SCENE_OBJECT_END
-			outliner_make_hierarchy(&soops->tree);
-		}
-	}
-	else if (soops->outlinevis == SO_SELECTED) {
-		FOREACH_SELECTED_BASE(view_layer, base)
-		{
-			ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
-			ten->directdata = base;
-		}
-		FOREACH_SELECTED_BASE_END
-		outliner_make_hierarchy(&soops->tree);
-	}
 	else if (soops->outlinevis == SO_SEQUENCE) {
 		Sequence *seq;
 		Editing *ed = BKE_sequencer_editing_get(scene, false);
@@ -2023,10 +2303,29 @@ void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, Spa
 		outliner_add_orphaned_datablocks(mainvar, soops);
 	}
 	else if (soops->outlinevis == SO_VIEW_LAYER) {
-		outliner_add_view_layer(soops, scene, view_layer);
+		if ((soops->filter & SO_FILTER_ENABLE) && (soops->filter & SO_FILTER_NO_COLLECTION)) {
+			for (Base *base = view_layer->object_bases.first; base; base = base->next) {
+				TreeElement *te_object = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
+				te_object->directdata = base;
+			}
+			outliner_make_hierarchy(&soops->tree);
+		}
+		else {
+			outliner_add_view_layer(soops, scene, view_layer);
+		}
 	}
 	else if (soops->outlinevis == SO_COLLECTIONS) {
-		outliner_add_collections(soops, scene);
+		if ((soops->filter & SO_FILTER_ENABLE) && (soops->filter & SO_FILTER_NO_COLLECTION)) {
+			FOREACH_SCENE_OBJECT(scene, ob)
+			{
+				outliner_add_element(soops, &soops->tree, ob, NULL, 0, 0);
+			}
+			FOREACH_SCENE_OBJECT_END
+			outliner_make_hierarchy(&soops->tree);
+		}
+		else {
+			outliner_add_collections(soops, scene);
+		}
 	}
 	else {
 		if (BASACT(view_layer)) {
@@ -2038,7 +2337,9 @@ void outliner_build_tree(Main *mainvar, Scene *scene, ViewLayer *view_layer, Spa
 	if ((soops->flag & SO_SKIP_SORT_ALPHA) == 0) {
 		outliner_sort(&soops->tree);
 	}
-	outliner_filter_tree(soops, &soops->tree);
+
+	outliner_filter_tree(soops, view_layer);
+	outliner_restore_scrolling_position(soops, ar, &focus);
 
 	BKE_main_id_clear_newpoins(mainvar);
 }