[skottie] Power-reduce paths (cubicTo -> lineTo)

For straight lines, Lottie exports control points conincident with the
vertices.  We can detect this case and emit more efficient lineTo's.

One wrinkle: we can only apply this power-reduction post-interpolation
(otherwise the path verbs and point count would not be guaranteed to
match).  Hence we store explicit shape data and defer the SkPath
conversion.

TBR=

Change-Id: I7818be464eabee6096d2078440843243a55c6e98
Reviewed-on: https://skia-review.googlesource.com/124800
Reviewed-by: Florin Malita <fmalita@chromium.org>
Commit-Queue: Florin Malita <fmalita@chromium.org>

5 files changed, 134 insertions, 60 deletions

diff --git a/experimental/skottie/Skottie.cpp b/experimental/skottie/Skottie.cpp
index bb98ad75f0..1b5886eee0 100644
--- a/experimental/skottie/Skottie.cpp
+++ b/experimental/skottie/Skottie.cpp
@@ -149,7 +149,9 @@ sk_sp<sksg::RenderNode> AttachComposition(const Json::Value&, AttachContext* ctx
 sk_sp<sksg::Path> AttachPath(const Json::Value& jpath, AttachContext* ctx) {
     auto path_node = sksg::Path::Make();
     return BindProperty<ShapeValue>(jpath, &ctx->fAnimators,
-            [path_node](const ShapeValue& p) { path_node->setPath(p); })
+        [path_node](const ShapeValue& p) {
+            path_node->setPath(ValueTraits<ShapeValue>::As<SkPath>(p));
+        })
         ? path_node
         : nullptr;
 }
diff --git a/experimental/skottie/SkottieAnimator.cpp b/experimental/skottie/SkottieAnimator.cpp
index 5f8d0db89e..34803e05b5 100644
--- a/experimental/skottie/SkottieAnimator.cpp
+++ b/experimental/skottie/SkottieAnimator.cpp
@@ -27,41 +27,6 @@ bool LogFail(const Json::Value& json, const char* msg) {
     return false;
 }
 
-template <typename T>
-static inline T lerp(const T&, const T&, float);
-
-template <>
-ScalarValue lerp(const ScalarValue& v0, const ScalarValue& v1, float t) {
-    SkASSERT(t >= 0 && t <= 1);
-    return v0 + (v1 - v0) * t;
-}
-
-template <>
-VectorValue lerp(const VectorValue& v0, const VectorValue& v1, float t) {
-    SkASSERT(v0.size() == v1.size());
-
-    VectorValue v;
-    v.reserve(v0.size());
-
-    for (size_t i = 0; i < v0.size(); ++i) {
-        v.push_back(lerp(v0[i], v1[i], t));
-    }
-
-    return v;
-}
-
-template <>
-ShapeValue lerp(const ShapeValue& v0, const ShapeValue& v1, float t) {
-    SkASSERT(t >= 0 && t <= 1);
-    SkASSERT(v1.isInterpolatable(v0));
-
-    ShapeValue v;
-    SkAssertResult(v1.interpolate(v0, t, &v));
-    v.setIsVolatile(true);
-
-    return v;
-}
-
 class KeyframeAnimatorBase : public sksg::Animator {
 public:
     int count() const { return fRecs.count(); }
@@ -264,7 +229,7 @@ private:
             const auto lt = this->localT(rec, t);
             const auto& v0 = fVs[rec.vidx0];
             const auto& v1 = fVs[rec.vidx1];
-            *v = lerp(v0, v1, lt);
+            *v = ValueTraits<T>::Lerp(v0, v1, lt);
         }
     }
 
diff --git a/experimental/skottie/SkottieParser.cpp b/experimental/skottie/SkottieParser.cpp
index 24603bf828..36690036d2 100644
--- a/experimental/skottie/SkottieParser.cpp
+++ b/experimental/skottie/SkottieParser.cpp
@@ -12,6 +12,7 @@
 #include "SkPath.h"
 #include "SkPoint.h"
 #include "SkString.h"
+#include "SkottieValue.h"
 
 #include <vector>
 
@@ -113,8 +114,8 @@ bool ParsePointVec(const Json::Value& jv, std::vector<SkPoint>* pts) {
 } // namespace
 
 template <>
-bool Parse<SkPath>(const Json::Value& jv, SkPath* v) {
-    SkASSERT(v->isEmpty());
+bool Parse<ShapeValue>(const Json::Value& jv, ShapeValue* v) {
+    SkASSERT(v->fVertices.empty());
 
     // Some versions wrap values as single-element arrays.
     if (jv.isArray() && jv.size() == 1) {
@@ -135,24 +136,11 @@ bool Parse<SkPath>(const Json::Value& jv, SkPath* v) {
         return false;
     }
 
-    if (!verts.empty()) {
-        v->moveTo(verts.front());
-    }
-
-    const auto& addCubic = [&](size_t from, size_t to) {
-        v->cubicTo(verts[from] + outPts[from],
-                   verts[to]   + inPts[to],
-                   verts[to]);
-    };
-
-    for (size_t i = 1; i < verts.size(); ++i) {
-        addCubic(i - 1, i);
-    }
-
-    if (!verts.empty() && ParseDefault(jv["c"], false)) {
-        addCubic(verts.size() - 1, 0);
-        v->close();
+    v->fVertices.reserve(inPts.size());
+    for (size_t i = 0; i < inPts.size(); ++i) {
+        v->fVertices.push_back(BezierVertex({inPts[i], outPts[i], verts[i]}));
     }
+    v->fClosed = ParseDefault(jv["c"], false);
 
     return true;
 }
diff --git a/experimental/skottie/SkottieValue.cpp b/experimental/skottie/SkottieValue.cpp
index 386c8ab623..edfa891aa1 100644
--- a/experimental/skottie/SkottieValue.cpp
+++ b/experimental/skottie/SkottieValue.cpp
@@ -8,6 +8,7 @@
 #include "SkottieValue.h"
 
 #include "SkColor.h"
+#include "SkNx.h"
 #include "SkPoint.h"
 #include "SkSize.h"
 
@@ -19,6 +20,12 @@ size_t ValueTraits<ScalarValue>::Cardinality(const ScalarValue&) {
 }
 
 template <>
+ScalarValue ValueTraits<ScalarValue>::Lerp(const ScalarValue& v0, const ScalarValue& v1, float t) {
+    SkASSERT(t >= 0 && t <= 1);
+    return v0 + (v1 - v0) * t;
+}
+
+template <>
 template <>
 SkScalar ValueTraits<ScalarValue>::As<SkScalar>(const ScalarValue& v) {
     return v;
@@ -30,6 +37,20 @@ size_t ValueTraits<VectorValue>::Cardinality(const VectorValue& vec) {
 }
 
 template <>
+VectorValue ValueTraits<VectorValue>::Lerp(const VectorValue& v0, const VectorValue& v1, float t) {
+    SkASSERT(v0.size() == v1.size());
+
+    VectorValue v;
+    v.reserve(v0.size());
+
+    for (size_t i = 0; i < v0.size(); ++i) {
+        v.push_back(ValueTraits<ScalarValue>::Lerp(v0[i], v1[i], t));
+    }
+
+    return v;
+}
+
+template <>
 template <>
 SkColor ValueTraits<VectorValue>::As<SkColor>(const VectorValue& v) {
     // best effort to turn this into a color
@@ -61,13 +82,79 @@ SkSize ValueTraits<VectorValue>::As<SkSize>(const VectorValue& vec) {
 }
 
 template <>
-size_t ValueTraits<ShapeValue>::Cardinality(const ShapeValue& path) {
-    return SkTo<size_t>(path.countVerbs());
+size_t ValueTraits<ShapeValue>::Cardinality(const ShapeValue& shape) {
+    return shape.fVertices.size();
+}
+
+static SkPoint lerp_point(const SkPoint& v0, const SkPoint& v1, const Sk2f& t) {
+    const auto v2f0 = Sk2f::Load(&v0),
+               v2f1 = Sk2f::Load(&v1);
+
+    SkPoint v;
+    (v2f0 + (v2f1 - v2f0) * t).store(&v);
+
+    return v;
+}
+
+template <>
+ShapeValue ValueTraits<ShapeValue>::Lerp(const ShapeValue& v0, const ShapeValue& v1, float t) {
+    SkASSERT(t >= 0 && t <= 1);
+    SkASSERT(v0.fVertices.size() == v1.fVertices.size());
+    SkASSERT(v0.fClosed == v1.fClosed);
+
+    ShapeValue v;
+    v.fClosed = v0.fClosed;
+    v.fVolatile = true; // interpolated values are volatile
+
+    const auto t2f = Sk2f(t);
+    v.fVertices.reserve(v0.fVertices.size());
+
+    for (size_t i = 0; i < v0.fVertices.size(); ++i) {
+        v.fVertices.emplace_back(BezierVertex({
+            lerp_point(v0.fVertices[i].fInPoint , v1.fVertices[i].fInPoint , t2f),
+            lerp_point(v0.fVertices[i].fOutPoint, v1.fVertices[i].fOutPoint, t2f),
+            lerp_point(v0.fVertices[i].fVertex  , v1.fVertices[i].fVertex  , t2f)
+        }));
+    }
+
+    return v;
 }
 
 template <>
 template <>
-SkPath ValueTraits<ShapeValue>::As<SkPath>(const ShapeValue& path) {
+SkPath ValueTraits<ShapeValue>::As<SkPath>(const ShapeValue& shape) {
+    SkPath path;
+
+    if (!shape.fVertices.empty()) {
+        path.moveTo(shape.fVertices.front().fVertex);
+    }
+
+    const auto& addCubic = [&](size_t from, size_t to) {
+        const auto c0 = shape.fVertices[from].fVertex + shape.fVertices[from].fOutPoint,
+                   c1 = shape.fVertices[to].fVertex   + shape.fVertices[to].fInPoint;
+
+        if (c0 == shape.fVertices[from].fVertex &&
+            c1 == shape.fVertices[to].fVertex) {
+            // If the control points are coincident, we can power-reduce to a straight line.
+            // TODO: we could also do that when the controls are on the same line as the
+            //       vertices, but it's unclear how common that case is.
+            path.lineTo(shape.fVertices[to].fVertex);
+        } else {
+            path.cubicTo(c0, c1, shape.fVertices[to].fVertex);
+        }
+    };
+
+    for (size_t i = 1; i < shape.fVertices.size(); ++i) {
+        addCubic(i - 1, i);
+    }
+
+    if (!shape.fVertices.empty() && shape.fClosed) {
+        addCubic(shape.fVertices.size() - 1, 0);
+        path.close();
+    }
+
+    path.setIsVolatile(shape.fVolatile);
+
     return path;
 }
 
diff --git a/experimental/skottie/SkottieValue.h b/experimental/skottie/SkottieValue.h
index 6d6d94a7a3..cfdbd7aba7 100644
--- a/experimental/skottie/SkottieValue.h
+++ b/experimental/skottie/SkottieValue.h
@@ -21,11 +21,43 @@ struct ValueTraits {
 
     template <typename U>
     static U As(const T&);
+
+    static T Lerp(const T&, const T&, float);
 };
 
 using ScalarValue = SkScalar;
 using VectorValue = std::vector<ScalarValue>;
-using ShapeValue  = SkPath;
+
+struct BezierVertex {
+    SkPoint fInPoint,  // "in" control point, relative to the vertex
+            fOutPoint, // "out" control point, relative to the vertex
+            fVertex;
+
+    bool operator==(const BezierVertex& other) const {
+        return fInPoint  == other.fInPoint
+            && fOutPoint == other.fOutPoint
+            && fVertex   == other.fVertex;
+    }
+
+    bool operator!=(const BezierVertex& other) const { return !(*this == other); }
+};
+
+struct ShapeValue {
+    std::vector<BezierVertex> fVertices;
+    bool                      fClosed   : 1,
+                              fVolatile : 1;
+
+    ShapeValue() : fClosed(false), fVolatile(false) {}
+    ShapeValue(const ShapeValue&)            = default;
+    ShapeValue(ShapeValue&&)                 = default;
+    ShapeValue& operator=(const ShapeValue&) = default;
+
+    bool operator==(const ShapeValue& other) const {
+        return fVertices == other.fVertices && fClosed == other.fClosed;
+    }
+
+    bool operator!=(const ShapeValue& other) const { return !(*this == other); }
+};
 
 } // namespace skottie