1 files changed, 87 insertions, 0 deletions
diff --git a/src/runtime/dragon/jobs/dragontreejobs.cpp b/src/runtime/dragon/jobs/dragontreejobs.cpp
index e60dc60..c3b01fc 100644
--- a/src/runtime/dragon/jobs/dragontreejobs.cpp
+++ b/src/runtime/dragon/jobs/dragontreejobs.cpp
@@ -33,6 +33,93 @@
 QT_BEGIN_NAMESPACE
 namespace Qt3DRender {
 namespace Dragon {
+
+TreeInfo generateInheritanceTable(TreeInfo inheritanceTable,
+                                  const NodeTree::Nodes hierarchy,
+                                  const ValueContainer<FrameGraphNode> nodes,
+                                  Qt3DCore::QNodeId rootEntityId)
+{
+    inheritanceTable.nodes.reset();
+
+    if (!nodes.anythingDirty())
+        return inheritanceTable;
+
+    const auto &changes = nodes.changes();
+    bool dirtyTree = false;
+    for (const auto &change : changes) {
+        if (change.action != Change::Action::Modified || change.info == Change::DirtyInfo::Tree) {
+            dirtyTree = true;
+            break;
+        }
+    }
+    if (!dirtyTree)
+        return inheritanceTable;
+
+    // Clear old data
+    inheritanceTable.leafNodes.clear();
+    inheritanceTable.nodes = synchronizeKeys(std::move(inheritanceTable.nodes), nodes);
+    inheritanceTable.rootNode = rootEntityId;
+
+    // Clear old data, set parent and find all children of all nodes
+    for (const auto &id : nodes.keys()) {
+        auto tableNode = *(inheritanceTable.nodes[id]);
+        inheritanceTable.nodes.markDirty(id);
+        inheritanceTable.nodes[id] = tableNode;
+    }
+
+
+    {
+        // Traverse the tree from top to bottom to add ancestor and descendant information
+        // using a depth-first search.
+        QStack<Qt3DCore::QNodeId> stack;
+        stack.push(rootEntityId);
+        while (!stack.isEmpty()) {
+            auto currentId = stack.pop();
+            QVector<Qt3DCore::QNodeId> currentAncestors = inheritanceTable.nodes[currentId]->ancestors
+                                                          + QVector<Qt3DCore::QNodeId>{{currentId}};
+
+            // NOTE: A copy is necessary, because we might insert into the map below
+            const QVector<Qt3DCore::QNodeId> children = hierarchy[currentId].childIds;
+            QVector<Qt3DCore::QNodeId> nodeChildren;
+            for (const auto &childId : children) {
+                if (nodes.contains(childId)) {
+                    nodeChildren.push_back(childId);
+                }
+            }
+
+            if (nodeChildren.isEmpty()) {
+                inheritanceTable.leafNodes.push_back(currentId);
+                continue;
+            }
+
+            // Iterate the children in reverse order (because the stack is last-in-first-out)
+            // TODO use std::reverse_iterator once we have C++17
+            for (auto it = nodeChildren.rbegin(); it != nodeChildren.rend(); ++it) {
+                const auto &childId = *it;
+                auto child = *inheritanceTable.nodes[childId];
+                child.ancestors = currentAncestors;
+                inheritanceTable.nodes[childId] = child;
+                // Go through all ancestors and add us as a child
+                for (const auto &ancestorId : qAsConst(currentAncestors)) {
+                    auto ancestor = *inheritanceTable.nodes[ancestorId];
+                    ancestor.descendants.push_back(childId);
+                    inheritanceTable.nodes[ancestorId] = ancestor;
+                }
+                // Only add if not added as one of the dirty nodes
+                stack.push(childId);
+            }
+        }
+        // Reverse all the ancestor lists
+        for (const auto &id : inheritanceTable.nodes.keys()) {
+            auto node = *inheritanceTable.nodes[id];
+            std::reverse(node.ancestors.begin(), node.ancestors.end());
+            inheritanceTable.nodes[id] = node;
+        }
+    }
+
+    return inheritanceTable;
+}
+
 } // namespace Dragon
 } // namespace Qt3DRender
 QT_END_NAMESPACE