aboutsummaryrefslogtreecommitdiffhomepage
path: root/experimental
diff options
context:
space:
mode:
authorGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-07-02 20:27:02 +0000
committerGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-07-02 20:27:02 +0000
commit8dcf114db9762c02d217beba6e29dffa4e92d298 (patch)
tree3d55d0135db941b88684a11cd794498b1777fb94 /experimental
parent0985c558fc7e014f5680a7532270c6cbad2bca6a (diff)
shape ops work in progress
M Intersection/DataTypes.cpp M Intersection/QuadraticIntersection_Test.cpp M Intersection/EdgeWalker.cpp M Intersection/LineQuadraticIntersection_Test.cpp M Intersection/LineIntersection_Test.cpp M Intersection/LineIntersection.cpp D Intersection/edge.xcodeproj M Intersection/SimplifyFindTop_Test.cpp M Intersection/DataTypes.h A Intersection/SimplifyRect4x4_Test.cpp M Intersection/CubicIntersection_Test.cpp M Intersection/QuadraticUtilities.h M Intersection/LineCubicIntersection_Test.cpp A Intersection/CurveUtilities.h M Intersection/QuadraticBezierClip.cpp M Intersection/QuadraticBounds.cpp M Intersection/LineUtilities.h M Intersection/Intersection_Tests.cpp M Intersection/Simplify.cpp M Intersection/EdgeWalker_TestUtility.cpp M Intersection/QuadraticUtilities.cpp M Intersection/thingsToDo.txt M Intersection/LineUtilities.cpp M Intersection/CubicUtilities.h M Intersection/SimplifyFindNext_Test.cpp M Intersection/Intersection_Tests.h M Intersection/CubicBezierClip.cpp M Intersection/ActiveEdge_Test.cpp M Intersection/CubicBounds.cpp M Intersection/Simplify.h M Intersection/SimplifyNew_Test.cpp M Intersection/EdgeWalker_Test.h M Intersection/CubicUtilities.cpp M Intersection/op.htm M Intersection/ConvexHull.cpp D Intersection/RectUtilities.cpp M Intersection/SimplifyAddIntersectingTs_Test.cpp git-svn-id: http://skia.googlecode.com/svn/trunk@4429 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'experimental')
-rwxr-xr-xexperimental/Intersection/ActiveEdge_Test.cpp10
-rw-r--r--experimental/Intersection/ConvexHull.cpp1
-rw-r--r--experimental/Intersection/CubicBezierClip.cpp1
-rw-r--r--experimental/Intersection/CubicBounds.cpp1
-rw-r--r--experimental/Intersection/CubicIntersection_Test.cpp1
-rw-r--r--experimental/Intersection/CubicUtilities.cpp72
-rw-r--r--experimental/Intersection/CubicUtilities.h9
-rw-r--r--experimental/Intersection/CurveUtilities.h15
-rw-r--r--experimental/Intersection/DataTypes.cpp109
-rw-r--r--experimental/Intersection/DataTypes.h16
-rw-r--r--experimental/Intersection/EdgeWalker.cpp10
-rw-r--r--experimental/Intersection/EdgeWalker_Test.h3
-rw-r--r--experimental/Intersection/EdgeWalker_TestUtility.cpp35
-rw-r--r--experimental/Intersection/Intersection_Tests.cpp2
-rw-r--r--experimental/Intersection/Intersection_Tests.h1
-rw-r--r--experimental/Intersection/LineCubicIntersection_Test.cpp2
-rw-r--r--experimental/Intersection/LineIntersection.cpp72
-rw-r--r--experimental/Intersection/LineIntersection_Test.cpp1
-rw-r--r--experimental/Intersection/LineQuadraticIntersection_Test.cpp2
-rw-r--r--experimental/Intersection/LineUtilities.cpp61
-rw-r--r--experimental/Intersection/LineUtilities.h14
-rw-r--r--experimental/Intersection/QuadraticBezierClip.cpp1
-rw-r--r--experimental/Intersection/QuadraticBounds.cpp1
-rw-r--r--experimental/Intersection/QuadraticIntersection_Test.cpp1
-rw-r--r--experimental/Intersection/QuadraticUtilities.cpp25
-rw-r--r--experimental/Intersection/QuadraticUtilities.h6
-rw-r--r--experimental/Intersection/RectUtilities.cpp0
-rw-r--r--experimental/Intersection/Simplify.cpp1391
-rw-r--r--experimental/Intersection/Simplify.h1
-rw-r--r--experimental/Intersection/SimplifyAddIntersectingTs_Test.cpp2
-rw-r--r--experimental/Intersection/SimplifyFindNext_Test.cpp6
-rw-r--r--experimental/Intersection/SimplifyFindTop_Test.cpp4
-rw-r--r--experimental/Intersection/SimplifyNew_Test.cpp259
-rw-r--r--experimental/Intersection/SimplifyRect4x4_Test.cpp209
-rw-r--r--experimental/Intersection/edge.xcodeproj/project.pbxproj1134
-rw-r--r--experimental/Intersection/op.htm72
-rw-r--r--experimental/Intersection/thingsToDo.txt353
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 = &current->addMoveTo(index, simple);
+ firstPt = &current->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);
+ }
+