From d0a19eb9140ecb968357f798f06d2b052b51fd89 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Tue, 19 Feb 2013 12:49:33 +0000 Subject: shape ops work in progress git-svn-id: http://skia.googlecode.com/svn/trunk@7766 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/CubicIntersection.cpp | 27 +++++++----------------- experimental/Intersection/QuadraticUtilities.cpp | 10 +++++++++ experimental/Intersection/QuadraticUtilities.h | 1 + experimental/Intersection/Simplify.cpp | 2 +- experimental/Intersection/SimplifyNew_Test.cpp | 16 +++++++++++++- experimental/Intersection/op.htm | 12 +++++++++++ 6 files changed, 47 insertions(+), 21 deletions(-) (limited to 'experimental/Intersection') diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp index d92c8bfe14..f4a7ef7859 100644 --- a/experimental/Intersection/CubicIntersection.cpp +++ b/experimental/Intersection/CubicIntersection.cpp @@ -11,6 +11,7 @@ #include "IntersectionUtilities.h" #include "LineIntersection.h" #include "LineUtilities.h" +#include "QuadraticUtilities.h" #if ONE_OFF_DEBUG static const double tLimits[2][2] = {{0.516980827, 0.516981209}, {0.647714088, 0.64771447}}; @@ -496,29 +497,17 @@ bool intersect3(const Cubic& c1, const Cubic& c2, Intersections& i) { return result; } +// Up promote the quad to a cubic. +// OPTIMIZATION If this is a common use case, optimize by duplicating +// the intersect 3 loop to avoid the promotion / demotion code int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& i) { - SkTDArray ts; - double precision = calcPrecision(cubic); - cubic_to_quadratics(cubic, precision, ts); - double tStart = 0; - Cubic part; - int tsCount = ts.count(); - for (int idx = 0; idx <= tsCount; ++idx) { - double t = idx < tsCount ? ts[idx] : 1; - Quadratic q1; - sub_divide(cubic, tStart, t, part); - demote_cubic_to_quad(part, q1); - Intersections locals; - intersect2(q1, quad, locals); - for (int tIdx = 0; tIdx < locals.used(); ++tIdx) { - double globalT = tStart + (t - tStart) * locals.fT[0][tIdx]; - i.insert(globalT, locals.fT[1][tIdx], locals.fPt[tIdx]); - } - tStart = t; - } + Cubic up; + toCubic(quad, up); + (void) intersect3(cubic, up, i); return i.used(); } +// FIXME: this needs to be recursive like intersect 3 bool intersect(const Cubic& cubic, Intersections& i) { SkTDArray ts; double precision = calcPrecision(cubic); diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp index fa8acea622..7133e2e65e 100644 --- a/experimental/Intersection/QuadraticUtilities.cpp +++ b/experimental/Intersection/QuadraticUtilities.cpp @@ -197,6 +197,16 @@ int quadraticRootsReal(const double A, const double B, const double C, double s[ #endif } +void toCubic(const Quadratic& quad, Cubic& cubic) { + cubic[0] = quad[0]; + cubic[2] = quad[1]; + cubic[3] = quad[2]; + cubic[1].x = (cubic[0].x + cubic[2].x * 2) / 3; + cubic[1].y = (cubic[0].y + cubic[2].y * 2) / 3; + cubic[2].x = (cubic[3].x + cubic[2].x * 2) / 3; + cubic[2].y = (cubic[3].y + cubic[2].y * 2) / 3; +} + static double derivativeAtT(const double* quad, double t) { double a = t - 1; double b = 1 - 2 * t; diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h index 8308f3878f..74ab80972d 100644 --- a/experimental/Intersection/QuadraticUtilities.h +++ b/experimental/Intersection/QuadraticUtilities.h @@ -36,6 +36,7 @@ inline void set_abc(const double* quad, double& a, double& b, double& c) { int quadraticRootsReal(double A, double B, double C, double t[2]); int quadraticRootsValidT(const double A, const double B, const double C, double s[2]); void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst); +void toCubic(const Quadratic& , Cubic& ); _Point top(const Quadratic& , double startT, double endT); void xy_at_t(const Quadratic& , double t, double& x, double& y); _Point xy_at_t(const Quadratic& , double t); diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index 5cfc3884d0..2c7103950f 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -2786,7 +2786,7 @@ public: // topmost tangent from y-min to first pt is closer to horizontal SkASSERT(!done()); int firstT = -1; - SkPoint topPt = activeLeftTop(onlySortable, &firstT); + /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT); SkASSERT(firstT >= 0); // sort the edges to find the leftmost int step = 1; diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index 4c83be7b6f..78b815ac89 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -3832,12 +3832,26 @@ static void cubicOp19i() { testShapeOp(path, pathB, kIntersect_Op); } -static void (*firstTest)() = cubicOp19i; +static void cubicOp20d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(0,1, 6,0, 2,1); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(1,2, 1,0, 1,0); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} + +static void (*firstTest)() = cubicOp20d; static struct { void (*fun)(); const char* str; } tests[] = { + TEST(cubicOp20d), TEST(cubicOp19i), TEST(cubicOp18d), TEST(cubicOp17d), diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index 6d45854767..9c2ce8e472 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -3589,11 +3589,23 @@ path.addRect(4, 13, 13, 16, SkPath::kCCW_Direction); pathB.close(); +
+ path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(0,1, 6,0, 2,1); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(1,2, 1,0, 1,0); + pathB.close(); +
+