aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-03-28 16:20:21 +0000
committerGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-03-28 16:20:21 +0000
commita5764233aa6b207c4169fff7fccae567a160a0fd (patch)
tree61f3d9581e178cf6c589711ef5c3b9b140448eaf
parentd3b9fbbc48c13a1b2a664cf7e01374a44c201f51 (diff)
first support at shape ops support for quads
git-svn-id: http://skia.googlecode.com/svn/trunk@3520 2bbb7eff-a529-9590-31e7-b0007b416f81
-rwxr-xr-xexperimental/Intersection/ActiveEdge_Test.cpp2
-rw-r--r--experimental/Intersection/EdgeDemo.cpp176
-rw-r--r--experimental/Intersection/EdgeDemo.h3
-rw-r--r--experimental/Intersection/EdgeDemoApp.mm68
-rw-r--r--experimental/Intersection/EdgeWalker.cpp696
-rw-r--r--experimental/Intersection/EdgeWalkerPolygons_Test.cpp8
-rw-r--r--experimental/Intersection/EdgeWalkerQuadratics_Test.cpp64
-rw-r--r--experimental/Intersection/Intersection_Tests.cpp4
-rw-r--r--experimental/Intersection/Intersection_Tests.h1
-rw-r--r--experimental/Intersection/Intersections.h8
-rw-r--r--experimental/Intersection/op.htm17
-rw-r--r--gyp/shapeops_demo.gyp52
-rw-r--r--gyp/shapeops_edge.gyp22
13 files changed, 771 insertions, 350 deletions
diff --git a/experimental/Intersection/ActiveEdge_Test.cpp b/experimental/Intersection/ActiveEdge_Test.cpp
index 2ee408921e..d89510f1d4 100755
--- a/experimental/Intersection/ActiveEdge_Test.cpp
+++ b/experimental/Intersection/ActiveEdge_Test.cpp
@@ -1,9 +1,11 @@
#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"
namespace UnitTest {
diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp
new file mode 100644
index 0000000000..b71b8186b2
--- /dev/null
+++ b/experimental/Intersection/EdgeDemo.cpp
@@ -0,0 +1,176 @@
+#include "EdgeDemo.h"
+#include "EdgeWalker_Test.h"
+#include "ShapeOps.h"
+#import "SkCanvas.h"
+#import "SkPaint.h"
+
+// Three circles bounce inside a rectangle. The circles describe three, four
+// or five points which in turn describe a polygon. The polygon points
+// bounce inside the circles. The circles rotate and scale over time. The
+// polygons are combined into a single path, simplified, and stroked.
+static bool drawCircles(SkCanvas* canvas, int step)
+{
+ const int circles = 3;
+ int scales[circles];
+ int angles[circles];
+ int locs[circles * 2];
+ int pts[circles * 2 * 4];
+ int c, p;
+ for (c = 0; c < circles; ++c) {
+ scales[c] = abs(10 - (step + c * 4) % 21);
+ angles[c] = (step + c * 6) % 600;
+ locs[c * 2] = abs(130 - (step + c * 9) % 261);
+ locs[c * 2 + 1] = abs(170 - (step + c * 11) % 341);
+ for (p = 0; p < 4; ++p) {
+ pts[c * 8 + p * 2] = abs(90 - ((step + c * 121 + p * 13) % 190));
+ pts[c * 8 + p * 2 + 1] = abs(110 - ((step + c * 223 + p * 17) % 230));
+ }
+ }
+ SkPath path, out;
+ for (c = 0; c < circles; ++c) {
+ for (p = 0; p < 4; ++p) {
+ SkScalar x = pts[c * 8 + p * 2];
+ SkScalar y = pts[c * 8 + p * 2 + 1];
+ x *= 3 + scales[c] / 10.0f;
+ y *= 3 + scales[c] / 10.0f;
+ SkScalar angle = angles[c] * 3.1415f * 2 / 600;
+ SkScalar temp = x * cos(angle) - y * sin(angle);
+ y = x * sin(angle) + y * cos(angle);
+ x = temp;
+ x += locs[c * 2] * 200 / 130.0f;
+ y += locs[c * 2 + 1] * 200 / 170.0f;
+ x += 50;
+ // y += 200;
+ if (p == 0) {
+ path.moveTo(x, y);
+ } else {
+ path.lineTo(x, y);
+ }
+ }
+ path.close();
+ }
+ showPath(path, "original:");
+ simplify(path, true, out);
+ showPath(out, "simplified:");
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ paint.setStyle(SkPaint::kStroke_Style);
+ paint.setStrokeWidth(3);
+ paint.setColor(0x3F007fbF);
+ canvas->drawPath(path, paint);
+ paint.setColor(0xFF60FF00);
+ paint.setStrokeWidth(1);
+ canvas->drawPath(out, paint);
+ return true;
+}
+
+static void createStar(SkPath& path, SkScalar innerRadius, SkScalar outerRadius,
+ SkScalar startAngle, int points, SkPoint center) {
+ SkScalar angle = startAngle;
+ for (int index = 0; index < points * 2; ++index) {
+ SkScalar radius = index & 1 ? outerRadius : innerRadius;
+ SkScalar x = radius * cos(angle);
+ SkScalar y = radius * sin(angle);
+ x += center.fX;
+ y += center.fY;
+ if (index == 0) {
+ path.moveTo(x, y);
+ } else {
+ path.lineTo(x, y);
+ }
+ angle += 3.1415f / points;
+ }
+ path.close();
+}
+
+static bool drawStars(SkCanvas* canvas, int step)
+{
+ SkPath path, out;
+ const int stars = 25;
+ int pts[stars];
+ static bool initialize = true;
+ int s;
+ for (s = 0; s < stars; ++s) {
+ pts[s] = 4 + (s % 7);
+ }
+ SkPoint locs[stars];
+ SkScalar angles[stars];
+ SkScalar innerRadius[stars];
+ SkScalar outerRadius[stars];
+ const int width = 640;
+ const int height = 480;
+ const int margin = 30;
+ const int minRadius = 120;
+ const int maxInner = 800;
+ const int maxOuter = 1153;
+ for (s = 0; s < stars; ++s) {
+ int starW = width - margin * 2 + (SkScalar) s * (stars - s) / stars;
+ locs[s].fX = (int) (step * (1.3f * (s + 1) / stars) + s * 121) % (starW * 2);
+ if (locs[s].fX > starW) {
+ locs[s].fX = starW * 2 - locs[s].fX;
+ }
+ locs[s].fX += margin;
+ int starH = height - margin * 2 + (SkScalar) s * s / stars;
+ locs[s].fY = (int) (step * (1.7f * (s + 1) / stars) + s * 183) % (starH * 2);
+ if (locs[s].fY > starH) {
+ locs[s].fY = starH * 2 - locs[s].fY;
+ }
+ locs[s].fY += margin;
+ angles[s] = ((step + s * 47) % (360 * 4)) * 3.1415f / 180 / 4;
+ innerRadius[s] = (step + s * 30) % (maxInner * 2);
+ if (innerRadius[s] > maxInner) {
+ innerRadius[s] = (maxInner * 2) - innerRadius[s];
+ }
+ innerRadius[s] = innerRadius[s] / 4 + minRadius;
+ outerRadius[s] = (step + s * 70) % (maxOuter * 2);
+ if (outerRadius[s] > maxOuter) {
+ outerRadius[s] = (maxOuter * 2) - outerRadius[s];
+ }
+ outerRadius[s] = outerRadius[s] / 4 + minRadius;
+ createStar(path, innerRadius[s] / 4.0f, outerRadius[s] / 4.0f,
+ angles[s], pts[s], locs[s]);
+ }
+#define SHOW_PATH 0
+#if SHOW_PATH
+ showPath(path, "original:");
+#endif
+#define TEST_SIMPLIFY 01
+#if TEST_SIMPLIFY
+ simplify(path, true, out);
+#if SHOW_PATH
+ showPath(out, "simplified:");
+#endif
+#endif
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ paint.setStyle(SkPaint::kStroke_Style);
+ paint.setStrokeWidth(6);
+ paint.setColor(0x1F003f7f);
+ canvas->drawPath(path, paint);
+ paint.setColor(0xFF305F00);
+ paint.setStrokeWidth(1);
+#if TEST_SIMPLIFY
+ canvas->drawPath(out, paint);
+#endif
+ return true;
+}
+
+static bool (*drawDemos[])(SkCanvas* , int) = {
+ drawStars,
+ drawCircles
+};
+
+static size_t drawDemosCount = sizeof(drawDemos) / sizeof(drawDemos[0]);
+
+static bool (*firstTest)(SkCanvas* , int) = 0;
+
+
+bool DrawEdgeDemo(SkCanvas* canvas, int step) {
+ size_t index = 0;
+ if (firstTest) {
+ while (index < drawDemosCount && drawDemos[index] != firstTest) {
+ ++index;
+ }
+ }
+ return (*drawDemos[index])(canvas, step);
+}
diff --git a/experimental/Intersection/EdgeDemo.h b/experimental/Intersection/EdgeDemo.h
new file mode 100644
index 0000000000..21c1563d81
--- /dev/null
+++ b/experimental/Intersection/EdgeDemo.h
@@ -0,0 +1,3 @@
+class SkCanvas;
+
+bool DrawEdgeDemo(SkCanvas* canvas, int step);
diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm
index a8b233e424..baae8bcb2b 100644
--- a/experimental/Intersection/EdgeDemoApp.mm
+++ b/experimental/Intersection/EdgeDemoApp.mm
@@ -1,7 +1,5 @@
-#include "EdgeWalker_Test.h"
-#include "ShapeOps.h"
+#include "EdgeDemo.h"
#import "SkCanvas.h"
-#import "SkPaint.h"
#import "SkWindow.h"
#include "SkGraphics.h"
#include "SkCGUtils.h"
@@ -14,66 +12,13 @@ public:
};
protected:
virtual void onDraw(SkCanvas* canvas) {
- // Three circles bounce inside a rectangle. The circles describe three, four
- // or five points which in turn describe a polygon. The polygon points
- // bounce inside the circles. The circles rotate and scale over time. The
- // polygons are combined into a single path, simplified, and stroked.
- static int step = 0;
- const int circles = 3;
- int scales[circles];
- int angles[circles];
- int locs[circles * 2];
- int pts[circles * 2 * 4];
- int c, p;
- for (c = 0; c < circles; ++c) {
- scales[c] = abs(10 - (step + c * 4) % 21);
- angles[c] = (step + c * 6) % 600;
- locs[c * 2] = abs(130 - (step + c * 9) % 261);
- locs[c * 2 + 1] = abs(170 - (step + c * 11) % 341);
- for (p = 0; p < 4; ++p) {
- pts[c * 8 + p * 2] = abs(90 - ((step + c * 121 + p * 13) % 190));
- pts[c * 8 + p * 2 + 1] = abs(110 - ((step + c * 223 + p * 17) % 230));
+ static int step = 0;
+ canvas->drawColor(SK_ColorWHITE);
+ if (DrawEdgeDemo(canvas, step)) {
+ ++step;
+ inval(NULL);
}
}
- SkPath path, out;
- for (c = 0; c < circles; ++c) {
- for (p = 0; p < 4; ++p) {
- SkScalar x = pts[c * 8 + p * 2];
- SkScalar y = pts[c * 8 + p * 2 + 1];
- x *= 3 + scales[c] / 10.0f;
- y *= 3 + scales[c] / 10.0f;
- SkScalar angle = angles[c] * 3.1415f * 2 / 600;
- SkScalar temp = x * cos(angle) - y * sin(angle);
- y = x * sin(angle) + y * cos(angle);
- x = temp;
- x += locs[c * 2] * 200 / 130.0f;
- y += locs[c * 2 + 1] * 200 / 170.0f;
- x += 50;
- // y += 200;
- if (p == 0) {
- path.moveTo(x, y);
- } else {
- path.lineTo(x, y);
- }
- }
- path.close();
- }
- showPath(path, "original:");
- simplify(path, true, out);
- showPath(out, "simplified:");
- SkPaint paint;
- paint.setAntiAlias(true);
- paint.setStyle(SkPaint::kStroke_Style);
- paint.setStrokeWidth(3);
- paint.setColor(0x3F007fbF);
- canvas->drawPath(path, paint);
- paint.setColor(0xFF60FF00);
- paint.setStrokeWidth(1);
- canvas->drawColor(SK_ColorWHITE);
- canvas->drawPath(out, paint);
- ++step;
- inval(NULL);
- }
private:
typedef SkView INHERITED;
};
@@ -97,6 +42,7 @@ protected:
};
#import "SimpleApp.h"
+
@implementation SimpleNSView
- (id)initWithDefaults {
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp
index 59ce914e23..7f0ddffc01 100644
--- a/experimental/Intersection/EdgeWalker.cpp
+++ b/experimental/Intersection/EdgeWalker.cpp
@@ -7,6 +7,7 @@
*/
#include "CurveIntersection.h"
+#include "Intersections.h"
#include "LineIntersection.h"
#include "SkPath.h"
#include "SkRect.h"
@@ -15,14 +16,13 @@
#include "ShapeOps.h"
#include "TSearch.h"
-#if 0 // set to 1 for no debugging whatsoever
+#if 01 // set to 1 for no debugging whatsoever
const bool gShowDebugf = false; // FIXME: remove once debugging is complete
#define DEBUG_DUMP 0
#define DEBUG_ADD 0
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_BOTTOM_TS 0
-#define COMPARE_DOUBLE 0
#define DEBUG_ABOVE_BELOW 0
#define DEBUG_ACTIVE_LESS_THAN 0
#define DEBUG_SORT_HORIZONTAL 0
@@ -38,9 +38,8 @@ const bool gShowDebugf = true; // FIXME: remove once debugging is complete
#define DEBUG_ADD 01
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_BOTTOM_TS 0
-#define COMPARE_DOUBLE 0
#define DEBUG_ABOVE_BELOW 01
-#define DEBUG_ACTIVE_LESS_THAN 01
+#define DEBUG_ACTIVE_LESS_THAN 0
#define DEBUG_SORT_HORIZONTAL 01
#define DEBUG_OUT 01
#define DEBUG_OUT_LESS_THAN 0
@@ -49,57 +48,101 @@ const bool gShowDebugf = true; // FIXME: remove once debugging is complete
#endif
-// FIXME: not wild about this -- for SkScalars backed by floats, would like to
-// represent deltas in terms of number of significant matching bits
-#define MIN_PT_DELTA 0.000001
-
static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
- double aRange[2], double bRange[2]) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
- _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
- return intersect(aLine, bLine, aRange, bRange);
+ Intersections& intersections) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
+}
+
+static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
+ Intersections& intersections) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ return intersect(aQuad, bLine, intersections);
+}
+
+static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
+ 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}};
+ const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ intersections.fUsed = intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
+ return intersections.fUsed;
+}
+
+static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
+ Intersections& intersections) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
+ return intersect(aQuad, bQuad, intersections);
+}
+
+static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
+ 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}};
+ const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY},
+ {b[3].fX, b[3].fY}};
+ return intersect(aCubic, bCubic, intersections);
}
static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
SkScalar y, double aRange[2]) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
return horizontalLineIntersect(aLine, left, right, y, aRange);
}
static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
double x, y;
- xy_at_t(aLine, t, x, y);
+ xy_at_t(line, t, x, y);
out->fX = SkDoubleToScalar(x);
out->fY = SkDoubleToScalar(y);
}
-#if COMPARE_DOUBLE
-static void LineXYAtT(const SkPoint a[2], double t, _Point* out) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
- xy_at_t(aLine, t, out->x, out->y);
+static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
+ const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ double x, y;
+ xy_at_t(quad, t, x, y);
+ out->fX = SkDoubleToScalar(x);
+ out->fY = SkDoubleToScalar(y);
}
-#endif
-#if 0 // unused for now
-static SkScalar LineXAtT(const SkPoint a[2], double t) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
- double x;
- xy_at_t(aLine, t, x, *(double*) 0);
- return SkDoubleToScalar(x);
+static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
+ 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, y;
+ xy_at_t(cubic, t, x, y);
+ out->fX = SkDoubleToScalar(x);
+ out->fY = SkDoubleToScalar(y);
}
-#endif
static SkScalar LineYAtT(const SkPoint a[2], double t) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
double y;
xy_at_t(aLine, t, *(double*) 0, y);
return SkDoubleToScalar(y);
}
+static SkScalar QuadYAtT(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 y;
+ xy_at_t(quad, t, *(double*) 0, y);
+ return SkDoubleToScalar(y);
+}
+
+static SkScalar CubicYAtT(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 y;
+ xy_at_t(cubic, t, *(double*) 0, y);
+ return SkDoubleToScalar(y);
+}
+
static void LineSubDivide(const SkPoint a[2], double startT, double endT,
SkPoint sub[2]) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
_Line dst;
sub_divide(aLine, startT, endT, dst);
sub[0].fX = SkDoubleToScalar(dst[0].x);
@@ -108,14 +151,35 @@ static void LineSubDivide(const SkPoint a[2], double startT, double endT,
sub[1].fY = SkDoubleToScalar(dst[1].y);
}
-#if COMPARE_DOUBLE
-static void LineSubDivide(const SkPoint a[2], double startT, double endT,
- _Line& dst) {
- _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
- sub_divide(aLine, startT, endT, dst);
+static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
+ SkPoint sub[3]) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ Quadratic dst;
+ sub_divide(aQuad, startT, endT, dst);
+ sub[0].fX = SkDoubleToScalar(dst[0].x);
+ sub[0].fY = SkDoubleToScalar(dst[0].y);
+ sub[1].fX = SkDoubleToScalar(dst[1].x);
+ sub[1].fY = SkDoubleToScalar(dst[1].y);
+ sub[2].fX = SkDoubleToScalar(dst[2].x);
+ sub[2].fY = SkDoubleToScalar(dst[2].y);
}
-#endif
+static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
+ SkPoint sub[4]) {
+ 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}};
+ Cubic dst;
+ sub_divide(aCubic, startT, endT, dst);
+ sub[0].fX = SkDoubleToScalar(dst[0].x);
+ sub[0].fY = SkDoubleToScalar(dst[0].y);
+ sub[1].fX = SkDoubleToScalar(dst[1].x);
+ sub[1].fY = SkDoubleToScalar(dst[1].y);
+ sub[2].fX = SkDoubleToScalar(dst[2].x);
+ sub[2].fY = SkDoubleToScalar(dst[2].y);
+ sub[3].fX = SkDoubleToScalar(dst[3].x);
+ sub[3].fY = SkDoubleToScalar(dst[3].y);
+}
+
/*
list of edges
bounds for edge
@@ -204,11 +268,11 @@ public:
: fFill(fill) {
}
- void addLine(const SkPoint line[2], int id, bool closeCall) {
+ void addCurve(const SkPoint line[4], SkPath::Verb verb, int id,
+ bool closeCall) {
OutEdge& newEdge = fEdges.push_back();
- newEdge.fPts[0] = line[0];
- newEdge.fPts[1] = line[1];
- newEdge.fVerb = SkPath::kLine_Verb;
+ memcpy(newEdge.fPts, line, (verb + 1) * sizeof(SkPoint));
+ newEdge.fVerb = verb;
newEdge.fID = id;
newEdge.fCloseCall = closeCall;
}
@@ -255,7 +319,8 @@ public:
break;
}
int closeEdgeIndex = -listIndex - 1;
- SkPoint firstPt, lastLine[2];
+ SkPoint firstPt, lastCurve[4];
+ uint8_t lastVerb;
bool doMove = true;
int edgeIndex;
do {
@@ -269,49 +334,80 @@ public:
start = &ptArray[0];
end = &ptArray[verb];
}
- switch (verb) {
- case SkPath::kLine_Verb:
- bool gap;
- if (doMove) {
- firstPt = *start;
- simple.moveTo(start->fX, start->fY);
- if (gShowDebugf) {
- SkDebugf("%s moveTo (%g,%g)\n", __FUNCTION__,
- start->fX, start->fY);
- }
- lastLine[0] = *start;
- lastLine[1] = *end;
- doMove = false;
- break;
+ if (doMove) {
+ firstPt = *start;
+ simple.moveTo(start->fX, start->fY);
+ if (gShowDebugf) {
+ SkDebugf("%s moveTo (%g,%g)\n", __FUNCTION__,
+ start->fX, start->fY);
+ }
+ lastCurve[0] = *start;
+ if (verb == SkPath::kQuad_Verb) {
+ lastCurve[1] = ptArray[1];
+ } else if (verb == SkPath::kCubic_Verb) {
+ if (advance < 0) {
+ lastCurve[1] = ptArray[2];
+ lastCurve[2] = ptArray[1];
+ } else {
+ lastCurve[1] = ptArray[1];
+ lastCurve[2] = ptArray[2];
}
- gap = lastLine[1] != *start;
- if (gap) {
- // FIXME: see comment in bridge -- this probably
- // conceals errors
- SkASSERT(fFill && UlpsDiff(lastLine[1].fY, start->fY) <= 10);
- simple.lineTo(lastLine[1].fX, lastLine[1].fY);
- if (gShowDebugf) {
- SkDebugf("%s lineTo x (%g,%g)\n", __FUNCTION__,
- lastLine[1].fX, lastLine[1].fY);
- }
+ }
+ lastCurve[verb] = *end;
+ lastVerb = verb;
+ doMove = false;
+ } else {
+ bool gap = lastCurve[verb] != *start;
+ if (gap) {
+ // FIXME: see comment in bridge -- this probably
+ // conceals errors
+ SkASSERT(fFill && UlpsDiff(lastCurve[lastVerb].fY, start->fY) <= 10);
+ switch (lastVerb) {
+ case SkPath::kLine_Verb:
+ simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);
+ break;
+ case SkPath::kQuad_Verb:
+ simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,
+ lastCurve[2].fX, lastCurve[2].fY);
+ break;
+ case SkPath::kCubic_Verb:
+ simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,
+ lastCurve[2].fX, lastCurve[2].fY,
+ lastCurve[3].fX, lastCurve[3].fY);
+ break;
}
- if (gap || !extendLine(lastLine, *end)) {
- // FIXME: see comment in bridge -- this probably
- // conceals errors
- SkASSERT(lastLine[1] == *start ||
- (fFill && UlpsDiff(lastLine[1].fY, start->fY) <= 10));
- simple.lineTo(start->fX, start->fY);
- if (gShowDebugf) {
- SkDebugf("%s lineTo (%g,%g)\n", __FUNCTION__,
- start->fX, start->fY);
- }
- lastLine[0] = *start;
+ if (gShowDebugf) {
+ const char* verbStr[] = {"", "line", "quad", "cubic"};
+ SkDebugf("%s %sTo-1 (%g,%g)\n", __FUNCTION__,
+ verbStr[lastVerb], lastCurve[lastVerb].fX,
+ lastCurve[lastVerb].fY);
}
- lastLine[1] = *end;
- break;
- default:
- // FIXME: add other curve types
- ;
+ }
+ if (gap || lastVerb != SkPath::kLine_Verb || !extendLine(lastCurve, *end)) {
+ // FIXME: see comment in bridge -- this probably
+ // conceals errors
+ SkASSERT(lastCurve[lastVerb] == *start ||
+ (fFill && UlpsDiff(lastCurve[lastVerb].fY, start->fY) <= 10));
+ simple.lineTo(start->fX, start->fY);
+ if (gShowDebugf) {
+ SkDebugf("%s lineTo (%g,%g)\n", __FUNCTION__,
+ start->fX, start->fY);
+ }
+ lastCurve[0] = *start;
+ }
+ if (verb == SkPath::kQuad_Verb) {
+ lastCurve[1] = ptArray[1];
+ } else if (verb == SkPath::kCubic_Verb) {
+ if (advance < 0) {
+ lastCurve[1] = ptArray[2];
+ lastCurve[2] = ptArray[1];
+ } else {
+ lastCurve[1] = ptArray[1];
+ lastCurve[2] = ptArray[2];
+ }
+ }
+ lastCurve[verb] = *end;
+ lastVerb = verb;
}
if (advance < 0) {
edgeIndex = fTops[listIndex];
@@ -329,11 +425,26 @@ public:
}
}
if (edgeIndex == closeEdgeIndex || edgeIndex == 0) {
- if (lastLine[1] != firstPt) {
- simple.lineTo(lastLine[1].fX, lastLine[1].fY);
+ if (lastCurve[lastVerb] != firstPt) {
+ switch (lastVerb) {
+ case SkPath::kLine_Verb:
+ simple.lineTo(lastCurve[1].fX, lastCurve[1].fY);
+ break;
+ case SkPath::kQuad_Verb:
+ simple.quadTo(lastCurve[1].fX, lastCurve[1].fY,
+ lastCurve[2].fX, lastCurve[2].fY);
+ break;
+ case SkPath::kCubic_Verb:
+ simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY,
+ lastCurve[2].fX, lastCurve[2].fY,
+ lastCurve[3].fX, lastCurve[3].fY);
+ break;
+ }
if (gShowDebugf) {
- SkDebugf("%s lineTo last (%g, %g)\n", __FUNCTION__,
- lastLine[1].fX, lastLine[1].fY);
+ const char* verbStr[] = {"", "line", "quad", "cubic"};
+ SkDebugf("%s %sTo last (%g, %g)\n", __FUNCTION__,
+ verbStr[lastVerb],
+ lastCurve[lastVerb].fX, lastCurve[lastVerb].fY);
}
}
simple.lineTo(firstPt.fX, firstPt.fY);
@@ -525,13 +636,24 @@ public:
}
#if DEBUG_DUMP
- // FIXME: pass current verb as parameter
- void dump(const SkPoint* pts) {
+ void dump(const SkPoint* pts, SkPath::Verb verb) {
const char className[] = "Intercepts";
const int tab = 8;
for (int i = 0; i < fTs.count(); ++i) {
SkPoint out;
- LineXYAtT(pts, fTs[i], &out);
+ switch (verb) {
+ case SkPath::kLine_Verb:
+ LineXYAtT(pts, fTs[i], &out);
+ break;
+ case SkPath::kQuad_Verb:
+ QuadXYAtT(pts, fTs[i], &out);
+ break;
+ case SkPath::kCubic_Verb:
+ CubicXYAtT(pts, fTs[i], &out);
+ break;
+ default:
+ SkASSERT(0);
+ }
SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className),
className, i, fTs[i], out.fX, out.fY);
}
@@ -682,7 +804,7 @@ struct InEdge {
SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className),
className, i);
// FIXME: take current verb into consideration
- fIntercepts[i].dump(pts);
+ fIntercepts[i].dump(pts, (SkPath::Verb) *verbs);
pts += *verbs++;
}
for (i = 0; i < fPts.count(); ++i) {
@@ -939,12 +1061,6 @@ public:
UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX),
(fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)));
#endif
- #if COMPARE_DOUBLE
- SkASSERT(((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX)
- < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX))
- == ((check.fY - fDAbove.y) * (fDBelow.x - fDAbove.x)
- < (fDBelow.y - fDAbove.y) * (check.fX - fDAbove.x)));
- #endif
return (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX)
< (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX);
}
@@ -963,12 +1079,6 @@ public:
(check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)),
UlpsDiff(fBelow.fX, rh.fBelow.fX), UlpsDiff(fBelow.fY, rh.fBelow.fY));
#endif
- #if COMPARE_DOUBLE
- SkASSERT(((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX)
- < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX))
- == ((rh.fDBelow.y - rh.fDAbove.y) * (check.fX - rh.fDAbove.x)
- < (check.fY - rh.fDAbove.y) * (rh.fDBelow.x - rh.fDAbove.x)));
- #endif
return (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX)
< (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX);
}
@@ -1059,46 +1169,49 @@ public:
}
void calcLeft() {
+ void (*xyAtTFunc)(const SkPoint a[], double t, SkPoint* out);
switch (fWorkEdge.verb()) {
- case SkPath::kLine_Verb: {
- // OPTIMIZATION: if fXAbove, fXBelow have already been computed
- // for the fTIndex, don't do it again
- // For identical x, this lets us know which edge is first.
- // If both edges have T values < 1, check x at next T (fXBelow).
- int add = (fTIndex <= fTs->count()) - 1;
- double tAbove = t(fTIndex + add);
- // OPTIMIZATION: may not need Y
- LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove);
- double tBelow = t(fTIndex - ~add);
- LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow);
- SkASSERT(tAbove != tBelow);
- while (fAbove.fY == fBelow.fY) {
- if (add < 0) {
- add -= 1;
- SkASSERT(fTIndex + add >= 0);
- tAbove = t(fTIndex + add);
- LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove);
- } else {
- add += 1;
- SkASSERT(fTIndex - ~add <= fTs->count() + 1);
- tBelow = t(fTIndex - ~add);
- LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow);
- }
- }
- #if COMPARE_DOUBLE
- LineXYAtT(fWorkEdge.fPts, tAbove, &fDAbove);
- LineXYAtT(fWorkEdge.fPts, tBelow, &fDBelow);
- #endif
- #if DEBUG_ABOVE_BELOW
- fTAbove = tAbove;
- fTBelow = tBelow;
- #endif
+ case SkPath::kLine_Verb:
+ xyAtTFunc = LineXYAtT;
+ break;
+ case SkPath::kQuad_Verb:
+ xyAtTFunc = QuadXYAtT;
+ break;
+ case SkPath::kCubic_Verb:
+ xyAtTFunc = CubicXYAtT;
break;
- }
default:
- // FIXME: add support for all curve types
SkASSERT(0);
}
+ // OPTIMIZATION: if fXAbove, fXBelow have already been computed
+ // for the fTIndex, don't do it again
+ // For identical x, this lets us know which edge is first.
+ // If both edges have T values < 1, check x at next T (fXBelow).
+ int add = (fTIndex <= fTs->count()) - 1;
+ double tAbove = t(fTIndex + add);
+ (*xyAtTFunc)(fWorkEdge.fPts, tAbove, &fAbove);
+ double tBelow = t(fTIndex - ~add);
+ (*xyAtTFunc)(fWorkEdge.fPts, tBelow, &fBelow);
+ SkASSERT(tAbove != tBelow);
+ // FIXME: this can loop forever
+ // need a break if we hit the end
+ while (fAbove.fY == fBelow.fY) {
+ if (add < 0 || fTIndex == fTs->count()) {
+ add -= 1;
+ SkASSERT(fTIndex + add >= 0);
+ tAbove = t(fTIndex + add);
+ (*xyAtTFunc)(fWorkEdge.fPts, tAbove, &fAbove);
+ } else {
+ add += 1;
+ SkASSERT(fTIndex - ~add <= fTs->count() + 1);
+ tBelow = t(fTIndex - ~add);
+ (*xyAtTFunc)(fWorkEdge.fPts, tBelow, &fBelow);
+ }
+ }
+ #if DEBUG_ABOVE_BELOW
+ fTAbove = tAbove;
+ fTBelow = tBelow;
+ #endif
}
bool done(SkScalar bottom) const {
@@ -1107,7 +1220,19 @@ public:
void fixBelow() {
if (fFixBelow) {
- LineXYAtT(fWorkEdge.fPts, nextT(), &fBelow);
+ switch (fWorkEdge.verb()) {
+ case SkPath::kLine_Verb:
+ LineXYAtT(fWorkEdge.fPts, nextT(), &fBelow);
+ break;
+ case SkPath::kQuad_Verb:
+ QuadXYAtT(fWorkEdge.fPts, nextT(), &fBelow);
+ break;
+ case SkPath::kCubic_Verb:
+ CubicXYAtT(fWorkEdge.fPts, nextT(), &fBelow);
+ break;
+ default:
+ SkASSERT(0);
+ }
fFixBelow = false;
}
}
@@ -1136,17 +1261,9 @@ public:
// t values, since the same t values could exist intersecting non-coincident
// edges.
bool isCoincidentWith(const ActiveEdge* edge, SkScalar y) const {
-
-#if 0
- if (!fAbove.equalsWithinTolerance(edge->fAbove, MIN_PT_DELTA)
- || !fBelow.equalsWithinTolerance(edge->fBelow, MIN_PT_DELTA)) {
- return false;
- }
-#else
if (fAbove != edge->fAbove || fBelow != edge->fBelow) {
return false;
}
-#endif
uint8_t verb = fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb();
uint8_t edgeVerb = edge->fDone ? edge->fWorkEdge.lastVerb()
: edge->fWorkEdge.verb();
@@ -1298,10 +1415,6 @@ public:
const SkTDArray<double>* fTs;
SkPoint fAbove;
SkPoint fBelow;
-#if COMPARE_DOUBLE
- _Point fDAbove;
- _Point fDBelow;
-#endif
#if DEBUG_ABOVE_BELOW
double fTAbove;
double fTBelow;
@@ -1375,6 +1488,34 @@ static void addBottomT(InEdge** currentPtr, InEdge** lastPtr,
}
}
+static void debugShowLineIntersection(int pts, const WorkEdge& wt,
+ const WorkEdge& wn, const double wtTs[2], const double wnTs[2]) {
+#if DEBUG_ADD_INTERSECTING_TS
+ if (!pts) {
+ return;
+ }
+ SkPoint wtOutPt, wnOutPt;
+ LineXYAtT(wt.fPts, wtTs[0], &wtOutPt);
+ LineXYAtT(wn.fPts, wnTs[0], &wnOutPt);
+ SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n",
+ __FUNCTION__,
+ wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY,
+ wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY,
+ test->fID, next->fID);
+ if (pts == 2) {
+ SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
+ }
+ SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n",
+ __FUNCTION__,
+ wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY,
+ wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY,
+ test->fID, next->fID);
+ if (pts == 2) {
+ SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]);
+ }
+#endif
+}
+
static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) {
InEdge** testPtr = currentPtr - 1;
// FIXME: lastPtr should be past the point of interest, so
@@ -1395,39 +1536,75 @@ static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) {
wt.init(test);
wn.init(next);
do {
- if (wt.verb() == SkPath::kLine_Verb
- && wn.verb() == SkPath::kLine_Verb) {
- double wtTs[2], wnTs[2];
- int pts = LineIntersect(wt.fPts, wn.fPts, wtTs, wnTs);
- if (pts) {
-#if DEBUG_ADD_INTERSECTING_TS
- SkPoint wtOutPt, wnOutPt;
- LineXYAtT(wt.fPts, wtTs[0], &wtOutPt);
- LineXYAtT(wn.fPts, wnTs[0], &wnOutPt);
- SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n",
- __FUNCTION__,
- wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY,
- wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY,
- test->fID, next->fID);
- if (pts == 2) {
- SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
+ int pts;
+ Intersections ts;
+ bool swap = false;
+ switch (wt.verb()) {
+ case SkPath::kLine_Verb:
+ switch (wn.verb()) {
+ case SkPath::kLine_Verb: {
+ pts = LineIntersect(wt.fPts, wn.fPts, ts);
+ debugShowLineIntersection(pts, wt, wn,
+ ts.fT[0], ts.fT[1]);
+ break;
+ }
+ case SkPath::kQuad_Verb: {
+ swap = true;
+ pts = QuadLineIntersect(wn.fPts, wt.fPts, ts);
+ break;
+ }
+ case SkPath::kCubic_Verb: {
+ swap = true;
+ pts = CubicLineIntersect(wn.fPts, wt.fPts, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
}
- SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n",
- __FUNCTION__,
- wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY,
- wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY,
- test->fID, next->fID);
- if (pts == 2) {
- SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]);
+ break;
+ case SkPath::kQuad_Verb:
+ switch (wn.verb()) {
+ case SkPath::kLine_Verb: {
+ pts = QuadLineIntersect(wt.fPts, wn.fPts, ts);
+ break;
+ }
+ case SkPath::kQuad_Verb: {
+ pts = QuadIntersect(wt.fPts, wn.fPts, ts);
+ break;
+ }
+ case SkPath::kCubic_Verb: {
+ // FIXME: promote quad to cubic
+ pts = CubicIntersect(wt.fPts, wn.fPts, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
}
-#endif
- test->add(wtTs, pts, wt.verbIndex());
- next->add(wnTs, pts, wn.verbIndex());
- }
- } else {
- // FIXME: add all combinations of curve types
- SkASSERT(0);
+ break;
+ case SkPath::kCubic_Verb:
+ switch (wn.verb()) {
+ case SkPath::kLine_Verb: {
+ pts = CubicLineIntersect(wt.fPts, wn.fPts, ts);
+ break;
+ }
+ case SkPath::kQuad_Verb: {
+ // FIXME: promote quad to cubic
+ pts = CubicIntersect(wt.fPts, wn.fPts, ts);
+ break;
+ }
+ case SkPath::kCubic_Verb: {
+ pts = CubicIntersect(wt.fPts, wn.fPts, ts);
+ break;
+ }
+ default:
+ SkASSERT(0);
+ }
+ break;
+ default:
+ SkASSERT(0);
}
+ test->add(ts.fT[swap], pts, wt.verbIndex());
+ next->add(ts.fT[!swap], pts, wn.verbIndex());
} while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance());
} while (nextPtr != lastPtr);
}
@@ -1495,14 +1672,25 @@ static SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges,
const SkTDArray<double>& fTs = intercepts.fTs;
size_t count = fTs.count();
for (size_t index = 0; index < count; ++index) {
- if (wt.verb() == SkPath::kLine_Verb) {
- SkScalar yIntercept = LineYAtT(wt.fPts, fTs[index]);
- if (yIntercept > y && bottom > yIntercept) {
- bottom = yIntercept;
+ SkScalar yIntercept;
+ switch (wt.verb()) {
+ case SkPath::kLine_Verb: {
+ yIntercept = LineYAtT(wt.fPts, fTs[index]);
+ break;
}
- } else {
- // FIXME: add all curve types
- SkASSERT(0);
+ case SkPath::kQuad_Verb: {
+ yIntercept = QuadYAtT(wt.fPts, fTs[index]);
+ break;
+ }
+ case SkPath::kCubic_Verb: {
+ yIntercept = CubicYAtT(wt.fPts, fTs[index]);
+ break;
+ }
+ default:
+ SkASSERT(0); // should never get here
+ }
+ if (yIntercept > y && bottom > yIntercept) {
+ bottom = yIntercept;
}
}
} while (wt.advance());
@@ -1805,13 +1993,8 @@ static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y,
bool closer = (winding & windingMask) == 0;
SkASSERT(!opener | !closer);
bool inWinding = opener | closer;
- SkPoint clippedPts[2];
+ SkPoint clippedPts[4];
const SkPoint* clipped = NULL;
- #if COMPARE_DOUBLE
- _Line dPoints;
- _Line clippedDPts;
- const _Point* dClipped = NULL;
- #endif
uint8_t verb = wt.verb();
bool moreToDo, aboveBottom;
do {
@@ -1821,80 +2004,69 @@ static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y,
double nextT;
do {
nextT = activePtr->nextT();
- if (verb == SkPath::kLine_Verb) {
- // FIXME: obtuse: want efficient way to say
- // !currentT && currentT != 1 || !nextT && nextT != 1
- if (currentT * nextT != 0 || currentT + nextT != 1) {
- // OPTIMIZATION: if !inWinding, we only need
- // clipped[1].fY
- LineSubDivide(points, currentT, nextT, clippedPts);
- clipped = clippedPts;
- #if COMPARE_DOUBLE
- LineSubDivide(points, currentT, nextT, clippedDPts);
- dClipped = clippedDPts;
- #endif
- } else {
- clipped = points;
- #if COMPARE_DOUBLE
- dPoints[0].x = SkScalarToDouble(points[0].fX);
- dPoints[0].y = SkScalarToDouble(points[1].fY);
- dPoints[1].x = SkScalarToDouble(points[0].fX);
- dPoints[1].y = SkScalarToDouble(points[1].fY);
- dClipped = dPoints;
- #endif
- }
- if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY
- != clipped[1].fY : clipped[0] != clipped[1])) {
- if (gShowDebugf) {
- SkDebugf("%*s line %1.9g,%1.9g %1.9g,%1.9g edge=%d"
- " v=%d t=(%1.9g,%1.9g)\n", tab, "",
- clipped[0].fX, clipped[0].fY,
- clipped[1].fX, clipped[1].fY,
- activePtr->ID(),
- activePtr->fWorkEdge.fVerb
- - activePtr->fWorkEdge.fEdge->fVerbs.begin(),
- currentT, nextT);
- }
- outBuilder.addLine(clipped,
- activePtr->fWorkEdge.fEdge->fID,
- activePtr->fCloseCall);
- } else {
- if (gShowDebugf) {
- SkDebugf("%*s skip %1.9g,%1.9g %1.9g,%1.9g"
- " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "",
- clipped[0].fX, clipped[0].fY,
- clipped[1].fX, clipped[1].fY,
- activePtr->ID(),
- activePtr->fWorkEdge.fVerb
- - activePtr->fWorkEdge.fEdge->fVerbs.begin(),
- currentT, nextT);
- }
+ // FIXME: obtuse: want efficient way to say
+ // !currentT && currentT != 1 || !nextT && nextT != 1
+ if (currentT * nextT != 0 || currentT + nextT != 1) {
+ // OPTIMIZATION: if !inWinding, we only need
+ // clipped[1].fY
+ switch (verb) {
+ case SkPath::kLine_Verb:
+ LineSubDivide(points, currentT, nextT, clippedPts);
+ break;
+ case SkPath::kQuad_Verb:
+ QuadSubDivide(points, currentT, nextT, clippedPts);
+ break;
+ case SkPath::kCubic_Verb:
+ CubicSubDivide(points, currentT, nextT, clippedPts);
+ break;
+ default:
+ SkASSERT(0);
+ break;
}
- // by advancing fAbove/fBelow, the next call to sortHorizontal
- // will use these values if they're still valid instead of
- // recomputing
- #if COMPARE_DOUBLE
- SkASSERT((clipped[1].fY > activePtr->fBelow.fY
- && bottom >= activePtr->fBelow.fY)
- == (dClipped[1].y > activePtr->fDBelow.y
- && bottom >= activePtr->fDBelow.y));
- #endif
- if (clipped[1].fY > activePtr->fBelow.fY
- && bottom >= activePtr->fBelow.fY ) {
- activePtr->fAbove = activePtr->fBelow;
- activePtr->fBelow = clipped[1];
- #if COMPARE_DOUBLE
- activePtr->fDAbove = activePtr->fDBelow;
- activePtr->fDBelow = dClipped[1];
- #endif
- #if DEBUG_ABOVE_BELOW
- activePtr->fTAbove = activePtr->fTBelow;
- activePtr->fTBelow = nextT;
- #endif
+ clipped = clippedPts;
+ } else {
+ clipped = points;
+ }
+ if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY
+ != clipped[verb].fY : clipped[0] != clipped[verb])) {
+ if (gShowDebugf) {
+ const char* verbStr[] = {"", "Line", "Quad", "Cubic"};
+ SkDebugf("%*s add%s %1.9g,%1.9g %1.9g,%1.9g edge=%d"
+ " v=%d t=(%1.9g,%1.9g)\n", tab, "",
+ verbStr[verb], clipped[0].fX, clipped[0].fY,
+ clipped[verb].fX, clipped[verb].fY,
+ activePtr->ID(),
+ activePtr->fWorkEdge.fVerb
+ - activePtr->fWorkEdge.fEdge->fVerbs.begin(),
+ currentT, nextT);
}
+ outBuilder.addCurve(clipped, (SkPath::Verb) verb,
+ activePtr->fWorkEdge.fEdge->fID,
+ activePtr->fCloseCall);
} else {
- // FIXME: add all curve types
- SkASSERT(0);
+ if (gShowDebugf ) {
+ const char* verbStr[] = {"", "Line", "Quad", "Cubic"};
+ SkDebugf("%*s skip%s %1.9g,%1.9g %1.9g,%1.9g"
+ " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "",
+ verbStr[verb], clipped[0].fX, clipped[0].fY,
+ clipped[verb].fX, clipped[verb].fY,
+ activePtr->ID(),
+ activePtr->fWorkEdge.fVerb
+ - activePtr->fWorkEdge.fEdge->fVerbs.begin(),
+ currentT, nextT);
+ }
+ }
+ // by advancing fAbove/fBelow, the next call to sortHorizontal
+ // will use these values if they're still valid instead of
+ // recomputing
+ if (clipped[1].fY > activePtr->fBelow.fY
+ && bottom >= activePtr->fBelow.fY ) {
+ activePtr->fAbove = activePtr->fBelow;
+ activePtr->fBelow = clipped[1];
+ #if DEBUG_ABOVE_BELOW
+ activePtr->fTAbove = activePtr->fTBelow;
+ activePtr->fTBelow = nextT;
+ #endif
}
currentT = nextT;
moreToDo = activePtr->advanceT();
diff --git a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp
index 51f65348f1..7bf6452bee 100644
--- a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp
@@ -703,12 +703,6 @@ path.lineTo(497.278107, -113.884933);
path.lineTo(449.18222, -45.6723022);
path.lineTo(340.41568, -170.97171);
path.close();
-path.moveTo(301.372925, -213.590073);
-path.lineTo(348.294434, -271.975586);
-path.lineTo(395.215973, -330.361145);
-path.lineTo(400.890381, -263.276855);
-path.lineTo(301.372925, -213.590073);
-path.close();
path.moveTo(326.610535, 34.0393639);
path.lineTo(371.334595, -14.9620667);
path.lineTo(416.058624, -63.9634857);
@@ -765,7 +759,7 @@ static void (*simplifyTests[])() = {
static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]);
-static void (*firstTest)() = 0;
+static void (*firstTest)() = testSimplifySkinnyTriangle12;
void SimplifyPolygonPaths_Test() {
size_t index = 0;
diff --git a/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
new file mode 100644
index 0000000000..ab4e39b637
--- /dev/null
+++ b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
@@ -0,0 +1,64 @@
+#include "EdgeWalker_Test.h"
+#include "Intersection_Tests.h"
+
+static void testSimplifyQuadratic1() {
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.quadTo(0, 0, 0, 1);
+ path.close();
+ testSimplify(path, true, out);
+}
+
+static void testSimplifyQuadratic2() {
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(20, 0, 20, 20);
+ path.close();
+ path.moveTo(20, 0);
+ path.quadTo(0, 0, 0, 20);
+ path.close();
+ testSimplify(path, true, out);
+ drawAsciiPaths(path, out, true);
+}
+
+static void testSimplifyQuadratic3() {
+ SkPath path, out;
+ path.moveTo(0, 0);
+ path.quadTo(20, 0, 20, 20);
+ path.close();
+ path.moveTo(0, 20);
+ path.quadTo(0, 0, 20, 0);
+ path.close();
+ testSimplify(path, true, out);
+ drawAsciiPaths(path, out, true);
+}
+
+static void (*simplifyTests[])() = {
+ testSimplifyQuadratic3,
+ testSimplifyQuadratic2,
+ testSimplifyQuadratic1,
+};
+
+static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]);
+
+static void (*firstTest)() = 0;
+
+void SimplifyQuadraticPaths_Test() {
+ size_t index = 0;
+ if (firstTest) {
+ while (index < simplifyTestsCount && simplifyTests[index] != firstTest) {
+ ++index;
+ }
+ }
+ bool firstTestComplete = false;
+ for ( ; index < simplifyTestsCount; ++index) {
+ (*simplifyTests[index])();
+ if (simplifyTests[index] == testSimplifyQuadratic1) {
+ SkDebugf("%s last fast quad test\n", __FUNCTION__);
+ }
+ firstTestComplete = true;
+ }
+}
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index d905b88934..5209eee22f 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -19,10 +19,12 @@ void Intersection_Tests() {
LineQuadraticIntersection_Test();
LineCubicIntersection_Test();
+ SimplifyQuadraticPaths_Test();
+
SimplifyPolygonPaths_Test();
SimplifyRectangularPaths_Test();
SimplifyQuadralateralPaths_Test();
-
+
SimplifyDegenerate4x4TrianglesThreaded_Test();
SimplifyNondegenerate4x4TrianglesThreaded_Test();
Simplify4x4QuadralateralsThreaded_Test();
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index f1287e1a1f..432f83fcf0 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -16,6 +16,7 @@ void SimplifyDegenerate4x4TrianglesThreaded_Test();
void SimplifyNondegenerate4x4TrianglesThreaded_Test();
void SimplifyPolygonPaths_Test();
void SimplifyQuadralateralPaths_Test();
+void SimplifyQuadraticPaths_Test();
void Simplify4x4QuadralateralsThreaded_Test();
void SimplifyRectangularPaths_Test();
void QuadraticBezierClip_Test();
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index 928926ea67..47c413ac7b 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -1,3 +1,6 @@
+#ifndef Intersections_DEFINE
+#define Intersections_DEFINE
+
class Intersections {
public:
Intersections()
@@ -43,7 +46,10 @@ public:
}
double fT[2][9];
-private:
int fUsed;
+private:
int fSwap;
};
+
+#endif
+
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index bd2bff0fee..b2c91237f2 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -56,14 +56,17 @@ path.lineTo( 9.030045, -163.413132);
path.close();
</div>
<div id="test_4div">
-path.moveTo( -5503.40843,1749.49658);
-path.lineTo(-5503.40843,1749.49718);
+path.moveTo(340.41568, -170.97171);
+path.lineTo(418.846893, -142.428329);
+path.lineTo(497.278107, -113.884933);
+path.lineTo(449.18222, -45.6723022);
+path.lineTo(340.41568, -170.97171);
path.close();
-path.moveTo( -5503.40843,1749.49658);
-path.lineTo(-5503.40729,1749.50314);
-path.close();
-path.moveTo( -5503.40729,1749.50314);
-path.lineTo(-5503.40729,1749.50361);
+path.moveTo(326.610535, 34.0393639);
+path.lineTo(371.334595, -14.9620667);
+path.lineTo(416.058624, -63.9634857);
+path.lineTo(460.782654, -112.96492);
+path.lineTo(326.610535, 34.0393639);
path.close();
</div>
</div>
diff --git a/gyp/shapeops_demo.gyp b/gyp/shapeops_demo.gyp
index f004850846..f3a8b4207b 100644
--- a/gyp/shapeops_demo.gyp
+++ b/gyp/shapeops_demo.gyp
@@ -12,13 +12,43 @@
'../experimental/SimpleCocoaApp', # needed to get SimpleApp.h
],
'sources': [
+ '../experimental/Intersection/ConvexHull.cpp',
+ '../experimental/Intersection/CubeRoot.cpp',
+ '../experimental/Intersection/CubicBezierClip.cpp',
+ '../experimental/Intersection/CubicIntersection.cpp',
+ '../experimental/Intersection/CubicReduceOrder.cpp',
+ '../experimental/Intersection/CubicSubDivide.cpp',
+ '../experimental/Intersection/CubicUtilities.cpp',
'../experimental/Intersection/DataTypes.cpp',
+ '../experimental/Intersection/EdgeDemo.cpp',
+ '../experimental/Intersection/EdgeDemoApp.mm',
'../experimental/Intersection/EdgeWalker.cpp',
'../experimental/Intersection/EdgeWalker_TestUtility.cpp',
+ '../experimental/Intersection/Extrema.cpp',
+ '../experimental/Intersection/LineCubicIntersection.cpp
'../experimental/Intersection/LineIntersection.cpp',
'../experimental/Intersection/LineParameterization.cpp',
+ '../experimental/Intersection/LineQuadraticIntersection.cpp',
'../experimental/Intersection/LineUtilities.cpp',
- '../experimental/Intersection/EdgeDemoApp.mm',
+ '../experimental/Intersection/QuadraticBezierClip.cpp',
+ '../experimental/Intersection/QuadraticIntersection.cpp',
+ '../experimental/Intersection/QuadraticReduceOrder.cpp',
+ '../experimental/Intersection/QuadraticSubDivide.cpp',
+ '../experimental/Intersection/QuadraticUtilities.cpp',
+ '../experimental/Intersection/CubicIntersection.h',
+ '../experimental/Intersection/CubicUtilities.h',
+ '../experimental/Intersection/CurveIntersection.h',
+ '../experimental/Intersection/DataTypes.h',
+ '../experimental/Intersection/EdgeDemo.h',
+ '../experimental/Intersection/Extrema.h',
+ '../experimental/Intersection/Intersections.h',
+ '../experimental/Intersection/IntersectionUtilities.h',
+ '../experimental/Intersection/LineIntersection.h',
+ '../experimental/Intersection/LineParameters.h',
+ '../experimental/Intersection/LineUtilities.h',
+ '../experimental/Intersection/QuadraticUtilities.h',
+ '../experimental/Intersection/ShapeOps.h',
+ '../experimental/Intersection/TSearch.h',
],
'dependencies': [
'core.gyp:core',
@@ -44,16 +74,16 @@
'sources': [
# Mac files
- '../src/utils/mac/SkEventNotifier.h',
- '../src/utils/mac/SkEventNotifier.mm',
- '../src/utils/mac/skia_mac.mm',
- '../src/utils/mac/SkNSView.h',
- '../src/utils/mac/SkNSView.mm',
- '../src/utils/mac/SkOptionsTableView.h',
- '../src/utils/mac/SkOptionsTableView.mm',
- '../src/utils/mac/SkOSWindow_Mac.mm',
- '../src/utils/mac/SkTextFieldCell.h',
- '../src/utils/mac/SkTextFieldCell.m',
+ '../src/views/mac/SkEventNotifier.h',
+ '../src/views/mac/SkEventNotifier.mm',
+ '../src/views/mac/skia_mac.mm',
+ '../src/views/mac/SkNSView.h',
+ '../src/views/mac/SkNSView.mm',
+ '../src/views/mac/SkOptionsTableView.h',
+ '../src/views/mac/SkOptionsTableView.mm',
+ '../src/views/mac/SkOSWindow_Mac.mm',
+ '../src/views/mac/SkTextFieldCell.h',
+ '../src/views/mac/SkTextFieldCell.m',
],
'libraries': [
'$(SDKROOT)/System/Library/Frameworks/QuartzCore.framework',
diff --git a/gyp/shapeops_edge.gyp b/gyp/shapeops_edge.gyp
index 58f5052a85..b5c9d16a3d 100644
--- a/gyp/shapeops_edge.gyp
+++ b/gyp/shapeops_edge.gyp
@@ -38,6 +38,7 @@
'../experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp',
'../experimental/Intersection/EdgeWalkerPolygons_Test.cpp',
'../experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp',
+ '../experimental/Intersection/EdgeWalkerQuadratics_Test.cpp',
'../experimental/Intersection/EdgeWalkerRectangles_Test.cpp',
'../experimental/Intersection/Extrema.cpp',
'../experimental/Intersection/Inline_Tests.cpp',
@@ -65,6 +66,27 @@
'../experimental/Intersection/QuadraticUtilities.cpp',
'../experimental/Intersection/RectUtilities.cpp',
'../experimental/Intersection/TestUtilities.cpp',
+ '../experimental/Intersection/CubicIntersection.h',
+ '../experimental/Intersection/CubicIntersection_TestData.h',
+ '../experimental/Intersection/CubicUtilities.h',
+ '../experimental/Intersection/CurveIntersection.h',
+ '../experimental/Intersection/DataTypes.h',
+ '../experimental/Intersection/EdgeMain.h',
+ '../experimental/Intersection/EdgeWalker_Test.h',
+ '../experimental/Intersection/EdgeWalkerPolygons_Mismatches.h',
+ '../experimental/Intersection/Extrema.h',
+ '../experimental/Intersection/Intersection_Tests.h',
+ '../experimental/Intersection/Intersections.h',
+ '../experimental/Intersection/IntersectionUtilities.h',
+ '../experimental/Intersection/LineIntersection.h',
+ '../experimental/Intersection/LineParameters.h',
+ '../experimental/Intersection/LineUtilities.h',
+ '../experimental/Intersection/Parameterization_Test.h',
+ '../experimental/Intersection/QuadraticIntersection_TestData.h',
+ '../experimental/Intersection/QuadraticUtilities.h',
+ '../experimental/Intersection/ShapeOps.h',
+ '../experimental/Intersection/TestUtilities.h',
+ '../experimental/Intersection/TSearch.h',
],
'dependencies': [
'core.gyp:core',