1 | // Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #include "qshadergraph_p.h" |
5 | |
6 | QT_BEGIN_NAMESPACE |
7 | namespace Qt3DRender |
8 | { |
9 | |
10 | namespace |
11 | { |
12 | QList<QShaderNode> copyOutputNodes(const QList<QShaderNode> &nodes, const QList<QShaderGraph::Edge> &edges) |
13 | { |
14 | auto res = QList<QShaderNode>(); |
15 | std::copy_if(first: nodes.cbegin(), last: nodes.cend(), |
16 | result: std::back_inserter(x&: res), |
17 | pred: [&edges] (const QShaderNode &node) { |
18 | return node.type() == QShaderNode::Output || |
19 | (node.type() == QShaderNode::Function && |
20 | !std::any_of(first: edges.cbegin(), |
21 | last: edges.cend(), |
22 | pred: [&node] (const QShaderGraph::Edge &edge) { |
23 | return edge.sourceNodeUuid == |
24 | node.uuid(); |
25 | })); |
26 | }); |
27 | return res; |
28 | } |
29 | |
30 | QList<QShaderGraph::Edge> incomingEdges(const QList<QShaderGraph::Edge> &edges, const QUuid &uuid) |
31 | { |
32 | auto res = QList<QShaderGraph::Edge>(); |
33 | std::copy_if(first: edges.cbegin(), last: edges.cend(), |
34 | result: std::back_inserter(x&: res), |
35 | pred: [uuid] (const QShaderGraph::Edge &edge) { |
36 | return edge.sourceNodeUuid == uuid; |
37 | }); |
38 | return res; |
39 | } |
40 | |
41 | QList<QShaderGraph::Edge> outgoingEdges(const QList<QShaderGraph::Edge> &edges, const QUuid &uuid) |
42 | { |
43 | auto res = QList<QShaderGraph::Edge>(); |
44 | std::copy_if(first: edges.cbegin(), last: edges.cend(), |
45 | result: std::back_inserter(x&: res), |
46 | pred: [uuid] (const QShaderGraph::Edge &edge) { |
47 | return edge.targetNodeUuid == uuid; |
48 | }); |
49 | return res; |
50 | } |
51 | |
52 | QShaderGraph::Statement nodeToStatement(const QShaderNode &node, int &nextVarId) |
53 | { |
54 | auto statement = QShaderGraph::Statement(); |
55 | statement.node = node; |
56 | |
57 | const QList<QShaderNodePort> ports = node.ports(); |
58 | for (const QShaderNodePort &port : ports) { |
59 | if (port.direction == QShaderNodePort::Input) { |
60 | statement.inputs.append(t: -1); |
61 | } else { |
62 | statement.outputs.append(t: nextVarId); |
63 | nextVarId++; |
64 | } |
65 | } |
66 | return statement; |
67 | } |
68 | |
69 | QShaderGraph::Statement completeStatement(const QHash<QUuid, QShaderGraph::Statement> &idHash, |
70 | const QList<QShaderGraph::Edge> &edges, |
71 | const QUuid &uuid) |
72 | { |
73 | auto targetStatement = idHash.value(key: uuid); |
74 | for (const QShaderGraph::Edge &edge : edges) { |
75 | if (edge.targetNodeUuid != uuid) |
76 | continue; |
77 | |
78 | const QShaderGraph::Statement sourceStatement = idHash.value(key: edge.sourceNodeUuid); |
79 | const int sourcePortIndex = sourceStatement.portIndex(direction: QShaderNodePort::Output, portName: edge.sourcePortName); |
80 | const int targetPortIndex = targetStatement.portIndex(direction: QShaderNodePort::Input, portName: edge.targetPortName); |
81 | |
82 | if (sourcePortIndex < 0 || targetPortIndex < 0) |
83 | continue; |
84 | |
85 | const QList<int> sourceOutputs = sourceStatement.outputs; |
86 | QList<int> &targetInputs = targetStatement.inputs; |
87 | targetInputs[targetPortIndex] = sourceOutputs[sourcePortIndex]; |
88 | } |
89 | return targetStatement; |
90 | } |
91 | |
92 | void removeNodesWithUnboundInputs(QList<QShaderGraph::Statement> &statements, |
93 | const QList<QShaderGraph::Edge> &allEdges) |
94 | { |
95 | // A node is invalid if any of its input ports is disconected |
96 | // or connected to the output port of another invalid node. |
97 | |
98 | // Keeps track of the edges from the nodes we know to be valid |
99 | // to unvisited nodes |
100 | auto currentEdges = QList<QShaderGraph::Edge>(); |
101 | |
102 | statements.erase(abegin: std::remove_if(first: statements.begin(), |
103 | last: statements.end(), |
104 | pred: [¤tEdges, &allEdges] (const QShaderGraph::Statement &statement) { |
105 | const QShaderNode &node = statement.node; |
106 | const QList<QShaderGraph::Edge> outgoing = outgoingEdges(edges: currentEdges, uuid: node.uuid()); |
107 | const QList<QShaderNodePort> ports = node.ports(); |
108 | |
109 | bool allInputsConnected = true; |
110 | for (const QShaderNodePort &port : node.ports()) { |
111 | if (port.direction == QShaderNodePort::Output) |
112 | continue; |
113 | |
114 | const auto edgeIt = std::find_if(first: outgoing.cbegin(), |
115 | last: outgoing.cend(), |
116 | pred: [&port] (const QShaderGraph::Edge &edge) { |
117 | return edge.targetPortName == port.name; |
118 | }); |
119 | |
120 | if (edgeIt != outgoing.cend()) |
121 | currentEdges.removeAll(t: *edgeIt); |
122 | else |
123 | allInputsConnected = false; |
124 | } |
125 | |
126 | if (allInputsConnected) { |
127 | const QList<QShaderGraph::Edge> incoming = incomingEdges(edges: allEdges, uuid: node.uuid()); |
128 | currentEdges.append(l: incoming); |
129 | } |
130 | |
131 | return !allInputsConnected; |
132 | }), |
133 | aend: statements.end()); |
134 | } |
135 | } |
136 | |
137 | QUuid QShaderGraph::Statement::uuid() const noexcept |
138 | { |
139 | return node.uuid(); |
140 | } |
141 | |
142 | int QShaderGraph::Statement::portIndex(QShaderNodePort::Direction direction, const QString &portName) const noexcept |
143 | { |
144 | const QList<QShaderNodePort> ports = node.ports(); |
145 | int index = 0; |
146 | for (const QShaderNodePort &port : ports) { |
147 | if (port.name == portName && port.direction == direction) |
148 | return index; |
149 | else if (port.direction == direction) |
150 | index++; |
151 | } |
152 | return -1; |
153 | } |
154 | |
155 | void QShaderGraph::addNode(const QShaderNode &node) |
156 | { |
157 | removeNode(node); |
158 | m_nodes.append(t: node); |
159 | } |
160 | |
161 | void QShaderGraph::removeNode(const QShaderNode &node) |
162 | { |
163 | const auto it = std::find_if(first: m_nodes.begin(), last: m_nodes.end(), |
164 | pred: [node] (const QShaderNode &n) { return n.uuid() == node.uuid(); }); |
165 | if (it != m_nodes.end()) |
166 | m_nodes.erase(pos: it); |
167 | } |
168 | |
169 | QList<QShaderNode> QShaderGraph::nodes() const noexcept |
170 | { |
171 | return m_nodes; |
172 | } |
173 | |
174 | void QShaderGraph::addEdge(const QShaderGraph::Edge &edge) |
175 | { |
176 | if (m_edges.contains(t: edge)) |
177 | return; |
178 | m_edges.append(t: edge); |
179 | } |
180 | |
181 | void QShaderGraph::removeEdge(const QShaderGraph::Edge &edge) |
182 | { |
183 | m_edges.removeAll(t: edge); |
184 | } |
185 | |
186 | QList<QShaderGraph::Edge> QShaderGraph::edges() const noexcept |
187 | { |
188 | return m_edges; |
189 | } |
190 | |
191 | QList<QShaderGraph::Statement> QShaderGraph::createStatements(const QStringList &enabledLayers) const |
192 | { |
193 | const auto intersectsEnabledLayers = [enabledLayers] (const QStringList &layers) { |
194 | return layers.isEmpty() |
195 | || std::any_of(first: layers.cbegin(), last: layers.cend(), |
196 | pred: [enabledLayers] (const QString &s) { return enabledLayers.contains(str: s); }); |
197 | }; |
198 | |
199 | const QList<QShaderNode> enabledNodes = [this, intersectsEnabledLayers] { |
200 | auto res = QList<QShaderNode>(); |
201 | std::copy_if(first: m_nodes.cbegin(), last: m_nodes.cend(), |
202 | result: std::back_inserter(x&: res), |
203 | pred: [intersectsEnabledLayers] (const QShaderNode &node) { |
204 | return intersectsEnabledLayers(node.layers()); |
205 | }); |
206 | return res; |
207 | }(); |
208 | |
209 | const QHash<QUuid, Statement> idHash = [enabledNodes] { |
210 | auto nextVarId = 0; |
211 | auto res = QHash<QUuid, Statement>(); |
212 | for (const QShaderNode &node : enabledNodes) |
213 | res.insert(key: node.uuid(), value: nodeToStatement(node, nextVarId)); |
214 | return res; |
215 | }(); |
216 | |
217 | const QList<Edge> enabledEdges = [this, intersectsEnabledLayers, &idHash] { |
218 | auto res = QList<Edge>(); |
219 | std::copy_if(first: m_edges.cbegin(), last: m_edges.cend(), |
220 | result: std::back_inserter(x&: res), |
221 | pred: [intersectsEnabledLayers, &idHash] (const Edge &edge) { |
222 | return intersectsEnabledLayers(edge.layers) |
223 | && idHash.contains(key: edge.sourceNodeUuid) |
224 | && idHash.contains(key: edge.targetNodeUuid); |
225 | }); |
226 | return res; |
227 | }(); |
228 | |
229 | auto result = QList<Statement>(); |
230 | QList<Edge> currentEdges = enabledEdges; |
231 | QList<QUuid> currentUuids = [enabledNodes, enabledEdges] { |
232 | const QList<QShaderNode> inputs = copyOutputNodes(nodes: enabledNodes, edges: enabledEdges); |
233 | auto res = QList<QUuid>(); |
234 | std::transform(first: inputs.cbegin(), last: inputs.cend(), |
235 | result: std::back_inserter(x&: res), |
236 | unary_op: [](const QShaderNode &node) { return node.uuid(); }); |
237 | return res; |
238 | }(); |
239 | |
240 | // Implements Kahn's algorithm to flatten the graph |
241 | // https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm |
242 | // |
243 | // We implement it with a small twist though, we follow the edges backward |
244 | // because we want to track the dependencies from the output nodes and not the |
245 | // input nodes |
246 | while (!currentUuids.isEmpty()) { |
247 | const QUuid uuid = currentUuids.takeFirst(); |
248 | result.append(t: completeStatement(idHash, edges: enabledEdges, uuid)); |
249 | |
250 | const QList<QShaderGraph::Edge> outgoing = outgoingEdges(edges: currentEdges, uuid); |
251 | for (const QShaderGraph::Edge &outgoingEdge : outgoing) { |
252 | currentEdges.removeAll(t: outgoingEdge); |
253 | const QUuid nextUuid = outgoingEdge.sourceNodeUuid; |
254 | const QList<QShaderGraph::Edge> incoming = incomingEdges(edges: currentEdges, uuid: nextUuid); |
255 | if (incoming.isEmpty()) |
256 | currentUuids.append(t: nextUuid); |
257 | } |
258 | } |
259 | |
260 | std::reverse(first: result.begin(), last: result.end()); |
261 | |
262 | removeNodesWithUnboundInputs(statements&: result, allEdges: enabledEdges); |
263 | |
264 | return result; |
265 | } |
266 | |
267 | bool operator==(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge &rhs) noexcept |
268 | { |
269 | return lhs.sourceNodeUuid == rhs.sourceNodeUuid |
270 | && lhs.sourcePortName == rhs.sourcePortName |
271 | && lhs.targetNodeUuid == rhs.targetNodeUuid |
272 | && lhs.targetPortName == rhs.targetPortName; |
273 | } |
274 | |
275 | bool operator==(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) noexcept |
276 | { |
277 | return lhs.inputs == rhs.inputs |
278 | && lhs.outputs == rhs.outputs |
279 | && lhs.node.uuid() == rhs.node.uuid(); |
280 | } |
281 | } |
282 | QT_END_NAMESPACE |
283 | |