From 42124518844034f786ac1c434dd54c0a300b0999 Mon Sep 17 00:00:00 2001 From: Kevin Ottens Date: Thu, 30 Mar 2017 09:29:14 +0200 Subject: [Shader Graph Gen.] Introduce QShaderGraph::Statement This is our "byte code" representing a flattened graph. It will be used as input for the code generation. Change-Id: Ie02a60d07c035f3d16872e79931eb7cde168a8d1 Reviewed-by: Sean Harmer --- src/gui/util/qshadergraph.cpp | 148 ++++++++++++++++++++++++++++++++++++++++++ src/gui/util/qshadergraph_p.h | 22 +++++++ 2 files changed, 170 insertions(+) (limited to 'src/gui/util') diff --git a/src/gui/util/qshadergraph.cpp b/src/gui/util/qshadergraph.cpp index 0735c3cfe3..5379e6ed7a 100644 --- a/src/gui/util/qshadergraph.cpp +++ b/src/gui/util/qshadergraph.cpp @@ -41,6 +41,101 @@ QT_BEGIN_NAMESPACE + +namespace +{ + QVector copyOutputNodes(const QVector &nodes) + { + auto res = QVector(); + std::copy_if(nodes.cbegin(), nodes.cend(), + std::back_inserter(res), + [] (const QShaderNode &node) { + return node.type() == QShaderNode::Output; + }); + return res; + } + + QVector incomingEdges(const QVector &edges, const QUuid &uuid) + { + auto res = QVector(); + std::copy_if(edges.cbegin(), edges.cend(), + std::back_inserter(res), + [uuid] (const QShaderGraph::Edge &edge) { + return edge.sourceNodeUuid == uuid; + }); + return res; + } + + QVector outgoingEdges(const QVector &edges, const QUuid &uuid) + { + auto res = QVector(); + std::copy_if(edges.cbegin(), edges.cend(), + std::back_inserter(res), + [uuid] (const QShaderGraph::Edge &edge) { + return edge.targetNodeUuid == uuid; + }); + return res; + } + + QShaderGraph::Statement nodeToStatement(const QShaderNode &node, int &nextVarId) + { + auto statement = QShaderGraph::Statement(); + statement.node = node; + + const auto ports = node.ports(); + for (const auto &port : ports) { + if (port.direction == QShaderNodePort::Input) { + statement.inputs.append(-1); + } else { + statement.outputs.append(nextVarId); + nextVarId++; + } + } + return statement; + } + + QShaderGraph::Statement completeStatement(const QHash &idHash, + const QVector edges, + const QUuid &uuid) + { + auto targetStatement = idHash.value(uuid); + for (const auto &edge : edges) { + if (edge.targetNodeUuid != uuid) + continue; + + const auto sourceStatement = idHash.value(edge.sourceNodeUuid); + const auto sourcePortIndex = sourceStatement.portIndex(QShaderNodePort::Output, edge.sourcePortName); + const auto targetPortIndex = targetStatement.portIndex(QShaderNodePort::Input, edge.targetPortName); + + if (sourcePortIndex < 0 || targetPortIndex < 0) + continue; + + const auto &sourceOutputs = sourceStatement.outputs; + auto &targetInputs = targetStatement.inputs; + targetInputs[targetPortIndex] = sourceOutputs[sourcePortIndex]; + } + return targetStatement; + } +} + +QUuid QShaderGraph::Statement::uuid() const Q_DECL_NOTHROW +{ + return node.uuid(); +} + +int QShaderGraph::Statement::portIndex(QShaderNodePort::Direction direction, const QString &portName) const Q_DECL_NOTHROW +{ + const auto ports = node.ports(); + int index = 0; + for (const auto &port : ports) { + if (port.name == portName && port.direction == direction) + return index; + else if (port.direction == direction) + index++; + } + return -1; +} + void QShaderGraph::addNode(const QShaderNode &node) { removeNode(node); @@ -77,6 +172,52 @@ QVector QShaderGraph::edges() const Q_DECL_NOTHROW return m_edges; } +QVector QShaderGraph::createStatements() const +{ + const auto idHash = [this] { + auto nextVarId = 0; + auto res = QHash(); + for (const auto &node : qAsConst(m_nodes)) + res.insert(node.uuid(), nodeToStatement(node, nextVarId)); + return res; + }(); + + auto result = QVector(); + auto currentEdges = m_edges; + auto currentUuids = [this] { + const auto inputs = copyOutputNodes(m_nodes); + auto res = QVector(); + std::transform(inputs.cbegin(), inputs.cend(), + std::back_inserter(res), + [](const QShaderNode &node) { return node.uuid(); }); + return res; + }(); + + // Implements Kahn's algorithm to flatten the graph + // https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm + // + // We implement it with a small twist though, we follow the edges backward + // because we want to track the dependencies from the output nodes and not the + // input nodes + while (!currentUuids.isEmpty()) { + const auto uuid = currentUuids.takeFirst(); + result.append(completeStatement(idHash, m_edges, uuid)); + + const auto outgoing = outgoingEdges(currentEdges, uuid); + for (const auto &outgoingEdge : outgoing) { + currentEdges.removeAll(outgoingEdge); + const QUuid nextUuid = outgoingEdge.sourceNodeUuid; + const auto incoming = incomingEdges(currentEdges, nextUuid); + if (incoming.isEmpty()) { + currentUuids.append(nextUuid); + } + } + } + + std::reverse(result.begin(), result.end()); + return result; +} + bool operator==(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge &rhs) Q_DECL_NOTHROW { return lhs.sourceNodeUuid == rhs.sourceNodeUuid @@ -85,4 +226,11 @@ bool operator==(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge &rhs) Q_ && lhs.targetPortName == rhs.targetPortName; } +bool operator==(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) Q_DECL_NOTHROW +{ + return lhs.inputs == rhs.inputs + && lhs.outputs == rhs.outputs + && lhs.node.uuid() == rhs.node.uuid(); +} + QT_END_NAMESPACE diff --git a/src/gui/util/qshadergraph_p.h b/src/gui/util/qshadergraph_p.h index c582dcd18b..fd8ddf6e05 100644 --- a/src/gui/util/qshadergraph_p.h +++ b/src/gui/util/qshadergraph_p.h @@ -69,6 +69,17 @@ public: QString targetPortName; }; + class Statement + { + public: + Q_GUI_EXPORT QUuid uuid() const Q_DECL_NOTHROW; + Q_GUI_EXPORT int portIndex(QShaderNodePort::Direction direction, const QString &portName) const Q_DECL_NOTHROW; + + QShaderNode node; + QVector inputs; + QVector outputs; + }; + Q_GUI_EXPORT void addNode(const QShaderNode &node); Q_GUI_EXPORT void removeNode(const QShaderNode &node); Q_GUI_EXPORT QVector nodes() const Q_DECL_NOTHROW; @@ -77,6 +88,8 @@ public: Q_GUI_EXPORT void removeEdge(const Edge &edge); Q_GUI_EXPORT QVector edges() const Q_DECL_NOTHROW; + Q_GUI_EXPORT QVector createStatements() const; + private: QVector m_nodes; QVector m_edges; @@ -89,12 +102,21 @@ inline bool operator!=(const QShaderGraph::Edge &lhs, const QShaderGraph::Edge & return !(lhs == rhs); } +Q_GUI_EXPORT bool operator==(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) Q_DECL_NOTHROW; + +inline bool operator!=(const QShaderGraph::Statement &lhs, const QShaderGraph::Statement &rhs) Q_DECL_NOTHROW +{ + return !(lhs == rhs); +} + Q_DECLARE_TYPEINFO(QShaderGraph, Q_MOVABLE_TYPE); Q_DECLARE_TYPEINFO(QShaderGraph::Edge, Q_MOVABLE_TYPE); +Q_DECLARE_TYPEINFO(QShaderGraph::Statement, Q_MOVABLE_TYPE); QT_END_NAMESPACE Q_DECLARE_METATYPE(QShaderGraph) Q_DECLARE_METATYPE(QShaderGraph::Edge) +Q_DECLARE_METATYPE(QShaderGraph::Statement) #endif // QSHADERGRAPH_P_H -- cgit v1.2.3