path ops -- rewrite angle sort

This is a major change resulting from a minor
tweak. In the old code, the intersection point
of two curves was shared between them, but the
intersection points and end points of sorted edges was
computed directly from the intersection T value.

In this CL, both intersection points and sorted points
are the same, and intermediate control points are computed
to preserve their slope.

The sort itself has been completely rewritten to be more
robust and remove 'magic' checks, conditions that empirically
worked but couldn't be rationalized.

This CL was triggered by errors generated computing the clips
of SKP files. At this point, all 73M standard tests work and
at least the first troublesome SKPs work.

Review URL: https://codereview.chromium.org/15338003

git-svn-id: http://skia.googlecode.com/svn/trunk@9432 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 9 insertions, 14 deletions

diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index 199d7be14b..b071ca5371 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -4,36 +4,31 @@
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
+#include "SkFloatBits.h"
 #include "SkPathOpsTypes.h"
 
 const int UlpsEpsilon = 16;
 
 // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
-union SkPathOpsUlpsFloat {
-    int32_t fInt;
-    float fFloat;
-
-    SkPathOpsUlpsFloat(float num = 0.0f) : fFloat(num) {}
-    bool negative() const { return fInt < 0; }
-};
-
+// FIXME: move to SkFloatBits.h
 bool AlmostEqualUlps(float A, float B) {
-    SkPathOpsUlpsFloat uA(A);
-    SkPathOpsUlpsFloat uB(B);
+    SkFloatIntUnion floatIntA, floatIntB;
+    floatIntA.fFloat = A;
+    floatIntB.fFloat = B;
     // Different signs means they do not match.
-    if (uA.negative() != uB.negative())
+    if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0))
     {
         // Check for equality to make sure +0 == -0
         return A == B;
     }
     // Find the difference in ULPs.
-    int ulpsDiff = abs(uA.fInt - uB.fInt);
+    int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
     return ulpsDiff <= UlpsEpsilon;
 }
 
 // cube root approximation using bit hack for 64-bit float
 // adapted from Kahan's cbrt
-static  double cbrt_5d(double d) {
+static double cbrt_5d(double d) {
     const unsigned int B1 = 715094163;
     double t = 0.0;
     unsigned int* pt = (unsigned int*) &t;
@@ -43,7 +38,7 @@ static  double cbrt_5d(double d) {
 }
 
 // iterative cube root approximation using Halley's method (double)
-static  double cbrta_halleyd(const double a, const double R) {
+static double cbrta_halleyd(const double a, const double R) {
     const double a3 = a * a * a;
     const double b = a * (a3 + R + R) / (a3 + a3 + R);
     return b;