diff options
19 files changed, 388 insertions, 204 deletions
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp index 833ac273b0..bf8ea468c3 100644 --- a/experimental/Intersection/CubicIntersection.cpp +++ b/experimental/Intersection/CubicIntersection.cpp @@ -14,7 +14,7 @@ #include "QuadraticUtilities.h" #if ONE_OFF_DEBUG -static const double tLimits[2][2] = {{0.599274754, 0.599275135}, {0.599274754, 0.599275135}}; +static const double tLimits[2][2] = {{0.772784538, 0.77278492}, {0.999111748, 0.999112129}}; #endif #define DEBUG_QUAD_PART 0 @@ -74,7 +74,7 @@ static double distanceFromEnd(double t) { static void bumpForRetry(double t1, double t2, double& s1, double& e1, double& s2, double& e2) { double dt1 = distanceFromEnd(t1); double dt2 = distanceFromEnd(t2); - double delta = 1.0 / precisionUnit; + double delta = 1.0 / gPrecisionUnit; if (dt1 < dt2) { if (t1 == dt1) { s1 = SkTMax(s1 - delta, 0.); @@ -277,60 +277,6 @@ static bool intersect2(const Cubic& cubic1, double t1s, double t1e, const Cubic& return i.intersected(); } -static bool intersectEnd(const Cubic& cubic1, bool start, const Cubic& cubic2, const _Rect& bounds2, - Intersections& i) { - _Line line1; - line1[1] = cubic1[start ? 0 : 3]; - if (line1[1].approximatelyEqual(cubic2[0]) || line1[1].approximatelyEqual(cubic2[3])) { - return false; - } - line1[0] = line1[1]; - _Point dxy1 = line1[0] - cubic1[start ? 1 : 2]; - if (dxy1.approximatelyZero()) { - dxy1 = line1[0] - cubic1[start ? 2 : 1]; - } - dxy1 /= precisionUnit; - line1[1] += dxy1; - _Rect line1Bounds; - line1Bounds.setBounds(line1); - if (!bounds2.intersects(line1Bounds)) { - return false; - } - _Line line2; - line2[0] = line2[1] = line1[0]; - _Point dxy2 = line2[0] - cubic1[start ? 3 : 0]; - SkASSERT(!dxy2.approximatelyZero()); - dxy2 /= precisionUnit; - line2[1] += dxy2; -#if 0 // this is so close to the first bounds test it isn't worth the short circuit test - _Rect line2Bounds; - line2Bounds.setBounds(line2); - if (!bounds2.intersects(line2Bounds)) { - return false; - } -#endif - Intersections local1; - if (!intersect(cubic2, line1, local1)) { - return false; - } - Intersections local2; - if (!intersect(cubic2, line2, local2)) { - return false; - } - double tMin, tMax; - tMin = tMax = local1.fT[0][0]; - for (int index = 1; index < local1.fUsed; ++index) { - tMin = SkTMin(tMin, local1.fT[0][index]); - tMax = SkTMax(tMax, local1.fT[0][index]); - } - for (int index = 1; index < local2.fUsed; ++index) { - tMin = SkTMin(tMin, local2.fT[0][index]); - tMax = SkTMax(tMax, local2.fT[0][index]); - } - return intersect2(cubic1, start ? 0 : 1, start ? 1.0 / precisionUnit : 1 - 1.0 / precisionUnit, - cubic2, tMin, tMax, 1, i); -} - // this flavor centers potential intersections recursively. In contrast, '2' may inadvertently // chase intersections near quadratic ends, requiring odd hacks to find them. static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& cubic2, @@ -398,7 +344,11 @@ static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& } result = true; } else if (cubic1 != cubic2 || !approximately_equal(to1, to2)) { - i.insert(to1, to2, p1); + if (i.swapped()) { // FIXME: insert should respect swap + i.insert(to2, to1, p1); + } else { + i.insert(to1, to2, p1); + } result = true; } } else { @@ -422,8 +372,8 @@ static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& offset, i.depth()); } // try parallel measure - _Point d1 = dxdy_at_t(cubic1, to1); - _Point d2 = dxdy_at_t(cubic2, to2); + _Vector d1 = dxdy_at_t(cubic1, to1); + _Vector d2 = dxdy_at_t(cubic2, to2); double shallow = d1.cross(d2); #if 1 || ONE_OFF_DEBUG // not sure this is worth debugging if (!approximately_zero(shallow)) { @@ -447,6 +397,49 @@ static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& return result; } +// intersect the end of the cubic with the other. Try lines from the end to control and opposite +// end to determine range of t on opposite cubic. +static bool intersectEnd(const Cubic& cubic1, bool start, const Cubic& cubic2, const _Rect& bounds2, + Intersections& i) { + _Line line; + int t1Index = start ? 0 : 3; + line[0] = cubic1[t1Index]; + // don't bother if the two cubics are connnected + if (line[0].approximatelyEqual(cubic2[0]) || line[0].approximatelyEqual(cubic2[3])) { + return false; + } + double tMin = 1, tMax = 0; + for (int index = 0; index < 4; ++index) { + if (index == t1Index) { + continue; + } + _Vector dxy1 = cubic1[index] - line[0]; + dxy1 /= gPrecisionUnit; + line[1] = line[0] + dxy1; + _Rect lineBounds; + lineBounds.setBounds(line); + if (!bounds2.intersects(lineBounds)) { + continue; + } + Intersections local; + if (!intersect(cubic2, line, local)) { + continue; + } + for (int index = 0; index < local.fUsed; ++index) { + tMin = SkTMin(tMin, local.fT[0][index]); + tMax = SkTMax(tMax, local.fT[0][index]); + } + } + if (tMin > tMax) { + return false; + } + double tMin1 = start ? 0 : 1 - 1.0 / gPrecisionUnit; + double tMax1 = start ? 1.0 / gPrecisionUnit : 1; + double tMin2 = SkTMax(tMin - 1.0 / gPrecisionUnit, 0.0); + double tMax2 = SkTMin(tMax + 1.0 / gPrecisionUnit, 1.0); + return intersect3(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i); +} + // FIXME: add intersection of convex hull on cubics' ends with the opposite cubic. The hull line // segments can be constructed to be only as long as the calculated precision suggests. If the hull // line segments intersect the cubic, then use the intersections to construct a subdivision for diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp index 53d33cf504..e45d543173 100644 --- a/experimental/Intersection/CubicIntersection_Test.cpp +++ b/experimental/Intersection/CubicIntersection_Test.cpp @@ -134,6 +134,9 @@ static const Cubic testSet[] = { const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]); static const Cubic newTestSet[] = { +{{0,1}, {2,5}, {6,0}, {5,3}}, +{{0,6}, {3,5}, {1,0}, {5,2}}, + {{0,1}, {3,6}, {1,0}, {5,2}}, {{0,1}, {2,5}, {1,0}, {6,3}}, @@ -553,10 +556,10 @@ void CubicIntersection_IntersectionFinder() { const Cubic& cubic1 = newTestSet[0]; const Cubic& cubic2 = newTestSet[1]; - double t1Seed = 0.633; - double t2Seed = 0.633; + double t1Seed = 0.77; + double t2Seed = 0.99; double t1Step = 0.1; - double t2Step = 0.1; + double t2Step = 0.01; _Point t1[3], t2[3]; bool toggle = true; do { diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp index 11d4e6cdb3..b27accf314 100644 --- a/experimental/Intersection/CubicUtilities.cpp +++ b/experimental/Intersection/CubicUtilities.cpp @@ -8,7 +8,7 @@ #include "Extrema.h" #include "QuadraticUtilities.h" -const int precisionUnit = 256; // FIXME: arbitrary -- should try different values in test framework +const int gPrecisionUnit = 256; // FIXME: arbitrary -- should try different values in test framework // FIXME: cache keep the bounds and/or precision with the caller? double calcPrecision(const Cubic& cubic) { @@ -16,7 +16,7 @@ double calcPrecision(const Cubic& cubic) { dRect.setBounds(cubic); // OPTIMIZATION: just use setRawBounds ? double width = dRect.right - dRect.left; double height = dRect.bottom - dRect.top; - return (width > height ? width : height) / precisionUnit; + return (width > height ? width : height) / gPrecisionUnit; } #if SK_DEBUG @@ -236,13 +236,8 @@ double dy_at_t(const Cubic& cubic, double t) { } // OPTIMIZE? compute t^2, t(1-t), and (1-t)^2 and pass them to another version of derivative at t? -void dxdy_at_t(const Cubic& cubic, double t, _Point& dxdy) { - dxdy.x = derivativeAtT(&cubic[0].x, t); - dxdy.y = derivativeAtT(&cubic[0].y, t); -} - -_Point dxdy_at_t(const Cubic& cubic, double t) { - _Point result = { derivativeAtT(&cubic[0].x, t), derivativeAtT(&cubic[0].y, t) }; +_Vector dxdy_at_t(const Cubic& cubic, double t) { + _Vector result = { derivativeAtT(&cubic[0].x, t), derivativeAtT(&cubic[0].y, t) }; return result; } @@ -306,6 +301,17 @@ _Point top(const Cubic& cubic, double startT, double endT) { return topPt; } +// OPTIMIZE: avoid computing the unused half +void xy_at_t(const Cubic& cubic, double t, double& x, double& y) { + _Point xy = xy_at_t(cubic, t); + if (&x) { + x = xy.x; + } + if (&y) { + y = xy.y; + } +} + _Point xy_at_t(const Cubic& cubic, double t) { double one_t = 1 - t; double one_t2 = one_t * one_t; @@ -319,13 +325,3 @@ _Point xy_at_t(const Cubic& cubic, double t) { return result; } - -void xy_at_t(const Cubic& cubic, double t, double& x, double& y) { - _Point xy = xy_at_t(cubic, t); - if (&x) { - x = xy.x; - } - if (&y) { - y = xy.y; - } -} diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h index 3f52a94621..646fb74aaf 100644 --- a/experimental/Intersection/CubicUtilities.h +++ b/experimental/Intersection/CubicUtilities.h @@ -25,8 +25,8 @@ int cubicRootsReal(double A, double B, double C, double D, double s[3]); void demote_cubic_to_quad(const Cubic& cubic, Quadratic& quad); double dx_at_t(const Cubic& , double t); double dy_at_t(const Cubic& , double t); -void dxdy_at_t(const Cubic& , double t, _Point& y); -_Point dxdy_at_t(const Cubic& cubic, double t); +//void dxdy_at_t(const Cubic& , double t, _Point& y); +_Vector dxdy_at_t(const Cubic& cubic, double t); int find_cubic_inflections(const Cubic& src, double tValues[]); bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath); void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst); @@ -35,6 +35,6 @@ _Point top(const Cubic& , double startT, double endT); void xy_at_t(const Cubic& , double t, double& x, double& y); _Point xy_at_t(const Cubic& , double t); -extern const int precisionUnit; +extern const int gPrecisionUnit; #endif diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp index b76731c65d..a4a3039cd5 100644 --- a/experimental/Intersection/DataTypes.cpp +++ b/experimental/Intersection/DataTypes.cpp @@ -16,6 +16,16 @@ const double SquaredEpsilon = PointEpsilon * PointEpsilon; const int UlpsEpsilon = 16; +_Vector operator-(const _Point& a, const _Point& b) { + _Vector v = {a.x - b.x, a.y - b.y}; + return v; +} + +_Point operator+(const _Point& a, const _Vector& b) { + _Point v = {a.x + b.x, a.y + b.y}; + return v; +} + // 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 3009c17ae0..4b682fff63 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -200,21 +200,20 @@ inline bool roughly_equal(double x, double y) { } #endif -struct _Point { +struct _Point; + +struct _Vector { double x; double y; - friend _Point operator-(const _Point& a, const _Point& b) { - _Point v = {a.x - b.x, a.y - b.y}; - return v; - } + friend _Point operator+(const _Point& a, const _Vector& b); - void operator+=(const _Point& v) { + void operator+=(const _Vector& v) { x += v.x; y += v.y; } - void operator-=(const _Point& v) { + void operator-=(const _Vector& v) { x -= v.x; y -= v.y; } @@ -229,6 +228,44 @@ struct _Point { y *= s; } + double cross(const _Vector& a) const { + return x * a.y - y * a.x; + } + + double dot(const _Vector& a) const { + return x * a.x + y * a.y; + } + + double length() const { + return sqrt(lengthSquared()); + } + + double lengthSquared() const { + return x * x + y * y; + } + + SkVector asSkVector() const { + SkVector v = {SkDoubleToScalar(x), SkDoubleToScalar(y)}; + return v; + } +}; + +struct _Point { + double x; + double y; + + friend _Vector operator-(const _Point& a, const _Point& b); + + void operator+=(const _Vector& v) { + x += v.x; + y += v.y; + } + + void operator-=(const _Vector& v) { + x -= v.x; + y -= v.y; + } + friend bool operator==(const _Point& a, const _Point& b) { return a.x == b.x && a.y == b.y; } @@ -277,32 +314,16 @@ struct _Point { return pt; } - double cross(const _Point& a) const { - return x * a.y - y * a.x; - } - double distance(const _Point& a) const { - _Point temp = *this - a; + _Vector temp = *this - a; return temp.length(); } double distanceSquared(const _Point& a) const { - _Point temp = *this - a; + _Vector temp = *this - a; return temp.lengthSquared(); } - double dot(const _Point& a) const { - return x * a.x + y * a.y; - } - - double length() const { - return sqrt(lengthSquared()); - } - - double lengthSquared() const { - return x * x + y * y; - } - double roughlyEqual(const _Point& a) const { return roughly_equal(a.y, y) && roughly_equal(a.x, x); } diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h index 9a35a7db89..fc4c26c6e7 100644 --- a/experimental/Intersection/Intersections.h +++ b/experimental/Intersection/Intersections.h @@ -54,6 +54,7 @@ public: } } + // FIXME : does not respect swap int insert(double one, double two, const _Point& pt); // start if index == 0 : end if index == 1 diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp index 186fa9b412..53319c4560 100644 --- a/experimental/Intersection/LineUtilities.cpp +++ b/experimental/Intersection/LineUtilities.cpp @@ -59,8 +59,8 @@ void sub_divide(const _Line& line, double t1, double t2, _Line& dst) { // See: the January 2001 Algorithm on Area of Triangles // return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y)); double is_left(const _Line& line, const _Point& pt) { - _Point P0 = line[1] - line[0]; - _Point P2 = pt - line[0]; + _Vector P0 = line[1] - line[0]; + _Vector P2 = pt - line[0]; return P0.cross(P2); } diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp index a13e39b2c1..ed6244e4c4 100644 --- a/experimental/Intersection/QuadraticImplicit.cpp +++ b/experimental/Intersection/QuadraticImplicit.cpp @@ -130,12 +130,9 @@ static bool addIntercept(const Quadratic& q1, const Quadratic& q2, double tMin, xy_at_t(q2, tMid, mid.x, mid.y); _Line line; line[0] = line[1] = mid; - _Point dxdy; - dxdy_at_t(q2, tMid, dxdy); - line[0].x -= dxdy.x; - line[0].y -= dxdy.y; - line[1].x += dxdy.x; - line[1].y += dxdy.y; + _Vector dxdy = dxdy_at_t(q2, tMid); + line[0] -= dxdy; + line[1] += dxdy; Intersections rootTs; int roots = intersect(q1, line, rootTs); if (roots == 0) { @@ -186,7 +183,6 @@ static bool isLinearInner(const Quadratic& q1, double t1s, double t1e, const Qua return true; } double tMin, tMax; - _Point dxy1, dxy2; if (tCount == 1) { tMin = tMax = tsFound[0]; } else if (tCount > 1) { @@ -206,11 +202,12 @@ static bool isLinearInner(const Quadratic& q1, double t1s, double t1e, const Qua tMax = t2e; } int split = 0; + _Vector dxy1, dxy2; if (tMin != tMax || tCount > 2) { - dxdy_at_t(q2, tMin, dxy2); + dxy2 = dxdy_at_t(q2, tMin); for (int index = 1; index < tCount; ++index) { dxy1 = dxy2; - dxdy_at_t(q2, tsFound[index], dxy2); + dxy2 = dxdy_at_t(q2, tsFound[index]); double dot = dxy1.dot(dxy2); if (dot < 0) { split = index - 1; @@ -244,10 +241,8 @@ static bool isLinearInner(const Quadratic& q1, double t1s, double t1e, const Qua } static double flatMeasure(const Quadratic& q) { - _Point mid = q[1]; - mid -= q[0]; - _Point dxy = q[2]; - dxy -= q[0]; + _Vector mid = q[1] - q[0]; + _Vector dxy = q[2] - q[0]; double length = dxy.length(); // OPTIMIZE: get rid of sqrt return fabs(mid.cross(dxy) / length); } diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp index e9b7d90bcb..46cf20ab51 100644 --- a/experimental/Intersection/QuadraticIntersection_Test.cpp +++ b/experimental/Intersection/QuadraticIntersection_Test.cpp @@ -54,6 +54,9 @@ static void standardTestCases() { } static const Quadratic testSet[] = { + {{4.09011926,2.20971038}, {4.74608133,1.9335932}, {5.02469918,2.00694987}}, + {{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}}, + {{1.80814127,2.41537795}, {2.23475077,2.05922313}, {3.16529668,1.98358763}}, {{2.16505631,2.55782454}, {2.40541285,2.02193091}, {2.99836023,1.68247638}}, @@ -319,10 +322,10 @@ static void intersectionFinder(int test1, int test2) { const Quadratic& quad1 = testSet[test1]; const Quadratic& quad2 = testSet[test2]; - double t1Seed = 0.579; - double t2Seed = 0.469; + double t1Seed = 0.966; + double t2Seed = 0.99; double t1Step = 0.1; - double t2Step = 0.1; + double t2Step = 0.01; _Point t1[3], t2[3]; bool toggle = true; do { diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp index 7133e2e65e..cba722be7f 100644 --- a/experimental/Intersection/QuadraticUtilities.cpp +++ b/experimental/Intersection/QuadraticUtilities.cpp @@ -11,11 +11,11 @@ // from http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html double nearestT(const Quadratic& quad, const _Point& pt) { - _Point pos = quad[0] - pt; + _Vector pos = quad[0] - pt; // search points P of bezier curve with PM.(dP / dt) = 0 // a calculus leads to a 3d degree equation : - _Point A = quad[1] - quad[0]; - _Point B = quad[2] - quad[1]; + _Vector A = quad[1] - quad[0]; + _Vector B = quad[2] - quad[1]; B -= A; double a = B.dot(B); double b = 3 * A.dot(B); @@ -222,12 +222,13 @@ double dy_at_t(const Quadratic& quad, double t) { return derivativeAtT(&quad[0].y, t); } -void dxdy_at_t(const Quadratic& quad, double t, _Point& dxy) { +_Vector dxdy_at_t(const Quadratic& quad, double t) { double a = t - 1; double b = 1 - 2 * t; double c = t; - dxy.x = a * quad[0].x + b * quad[1].x + c * quad[2].x; - dxy.y = a * quad[0].y + b * quad[1].y + c * quad[2].y; + _Vector result = { a * quad[0].x + b * quad[1].x + c * quad[2].x, + a * quad[0].y + b * quad[1].y + c * quad[2].y }; + return result; } void xy_at_t(const Quadratic& quad, double t, double& x, double& y) { diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h index fe6bc68731..8ec9037e10 100644 --- a/experimental/Intersection/QuadraticUtilities.h +++ b/experimental/Intersection/QuadraticUtilities.h @@ -14,7 +14,9 @@ int add_valid_ts(double s[], int realRoots, double* t); void chop_at(const Quadratic& src, QuadraticPair& dst, double t); double dx_at_t(const Quadratic& , double t); double dy_at_t(const Quadratic& , double t); -void dxdy_at_t(const Quadratic& , double t, _Point& xy); +//void dxdy_at_t(const Quadratic& , double t, _Point& xy); +_Vector dxdy_at_t(const Quadratic& , double t); + double nearestT(const Quadratic& , const _Point& ); bool point_in_hull(const Quadratic& , const _Point& ); diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp index bc390c72ea..f1792a87eb 100644 --- a/experimental/Intersection/ShapeOps.cpp +++ b/experimental/Intersection/ShapeOps.cpp @@ -168,7 +168,7 @@ static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, Segment* next = current->findNextOp(chaseArray, nextStart, nextEnd, unsortable, op, xorMask, xorOpMask); if (!next) { - SkASSERT(!unsortable); + // SkASSERT(!unsortable); if (!unsortable && simple.hasMove() && current->verb() != SkPath::kLine_Verb && !simple.isClosed()) { diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index f4d8875794..ea4c9bf162 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -44,6 +44,7 @@ const bool gRunTestsInOneThread = false; #define DEBUG_ADD_INTERSECTING_TS 0 #define DEBUG_ADD_T_PAIR 0 #define DEBUG_ANGLE 0 +#define DEBUG_AS_C_CODE 1 #define DEBUG_ASSEMBLE 0 #define DEBUG_CONCIDENT 0 #define DEBUG_CROSS 0 @@ -68,6 +69,7 @@ const bool gRunTestsInOneThread = true; #define DEBUG_ADD_INTERSECTING_TS 1 #define DEBUG_ADD_T_PAIR 1 #define DEBUG_ANGLE 1 +#define DEBUG_AS_C_CODE 0 #define DEBUG_ASSEMBLE 1 #define DEBUG_CONCIDENT 1 #define DEBUG_CROSS 0 @@ -382,25 +384,23 @@ static SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = { CubicDYAtT }; -static SkPoint LineDXDYAtT(const SkPoint a[2], double ) { +static SkVector LineDXDYAtT(const SkPoint a[2], double ) { return a[1] - a[0]; } -static SkPoint QuadDXDYAtT(const SkPoint a[3], double t) { +static SkVector QuadDXDYAtT(const SkPoint a[3], double t) { MAKE_CONST_QUAD(quad, a); - _Point pt; - dxdy_at_t(quad, t, pt); - return pt.asSkPoint(); + _Vector v = dxdy_at_t(quad, t); + return v.asSkVector(); } -static SkPoint CubicDXDYAtT(const SkPoint a[4], double t) { +static SkVector CubicDXDYAtT(const SkPoint a[4], double t) { MAKE_CONST_CUBIC(cubic, a); - _Point pt; - dxdy_at_t(cubic, t, pt); - return pt.asSkPoint(); + _Vector v = dxdy_at_t(cubic, t); + return v.asSkVector(); } -static SkPoint (* const SegmentDXDYAtT[])(const SkPoint [], double ) = { +static SkVector (* const SegmentDXDYAtT[])(const SkPoint [], double ) = { NULL, LineDXDYAtT, QuadDXDYAtT, @@ -1646,7 +1646,7 @@ public: // resolve overlapping ts when considering coincidence later // add non-coincident intersection. Resulting edges are sorted in T. - int addT(double newT, Segment* other, const SkPoint& pt) { + int addT(Segment* other, const SkPoint& pt, double& newT) { // FIXME: in the pathological case where there is a ton of intercepts, // binary search? int insertedAt = -1; @@ -1692,8 +1692,11 @@ public: span->fUnsortableStart = false; span->fUnsortableEnd = false; int less = -1; - while (&span[less + 1] - fTs.begin() > 0 && !span[less].fDone - && xyAtT(&span[less]) == xyAtT(span)) { + while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) { +#if 1 + if (span[less].fDone) { + break; + } double tInterval = newT - span[less].fT; if (precisely_negative(tInterval)) { break; @@ -1719,11 +1722,34 @@ public: } } ++fDoneSpans; +#else + double tInterval = newT - span[less].fT; + if (precisely_negative(tInterval)) { + break; + } + if (fVerb == SkPath::kCubic_Verb) { + double tMid = newT - tInterval / 2; + _Point midPt; + CubicXYAtT(fPts, tMid, &midPt); + if (!midPt.approximatelyEqual(xyAtT(span))) { + break; + } + } + SkASSERT(span[less].fDone == span->fDone); + if (span[less].fT == 0) { + span->fT = newT = 0; + } else { + setSpanT(less, newT); + } +#endif --less; } int more = 1; - while (fTs.end() - &span[more - 1] > 1 && !span[more - 1].fDone - && xyAtT(&span[more]) == xyAtT(span)) { + while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) { +#if 1 + if (span[more - 1].fDone) { + break; + } double tEndInterval = span[more].fT - newT; if (precisely_negative(tEndInterval)) { break; @@ -1749,6 +1775,26 @@ public: } } ++fDoneSpans; +#else + double tEndInterval = span[more].fT - newT; + if (precisely_negative(tEndInterval)) { + break; + } + if (fVerb == SkPath::kCubic_Verb) { + double tMid = newT - tEndInterval / 2; + _Point midEndPt; + CubicXYAtT(fPts, tMid, &midEndPt); + if (!midEndPt.approximatelyEqual(xyAtT(span))) { + break; + } + } + SkASSERT(span[more - 1].fDone == span[more].fDone); + if (newT == 0) { + setSpanT(more, 0); + } else { + span->fT = newT = span[more].fT; + } +#endif ++more; } return insertedAt; @@ -1836,8 +1882,8 @@ public: } } - int addUnsortableT(double newT, Segment* other, bool start, const SkPoint& pt) { - int result = addT(newT, other, pt); + int addUnsortableT(Segment* other, bool start, const SkPoint& pt, double& newT) { + int result = addT(other, pt, newT); Span* span = &fTs[result]; if (start) { if (result > 0) { @@ -1961,8 +2007,8 @@ public: SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", __FUNCTION__, fID, t, other.fID, otherT); #endif - int insertedAt = addT(t, &other, pt); - int otherInsertedAt = other.addT(otherT, this, pt); + int insertedAt = addT(&other, pt, t); + int otherInsertedAt = other.addT(this, pt, otherT); addOtherT(insertedAt, otherT, otherInsertedAt); other.addOtherT(otherInsertedAt, t, insertedAt); matchWindingValue(insertedAt, t, borrowWind); @@ -2292,7 +2338,7 @@ public: return done(SkMin32(angle->start(), angle->end())); } - SkPoint dxdy(int index) const { + SkVector dxdy(int index) const { return (*SegmentDXDYAtT[fVerb])(fPts, fTs[index].fT); } @@ -2859,8 +2905,8 @@ public: bool bumpsUp = leftSegment->bumpsUp(tIndex, endIndex); SkPoint xyE = leftSegment->xyAtT(endIndex); SkPoint xyS = leftSegment->xyAtT(tIndex); - SkPoint dxyE = leftSegment->dxdy(endIndex); - SkPoint dxyS = leftSegment->dxdy(tIndex); + SkVector dxyE = leftSegment->dxdy(endIndex); + SkVector dxyS = leftSegment->dxdy(tIndex); double cross = dxyE.cross(dxyS); bool bumpCheck = bumpsUp && xyE.fY < xyS.fY && dxyE.fX < 0; #if DEBUG_SWAP_TOP @@ -3622,6 +3668,12 @@ the same winding is shared by both. void setOppXor(bool isOppXor) { fOppXor = isOppXor; } + + void setSpanT(int index, double t) { + Span& span = fTs[index]; + span.fT = t; + span.fOther->fTs[span.fOtherIndex].fOtherT = t; + } void setUpWinding(int index, int endIndex, int& maxWinding, int& sumWinding) { int deltaSum = spanSign(index, endIndex); @@ -4049,6 +4101,8 @@ the same winding is shared by both. double lastT = -1; #endif for (int i = 0; i < fTs.count(); ++i) { + SkASSERT(&fTs[i] == &fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOther-> + fTs[fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOtherIndex]); if (fTs[i].fDone) { continue; } @@ -4383,14 +4437,14 @@ public: return fSegments.count(); } - int addT(int segIndex, double newT, Contour* other, int otherIndex, const SkPoint& pt) { + int addT(int segIndex, Contour* other, int otherIndex, const SkPoint& pt, double& newT) { setContainsIntercepts(); - return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex], pt); + return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT); } - int addUnsortableT(int segIndex, double newT, Contour* other, int otherIndex, bool start, - const SkPoint& pt) { - return fSegments[segIndex].addUnsortableT(newT, &other->fSegments[otherIndex], start, pt); + int addUnsortableT(int segIndex, Contour* other, int otherIndex, bool start, + const SkPoint& pt, double& newT) { + return fSegments[segIndex].addUnsortableT(&other->fSegments[otherIndex], start, pt, newT); } const Bounds& bounds() const { @@ -4559,7 +4613,8 @@ public: double endT = coincidence.fTs[0][1]; bool cancelers; if ((cancelers = startT > endT)) { - SkTSwap<double>(startT, endT); + SkTSwap(startT, endT); + SkTSwap(coincidence.fPts[0], coincidence.fPts[1]); } SkASSERT(!approximately_negative(endT - startT)); double oStartT = coincidence.fTs[1][0]; @@ -5075,12 +5130,12 @@ 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, const SkPoint& pt) { - return fContour->addT(fIndex, newT, other.fContour, other.fIndex, pt); + int addT(const Work& other, const SkPoint& pt, double& newT) { + return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT); } - int addUnsortableT(double newT, const Work& other, bool start, const SkPoint& pt) { - return fContour->addUnsortableT(fIndex, newT, other.fContour, other.fIndex, start, pt); + int addUnsortableT(const Work& other, bool start, const SkPoint& pt, double& newT) { + return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, start, pt, newT); } bool advance() { @@ -5199,7 +5254,6 @@ protected: #if DEBUG_ADD_INTERSECTING_TS -#define DEBUG_AS_C_CODE 1 #if DEBUG_AS_C_CODE #define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}" #define QUAD_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}" @@ -5586,9 +5640,9 @@ static bool addIntersectTs(Contour* test, Contour* next) { // FIXME: if unsortable, the other points to the original. This logic is // untested downstream. SkPoint point = ts.fPt[pt].asSkPoint(); - int testTAt = wt.addUnsortableT(ts.fT[swap][pt], wt, start, point); + int testTAt = wt.addUnsortableT(wt, start, point, ts.fT[swap][pt]); wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt); - testTAt = wn.addUnsortableT(ts.fT[!swap][pt], wn, start ^ ts.fFlip, point); + testTAt = wn.addUnsortableT(wn, start ^ ts.fFlip, point, ts.fT[!swap][pt]); wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt); start ^= true; } @@ -5613,8 +5667,8 @@ static bool addIntersectTs(Contour* test, Contour* next) { SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); SkPoint point = ts.fPt[pt].asSkPoint(); - int testTAt = wt.addT(ts.fT[swap][pt], wn, point); - int nextTAt = wn.addT(ts.fT[!swap][pt], wt, point); + int testTAt = wt.addT(wn, point, ts.fT[swap][pt]); + int nextTAt = wn.addT(wt, point, ts.fT[!swap][pt]); wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt); wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt); } @@ -5640,8 +5694,8 @@ static void addSelfIntersectTs(Contour* test) { SkASSERT(ts.fT[0][0] >= 0 && ts.fT[0][0] <= 1); SkASSERT(ts.fT[1][0] >= 0 && ts.fT[1][0] <= 1); SkPoint point = ts.fPt[0].asSkPoint(); - int testTAt = wt.addT(ts.fT[0][0], wt, point); - int nextTAt = wt.addT(ts.fT[1][0], wt, point); + int testTAt = wt.addT(wt, point, ts.fT[0][0]); + int nextTAt = wt.addT(wt, point, ts.fT[1][0]); wt.addOtherT(testTAt, ts.fT[1][0], nextTAt); wt.addOtherT(nextTAt, ts.fT[0][0], testTAt); } while (wt.advance()); diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index 0d49bb91a5..ffba8dc6e4 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -4138,12 +4138,52 @@ static void cubicOp30d() { testShapeOp(path, pathB, kDifference_Op); } -static void (*firstTest)() = cubicOp30d; +static void cubicOp31d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,2); + path.cubicTo(0,3, 2,1, 4,0); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1,2); + pathB.cubicTo(0,4, 2,0, 3,0); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} + +static void cubicOp31u() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,2); + path.cubicTo(0,3, 2,1, 4,0); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1,2); + pathB.cubicTo(0,4, 2,0, 3,0); + pathB.close(); + testShapeOp(path, pathB, kUnion_Op); +} + +static void testCubic2() { + SkPath path; + path.moveTo(0,2); + path.cubicTo(0,3, 2,1, 4,0); + path.close(); + path.moveTo(1,2); + path.cubicTo(0,4, 2,0, 3,0); + path.close(); + testSimplifyx(path); +} + +static void (*firstTest)() = 0; static struct { void (*fun)(); const char* str; } tests[] = { + TEST(testCubic2), + TEST(cubicOp31u), + TEST(cubicOp31d), TEST(cubicOp30d), TEST(cubicOp29d), TEST(cubicOp28u), @@ -4551,7 +4591,7 @@ static void (*firstSubTest)() = 0; static bool skipAll = false; static bool runSubTestsFirst = false; -static bool runReverse = true; +static bool runReverse = false; static void (*stopTest)() = 0; void SimplifyNew_Test() { diff --git a/experimental/Intersection/TriangleUtilities.cpp b/experimental/Intersection/TriangleUtilities.cpp index 38915d4712..9889368079 100644 --- a/experimental/Intersection/TriangleUtilities.cpp +++ b/experimental/Intersection/TriangleUtilities.cpp @@ -10,9 +10,9 @@ // http://www.blackpawn.com/texts/pointinpoly/default.html bool pointInTriangle(const Triangle& triangle, const _Point& pt) { // Compute vectors - _Point v0 = triangle[2] - triangle[0]; - _Point v1 = triangle[1] - triangle[0]; - _Point v2 = pt - triangle[0]; + _Vector v0 = triangle[2] - triangle[0]; + _Vector v1 = triangle[1] - triangle[0]; + _Vector v2 = pt - triangle[0]; // Compute dot products double dot00 = v0.dot(v0); diff --git a/experimental/Intersection/as.htm b/experimental/Intersection/as.htm index b5487668b6..93845cbbc7 100644 --- a/experimental/Intersection/as.htm +++ b/experimental/Intersection/as.htm @@ -40,11 +40,33 @@ debugShowActiveSpans id=2 (3,2 0,1) t=0.0604518624 (2.81864452,1.93954813) tEnd= debugShowActiveSpans id=2 (3,2 0,1) t=0.400657994 (1.79802597,1.59934199) tEnd=1 other=3 otherT=0.57224743 otherIndex=2 windSum=? windValue=1 oppValue=0 </div> +<div id="cubicOp31d"> +debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0 (0,2) tEnd=0.5 other=2 otherT=1 otherIndex=3 windSum=1 windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0.5 (1.25,1.75) tEnd=1 other=4 otherT=0.875 otherIndex=2 windSum=1 windValue=1 oppValue=0 +debugShowActiveSpans id=2 (4,0 0,2) t=0 (4,0) tEnd=0.5 other=1 otherT=1 otherIndex=3 windSum=1 windValue=1 oppValue=0 +debugShowActiveSpans id=2 (4,0 0,2) t=0.586298186 (1.65480721,1.17259634) tEnd=1 other=3 otherT=0.622399169 otherIndex=3 windSum=1 windValue=1 oppValue=0 +debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0 (1,2) tEnd=0.5 other=4 otherT=1 otherIndex=4 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0.500000008 (1.25,1.75) tEnd=0.622399169 other=1 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0 +debugShowActiveSpans id=4 (3,0 1,2) t=0.5 (2,1) tEnd=0.875 other=2 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0 +debugShowActiveSpans id=4 (3,0 1,2) t=0.875 (1.25,1.75) tEnd=1 other=1 otherT=0.5 otherIndex=2 windSum=? windValue=1 oppValue=0 +</div> + +<div id="cubicOp31da"> +debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0 (0,2) tEnd=0.5 other=2 otherT=1 otherIndex=3 windSum=1 windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0.5 (1.25,1.75) tEnd=1 other=4 otherT=0.875 otherIndex=2 windSum=1 windValue=1 oppValue=0 +debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0 (1,2) tEnd=0.5 other=4 otherT=1 otherIndex=4 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0.500000008 (1.25,1.75) tEnd=0.622399169 other=1 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0 +debugShowActiveSpans id=4 (3,0 1,2) t=0.5 (2,1) tEnd=0.875 other=2 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0 +debugShowActiveSpans id=4 (3,0 1,2) t=0.875 (1.25,1.75) tEnd=1 other=1 otherT=0.5 otherIndex=2 windSum=? windValue=1 oppValue=0 +</div> + </div> <script type="text/javascript"> var testDivs = [ + cubicOp31da, + cubicOp31d, cubicOp28u, cubicOp25i, cubicOp19i, diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index 466551b388..199a9df076 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -3710,11 +3710,23 @@ path.addRect(4, 13, 13, 16, SkPath::kCCW_Direction); pathB.close(); </div> +<div id="cubicOp31d"> + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,2); + path.cubicTo(0,3, 2,1, 4,0); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1,2); + pathB.cubicTo(0,4, 2,0, 3,0); + pathB.close(); +</div> + </div> <script type="text/javascript"> var testDivs = [ + cubicOp31d, cubicOp30d, cubicOp29d, cubicOp28u, diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm index 1d9cfa589b..db77fa4d70 100644 --- a/experimental/Intersection/qc.htm +++ b/experimental/Intersection/qc.htm @@ -2065,11 +2065,34 @@ quad=(1.20573276,0.813456177 1.2679289,0.830085346 1.33333333,0.851851852) {{2.16505631,2.55782454}, {2.40541285,2.02193091}, {2.99836023,1.68247638}}, </div> +<div id="cubicOp30d"> +{{0,1}, {2,5}, {6,0}, {5,3}}, +{{0,6}, {3,5}, {1,0}, {5,2}}, + + {{0,1}, {0.585028897,2.1161006}, {1.31572211,2.42528354}}, + {{1.31572211,2.42528354}, {2.04641532,2.73446648}, {2.77656625,2.5918049}}, + {{2.77656625,2.5918049}, {3.50671719,2.44914333}, {4.09011926,2.20971038}}, + {{4.09011926,2.20971038}, {4.74608133,1.9335932}, {5.02469918,2.00694987}}, + {{5.02469918,2.00694987}, {5.30331702,2.08030653}, {5,3}}, + + {{0,6}, {0.946962644,5.64705935}, {1.35765232,4.89865813}}, + {{1.35765232,4.89865813}, {1.768342,4.1502569}, {1.97833659,3.34197296}}, + {{1.97833659,3.34197296}, {2.2269947,2.25886123}, {2.79472921,1.73568666}}, + {{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}}, +</div> + +<div id="quadOp30d"> + {{4.09011926,2.20971038}, {4.74608133,1.9335932}, {5.02469918,2.00694987}}, + {{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}}, +</div> + </div> <script type="text/javascript"> var testDivs = [ + quadOp30d, + cubicOp30d, quadOp27d, cubicOp27d, quadSelf1, @@ -2345,6 +2368,7 @@ var drawCubics = true; var drawQuads = true; var drawControlLines = true; var drawTangents = false; +var drawGrid = true; var xmin, xmax, ymin, ymax; function parse(test, title) { @@ -2448,35 +2472,38 @@ function draw(test, title, scale) { var unit = scale * ticks; ctx.lineWidth = 1; - var i; - for (i = 0; i <= rows * ticks; ++i) { - ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; - ctx.beginPath(); - ctx.moveTo(at_x + 0, at_y + i * minScale); - ctx.lineTo(at_x + ticks * columns * minScale, at_y + i * minScale); - ctx.stroke(); - } - for (i = 0; i <= columns * ticks; ++i) { - ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; - ctx.beginPath(); - ctx.moveTo(at_x + i * minScale, at_y + 0); - ctx.lineTo(at_x + i * minScale, at_y + ticks * rows * minScale); - ctx.stroke(); + if (drawGrid) { + var i; + for (i = 0; i <= rows * ticks; ++i) { + ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; + ctx.beginPath(); + ctx.moveTo(at_x + 0, at_y + i * minScale); + ctx.lineTo(at_x + ticks * columns * minScale, at_y + i * minScale); + ctx.stroke(); + } + for (i = 0; i <= columns * ticks; ++i) { + ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; + ctx.beginPath(); + ctx.moveTo(at_x + i * minScale, at_y + 0); + ctx.lineTo(at_x + i * minScale, at_y + ticks * rows * minScale); + ctx.stroke(); + } } - var xoffset = xStart * -unit + at_x; var yoffset = yStart * -unit + at_y; - ctx.fillStyle = "rgb(40,80,60)" - for (i = 0; i <= columns; i += 1) - { - num = xStart + i / subscale; - ctx.fillText(num.toFixed(decimal_places), xoffset + num * unit - 5, 10); - } - for (i = 0; i <= rows; i += 1) - { - num = yStart + i / subscale; - ctx.fillText(num.toFixed(decimal_places), 0, yoffset + num * unit + 0); + ctx.fillStyle = "rgb(40,80,60)" + if (drawGrid) { + for (i = 0; i <= columns; i += 1) + { + num = xStart + i / subscale; + ctx.fillText(num.toFixed(decimal_places), xoffset + num * unit - 5, 10); + } + for (i = 0; i <= rows; i += 1) + { + num = yStart + i / subscale; + ctx.fillText(num.toFixed(decimal_places), 0, yoffset + num * unit + 0); + } } var curves, pts; for (curves in test) { @@ -2609,6 +2636,10 @@ function doKeyPress(evt) { } redraw(); break; + case 'g': + drawGrid ^= true; + redraw(); + break; case 'l': drawControlLines ^= true; redraw(); |