1/****************************************************************************
2**
3** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB).
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtGui module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qshadergraph_p.h"
41
42QT_BEGIN_NAMESPACE
43namespace Qt3DRender
44{
45
46namespace
47{
48 QVector<QShaderNode> copyOutputNodes(const QVector<QShaderNode> &nodes, const QVector<QShaderGraph::Edge> &edges)
49 {
50 auto res = QVector<QShaderNode>();
51 std::copy_if(first: nodes.cbegin(), last: nodes.cend(),
52 result: std::back_inserter(x&: res),
53 pred: [&edges] (const QShaderNode &node) {
54 return node.type() == QShaderNode::Output ||
55 (node.type() == QShaderNode::Function &&
56 !std::any_of(first: edges.cbegin(),
57 last: edges.cend(),
58 pred: [&node] (const QShaderGraph::Edge &edge) {
59 return edge.sourceNodeUuid ==
60 node.uuid();
61 }));
62 });
63 return res;
64 }
65
66 QVector<QShaderGraph::Edge> incomingEdges(const QVector<QShaderGraph::Edge> &edges, const QUuid &uuid)
67 {
68 auto res = QVector<QShaderGraph::Edge>();
69 std::copy_if(first: edges.cbegin(), last: edges.cend(),
70 result: std::back_inserter(x&: res),
71 pred: [uuid] (const QShaderGraph::Edge &edge) {
72 return edge.sourceNodeUuid == uuid;
73 });
74 return res;
75 }
76
77 QVector<QShaderGraph::Edge> outgoingEdges(const QVector<QShaderGraph::Edge> &edges, const QUuid &uuid)
78 {
79 auto res = QVector<QShaderGraph::Edge>();
80 std::copy_if(first: edges.cbegin(), last: edges.cend(),
81 result: std::back_inserter(x&: res),
82 pred: [uuid] (const QShaderGraph::Edge &edge) {
83 return edge.targetNodeUuid == uuid;
84 });
85 return res;
86 }
87
88 QShaderGraph::Statement nodeToStatement(const QShaderNode &node, int &nextVarId)
89 {
90 auto statement = QShaderGraph::Statement();
91 statement.node = node;
92
93 const QVector<QShaderNodePort> ports = node.ports();
94 for (const QShaderNodePort &port : ports) {
95 if (port.direction == QShaderNodePort::Input) {
96 statement.inputs.append(t: -1);
97 } else {
98 statement.outputs.append(t: nextVarId);
99 nextVarId++;
100 }
101 }
102 return statement;
103 }
104
105 QShaderGraph::Statement completeStatement(const QHash<QUuid, QShaderGraph::Statement> &idHash,
106 const QVector<QShaderGraph::Edge> edges,
107 const QUuid &uuid)
108 {
109 auto targetStatement = idHash.value(akey: uuid);
110 for (const QShaderGraph::Edge &edge : edges) {
111 if (edge.targetNodeUuid != uuid)
112 continue;
113
114 const QShaderGraph::Statement sourceStatement = idHash.value(akey: edge.sourceNodeUuid);
115 const int sourcePortIndex = sourceStatement.portIndex(direction: QShaderNodePort::Output, portName: edge.sourcePortName);
116 const int targetPortIndex = targetStatement.portIndex(direction: QShaderNodePort::Input, portName: edge.targetPortName);
117
118 if (sourcePortIndex < 0 || targetPortIndex < 0)
119 continue;
120
121 const QVector<int> sourceOutputs = sourceStatement.outputs;
122 QVector<int> &targetInputs = targetStatement.inputs;
123 targetInputs[targetPortIndex] = sourceOutputs[sourcePortIndex];
124 }
125 return targetStatement;
126 }
127
128 void removeNodesWithUnboundInputs(QVector<QShaderGraph::Statement> &statements,
129 const QVector<QShaderGraph::Edge> &allEdges)
130 {
131 // A node is invalid if any of its input ports is disconected
132 // or connected to the output port of another invalid node.
133
134 // Keeps track of the edges from the nodes we know to be valid
135 // to unvisited nodes
136 auto currentEdges = QVector<QShaderGraph::Edge>();
137
138 statements.erase(abegin: std::remove_if(first: statements.begin(),
139 last: statements.end(),
140 pred: [&currentEdges, &allEdges] (const QShaderGraph::Statement &statement) {
141 const QShaderNode &node = statement.node;
142 const QVector<QShaderGraph::Edge> outgoing = outgoingEdges(edges: currentEdges, uuid: node.uuid());
143 const QVector<QShaderNodePort> ports = node.ports();
144
145 bool allInputsConnected = true;
146 for (const QShaderNodePort &port : node.ports()) {
147 if (port.direction == QShaderNodePort::Output)
148 continue;
149
150 const auto edgeIt = std::find_if(first: outgoing.cbegin(),
151 last: outgoing.cend(),
152 pred: [&port] (const QShaderGraph::Edge &edge) {
153 return edge.targetPortName == port.name;
154 });
155
156 if (edgeIt != outgoing.cend())
157 currentEdges.removeAll(t: *edgeIt);
158 else
159 allInputsConnected = false;
160 }
161
162 if (allInputsConnected) {
163 const QVector<QShaderGraph::Edge> incoming = incomingEdges(edges: allEdges, uuid: node.uuid());
164 currentEdges.append(l: incoming);
165 }
166
167 return !allInputsConnected;
168 }),
169 aend: statements.end());
170 }
171}
172
173QUuid QShaderGraph::Statement::uuid() const noexcept
174{
175 return node.uuid();
176}
177
178int QShaderGraph::Statement::portIndex(QShaderNodePort::Direction direction, const QString &portName) const noexcept
179{
180 const QVector<QShaderNodePort> ports = node.ports();
181 int index = 0;
182 for (const QShaderNodePort &port : ports) {
183 if (port.name == portName && port.direction == direction)
184 return index;
185 else if (port.direction == direction)
186 index++;
187 }
188 return -1;
189}
190
191void QShaderGraph::addNode(const QShaderNode &node)
192{
193 removeNode(node);
194 m_nodes.append(t: node);
195}
196
197void QShaderGraph::removeNode(const QShaderNode &node)
198{
199 const auto it = std::find_if(first: m_nodes.begin(), last: m_nodes.end(),
200 pred: [node] (const QShaderNode &n) { return n.uuid() == node.uuid(); });
201 if (it != m_nodes.end())
202 m_nodes.erase(pos: it);
203}
204
205QVector<QShaderNode> QShaderGraph::nodes() const noexcept
206{
207 return m_nodes;
208}
209
210void QShaderGraph::addEdge(const QShaderGraph::Edge &edge)
211{
212 if (m_edges.contains(t: edge))
213 return;
214 m_edges.append(t: edge);
215}
216
217void QShaderGraph::removeEdge(const QShaderGraph::Edge &edge)
218{
219 m_edges.removeAll(t: edge);
220}
221
222QVector<QShaderGraph::Edge> QShaderGraph::edges() const noexcept
223{
224 return m_edges;
225}
226
227QVector<QShaderGraph::Statement> QShaderGraph::createStatements(const QStringList &enabledLayers) const
228{
229 const auto intersectsEnabledLayers = [enabledLayers] (const QStringList &layers) {
230 return layers.isEmpty()
231 || std::any_of(first: layers.cbegin(), last: layers.cend(),
232 pred: [enabledLayers] (const QString &s) { return enabledLayers.contains(str: s); });
233 };
234
235 const QVector<QShaderNode> enabledNodes = [this, intersectsEnabledLayers] {
236 auto res = QVector<QShaderNode>();
237 std::copy_if(first: m_nodes.cbegin(), last: m_nodes.cend(),
238 result: std::back_inserter(x&: res),
239 pred: [intersectsEnabledLayers] (const QShaderNode &node) {
240 return intersectsEnabledLayers(node.layers());
241 });
242 return res;
243 }();
244
245 const QHash<QUuid, Statement> idHash = [enabledNodes] {
246 auto nextVarId = 0;
247 auto res = QHash<QUuid, Statement>();
248 for (const QShaderNode &node : enabledNodes)
249 res.insert(akey: node.uuid(), avalue: nodeToStatement(node, nextVarId));
250 return res;
251 }();
252
253 const QVector<Edge> enabledEdges = [this, intersectsEnabledLayers, &idHash] {
254 auto res = QVector<Edge>();
255 std::copy_if(first: m_edges.cbegin(), last: m_edges.cend(),
256 result: std::back_inserter(x&: res),
257 pred: [intersectsEnabledLayers, &idHash] (const Edge &edge) {
258 return intersectsEnabledLayers(edge.layers)
259 && idHash.contains(akey: edge.sourceNodeUuid)
260 && idHash.contains(akey: edge.targetNodeUuid);
261 });
262 return res;
263 }();
264
265 auto result = QVector<Statement>();
266 QVector<Edge> currentEdges = enabledEdges;
267 QVector<QUuid> currentUuids = [enabledNodes, enabledEdges] {
268 const QVector<QShaderNode> inputs = copyOutputNodes(nodes: enabledNodes, edges: enabledEdges);
269 auto res = QVector<QUuid>();
270 std::transform(first: inputs.cbegin(), last: inputs.cend(),
271 result: std::back_inserter(x&: res),
272 unary_op: [](const QShaderNode &node) { return node.uuid(); });
273 return res;
274 }();
275
276 // Implements Kahn's algorithm to flatten the graph
277 // https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
278 //
279 // We implement it with a small twist though, we follow the edges backward
280 // because we want to track the dependencies from the output nodes and not the
281 // input nodes
282 while (!currentUuids.isEmpty()) {
283 const QUuid uuid = currentUuids.takeFirst();
284 result.append(t: completeStatement(idHash, edges: enabledEdges, uuid));
285
286 const QVector<QShaderGraph::Edge> outgoing = outgoingEdges(edges: currentEdges, uuid);
287 for (const QShaderGraph::Edge &outgoingEdge : outgoing) {
288 currentEdges.removeAll(t: outgoingEdge);
289 const QUuid nextUuid = outgoingEdge.sourceNodeUuid;
290 const QVector<QShaderGraph::Edge> incoming = incomingEdges(edges: currentEdges, uuid: nextUuid);
291 if (incoming.isEmpty()) {
292 currentUuids.append(t: nextUuid);
293 }
294 }
295 }
296
297 std::reverse(first: result.begin(), last: result.end());
298
299 removeNodesWithUnboundInputs(statements&: result, allEdges: enabledEdges);
300
301 return result;
302}
303
304bool operator==(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge &rhs) noexcept
305{
306 return lhs.sourceNodeUuid == rhs.sourceNodeUuid
307 && lhs.sourcePortName == rhs.sourcePortName
308 && lhs.targetNodeUuid == rhs.targetNodeUuid
309 && lhs.targetPortName == rhs.targetPortName;
310}
311
312bool operator==(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) noexcept
313{
314 return lhs.inputs == rhs.inputs
315 && lhs.outputs == rhs.outputs
316 && lhs.node.uuid() == rhs.node.uuid();
317}
318}
319QT_END_NAMESPACE
320

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