Improve cubic KLM accuracy

Moves cubic root finding logic out of GrPathUtils and
PathOpsCubicIntersectionTest, and unifies it in SkGeometry.

"Normalizes" the homogeneous parameter values of the roots, rather
than the cubic inflection function. Does this normalization by
twiddling the exponents instead of division (which causes a loss of
precision).

Abandons the built-in derivatives in GrCubicEffect. These don't have
high enough precision on many mobile gpus. Instead we pass the KLM
matrix to the vertex shader via uniform, where we can use it to set up
new linear functionals from which the fragment shader can calculate
the gradient of the implicit function.

Bug: skia:4410
Change-Id: Ibd64e999520adc8cdef7803a492d3699995aef5a
Reviewed-on: https://skia-review.googlesource.com/19017
Reviewed-by: Greg Daniel <egdaniel@google.com>
Commit-Queue: Chris Dalton <csmartdalton@google.com>

1 files changed, 30 insertions, 17 deletions

diff --git a/src/gpu/GrPathUtils.h b/src/gpu/GrPathUtils.h
index fdfd375427..35f94d0329 100644
--- a/src/gpu/GrPathUtils.h
+++ b/src/gpu/GrPathUtils.h
@@ -8,6 +8,7 @@
 #ifndef GrPathUtils_DEFINED
 #define GrPathUtils_DEFINED
 
+#include "SkGeometry.h"
 #include "SkRect.h"
 #include "SkPathPriv.h"
 #include "SkTArray.h"
@@ -123,6 +124,30 @@ namespace GrPathUtils {
                                                 SkPathPriv::FirstDirection dir,
                                                 SkTArray<SkPoint, true>* quads);
 
+    // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the
+    // curve (when facing in the direction of increasing parameter values) will be the area that
+    // satisfies:
+    //
+    //     k^3 < l*m
+    //
+    // Output:
+    //
+    // klm: Holds the linear functionals K,L,M as row vectors:
+    //
+    //          | ..K.. |   | x |      | k |
+    //          | ..L.. | * | y |  ==  | l |
+    //          | ..M.. |   | 1 |      | m |
+    //
+    // NOTE: the KLM lines are calculated in the same space as the input control points. If you
+    // transform the points the lines will also need to be transformed. This can be done by mapping
+    // the lines with the inverse-transpose of the matrix used to map the points.
+    //
+    // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M
+    // intersect with K (See SkClassifyCubic).
+    //
+    // Returns the cubic's classification.
+    SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, SkScalar t[2], SkScalar s[2]);
+
     // Chops the cubic bezier passed in by src, at the double point (intersection point)
     // if the curve is a cubic loop. If it is a loop, there will be two parametric values for
     // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1.
@@ -132,32 +157,20 @@ namespace GrPathUtils {
     // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics,
     //             dst[0..3] and dst[3..6] if dst is not nullptr
     // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic,
-    //             dst[0..3] if dst is not nullptr
-    //
-    // Optional KLM Calculation:
-    // The function can also return the KLM linear functionals for the cubic implicit form of
-    // k^3 - lm. This can be shared by all chopped cubics.
+    //             src[0..3]
     //
     // Output:
     //
-    // klm: Holds the linear functionals K,L,M as row vectors:
-    //
-    //          | ..K.. |   | x |      | k |
-    //          | ..L.. | * | y |  ==  | l |
-    //          | ..M.. |   | 1 |      | m |
+    // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().)
     //
     // loopIndex: This value will tell the caller which of the chopped sections (if any) are the
     //            actual loop. A value of -1 means there is no loop section. The caller can then use
     //            this value to decide how/if they want to flip the orientation of this section.
     //            The flip should be done by negating the k and l values as follows:
     //
-    //                KLM.postScale(-1, -1)
-    //
-    // Notice that the KLM lines are calculated in the same space as the input control points.
-    // If you transform the points the lines will also need to be transformed. This can be done
-    // by mapping the lines with the inverse-transpose of the matrix used to map the points.
-    int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = nullptr,
-                                    SkMatrix* klm = nullptr, int* loopIndex = nullptr);
+    //            KLM.postScale(-1, -1)
+    int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
+                                    int* loopIndex);
 
     // When tessellating curved paths into linear segments, this defines the maximum distance
     // in screen space which a segment may deviate from the mathmatically correct value.