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
6QT_BEGIN_NAMESPACE
7namespace Qt3DRender
8{
9
10namespace
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: [&currentEdges, &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
137QUuid QShaderGraph::Statement::uuid() const noexcept
138{
139 return node.uuid();
140}
141
142int 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
155void QShaderGraph::addNode(const QShaderNode &node)
156{
157 removeNode(node);
158 m_nodes.append(t: node);
159}
160
161void 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
169QList<QShaderNode> QShaderGraph::nodes() const noexcept
170{
171 return m_nodes;
172}
173
174void QShaderGraph::addEdge(const QShaderGraph::Edge &edge)
175{
176 if (m_edges.contains(t: edge))
177 return;
178 m_edges.append(t: edge);
179}
180
181void QShaderGraph::removeEdge(const QShaderGraph::Edge &edge)
182{
183 m_edges.removeAll(t: edge);
184}
185
186QList<QShaderGraph::Edge> QShaderGraph::edges() const noexcept
187{
188 return m_edges;
189}
190
191QList<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
267bool 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
275bool 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}
282QT_END_NAMESPACE
283

source code of qt3d/src/render/shadergraph/qshadergraph.cpp