Fix two issues related to non-treelike (diamond) effect graphs.

First of all, we could have an assert failure when an input was used twice.
Work around it by simply ignoring the input the second time.

This, however, would expose an issue where effects could be emitted in the
.glsl file out-of-order. Refactor the topological sort code so that it can
be reused for arbitrary subgraphs, and then use it to topologically sort
the list of effects in each pass.

Add a unit test to verify that all of this works.

diff --git a/add.frag b/add.frag
new file mode 100644 (file)
index 0000000..7d8ea58
--- /dev/null
+++ b/add.frag
@@ -0,0 +1,3 @@
+vec4 FUNCNAME(vec2 tc) {
+       return INPUT1(tc) + INPUT2(tc);
+}

diff --git a/effect_chain.cpp b/effect_chain.cpp
index 475821585abf7df9967214647711062dc9dd51f2..5d0037cf6b4397cd9c44dcb57b1b5c3be616303a 100644 (file)
--- a/effect_chain.cpp
+++ b/effect_chain.cpp
@@ -229,8 +229,10 @@ Phase *EffectChain::compile_glsl_program(
                frag_shader += "\n";
        }
 
-       for (unsigned i = 0; i < effects.size(); ++i) {
-               Node *node = effects[i];
+       std::vector<Node *> sorted_effects = topological_sort(effects);
+
+       for (unsigned i = 0; i < sorted_effects.size(); ++i) {
+               Node *node = sorted_effects[i];
 
                if (node->incoming_links.size() == 1) {
                        frag_shader += std::string("#define INPUT ") + node->incoming_links[0]->effect_id + "\n";
@@ -261,13 +263,13 @@ Phase *EffectChain::compile_glsl_program(
 
                input_needs_mipmaps |= node->effect->needs_mipmaps();
        }
-       for (unsigned i = 0; i < effects.size(); ++i) {
-               Node *node = effects[i];
+       for (unsigned i = 0; i < sorted_effects.size(); ++i) {
+               Node *node = sorted_effects[i];
                if (node->effect->num_inputs() == 0) {
                        CHECK(node->effect->set_int("needs_mipmaps", input_needs_mipmaps));
                }
        }
-       frag_shader += std::string("#define INPUT ") + effects.back()->effect_id + "\n";
+       frag_shader += std::string("#define INPUT ") + sorted_effects.back()->effect_id + "\n";
        frag_shader.append(read_file("footer.frag"));
 
        if (movit_debug_level == MOVIT_DEBUG_ON) {
@@ -300,7 +302,7 @@ Phase *EffectChain::compile_glsl_program(
        phase->fragment_shader = fs_obj;
        phase->input_needs_mipmaps = input_needs_mipmaps;
        phase->inputs = true_inputs;
-       phase->effects = effects;
+       phase->effects = sorted_effects;
 
        return phase;
 }
@@ -343,8 +345,12 @@ void EffectChain::construct_glsl_programs(Node *output)
                        Node *node = effects_todo_this_phase.top();
                        effects_todo_this_phase.pop();
 
-                       // This should currently only happen for effects that are phase outputs,
-                       // and we throw those out separately below.
+                       // This should currently only happen for effects that are inputs
+                       // (either true inputs or phase outputs). We special-case inputs,
+                       // and then deduplicate phase outputs in compile_glsl_program().
+                       if (node->effect->num_inputs() == 0 && completed_effects.count(node)) {
+                               continue;
+                       }
                        assert(completed_effects.count(node) == 0);
 
                        this_phase_effects.push_back(node);
@@ -638,27 +644,30 @@ void EffectChain::find_output_size(Phase *phase)
        phase->output_height = best_width * aspect_denom / aspect_nom;
 }
 
-void EffectChain::sort_nodes_topologically()
+void EffectChain::sort_all_nodes_topologically()
 {
-       std::set<Node *> visited_nodes;
+       nodes = topological_sort(nodes);
+}
+
+std::vector<Node *> EffectChain::topological_sort(const std::vector<Node *> &nodes)
+{
+       std::set<Node *> nodes_left_to_visit(nodes.begin(), nodes.end());
        std::vector<Node *> sorted_list;
        for (unsigned i = 0; i < nodes.size(); ++i) {
-               if (nodes[i]->incoming_links.size() == 0) {
-                       topological_sort_visit_node(nodes[i], &visited_nodes, &sorted_list);
-               }
+               topological_sort_visit_node(nodes[i], &nodes_left_to_visit, &sorted_list);
        }
        reverse(sorted_list.begin(), sorted_list.end());
-       nodes = sorted_list;
+       return sorted_list;
 }
 
-void EffectChain::topological_sort_visit_node(Node *node, std::set<Node *> *visited_nodes, std::vector<Node *> *sorted_list)
+void EffectChain::topological_sort_visit_node(Node *node, std::set<Node *> *nodes_left_to_visit, std::vector<Node *> *sorted_list)
 {
-       if (visited_nodes->count(node) != 0) {
+       if (nodes_left_to_visit->count(node) == 0) {
                return;
        }
-       visited_nodes->insert(node);
+       nodes_left_to_visit->erase(node);
        for (unsigned i = 0; i < node->outgoing_links.size(); ++i) {
-               topological_sort_visit_node(node->outgoing_links[i], visited_nodes, sorted_list);
+               topological_sort_visit_node(node->outgoing_links[i], nodes_left_to_visit, sorted_list);
        }
        sorted_list->push_back(node);
 }
@@ -700,7 +709,7 @@ void EffectChain::find_color_spaces_for_inputs()
 void EffectChain::propagate_gamma_and_color_space()
 {
        // We depend on going through the nodes in order.
-       sort_nodes_topologically();
+       sort_all_nodes_topologically();
 
        for (unsigned i = 0; i < nodes.size(); ++i) {
                Node *node = nodes[i];
@@ -742,7 +751,7 @@ void EffectChain::propagate_gamma_and_color_space()
 void EffectChain::propagate_alpha()
 {
        // We depend on going through the nodes in order.
-       sort_nodes_topologically();
+       sort_all_nodes_topologically();
 
        for (unsigned i = 0; i < nodes.size(); ++i) {
                Node *node = nodes[i];

diff --git a/effect_chain.h b/effect_chain.h
index 666df9e5738b4de515b80a3e67452356f55b6d67..b51c2bb56cc0d97222ddf7ca99c98d5d8988df38 100644 (file)
--- a/effect_chain.h
+++ b/effect_chain.h
@@ -179,8 +179,17 @@ private:
        // Some of the graph algorithms assume that the nodes array is sorted
        // topologically (inputs are always before outputs), but some operations
        // (like graph rewriting) can change that. This function restores that order.
-       void sort_nodes_topologically();
-       void topological_sort_visit_node(Node *node, std::set<Node *> *visited_nodes, std::vector<Node *> *sorted_list);
+       void sort_all_nodes_topologically();
+
+       // Do the actual topological sort. <nodes> must be a connected, acyclic subgraph;
+       // links that go to nodes not in the set will be ignored.
+       std::vector<Node *> topological_sort(const std::vector<Node *> &nodes);
+
+       // Utility function used by topological_sort() to do a depth-first search.
+       // The reason why we store nodes left to visit instead of a more conventional
+       // list of nodes to visit is that we want to be able to limit ourselves to
+       // a subgraph instead of all nodes. The set thus serves a dual purpose.
+       void topological_sort_visit_node(Node *node, std::set<Node *> *nodes_left_to_visit, std::vector<Node *> *sorted_list);
 
        // Used during finalize().
        void find_color_spaces_for_inputs();

diff --git a/effect_chain_test.cpp b/effect_chain_test.cpp
index 356d628e7e0fbd7dd2c293a9efafd34ed36cfed1..4a9712edba194ceb7dc93fb1266e71c6daa78c4d 100644 (file)
--- a/effect_chain_test.cpp
+++ b/effect_chain_test.cpp
@@ -594,3 +594,69 @@ TEST(EffectChainTest, ResizeDownByFourThenUpByFour) {
 
        expect_equal(expected_data, out_data, 4, 16);
 }
+
+// An effect that multiplies with a constant. Used below.
+class MultiplyEffect : public Effect {
+public:
+       MultiplyEffect() { register_float("factor", &factor); }
+       virtual std::string effect_type_id() const { return "MultiplyEffect"; }
+       std::string output_fragment_shader() { return read_file("multiply.frag"); }
+       virtual AlphaHandling alpha_handling() const { return DONT_CARE_ALPHA_TYPE; }
+
+private:
+       float factor;
+};
+
+// An effect that adds its two inputs together. Used below.
+class AddEffect : public Effect {
+public:
+       AddEffect() {}
+       virtual std::string effect_type_id() const { return "AddEffect"; }
+       std::string output_fragment_shader() { return read_file("add.frag"); }
+       virtual unsigned num_inputs() const { return 2; }
+       virtual AlphaHandling alpha_handling() const { return DONT_CARE_ALPHA_TYPE; }
+};
+
+// Constructs the graph
+//
+//             FlatInput               |
+//            /         \              |
+//  MultiplyEffect  MultiplyEffect     |
+//            \         /              |
+//             AddEffect               |
+//
+// and verifies that it gives the correct output.
+TEST(EffectChainTest, DiamondGraph) {
+       float data[] = {
+               1.0f, 1.0f,
+               1.0f, 0.0f,
+       };
+       float expected_data[] = {
+               2.5f, 2.5f,
+               2.5f, 0.0f,
+       };
+       float out_data[2 * 2];
+
+       MultiplyEffect *mul_half = new MultiplyEffect();
+       ASSERT_TRUE(mul_half->set_float("factor", 0.5f));
+       
+       MultiplyEffect *mul_two = new MultiplyEffect();
+       ASSERT_TRUE(mul_two->set_float("factor", 2.0f));
+
+       EffectChainTester tester(NULL, 2, 2);
+
+       ImageFormat format;
+       format.color_space = COLORSPACE_sRGB;
+       format.gamma_curve = GAMMA_LINEAR;
+
+       FlatInput *input = new FlatInput(format, FORMAT_GRAYSCALE, GL_FLOAT, 2, 2);
+       input->set_pixel_data(data);
+
+       tester.get_chain()->add_input(input);
+       tester.get_chain()->add_effect(mul_half, input);
+       tester.get_chain()->add_effect(mul_two, input);
+       tester.get_chain()->add_effect(new AddEffect(), mul_half, mul_two);
+       tester.run(out_data, GL_RED, COLORSPACE_sRGB, GAMMA_LINEAR);
+
+       expect_equal(expected_data, out_data, 2, 2);
+}

diff --git a/multiply.frag b/multiply.frag
new file mode 100644 (file)
index 0000000..88f8bf7
--- /dev/null
+++ b/multiply.frag
@@ -0,0 +1,3 @@
+vec4 FUNCNAME(vec2 tc) {
+       return INPUT(tc) * PREFIX(factor);
+}