Fix two issues related to non-treelike (diamond) effect graphs.
authorSteinar H. Gunderson <sgunderson@bigfoot.com>
Tue, 15 Jan 2013 21:44:22 +0000 (22:44 +0100)
committerSteinar H. Gunderson <sgunderson@bigfoot.com>
Tue, 15 Jan 2013 21:44:22 +0000 (22:44 +0100)
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.

add.frag [new file with mode: 0644]
effect_chain.cpp
effect_chain.h
effect_chain_test.cpp
multiply.frag [new file with mode: 0644]

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);
+}
index 4758215..5d0037c 100644 (file)
@@ -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];
index 666df9e..b51c2bb 100644 (file)
@@ -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();
index 356d628..4a9712e 100644 (file)
@@ -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
@@ -0,0 +1,3 @@
+vec4 FUNCNAME(vec2 tc) {
+       return INPUT(tc) * PREFIX(factor);
+}