diff options
Diffstat (limited to 'experimental')
37 files changed, 2140 insertions, 1763 deletions
diff --git a/experimental/Intersection/ActiveEdge_Test.cpp b/experimental/Intersection/ActiveEdge_Test.cpp index 3e1b958ab6..5456155abc 100755 --- a/experimental/Intersection/ActiveEdge_Test.cpp +++ b/experimental/Intersection/ActiveEdge_Test.cpp @@ -1,12 +1,4 @@ -#include "CurveIntersection.h" -#include "Intersections.h" -#include "LineIntersection.h" -#include "SkPath.h" -#include "SkRect.h" -#include "SkTArray.h" -#include "SkTDArray.h" -#include "ShapeOps.h" -#include "TSearch.h" +#include "Simplify.h" namespace UnitTest { diff --git a/experimental/Intersection/ConvexHull.cpp b/experimental/Intersection/ConvexHull.cpp index 6cdbe60995..1551720eef 100644 --- a/experimental/Intersection/ConvexHull.cpp +++ b/experimental/Intersection/ConvexHull.cpp @@ -1,4 +1,5 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "IntersectionUtilities.h" /* Given a cubic, find the convex hull described by the end and control points. diff --git a/experimental/Intersection/CubicBezierClip.cpp b/experimental/Intersection/CubicBezierClip.cpp index 4ed1369d1a..4eddc70a42 100644 --- a/experimental/Intersection/CubicBezierClip.cpp +++ b/experimental/Intersection/CubicBezierClip.cpp @@ -1,4 +1,5 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "LineParameters.h" #include <algorithm> // used for std::swap diff --git a/experimental/Intersection/CubicBounds.cpp b/experimental/Intersection/CubicBounds.cpp index 8d14ea5a9e..024fb9637f 100644 --- a/experimental/Intersection/CubicBounds.cpp +++ b/experimental/Intersection/CubicBounds.cpp @@ -1,4 +1,5 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "Extrema.h" static int isBoundedByEndPoints(double a, double b, double c, double d) diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp index 005e77781c..14b30ed50e 100644 --- a/experimental/Intersection/CubicIntersection_Test.cpp +++ b/experimental/Intersection/CubicIntersection_Test.cpp @@ -1,4 +1,5 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "CubicIntersection_TestData.h" #include "Intersection_Tests.h" #include "Intersections.h" diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp index 3fab29ec80..05c00a0d29 100644 --- a/experimental/Intersection/CubicUtilities.cpp +++ b/experimental/Intersection/CubicUtilities.cpp @@ -74,3 +74,75 @@ int cubicRoots(double A, double B, double C, double D, double t[3]) { } return (int)(roots - t); } + +// from http://www.cs.sunysb.edu/~qin/courses/geometry/4.pdf +// c(t) = a(1-t)^3 + 3bt(1-t)^2 + 3c(1-t)t^2 + dt^3 +// c'(t) = -3a(1-t)^2 + 3b((1-t)^2 - 2t(1-t)) + 3c(2t(1-t) - t^2) + 3dt^2 +// = 3(b-a)(1-t)^2 + 6(c-b)t(1-t) + 3(d-c)t^2 +double derivativeAtT(const double* cubic, double t) { + double one_t = 1 - t; + double a = cubic[0]; + double b = cubic[2]; + double c = cubic[4]; + double d = cubic[6]; + return (b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t; +} + +// same as derivativeAtT +// which is more accurate? which is faster? +double derivativeAtT_2(const double* cubic, double t) { + double a = cubic[2] - cubic[0]; + double b = cubic[4] - 2 * cubic[2] + cubic[0]; + double c = cubic[6] + 3 * (cubic[2] - cubic[4]) - cubic[0]; + return c * c * t * t + 2 * b * t + a; +} + +void dxdy_at_t(const Cubic& cubic, double t, double& dx, double& dy) { + if (&dx) { + dx = derivativeAtT(&cubic[0].x, t); + } + if (&dy) { + dy = derivativeAtT(&cubic[0].y, t); + } +} + +bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath) { + double dy = cubic[index].y - cubic[zero].y; + double dx = cubic[index].x - cubic[zero].x; + if (approximately_equal(dy, 0)) { + if (approximately_equal(dx, 0)) { + return false; + } + memcpy(rotPath, cubic, sizeof(Cubic)); + return true; + } + for (int index = 0; index < 4; ++index) { + rotPath[index].x = cubic[index].x * dx + cubic[index].y * dy; + rotPath[index].y = cubic[index].y * dx - cubic[index].x * dy; + } + return true; +} + +double secondDerivativeAtT(const double* cubic, double t) { + double a = cubic[0]; + double b = cubic[2]; + double c = cubic[4]; + double d = cubic[6]; + return (c - 2 * b + a) * (1 - t) + (d - 2 * c + b) * t; +} + +void xy_at_t(const Cubic& cubic, double t, double& x, double& y) { + double one_t = 1 - t; + double one_t2 = one_t * one_t; + double a = one_t2 * one_t; + double b = 3 * one_t2 * t; + double t2 = t * t; + double c = 3 * one_t * t2; + double d = t2 * t; + if (&x) { + x = a * cubic[0].x + b * cubic[1].x + c * cubic[2].x + d * cubic[3].x; + } + if (&y) { + y = a * cubic[0].y + b * cubic[1].y + c * cubic[2].y + d * cubic[3].y; + } +} diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h index 7a99c95218..94255ee46c 100644 --- a/experimental/Intersection/CubicUtilities.h +++ b/experimental/Intersection/CubicUtilities.h @@ -1,3 +1,12 @@ +#include "DataTypes.h" + double cube_root(double x); void coefficients(const double* cubic, double& A, double& B, double& C, double& D); int cubicRoots(double A, double B, double C, double D, double t[3]); +double derivativeAtT(const double* cubic, double t); +// competing version that should produce same results +double derivativeAtT_2(const double* cubic, double t); +void dxdy_at_t(const Cubic& , double t, double& x, double& y); +bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath); +double secondDerivativeAtT(const double* cubic, double t); +void xy_at_t(const Cubic& , double t, double& x, double& y); diff --git a/experimental/Intersection/CurveUtilities.h b/experimental/Intersection/CurveUtilities.h new file mode 100644 index 0000000000..4d346327eb --- /dev/null +++ b/experimental/Intersection/CurveUtilities.h @@ -0,0 +1,15 @@ +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef CurveUtilities_DEFINE +#define CurveUtilities_DEFINE + +#include "CubicUtilities.h" +#include "LineUtilities.h" +#include "QuadraticUtilities.h" + +#endif diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp index d4ce962c83..db153f6f9a 100644 --- a/experimental/Intersection/DataTypes.cpp +++ b/experimental/Intersection/DataTypes.cpp @@ -21,115 +21,6 @@ const double SquaredEpsilon = PointEpsilon * PointEpsilon; const int UlpsEpsilon = 16; -bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath) { - double dy = cubic[index].y - cubic[zero].y; - double dx = cubic[index].x - cubic[zero].x; - if (approximately_equal(dy, 0)) { - if (approximately_equal(dx, 0)) { - return false; - } - memcpy(rotPath, cubic, sizeof(Cubic)); - return true; - } - for (int index = 0; index < 4; ++index) { - rotPath[index].x = cubic[index].x * dx + cubic[index].y * dy; - rotPath[index].y = cubic[index].y * dx - cubic[index].x * dy; - } - return true; -} - -double t_at(const _Line& line, const _Point& pt) { - double dx = line[1].x - line[0].x; - double dy = line[1].y - line[0].y; - if (fabs(dx) > fabs(dy)) { - if (approximately_zero(dx)) { - return 0; - } - return (pt.x - line[0].x) / dx; - } - if (approximately_zero(dy)) { - return 0; - } - return (pt.y - line[0].y) / dy; -} - -static void setMinMax(double x, int flags, double& minX, double& maxX) { - if (minX > x && (flags & (kFindTopMin | kFindBottomMin))) { - minX = x; - } - if (maxX < x && (flags & (kFindTopMax | kFindBottomMax))) { - maxX = x; - } -} - -void x_at(const _Point& p1, const _Point& p2, double top, double bottom, - int flags, double& minX, double& maxX) { - if (approximately_equal(p1.y, p2.y)) { - // It should be OK to bail early in this case. There's another edge - // which shares this end point which can intersect without failing to - // have a slope ... maybe - return; - } - - // p2.x is always greater than p1.x -- the part of points (p1, p2) are - // moving from the start of the cubic towards its end. - // if p1.y < p2.y, minX can be affected - // if p1.y > p2.y, maxX can be affected - double slope = (p2.x - p1.x) / (p2.y - p1.y); - int topFlags = flags & (kFindTopMin | kFindTopMax); - if (topFlags && (top <= p1.y && top >= p2.y - || top >= p1.y && top <= p2.y)) { - double x = p1.x + (top - p1.y) * slope; - setMinMax(x, topFlags, minX, maxX); - } - int bottomFlags = flags & (kFindBottomMin | kFindBottomMax); - if (bottomFlags && (bottom <= p1.y && bottom >= p2.y - || bottom >= p1.y && bottom <= p2.y)) { - double x = p1.x + (bottom - p1.y) * slope; - setMinMax(x, bottomFlags, minX, maxX); - } -} - -void xy_at_t(const Cubic& cubic, double t, double& x, double& y) { - double one_t = 1 - t; - double one_t2 = one_t * one_t; - double a = one_t2 * one_t; - double b = 3 * one_t2 * t; - double t2 = t * t; - double c = 3 * one_t * t2; - double d = t2 * t; - if (&x) { - x = a * cubic[0].x + b * cubic[1].x + c * cubic[2].x + d * cubic[3].x; - } - if (&y) { - y = a * cubic[0].y + b * cubic[1].y + c * cubic[2].y + d * cubic[3].y; - } -} - -void xy_at_t(const _Line& line, double t, double& x, double& y) { - double one_t = 1 - t; - if (&x) { - x = one_t * line[0].x + t * line[1].x; - } - if (&y) { - y = one_t * line[0].y + t * line[1].y; - } -} - -void xy_at_t(const Quadratic& quad, double t, double& x, double& y) { - double one_t = 1 - t; - double a = one_t * one_t; - double b = 2 * one_t * t; - double c = t * t; - if (&x) { - x = a * quad[0].x + b * quad[1].x + c * quad[2].x; - } - if (&y) { - y = a * quad[0].y + b * quad[1].y + c * quad[2].y; - } -} - - // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ union Float_t { diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h index 8b7ff7fb30..6218a65702 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -168,20 +168,4 @@ struct QuadraticPair { _Point pts[5]; }; -enum x_at_flags { - kFindTopMin = 1, - kFindTopMax = 2, - kFindBottomMin = 4, - kFindBottomMax = 8 -}; - -bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath); -double t_at(const _Line&, const _Point& ); -void x_at(const _Point& p1, const _Point& p2, double minY, double maxY, - int flags, double& tMin, double& tMax); -void xy_at_t(const Cubic& , double t, double& x, double& y); -void xy_at_t(const _Line& , double t, double& x, double& y); -void xy_at_t(const Quadratic& , double t, double& x, double& y); - - #endif // __DataTypes_h__ diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index e74689fb41..0f624b5633 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -5,15 +5,7 @@ * found in the LICENSE file. */ -#include "CurveIntersection.h" -#include "Intersections.h" -#include "LineIntersection.h" -#include "SkPath.h" -#include "SkRect.h" -#include "SkTArray.h" -#include "SkTDArray.h" -#include "ShapeOps.h" -#include "TSearch.h" +#include "Simplify.h" #undef SkASSERT #define SkASSERT(cond) while (!(cond)) { sk_throw(); } diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h index e8215a369f..b35da6d351 100644 --- a/experimental/Intersection/EdgeWalker_Test.h +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -15,6 +15,9 @@ extern bool drawAsciiPaths(const SkPath& one, const SkPath& two, extern void showPath(const SkPath& path, const char* str = NULL); extern bool testSimplify(const SkPath& path, bool fill, SkPath& out, SkBitmap& bitmap, SkCanvas* canvas = 0); +extern bool testSimplifyx(const SkPath& path, SkPath& out, + SkBitmap& bitmap, SkCanvas* canvas = 0); +extern bool testSimplifyx(const SkPath& path); struct State4 { State4(); diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp index 2a29648a25..7e65e8f032 100644 --- a/experimental/Intersection/EdgeWalker_TestUtility.cpp +++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp @@ -60,7 +60,7 @@ static int pathsDrawTheSame(const SkPath& one, const SkPath& two, int bitWidth = SkScalarCeil(larger.width()) + 2; int bitHeight = SkScalarCeil(larger.height()) + 2; if (bits.width() < bitWidth * 2 || bits.height() < bitHeight) { - if (bits.width() >= 200) { + if (bits.width() >= 200 && false) { SkDebugf("%s bitWidth=%d bitHeight=%d\n", __FUNCTION__, bitWidth, bitHeight); } bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight); @@ -192,10 +192,10 @@ int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap, const SkRect& bounds2 = two.getBounds(); SkRect larger = bounds1; larger.join(bounds2); - SkScalar xScale = std::max(80.0f / larger.width(), 1.0f); - SkScalar yScale = std::max(60.0f / larger.height(), 1.0f); + SkScalar xScale = std::max(32.0f / larger.width(), 1.0f); + SkScalar yScale = std::max(24.0f / larger.height(), 1.0f); errors = scaledDrawTheSame(one, two, xScale, yScale, false, bitmap, canvas); - if (errors > 50) { + if (errors > 5) { scaledDrawTheSame(one, two, xScale, yScale, true, bitmap, canvas); } } @@ -203,7 +203,7 @@ int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap, SkDebugf("\n%s errors=%d\n", __FUNCTION__, errors); max = errors; } - const int MAX_ERRORS = 100; + const int MAX_ERRORS = 20; if (errors > MAX_ERRORS) SkDebugf("\n%s errors=%d\n", __FUNCTION__, errors); if (errors > MAX_ERRORS && gComparePathsAssert) { showPath(one); @@ -256,6 +256,31 @@ bool testSimplify(const SkPath& path, bool fill, SkPath& out, SkBitmap& bitmap, return comparePaths(path, out, bitmap, canvas) == 0; } +bool testSimplifyx(const SkPath& path, SkPath& out, SkBitmap& bitmap, + SkCanvas* canvas) { + if (gShowPath) { + showPath(path); + } + simplifyx(path, out); + if (!gComparePaths) { + return true; + } + return comparePaths(path, out, bitmap, canvas) == 0; +} + +bool testSimplifyx(const SkPath& path) { + if (false) { + showPath(path); + } + SkPath out; + simplifyx(path, out); + if (false) { + return true; + } + SkBitmap bitmap; + return comparePaths(path, out, bitmap, 0) == 0; +} + State4::State4() { bitmap.setConfig(SkBitmap::kARGB_8888_Config, 150 * 2, 100); bitmap.allocPixels(); diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index e0b07f9029..017f1d1478 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -2,12 +2,12 @@ #include "Intersection_Tests.h" void cubecode_test(int test); -void testSimplify(); #define TEST_QUADS_FIRST 0 void Intersection_Tests() { SimplifyNew_Test(); + Simplify4x4RectsThreaded_Test(); SimplifyFindNext_Test(); SimplifyFindTop_Test(); SimplifyAngle_Test(); diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h index ca7c359bf0..4873bf9845 100644 --- a/experimental/Intersection/Intersection_Tests.h +++ b/experimental/Intersection/Intersection_Tests.h @@ -28,6 +28,7 @@ void SimplifyQuadralateralPaths_Test(); void SimplifyQuadraticPaths_Test(); void Simplify4x4QuadralateralsThreaded_Test(); void Simplify4x4QuadraticsThreaded_Test(); +void Simplify4x4RectsThreaded_Test(); void SimplifyRectangularPaths_Test(); void QuadraticBezierClip_Test(); void QuadraticCoincidence_Test(); diff --git a/experimental/Intersection/LineCubicIntersection_Test.cpp b/experimental/Intersection/LineCubicIntersection_Test.cpp index f05dbd634f..8492b863e3 100644 --- a/experimental/Intersection/LineCubicIntersection_Test.cpp +++ b/experimental/Intersection/LineCubicIntersection_Test.cpp @@ -1,7 +1,7 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "Intersection_Tests.h" #include "Intersections.h" -#include "LineUtilities.h" #include "TestUtilities.h" struct lineCubic { diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp index 31e857ed41..3efa240d83 100644 --- a/experimental/Intersection/LineIntersection.cpp +++ b/experimental/Intersection/LineIntersection.cpp @@ -39,6 +39,7 @@ int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2] aPtr = &a[0].y; bPtr = &b[0].y; } + #if 0 // sorting edges fails to preserve original direction double aMin = aPtr[0]; double aMax = aPtr[2]; double bMin = bPtr[0]; @@ -62,6 +63,27 @@ int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2] bRange[!bIn] = aMax >= bMax ? 1 : (aMax - bMin) / (bMax - bMin); } return 1 + ((aRange[0] != aRange[1]) || (bRange[0] != bRange[1])); + #else + assert(aRange); + assert(bRange); + double a0 = aPtr[0]; + double a1 = aPtr[2]; + double b0 = bPtr[0]; + double b1 = bPtr[2]; + double at0 = (a0 - b0) / (a0 - a1); + double at1 = (a0 - b1) / (a0 - a1); + if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { + return 0; + } + aRange[0] = std::max(std::min(at0, 1.0), 0.0); + aRange[1] = std::max(std::min(at1, 1.0), 0.0); + int bIn = (a0 - a1) * (b0 - b1) < 0; + bRange[bIn] = std::max(std::min((b0 - a0) / (b0 - b1), 1.0), 0.0); + bRange[!bIn] = std::max(std::min((b0 - a1) / (b0 - b1), 1.0), 0.0); + bool second = fabs(aRange[0] - aRange[1]) > FLT_EPSILON; + assert((fabs(bRange[0] - bRange[1]) <= FLT_EPSILON) ^ second); + return 1 + second; + #endif } } double ab0y = a[0].y - b[0].y; @@ -140,6 +162,7 @@ int horizontalIntersect(const _Line& line, double left, double right, break; } case 2: + #if 0 // sorting edges fails to preserve original direction double lineL = line[0].x; double lineR = line[1].x; if (lineL > lineR) { @@ -159,6 +182,30 @@ int horizontalIntersect(const _Line& line, double left, double right, intersections.fT[0][1] = (overlapR - line[0].x) / (line[1].x - line[0].x); intersections.fT[1][1] = (overlapR - left) / (right - left); } + #else + double a0 = line[0].x; + double a1 = line[1].x; + double b0 = flipped ? right : left; + double b1 = flipped ? left : right; + // FIXME: share common code below + double at0 = (a0 - b0) / (a0 - a1); + double at1 = (a0 - b1) / (a0 - a1); + if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { + return 0; + } + intersections.fT[0][0] = std::max(std::min(at0, 1.0), 0.0); + intersections.fT[0][1] = std::max(std::min(at1, 1.0), 0.0); + int bIn = (a0 - a1) * (b0 - b1) < 0; + intersections.fT[1][bIn] = std::max(std::min((b0 - a0) / (b0 - b1), + 1.0), 0.0); + intersections.fT[1][!bIn] = std::max(std::min((b0 - a1) / (b0 - b1), + 1.0), 0.0); + bool second = fabs(intersections.fT[0][0] - intersections.fT[0][1]) + > FLT_EPSILON; + assert((fabs(intersections.fT[1][0] - intersections.fT[1][1]) + <= FLT_EPSILON) ^ second); + return 1 + second; + #endif break; } if (flipped) { @@ -204,6 +251,7 @@ int verticalIntersect(const _Line& line, double top, double bottom, break; } case 2: + #if 0 // sorting edges fails to preserve original direction double lineT = line[0].y; double lineB = line[1].y; if (lineT > lineB) { @@ -223,6 +271,30 @@ int verticalIntersect(const _Line& line, double top, double bottom, intersections.fT[0][1] = (overlapB - line[0].y) / (line[1].y - line[0].y); intersections.fT[1][1] = (overlapB - top) / (bottom - top); } + #else + double a0 = line[0].y; + double a1 = line[1].y; + double b0 = flipped ? bottom : top; + double b1 = flipped ? top : bottom; + // FIXME: share common code above + double at0 = (a0 - b0) / (a0 - a1); + double at1 = (a0 - b1) / (a0 - a1); + if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { + return 0; + } + intersections.fT[0][0] = std::max(std::min(at0, 1.0), 0.0); + intersections.fT[0][1] = std::max(std::min(at1, 1.0), 0.0); + int bIn = (a0 - a1) * (b0 - b1) < 0; + intersections.fT[1][bIn] = std::max(std::min((b0 - a0) / (b0 - b1), + 1.0), 0.0); + intersections.fT[1][!bIn] = std::max(std::min((b0 - a1) / (b0 - b1), + 1.0), 0.0); + bool second = fabs(intersections.fT[0][0] - intersections.fT[0][1]) + > FLT_EPSILON; + assert((fabs(intersections.fT[1][0] - intersections.fT[1][1]) + <= FLT_EPSILON) ^ second); + return 1 + second; + #endif break; } if (flipped) { diff --git a/experimental/Intersection/LineIntersection_Test.cpp b/experimental/Intersection/LineIntersection_Test.cpp index 04b55be884..c73c9b3f7c 100644 --- a/experimental/Intersection/LineIntersection_Test.cpp +++ b/experimental/Intersection/LineIntersection_Test.cpp @@ -1,3 +1,4 @@ +#include "CurveUtilities.h" #include "Intersection_Tests.h" #include "LineIntersection.h" diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp index a48f0af128..7551dc3df2 100644 --- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp +++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp @@ -1,7 +1,7 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "Intersection_Tests.h" #include "Intersections.h" -#include "LineUtilities.h" #include "TestUtilities.h" struct lineQuad { diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp index ca94544a13..8a1c0d7c62 100644 --- a/experimental/Intersection/LineUtilities.cpp +++ b/experimental/Intersection/LineUtilities.cpp @@ -58,3 +58,64 @@ float isLeft( _Point P0, _Point P1, _Point P2 ) } #endif +double t_at(const _Line& line, const _Point& pt) { + double dx = line[1].x - line[0].x; + double dy = line[1].y - line[0].y; + if (fabs(dx) > fabs(dy)) { + if (approximately_zero(dx)) { + return 0; + } + return (pt.x - line[0].x) / dx; + } + if (approximately_zero(dy)) { + return 0; + } + return (pt.y - line[0].y) / dy; +} + +static void setMinMax(double x, int flags, double& minX, double& maxX) { + if (minX > x && (flags & (kFindTopMin | kFindBottomMin))) { + minX = x; + } + if (maxX < x && (flags & (kFindTopMax | kFindBottomMax))) { + maxX = x; + } +} + +void x_at(const _Point& p1, const _Point& p2, double top, double bottom, + int flags, double& minX, double& maxX) { + if (approximately_equal(p1.y, p2.y)) { + // It should be OK to bail early in this case. There's another edge + // which shares this end point which can intersect without failing to + // have a slope ... maybe + return; + } + + // p2.x is always greater than p1.x -- the part of points (p1, p2) are + // moving from the start of the cubic towards its end. + // if p1.y < p2.y, minX can be affected + // if p1.y > p2.y, maxX can be affected + double slope = (p2.x - p1.x) / (p2.y - p1.y); + int topFlags = flags & (kFindTopMin | kFindTopMax); + if (topFlags && (top <= p1.y && top >= p2.y + || top >= p1.y && top <= p2.y)) { + double x = p1.x + (top - p1.y) * slope; + setMinMax(x, topFlags, minX, maxX); + } + int bottomFlags = flags & (kFindBottomMin | kFindBottomMax); + if (bottomFlags && (bottom <= p1.y && bottom >= p2.y + || bottom >= p1.y && bottom <= p2.y)) { + double x = p1.x + (bottom - p1.y) * slope; + setMinMax(x, bottomFlags, minX, maxX); + } +} + +void xy_at_t(const _Line& line, double t, double& x, double& y) { + double one_t = 1 - t; + if (&x) { + x = one_t * line[0].x + t * line[1].x; + } + if (&y) { + y = one_t * line[0].y + t * line[1].y; + } +} diff --git a/experimental/Intersection/LineUtilities.h b/experimental/Intersection/LineUtilities.h index 4dafc9fdcc..fc55a741aa 100644 --- a/experimental/Intersection/LineUtilities.h +++ b/experimental/Intersection/LineUtilities.h @@ -2,3 +2,17 @@ bool implicitLine(const _Line& line, double& slope, double& axisIntercept); int reduceOrder(const _Line& line, _Line& reduced); + +double t_at(const _Line&, const _Point& ); +void xy_at_t(const _Line& , double t, double& x, double& y); + +enum x_at_flags { + kFindTopMin = 1, + kFindTopMax = 2, + kFindBottomMin = 4, + kFindBottomMax = 8 +}; + +void x_at(const _Point& p1, const _Point& p2, double minY, double maxY, + int flags, double& tMin, double& tMax); + diff --git a/experimental/Intersection/QuadraticBezierClip.cpp b/experimental/Intersection/QuadraticBezierClip.cpp index d9d984d5dd..e27db7c7eb 100644 --- a/experimental/Intersection/QuadraticBezierClip.cpp +++ b/experimental/Intersection/QuadraticBezierClip.cpp @@ -1,4 +1,5 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "LineParameters.h" #include <algorithm> // used for std::swap diff --git a/experimental/Intersection/QuadraticBounds.cpp b/experimental/Intersection/QuadraticBounds.cpp index 813fccc67e..27c170e808 100644 --- a/experimental/Intersection/QuadraticBounds.cpp +++ b/experimental/Intersection/QuadraticBounds.cpp @@ -1,4 +1,5 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "Extrema.h" static int isBoundedByEndPoints(double a, double b, double c) diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp index adf91bde86..7aeb580335 100644 --- a/experimental/Intersection/QuadraticIntersection_Test.cpp +++ b/experimental/Intersection/QuadraticIntersection_Test.cpp @@ -1,4 +1,5 @@ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "Intersection_Tests.h" #include "Intersections.h" #include "QuadraticIntersection_TestData.h" diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp index 4b4d79417e..4b695df7b6 100644 --- a/experimental/Intersection/QuadraticUtilities.cpp +++ b/experimental/Intersection/QuadraticUtilities.cpp @@ -25,3 +25,28 @@ int quadraticRoots(double A, double B, double C, double t[2]) { } return foundRoots; } + +void dxdy_at_t(const Quadratic& quad, double t, double& x, double& y) { + double a = t - 1; + double b = 1 - 2 * t; + double c = t; + if (&x) { + x = a * quad[0].x + b * quad[1].x + c * quad[2].x; + } + if (&y) { + y = a * quad[0].y + b * quad[1].y + c * quad[2].y; + } +} + +void xy_at_t(const Quadratic& quad, double t, double& x, double& y) { + double one_t = 1 - t; + double a = one_t * one_t; + double b = 2 * one_t * t; + double c = t * t; + if (&x) { + x = a * quad[0].x + b * quad[1].x + c * quad[2].x; + } + if (&y) { + y = a * quad[0].y + b * quad[1].y + c * quad[2].y; + } +} diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h index 2b7e34a2a2..7ac48e5f8a 100644 --- a/experimental/Intersection/QuadraticUtilities.h +++ b/experimental/Intersection/QuadraticUtilities.h @@ -1,3 +1,7 @@ +#include "DataTypes.h" + +void dxdy_at_t(const Quadratic& , double t, double& x, double& y); + /* Parameterization form, given A*t*t + 2*B*t*(1-t) + C*(1-t)*(1-t) * * a = A - 2*B + C @@ -14,3 +18,5 @@ inline void set_abc(const double* quad, double& a, double& b, double& c) { } int quadraticRoots(double A, double B, double C, double t[2]); + +void xy_at_t(const Quadratic& , double t, double& x, double& y); diff --git a/experimental/Intersection/RectUtilities.cpp b/experimental/Intersection/RectUtilities.cpp deleted file mode 100644 index e69de29bb2..0000000000 --- a/experimental/Intersection/RectUtilities.cpp +++ /dev/null diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index b57acf341d..23a0a3dc62 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -25,9 +25,12 @@ #define DEBUG_ADD_INTERSECTING_TS 0 #define DEBUG_BRIDGE 0 +#define DEBUG_CROSS 0 #define DEBUG_DUMP 0 #define DEBUG_PATH_CONSTRUCTION 0 +#define DEBUG_WINDING 0 #define DEBUG_UNUSED 0 // set to expose unused functions +#define DEBUG_MARK_DONE 0 #else @@ -35,9 +38,12 @@ #define DEBUG_ADD_INTERSECTING_TS 0 #define DEBUG_BRIDGE 1 +#define DEBUG_CROSS 1 #define DEBUG_DUMP 1 #define DEBUG_PATH_CONSTRUCTION 1 +#define DEBUG_WINDING 0 #define DEBUG_UNUSED 0 // set to expose unused functions +#define DEBUG_MARK_DONE 01 #endif @@ -48,6 +54,10 @@ static int gContourID; static int gSegmentID; #endif +#ifndef DEBUG_TEST +#define DEBUG_TEST 0 +#endif + static int LineIntersect(const SkPoint a[2], const SkPoint b[2], Intersections& intersections) { const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; @@ -95,24 +105,12 @@ static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, return horizontalIntersect(aLine, left, right, y, flipped, intersections); } -static int VLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, - SkScalar y, bool flipped, Intersections& intersections) { - const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - return verticalIntersect(aLine, left, right, y, flipped, intersections); -} - static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y, bool flipped, Intersections& intersections) { const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; return horizontalIntersect(aQuad, left, right, y, flipped, intersections); } -static int VQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, - SkScalar y, bool flipped, Intersections& intersections) { - const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; - return verticalIntersect(aQuad, left, right, y, flipped, intersections); -} - static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y, bool flipped, Intersections& intersections) { const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, @@ -120,13 +118,33 @@ static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, return horizontalIntersect(aCubic, left, right, y, flipped, intersections); } -static int VCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, - SkScalar y, bool flipped, Intersections& intersections) { +static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom, + SkScalar x, bool flipped, Intersections& intersections) { + const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + return verticalIntersect(aLine, top, bottom, x, flipped, intersections); +} + +static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom, + SkScalar x, bool flipped, Intersections& intersections) { + const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; + return verticalIntersect(aQuad, top, bottom, x, flipped, intersections); +} + +static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom, + SkScalar x, bool flipped, Intersections& intersections) { const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; - return verticalIntersect(aCubic, left, right, y, flipped, intersections); + return verticalIntersect(aCubic, top, bottom, x, flipped, intersections); } +static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar , + SkScalar , SkScalar , bool , Intersections& ) = { + NULL, + VLineIntersect, + VQuadIntersect, + VCubicIntersect +}; + static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; double x, y; @@ -217,6 +235,32 @@ static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = { CubicYAtT }; +static SkScalar LineDXAtT(const SkPoint a[2], double ) { + return a[1].fX - a[0].fX; +} + +static SkScalar QuadDXAtT(const SkPoint a[3], double t) { + const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; + double x; + dxdy_at_t(quad, t, x, *(double*) 0); + return SkDoubleToScalar(x); +} + +static SkScalar CubicDXAtT(const SkPoint a[4], double t) { + const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, + {a[3].fX, a[3].fY}}; + double x; + dxdy_at_t(cubic, t, x, *(double*) 0); + return SkDoubleToScalar(x); +} + +static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = { + NULL, + LineDXAtT, + QuadDXAtT, + CubicDXAtT +}; + static void LineSubDivide(const SkPoint a[2], double startT, double endT, SkPoint sub[2]) { const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; @@ -416,6 +460,10 @@ public: return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy; } + bool cancels(const Angle& rh) const { + return fDx * rh.fDx < 0 || fDy * rh.fDy < 0; + } + int end() const { return fEnd; } @@ -427,7 +475,7 @@ public: // since all angles share a point, this needs to know which point // is the common origin, i.e., whether the center is at pts[0] or pts[verb] // practically, this should only be called by addAngle - void set(const SkPoint* pts, SkPath::Verb verb, Segment* segment, + void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment, int start, int end) { SkASSERT(start != end); fSegment = segment; @@ -498,18 +546,13 @@ public: } Segment* segment() const { - return fSegment; + return const_cast<Segment*>(fSegment); } int sign() const { return SkSign32(fStart - fEnd); } - bool slopeEquals(const Angle& rh) const { - return fDx == rh.fDx && fDy == rh.fDy; - - } - int start() const { return fStart; } @@ -521,7 +564,7 @@ private: SkScalar fDDy; SkScalar fDDDx; SkScalar fDDDy; - Segment* fSegment; + const Segment* fSegment; int fStart; int fEnd; }; @@ -536,13 +579,32 @@ static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) { QSort<Angle>(angleList.begin(), angleList.end() - 1); } -// Bounds, unlike Rect, does not consider a vertical line to be empty. +// Bounds, unlike Rect, does not consider a line to be empty. struct Bounds : public SkRect { static bool Intersects(const Bounds& a, const Bounds& b) { return a.fLeft <= b.fRight && b.fLeft <= a.fRight && a.fTop <= b.fBottom && b.fTop <= a.fBottom; } + void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) { + if (left < fLeft) { + fLeft = left; + } + if (top < fTop) { + fTop = top; + } + if (right > fRight) { + fRight = right; + } + if (bottom > fBottom) { + fBottom = bottom; + } + } + + void add(const Bounds& toAdd) { + add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom); + } + bool isEmpty() { return fLeft > fRight || fTop > fBottom || fLeft == fRight && fTop == fBottom @@ -570,14 +632,13 @@ struct Bounds : public SkRect { }; struct Span { - double fT; Segment* fOther; + mutable SkPoint const* fPt; // lazily computed as needed + double fT; double fOtherT; // value at fOther[fOtherIndex].fT - mutable SkPoint const * fPt; // lazily computed as needed int fOtherIndex; // can't be used during intersection - int fWinding; // accumulated from contours surrounding this one - // OPTIMIZATION: coincident needs only 2 bits (values are -1, 0, 1) - int fCoincident; // -1 start of coincidence, 0 no coincidence, 1 end + int fWindSum; // accumulated from contours surrounding this one + int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident bool fDone; // if set, this span to next higher T has been processed }; @@ -589,7 +650,26 @@ public: #endif } - void addAngle(SkTDArray<Angle>& angles, int start, int end) { + SkScalar activeTop() const { + SkASSERT(!done()); + int count = fTs.count(); + SkScalar result = SK_ScalarMax; + bool lastDone = true; + for (int index = 0; index < count; ++index) { + bool done = fTs[index].fDone; + if (!done || !lastDone) { + SkScalar y = yAtT(index); + if (result > y) { + result = y; + } + } + lastDone = done; + } + SkASSERT(result < SK_ScalarMax); + return result; + } + + void addAngle(SkTDArray<Angle>& angles, int start, int end) const { SkASSERT(start != end); SkPoint edge[4]; (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); @@ -603,31 +683,34 @@ public: } // FIXME: this needs to defer add for aligned consecutive line segments - SkPoint addCurveTo(int start, int end, SkPath& path) { + SkPoint addCurveTo(int start, int end, SkPath& path, bool active) { SkPoint edge[4]; + // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); + if (active) { #if DEBUG_PATH_CONSTRUCTION - SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__, - kLVerbStr[fVerb], edge[1].fX, edge[1].fY); - if (fVerb > 1) { - SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY); - } - if (fVerb > 2) { - SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY); - } - SkDebugf("\n"); + SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__, + kLVerbStr[fVerb], edge[1].fX, edge[1].fY); + if (fVerb > 1) { + SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY); + } + if (fVerb > 2) { + SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY); + } + SkDebugf("\n"); #endif - switch (fVerb) { - case SkPath::kLine_Verb: - path.lineTo(edge[1].fX, edge[1].fY); - break; - case SkPath::kQuad_Verb: - path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); - break; - case SkPath::kCubic_Verb: - path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, - edge[3].fX, edge[3].fY); - break; + switch (fVerb) { + case SkPath::kLine_Verb: + path.lineTo(edge[1].fX, edge[1].fY); + break; + case SkPath::kQuad_Verb: + path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); + break; + case SkPath::kCubic_Verb: + path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, + edge[3].fX, edge[3].fY); + break; + } } return edge[fVerb]; } @@ -637,12 +720,14 @@ public: fBounds.set(pts, 2); } - const SkPoint& addMoveTo(int tIndex, SkPath& path) { - const SkPoint& pt = xyAtT(&fTs[tIndex]); + const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) { + const SkPoint& pt = xyAtT(tIndex); + if (active) { #if DEBUG_PATH_CONSTRUCTION - SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY); + SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY); #endif - path.moveTo(pt.fX, pt.fY); + path.moveTo(pt.fX, pt.fY); + } return pt; } @@ -657,50 +742,233 @@ public: init(pts, SkPath::kQuad_Verb); fBounds.setQuadBounds(pts); } + + // Defer all coincident edge processing until + // after normal intersections have been computed + +// no need to be tricky; insert in normal T order +// resolve overlapping ts when considering coincidence later - // edges are sorted by T, then by coincidence - int addT(double newT, Segment& other, int coincident) { + // add non-coincident intersection. Resulting edges are sorted in T. + int addT(double newT, Segment* other) { // FIXME: in the pathological case where there is a ton of intercepts, // binary search? int insertedAt = -1; - Span* span; size_t tCount = fTs.count(); - for (size_t idx2 = 0; idx2 < tCount; ++idx2) { + for (size_t index = 0; index < tCount; ++index) { // OPTIMIZATION: if there are three or more identical Ts, then // the fourth and following could be further insertion-sorted so // that all the edges are clockwise or counterclockwise. // This could later limit segment tests to the two adjacent // neighbors, although it doesn't help with determining which // circular direction to go in. - if (newT < fTs[idx2].fT || (newT == fTs[idx2].fT && - coincident <= fTs[idx2].fCoincident)) { - insertedAt = idx2; - span = fTs.insert(idx2); - goto finish; + if (newT < fTs[index].fT) { + insertedAt = index; + break; } } - insertedAt = tCount; - span = fTs.append(); -finish: + Span* span; + if (insertedAt >= 0) { + span = fTs.insert(insertedAt); + } else { + insertedAt = tCount; + span = fTs.append(); + } span->fT = newT; - span->fOther = &other; + span->fOther = other; span->fPt = NULL; - span->fWinding = 0; - if (span->fDone = newT == 1) { + span->fWindSum = SK_MinS32; + span->fWindValue = 1; + if ((span->fDone = newT == 1)) { ++fDoneSpans; } - span->fCoincident = coincident; - fCoincident |= coincident; // OPTIMIZATION: ever used? return insertedAt; } - void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) { + // set spans from start to end to decrement by one + // note this walks other backwards + // FIMXE: there's probably an edge case that can be constructed where + // two span in one segment are separated by float epsilon on one span but + // not the other, if one segment is very small. For this + // case the counts asserted below may or may not be enough to separate the + // spans. Even if the counts work out, what if the spanw aren't correctly + // sorted? It feels better in such a case to match the span's other span + // pointer since both coincident segments must contain the same spans. + void addTCancel(double startT, double endT, Segment& other, + double oStartT, double oEndT) { + SkASSERT(endT - startT >= FLT_EPSILON); + SkASSERT(oEndT - oStartT >= FLT_EPSILON); + int index = 0; + while (startT - fTs[index].fT >= FLT_EPSILON) { + ++index; + } + int oCount = other.fTs.count(); + while (other.fTs[--oCount].fT - oEndT >= FLT_EPSILON) + ; + int oIndex = oCount; + while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON) + ; + Span* test = &fTs[index]; + Span* oTest = &other.fTs[oIndex]; + SkDEBUGCODE(int testWindValue = test->fWindValue); + SkDEBUGCODE(int oTestWindValue = oTest->fWindValue); + SkDEBUGCODE(int startIndex = index); + SkTDArray<double> outsideTs; + SkTDArray<double> oOutsideTs; + do { + bool decrement = test->fWindValue && oTest->fWindValue; + Span* end = test; + double startT = end->fT; + double oStartT = oTest->fT; + do { + SkASSERT(testWindValue == end->fWindValue); + if (decrement) { + if (--(end->fWindValue) == 0) { + end->fDone = true; + ++fDoneSpans; + *outsideTs.append() = end->fT; + *outsideTs.append() = oStartT; + } + } + end = &fTs[++index]; + } while (end->fT - test->fT < FLT_EPSILON); + SkASSERT(oCount - oIndex == index - startIndex); + Span* oTestStart = oTest; + SkDEBUGCODE(oCount = oIndex); + do { + SkASSERT(oTestWindValue == oTestStart->fWindValue); + if (decrement) { + if (--(oTestStart->fWindValue) == 0) { + oTestStart->fDone = true; + ++other.fDoneSpans; + *oOutsideTs.append() = oTestStart->fT; + *oOutsideTs.append() = startT; + } + } + if (!oIndex) { + break; + } + oTestStart = &other.fTs[--oIndex]; + } while (oTest->fT - oTestStart->fT < FLT_EPSILON); + test = end; + oTest = oTestStart; + } while (test->fT < endT - FLT_EPSILON); + SkASSERT(!oIndex || oTest->fT <= oStartT - FLT_EPSILON); +#if 0 + if (!done() && outsideTs.count()) { + addTOutsides(outsideTs, &other, oStartT); + } + if (!other.done() && oOutsideTs.count()) { + other.addTOutsides(oOutsideTs, this, startT); + } +#endif + } + + // set spans from start to end to increment the greater by one and decrement + // the lesser + void addTCoincident(double startT, double endT, Segment& other, + double oStartT, double oEndT) { + SkASSERT(endT - startT >= FLT_EPSILON); + SkASSERT(oEndT - oStartT >= FLT_EPSILON); + int index = 0; + while (startT - fTs[index].fT >= FLT_EPSILON) { + ++index; + } + int oIndex = 0; + while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) { + ++oIndex; + } + Span* test = &fTs[index]; + Span* oTest = &other.fTs[oIndex]; + SkDEBUGCODE(int testWindValue = test->fWindValue); + SkDEBUGCODE(int oTestWindValue = oTest->fWindValue); + SkTDArray<double> outsideTs; + SkTDArray<double> oOutsideTs; + do { + bool decrementOther = test->fWindValue >= oTest->fWindValue; + Span* end = test; + double startT = end->fT; + double oStartT = oTest->fT; + do { + SkASSERT(testWindValue == end->fWindValue); + if (decrementOther) { + ++(end->fWindValue); + } else { + if (--(end->fWindValue) == 0) { + end->fDone = true; + ++fDoneSpans; + *outsideTs.append() = end->fT; + *outsideTs.append() = oStartT; + } + } + end = &fTs[++index]; + } while (end->fT - test->fT < FLT_EPSILON); + Span* oEnd = oTest; + do { + SkASSERT(oTestWindValue == oEnd->fWindValue); + if (decrementOther) { + if (--(oEnd->fWindValue) == 0) { + oEnd->fDone = true; + ++other.fDoneSpans; + *oOutsideTs.append() = oEnd->fT; + *oOutsideTs.append() = startT; + } + } else { + ++(oEnd->fWindValue); + } + oEnd = &other.fTs[++oIndex]; + } while (oEnd->fT - oTest->fT < FLT_EPSILON); + test = end; + oTest = oEnd; + } while (test->fT < endT - FLT_EPSILON); + SkASSERT(oTest->fT < oEndT + FLT_EPSILON); + SkASSERT(oTest->fT > oEndT - FLT_EPSILON); + if (!done() && outsideTs.count()) { + addTOutsides(outsideTs, &other, oEndT); + } + if (!other.done() && oOutsideTs.count()) { + other.addTOutsides(oOutsideTs, this, endT); + } + } + + void addTOutsides(const SkTDArray<double>& outsideTs, Segment* other, + double otherEnd) { + int count = outsideTs.count(); + double endT = 0; + int endSpan = 0; + for (int index = 0; index < count; index += 2) { + double t = outsideTs[index]; + double otherT = outsideTs[index + 1]; + if (t > 1 - FLT_EPSILON) { + return; + } + if (t - endT > FLT_EPSILON) { + endSpan = addTPair(t, other, otherT); + } + do { + endT = fTs[++endSpan].fT; + } while (endT - t < FLT_EPSILON); + } + addTPair(endT, other, otherEnd); + } + + int addTPair(double t, Segment* other, double otherT) { + int insertedAt = addT(t, other); + int otherInsertedAt = other->addT(otherT, this); + addOtherT(insertedAt, otherT, otherInsertedAt); + other->addOtherT(otherInsertedAt, t, insertedAt); + return insertedAt; + } + + void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { // add edge leading into junction - addAngle(angles, end, start); + if (fTs[SkMin32(end, start)].fWindValue > 0) { + addAngle(angles, end, start); + } // add edge leading away from junction int step = SkSign32(end - start); int tIndex = nextSpan(end, step); - if (tIndex >= 0) { + if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) { addAngle(angles, end, tIndex); } } @@ -710,15 +978,14 @@ finish: } void buildAngles(int index, SkTDArray<Angle>& angles) const { - SkASSERT(!done()); double referenceT = fTs[index].fT; int lesser = index; - while (--lesser >= 0 && referenceT == fTs[lesser].fT) { + while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { buildAnglesInner(lesser, angles); } do { buildAnglesInner(index, angles); - } while (++index < fTs.count() && referenceT == fTs[index].fT); + } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); } void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { @@ -731,15 +998,22 @@ finish: int oIndex = span->fOtherIndex; // if done == -1, prior span has already been processed int step = 1; - int next = other->nextSpanEnd(oIndex, step); + int next = other->nextSpan(oIndex, step); if (next < 0) { step = -step; - next = other->nextSpanEnd(oIndex, step); + next = other->nextSpan(oIndex, step); } - oIndex = other->coincidentEnd(oIndex, -step); // add candidate into and away from junction other->addTwoAngles(next, oIndex, angles); - } + } + + // OPTIMIZATION: inefficient, refactor + bool cancels(const Segment& other) const { + SkTDArray<Angle> angles; + addAngle(angles, 0, fTs.count() - 1); + other.addAngle(angles, 0, other.fTs.count() - 1); + return angles[0].cancels(angles[1]); + } // figure out if the segment's ascending T goes clockwise or not // not enough context to write this as shown @@ -752,45 +1026,41 @@ finish: return false; } - static bool Coincident(const Angle* current, const Angle* next) { - const Segment* segment = current->segment(); - const Span& span = segment->fTs[current->start()]; - if (!span.fCoincident) { - return false; - } - const Segment* nextSegment = next->segment(); - const Span& nextSpan = nextSegment->fTs[next->start()]; - if (!nextSpan.fCoincident) { - return false; - } - // use angle dx/dy instead of other since 3 or more may be coincident - return current->slopeEquals(*next); - } - - static bool CoincidentCancels(const Angle* current, const Angle* next) { - return SkSign32(current->start() - current->end()) - != SkSign32(next->start() - next->end()); - } - - int coincidentEnd(int from, int step) const { - double fromT = fTs[from].fT; - int count = fTs.count(); - int to = from; - while (step > 0 ? ++to < count : --to >= 0) { - const Span& span = fTs[to]; - if (fromT != span.fT) { - // FIXME: we assume that if the T changes, we don't care about - // coincident -- but in nextSpan, we require that both the T - // and actual loc change to represent a span. This asymettry may - // be OK or may be trouble -- if trouble, probably will need to - // detect coincidence earlier or sort differently - break; + int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const { + int start = 0; + int bestT = -1; + SkScalar top = bounds().fTop; + SkScalar bottom = bounds().fBottom; + int end; + do { + end = nextSpan(start, 1); + SkPoint edge[4]; + // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can + // work with the original data directly + (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); + // start here; intersect ray starting at basePt with edge + Intersections intersections; + int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX, + false, intersections); + if (pts == 0) { + continue; } - if (span.fCoincident == step) { - return to; + if (pts > 1 && fVerb == SkPath::kLine_Verb) { + // if the intersection is edge on, wait for another one + continue; } - } - return from; + SkASSERT(pts == 1); // FIXME: more code required to disambiguate + SkPoint pt; + double foundT = intersections.fT[0][0]; + (*SegmentXYAtT[fVerb])(fPts, foundT, &pt); + if (bestY < pt.fY) { + bestY = pt.fY; + bestT = foundT < 1 ? start : end; + hitT = foundT; + } + start = end; + } while (fTs[end].fT != 1); + return bestT; } bool done() const { @@ -798,37 +1068,46 @@ finish: return fDoneSpans == fTs.count(); } + // so the span needs to contain the pairing info found here + // this should include the winding computed for the edge, and + // what edge it connects to, and whether it is discarded + // (maybe discarded == abs(winding) > 1) ? + // only need derivatives for duration of sorting, add a new struct + // for pairings, remove extra spans that have zero length and + // reference an unused other + // for coincident, the last span on the other may be marked done + // (always?) + + // if loop is exhausted, contour may be closed. + // FIXME: pass in close point so we can check for closure + + // given a segment, and a sense of where 'inside' is, return the next + // segment. If this segment has an intersection, or ends in multiple + // segments, find the mate that continues the outside. + // note that if there are multiples, but no coincidence, we can limit + // choices to connections in the correct direction + + // mark found segments as done + // start is the index of the beginning T of this edge // it is guaranteed to have an end which describes a non-zero length (?) // winding -1 means ccw, 1 means cw - // step is in/out -1 or 1 - // spanIndex is returned + // firstFind allows coincident edges to be treated differently Segment* findNext(int winding, const int startIndex, const int endIndex, - int& nextStart, int& nextEnd) { + int& nextStart, int& nextEnd, bool firstFind) { SkASSERT(startIndex != endIndex); int count = fTs.count(); SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); - int step = SkSign32(endIndex - startIndex); - int end = nextSpanEnd(startIndex, step); + int end = nextSpan(startIndex, step); SkASSERT(end >= 0); - - // preflight for coincidence -- if present, it may change winding - // considerations and whether reversed edges can be followed - - // Discard opposing direction candidates if no coincidence was found. Span* endSpan = &fTs[end]; Segment* other; - if (isSimple(end, step)) { + if (isSimple(end)) { // mark the smaller of startIndex, endIndex done, and all adjacent // spans with the same T value (but not 'other' spans) markDone(SkMin32(startIndex, endIndex), winding); - // move in winding direction until edge in correct direction - // balance wrong direction edges before finding correct one - // this requres that the intersection is angularly sorted - // for a single intersection, special case -- choose the opposite - // edge that steps the same other = endSpan->fOther; nextStart = endSpan->fOtherIndex; nextEnd = nextStart + step; @@ -857,106 +1136,65 @@ finish: } } // back up if prior edge is coincident with firstIndex - int prior = firstIndex; - do { - if (--prior < 0) { - prior = angleCount - 1; - } - SkASSERT(prior != angleIndex); - if (!Coincident(sorted[prior], sorted[firstIndex])) { - break; - } - firstIndex = prior; - angle = sorted[prior]; - } while (true); - - // put some thought into handling coincident edges - // 1) defer the initial moveTo/curveTo until we know that firstIndex - // isn't coincident (although maybe findTop could tell us that) - // 2) allow the below to mark and skip coincident pairs - // 3) return something (null?) if all segments cancel each other out - // 4) if coincident edges don't cancel, figure out which to return (follow) - + // adjustFirst(sorted, firstIndex, winding, firstFind); SkASSERT(firstIndex >= 0); int startWinding = winding; - int nextIndex = firstIndex; - const Angle* nextAngle; - Segment* nextSegment; + int nextIndex = firstIndex + 1; + int lastIndex = firstIndex != 0 ? firstIndex : angleCount; + const Angle* foundAngle = NULL; + // bool alreadyMarked = angle->segment()->fTs[SkMin32(angle->start(), + // angle->end())].fDone; + // iterate through the angle, and compute everyone's winding + bool firstEdge = true; do { - if (++nextIndex == angleCount) { + if (nextIndex == angleCount) { nextIndex = 0; } - SkASSERT(nextIndex != firstIndex); // should never wrap around - nextAngle = sorted[nextIndex]; + const Angle* nextAngle = sorted[nextIndex]; int maxWinding = winding; - winding -= nextAngle->sign(); - nextSegment = nextAngle->segment(); - if (nextSegment->done()) { - if (!winding) { - break; - } - continue; - } - bool pairCoincides = Coincident(angle, nextAngle); - bool pairCancels = pairCoincides - && CoincidentCancels(angle, nextAngle); - if (pairCancels) { - angle->segment()->markAndChaseCoincident(angle->start(), - angle->end(), nextSegment); - return NULL; - } + Segment* nextSegment = nextAngle->segment(); + int windValue = nextSegment->windValue(nextAngle); + SkASSERT(windValue > 0); + winding -= nextAngle->sign() * windValue; + firstEdge = false; if (!winding) { - break; - } - if (pairCoincides) { - bool markNext = abs(maxWinding) < abs(winding); - if (markNext) { - nextSegment->markDone(SkMin32(nextAngle->start(), - nextAngle->end()), winding); - } else { - angle->segment()->markDone(SkMin32(angle->start(), - angle->end()), maxWinding); + if (!foundAngle) { + foundAngle = nextAngle; } + goto doNext; + } + if (nextSegment->done()) { + goto doNext; } // if the winding is non-zero, nextAngle does not connect to // current chain. If we haven't done so already, mark the angle // as done, record the winding value, and mark connected unambiguous // segments as well. - else if (nextSegment->winding(nextAngle) == 0) { + if (nextSegment->winding(nextAngle) == SK_MinS32) { if (abs(maxWinding) < abs(winding)) { maxWinding = winding; } - nextSegment->markAndChaseWinding(nextAngle, maxWinding); + if (foundAngle) { + nextSegment->markAndChaseWinding(nextAngle, maxWinding); + } else { + nextSegment->markAndChaseDone(nextAngle, maxWinding); + } } - } while ((angle = nextAngle)); // always true - markDone(SkMin32(startIndex, endIndex), startWinding); - nextStart = nextAngle->start(); - nextEnd = nextAngle->end(); - return nextSegment; + doNext: + angle = nextAngle; + } while (++nextIndex != lastIndex); + // if (!alreadyMarked) { + sorted[firstIndex]->segment()-> + markDone(SkMin32(startIndex, endIndex), startWinding); + // } + if (!foundAngle) { + return NULL; + } + nextStart = foundAngle->start(); + nextEnd = foundAngle->end(); + return foundAngle->segment(); } - - // so the span needs to contain the pairing info found here - // this should include the winding computed for the edge, and - // what edge it connects to, and whether it is discarded - // (maybe discarded == abs(winding) > 1) ? - // only need derivatives for duration of sorting, add a new struct - // for pairings, remove extra spans that have zero length and - // reference an unused other - // for coincident, the last span on the other may be marked done - // (always?) - - // if loop is exhausted, contour may be closed. - // FIXME: pass in close point so we can check for closure - - // given a segment, and a sense of where 'inside' is, return the next - // segment. If this segment has an intersection, or ends in multiple - // segments, find the mate that continues the outside. - // note that if there are multiples, but no coincidence, we can limit - // choices to connections in the correct direction - - // mark found segments as done - // FIXME: this is tricky code; needs its own unit test void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered int count = fTs.count(); @@ -985,7 +1223,7 @@ finish: // so, the span from here to there is coincident. for (int index = matchIndex + 1; index < count; ++index) { Span* test = &fTs[index]; - if (test->fCoincident) { + if (test->fDone) { continue; } Segment* tOther = test->fOther; @@ -1007,7 +1245,7 @@ finish: double moStartT, moEndT; for (int moIndex = 0; moIndex < moCount; ++moIndex) { Span& moSpan = mOther->fTs[moIndex]; - if (moSpan.fCoincident) { + if (moSpan.fDone) { continue; } if (moSpan.fOther == this) { @@ -1060,11 +1298,16 @@ finish: || !tOther->isLinear(toStart, toEnd)) { continue; } - // FIXME: may need to resort if we depend on coincidence first, last - mOther->fTs[moStart].fCoincident = -1; - tOther->fTs[toStart].fCoincident = -1; - mOther->fTs[moEnd].fCoincident = 1; - tOther->fTs[toEnd].fCoincident = 1; + // FIXME: defer implementation until the rest works + // this may share code with regular coincident detection + SkASSERT(0); + #if 0 + if (flipped) { + mOther->addTCancel(moStart, moEnd, tOther, tStart, tEnd); + } else { + mOther->addTCoincident(moStart, moEnd, tOther, tStart, tEnd); + } + #endif } } @@ -1077,10 +1320,10 @@ finish: SkASSERT(!done()); int firstT; int lastT; - int firstCoinT; SkPoint topPt; topPt.fY = SK_ScalarMax; int count = fTs.count(); + // see if either end is not done since we want smaller Y of the pair bool lastDone = true; for (int index = 0; index < count; ++index) { const Span& span = fTs[index]; @@ -1089,22 +1332,13 @@ finish: if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY && topPt.fX > intercept.fX)) { topPt = intercept; - firstT = lastT = firstCoinT = index; + firstT = lastT = index; } else if (topPt == intercept) { lastT = index; - if (span.fCoincident) { - firstCoinT = index; - } } } lastDone = span.fDone; } - // if there's only a pair of segments, go with the endpoint chosen above - if (firstT == lastT) { - tIndex = firstT; - endIndex = firstT > 0 ? tIndex - 1 : tIndex + 1; - return this; - } // sort the edges to find the leftmost int step = 1; int end = nextSpan(firstT, step); @@ -1117,7 +1351,7 @@ finish: // look for left-ness from tLeft to firstT (matching y of other) SkTDArray<Angle> angles; SkASSERT(firstT - end != 0); - addTwoAngles(end, firstCoinT, angles); + addTwoAngles(end, firstT, angles); buildAngles(firstT, angles); SkTDArray<Angle*> sorted; sortAngles(angles, sorted); @@ -1150,93 +1384,27 @@ finish: Span& oSpan = other->fTs[o]; if (oT == oSpan.fT && this == oSpan.fOther) { iSpan.fOtherIndex = o; + break; } } } } // OPTIMIZATION: uses tail recursion. Unwise? - void innerCoincidentChase(int step, Segment* other) { - // find other at index - SkASSERT(!done()); - const Span* start = NULL; - const Span* end = NULL; - int index, startIndex, endIndex; - int count = fTs.count(); - for (index = 0; index < count; ++index) { - const Span& span = fTs[index]; - if (!span.fCoincident || span.fOther != other) { - continue; - } - if (!start) { - if (span.fDone) { - continue; - } - startIndex = index; - start = &span; - } else { - SkASSERT(!end); - endIndex = index; - end = &span; - } - } - if (!end) { + void innerChaseDone(int index, int step, int winding) { + int end = nextSpan(index, step); + if (multipleSpans(end, step)) { return; } - Segment* next; - Segment* nextOther; - if (step < 0) { - next = start->fT == 0 ? NULL : this; - nextOther = other->fTs[start->fOtherIndex].fT == 1 ? NULL : other; - } else { - next = end->fT == 1 ? NULL : this; - nextOther = other->fTs[end->fOtherIndex].fT == 0 ? NULL : other; - } - SkASSERT(!next || !nextOther); - for (index = 0; index < count; ++index) { - const Span& span = fTs[index]; - if (span.fCoincident || span.fOther == other) { - continue; - } - bool checkNext = !next && (step < 0 ? span.fT == 0 - && span.fOtherT == 1 : span.fT == 1 && span.fOtherT == 0); - bool checkOther = !nextOther && (step < 0 ? span.fT == start->fT - && span.fOtherT == 0 : span.fT == end->fT && span.fOtherT == 1); - if (!checkNext && !checkOther) { - continue; - } - Segment* oSegment = span.fOther; - if (oSegment->done()) { - continue; - } - int oCount = oSegment->fTs.count(); - for (int oIndex = 0; oIndex < oCount; ++oIndex) { - const Span& oSpan = oSegment->fTs[oIndex]; - if (oSpan.fT > 0 && oSpan.fT < 1) { - continue; - } - if (!oSpan.fCoincident) { - continue; - } - if (checkNext && (oSpan.fT == 0 ^ step < 0)) { - next = oSegment; - checkNext = false; - } - if (checkOther && (oSpan.fT == 1 ^ step < 0)) { - nextOther = oSegment; - checkOther = false; - } - } - } - markDone(SkMin32(startIndex, endIndex), 0); - other->markDone(SkMin32(start->fOtherIndex, end->fOtherIndex), 0); - if (next && nextOther) { - next->innerCoincidentChase(step, nextOther); - } + const Span& endSpan = fTs[end]; + Segment* other = endSpan.fOther; + index = endSpan.fOtherIndex; + int otherEnd = other->nextSpan(index, step); + other->innerChaseDone(index, step, winding); + other->markDone(SkMin32(index, otherEnd), winding); } - // OPTIMIZATION: uses tail recursion. Unwise? - void innerChase(int index, int step, int winding) { + void innerChaseWinding(int index, int step, int winding) { int end = nextSpan(index, step); if (multipleSpans(end, step)) { return; @@ -1245,15 +1413,19 @@ finish: Segment* other = endSpan.fOther; index = endSpan.fOtherIndex; int otherEnd = other->nextSpan(index, step); - other->innerChase(index, step, winding); - other->markDone(SkMin32(index, otherEnd), winding); + int min = SkMin32(index, otherEnd); + if (other->fTs[min].fWindSum != SK_MinS32) { + SkASSERT(other->fTs[index].fWindSum == winding); + return; + } + other->innerChaseWinding(index, step, winding); + other->markWinding(min, winding); } void init(const SkPoint pts[], SkPath::Verb verb) { fPts = pts; fVerb = verb; fDoneSpans = 0; - fCoincident = 0; } bool intersected() const { @@ -1276,27 +1448,19 @@ finish: } } - bool isSimple(int index, int step) const { + bool isSimple(int end) const { int count = fTs.count(); if (count == 2) { return true; } - double spanT = fTs[index].fT; - if (spanT > 0 && spanT < 1) { - return false; - } - if (step < 0) { - const Span& secondSpan = fTs[1]; - if (secondSpan.fT == 0) { - return false; - } - return xyAtT(&fTs[0]) != xyAtT(&secondSpan); + double t = fTs[end].fT; + if (t < FLT_EPSILON) { + return fTs[1].fT >= FLT_EPSILON; } - const Span& penultimateSpan = fTs[count - 2]; - if (penultimateSpan.fT == 1) { - return false; + if (t > 1 - FLT_EPSILON) { + return fTs[count - 2].fT <= 1 - FLT_EPSILON; } - return xyAtT(&fTs[count - 1]) != xyAtT(&penultimateSpan); + return false; } bool isHorizontal() const { @@ -1311,51 +1475,101 @@ finish: return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); } - void markAndChaseCoincident(int index, int endIndex, Segment* other) { - int step = SkSign32(endIndex - index); - innerCoincidentChase(step, other); - } - // this span is excluded by the winding rule -- chase the ends // as long as they are unambiguous to mark connections as done // and give them the same winding value - void markAndChaseWinding(const Angle* angle, int winding) { + void markAndChaseDone(const Angle* angle, int winding) { int index = angle->start(); int endIndex = angle->end(); int step = SkSign32(endIndex - index); - innerChase(index, step, winding); + innerChaseDone(index, step, winding); markDone(SkMin32(index, endIndex), winding); } + void markAndChaseWinding(const Angle* angle, int winding) { + int index = angle->start(); + int endIndex = angle->end(); + int min = SkMin32(index, endIndex); + int step = SkSign32(endIndex - index); + innerChaseWinding(index, step, winding); + markWinding(min, winding); + } + // FIXME: this should also mark spans with equal (x,y) + // This may be called when the segment is already marked done. While this + // wastes time, it shouldn't do any more than spin through the T spans. + // OPTIMIZATION: abort on first done found (assuming that this code is + // always called to mark segments done). void markDone(int index, int winding) { - SkASSERT(!done()); + // SkASSERT(!done()); double referenceT = fTs[index].fT; int lesser = index; - while (--lesser >= 0 && referenceT == fTs[lesser].fT) { + while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { Span& span = fTs[lesser]; - // FIXME: this needs to assert that all are not done or one or more are - // coincident - // SkASSERT(!span.fDone || span.fCoincident); if (span.fDone) { continue; } + #if DEBUG_MARK_DONE + const SkPoint& pt = xyAtT(&span); + SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", + __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); + #endif span.fDone = true; - SkASSERT(!span.fWinding || span.fWinding == winding); - span.fWinding = winding; + SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); + span.fWindSum = winding; fDoneSpans++; } do { Span& span = fTs[index]; - // SkASSERT(!span.fDone || span.fCoincident); + // SkASSERT(!span.fDone); if (span.fDone) { continue; } + #if DEBUG_MARK_DONE + const SkPoint& pt = xyAtT(&span); + SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", + __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); + #endif span.fDone = true; - SkASSERT(!span.fWinding || span.fWinding == winding); - span.fWinding = winding; + SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); + span.fWindSum = winding; fDoneSpans++; - } while (++index < fTs.count() && referenceT == fTs[index].fT); + } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); + } + + void markWinding(int index, int winding) { + SkASSERT(!done()); + double referenceT = fTs[index].fT; + int lesser = index; + while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { + Span& span = fTs[lesser]; + if (span.fDone) { + continue; + } + SkASSERT(span.fWindValue == 1 || winding == 0); + SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); + #if DEBUG_MARK_DONE + const SkPoint& pt = xyAtT(&span); + SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", + __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); + #endif + span.fWindSum = winding; + } + do { + Span& span = fTs[index]; + // SkASSERT(!span.fDone || span.fCoincident); + if (span.fDone) { + continue; + } + SkASSERT(span.fWindValue == 1 || winding == 0); + SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); + #if DEBUG_MARK_DONE + const SkPoint& pt = xyAtT(&span); + SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", + __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); + #endif + span.fWindSum = winding; + } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); } bool multipleSpans(int end, int step) const { @@ -1368,18 +1582,14 @@ finish: // coincidence is found when the beginning Ts contain -step and the end // contains step. When it is looking for the beginning of the next, the // first Ts found can be ignored and the last Ts should contain -step. + // OPTIMIZATION: probably should split into two functions int nextSpan(int from, int step) const { const Span& fromSpan = fTs[from]; int count = fTs.count(); int to = from; while (step > 0 ? ++to < count : --to >= 0) { const Span& span = fTs[to]; - if (fromSpan.fT == span.fT) { - continue; - } - const SkPoint& loc = xyAtT(&span); - const SkPoint& fromLoc = xyAtT(&fromSpan); - if (fromLoc == loc) { + if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) { continue; } return to; @@ -1387,16 +1597,6 @@ finish: return -1; } - // once past current span, if step>0, look for coicident==1 - // if step<0, look for coincident==-1 - int nextSpanEnd(int from, int step) const { - int result = nextSpan(from, step); - if (result < 0) { - return result; - } - return coincidentEnd(result, step); - } - const SkPoint* pts() const { return fPts; } @@ -1411,6 +1611,11 @@ finish: const Span& span(int tIndex) const { return fTs[tIndex]; } + + int spanSign(int startIndex, int endIndex) const { + return startIndex < endIndex ? -fTs[startIndex].fWindValue : + fTs[endIndex].fWindValue; + } // OPTIMIZATION: mark as debugging only if used solely by tests double t(int tIndex) const { @@ -1424,18 +1629,64 @@ finish: SkPath::Verb verb() const { return fVerb; } + + // if the only remaining spans are small, ignore them, and mark done + bool virtuallyDone() { + int count = fTs.count(); + double previous = 0; + bool previousDone = fTs[0].fDone; + for (int index = 1; index < count; ++index) { + Span& span = fTs[index]; + double t = span.fT; + if (t - previous < FLT_EPSILON) { + if (span.fDone && !previousDone) { + int prior = --index; + int winding = span.fWindSum; + do { + Span& priorSpan = fTs[prior]; + priorSpan.fDone = true; + priorSpan.fWindSum = winding; + fDoneSpans++; + } while (--prior >= 0 && t - fTs[prior].fT < FLT_EPSILON); + } + } else if (!previousDone) { + return false; + } + previous = t; + previousDone = span.fDone; + } + SkASSERT(done()); + return true; + } + + int winding(int tIndex) const { + return fTs[tIndex].fWindSum; + } - bool winding(const Angle* angle) { + int winding(const Angle* angle) const { int start = angle->start(); int end = angle->end(); int index = SkMin32(start, end); - Span& span = fTs[index]; - return span.fWinding; + return winding(index); + } + + int windValue(int tIndex) const { + return fTs[tIndex].fWindValue; + } + + int windValue(const Angle* angle) const { + int start = angle->start(); + int end = angle->end(); + int index = SkMin32(start, end); + return windValue(index); + } + + SkScalar xAtT(const Span* span) const { + return xyAtT(span).fX; } - SkScalar xAtT(double t) const { - SkASSERT(t >= 0 && t <= 1); - return (*SegmentXAtT[fVerb])(fPts, t); + const SkPoint& xyAtT(int index) const { + return xyAtT(&fTs[index]); } const SkPoint& xyAtT(const Span* span) const { @@ -1452,10 +1703,13 @@ finish: } return *span->fPt; } + + SkScalar yAtT(int index) const { + return yAtT(&fTs[index]); + } - SkScalar yAtT(double t) const { - SkASSERT(t >= 0 && t <= 1); - return (*SegmentYAtT[fVerb])(fPts, t); + SkScalar yAtT(const Span* span) const { + return xyAtT(span).fY; } #if DEBUG_DUMP @@ -1466,10 +1720,10 @@ finish: SkPoint out; (*SegmentXYAtT[fVerb])(fPts, t(i), &out); SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" - " otherT=%1.9g winding=%d\n", + " otherT=%1.9g windSum=%d\n", tab + sizeof(className), className, fID, kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, - fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWinding); + fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum); } SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", tab + sizeof(className), className, fID, @@ -1486,14 +1740,17 @@ private: // be allocated as needed instead of always initialized -- though maybe // the initialization is lightweight enough that it hardly matters mutable SkTDArray<SkPoint> fIntersections; - // FIXME: coincident only needs two bits (-1, 0, 1) - int fCoincident; // non-zero if some coincident span inside int fDoneSpans; // used for quick check that segment is finished #if DEBUG_DUMP int fID; #endif }; +struct Coincidence { + Segment* fSegments[2]; + double fTs[2][2]; +}; + class Contour { public: Contour() { @@ -1509,6 +1766,26 @@ public: : fBounds.fTop < rh.fBounds.fTop; } + void addCoincident(int index, Contour* other, int otherIndex, + const Intersections& ts, bool swap) { + Coincidence& coincidence = *fCoincidences.append(); + coincidence.fSegments[0] = &fSegments[index]; + coincidence.fSegments[1] = &other->fSegments[otherIndex]; + coincidence.fTs[swap][0] = ts.fT[0][0]; + coincidence.fTs[swap][1] = ts.fT[0][1]; + coincidence.fTs[!swap][0] = ts.fT[1][0]; + coincidence.fTs[!swap][1] = ts.fT[1][1]; + } + + void addCross(const Contour* crosser) { +#ifdef DEBUG_CROSS + for (int index = 0; index < fCrosses.count(); ++index) { + SkASSERT(fCrosses[index] != crosser); + } +#endif + *fCrosses.append() = crosser; + } + void addCubic(const SkPoint pts[4]) { fSegments.push_back().addCubic(pts); fContainsCurves = true; @@ -1518,6 +1795,10 @@ public: fSegments.push_back().addLine(pts); return fSegments.count(); } + + void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) { + fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); + } int addQuad(const SkPoint pts[3]) { fSegments.push_back().addQuad(pts); @@ -1525,6 +1806,11 @@ public: return fSegments.count(); } + int addT(int segIndex, double newT, Contour* other, int otherIndex) { + containsIntercepts(); + return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]); + } + const Bounds& bounds() const { return fBounds; } @@ -1538,6 +1824,48 @@ public: fContainsIntercepts = true; } + const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY, + int &tIndex, double& hitT) { + int segmentCount = fSegments.count(); + const Segment* bestSegment = NULL; + for (int test = 0; test < segmentCount; ++test) { + Segment* testSegment = &fSegments[test]; + const SkRect& bounds = testSegment->bounds(); + if (bounds.fTop < bestY) { + continue; + } + if (bounds.fTop > basePt.fY) { + continue; + } + if (bounds.fLeft > basePt.fX) { + continue; + } + if (bounds.fRight < basePt.fX) { + continue; + } + double testHitT; + int testT = testSegment->crossedSpan(basePt, bestY, testHitT); + if (testT >= 0) { + bestSegment = testSegment; + tIndex = testT; + hitT = testHitT; + } + } + return bestSegment; + } + + bool crosses(const Contour* crosser) const { + if (this == crosser) { + return true; + } + for (int index = 0; index < fCrosses.count(); ++index) { + if (fCrosses[index] == crosser) { + return true; + } + } + return false; + } + void findTooCloseToCall(int winding) { int segmentCount = fSegments.count(); for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { @@ -1556,44 +1884,118 @@ public: fSegments.reset(); fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); fContainsCurves = fContainsIntercepts = false; + fWindingSum = -1; } + void resolveCoincidence(int winding) { + int count = fCoincidences.count(); + for (int index = 0; index < count; ++index) { + Coincidence& coincidence = fCoincidences[index]; + Segment* thisOne = coincidence.fSegments[0]; + Segment* other = coincidence.fSegments[1]; + double startT = coincidence.fTs[0][0]; + double endT = coincidence.fTs[0][1]; + if (startT > endT) { + SkTSwap<double>(startT, endT); + } + SkASSERT(endT - startT >= FLT_EPSILON); + double oStartT = coincidence.fTs[1][0]; + double oEndT = coincidence.fTs[1][1]; + if (oStartT > oEndT) { + SkTSwap<double>(oStartT, oEndT); + } + SkASSERT(oEndT - oStartT >= FLT_EPSILON); + if (winding > 0 || thisOne->cancels(*other)) { + thisOne->addTCancel(startT, endT, *other, oStartT, oEndT); + } else { + thisOne->addTCoincident(startT, endT, *other, oStartT, oEndT); + } + } + } + + const SkTArray<Segment>& segments() { + return fSegments; + } + + void setWinding(int winding) { + SkASSERT(fWindingSum < 0); + fWindingSum = winding; + } + // OPTIMIZATION: feel pretty uneasy about this. It seems like once again // we need to sort and walk edges in y, but that on the surface opens the // same can of worms as before. But then, this is a rough sort based on // segments' top, and not a true sort, so it could be ameniable to regular // sorting instead of linear searching. Still feel like I'm missing something - Segment* topSegment() { + Segment* topSegment(SkScalar& bestY) { int segmentCount = fSegments.count(); SkASSERT(segmentCount > 0); int best = -1; Segment* bestSegment = NULL; while (++best < segmentCount) { Segment* testSegment = &fSegments[best]; + #if 0 // FIXME: remove if not needed + if (testSegment->virtuallyDone()) { + continue; + } + #else if (testSegment->done()) { continue; } + #endif bestSegment = testSegment; break; } if (!bestSegment) { return NULL; } - SkScalar bestTop = bestSegment->bounds().fTop; + SkScalar bestTop = bestSegment->activeTop(); for (int test = best + 1; test < segmentCount; ++test) { Segment* testSegment = &fSegments[test]; if (testSegment->done()) { continue; } - SkScalar testTop = testSegment->bounds().fTop; + if (testSegment->bounds().fTop > bestTop) { + continue; + } + SkScalar testTop = testSegment->activeTop(); if (bestTop > testTop) { bestTop = testTop; bestSegment = testSegment; } } + bestY = bestTop; return bestSegment; } + int updateSegment(int index, const SkPoint* pts) { + Segment& segment = fSegments[index]; + segment.updatePts(pts); + return segment.verb() + 1; + } + + int winding() { + if (fWindingSum >= 0) { + return fWindingSum; + } + // check peers + int count = fCrosses.count(); + for (int index = 0; index < count; ++index) { + const Contour* crosser = fCrosses[index]; + if (0 <= crosser->fWindingSum) { + fWindingSum = crosser->fWindingSum; + break; + } + } + return fWindingSum; + } + +#if DEBUG_TEST + SkTArray<Segment>& debugSegments() { + return fSegments; + } +#endif + #if DEBUG_DUMP void dump() { int i; @@ -1627,17 +2029,18 @@ protected: } fBounds = fSegments.front().bounds(); for (int index = 1; index < count; ++index) { - fBounds.growToInclude(fSegments[index].bounds()); + fBounds.add(fSegments[index].bounds()); } } -public: - SkTArray<Segment> fSegments; // not worth accessor functions? - private: + SkTArray<Segment> fSegments; + SkTDArray<Coincidence> fCoincidences; + SkTDArray<const Contour*> fCrosses; Bounds fBounds; bool fContainsIntercepts; bool fContainsCurves; + int fWindingSum; // initial winding number outside #if DEBUG_DUMP int fID; #endif @@ -1661,7 +2064,7 @@ EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) protected: void complete() { - if (fCurrentContour && fCurrentContour->fSegments.count()) { + if (fCurrentContour && fCurrentContour->segments().count()) { fCurrentContour->complete(); fCurrentContour = NULL; } @@ -1755,25 +2158,24 @@ void walk() { SkASSERT(fCurrentContour); } complete(); - if (fCurrentContour && !fCurrentContour->fSegments.count()) { + if (fCurrentContour && !fCurrentContour->segments().count()) { fContours.pop_back(); } // correct pointers in contours since fReducePts may have moved as it grew int cIndex = 0; - fCurrentContour = &fContours[0]; int extraCount = fExtra.count(); - SkASSERT(fExtra[0] == -1); + SkASSERT(extraCount == 0 || fExtra[0] == -1); int eIndex = 0; int rIndex = 0; while (++eIndex < extraCount) { int offset = fExtra[eIndex]; if (offset < 0) { - fCurrentContour = &fContours[++cIndex]; + ++cIndex; continue; } - Segment& segment = fCurrentContour->fSegments[offset - 1]; - segment.updatePts(&fReducePts[rIndex]); - rIndex += segment.verb() + 1; + fCurrentContour = &fContours[cIndex]; + rIndex += fCurrentContour->updateSegment(offset - 1, + &fReducePts[rIndex]); } fExtra.reset(); // we're done with this } @@ -1797,11 +2199,15 @@ public: kQuad_Segment = SkPath::kQuad_Verb, kCubic_Segment = SkPath::kCubic_Verb, }; + + void addCoincident(Work& other, const Intersections& ts, bool swap) { + fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); + } // FIXME: does it make sense to write otherIndex now if we're going to // fix it up later? void addOtherT(int index, double otherT, int otherIndex) { - fContour->fSegments[fIndex].addOtherT(index, otherT, otherIndex); + fContour->addOtherT(fIndex, index, otherT, otherIndex); } // Avoid collapsing t values that are close to the same since @@ -1809,10 +2215,8 @@ public: // be nearly equal, any problems caused by this should be taken care // of later. // On the edge or out of range values are negative; add 2 to get end - int addT(double newT, const Work& other, int coincident) { - fContour->containsIntercepts(); - return fContour->fSegments[fIndex].addT(newT, - other.fContour->fSegments[other.fIndex], coincident); + int addT(double newT, const Work& other) { + return fContour->addT(fIndex, newT, other.fContour, other.fIndex); } bool advance() { @@ -1824,7 +2228,7 @@ public: } const Bounds& bounds() const { - return fContour->fSegments[fIndex].bounds(); + return fContour->segments()[fIndex].bounds(); } const SkPoint* cubic() const { @@ -1834,7 +2238,7 @@ public: void init(Contour* contour) { fContour = contour; fIndex = 0; - fLast = contour->fSegments.count(); + fLast = contour->segments().count(); } SkScalar left() const { @@ -1852,7 +2256,7 @@ public: } const SkPoint* pts() const { - return fContour->fSegments[fIndex].pts(); + return fContour->segments()[fIndex].pts(); } SkScalar right() const { @@ -1864,7 +2268,7 @@ public: } SegmentType segmentType() const { - const Segment& segment = fContour->fSegments[fIndex]; + const Segment& segment = fContour->segments()[fIndex]; SegmentType type = (SegmentType) segment.verb(); if (type != kLine_Segment) { return type; @@ -1888,7 +2292,7 @@ public: } SkPath::Verb verb() const { - return fContour->fSegments[fIndex].verb(); + return fContour->segments()[fIndex].verb(); } SkScalar x() const { @@ -1904,7 +2308,7 @@ public: } bool yFlipped() const { - return y() != pts()[0].fX; + return y() != pts()[0].fY; } protected: @@ -1959,6 +2363,7 @@ static bool addIntersectTs(Contour* test, Contour* next) { } Work wt; wt.init(test); + bool foundCommonContour = test == next; do { Work wn; wn.init(next); @@ -2116,70 +2521,155 @@ static bool addIntersectTs(Contour* test, Contour* next) { default: SkASSERT(0); } + if (!foundCommonContour && pts > 0) { + test->addCross(next); + next->addCross(test); + foundCommonContour = true; + } // in addition to recording T values, record matching segment - int testCoin; - int nextCoin; if (pts == 2 && wn.segmentType() <= Work::kLine_Segment && wt.segmentType() <= Work::kLine_Segment) { - // pass coincident so that smaller T is -1, larger T is 1 - testCoin = ts.fT[swap][0] < ts.fT[swap][1] ? -1 : 1; - nextCoin = ts.fT[!swap][0] < ts.fT[!swap][1] ? -1 : 1; - } else { - testCoin = nextCoin = 0; + wt.addCoincident(wn, ts, swap); + continue; } for (int pt = 0; pt < pts; ++pt) { SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); - int testTAt = wt.addT(ts.fT[swap][pt], wn, testCoin); - int nextTAt = wn.addT(ts.fT[!swap][pt], wt, nextCoin); + int testTAt = wt.addT(ts.fT[swap][pt], wn); + int nextTAt = wn.addT(ts.fT[!swap][pt], wt); wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt); wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt); - testCoin = -testCoin; - nextCoin = -nextCoin; } } while (wn.advance()); } while (wt.advance()); return true; } +// resolve any coincident pairs found while intersecting, and // see if coincidence is formed by clipping non-concident segments static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { int contourCount = contourList.count(); for (int cIndex = 0; cIndex < contourCount; ++cIndex) { Contour* contour = contourList[cIndex]; + contour->resolveCoincidence(winding); + } + for (int cIndex = 0; cIndex < contourCount; ++cIndex) { + Contour* contour = contourList[cIndex]; contour->findTooCloseToCall(winding); } } +// project a ray from the top of the contour up and see if it hits anything +// note: when we compute line intersections, we keep track of whether +// two contours touch, so we need only look at contours not touching this one. +// OPTIMIZATION: sort contourList vertically to avoid linear walk +static int innerContourCheck(SkTDArray<Contour*>& contourList, + Contour* baseContour, const SkPoint& basePt) { + int contourCount = contourList.count(); + int winding = 0; + SkScalar bestY = SK_ScalarMin; + for (int cTest = 0; cTest < contourCount; ++cTest) { + Contour* contour = contourList[cTest]; + if (basePt.fY < contour->bounds().fTop) { + continue; + } + if (bestY > contour->bounds().fBottom) { + continue; + } + if (baseContour->crosses(contour)) { + continue; + } + int tIndex; + double tHit; + const Segment* test = contour->crossedSegment(basePt, bestY, tIndex, + tHit); + if (!test) { + continue; + } + // If the ray hit the end of a span, we need to construct the wheel of + // angles to find the span closest to the ray -- even if there are just + // two spokes on the wheel. + if (tHit == test->t(tIndex)) { + SkTDArray<Angle> angles; + int end = test->nextSpan(tIndex, 1); + if (end < 0) { + end = test->nextSpan(tIndex, -1); + } + test->addTwoAngles(tIndex, end, angles); + // test->buildAnglesInner(tIndex, angles); + test->buildAngles(tIndex, angles); + SkTDArray<Angle*> sorted; + sortAngles(angles, sorted); + const Angle* angle = sorted[0]; + test = angle->segment(); + SkScalar testDx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); + if (testDx == 0) { + angle = *(sorted.end() - 1); + test = angle->segment(); + SkASSERT((*SegmentDXAtT[test->verb()])(test->pts(), tHit) != 0); + } + tIndex = angle->start(); // lesser Y + winding = test->winding(SkMin32(tIndex, angle->end())); + #if DEBUG_WINDING + SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding); + #endif + } else { + winding = test->winding(tIndex); + #if DEBUG_WINDING + SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding); + #endif + } + // see if a + change in T results in a +/- change in X (compute x'(T)) + SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); + #if DEBUG_WINDING + SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); + #endif + SkASSERT(dx != 0); + if (winding * dx > 0) { // if same signs, result is negative + winding += dx > 0 ? -1 : 1; + #if DEBUG_WINDING + SkDebugf("%s 3 winding=%d\n", __FUNCTION__, winding); + #endif + } + } + baseContour->setWinding(winding); + return winding; +} // OPTIMIZATION: not crazy about linear search here to find top active y. // seems like we should break down and do the sort, or maybe sort each // contours' segments? // Once the segment array is built, there's no reason I can think of not to // sort it in Y. hmmm +// FIXME: return the contour found to pass to inner contour check static Segment* findTopContour(SkTDArray<Contour*>& contourList, - int contourCount) { + Contour*& topContour) { + int contourCount = contourList.count(); int cIndex = 0; Segment* topStart; + SkScalar bestY = SK_ScalarMax; + Contour* contour; do { - Contour* topContour = contourList[cIndex]; - topStart = topContour->topSegment(); + contour = contourList[cIndex]; + topStart = contour->topSegment(bestY); } while (!topStart && ++cIndex < contourCount); if (!topStart) { return NULL; } - SkScalar top = topStart->bounds().fTop; - for (int cTest = cIndex + 1; cTest < contourCount; ++cTest) { - Contour* contour = contourList[cTest]; - if (top < contour->bounds().fTop) { + topContour = contour; + while (++cIndex < contourCount) { + contour = contourList[cIndex]; + if (bestY < contour->bounds().fTop) { continue; } - Segment* test = contour->topSegment(); - if (top > test->bounds().fTop) { - cIndex = cTest; - topStart = test; - top = test->bounds().fTop; + SkScalar testY = SK_ScalarMax; + Segment* test = contour->topSegment(testY); + if (!test || bestY <= testY) { + continue; } + topContour = contour; + topStart = test; + bestY = testY; } return topStart; } @@ -2194,36 +2684,65 @@ static Segment* findTopContour(SkTDArray<Contour*>& contourList, // since we start with leftmost top edge, we'll traverse through a // smaller angle counterclockwise to get to the next edge. static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { - int contourCount = contourList.count(); + // after findTopContour has already been called once, check if + // result of subsequent findTopContour has no winding set + bool firstContour = true; do { - Segment* topStart = findTopContour(contourList, contourCount); + Contour* topContour; + Segment* topStart = findTopContour(contourList, topContour); if (!topStart) { break; } - // FIXME: if this contour is inside others, winding will not be zero initially - int winding = 0; // zero says there are no contours outside this one // Start at the top. Above the top is outside, below is inside. // follow edges to intersection by changing the index by direction. int index, endIndex; Segment* current = topStart->findTop(index, endIndex); - winding += SkSign32(index - endIndex); + int winding; + int contourWinding; + if (firstContour) { + topContour->setWinding(0); + contourWinding = 0; + firstContour = false; + winding = 0; + } else { + winding = topContour->winding(); + #if DEBUG_WINDING + SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding); + #endif + if (!winding) { + const SkPoint& topPoint = current->xyAtT(endIndex); + winding = innerContourCheck(contourList, topContour, topPoint); + #if DEBUG_WINDING + SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding); + #endif + } + } const SkPoint* firstPt = NULL; SkPoint lastPt; + bool active = winding >= -1 && winding <= 1; + bool firstTime = true; + int spanWinding = current->spanSign(index, endIndex); + #if DEBUG_WINDING + SkDebugf("%s spanWinding=%d\n", __FUNCTION__, startWinding); + #endif do { SkASSERT(!current->done()); int nextStart, nextEnd; - Segment* next = current->findNext(winding, index, endIndex, - nextStart, nextEnd); + Segment* next = current->findNext(winding + spanWinding, index, + endIndex, nextStart, nextEnd, firstTime); if (!next) { break; } if (!firstPt) { - firstPt = ¤t->addMoveTo(index, simple); + firstPt = ¤t->addMoveTo(index, simple, active); } - lastPt = current->addCurveTo(index, endIndex, simple); + lastPt = current->addCurveTo(index, endIndex, simple, active); current = next; index = nextStart; endIndex = nextEnd; + spanWinding = SkSign32(spanWinding) * next->windValue( + SkMin32(nextStart, nextEnd)); + firstTime = false; } while (*firstPt != lastPt); if (firstPt) { #if DEBUG_PATH_CONSTRUCTION @@ -2232,8 +2751,6 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { simple.close(); } } while (true); - // FIXME: more work to be done for contained (but not intersecting) - // segments } static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { diff --git a/experimental/Intersection/Simplify.h b/experimental/Intersection/Simplify.h index ae338eedeb..a0b936abf0 100644 --- a/experimental/Intersection/Simplify.h +++ b/experimental/Intersection/Simplify.h @@ -5,6 +5,7 @@ * found in the LICENSE file. */ #include "CurveIntersection.h" +#include "CurveUtilities.h" #include "Intersections.h" #include "LineIntersection.h" #include "LineParameters.h" diff --git a/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp b/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp index da2569c5e0..09481c385a 100644 --- a/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp +++ b/experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp @@ -87,7 +87,7 @@ static void testPath(const SkPath& path, const SkPoint* pts1, SkPath::Verb c1Typ SimplifyAddIntersectingTsTest::Contour& c1 = contour[0]; SimplifyAddIntersectingTsTest::Contour& c2 = contour[1]; addIntersectTs(&c1, &c2); - bool c1Intersected = c1.fSegments[0].intersected(); + bool c1Intersected = c1.segments()[0].intersected(); // bool c2Intersected = c2.fSegments[0].intersected(); #if DEBUG_DUMP SkDebugf("%s %s (%1.9g,%1.9g %1.9g,%1.9g) %s %s (%1.9g,%1.9g %1.9g,%1.9g)\n", diff --git a/experimental/Intersection/SimplifyFindNext_Test.cpp b/experimental/Intersection/SimplifyFindNext_Test.cpp index 66af15bb0a..c8ca984c8d 100644 --- a/experimental/Intersection/SimplifyFindNext_Test.cpp +++ b/experimental/Intersection/SimplifyFindNext_Test.cpp @@ -5,6 +5,8 @@ * found in the LICENSE file. */ +#define DEBUG_TEST 1 + #include "Simplify.h" namespace SimplifyFindNextTest { @@ -27,12 +29,12 @@ static const SimplifyFindNextTest::Segment* testCommon( addIntersectTs(contourList[1], contourList[1]); } fixOtherTIndex(contourList); - SimplifyFindNextTest::Segment& segment = contours[0].fSegments[0]; + SimplifyFindNextTest::Segment& segment = contours[0].debugSegments()[0]; SkPoint pts[2]; pts[0] = segment.xyAtT(&segment.span(endIndex)); int nextStart, nextEnd; SimplifyFindNextTest::Segment* next = segment.findNext(winding, - startIndex, endIndex, nextStart, nextEnd); + startIndex, endIndex, nextStart, nextEnd, true); pts[1] = next->xyAtT(&next->span(nextStart)); SkASSERT(pts[0] == pts[1]); return next; diff --git a/experimental/Intersection/SimplifyFindTop_Test.cpp b/experimental/Intersection/SimplifyFindTop_Test.cpp index 2abde363cb..9e8d2bbfe7 100644 --- a/experimental/Intersection/SimplifyFindTop_Test.cpp +++ b/experimental/Intersection/SimplifyFindTop_Test.cpp @@ -27,8 +27,8 @@ static const SimplifyFindTopTest::Segment* testCommon( addIntersectTs(contourList[1], contourList[1]); } fixOtherTIndex(contourList); - SimplifyFindTopTest::Segment* topStart = findTopContour(contourList, - contourList.count()); + SimplifyFindTopTest::Contour* top; + SimplifyFindTopTest::Segment* topStart = findTopContour(contourList, top); const SimplifyFindTopTest::Segment* topSegment = topStart->findTop(index, end); return topSegment; diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index c99b8e9320..022518b8b3 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -5,29 +5,9 @@ * found in the LICENSE file. */ -#include "Simplify.h" - -namespace SimplifyNewTest { - -#include "Simplify.cpp" - -} // end of SimplifyNewTest namespace - #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" - -static bool testSimplifyx(const SkPath& path) { - if (false) { - showPath(path); - } - SkPath out; - simplifyx(path, out); - if (false) { - return true; - } - SkBitmap bitmap; - return comparePaths(path, out, bitmap, 0) == 0; -} +#include "ShapeOps.h" static void testLine1() { SkPath path, simple; @@ -146,17 +126,228 @@ static void testLine9() { testSimplifyx(path); } +static void testLine10() { + SkPath path, simple; + path.moveTo(0,4); + path.lineTo(4,4); + path.lineTo(2,2); + path.close(); + path.moveTo(2,1); + path.lineTo(3,4); + path.lineTo(6,1); + path.close(); + testSimplifyx(path); +} + +static void testLine10a() { + SkPath path, simple; + path.moveTo(0,4); + path.lineTo(8,4); + path.lineTo(4,0); + path.close(); + path.moveTo(2,2); + path.lineTo(3,3); + path.lineTo(4,2); + path.close(); + testSimplifyx(path); +} + +static void addCWContainer(SkPath& path) { + path.moveTo(6,4); + path.lineTo(0,4); + path.lineTo(3,1); + path.close(); +} + +static void addCCWContainer(SkPath& path) { + path.moveTo(0,4); + path.lineTo(6,4); + path.lineTo(3,1); + path.close(); +} + +static void addCWContents(SkPath& path) { + path.moveTo(2,3); + path.lineTo(3,2); + path.lineTo(4,3); + path.close(); +} + +static void addCCWContents(SkPath& path) { + path.moveTo(3,2); + path.lineTo(2,3); + path.lineTo(4,3); + path.close(); +} + +static void testLine11() { + SkPath path, simple; + addCWContainer(path); + addCWContents(path); + testSimplifyx(path); +} + +static void testLine12() { + SkPath path, simple; + addCCWContainer(path); + addCWContents(path); + testSimplifyx(path); +} + +static void testLine13() { + SkPath path, simple; + addCWContainer(path); + addCCWContents(path); + testSimplifyx(path); +} + +static void testLine14() { + SkPath path, simple; + addCCWContainer(path); + addCCWContents(path); + testSimplifyx(path); +} + +static void testLine15() { + SkPath path, simple; + path.addRect(0, 0, 9, 9, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine16() { + SkPath path, simple; + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 4, 9, 9, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine17() { + SkPath path, simple; + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine18() { + SkPath path, simple; + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(12, 4, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine19() { + SkPath path, simple; + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(12, 16, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine20() { + SkPath path, simple; + path.addRect(0, 12, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 12, 9, 9, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine21() { + SkPath path, simple; + path.addRect(0, 12, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 16, 9, 9, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine22() { + SkPath path, simple; + path.addRect(0, 12, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine23() { + SkPath path, simple; + path.addRect(0, 12, 12, 12, (SkPath::Direction) 0); + path.addRect(12, 0, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +} + + + +static void testLine24a() { + SkPath path, simple; + path.moveTo(2,0); + path.lineTo(4,4); + path.lineTo(0,4); + path.close(); + path.moveTo(2,0); + path.lineTo(1,2); + path.lineTo(2,2); + path.close(); + testSimplifyx(path); +} + +static void testLine24() { + SkPath path, simple; + path.addRect(0, 18, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine25() { + SkPath path, simple; + path.addRect(0, 6, 12, 12, (SkPath::Direction) 0); + path.addRect(12, 0, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine26() { + SkPath path, simple; + path.addRect(0, 18, 12, 12, (SkPath::Direction) 0); + path.addRect(0, 12, 9, 9, (SkPath::Direction) 0); + testSimplifyx(path); +} + +static void testLine27() { + SkPath path, simple; + path.addRect(0, 18, 12, 12, (SkPath::Direction) 0); + path.addRect(12, 8, 21, 21, (SkPath::Direction) 0); + testSimplifyx(path); +} + +#define TEST(name) { name, #name } -static void (*tests[])() = { - testLine1, - testLine2, - testLine3, - testLine4, - testLine5, - testLine6, - testLine7, - testLine8, - testLine9 +static struct { + void (*fun)(); + const char* str; +} tests[] = { + TEST(testLine1), + TEST(testLine2), + TEST(testLine3), + TEST(testLine4), + TEST(testLine5), + TEST(testLine6), + TEST(testLine7), + TEST(testLine8), + TEST(testLine9), + TEST(testLine10), + TEST(testLine10a), + TEST(testLine11), + TEST(testLine12), + TEST(testLine13), + TEST(testLine14), + TEST(testLine15), + TEST(testLine16), + TEST(testLine17), + TEST(testLine18), + TEST(testLine19), + TEST(testLine20), + TEST(testLine21), + TEST(testLine22), + TEST(testLine23), + TEST(testLine24a), + TEST(testLine24), + TEST(testLine25), + TEST(testLine26), + TEST(testLine27), }; static const size_t testCount = sizeof(tests) / sizeof(tests[0]); @@ -170,14 +361,14 @@ void SimplifyNew_Test() { } size_t index = 0; if (firstTest) { - while (index < testCount && tests[index] != firstTest) { + while (index < testCount && tests[index].fun != firstTest) { ++index; } } bool firstTestComplete = false; for ( ; index < testCount; ++index) { - SkDebugf("%s [%d]\n", __FUNCTION__, index + 1); - (*tests[index])(); + SkDebugf("%s [%s]\n", __FUNCTION__, tests[index].str); + (*tests[index].fun)(); firstTestComplete = true; } } diff --git a/experimental/Intersection/SimplifyRect4x4_Test.cpp b/experimental/Intersection/SimplifyRect4x4_Test.cpp new file mode 100644 index 0000000000..b83c1cd032 --- /dev/null +++ b/experimental/Intersection/SimplifyRect4x4_Test.cpp @@ -0,0 +1,209 @@ +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ +#include "EdgeWalker_Test.h" +#include "Intersection_Tests.h" +#include "ShapeOps.h" +#include "SkBitmap.h" +#include "SkCanvas.h" +#include <assert.h> +#include <pthread.h> + +// four rects, of four sizes +// for 3 smaller sizes, tall, wide + // top upper mid lower bottom aligned (3 bits, 5 values) + // same with x (3 bits, 5 values) +// not included, square, tall, wide (2 bits) +// cw or ccw (1 bit) + +static void* testSimplify4x4RectsMain(void* data) +{ + char pathStr[1024]; // gdb: set print elements 400 + bzero(pathStr, sizeof(pathStr)); + SkASSERT(data); + State4& state = *(State4*) data; + int aShape = state.a & 0x03; + int aCW = state.a >> 1; + int bShape = state.b & 0x03; + int bCW = state.b >> 1; + int cShape = state.c & 0x03; + int cCW = state.c >> 1; + int dShape = state.d & 0x03; + int dCW = state.d >> 1; + for (int aXAlign = 0 ; aXAlign < 5; ++aXAlign) { + for (int aYAlign = 0 ; aYAlign < 5; ++aYAlign) { + for (int bXAlign = 0 ; bXAlign < 5; ++bXAlign) { + for (int bYAlign = 0 ; bYAlign < 5; ++bYAlign) { + for (int cXAlign = 0 ; cXAlign < 5; ++cXAlign) { + for (int cYAlign = 0 ; cYAlign < 5; ++cYAlign) { + for (int dXAlign = 0 ; dXAlign < 5; ++dXAlign) { + for (int dYAlign = 0 ; dYAlign < 5; ++dYAlign) { + SkPath path, out; + char* str = pathStr; + path.setFillType(SkPath::kWinding_FillType); + int l, t, r, b; + if (aShape) { + switch (aShape) { + case 1: // square + l = 0; r = 60; + t = 0; b = 60; + aXAlign = 5; + aYAlign = 5; + break; + case 2: + l = aXAlign * 12; + r = l + 30; + t = 0; b = 60; + aYAlign = 5; + break; + case 3: + l = 0; r = 60; + t = aYAlign * 12; + b = l + 30; + aXAlign = 5; + break; + } + path.addRect(l, t, r, b, (SkPath::Direction) aCW); + str += sprintf(str, " path.addRect(%d, %d, %d, %d," + " (SkPath::Direction) %d);\n", l, t, r, b, aCW); + } else { + aXAlign = 5; + aYAlign = 5; + } + if (bShape) { + switch (bShape) { + case 1: // square + l = bXAlign * 10; + r = l + 20; + t = bYAlign * 10; + b = l + 20; + break; + case 2: + l = bXAlign * 10; + r = l + 20; + t = 10; b = 40; + bYAlign = 5; + break; + case 3: + l = 10; r = 40; + t = bYAlign * 10; + b = l + 20; + bXAlign = 5; + break; + } + path.addRect(l, t, r, b, (SkPath::Direction) bCW); + str += sprintf(str, " path.addRect(%d, %d, %d, %d," + " (SkPath::Direction) %d);\n", l, t, r, b, bCW); + } else { + bXAlign = 5; + bYAlign = 5; + } + if (cShape) { + switch (cShape) { + case 1: // square + l = cXAlign * 6; + r = l + 12; + t = cYAlign * 6; + b = l + 12; + break; + case 2: + l = cXAlign * 6; + r = l + 12; + t = 20; b = 30; + cYAlign = 5; + break; + case 3: + l = 20; r = 30; + t = cYAlign * 6; + b = l + 20; + cXAlign = 5; + break; + } + path.addRect(l, t, r, b, (SkPath::Direction) cCW); + str += sprintf(str, " path.addRect(%d, %d, %d, %d," + " (SkPath::Direction) %d);\n", l, t, r, b, cCW); + } else { + cXAlign = 5; + cYAlign = 5; + } + if (dShape) { + switch (dShape) { + case 1: // square + l = dXAlign * 4; + r = l + 9; + t = dYAlign * 4; + b = l + 9; + break; + case 2: + l = dXAlign * 6; + r = l + 9; + t = 32; b = 36; + dYAlign = 5; + break; + case 3: + l = 32; r = 36; + t = dYAlign * 6; + b = l + 9; + dXAlign = 5; + break; + } + path.addRect(l, t, r, b, (SkPath::Direction) dCW); + str += sprintf(str, " path.addRect(%d, %d, %d, %d," + " (SkPath::Direction) %d);\n", l, t, r, b, dCW); + } else { + dXAlign = 5; + dYAlign = 5; + } + path.close(); + SkDebugf("%s", pathStr); + if (!testSimplifyx(path, out, state.bitmap, state.canvas)) { + SkDebugf("*/\n{ %s %d, %d, %d, %d, %d, %d, %d, %d," + " %d, %d, %d, %d },\n/*\n", + __FUNCTION__, state.a, state.b, state.c, state.d, + aXAlign, aYAlign, bXAlign, bYAlign, + cXAlign, cYAlign, dXAlign, dYAlign); + } + } + } + } + } + } + } + } + } + return NULL; +} + +const int maxThreads = 1; // gRunTestsInOneThread ? 1 : 24; + +void Simplify4x4RectsThreaded_Test() +{ + State4 threadState[maxThreads]; + int threadIndex = 0; + for (int a = 0; a < 8; ++a) { // outermost + for (int b = a ; b < 8; ++b) { + for (int c = b ; c < 8; ++c) { + for (int d = c; d < 8; ++d) { + State4* statePtr = &threadState[threadIndex]; + statePtr->a = a; + statePtr->b = b; + statePtr->c = c; + statePtr->d = d; + if (maxThreads > 1) { + createThread(statePtr, testSimplify4x4RectsMain); + if (++threadIndex >= maxThreads) { + waitForCompletion(threadState, threadIndex); + } + } else { + testSimplify4x4RectsMain(statePtr); + } + } + } + } + } + waitForCompletion(threadState, threadIndex); +} + diff --git a/experimental/Intersection/edge.xcodeproj/project.pbxproj b/experimental/Intersection/edge.xcodeproj/project.pbxproj deleted file mode 100644 index 6a6ea320b0..0000000000 --- a/experimental/Intersection/edge.xcodeproj/project.pbxproj +++ /dev/null @@ -1,1134 +0,0 @@ -// !$*UTF8*$! -{ - archiveVersion = 1; - classes = { - }; - objectVersion = 45; - objects = { - -/* Begin PBXBuildFile section */ - 1DDD58160DA1D0A300B32029 /* MainMenu.xib in Resources */ = {isa = PBXBuildFile; fileRef = 1DDD58140DA1D0A300B32029 /* MainMenu.xib */; }; - 8D11072B0486CEB800E47090 /* InfoPlist.strings in Resources */ = {isa = PBXBuildFile; fileRef = 089C165CFE840E0CC02AAC07 /* InfoPlist.strings */; }; - FE3201C8144DCC68006DDA67 /* skia_mac.mm in Sources */ = {isa = PBXBuildFile; fileRef = FE3201C6144DCC68006DDA67 /* skia_mac.mm */; }; - FE3201C9144DCC68006DDA67 /* SkOSWindow_Mac.mm in Sources */ = {isa = PBXBuildFile; fileRef = FE3201C7144DCC68006DDA67 /* SkOSWindow_Mac.mm */; }; - FE3DBAFE150E4A680006ADF4 /* junk.htm in Resources */ = {isa = PBXBuildFile; fileRef = FE3DBAFD150E4A680006ADF4 /* junk.htm */; }; - FE7130A114CE0EEB0008E392 /* LineQuadraticIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */; }; - FE7131C414CF5A960008E392 /* LineQuadraticIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */; }; - FE7131EE14D03AED0008E392 /* LineCubicIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7131ED14D03AED0008E392 /* LineCubicIntersection.cpp */; }; - FE71324214D047670008E392 /* QuadraticUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71324114D047670008E392 /* QuadraticUtilities.cpp */; }; - FE71324F14D04D460008E392 /* CubicUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA54114BC838600B35E2C /* CubicUtilities.cpp */; }; - FE71325014D04D480008E392 /* CubeRoot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA53014BB934700B35E2C /* CubeRoot.cpp */; }; - FE71325F14D050D80008E392 /* LineUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71325E14D050D80008E392 /* LineUtilities.cpp */; }; - FE71334214D06B0F0008E392 /* LineCubicIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71334114D06B0F0008E392 /* LineCubicIntersection_Test.cpp */; }; - FE7134F514D1E7C70008E392 /* LineParameterization.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7134F414D1E7C70008E392 /* LineParameterization.cpp */; }; - FE71351314D2E9F50008E392 /* RectUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71351214D2E9F50008E392 /* RectUtilities.cpp */; }; - FE71358614D309E90008E392 /* EdgeWalker.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71358514D309E90008E392 /* EdgeWalker.cpp */; }; - FE7413AE14F689E700056D7B /* libopts.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEF87C2C13E0410900335C58 /* libopts.a */; }; - FE7413D414F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7413D314F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp */; }; - FE7413D814F691C200056D7B /* EdgeWalker_TestUtility.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7413D714F691C200056D7B /* EdgeWalker_TestUtility.cpp */; }; - FE99AE40151B4ED10072AA0D /* tempskinny4.txt in Resources */ = {isa = PBXBuildFile; fileRef = FE99AE3F151B4ED10072AA0D /* tempskinny4.txt */; }; - FE99AE44151B4EE70072AA0D /* xtempskinny4.txt in Resources */ = {isa = PBXBuildFile; fileRef = FE99AE43151B4EE70072AA0D /* xtempskinny4.txt */; }; - FE99AEBE151B64ED0072AA0D /* op.htm in Resources */ = {isa = PBXBuildFile; fileRef = FE99AEBD151B64ED0072AA0D /* op.htm */; }; - FE99AF2B151CC0AA0072AA0D /* ActiveEdge_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE99AF2A151CC0AA0072AA0D /* ActiveEdge_Test.cpp */; }; - FE99B13215209E300072AA0D /* EdgeWalkerPolygon4x4_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE99B13115209E300072AA0D /* EdgeWalkerPolygon4x4_Test.cpp */; }; - FEA5F4E21498000C005052F9 /* libports.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA5F4E11497FFF6005052F9 /* libports.a */; }; - FEA61B0014EF589900B736CB /* libanimator.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7268144DD3EA0059E97B /* libanimator.a */; }; - FEA61B2C14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEA61B2B14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp */; }; - FEA671D013C4A21600FE6FC1 /* AGL.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA671CF13C4A21600FE6FC1 /* AGL.framework */; }; - FEA671D813C4A21600FE6FC1 /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA671D713C4A21600FE6FC1 /* Foundation.framework */; }; - FEA671DA13C4A21600FE6FC1 /* OpenGL.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA671D913C4A21600FE6FC1 /* OpenGL.framework */; }; - FEA6778313C4B3A300FE6FC1 /* EdgeApp.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEA6778213C4B3A300FE6FC1 /* EdgeApp.cpp */; }; - FEC117CC14843B0A0086BF1F /* CubicBezierClip_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC117CB14843B0A0086BF1F /* CubicBezierClip_Test.cpp */; }; - FEC118B8148666670086BF1F /* ConvexHull.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC118B7148666670086BF1F /* ConvexHull.cpp */; }; - FEC118C2148668F30086BF1F /* DataTypes.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC118C1148668F30086BF1F /* DataTypes.cpp */; }; - FEC11911148682200086BF1F /* CubicReduceOrder.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC11910148682200086BF1F /* CubicReduceOrder.cpp */; }; - FEC1191B148683330086BF1F /* Extrema.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1191A148683330086BF1F /* Extrema.cpp */; }; - FEC1195514869DCA0086BF1F /* LineIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1195414869DC90086BF1F /* LineIntersection.cpp */; }; - FEC11E3E148D65780086BF1F /* CubicSubDivide.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC11E3D148D65780086BF1F /* CubicSubDivide.cpp */; }; - FEC12116148EB4EC0086BF1F /* CubicIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC12115148EB4EC0086BF1F /* CubicIntersection.cpp */; }; - FEC1211B148EB5200086BF1F /* CubicBezierClip.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1211A148EB5200086BF1F /* CubicBezierClip.cpp */; }; - FEC1238F149000100086BF1F /* LineParameteters_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1238E149000100086BF1F /* LineParameteters_Test.cpp */; }; - FEC123A6149001A00086BF1F /* SkAntiEdge.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEA670F013C49E2200FE6FC1 /* SkAntiEdge.cpp */; }; - FEC12CE014913E650086BF1F /* LineIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC12CDF14913E650086BF1F /* LineIntersection_Test.cpp */; }; - FECA984014AA044100B35E2C /* CubicParameterization.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECA983F14AA044100B35E2C /* CubicParameterization.cpp */; }; - FECA985114AA046600B35E2C /* QuadraticParameterization.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECA985014AA046600B35E2C /* QuadraticParameterization.cpp */; }; - FECA986214AA2E5900B35E2C /* QuadraticParameterization_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECA986114AA2E5900B35E2C /* QuadraticParameterization_Test.cpp */; }; - FECA987814AA319300B35E2C /* QuadraticSubDivide.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECA987714AA319300B35E2C /* QuadraticSubDivide.cpp */; }; - FECA997C14AB966900B35E2C /* CubicParameterizationCode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECA997B14AB966900B35E2C /* CubicParameterizationCode.cpp */; }; - FECA9A5A14B3B09100B35E2C /* CubicParameterization_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECA9A5914B3B09100B35E2C /* CubicParameterization_Test.cpp */; }; - FECAA52214BB527000B35E2C /* QuadraticIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA52114BB527000B35E2C /* QuadraticIntersection.cpp */; }; - FECAA56D14BCA23200B35E2C /* QuadraticReduceOrder.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA56C14BCA23200B35E2C /* QuadraticReduceOrder.cpp */; }; - FECAA58414BCBD4E00B35E2C /* QuadraticBezierClip.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA58314BCBD4E00B35E2C /* QuadraticBezierClip.cpp */; }; - FECAA67914BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA67814BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp */; }; - FECAA68514BCDE2600B35E2C /* QuadraticIntersection_TestData.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA68414BCDE2600B35E2C /* QuadraticIntersection_TestData.cpp */; }; - FECAA6C714BDCE9B00B35E2C /* QuadraticIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA6C614BDCE9B00B35E2C /* QuadraticIntersection_Test.cpp */; }; - FECAA6E114BDDF2D00B35E2C /* QuadraticReduceOrder_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA6E014BDDF2D00B35E2C /* QuadraticReduceOrder_Test.cpp */; }; - FED53C391483CB9400F6359E /* Inline_Tests.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FED53C381483CB9400F6359E /* Inline_Tests.cpp */; }; - FED865F915056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FED865F815056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp */; }; - FED866D715066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FED866D615066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp */; }; - FEED7245144DD2250059E97B /* SkEventNotifier.mm in Sources */ = {isa = PBXBuildFile; fileRef = FEED723E144DD2250059E97B /* SkEventNotifier.mm */; }; - FEED7292144DD4610059E97B /* libexperimental.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED726E144DD4050059E97B /* libexperimental.a */; }; - FEED7293144DD4620059E97B /* libskgr.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7276144DD4140059E97B /* libskgr.a */; }; - FEED7294144DD4630059E97B /* libgr.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7278144DD4140059E97B /* libgr.a */; }; - FEED7295144DD4650059E97B /* libimages.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED727E144DD4200059E97B /* libimages.a */; }; - FEED7296144DD4660059E97B /* libtess.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7284144DD4300059E97B /* libtess.a */; }; - FEED7297144DD46A0059E97B /* libpdf.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED728A144DD4440059E97B /* libpdf.a */; }; - FEED7298144DD46B0059E97B /* libsvg.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7290144DD44D0059E97B /* libsvg.a */; }; - FEED7299144DD46F0059E97B /* libviews.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7262144DD38D0059E97B /* libviews.a */; }; - FEED72A2144DD4AA0059E97B /* libxml.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED72A1144DD4A80059E97B /* libxml.a */; }; - FEED72AB144DD50A0059E97B /* SampleAppDelegate.mm in Sources */ = {isa = PBXBuildFile; fileRef = FEED723D144DD2250059E97B /* SampleAppDelegate.mm */; }; - FEED72B0144DD5710059E97B /* SampleApp.xib in Resources */ = {isa = PBXBuildFile; fileRef = FEED723C144DD2250059E97B /* SampleApp.xib */; }; - FEED7378144DD5F70059E97B /* ApplicationServices.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA671D113C4A21600FE6FC1 /* ApplicationServices.framework */; }; - FEED7584144DD6360059E97B /* Cocoa.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7583144DD6360059E97B /* Cocoa.framework */; }; - FEED75DD144DD6590059E97B /* QuartzCore.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED75DC144DD6590059E97B /* QuartzCore.framework */; }; - FEED75DF144DD6840059E97B /* libz.dylib in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED75DE144DD6840059E97B /* libz.dylib */; }; - FEED7626144F22E20059E97B /* CubicReduceOrder_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEED7625144F22E20059E97B /* CubicReduceOrder_Test.cpp */; }; - FEED762C144F236C0059E97B /* CubicIntersection_TestData.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEED762B144F236C0059E97B /* CubicIntersection_TestData.cpp */; }; - FEED764C144F29BD0059E97B /* TestUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEED764B144F29BD0059E97B /* TestUtilities.cpp */; }; - FEED768A144F2E7D0059E97B /* CubicIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEED7689144F2E7D0059E97B /* CubicIntersection_Test.cpp */; }; - FEED76C1144F3E7F0059E97B /* ConvexHull_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEED76C0144F3E7F0059E97B /* ConvexHull_Test.cpp */; }; - FEED76EE144F66E90059E97B /* Intersection_Tests.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEED76ED144F66E90059E97B /* Intersection_Tests.cpp */; }; - FEF87C3C13E0413500335C58 /* libcore.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEF87C1A13E040E000335C58 /* libcore.a */; }; - FEF87C3D13E0413A00335C58 /* libeffects.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEF87C2313E040F100335C58 /* libeffects.a */; }; - FEF87C3F13E0414400335C58 /* libutils.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEF87C3B13E0412600335C58 /* libutils.a */; }; -/* End PBXBuildFile section */ - -/* Begin PBXContainerItemProxy section */ - FEA5F4E01497FFF6005052F9 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEA5F4D91497FFF6005052F9 /* ports.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = CDE03B47AA5CD6CE32E53995; - remoteInfo = ports; - }; - FEE70DA6153487F200814606 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C2413E0410900335C58 /* opts.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = ECDC7853EF9A45553165AE98 /* libopts_ssse3.a */; - remoteInfo = opts_ssse3; - }; - FEED7261144DD38D0059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED725D144DD38D0059E97B /* views.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 86302AD97E7E3B2ECED008C3; - remoteInfo = views; - }; - FEED7267144DD3EA0059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED7263144DD3EA0059E97B /* animator.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 3D2E8ABFA0A0734A3D0C9119; - remoteInfo = animator; - }; - FEED726D144DD4050059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED7269144DD4050059E97B /* experimental.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = E18165BCFCD262D9D8DC9100; - remoteInfo = experimental; - }; - FEED7275144DD4140059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED726F144DD4140059E97B /* gpu.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 9756429FF98563EB31F7DB61; - remoteInfo = skgr; - }; - FEED7277144DD4140059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED726F144DD4140059E97B /* gpu.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 4005E78FA1587FEF4005B75F; - remoteInfo = gr; - }; - FEED727D144DD4200059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED7279144DD4200059E97B /* images.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = CDE66C29FD25244B1B30A964; - remoteInfo = images; - }; - FEED7283144DD4300059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED727F144DD4300059E97B /* libtess.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 985181AD94E99169C732B721; - remoteInfo = libtess; - }; - FEED7289144DD4440059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED7285144DD4440059E97B /* pdf.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 46FE697B5062CDA12F1A8C6E; - remoteInfo = pdf; - }; - FEED728F144DD44D0059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED728B144DD44D0059E97B /* svg.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = E11E06188E29426A061DFAA2; - remoteInfo = svg; - }; - FEED72A0144DD4A80059E97B /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEED729C144DD4A80059E97B /* xml.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = B9B83862B1FE3A5230CB0ED6; - remoteInfo = xml; - }; - FEF87C1913E040E000335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C1213E040E000335C58 /* core.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 8B1FC9FF853D5C32F4771091; - remoteInfo = core; - }; - FEF87C2213E040F100335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C1B13E040F100335C58 /* effects.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = BB64F2E443C9412F1328140F; - remoteInfo = effects; - }; - FEF87C2B13E0410900335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C2413E0410900335C58 /* opts.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = 6FDD5BFF3B676557344FAA2B; - remoteInfo = opts; - }; - FEF87C3A13E0412600335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C3313E0412600335C58 /* utils.xcodeproj */; - proxyType = 2; - remoteGlobalIDString = C196E82C2F3304B37526F8F3; - remoteInfo = utils; - }; - FEF87C4013E0414D00335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C1213E040E000335C58 /* core.xcodeproj */; - proxyType = 1; - remoteGlobalIDString = 5A9991BB6607533745115226; - remoteInfo = core; - }; - FEF87C4213E0415100335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C1B13E040F100335C58 /* effects.xcodeproj */; - proxyType = 1; - remoteGlobalIDString = F0EB02F40D8DAD92937C53E1; - remoteInfo = effects; - }; - FEF87C4413E0415500335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C2413E0410900335C58 /* opts.xcodeproj */; - proxyType = 1; - remoteGlobalIDString = 801760729BE30DF59BEA25B9; - remoteInfo = opts; - }; - FEF87C4613E0415900335C58 /* PBXContainerItemProxy */ = { - isa = PBXContainerItemProxy; - containerPortal = FEF87C3313E0412600335C58 /* utils.xcodeproj */; - proxyType = 1; - remoteGlobalIDString = 7364408688F1A6434987562A; - remoteInfo = utils; - }; -/* End PBXContainerItemProxy section */ - -/* Begin PBXFileReference section */ - 089C165DFE840E0CC02AAC07 /* English */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.plist.strings; name = English; path = English.lproj/InfoPlist.strings; sourceTree = "<group>"; }; - 1DDD58150DA1D0A300B32029 /* English */ = {isa = PBXFileReference; lastKnownFileType = file.xib; name = English; path = English.lproj/MainMenu.xib; sourceTree = "<group>"; }; - 256AC3F00F4B6AF500CF3369 /* edge_Prefix.pch */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = edge_Prefix.pch; sourceTree = "<group>"; }; - 8D1107310486CEB800E47090 /* edge-Info.plist */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.plist.xml; path = "edge-Info.plist"; sourceTree = "<group>"; }; - 8D1107320486CEB800E47090 /* edge.app */ = {isa = PBXFileReference; explicitFileType = wrapper.application; includeInIndex = 0; path = edge.app; sourceTree = BUILT_PRODUCTS_DIR; }; - FE3201C6144DCC68006DDA67 /* skia_mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = skia_mac.mm; path = ../../src/utils/mac/skia_mac.mm; sourceTree = SOURCE_ROOT; }; - FE3201C7144DCC68006DDA67 /* SkOSWindow_Mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkOSWindow_Mac.mm; path = ../../src/utils/mac/SkOSWindow_Mac.mm; sourceTree = SOURCE_ROOT; }; - FE3DB8C9150A48320006ADF4 /* junk.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = junk.txt; sourceTree = "<group>"; }; - FE3DBAFD150E4A680006ADF4 /* junk.htm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; name = junk.htm; path = ../../../../../junk.htm; sourceTree = SOURCE_ROOT; }; - FE4FE7411492417500A12A34 /* IntersectionUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = IntersectionUtilities.cpp; sourceTree = "<group>"; }; - FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection.cpp; sourceTree = "<group>"; }; - FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection_Test.cpp; sourceTree = "<group>"; }; - FE7131ED14D03AED0008E392 /* LineCubicIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineCubicIntersection.cpp; sourceTree = "<group>"; }; - FE71324114D047670008E392 /* QuadraticUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticUtilities.cpp; sourceTree = "<group>"; }; - FE71325114D04D7A0008E392 /* CubicUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CubicUtilities.h; sourceTree = "<group>"; }; - FE71325D14D050D80008E392 /* LineUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LineUtilities.h; sourceTree = "<group>"; }; - FE71325E14D050D80008E392 /* LineUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineUtilities.cpp; sourceTree = "<group>"; }; - FE71334114D06B0F0008E392 /* LineCubicIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineCubicIntersection_Test.cpp; sourceTree = "<group>"; }; - FE7134DF14D1E5680008E392 /* Parameterization_Test.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Parameterization_Test.h; sourceTree = "<group>"; }; - FE7134F414D1E7C70008E392 /* LineParameterization.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineParameterization.cpp; sourceTree = "<group>"; }; - FE71351214D2E9F50008E392 /* RectUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RectUtilities.cpp; sourceTree = "<group>"; }; - FE71358514D309E90008E392 /* EdgeWalker.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalker.cpp; sourceTree = "<group>"; }; - FE713C6114D9879B0008E392 /* TSearch.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TSearch.h; sourceTree = "<group>"; }; - FE7413D314F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerPolygons_Test.cpp; sourceTree = "<group>"; }; - FE7413D714F691C200056D7B /* EdgeWalker_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalker_TestUtility.cpp; sourceTree = "<group>"; }; - FE7413DB14F6926D00056D7B /* EdgeWalker_Test.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = EdgeWalker_Test.h; sourceTree = "<group>"; }; - FE99AE3F151B4ED10072AA0D /* tempskinny4.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = tempskinny4.txt; sourceTree = "<group>"; }; - FE99AE43151B4EE70072AA0D /* xtempskinny4.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = xtempskinny4.txt; sourceTree = "<group>"; }; - FE99AEBD151B64ED0072AA0D /* op.htm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = op.htm; sourceTree = "<group>"; }; - FE99AF2A151CC0AA0072AA0D /* ActiveEdge_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ActiveEdge_Test.cpp; sourceTree = "<group>"; }; - FE99B13115209E300072AA0D /* EdgeWalkerPolygon4x4_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerPolygon4x4_Test.cpp; sourceTree = "<group>"; }; - FEA5F4D91497FFF6005052F9 /* ports.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = ports.xcodeproj; path = ../../out/gyp/ports.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEA61B2B14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerRectangles_Test.cpp; sourceTree = "<group>"; }; - FEA670F013C49E2200FE6FC1 /* SkAntiEdge.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SkAntiEdge.cpp; sourceTree = "<group>"; }; - FEA670F113C49E2200FE6FC1 /* SkAntiEdge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SkAntiEdge.h; sourceTree = "<group>"; }; - FEA6710713C4A13900FE6FC1 /* gyp */ = {isa = PBXFileReference; lastKnownFileType = folder; name = gyp; path = ../../out/gyp; sourceTree = SOURCE_ROOT; }; - FEA671CF13C4A21600FE6FC1 /* AGL.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = AGL.framework; path = System/Library/Frameworks/AGL.framework; sourceTree = SDKROOT; }; - FEA671D113C4A21600FE6FC1 /* ApplicationServices.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = ApplicationServices.framework; path = System/Library/Frameworks/ApplicationServices.framework; sourceTree = SDKROOT; }; - FEA671D713C4A21600FE6FC1 /* Foundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Foundation.framework; path = System/Library/Frameworks/Foundation.framework; sourceTree = SDKROOT; }; - FEA671D913C4A21600FE6FC1 /* OpenGL.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = OpenGL.framework; path = System/Library/Frameworks/OpenGL.framework; sourceTree = SDKROOT; }; - FEA6778213C4B3A300FE6FC1 /* EdgeApp.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeApp.cpp; sourceTree = "<group>"; }; - FEC117CB14843B0A0086BF1F /* CubicBezierClip_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicBezierClip_Test.cpp; sourceTree = "<group>"; }; - FEC118B7148666670086BF1F /* ConvexHull.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ConvexHull.cpp; sourceTree = "<group>"; }; - FEC118C1148668F30086BF1F /* DataTypes.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DataTypes.cpp; sourceTree = "<group>"; }; - FEC11910148682200086BF1F /* CubicReduceOrder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicReduceOrder.cpp; sourceTree = "<group>"; }; - FEC1191A148683330086BF1F /* Extrema.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Extrema.cpp; sourceTree = "<group>"; }; - FEC1191E148683850086BF1F /* Extrema.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Extrema.h; sourceTree = "<group>"; }; - FEC1195314869DC90086BF1F /* LineIntersection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LineIntersection.h; sourceTree = "<group>"; }; - FEC1195414869DC90086BF1F /* LineIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineIntersection.cpp; sourceTree = "<group>"; }; - FEC11A821487D23E0086BF1F /* Intersections.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Intersections.h; sourceTree = "<group>"; }; - FEC11A851487D2650086BF1F /* LineParameters.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LineParameters.h; sourceTree = "<group>"; }; - FEC11A881487D2F50086BF1F /* IntersectionUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IntersectionUtilities.h; sourceTree = "<group>"; }; - FEC11E3D148D65780086BF1F /* CubicSubDivide.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicSubDivide.cpp; sourceTree = "<group>"; }; - FEC12115148EB4EC0086BF1F /* CubicIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection.cpp; sourceTree = "<group>"; }; - FEC1211A148EB5200086BF1F /* CubicBezierClip.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicBezierClip.cpp; sourceTree = "<group>"; }; - FEC1238E149000100086BF1F /* LineParameteters_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineParameteters_Test.cpp; sourceTree = "<group>"; }; - FEC12CDF14913E650086BF1F /* LineIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineIntersection_Test.cpp; sourceTree = "<group>"; }; - FECA983F14AA044100B35E2C /* CubicParameterization.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicParameterization.cpp; sourceTree = "<group>"; }; - FECA985014AA046600B35E2C /* QuadraticParameterization.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticParameterization.cpp; sourceTree = "<group>"; }; - FECA986114AA2E5900B35E2C /* QuadraticParameterization_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticParameterization_Test.cpp; sourceTree = "<group>"; }; - FECA987714AA319300B35E2C /* QuadraticSubDivide.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticSubDivide.cpp; sourceTree = "<group>"; }; - FECA997B14AB966900B35E2C /* CubicParameterizationCode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicParameterizationCode.cpp; sourceTree = "<group>"; }; - FECA9A5914B3B09100B35E2C /* CubicParameterization_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicParameterization_Test.cpp; sourceTree = "<group>"; }; - FECAA52114BB527000B35E2C /* QuadraticIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticIntersection.cpp; sourceTree = "<group>"; }; - FECAA52B14BB6B0900B35E2C /* QuadraticUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = QuadraticUtilities.h; sourceTree = "<group>"; }; - FECAA53014BB934700B35E2C /* CubeRoot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubeRoot.cpp; sourceTree = "<group>"; }; - FECAA54114BC838600B35E2C /* CubicUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicUtilities.cpp; sourceTree = "<group>"; }; - FECAA56C14BCA23200B35E2C /* QuadraticReduceOrder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticReduceOrder.cpp; sourceTree = "<group>"; }; - FECAA58314BCBD4E00B35E2C /* QuadraticBezierClip.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticBezierClip.cpp; sourceTree = "<group>"; }; - FECAA67814BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticBezierClip_Test.cpp; sourceTree = "<group>"; }; - FECAA68314BCDE2600B35E2C /* QuadraticIntersection_TestData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = QuadraticIntersection_TestData.h; sourceTree = "<group>"; }; - FECAA68414BCDE2600B35E2C /* QuadraticIntersection_TestData.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticIntersection_TestData.cpp; sourceTree = "<group>"; }; - FECAA6C614BDCE9B00B35E2C /* QuadraticIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticIntersection_Test.cpp; sourceTree = "<group>"; }; - FECAA6E014BDDF2D00B35E2C /* QuadraticReduceOrder_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticReduceOrder_Test.cpp; sourceTree = "<group>"; }; - FECAAB7F14BDFAFD00B35E2C /* CubicParameterization_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicParameterization_TestUtility.cpp; sourceTree = "<group>"; }; - FECAACA614BE1C6100B35E2C /* QuadraticParameterization_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticParameterization_TestUtility.cpp; sourceTree = "<group>"; }; - FED53C381483CB9400F6359E /* Inline_Tests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Inline_Tests.cpp; sourceTree = "<group>"; }; - FED865F815056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerQuadralaterals_Test.cpp; sourceTree = "<group>"; }; - FED866D615066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerPolygons_Mismatches.cpp; sourceTree = "<group>"; }; - FEED723C144DD2250059E97B /* SampleApp.xib */ = {isa = PBXFileReference; lastKnownFileType = file.xib; name = SampleApp.xib; path = ../../src/utils/mac/SampleApp.xib; sourceTree = SOURCE_ROOT; }; - FEED723D144DD2250059E97B /* SampleAppDelegate.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SampleAppDelegate.mm; path = ../../src/utils/mac/SampleAppDelegate.mm; sourceTree = SOURCE_ROOT; }; - FEED723E144DD2250059E97B /* SkEventNotifier.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkEventNotifier.mm; path = ../../src/utils/mac/SkEventNotifier.mm; sourceTree = SOURCE_ROOT; }; - FEED723F144DD2250059E97B /* SkNSView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkNSView.mm; path = ../../src/utils/mac/SkNSView.mm; sourceTree = SOURCE_ROOT; }; - FEED7240144DD2250059E97B /* SkOptionsTableView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkOptionsTableView.mm; path = ../../src/utils/mac/SkOptionsTableView.mm; sourceTree = SOURCE_ROOT; }; - FEED7241144DD2250059E97B /* SkSampleNSView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkSampleNSView.mm; path = ../../src/utils/mac/SkSampleNSView.mm; sourceTree = SOURCE_ROOT; }; - FEED7242144DD2250059E97B /* SkTextFieldCell.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = SkTextFieldCell.m; path = ../../src/utils/mac/SkTextFieldCell.m; sourceTree = SOURCE_ROOT; }; - FEED725D144DD38D0059E97B /* views.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = views.xcodeproj; path = ../../out/gyp/views.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED7263144DD3EA0059E97B /* animator.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = animator.xcodeproj; path = ../../out/gyp/animator.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED7269144DD4050059E97B /* experimental.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = experimental.xcodeproj; path = ../../out/gyp/experimental.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED726F144DD4140059E97B /* gpu.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = gpu.xcodeproj; path = ../../out/gyp/gpu.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED7279144DD4200059E97B /* images.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = images.xcodeproj; path = ../../out/gyp/images.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED727F144DD4300059E97B /* libtess.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = libtess.xcodeproj; path = ../../out/gyp/libtess.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED7285144DD4440059E97B /* pdf.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = pdf.xcodeproj; path = ../../out/gyp/pdf.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED728B144DD44D0059E97B /* svg.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = svg.xcodeproj; path = ../../out/gyp/svg.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED729C144DD4A80059E97B /* xml.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = xml.xcodeproj; path = ../../out/gyp/xml.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEED7583144DD6360059E97B /* Cocoa.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Cocoa.framework; path = /System/Library/Frameworks/Cocoa.framework; sourceTree = "<absolute>"; }; - FEED75DC144DD6590059E97B /* QuartzCore.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = QuartzCore.framework; path = /System/Library/Frameworks/QuartzCore.framework; sourceTree = "<absolute>"; }; - FEED75DE144DD6840059E97B /* libz.dylib */ = {isa = PBXFileReference; lastKnownFileType = "compiled.mach-o.dylib"; name = libz.dylib; path = /usr/lib/libz.dylib; sourceTree = "<absolute>"; }; - FEED7625144F22E20059E97B /* CubicReduceOrder_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicReduceOrder_Test.cpp; sourceTree = "<group>"; }; - FEED762B144F236C0059E97B /* CubicIntersection_TestData.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection_TestData.cpp; sourceTree = "<group>"; }; - FEED762F144F23CA0059E97B /* CurveIntersection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CurveIntersection.h; sourceTree = "<group>"; }; - FEED7632144F25150059E97B /* CubicIntersection_TestData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CubicIntersection_TestData.h; sourceTree = "<group>"; }; - FEED764B144F29BD0059E97B /* TestUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TestUtilities.cpp; sourceTree = "<group>"; }; - FEED764F144F2A160059E97B /* DataTypes.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DataTypes.h; sourceTree = "<group>"; }; - FEED7673144F2D770059E97B /* TestUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TestUtilities.h; sourceTree = "<group>"; }; - FEED7680144F2E480059E97B /* Intersection_Tests.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Intersection_Tests.h; sourceTree = "<group>"; }; - FEED7689144F2E7D0059E97B /* CubicIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection_Test.cpp; sourceTree = "<group>"; }; - FEED76C0144F3E7F0059E97B /* ConvexHull_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ConvexHull_Test.cpp; sourceTree = "<group>"; }; - FEED76ED144F66E90059E97B /* Intersection_Tests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Intersection_Tests.cpp; sourceTree = "<group>"; }; - FEF87C1213E040E000335C58 /* core.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = core.xcodeproj; path = ../../out/gyp/core.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEF87C1B13E040F100335C58 /* effects.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = effects.xcodeproj; path = ../../out/gyp/effects.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEF87C2413E0410900335C58 /* opts.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = opts.xcodeproj; path = ../../out/gyp/opts.xcodeproj; sourceTree = SOURCE_ROOT; }; - FEF87C3313E0412600335C58 /* utils.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = utils.xcodeproj; path = ../../out/gyp/utils.xcodeproj; sourceTree = SOURCE_ROOT; }; -/* End PBXFileReference section */ - -/* Begin PBXFrameworksBuildPhase section */ - 8D11072E0486CEB800E47090 /* Frameworks */ = { - isa = PBXFrameworksBuildPhase; - buildActionMask = 2147483647; - files = ( - FEF87C3C13E0413500335C58 /* libcore.a in Frameworks */, - FEF87C3D13E0413A00335C58 /* libeffects.a in Frameworks */, - FEF87C3F13E0414400335C58 /* libutils.a in Frameworks */, - FEA671D813C4A21600FE6FC1 /* Foundation.framework in Frameworks */, - FEA671D013C4A21600FE6FC1 /* AGL.framework in Frameworks */, - FEA671DA13C4A21600FE6FC1 /* OpenGL.framework in Frameworks */, - FEED7292144DD4610059E97B /* libexperimental.a in Frameworks */, - FEED7293144DD4620059E97B /* libskgr.a in Frameworks */, - FEED7294144DD4630059E97B /* libgr.a in Frameworks */, - FEED7295144DD4650059E97B /* libimages.a in Frameworks */, - FEED7296144DD4660059E97B /* libtess.a in Frameworks */, - FEED7297144DD46A0059E97B /* libpdf.a in Frameworks */, - FEED7298144DD46B0059E97B /* libsvg.a in Frameworks */, - FEED7299144DD46F0059E97B /* libviews.a in Frameworks */, - FEED72A2144DD4AA0059E97B /* libxml.a in Frameworks */, - FEED7378144DD5F70059E97B /* ApplicationServices.framework in Frameworks */, - FEED7584144DD6360059E97B /* Cocoa.framework in Frameworks */, - FEED75DD144DD6590059E97B /* QuartzCore.framework in Frameworks */, - FEED75DF144DD6840059E97B /* libz.dylib in Frameworks */, - FEA5F4E21498000C005052F9 /* libports.a in Frameworks */, - FEA61B0014EF589900B736CB /* libanimator.a in Frameworks */, - FE7413AE14F689E700056D7B /* libopts.a in Frameworks */, - ); - runOnlyForDeploymentPostprocessing = 0; - }; -/* End PBXFrameworksBuildPhase section */ - -/* Begin PBXGroup section */ - 19C28FACFE9D520D11CA2CBB /* Products */ = { - isa = PBXGroup; - children = ( - 8D1107320486CEB800E47090 /* edge.app */, - ); - name = Products; - sourceTree = "<group>"; - }; - 29B97314FDCFA39411CA2CEA /* edge */ = { - isa = PBXGroup; - children = ( - FE99AEBD151B64ED0072AA0D /* op.htm */, - FEA670EF13C49D7600FE6FC1 /* views */, - FEC123A7149001B20086BF1F /* AntiEdge */, - 29B97315FDCFA39411CA2CEA /* Intersection */, - FE71354F14D305FD0008E392 /* ShapeOps */, - FEC123A5149001540086BF1F /* Tests */, - 29B97317FDCFA39411CA2CEA /* Resources */, - 29B97323FDCFA39411CA2CEA /* Frameworks */, - 19C28FACFE9D520D11CA2CBB /* Products */, - FEED7263144DD3EA0059E97B /* animator.xcodeproj */, - FEF87C1213E040E000335C58 /* core.xcodeproj */, - FEF87C1B13E040F100335C58 /* effects.xcodeproj */, - FEED7269144DD4050059E97B /* experimental.xcodeproj */, - FEED726F144DD4140059E97B /* gpu.xcodeproj */, - FEED7279144DD4200059E97B /* images.xcodeproj */, - FEED727F144DD4300059E97B /* libtess.xcodeproj */, - FEF87C2413E0410900335C58 /* opts.xcodeproj */, - FEA5F4D91497FFF6005052F9 /* ports.xcodeproj */, - FEED7285144DD4440059E97B /* pdf.xcodeproj */, - FEED728B144DD44D0059E97B /* svg.xcodeproj */, - FEF87C3313E0412600335C58 /* utils.xcodeproj */, - FEED725D144DD38D0059E97B /* views.xcodeproj */, - FEED729C144DD4A80059E97B /* xml.xcodeproj */, - FEA6710713C4A13900FE6FC1 /* gyp */, - ); - name = edge; - sourceTree = "<group>"; - }; - 29B97315FDCFA39411CA2CEA /* Intersection */ = { - isa = PBXGroup; - children = ( - FEC118B7148666670086BF1F /* ConvexHull.cpp */, - FECAA53014BB934700B35E2C /* CubeRoot.cpp */, - FEC1211A148EB5200086BF1F /* CubicBezierClip.cpp */, - FEC12115148EB4EC0086BF1F /* CubicIntersection.cpp */, - FECA983F14AA044100B35E2C /* CubicParameterization.cpp */, - FECA997B14AB966900B35E2C /* CubicParameterizationCode.cpp */, - FEC11910148682200086BF1F /* CubicReduceOrder.cpp */, - FECAA54114BC838600B35E2C /* CubicUtilities.cpp */, - FEC11E3D148D65780086BF1F /* CubicSubDivide.cpp */, - FE71325114D04D7A0008E392 /* CubicUtilities.h */, - FEED762F144F23CA0059E97B /* CurveIntersection.h */, - FEED764F144F2A160059E97B /* DataTypes.h */, - FEC118C1148668F30086BF1F /* DataTypes.cpp */, - FEC1191E148683850086BF1F /* Extrema.h */, - FEC1191A148683330086BF1F /* Extrema.cpp */, - FEC11A821487D23E0086BF1F /* Intersections.h */, - FEC11A881487D2F50086BF1F /* IntersectionUtilities.h */, - FE4FE7411492417500A12A34 /* IntersectionUtilities.cpp */, - FEC1195314869DC90086BF1F /* LineIntersection.h */, - FEC1195414869DC90086BF1F /* LineIntersection.cpp */, - FE7134F414D1E7C70008E392 /* LineParameterization.cpp */, - FEC11A851487D2650086BF1F /* LineParameters.h */, - FE71325D14D050D80008E392 /* LineUtilities.h */, - FE71325E14D050D80008E392 /* LineUtilities.cpp */, - FE7131ED14D03AED0008E392 /* LineCubicIntersection.cpp */, - FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */, - FECAA58314BCBD4E00B35E2C /* QuadraticBezierClip.cpp */, - FECAA52114BB527000B35E2C /* QuadraticIntersection.cpp */, - FECA985014AA046600B35E2C /* QuadraticParameterization.cpp */, - FECAA56C14BCA23200B35E2C /* QuadraticReduceOrder.cpp */, - FECA987714AA319300B35E2C /* QuadraticSubDivide.cpp */, - FECAA52B14BB6B0900B35E2C /* QuadraticUtilities.h */, - FE71324114D047670008E392 /* QuadraticUtilities.cpp */, - FE71351214D2E9F50008E392 /* RectUtilities.cpp */, - ); - name = Intersection; - sourceTree = "<group>"; - }; - 29B97317FDCFA39411CA2CEA /* Resources */ = { - isa = PBXGroup; - children = ( - 8D1107310486CEB800E47090 /* edge-Info.plist */, - 089C165CFE840E0CC02AAC07 /* InfoPlist.strings */, - 1DDD58140DA1D0A300B32029 /* MainMenu.xib */, - ); - name = Resources; - sourceTree = "<group>"; - }; - 29B97323FDCFA39411CA2CEA /* Frameworks */ = { - isa = PBXGroup; - children = ( - FEA671CF13C4A21600FE6FC1 /* AGL.framework */, - FEA671D113C4A21600FE6FC1 /* ApplicationServices.framework */, - FEED7583144DD6360059E97B /* Cocoa.framework */, - FEA671D713C4A21600FE6FC1 /* Foundation.framework */, - FEA671D913C4A21600FE6FC1 /* OpenGL.framework */, - FEED75DC144DD6590059E97B /* QuartzCore.framework */, - FEED75DE144DD6840059E97B /* libz.dylib */, - ); - name = Frameworks; - sourceTree = "<group>"; - }; - FE71354F14D305FD0008E392 /* ShapeOps */ = { - isa = PBXGroup; - children = ( - FE99AE43151B4EE70072AA0D /* xtempskinny4.txt */, - FE99AE3F151B4ED10072AA0D /* tempskinny4.txt */, - FE3DBAFD150E4A680006ADF4 /* junk.htm */, - FE3DB8C9150A48320006ADF4 /* junk.txt */, - FE71358514D309E90008E392 /* EdgeWalker.cpp */, - FE713C6114D9879B0008E392 /* TSearch.h */, - ); - name = ShapeOps; - sourceTree = "<group>"; - }; - FEA5F4DA1497FFF6005052F9 /* Products */ = { - isa = PBXGroup; - children = ( - FEA5F4E11497FFF6005052F9 /* libports.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEA670EF13C49D7600FE6FC1 /* views */ = { - isa = PBXGroup; - children = ( - FEED723C144DD2250059E97B /* SampleApp.xib */, - FEED723D144DD2250059E97B /* SampleAppDelegate.mm */, - FEED723E144DD2250059E97B /* SkEventNotifier.mm */, - FEED723F144DD2250059E97B /* SkNSView.mm */, - FEED7240144DD2250059E97B /* SkOptionsTableView.mm */, - FEED7241144DD2250059E97B /* SkSampleNSView.mm */, - FEED7242144DD2250059E97B /* SkTextFieldCell.m */, - FE3201C7144DCC68006DDA67 /* SkOSWindow_Mac.mm */, - FE3201C6144DCC68006DDA67 /* skia_mac.mm */, - ); - name = views; - sourceTree = "<group>"; - }; - FEC123A5149001540086BF1F /* Tests */ = { - isa = PBXGroup; - children = ( - FE99AF2A151CC0AA0072AA0D /* ActiveEdge_Test.cpp */, - FEED76C0144F3E7F0059E97B /* ConvexHull_Test.cpp */, - FEC117CB14843B0A0086BF1F /* CubicBezierClip_Test.cpp */, - FEED7689144F2E7D0059E97B /* CubicIntersection_Test.cpp */, - FEED7632144F25150059E97B /* CubicIntersection_TestData.h */, - FEED762B144F236C0059E97B /* CubicIntersection_TestData.cpp */, - FECA9A5914B3B09100B35E2C /* CubicParameterization_Test.cpp */, - FECAAB7F14BDFAFD00B35E2C /* CubicParameterization_TestUtility.cpp */, - FEED7625144F22E20059E97B /* CubicReduceOrder_Test.cpp */, - FE7413DB14F6926D00056D7B /* EdgeWalker_Test.h */, - FE7413D714F691C200056D7B /* EdgeWalker_TestUtility.cpp */, - FE7413D314F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp */, - FE99B13115209E300072AA0D /* EdgeWalkerPolygon4x4_Test.cpp */, - FED866D615066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp */, - FED865F815056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp */, - FEA61B2B14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp */, - FED53C381483CB9400F6359E /* Inline_Tests.cpp */, - FEED7680144F2E480059E97B /* Intersection_Tests.h */, - FEED76ED144F66E90059E97B /* Intersection_Tests.cpp */, - FE71334114D06B0F0008E392 /* LineCubicIntersection_Test.cpp */, - FEC12CDF14913E650086BF1F /* LineIntersection_Test.cpp */, - FEC1238E149000100086BF1F /* LineParameteters_Test.cpp */, - FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */, - FE7134DF14D1E5680008E392 /* Parameterization_Test.h */, - FECAA67814BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp */, - FECAA6C614BDCE9B00B35E2C /* QuadraticIntersection_Test.cpp */, - FECAA68314BCDE2600B35E2C /* QuadraticIntersection_TestData.h */, - FECAA68414BCDE2600B35E2C /* QuadraticIntersection_TestData.cpp */, - FECA986114AA2E5900B35E2C /* QuadraticParameterization_Test.cpp */, - FECAACA614BE1C6100B35E2C /* QuadraticParameterization_TestUtility.cpp */, - FECAA6E014BDDF2D00B35E2C /* QuadraticReduceOrder_Test.cpp */, - FEED7673144F2D770059E97B /* TestUtilities.h */, - FEED764B144F29BD0059E97B /* TestUtilities.cpp */, - ); - name = Tests; - sourceTree = "<group>"; - }; - FEC123A7149001B20086BF1F /* AntiEdge */ = { - isa = PBXGroup; - children = ( - FEA670F113C49E2200FE6FC1 /* SkAntiEdge.h */, - FEA670F013C49E2200FE6FC1 /* SkAntiEdge.cpp */, - 256AC3F00F4B6AF500CF3369 /* edge_Prefix.pch */, - FEA6778213C4B3A300FE6FC1 /* EdgeApp.cpp */, - ); - name = AntiEdge; - sourceTree = "<group>"; - }; - FEED725E144DD38D0059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED7262144DD38D0059E97B /* libviews.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED7264144DD3EA0059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED7268144DD3EA0059E97B /* libanimator.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED726A144DD4050059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED726E144DD4050059E97B /* libexperimental.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED7270144DD4140059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED7276144DD4140059E97B /* libskgr.a */, - FEED7278144DD4140059E97B /* libgr.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED727A144DD4200059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED727E144DD4200059E97B /* libimages.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED7280144DD4300059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED7284144DD4300059E97B /* libtess.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED7286144DD4440059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED728A144DD4440059E97B /* libpdf.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED728C144DD44D0059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED7290144DD44D0059E97B /* libsvg.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEED729D144DD4A80059E97B /* Products */ = { - isa = PBXGroup; - children = ( - FEED72A1144DD4A80059E97B /* libxml.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEF87C1313E040E000335C58 /* Products */ = { - isa = PBXGroup; - children = ( - FEF87C1A13E040E000335C58 /* libcore.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEF87C1C13E040F100335C58 /* Products */ = { - isa = PBXGroup; - children = ( - FEF87C2313E040F100335C58 /* libeffects.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEF87C2513E0410900335C58 /* Products */ = { - isa = PBXGroup; - children = ( - FEF87C2C13E0410900335C58 /* libopts.a */, - FEE70DA7153487F200814606 /* libopts_ssse3.a */, - ); - name = Products; - sourceTree = "<group>"; - }; - FEF87C3413E0412600335C58 /* Products */ = { - isa = PBXGroup; - children = ( - FEF87C3B13E0412600335C58 /* libutils.a */, - ); - name = Products; - sourceTree = "<group>"; - }; -/* End PBXGroup section */ - -/* Begin PBXNativeTarget section */ - 8D1107260486CEB800E47090 /* edge */ = { - isa = PBXNativeTarget; - buildConfigurationList = C01FCF4A08A954540054247B /* Build configuration list for PBXNativeTarget "edge" */; - buildPhases = ( - 8D1107290486CEB800E47090 /* Resources */, - 8D11072C0486CEB800E47090 /* Sources */, - 8D11072E0486CEB800E47090 /* Frameworks */, - ); - buildRules = ( - ); - dependencies = ( - FEF87C4113E0414D00335C58 /* PBXTargetDependency */, - FEF87C4313E0415100335C58 /* PBXTargetDependency */, - FEF87C4513E0415500335C58 /* PBXTargetDependency */, - FEF87C4713E0415900335C58 /* PBXTargetDependency */, - ); - name = edge; - productInstallPath = "$(HOME)/Applications"; - productName = edge; - productReference = 8D1107320486CEB800E47090 /* edge.app */; - productType = "com.apple.product-type.application"; - }; -/* End PBXNativeTarget section */ - -/* Begin PBXProject section */ - 29B97313FDCFA39411CA2CEA /* Project object */ = { - isa = PBXProject; - buildConfigurationList = C01FCF4E08A954540054247B /* Build configuration list for PBXProject "edge" */; - compatibilityVersion = "Xcode 3.1"; - developmentRegion = English; - hasScannedForEncodings = 1; - knownRegions = ( - English, - Japanese, - French, - German, - ); - mainGroup = 29B97314FDCFA39411CA2CEA /* edge */; - projectDirPath = ""; - projectReferences = ( - { - ProductGroup = FEED7264144DD3EA0059E97B /* Products */; - ProjectRef = FEED7263144DD3EA0059E97B /* animator.xcodeproj */; - }, - { - ProductGroup = FEF87C1313E040E000335C58 /* Products */; - ProjectRef = FEF87C1213E040E000335C58 /* core.xcodeproj */; - }, - { - ProductGroup = FEF87C1C13E040F100335C58 /* Products */; - ProjectRef = FEF87C1B13E040F100335C58 /* effects.xcodeproj */; - }, - { - ProductGroup = FEED726A144DD4050059E97B /* Products */; - ProjectRef = FEED7269144DD4050059E97B /* experimental.xcodeproj */; - }, - { - ProductGroup = FEED7270144DD4140059E97B /* Products */; - ProjectRef = FEED726F144DD4140059E97B /* gpu.xcodeproj */; - }, - { - ProductGroup = FEED727A144DD4200059E97B /* Products */; - ProjectRef = FEED7279144DD4200059E97B /* images.xcodeproj */; - }, - { - ProductGroup = FEED7280144DD4300059E97B /* Products */; - ProjectRef = FEED727F144DD4300059E97B /* libtess.xcodeproj */; - }, - { - ProductGroup = FEF87C2513E0410900335C58 /* Products */; - ProjectRef = FEF87C2413E0410900335C58 /* opts.xcodeproj */; - }, - { - ProductGroup = FEED7286144DD4440059E97B /* Products */; - ProjectRef = FEED7285144DD4440059E97B /* pdf.xcodeproj */; - }, - { - ProductGroup = FEA5F4DA1497FFF6005052F9 /* Products */; - ProjectRef = FEA5F4D91497FFF6005052F9 /* ports.xcodeproj */; - }, - { - ProductGroup = FEED728C144DD44D0059E97B /* Products */; - ProjectRef = FEED728B144DD44D0059E97B /* svg.xcodeproj */; - }, - { - ProductGroup = FEF87C3413E0412600335C58 /* Products */; - ProjectRef = FEF87C3313E0412600335C58 /* utils.xcodeproj */; - }, - { - ProductGroup = FEED725E144DD38D0059E97B /* Products */; - ProjectRef = FEED725D144DD38D0059E97B /* views.xcodeproj */; - }, - { - ProductGroup = FEED729D144DD4A80059E97B /* Products */; - ProjectRef = FEED729C144DD4A80059E97B /* xml.xcodeproj */; - }, - ); - projectRoot = ""; - targets = ( - 8D1107260486CEB800E47090 /* edge */, - ); - }; -/* End PBXProject section */ - -/* Begin PBXReferenceProxy section */ - FEA5F4E11497FFF6005052F9 /* libports.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libports.a; - remoteRef = FEA5F4E01497FFF6005052F9 /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEE70DA7153487F200814606 /* libopts_ssse3.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libopts_ssse3.a; - remoteRef = FEE70DA6153487F200814606 /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED7262144DD38D0059E97B /* libviews.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libviews.a; - remoteRef = FEED7261144DD38D0059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED7268144DD3EA0059E97B /* libanimator.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libanimator.a; - remoteRef = FEED7267144DD3EA0059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED726E144DD4050059E97B /* libexperimental.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libexperimental.a; - remoteRef = FEED726D144DD4050059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED7276144DD4140059E97B /* libskgr.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libskgr.a; - remoteRef = FEED7275144DD4140059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED7278144DD4140059E97B /* libgr.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libgr.a; - remoteRef = FEED7277144DD4140059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED727E144DD4200059E97B /* libimages.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libimages.a; - remoteRef = FEED727D144DD4200059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED7284144DD4300059E97B /* libtess.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libtess.a; - remoteRef = FEED7283144DD4300059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED728A144DD4440059E97B /* libpdf.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libpdf.a; - remoteRef = FEED7289144DD4440059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED7290144DD44D0059E97B /* libsvg.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libsvg.a; - remoteRef = FEED728F144DD44D0059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEED72A1144DD4A80059E97B /* libxml.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libxml.a; - remoteRef = FEED72A0144DD4A80059E97B /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEF87C1A13E040E000335C58 /* libcore.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libcore.a; - remoteRef = FEF87C1913E040E000335C58 /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEF87C2313E040F100335C58 /* libeffects.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libeffects.a; - remoteRef = FEF87C2213E040F100335C58 /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEF87C2C13E0410900335C58 /* libopts.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libopts.a; - remoteRef = FEF87C2B13E0410900335C58 /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; - FEF87C3B13E0412600335C58 /* libutils.a */ = { - isa = PBXReferenceProxy; - fileType = archive.ar; - path = libutils.a; - remoteRef = FEF87C3A13E0412600335C58 /* PBXContainerItemProxy */; - sourceTree = BUILT_PRODUCTS_DIR; - }; -/* End PBXReferenceProxy section */ - -/* Begin PBXResourcesBuildPhase section */ - 8D1107290486CEB800E47090 /* Resources */ = { - isa = PBXResourcesBuildPhase; - buildActionMask = 2147483647; - files = ( - 8D11072B0486CEB800E47090 /* InfoPlist.strings in Resources */, - 1DDD58160DA1D0A300B32029 /* MainMenu.xib in Resources */, - FEED72B0144DD5710059E97B /* SampleApp.xib in Resources */, - FE3DBAFE150E4A680006ADF4 /* junk.htm in Resources */, - FE99AE40151B4ED10072AA0D /* tempskinny4.txt in Resources */, - FE99AE44151B4EE70072AA0D /* xtempskinny4.txt in Resources */, - FE99AEBE151B64ED0072AA0D /* op.htm in Resources */, - ); - runOnlyForDeploymentPostprocessing = 0; - }; -/* End PBXResourcesBuildPhase section */ - -/* Begin PBXSourcesBuildPhase section */ - 8D11072C0486CEB800E47090 /* Sources */ = { - isa = PBXSourcesBuildPhase; - buildActionMask = 2147483647; - files = ( - FEA6778313C4B3A300FE6FC1 /* EdgeApp.cpp in Sources */, - FE3201C8144DCC68006DDA67 /* skia_mac.mm in Sources */, - FE3201C9144DCC68006DDA67 /* SkOSWindow_Mac.mm in Sources */, - FEED7245144DD2250059E97B /* SkEventNotifier.mm in Sources */, - FEED72AB144DD50A0059E97B /* SampleAppDelegate.mm in Sources */, - FEED7626144F22E20059E97B /* CubicReduceOrder_Test.cpp in Sources */, - FEED762C144F236C0059E97B /* CubicIntersection_TestData.cpp in Sources */, - FEED764C144F29BD0059E97B /* TestUtilities.cpp in Sources */, - FEED768A144F2E7D0059E97B /* CubicIntersection_Test.cpp in Sources */, - FEED76C1144F3E7F0059E97B /* ConvexHull_Test.cpp in Sources */, - FEED76EE144F66E90059E97B /* Intersection_Tests.cpp in Sources */, - FED53C391483CB9400F6359E /* Inline_Tests.cpp in Sources */, - FEC117CC14843B0A0086BF1F /* CubicBezierClip_Test.cpp in Sources */, - FEC118B8148666670086BF1F /* ConvexHull.cpp in Sources */, - FEC118C2148668F30086BF1F /* DataTypes.cpp in Sources */, - FEC11911148682200086BF1F /* CubicReduceOrder.cpp in Sources */, - FEC1191B148683330086BF1F /* Extrema.cpp in Sources */, - FEC1195514869DCA0086BF1F /* LineIntersection.cpp in Sources */, - FEC11E3E148D65780086BF1F /* CubicSubDivide.cpp in Sources */, - FEC12116148EB4EC0086BF1F /* CubicIntersection.cpp in Sources */, - FEC1211B148EB5200086BF1F /* CubicBezierClip.cpp in Sources */, - FEC1238F149000100086BF1F /* LineParameteters_Test.cpp in Sources */, - FEC123A6149001A00086BF1F /* SkAntiEdge.cpp in Sources */, - FEC12CE014913E650086BF1F /* LineIntersection_Test.cpp in Sources */, - FECA984014AA044100B35E2C /* CubicParameterization.cpp in Sources */, - FECA985114AA046600B35E2C /* QuadraticParameterization.cpp in Sources */, - FECA986214AA2E5900B35E2C /* QuadraticParameterization_Test.cpp in Sources */, - FECA987814AA319300B35E2C /* QuadraticSubDivide.cpp in Sources */, - FECA997C14AB966900B35E2C /* CubicParameterizationCode.cpp in Sources */, - FECA9A5A14B3B09100B35E2C /* CubicParameterization_Test.cpp in Sources */, - FECAA52214BB527000B35E2C /* QuadraticIntersection.cpp in Sources */, - FECAA56D14BCA23200B35E2C /* QuadraticReduceOrder.cpp in Sources */, - FECAA58414BCBD4E00B35E2C /* QuadraticBezierClip.cpp in Sources */, - FECAA67914BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp in Sources */, - FECAA68514BCDE2600B35E2C /* QuadraticIntersection_TestData.cpp in Sources */, - FECAA6C714BDCE9B00B35E2C /* QuadraticIntersection_Test.cpp in Sources */, - FECAA6E114BDDF2D00B35E2C /* QuadraticReduceOrder_Test.cpp in Sources */, - FE7130A114CE0EEB0008E392 /* LineQuadraticIntersection.cpp in Sources */, - FE7131C414CF5A960008E392 /* LineQuadraticIntersection_Test.cpp in Sources */, - FE7131EE14D03AED0008E392 /* LineCubicIntersection.cpp in Sources */, - FE71324214D047670008E392 /* QuadraticUtilities.cpp in Sources */, - FE71324F14D04D460008E392 /* CubicUtilities.cpp in Sources */, - FE71325014D04D480008E392 /* CubeRoot.cpp in Sources */, - FE71325F14D050D80008E392 /* LineUtilities.cpp in Sources */, - FE71334214D06B0F0008E392 /* LineCubicIntersection_Test.cpp in Sources */, - FE7134F514D1E7C70008E392 /* LineParameterization.cpp in Sources */, - FE71351314D2E9F50008E392 /* RectUtilities.cpp in Sources */, - FE71358614D309E90008E392 /* EdgeWalker.cpp in Sources */, - FEA61B2C14F2AF6600B736CB /* EdgeWalkerRectangles_Test.cpp in Sources */, - FE7413D414F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp in Sources */, - FE7413D814F691C200056D7B /* EdgeWalker_TestUtility.cpp in Sources */, - FED865F915056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp in Sources */, - FED866D715066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp in Sources */, - FE99AF2B151CC0AA0072AA0D /* ActiveEdge_Test.cpp in Sources */, - FE99B13215209E300072AA0D /* EdgeWalkerPolygon4x4_Test.cpp in Sources */, - ); - runOnlyForDeploymentPostprocessing = 0; - }; -/* End PBXSourcesBuildPhase section */ - -/* Begin PBXTargetDependency section */ - FEF87C4113E0414D00335C58 /* PBXTargetDependency */ = { - isa = PBXTargetDependency; - name = core; - targetProxy = FEF87C4013E0414D00335C58 /* PBXContainerItemProxy */; - }; - FEF87C4313E0415100335C58 /* PBXTargetDependency */ = { - isa = PBXTargetDependency; - name = effects; - targetProxy = FEF87C4213E0415100335C58 /* PBXContainerItemProxy */; - }; - FEF87C4513E0415500335C58 /* PBXTargetDependency */ = { - isa = PBXTargetDependency; - name = opts; - targetProxy = FEF87C4413E0415500335C58 /* PBXContainerItemProxy */; - }; - FEF87C4713E0415900335C58 /* PBXTargetDependency */ = { - isa = PBXTargetDependency; - name = utils; - targetProxy = FEF87C4613E0415900335C58 /* PBXContainerItemProxy */; - }; -/* End PBXTargetDependency section */ - -/* Begin PBXVariantGroup section */ - 089C165CFE840E0CC02AAC07 /* InfoPlist.strings */ = { - isa = PBXVariantGroup; - children = ( - 089C165DFE840E0CC02AAC07 /* English */, - ); - name = InfoPlist.strings; - sourceTree = "<group>"; - }; - 1DDD58140DA1D0A300B32029 /* MainMenu.xib */ = { - isa = PBXVariantGroup; - children = ( - 1DDD58150DA1D0A300B32029 /* English */, - ); - name = MainMenu.xib; - sourceTree = "<group>"; - }; -/* End PBXVariantGroup section */ - -/* Begin XCBuildConfiguration section */ - C01FCF4B08A954540054247B /* Debug */ = { - isa = XCBuildConfiguration; - buildSettings = { - CLANG_WARN_CXX0X_EXTENSIONS = NO; - GCC_OPTIMIZATION_LEVEL = 0; - INFOPLIST_FILE = "edge-Info.plist"; - LIBRARY_SEARCH_PATHS = "$(SDKROOT)/System/Library/Frameworks"; - PRODUCT_NAME = edge; - SDKROOT = macosx10.6; - SYMROOT = ../xcodebuild; - WRAPPER_PREFIX = ""; - }; - name = Debug; - }; - C01FCF4C08A954540054247B /* Release */ = { - isa = XCBuildConfiguration; - buildSettings = { - CLANG_WARN_CXX0X_EXTENSIONS = NO; - GCC_OPTIMIZATION_LEVEL = 3; - INFOPLIST_FILE = "edge-Info.plist"; - LIBRARY_SEARCH_PATHS = "$(SDKROOT)/System/Library/Frameworks"; - PRODUCT_NAME = edge; - SDKROOT = macosx10.6; - SYMROOT = ../xcodebuild; - WRAPPER_PREFIX = ""; - }; - name = Release; - }; - C01FCF4F08A954540054247B /* Debug */ = { - isa = XCBuildConfiguration; - buildSettings = { - GCC_PREPROCESSOR_DEFINITIONS = ( - "\"SK_SCALAR_IS_FLOAT\"", - "\"SK_CAN_USE_FLOAT\"", - "\"SK_BUILD_FOR_MAC\"", - "\"SK_USE_POSIX_THREADS\"", - "\"GR_MAC_BUILD=1\"", - "\"SK_SUPPORT_PDF\"", - "\"SK_DEBUG\"", - "\"GR_DEBUG=1\"", - ); - HEADER_SEARCH_PATHS = ( - ../../gpu/include, - ../../src/core, - "../../include/**", - ../../gm, - ); - INTERMEDIATE_DIR = "$(PROJECT_DERIVED_FILE_DIR)/$(CONFIGURATION)"; - SHARED_INTERMEDIATE_DIR = "$(SYMROOT)/DerivedSources/$(CONFIGURATION)"; - }; - name = Debug; - }; - C01FCF5008A954540054247B /* Release */ = { - isa = XCBuildConfiguration; - buildSettings = { - GCC_PREPROCESSOR_DEFINITIONS = ( - "\"SK_SCALAR_IS_FLOAT\"", - "\"SK_CAN_USE_FLOAT\"", - "\"SK_BUILD_FOR_MAC\"", - "\"SK_USE_POSIX_THREADS\"", - "\"GR_MAC_BUILD=1\"", - "\"SK_SUPPORT_PDF\"", - "\"SK_RELEASE\"", - "\"GR_RELEASE=1\"", - "\"NDEBUG\"", - ); - HEADER_SEARCH_PATHS = ( - ../../gpu/include, - ../../src/core, - "../../include/**", - ../../gm, - ); - INTERMEDIATE_DIR = "$(PROJECT_DERIVED_FILE_DIR)/$(CONFIGURATION)"; - SHARED_INTERMEDIATE_DIR = "$(SYMROOT)/DerivedSources/$(CONFIGURATION)"; - }; - name = Release; - }; -/* End XCBuildConfiguration section */ - -/* Begin XCConfigurationList section */ - C01FCF4A08A954540054247B /* Build configuration list for PBXNativeTarget "edge" */ = { - isa = XCConfigurationList; - buildConfigurations = ( - C01FCF4B08A954540054247B /* Debug */, - C01FCF4C08A954540054247B /* Release */, - ); - defaultConfigurationIsVisible = 0; - defaultConfigurationName = Release; - }; - C01FCF4E08A954540054247B /* Build configuration list for PBXProject "edge" */ = { - isa = XCConfigurationList; - buildConfigurations = ( - C01FCF4F08A954540054247B /* Debug */, - C01FCF5008A954540054247B /* Release */, - ); - defaultConfigurationIsVisible = 0; - defaultConfigurationName = Release; - }; -/* End XCConfigurationList section */ - }; - rootObject = 29B97313FDCFA39411CA2CEA /* Project object */; -} diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index 5173eaba27..f496f7c16a 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -259,11 +259,76 @@ path.close(); testSimplify(path, true, out, bitmap); drawAsciiPaths(path, out, true); </div> + +<div id="testSimplifyQuadratic19"> + SkPath path, simple; + path.moveTo(0,4); + path.lineTo(6,4); + path.lineTo(3,1); + path.close(); + path.moveTo(2,3); + path.lineTo(3,2); + path.lineTo(4,3); + path.close(); + testSimplifyx(path); +</div> + +<div id="testSimplifyQuadratic20"> + SkPath path, simple; + path.moveTo(0,4); + path.lineTo(6,4); + path.lineTo(3,1); + path.close(); + path.moveTo(2,3); + path.lineTo(4,3); + path.lineTo(3,2); + path.close(); + testSimplifyx(path); +</div> + +<div id="testSimplifyQuadratic21"> + SkPath path, simple; + path.moveTo(0,4); + path.lineTo(8,4); + path.lineTo(4,0); + path.close(); + path.moveTo(2,2); + path.lineTo(3,3); + path.lineTo(4,2); + path.close(); + testSimplifyx(path); +</div> + +<div id="testLine6"> + SkPath path, simple; + path.moveTo(0,0); + path.lineTo(4,0); + path.lineTo(2,2); + path.close(); + path.moveTo(2,0); + path.lineTo(6,0); + path.lineTo(4,2); + path.close(); + testSimplifyx(path); +</div> + +<!-- don't support addRect yet --> +<div id="testLine17"> + SkPath path, simple; + path.addRect(0, 0, 12, 12, (SkPath::Direction) 0); + path.addRect(4, 12, 13, 13, (SkPath::Direction) 0); + testSimplifyx(path); +</div> + </div> <script type="text/javascript"> var testDivs = [ + testLine6, + testSimplifyQuadratic21, + testSimplifyQuadratic20, + testSimplifyQuadratic19, testSimplifyQuadratic18, testSimplifyQuadratic17, testSimplifyQuadratic16, @@ -412,10 +477,10 @@ function draw(test, _at_x, _at_y, scale) { } ctx.strokeStyle = "red"; var contours, verbs, pts; + ctx.beginPath(); for (contours in test) { var contour = test[contours]; if (contours == 2) ctx.strokeStyle = "blue"; - ctx.beginPath(); var first = true; for (verbs in contour) { var verb = contour[verbs]; @@ -438,8 +503,11 @@ function draw(test, _at_x, _at_y, scale) { break; } } - ctx.stroke(); + ctx.closePath(); } + ctx.stroke(); + ctx.fillStyle="rgba(192,192,255, 0.3)"; + ctx.fill(); ctx.fillStyle="blue"; for (contours in test) { diff --git a/experimental/Intersection/thingsToDo.txt b/experimental/Intersection/thingsToDo.txt index e3aec3e9cd..ab1be7fbf3 100644 --- a/experimental/Intersection/thingsToDo.txt +++ b/experimental/Intersection/thingsToDo.txt @@ -164,3 +164,356 @@ According to Mike/Rob, the flatness for quadratics increases by 4 for each subdivision, and a crude guess of the curvature can be had by comparing P1 to (P0+P2)/2. By looking at the ULPS of the numbers, I can guess what value of T may be far enough that the curves diverge but don't cross. + +==== + +Code I May Not Need Any More + + static bool CoincidentCandidate(const Angle* current) { + const Segment* segment = current->segment(); + int min = SkMin32(current->start(), current->end()); + do { + const Span& span = segment->fTs[min]; + if (span.fCoincident == Span::kStart_Coincidence) { + return true; + } + } while (--min >= 0); + return false; + } + + static bool CoincidentHalf(const Angle* current, const Angle* next) { + const Segment* other = next->segment(); + const Segment* segment = current->segment(); + int min = SkMin32(current->start(), current->end()); + const Span& minSpan = segment->fTs[min]; + if (minSpan.fOther == other) { + return minSpan.fCoincident == Span::kStart_Coincidence; + } + int index = min; + int spanCount = segment->fTs.count(); + while (++index < spanCount) { + const Span& span = segment->fTs[index]; + if (minSpan.fT != span.fT) { + break; + } + if (span.fOther != other) { + continue; + } + return span.fCoincident == Span::kStart_Coincidence; + } + index = min; + while (--index >= 0) { + const Span& span = segment->fTs[index]; + if (span.fOther != other) { + continue; + } + return span.fCoincident == Span::kStart_Coincidence; + } + return false; + } + + static bool Coincident(const Angle* current, const Angle* next) { + return CoincidentHalf(current, next) && + CoincidentHalf(next, current); + } + + // If three lines cancel in a - b - c order, a - b may or may not + // eliminate the edge that describes the b - c cancellation. Check done to + // determine this. + static bool CoincidentCancels(const Angle* current, const Angle* next) { + int curMin = SkMin32(current->start(), current->end()); + if (current->segment()->fTs[curMin].fDone) { + return false; + } + int nextMin = SkMin32(next->start(), next->end()); + if (next->segment()->fTs[nextMin].fDone) { + return false; + } + return SkSign32(current->start() - current->end()) + != SkSign32(next->start() - next->end()); + } + + // FIXME: at this point, just have two functions for the different steps + int coincidentEnd(int from, int step) const { + double fromT = fTs[from].fT; + int count = fTs.count(); + int to = from; + while (step > 0 ? ++to < count : --to >= 0) { + const Span& span = fTs[to]; + if ((step > 0 ? span.fT - fromT : fromT - span.fT) >= FLT_EPSILON ) { + // FIXME: we assume that if the T changes, we don't care about + // coincident -- but in nextSpan, we require that both the T + // and actual loc change to represent a span. This asymettry may + // be OK or may be trouble -- if trouble, probably will need to + // detect coincidence earlier or sort differently + break; + } +#if 01 + if (span.fCoincident == (step < 0 ? Span::kStart_Coincidence : + Span::kEnd_Coincidence)) { + from = to; + } +#else + from = to; +#endif + } + return from; + } + + // once past current span, if step>0, look for coicident==1 + // if step<0, look for coincident==-1 + int nextSpanEnd(int from, int step) const { + int result = nextSpan(from, step); + if (result < 0) { + return result; + } + return coincidentEnd(result, step); + } + + + void adjustFirst(const SkTDArray<Angle*>& sorted, int& first, int& winding, + bool outside) { + int firstIndex = first; + int angleCount = sorted.count(); + if (true || outside) { + const Angle* angle = sorted[firstIndex]; + int prior = firstIndex; + do { + if (--prior < 0) { + prior = angleCount - 1; + } + if (prior == firstIndex) { // all are coincident with each other + return; + } + if (!Coincident(sorted[prior], sorted[first])) { + return; + } + winding += angle->sign(); + first = prior; + angle = sorted[prior]; + winding -= angle->sign(); + } while (true); + } + do { + int next = first + 1; + if (next == angleCount) { + next = 0; + } + if (next == firstIndex) { // all are coincident with each other + return; + } + if (!Coincident(sorted[first], sorted[next])) { + return; + } + first = next; + } while (true); + } + + bool nextIsCoincident = CoincidentCandidate(nextAngle); + bool finalOrNoCoincident = true; + bool pairCoincides = false; + bool pairCancels = false; + if (nextIsCoincident) { + int followIndex = nextIndex + 1; + if (followIndex == angleCount) { + followIndex = 0; + } + const Angle* followAngle = sorted[followIndex]; + finalOrNoCoincident = !Coincident(nextAngle, followAngle); + if ((pairCoincides = Coincident(angle, nextAngle))) { + pairCancels = CoincidentCancels(angle, nextAngle); + } + } + if (pairCancels && !foundAngle && !nextSegment->done()) { + Segment* aSeg = angle->segment(); + // alreadyMarked |= aSeg == sorted[firstIndex]->segment(); + aSeg->markAndChaseCoincident(angle->start(), angle->end(), + nextSegment); + if (firstEdge) { + return NULL; + } + } + if (pairCoincides) { + if (pairCancels) { + goto doNext; + } + int minT = SkMin32(nextAngle->start(), nextAngle->end()); + bool markNext = abs(maxWinding) < abs(winding); + if (markNext) { + nextSegment->markDone(minT, winding); + } + int oldMinT = SkMin32(angle->start(), angle->end()); + if (true || !foundAngle) { + // SkASSERT(0); // do we ever get here? + Segment* aSeg = angle->segment(); + // alreadyMarked |= aSeg == sorted[firstIndex]->segment(); + aSeg->markDone(oldMinT, maxWinding); + } + } + + // OPTIMIZATION: uses tail recursion. Unwise? + void innerCoincidentChase(int step, Segment* other) { + // find other at index + // SkASSERT(!done()); + const Span* start = NULL; + const Span* end = NULL; + int index, startIndex, endIndex; + int count = fTs.count(); + for (index = 0; index < count; ++index) { + const Span& span = fTs[index]; + if (!span.fCoincident || span.fOther != other) { + continue; + } + if (!start) { + startIndex = index; + start = &span; + } else { + SkASSERT(!end); + endIndex = index; + end = &span; + } + } + if (!end) { + return; + } + bool thisDone = fTs[SkMin32(startIndex, endIndex)].fDone; + bool otherDone = other->fTs[SkMin32(start->fOtherIndex, + end->fOtherIndex)].fDone; + if (thisDone && otherDone) { + return; + } + Segment* next; + Segment* nextOther; + if (step < 0) { + next = start->fT == 0 ? NULL : this; + nextOther = other->fTs[start->fOtherIndex].fT > 1 - FLT_EPSILON ? NULL : other; + } else { + next = end->fT == 1 ? NULL : this; + nextOther = other->fTs[end->fOtherIndex].fT < FLT_EPSILON ? NULL : other; + } + SkASSERT(!next || !nextOther); + for (index = 0; index < count; ++index) { + const Span& span = fTs[index]; + if (span.fCoincident || span.fOther == other) { + continue; + } + bool checkNext = !next && (step < 0 ? span.fT < FLT_EPSILON + && span.fOtherT > 1 - FLT_EPSILON : span.fT > 1 - FLT_EPSILON + && span.fOtherT < FLT_EPSILON); + bool checkOther = !nextOther && (step < 0 ? fabs(span.fT - start->fT) < FLT_EPSILON + && span.fOtherT < FLT_EPSILON : fabs(span.fT - end->fT) < FLT_EPSILON + && span.fOtherT > 1 - FLT_EPSILON); + if (!checkNext && !checkOther) { + continue; + } + Segment* oSegment = span.fOther; + if (oSegment->done()) { + continue; + } + int oCount = oSegment->fTs.count(); + for (int oIndex = 0; oIndex < oCount; ++oIndex) { + const Span& oSpan = oSegment->fTs[oIndex]; + if (oSpan.fT >= FLT_EPSILON && oSpan.fT <= 1 - FLT_EPSILON) { + continue; + } + if (!oSpan.fCoincident) { + continue; + } + if (checkNext && (oSpan.fT < FLT_EPSILON ^ step < 0)) { + next = oSegment; + checkNext = false; + } + if (checkOther && (oSpan.fT > 1 - FLT_EPSILON ^ step < 0)) { + nextOther = oSegment; + checkOther = false; + } + } + } + // this needs to walk both spans in lock step, skipping edges that + // are already marked done on one or the other + markCanceled(startIndex, endIndex); + if (next && nextOther) { + next->innerCoincidentChase(step, nextOther); + } + } + + // cancel coincident edges in lock step + void markCanceled(int start, int end) { + if (done()) { + return; + } + Segment* other = fTs[start].fOther; + if (other->done()) { + return; + } + if (start > end) { + SkTSwap<int>(start, end); + } + double maxT = fTs[end].fT - FLT_EPSILON; + int spanCount = fTs.count(); + // since these cancel, this walks up and other walks down + int oStart = fTs[start].fOtherIndex; + double oStartT = other->fTs[oStart].fT; + while (oStartT - other->fTs[--oStart].fT < FLT_EPSILON) + ; + double startT = fTs[start].fT; + while (start > 0 && startT - fTs[start - 1].fT < FLT_EPSILON) { + --start; + } + do { + Span* span = &fTs[start]; + Span* oSpan = &other->fTs[oStart]; + // find start of each, and see if both are not done + bool markDone = !span->fDone && !oSpan->fDone; + double spanT = span->fT; + do { + if (markDone) { + span->fCanceled = true; + #if DEBUG_MARK_DONE + const SkPoint& pt = xyAtT(span); + SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", + __FUNCTION__, fID, start, span->fT, pt.fX, pt.fY); + #endif + SkASSERT(!span->fDone); + span->fDone = true; + span->fWinding = 0; + fDoneSpans++; + } + if (++start == spanCount) { + break; + } + span = &fTs[start]; + } while (span->fT - spanT < FLT_EPSILON); + double oSpanT = oSpan->fT; + do { + if (markDone) { + oSpan->fCanceled = true; + #if DEBUG_MARK_DONE + const SkPoint& oPt = xyAtT(oSpan); + SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", + __FUNCTION__, other->fID, oStart, oSpan->fT, + oPt.fX, oPt.fY); + #endif + SkASSERT(!oSpan->fDone); + oSpan->fDone = true; + oSpan->fWinding = 0; + other->fDoneSpans++; + } + if (--oStart < 0) { + break; + } + oSpan = &other->fTs[oStart]; + } while (oSpanT - oSpan->fT < FLT_EPSILON); + } while (fTs[start].fT <= maxT); + } + + bool canceled(int start, int end) const { + int min = SkMin32(start, end); + return fTs[min].fCanceled; + } + + void markAndChaseCoincident(int index, int endIndex, Segment* other) { + int step = SkSign32(endIndex - index); + innerCoincidentChase(step, other); + } + |