Update 2pt conical gradient in raster pipeline

The updated algorithm matches our new GPU algorithm
(https://skia.org/dev/design/conical) and it brings
about 7%-26% speedup. In the next CL, I'll simplify
the GPU code by reusing the CPU code in this CL.

    7.20% faster in gradient_conical_clamp_hicolor
    8.94% faster in gradient_conicalZero_clamp_hicolor
   10.00% faster in gradient_conicalOut_clamp_hicolor
   11.72% faster in gradient_conicalOutZero_clamp_hicolor
   13.62% faster in gradient_conical_clamp_3color
   16.52% faster in gradient_conicalZero_clamp_3color
   17.48% faster in gradient_conical_clamp
   17.70% faster in gradient_conical_clamp_shallow
   20.60% faster in gradient_conicalOut_clamp_3color
   20.98% faster in gradient_conicalOutZero_clamp_3color
   21.79% faster in gradient_conicalZero_clamp
   22.48% faster in gradient_conicalOut_clamp
   26.13% faster in gradient_conicalOutZero_clamp

Bug: skia:
Change-Id: Ia159495e1c77658cb28e48c9edf84938464e501c
Reviewed-on: https://skia-review.googlesource.com/90262
Commit-Queue: Yuqian Li <liyuqian@google.com>
Reviewed-by: Mike Klein <mtklein@chromium.org>

2 files changed, 125 insertions, 6 deletions

diff --git a/src/shaders/gradients/SkTwoPointConicalGradient.cpp b/src/shaders/gradients/SkTwoPointConicalGradient.cpp
index 8cf6409afe..7c6b3342af 100644
--- a/src/shaders/gradients/SkTwoPointConicalGradient.cpp
+++ b/src/shaders/gradients/SkTwoPointConicalGradient.cpp
@@ -12,6 +12,49 @@
 #include "SkWriteBuffer.h"
 #include "../../jumper/SkJumper.h"
 
+// Please see https://skia.org/dev/design/conical for how our shader works.
+
+void SkTwoPointConicalGradient::FocalData::set(SkScalar r0, SkScalar r1, SkMatrix& matrix) {
+#ifdef SK_SUPPORT_LEGACY_2PT_CONICAL
+    // Just initialize the memory. We are not supposed to do anything in legacy mode.
+    fIsSwapped = false;
+    fFocalX = fR1 = 0;
+#else
+    fIsSwapped = false;
+    fFocalX = r0 / (r0 - r1);
+    if (SkScalarNearlyZero(fFocalX - 1)) {
+        // swap r0, r1
+        matrix.postTranslate(-1, 0);
+        matrix.postScale(-1, 1);
+        std::swap(r0, r1);
+        fFocalX = 0; // because r0 is now 0
+        fIsSwapped = true;
+    }
+
+    // Map {focal point, (1, 0)} to {(0, 0), (1, 0)}
+    const SkPoint from[2]   = { {fFocalX, 0}, {1, 0} };
+    const SkPoint to[2]     = { {0, 0}, {1, 0} };
+    SkMatrix focalMatrix;
+    if (!focalMatrix.setPolyToPoly(from, to, 2)) {
+        SkDEBUGFAILF("Mapping focal point failed unexpectedly for focalX = %f.\n", fFocalX);
+        // We won't be able to draw the gradient; at least make sure that we initialize the
+        // memory to prevent security issues.
+        focalMatrix = SkMatrix::MakeScale(1, 1);
+    }
+    matrix.postConcat(focalMatrix);
+    fR1 = r1 / SkScalarAbs(1 - fFocalX); // focalMatrix has a scale of 1/(1-f)
+
+    // The following transformations are just to accelerate the shader computation by saving
+    // some arithmatic operations.
+    if (this->isFocalOnCircle()) {
+        matrix.postScale(0.5, 0.5);
+    } else {
+        matrix.postScale(fR1 / (fR1 * fR1 - 1), 1 / sqrt(SkScalarAbs(fR1 * fR1 - 1)));
+    }
+    matrix.postScale(SkScalarAbs(1 - fFocalX), SkScalarAbs(1 - fFocalX)); // scale |1 - f|
+#endif
+}
+
 sk_sp<SkShader> SkTwoPointConicalGradient::Create(const SkPoint& c0, SkScalar r0,
                                                   const SkPoint& c1, SkScalar r1,
                                                   const Descriptor& desc) {
@@ -34,18 +77,22 @@ sk_sp<SkShader> SkTwoPointConicalGradient::Create(const SkPoint& c0, SkScalar r0
             return nullptr;
         }
 
-        // General two-point case.
-        gradientType = Type::kTwoPoint;
+        gradientType = SkScalarNearlyZero(r1 - r0) ? Type::kStrip : Type::kFocal;
     }
 
+    FocalData focalData;
+    if (gradientType == Type::kFocal) {
+        const auto dCenter = (c0 - c1).length();
+        focalData.set(r0 / dCenter, r1 / dCenter, gradientMatrix); // this may change gradientMatrix
+    }
     return sk_sp<SkShader>(new SkTwoPointConicalGradient(c0, r0, c1, r1, desc,
-                                                         gradientType, gradientMatrix));
+                                                         gradientType, gradientMatrix, focalData));
 }
 
 SkTwoPointConicalGradient::SkTwoPointConicalGradient(
         const SkPoint& start, SkScalar startRadius,
         const SkPoint& end, SkScalar endRadius,
-        const Descriptor& desc, Type type, const SkMatrix& gradientMatrix)
+        const Descriptor& desc, Type type, const SkMatrix& gradientMatrix, const FocalData& data)
     : SkGradientShaderBase(desc, gradientMatrix)
     , fCenter1(start)
     , fCenter2(end)
@@ -55,6 +102,9 @@ SkTwoPointConicalGradient::SkTwoPointConicalGradient(
 {
     // this is degenerate, and should be caught by our caller
     SkASSERT(fCenter1 != fCenter2 || fRadius1 != fRadius2);
+    if (type == Type::kFocal) {
+        fFocalData = data;
+    }
 }
 
 bool SkTwoPointConicalGradient::isOpaque() const {
@@ -189,6 +239,7 @@ void SkTwoPointConicalGradient::appendGradientStages(SkArenaAlloc* alloc, SkRast
         return;
     }
 
+#ifdef SK_SUPPORT_LEGACY_2PT_CONICAL
     const auto dCenter = (fCenter1 - fCenter2).length();
 
     // Since we've squashed the centers into a unit vector, we must also scale
@@ -230,7 +281,48 @@ void SkTwoPointConicalGradient::appendGradientStages(SkArenaAlloc* alloc, SkRast
     }
 
     if (!isWellBehaved) {
+        p->append(SkRasterPipeline::mask_2pt_conical_degenerates_legacy, ctx);
+        postPipeline->append(SkRasterPipeline::apply_vector_mask, &ctx->fMask);
+    }
+#else
+    if (fType == Type::kStrip) {
+        auto* ctx = alloc->make<SkJumper_2PtConicalCtx>();
+        SkScalar scaledR0 = fRadius1 / this->getCenterX1();
+        ctx->fP0 = scaledR0 * scaledR0;
+        p->append(SkRasterPipeline::xy_to_2pt_conical_strip, ctx);
+        p->append(SkRasterPipeline::mask_2pt_conical_nan, ctx);
+        postPipeline->append(SkRasterPipeline::apply_vector_mask, &ctx->fMask);
+        return;
+    }
+
+    auto* ctx = alloc->make<SkJumper_2PtConicalCtx>();
+    ctx->fP0 = 1/fFocalData.fR1;
+    ctx->fP1 = fFocalData.fFocalX;
+
+    if (fFocalData.isFocalOnCircle()) {
+        p->append(SkRasterPipeline::xy_to_2pt_conical_focal_on_circle);
+    } else if (fFocalData.isWellBehaved()) {
+        p->append(SkRasterPipeline::xy_to_2pt_conical_well_behaved, ctx);
+    } else if (fFocalData.isSwapped() || 1 - fFocalData.fFocalX < 0) {
+        p->append(SkRasterPipeline::xy_to_2pt_conical_smaller, ctx);
+    } else {
+        p->append(SkRasterPipeline::xy_to_2pt_conical_greater, ctx);
+    }
+
+    if (!fFocalData.isWellBehaved()) {
         p->append(SkRasterPipeline::mask_2pt_conical_degenerates, ctx);
+    }
+    if (1 - fFocalData.fFocalX < 0) {
+        p->append(SkRasterPipeline::negate_x);
+    }
+    if (!fFocalData.isNativelyFocal()) {
+        p->append(SkRasterPipeline::alter_2pt_conical_compensate_focal, ctx);
+    }
+    if (fFocalData.isSwapped()) {
+        p->append(SkRasterPipeline::alter_2pt_conical_unswap);
+    }
+    if (!fFocalData.isWellBehaved()) {
         postPipeline->append(SkRasterPipeline::apply_vector_mask, &ctx->fMask);
     }
+#endif
 }
diff --git a/src/shaders/gradients/SkTwoPointConicalGradient.h b/src/shaders/gradients/SkTwoPointConicalGradient.h
index 96039e4771..623e69f95a 100644
--- a/src/shaders/gradients/SkTwoPointConicalGradient.h
+++ b/src/shaders/gradients/SkTwoPointConicalGradient.h
@@ -13,6 +13,30 @@
 
 class SkTwoPointConicalGradient final : public SkGradientShaderBase {
 public:
+    // See https://skia.org/dev/design/conical for what focal data means and how our shader works.
+    // We make it public so the GPU shader can also use it.
+    struct FocalData {
+        SkScalar    fR1;        // r1 after mapping focal point to (0, 0)
+        SkScalar    fFocalX;    // f
+        bool        fIsSwapped; // whether we swapped r0, r1
+
+        // The input r0, r1 are the radii when we map centers to {(0, 0), (1, 0)}.
+        // We'll post concat matrix with our transformation matrix that maps focal point to (0, 0).
+        void set(SkScalar r0, SkScalar r1, SkMatrix& matrix);
+
+        // Whether the focal point (0, 0) is on the end circle with center (1, 0) and radius r1. If
+        // this is true, it's as if an aircraft is flying at Mach 1 and all circles (soundwaves)
+        // will go through the focal point (aircraft). In our previous implementations, this was
+        // known as the edge case where the inside circle touches the outside circle (on the focal
+        // point). If we were to solve for t bruteforcely using a quadratic equation, this case
+        // implies that the quadratic equation degenerates to a linear equation.
+        bool isFocalOnCircle() const { return SkScalarNearlyZero(1 - fR1); }
+
+        bool isSwapped() const { return fIsSwapped; }
+        bool isWellBehaved() const { return !this->isFocalOnCircle() && fR1 > 1; }
+        bool isNativelyFocal() const { return SkScalarNearlyZero(fFocalX); }
+    };
+
     static sk_sp<SkShader> Create(const SkPoint& start, SkScalar startRadius,
                                   const SkPoint& end, SkScalar endRadius,
                                   const Descriptor&);
@@ -45,12 +69,13 @@ protected:
 private:
     enum class Type {
         kRadial,
-        kTwoPoint,
+        kStrip,
+        kFocal
     };
 
     SkTwoPointConicalGradient(const SkPoint& c0, SkScalar r0,
                               const SkPoint& c1, SkScalar r1,
-                              const Descriptor&, Type, const SkMatrix&);
+                              const Descriptor&, Type, const SkMatrix&, const FocalData&);
 
     SkPoint  fCenter1;
     SkPoint  fCenter2;
@@ -58,6 +83,8 @@ private:
     SkScalar fRadius2;
     Type     fType;
 
+    FocalData fFocalData;
+
     friend class SkGradientShader;
     typedef SkGradientShaderBase INHERITED;
 };