Add function to evaluate a blend tree

Turns out with this design, evaluating the blend tree is actually
really simple. Visit the tree nodes and call blend on the interior
nodes. The leaf nodes will already have their values from an
earlier stage.

This also makes apparent yet another opportunity for parallelism
during the blend tree evaluation. The blend tree may contain
independent subtrees that can safely be evaluated in parallel.

Once we have the ability for jobs to spawn jobs there are at
least 3 ways we can have parallelism in the blend tree evaluation:

1) Each blended clip animator can be processed in its own job.
2) Sub trees of the blend tree can be evaluated in parallel,
   relying upon dependencies between jobs to do this properly.
3) Within each node's doBlend() there is potential to use a
   parallel implementation of the map operation like parallel_for
   in TBB.

There are also other opportunities in earlier stages of processing
such as when evaluating the actual clips, we then need a gather
operation to map the clip results into the layout used by the
blend tree. This evaluations could be done in parallel as well as
a parallel gather (which is just a map with a random access read
operation).

This all bodes well for being able to process large numbers of
animations each containing large numbers of channels which will
be needed when we add support for skeletons.

Change-Id: Id81e3a5e563a7ef9b7ac39b90c518c656cf8a3cf
Reviewed-by: Paul Lemire <paul.lemire@kdab.com>
Reviewed-by: Mike Krus <mike.krus@kdab.com>

4 files changed, 44 insertions, 4 deletions

diff --git a/src/animation/backend/animationutils.cpp b/src/animation/backend/animationutils.cpp
index b96292eb9..8f1a681d4 100644
--- a/src/animation/backend/animationutils.cpp
+++ b/src/animation/backend/animationutils.cpp
@@ -369,6 +369,42 @@ QVector<Qt3DCore::QNodeId> gatherValueNodesToEvaluate(Handler *handler,
     return clipIds;
 }
 
+ClipResults evaluateBlendTree(Handler *handler,
+                              BlendedClipAnimator *animator,
+                              Qt3DCore::QNodeId blendTreeRootId)
+{
+    Q_ASSERT(handler);
+    Q_ASSERT(blendTreeRootId.isNull() == false);
+    const Qt3DCore::QNodeId animatorId = animator->peerId();
+
+    // We need the ClipBlendNodeManager to be able to lookup nodes from their Ids
+    ClipBlendNodeManager *nodeManager = handler->clipBlendNodeManager();
+
+    // Visit the tree in a post-order manner and for each interior node call
+    // blending function. We only need to visit the nodes that affect the blend
+    // tree at this time.
+    ClipBlendNodeVisitor visitor(nodeManager,
+                                 ClipBlendNodeVisitor::PostOrder,
+                                 ClipBlendNodeVisitor::VisitOnlyDependencies);
+
+    // TODO: When jobs can spawn other jobs we could evaluate subtrees of
+    // the blend tree in parallel. Since it's just a dependency tree, it maps
+    // simply onto the dependencies between jobs.
+    auto func = [animatorId] (ClipBlendNode *blendNode) {
+        // Look up the blend node and if it's an interior node, perform
+        // the blend operation
+        if (blendNode->blendType() != ClipBlendNode::ValueType)
+            blendNode->performBlend(animatorId);
+    };
+    visitor.traverse(blendTreeRootId, func);
+
+    // The clip results stored in the root node for this animator
+    // now represent the result of the blend tree evaluation
+    ClipBlendNode *blendTreeRootNode = nodeManager->lookupNode(blendTreeRootId);
+    Q_ASSERT(blendTreeRootNode);
+    return blendTreeRootNode->clipResults(animatorId);
+}
+
 } // Animation
 } // Qt3DAnimation
 
diff --git a/src/animation/backend/animationutils_p.h b/src/animation/backend/animationutils_p.h
index 83946273c..da85451f8 100644
--- a/src/animation/backend/animationutils_p.h
+++ b/src/animation/backend/animationutils_p.h
@@ -58,6 +58,7 @@ namespace Qt3DAnimation {
 namespace Animation {
 
 struct Channel;
+class BlendedClipAnimator;
 class Handler;
 class AnimationClipLoader;
 class ChannelMapper;
@@ -171,6 +172,11 @@ Q_AUTOTEST_EXPORT
 QVector<Qt3DCore::QNodeId> gatherValueNodesToEvaluate(Handler *handler,
                                                       Qt3DCore::QNodeId blendTreeRootId);
 
+Q_AUTOTEST_EXPORT
+ClipResults evaluateBlendTree(Handler *handler,
+                              BlendedClipAnimator *animator,
+                              Qt3DCore::QNodeId blendNodeId);
+
 } // Animation
 } // Qt3DAnimation
 
diff --git a/src/animation/backend/blendedclipanimator_p.h b/src/animation/backend/blendedclipanimator_p.h
index aff8b97fd..345cb874c 100644
--- a/src/animation/backend/blendedclipanimator_p.h
+++ b/src/animation/backend/blendedclipanimator_p.h
@@ -80,6 +80,7 @@ public:
     void setStartTime(qint64 globalTime) { m_startGlobalTime = globalTime; }
     qint64 startTime() const { return m_startGlobalTime; }
 
+    void setLoops(int loops) { m_loops = loops; }
     int loops() const { return m_loops; }
 
     int currentLoop() const { return m_currentLoop; }
diff --git a/src/animation/backend/clipblendnode_p.h b/src/animation/backend/clipblendnode_p.h
index b4eceb2c1..17e219dd4 100644
--- a/src/animation/backend/clipblendnode_p.h
+++ b/src/animation/backend/clipblendnode_p.h
@@ -84,9 +84,9 @@ public:
 
     // TODO: Remove this old blend() virtual and rename performBlend() to blend()
     virtual float blend(float value1, float value2) const = 0;
-
     void performBlend(Qt3DCore::QNodeId animatorId);
 
+    void setClipResults(Qt3DCore::QNodeId animatorId, const ClipResults &clipResults);
     ClipResults clipResults(Qt3DCore::QNodeId animatorId) const;
 
     virtual QVector<Qt3DCore::QNodeId> dependencyIds() const = 0;
@@ -95,9 +95,6 @@ public:
 protected:
     explicit ClipBlendNode(BlendType blendType);
     void initializeFromPeer(const Qt3DCore::QNodeCreatedChangeBasePtr &change) Q_DECL_OVERRIDE;
-
-    void setClipResults(Qt3DCore::QNodeId animatorId, const ClipResults &clipResults);
-
     virtual ClipResults doBlend(const QVector<ClipResults> &blendData) const = 0;
 
 private: