GPencil: Cancel Fill if the filled area is not closed
[blender.git] / source / blender / nodes / intern / node_tree_ref.cc
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 #include "NOD_node_tree_ref.hh"
18
19 #include "BLI_dot_export.hh"
20
21 namespace blender::nodes {
22
23 NodeTreeRef::NodeTreeRef(bNodeTree *btree) : btree_(btree)
24 {
25   Map<bNode *, NodeRef *> node_mapping;
26
27   LISTBASE_FOREACH (bNode *, bnode, &btree->nodes) {
28     NodeRef &node = *allocator_.construct<NodeRef>();
29
30     node.tree_ = this;
31     node.bnode_ = bnode;
32     node.id_ = nodes_by_id_.append_and_get_index(&node);
33     RNA_pointer_create(&btree->id, &RNA_Node, bnode, &node.rna_);
34
35     LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->inputs) {
36       InputSocketRef &socket = *allocator_.construct<InputSocketRef>();
37       socket.node_ = &node;
38       socket.index_ = node.inputs_.append_and_get_index(&socket);
39       socket.is_input_ = true;
40       socket.bsocket_ = bsocket;
41       socket.id_ = sockets_by_id_.append_and_get_index(&socket);
42       RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.rna_);
43     }
44
45     LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->outputs) {
46       OutputSocketRef &socket = *allocator_.construct<OutputSocketRef>();
47       socket.node_ = &node;
48       socket.index_ = node.outputs_.append_and_get_index(&socket);
49       socket.is_input_ = false;
50       socket.bsocket_ = bsocket;
51       socket.id_ = sockets_by_id_.append_and_get_index(&socket);
52       RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.rna_);
53     }
54
55     input_sockets_.extend(node.inputs_.as_span());
56     output_sockets_.extend(node.outputs_.as_span());
57
58     node_mapping.add_new(bnode, &node);
59   }
60
61   LISTBASE_FOREACH (bNodeLink *, blink, &btree->links) {
62     OutputSocketRef &from_socket = this->find_output_socket(
63         node_mapping, blink->fromnode, blink->fromsock);
64     InputSocketRef &to_socket = this->find_input_socket(
65         node_mapping, blink->tonode, blink->tosock);
66
67     from_socket.directly_linked_sockets_.append(&to_socket);
68     to_socket.directly_linked_sockets_.append(&from_socket);
69   }
70
71   for (OutputSocketRef *socket : output_sockets_) {
72     if (!socket->node_->is_reroute_node()) {
73       this->find_targets_skipping_reroutes(*socket, socket->linked_sockets_);
74       for (SocketRef *target : socket->linked_sockets_) {
75         target->linked_sockets_.append(socket);
76       }
77     }
78   }
79
80   for (NodeRef *node : nodes_by_id_) {
81     const bNodeType *nodetype = node->bnode_->typeinfo;
82     nodes_by_type_.add(nodetype, node);
83   }
84 }
85
86 NodeTreeRef::~NodeTreeRef()
87 {
88   for (NodeRef *node : nodes_by_id_) {
89     node->~NodeRef();
90   }
91   for (InputSocketRef *socket : input_sockets_) {
92     socket->~InputSocketRef();
93   }
94   for (OutputSocketRef *socket : output_sockets_) {
95     socket->~OutputSocketRef();
96   }
97 }
98
99 InputSocketRef &NodeTreeRef::find_input_socket(Map<bNode *, NodeRef *> &node_mapping,
100                                                bNode *bnode,
101                                                bNodeSocket *bsocket)
102 {
103   NodeRef *node = node_mapping.lookup(bnode);
104   for (InputSocketRef *socket : node->inputs_) {
105     if (socket->bsocket_ == bsocket) {
106       return *socket;
107     }
108   }
109   BLI_assert(false);
110   return *node->inputs_[0];
111 }
112
113 OutputSocketRef &NodeTreeRef::find_output_socket(Map<bNode *, NodeRef *> &node_mapping,
114                                                  bNode *bnode,
115                                                  bNodeSocket *bsocket)
116 {
117   NodeRef *node = node_mapping.lookup(bnode);
118   for (OutputSocketRef *socket : node->outputs_) {
119     if (socket->bsocket_ == bsocket) {
120       return *socket;
121     }
122   }
123   BLI_assert(false);
124   return *node->outputs_[0];
125 }
126
127 void NodeTreeRef::find_targets_skipping_reroutes(OutputSocketRef &socket,
128                                                  Vector<SocketRef *> &r_targets)
129 {
130   for (SocketRef *direct_target : socket.directly_linked_sockets_) {
131     if (direct_target->node_->is_reroute_node()) {
132       this->find_targets_skipping_reroutes(*direct_target->node_->outputs_[0], r_targets);
133     }
134     else {
135       r_targets.append_non_duplicates(direct_target);
136     }
137   }
138 }
139
140 static bool has_link_cycles_recursive(const NodeRef &node,
141                                       MutableSpan<bool> visited,
142                                       MutableSpan<bool> is_in_stack)
143 {
144   const int node_id = node.id();
145   if (is_in_stack[node_id]) {
146     return true;
147   }
148   if (visited[node_id]) {
149     return false;
150   }
151
152   visited[node_id] = true;
153   is_in_stack[node_id] = true;
154
155   for (const OutputSocketRef *from_socket : node.outputs()) {
156     for (const InputSocketRef *to_socket : from_socket->directly_linked_sockets()) {
157       const NodeRef &to_node = to_socket->node();
158       if (has_link_cycles_recursive(to_node, visited, is_in_stack)) {
159         return true;
160       }
161     }
162   }
163
164   is_in_stack[node_id] = false;
165   return false;
166 }
167
168 bool NodeTreeRef::has_link_cycles() const
169 {
170   const int node_amount = nodes_by_id_.size();
171   Array<bool> visited(node_amount, false);
172   Array<bool> is_in_stack(node_amount, false);
173
174   for (const NodeRef *node : nodes_by_id_) {
175     if (has_link_cycles_recursive(*node, visited, is_in_stack)) {
176       return true;
177     }
178   }
179   return false;
180 }
181
182 std::string NodeTreeRef::to_dot() const
183 {
184   dot::DirectedGraph digraph;
185   digraph.set_rankdir(dot::Attr_rankdir::LeftToRight);
186
187   Map<const NodeRef *, dot::NodeWithSocketsRef> dot_nodes;
188
189   for (const NodeRef *node : nodes_by_id_) {
190     dot::Node &dot_node = digraph.new_node("");
191     dot_node.set_background_color("white");
192
193     Vector<std::string> input_names;
194     Vector<std::string> output_names;
195     for (const InputSocketRef *socket : node->inputs()) {
196       input_names.append(socket->name());
197     }
198     for (const OutputSocketRef *socket : node->outputs()) {
199       output_names.append(socket->name());
200     }
201
202     dot_nodes.add_new(node,
203                       dot::NodeWithSocketsRef(dot_node, node->name(), input_names, output_names));
204   }
205
206   for (const OutputSocketRef *from_socket : output_sockets_) {
207     for (const InputSocketRef *to_socket : from_socket->directly_linked_sockets()) {
208       dot::NodeWithSocketsRef &from_dot_node = dot_nodes.lookup(&from_socket->node());
209       dot::NodeWithSocketsRef &to_dot_node = dot_nodes.lookup(&to_socket->node());
210
211       digraph.new_edge(from_dot_node.output(from_socket->index()),
212                        to_dot_node.input(to_socket->index()));
213     }
214   }
215
216   return digraph.to_dot_string();
217 }
218
219 }  // namespace blender::nodes