VSE: Fix rendering inconsistency

Fix issue described in T87678, which was partially a bug and partially
change in intended(at least as far as I can tell) behaior.

Function `evaluate_seq_frame_gen` that was partially responsible for
filtering strips in stack for rendering wasn't working correctly.
Intended functionality seems to be removing all effect inputs from stack
as it is unlikely that user would want these to be blended in. However
there was logic to exclude effects placed into same input, which because
of weak implementation caused, that any effect input, that is effect as
well will be considered to be part of stack to be blended in.
This bug was apparently used to produce effects like glow over original
image.

Even though this is originally unintended, I have kept this logic, but
I have made it explicit.

Another change is request made in T87678 to make it possible to keep
effect inputs as part of stack when they are placed above the effect,
which would imply that blending is intended. This change is again
explicitly defined.

Whole implementation has been refactored, so logic is consolidated
and code should be as explicit as possible and more readable.
`must_render_strip function` may be still quite hard to read, not sure
if I can make it nicer.

Last change is for remove gaps feature code - it used same rendering
code, which may be reason why its logic was split in first place.
Now it uses sequencer iterator, which will definitely be faster than
original code, but I could have used `LISTBASE_FOREACH` in this case.

Reviewed By: sergey

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

4 files changed, 144 insertions, 88 deletions

diff --git a/source/blender/sequencer/SEQ_iterator.h b/source/blender/sequencer/SEQ_iterator.h
index 5f0836f5ca9..c7c2dc275ee 100644
--- a/source/blender/sequencer/SEQ_iterator.h
+++ b/source/blender/sequencer/SEQ_iterator.h
@@ -72,6 +72,7 @@ struct Sequence *SEQ_iterator_yield(SeqIterator *iterator);
 
 SeqCollection *SEQ_collection_create(void);
 bool SEQ_collection_append_strip(struct Sequence *seq, SeqCollection *data);
+bool SEQ_collection_remove_strip(struct Sequence *seq, SeqCollection *data);
 void SEQ_collection_free(SeqCollection *collection);
 void SEQ_collection_merge(SeqCollection *collection_dst, SeqCollection *collection_src);
 void SEQ_collection_expand(struct ListBase *seqbase,
@@ -85,6 +86,7 @@ SeqCollection *SEQ_query_by_reference(struct Sequence *seq_reference,
                                                           struct ListBase *seqbase,
                                                           SeqCollection *collection));
 SeqCollection *SEQ_query_selected_strips(struct ListBase *seqbase);
+SeqCollection *SEQ_query_all_strips(ListBase *seqbase);
 SeqCollection *SEQ_query_all_strips_recursive(ListBase *seqbase);
 void SEQ_query_strip_effect_chain(struct Sequence *seq_reference,
                                   struct ListBase *seqbase,
diff --git a/source/blender/sequencer/intern/iterator.c b/source/blender/sequencer/intern/iterator.c
index 5225fc925e8..9bbc5362f18 100644
--- a/source/blender/sequencer/intern/iterator.c
+++ b/source/blender/sequencer/intern/iterator.c
@@ -149,6 +149,18 @@ bool SEQ_collection_append_strip(Sequence *seq, SeqCollection *collection)
 }
 
 /**
+ * Remove strip from collection.
+ *
+ * \param seq: strip to be removed
+ * \param collection: collection from which strip will be removed
+ * \return true if strip exists in set and it was removed from set, otherwise false
+ */
+bool SEQ_collection_remove_strip(Sequence *seq, SeqCollection *collection)
+{
+  return BLI_gset_remove(collection->set, seq, NULL);
+}
+
+/**
  * Move strips from collection_src to collection_dst. Source collection will be freed.
  *
  * \param collection_dst: destination collection
@@ -214,6 +226,21 @@ SeqCollection *SEQ_query_all_strips_recursive(ListBase *seqbase)
 }
 
 /**
+ * Query all strips in seqbase. This does not include strips nested in meta strips.
+ *
+ * \param seqbase: ListBase in which strips are queried
+ * \return strip collection
+ */
+SeqCollection *SEQ_query_all_strips(ListBase *seqbase)
+{
+  SeqCollection *collection = SEQ_collection_create();
+  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
+    SEQ_collection_append_strip(seq, collection);
+  }
+  return collection;
+}
+
+/**
  * Query all selected strips in seqbase.
  *
  * \param seqbase: ListBase in which strips are queried
diff --git a/source/blender/sequencer/intern/render.c b/source/blender/sequencer/intern/render.c
index f892f1c1b41..e8e600f910c 100644
--- a/source/blender/sequencer/intern/render.c
+++ b/source/blender/sequencer/intern/render.c
@@ -65,6 +65,7 @@
 #include "RE_pipeline.h"
 
 #include "SEQ_effects.h"
+#include "SEQ_iterator.h"
 #include "SEQ_modifier.h"
 #include "SEQ_proxy.h"
 #include "SEQ_render.h"
@@ -259,120 +260,132 @@ StripElem *SEQ_render_give_stripelem(Sequence *seq, int timeline_frame)
   return se;
 }
 
-static int evaluate_seq_frame_gen(Sequence **seq_arr,
-                                  ListBase *seqbase,
-                                  int timeline_frame,
-                                  int chanshown)
+static bool seq_is_effect_of(const Sequence *seq_effect, const Sequence *possibly_input)
 {
-  /* Use arbitrary sized linked list, the size could be over MAXSEQ. */
-  LinkNodePair effect_inputs = {NULL, NULL};
-  int totseq = 0;
+  if (seq_effect->seq1 == possibly_input || seq_effect->seq2 == possibly_input ||
+      seq_effect->seq3 == possibly_input) {
+    return true;
+  }
+  return false;
+}
 
-  memset(seq_arr, 0, sizeof(Sequence *) * (MAXSEQ + 1));
+/* Check if seq must be rendered. This depends on whole stack in some cases, not only seq itself.
+ * Order of applying these conditions is important. */
+static bool must_render_strip(const Sequence *seq, SeqCollection *strips_under_playhead)
+{
+  /* Sound strips are not rendered. */
+  if (seq->type == SEQ_TYPE_SOUND_RAM) {
+    return false;
+  }
+  /* Muted strips are not rendered. */
+  if ((seq->flag & SEQ_MUTE) != 0) {
+    return false;
+  }
 
-  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
-    if ((seq->startdisp <= timeline_frame) && (seq->enddisp > timeline_frame)) {
-      if ((seq->type & SEQ_TYPE_EFFECT) && !(seq->flag & SEQ_MUTE)) {
+  bool seq_have_effect_in_stack = false;
+  Sequence *seq_iter;
+  SEQ_ITERATOR_FOREACH (seq_iter, strips_under_playhead) {
+    /* Strips is below another strip with replace blending are not rendered. */
+    if (seq_iter->blend_mode == SEQ_BLEND_REPLACE && seq->machine < seq_iter->machine) {
+      return false;
+    }
 
-        if (seq->seq1) {
-          BLI_linklist_append_alloca(&effect_inputs, seq->seq1);
-        }
+    if ((seq_iter->type & SEQ_TYPE_EFFECT) != 0 && seq_is_effect_of(seq_iter, seq)) {
+      /* Strips in same channel or higher than its effect are rendered. */
+      if (seq->machine >= seq_iter->machine) {
+        return true;
+      }
+      /* Mark that this strip has effect in stack, that is above the strip. */
+      seq_have_effect_in_stack = true;
+    }
+  }
 
-        if (seq->seq2) {
-          BLI_linklist_append_alloca(&effect_inputs, seq->seq2);
-        }
+  /* All effects are rendered (with respect to conditions above). */
+  if ((seq->type & SEQ_TYPE_EFFECT) != 0) {
+    return true;
+  }
 
-        if (seq->seq3) {
-          BLI_linklist_append_alloca(&effect_inputs, seq->seq3);
-        }
-      }
+  /* If strip has effects in stack, and all effects are above this strip, it it not rendered. */
+  if (seq_have_effect_in_stack) {
+    return false;
+  }
+
+  return true;
+}
 
-      seq_arr[seq->machine] = seq;
-      totseq++;
+static SeqCollection *query_strips_at_frame(ListBase *seqbase, const int timeline_frame)
+{
+  SeqCollection *collection = SEQ_collection_create();
+
+  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
+    if ((seq->startdisp <= timeline_frame) && (seq->enddisp > timeline_frame)) {
+      SEQ_collection_append_strip(seq, collection);
     }
   }
+  return collection;
+}
 
-  /* Drop strips which are used for effect inputs, we don't want
-   * them to blend into render stack in any other way than effect
-   * string rendering. */
-  for (LinkNode *seq_item = effect_inputs.list; seq_item; seq_item = seq_item->next) {
-    Sequence *seq = seq_item->link;
-    /* It's possible that effect strip would be placed to the same
-     * 'machine' as its inputs. We don't want to clear such strips
-     * from the stack. */
-    if (seq_arr[seq->machine] && seq_arr[seq->machine]->type & SEQ_TYPE_EFFECT) {
-      continue;
-    }
-    /* If we're shown a specified channel, then we want to see the strips
-     * which belongs to this machine. */
-    if (chanshown != 0 && chanshown <= seq->machine) {
+static void collection_filter_channel_up_to_incl(SeqCollection *collection, const int channel)
+{
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, collection) {
+    if (seq->machine <= channel) {
       continue;
     }
-    seq_arr[seq->machine] = NULL;
+    SEQ_collection_remove_strip(seq, collection);
   }
-
-  return totseq;
 }
 
-/**
- * Count number of strips in timeline at timeline_frame
- *
- * \param seqbase: ListBase in which strips are located
- * \param timeline_frame: frame on timeline from where gaps are searched for
- * \return number of strips
- */
-int SEQ_render_evaluate_frame(ListBase *seqbase, int timeline_frame)
+/* Remove strips we don't want to render from collection. */
+static void collection_filter_rendered_strips(SeqCollection *collection)
 {
-  Sequence *seq_arr[MAXSEQ + 1];
-  return evaluate_seq_frame_gen(seq_arr, seqbase, timeline_frame, 0);
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, collection) {
+    if (must_render_strip(seq, collection)) {
+      continue;
+    }
+    SEQ_collection_remove_strip(seq, collection);
+  }
 }
 
-static bool video_seq_is_rendered(Sequence *seq)
+static int seq_channel_cmp_fn(const void *a, const void *b)
 {
-  return (seq && !(seq->flag & SEQ_MUTE) && seq->type != SEQ_TYPE_SOUND_RAM);
+  return (*(Sequence **)a)->machine - (*(Sequence **)b)->machine;
 }
 
-int seq_get_shown_sequences(ListBase *seqbasep,
-                            int timeline_frame,
-                            int chanshown,
-                            Sequence **seq_arr_out)
+int seq_get_shown_sequences(ListBase *seqbase,
+                            const int timeline_frame,
+                            const int chanshown,
+                            Sequence **r_seq_arr)
 {
-  Sequence *seq_arr[MAXSEQ + 1];
-  int b = chanshown;
-  int cnt = 0;
+  SeqCollection *collection = query_strips_at_frame(seqbase, timeline_frame);
 
-  if (b > MAXSEQ) {
-    return 0;
-  }
-
-  if (evaluate_seq_frame_gen(seq_arr, seqbasep, timeline_frame, chanshown)) {
-    if (b == 0) {
-      b = MAXSEQ;
-    }
-    for (; b > 0; b--) {
-      if (video_seq_is_rendered(seq_arr[b])) {
-        break;
-      }
-    }
+  if (chanshown != 0) {
+    collection_filter_channel_up_to_incl(collection, chanshown);
   }
+  collection_filter_rendered_strips(collection);
 
-  chanshown = b;
+  const int strip_count = BLI_gset_len(collection->set);
 
-  for (; b > 0; b--) {
-    if (video_seq_is_rendered(seq_arr[b])) {
-      if (seq_arr[b]->blend_mode == SEQ_BLEND_REPLACE) {
-        break;
-      }
-    }
+  if (strip_count > MAXSEQ) {
+    BLI_assert(!"Too many strips, this shouldn't happen");
+    return 0;
   }
 
-  for (; b <= chanshown && b >= 0; b++) {
-    if (video_seq_is_rendered(seq_arr[b])) {
-      seq_arr_out[cnt++] = seq_arr[b];
-    }
+  /* Copy collection elements into array. */
+  memset(r_seq_arr, 0, sizeof(Sequence *) * (MAXSEQ + 1));
+  Sequence *seq;
+  int index = 0;
+  SEQ_ITERATOR_FOREACH (seq, collection) {
+    r_seq_arr[index] = seq;
+    index++;
   }
+  SEQ_collection_free(collection);
+
+  /* Sort array by channel. */
+  qsort(r_seq_arr, strip_count, sizeof(Sequence *), seq_channel_cmp_fn);
 
-  return cnt;
+  return strip_count;
 }
 
 /** \} */
diff --git a/source/blender/sequencer/intern/strip_time.c b/source/blender/sequencer/intern/strip_time.c
index a7a6e2595be..40d7fade308 100644
--- a/source/blender/sequencer/intern/strip_time.c
+++ b/source/blender/sequencer/intern/strip_time.c
@@ -36,6 +36,7 @@
 
 #include "IMB_imbuf.h"
 
+#include "SEQ_iterator.h"
 #include "SEQ_render.h"
 #include "SEQ_sequencer.h"
 #include "SEQ_time.h"
@@ -404,6 +405,17 @@ void SEQ_timeline_boundbox(const Scene *scene, const ListBase *seqbase, rctf *re
   }
 }
 
+static bool strip_exists_at_frame(SeqCollection *all_strips, const int timeline_frame)
+{
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, all_strips) {
+    if ((seq->startdisp <= timeline_frame) && (seq->enddisp > timeline_frame)) {
+      return true;
+    }
+  }
+  return false;
+}
+
 /**
  * Find first gap between strips after initial_frame and describe it by filling data of r_gap_info
  *
@@ -425,10 +437,12 @@ void seq_time_gap_info_get(const Scene *scene,
   int timeline_frame = initial_frame;
   r_gap_info->gap_exists = false;
 
-  if (SEQ_render_evaluate_frame(seqbase, initial_frame) == 0) {
+  SeqCollection *collection = SEQ_query_all_strips(seqbase);
+
+  if (!strip_exists_at_frame(collection, initial_frame)) {
     /* Search backward for gap_start_frame. */
     for (; timeline_frame >= sfra; timeline_frame--) {
-      if (SEQ_render_evaluate_frame(seqbase, timeline_frame) != 0) {
+      if (strip_exists_at_frame(collection, timeline_frame)) {
         break;
       }
     }
@@ -438,7 +452,7 @@ void seq_time_gap_info_get(const Scene *scene,
   else {
     /* Search forward for gap_start_frame. */
     for (; timeline_frame <= efra; timeline_frame++) {
-      if (SEQ_render_evaluate_frame(seqbase, timeline_frame) == 0) {
+      if (!strip_exists_at_frame(collection, timeline_frame)) {
         r_gap_info->gap_start_frame = timeline_frame;
         break;
       }
@@ -446,7 +460,7 @@ void seq_time_gap_info_get(const Scene *scene,
   }
   /* Search forward for gap_end_frame. */
   for (; timeline_frame <= efra; timeline_frame++) {
-    if (SEQ_render_evaluate_frame(seqbase, timeline_frame) != 0) {
+    if (strip_exists_at_frame(collection, timeline_frame)) {
       const int gap_end_frame = timeline_frame;
       r_gap_info->gap_length = gap_end_frame - r_gap_info->gap_start_frame;
       r_gap_info->gap_exists = true;