Add function to find set of leaf blend node ids that need evaluating

We should only evaluate the clips that are actually dependencies of
the blend tree being evaluated given its current state. At present
this will simply be the set of all leaf nodes in the blend tree but
in the future when we support generalised lerp nodes etc, this will
yield the subset needed for the current state.

This involved adding support for pre-order traversal of the blend tree.
As a result, extended the visitor to work with both pre and post orders
and for all nodes or only the dependencies.

Note that we return the ids of the blend tree nodes, not the ids of
the clips themsevles. This is so we can then index the results by
blend node id in a later commit.

Change-Id: Ia13fe90ec3090306c1e8ade316ce0540f36a67fd
Reviewed-by: Mike Krus <mike.krus@kdab.com>

4 files changed, 176 insertions, 16 deletions

diff --git a/src/animation/backend/animationutils.cpp b/src/animation/backend/animationutils.cpp
index a60c530b4..910fa45cd 100644
--- a/src/animation/backend/animationutils.cpp
+++ b/src/animation/backend/animationutils.cpp
@@ -37,6 +37,9 @@
 #include "animationutils_p.h"
 #include <Qt3DAnimation/private/handler_p.h>
 #include <Qt3DAnimation/private/managers_p.h>
+#include <Qt3DAnimation/private/clipblendnode_p.h>
+#include <Qt3DAnimation/private/clipblendnodevisitor_p.h>
+#include <Qt3DAnimation/private/clipblendvalue_p.h>
 #include <Qt3DCore/qpropertyupdatedchange.h>
 #include <Qt3DCore/private/qpropertyupdatedchangebase_p.h>
 #include <QtGui/qvector2d.h>
@@ -59,9 +62,8 @@ ClipEvaluationData evaluationDataForClip(AnimationClipLoader *clip,
     result.localTime = localTimeFromGlobalTime(animatorData.globalTime, animatorData.startTime,
                                                animatorData.playbackRate, clip->duration(),
                                                animatorData.loopCount, result.currentLoop);
-    result.isFinalFrame = (result.localTime >= clip->duration() &&
-                           animatorData.loopCount != 0 &&
-                           result.currentLoop >= animatorData.loopCount - 1);
+    result.isFinalFrame = isFinalFrame(result.localTime, clip->duration(),
+                                       result.currentLoop, animatorData.loopCount);
     return result;
 }
 
@@ -333,6 +335,39 @@ QVector<MappingData> buildPropertyMappings(Handler *handler,
     return mappingDataVec;
 }
 
+QVector<Qt3DCore::QNodeId> gatherValueNodesToEvaluate(Handler *handler,
+                                                      Qt3DCore::QNodeId blendTreeRootId)
+{
+    Q_ASSERT(handler);
+    Q_ASSERT(blendTreeRootId.isNull() == false);
+
+    // We need the ClipBlendNodeManager to be able to lookup nodes from their Ids
+    ClipBlendNodeManager *nodeManager = handler->clipBlendNodeManager();
+
+    // Visit the tree in a pre-order manner and collect the dependencies
+    QVector<Qt3DCore::QNodeId> clipIds;
+    ClipBlendNodeVisitor visitor(nodeManager,
+                                 ClipBlendNodeVisitor::PreOrder,
+                                 ClipBlendNodeVisitor::VisitOnlyDependencies);
+
+    auto func = [&clipIds, nodeManager] (ClipBlendNode *blendNode) {
+        const auto dependencyIds = blendNode->dependencyIds();
+        for (const auto dependencyId : dependencyIds) {
+            // Look up the blend node and if it's a value type (clip),
+            // add it to the set of value node ids that need to be evaluated
+            ClipBlendNode *node = nodeManager->lookupNode(dependencyId);
+            if (node && node->blendType() == ClipBlendNode::ValueType)
+                clipIds.append(dependencyId);
+        }
+    };
+    visitor.traverse(blendTreeRootId, func);
+
+    // Sort and remove duplicates
+    std::sort(clipIds.begin(), clipIds.end());
+    auto last = std::unique(clipIds.begin(), clipIds.end());
+    clipIds.erase(last, clipIds.end());
+    return clipIds;
+}
 
 } // Animation
 } // Qt3DAnimation
diff --git a/src/animation/backend/animationutils_p.h b/src/animation/backend/animationutils_p.h
index 5434b2188..1b5a02033 100644
--- a/src/animation/backend/animationutils_p.h
+++ b/src/animation/backend/animationutils_p.h
@@ -111,6 +111,16 @@ AnimatorEvaluationData evaluationDataForAnimator(Animator animator, qint64 globa
     return data;
 }
 
+inline bool isFinalFrame(double localTime,
+                         double duration,
+                         int currentLoop,
+                         int loopCount)
+{
+    return (localTime >= duration &&
+            loopCount != 0 &&
+            currentLoop >= loopCount - 1);
+}
+
 Q_AUTOTEST_EXPORT
 ClipEvaluationData evaluationDataForClip(AnimationClipLoader *clip,
                                          const AnimatorEvaluationData &animatorData);
@@ -155,6 +165,10 @@ double phaseFromGlobalTime(double t_global, double t_start_global,
                            double playbackRate, double duration,
                            int loopCount, int &currentLoop);
 
+Q_AUTOTEST_EXPORT
+QVector<Qt3DCore::QNodeId> gatherValueNodesToEvaluate(Handler *handler,
+                                                      Qt3DCore::QNodeId blendTreeRootId);
+
 } // Animation
 } // Qt3DAnimation
 
diff --git a/src/animation/backend/clipblendnodevisitor.cpp b/src/animation/backend/clipblendnodevisitor.cpp
index 12533d2ca..a040892ad 100644
--- a/src/animation/backend/clipblendnodevisitor.cpp
+++ b/src/animation/backend/clipblendnodevisitor.cpp
@@ -41,35 +41,130 @@
 QT_BEGIN_NAMESPACE
 
 namespace Qt3DAnimation {
-
 namespace Animation {
 
-ClipBlendNodeVisitor::ClipBlendNodeVisitor(ClipBlendNodeManager *manager)
+/*!
+    \class ClipBlendNodeVisitor
+    \internal
+    Visits a blend tree in either pre- or post-order manner, optionally taking care
+    to only visit the nodes that are dependencies of evaluating the blend
+    tree.
+*/
+ClipBlendNodeVisitor::ClipBlendNodeVisitor(ClipBlendNodeManager *manager,
+                                           TraversalOrder order,
+                                           NodeFilter filter)
     : m_manager(manager)
+    , m_order(order)
+    , m_filter(filter)
 {
 }
 
-void ClipBlendNodeVisitor::traverse(Qt3DCore::QNodeId rootId, const VisitFunction &visitFunction) const
+void ClipBlendNodeVisitor::traverse(Qt3DCore::QNodeId rootId,
+                                    const VisitFunction &visitFunction) const
 {
     ClipBlendNode *node = m_manager->lookupNode(rootId);
-    if (node != nullptr)
-        visit(node, visitFunction);
+    if (node != nullptr) {
+        switch (m_order) {
+        case PreOrder: {
+            switch (m_filter) {
+            case VisitAllNodes:
+                visitPreOrderAllNodes(node, visitFunction);
+                break;
+
+            case VisitOnlyDependencies:
+                visitPreOrderDependencyNodes(node, visitFunction);
+                break;
+            }
+
+            break;
+        }
+
+        case PostOrder: {
+            switch (m_filter) {
+            case VisitAllNodes:
+                visitPostOrderAllNodes(node, visitFunction);
+                break;
+
+            case VisitOnlyDependencies:
+                visitPostOrderDependencyNodes(node, visitFunction);
+                break;
+            }
+
+            break;
+        }
+        }
+    }
 }
 
-// Leaf to root traversal (Post-order traversal)
-void ClipBlendNodeVisitor::visit(ClipBlendNode *node, const VisitFunction &visitFunction) const
+/*!
+    \internal
+    Leaf to root traversal (Pre-order traversal) visiting all nodes even if
+    they will not participate in current evaluation of the blend tree.
+*/
+void ClipBlendNodeVisitor::visitPreOrderAllNodes(ClipBlendNode *node,
+                                                 const VisitFunction &visitFunction) const
 {
+    visitFunction(node);
     const Qt3DCore::QNodeIdVector childIds = node->childrenIds();
     for (const Qt3DCore::QNodeId childId: childIds) {
         ClipBlendNode *childNode = m_manager->lookupNode(childId);
         if (childNode != nullptr)
-            visit(childNode, visitFunction);
+            visitPreOrderAllNodes(childNode, visitFunction);
+    }
+}
+
+/*!
+    \internal
+    Leaf to root traversal (Post-order traversal) visiting all nodes even if
+    they will not participate in current evaluation of the blend tree.
+*/
+void ClipBlendNodeVisitor::visitPostOrderAllNodes(ClipBlendNode *node,
+                                                  const VisitFunction &visitFunction) const
+{
+    const Qt3DCore::QNodeIdVector childIds = node->childrenIds();
+    for (const Qt3DCore::QNodeId childId: childIds) {
+        ClipBlendNode *childNode = m_manager->lookupNode(childId);
+        if (childNode != nullptr)
+            visitPostOrderAllNodes(childNode, visitFunction);
     }
     visitFunction(node);
 }
 
-} // Animation
+/*!
+    \internal
+    Leaf to root traversal (Pre-order traversal) visiting only nodes required
+    to evaluate the blend tree given its current state.
+*/
+void ClipBlendNodeVisitor::visitPreOrderDependencyNodes(ClipBlendNode *node,
+                                                        const VisitFunction &visitFunction) const
+{
+    visitFunction(node);
+    const Qt3DCore::QNodeIdVector childIds = node->dependencyIds();
+    for (const Qt3DCore::QNodeId childId: childIds) {
+        ClipBlendNode *childNode = m_manager->lookupNode(childId);
+        if (childNode != nullptr)
+            visitPreOrderDependencyNodes(childNode, visitFunction);
+    }
+}
+
+/*!
+    \internal
+    Leaf to root traversal (Post-order traversal) visiting only nodes required
+    to evaluate the blend tree given its current state.
+*/
+void ClipBlendNodeVisitor::visitPostOrderDependencyNodes(ClipBlendNode *node,
+                                                         const VisitFunction &visitFunction) const
+{
+    const Qt3DCore::QNodeIdVector childIds = node->dependencyIds();
+    for (const Qt3DCore::QNodeId childId: childIds) {
+        ClipBlendNode *childNode = m_manager->lookupNode(childId);
+        if (childNode != nullptr)
+            visitPostOrderDependencyNodes(childNode, visitFunction);
+    }
+    visitFunction(node);
+}
 
+} // Animation
 } // Qt3DAnimation
 
 QT_END_NAMESPACE
diff --git a/src/animation/backend/clipblendnodevisitor_p.h b/src/animation/backend/clipblendnodevisitor_p.h
index d619c7132..1bedb206a 100644
--- a/src/animation/backend/clipblendnodevisitor_p.h
+++ b/src/animation/backend/clipblendnodevisitor_p.h
@@ -55,7 +55,6 @@
 QT_BEGIN_NAMESPACE
 
 namespace Qt3DAnimation {
-
 namespace Animation {
 
 class ClipBlendNodeManager;
@@ -66,18 +65,35 @@ using VisitFunction = std::function<void (ClipBlendNode *)>;
 class Q_AUTOTEST_EXPORT ClipBlendNodeVisitor
 {
 public:
-    explicit ClipBlendNodeVisitor(ClipBlendNodeManager *manager);
+    enum TraversalOrder {
+        PreOrder,
+        PostOrder
+    };
+
+    enum NodeFilter {
+        VisitAllNodes,
+        VisitOnlyDependencies
+    };
+
+    explicit ClipBlendNodeVisitor(ClipBlendNodeManager *manager,
+                                  TraversalOrder order = PostOrder,
+                                  NodeFilter filter = VisitAllNodes);
 
     void traverse(Qt3DCore::QNodeId rootId, const VisitFunction &visitFunction) const;
 
 private:
-    void visit(ClipBlendNode *node, const VisitFunction &visitFunction) const;
+    void visitPreOrderAllNodes(ClipBlendNode *node, const VisitFunction &visitFunction) const;
+    void visitPostOrderAllNodes(ClipBlendNode *node, const VisitFunction &visitFunction) const;
+
+    void visitPreOrderDependencyNodes(ClipBlendNode *node, const VisitFunction &visitFunction) const;
+    void visitPostOrderDependencyNodes(ClipBlendNode *node, const VisitFunction &visitFunction) const;
 
     ClipBlendNodeManager *m_manager;
+    TraversalOrder m_order;
+    NodeFilter m_filter;
 };
 
 } // Animation
-
 } // Qt3DAnimation
 
 QT_END_NAMESPACE