path ops -- rewrite angle sort
This is a major change resulting from a minor
tweak. In the old code, the intersection point
of two curves was shared between them, but the
intersection points and end points of sorted edges was
computed directly from the intersection T value.
In this CL, both intersection points and sorted points
are the same, and intermediate control points are computed
to preserve their slope.
The sort itself has been completely rewritten to be more
robust and remove 'magic' checks, conditions that empirically
worked but couldn't be rationalized.
This CL was triggered by errors generated computing the clips
of SKP files. At this point, all 73M standard tests work and
at least the first troublesome SKPs work.
Review URL: https://codereview.chromium.org/15338003
git-svn-id: http://skia.googlecode.com/svn/trunk@9432 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 922c103..5106bbb 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -426,6 +426,35 @@
&& pt[0].approximatelyEqual(pt[1])) {
removeOne(used() - 2);
}
+ // vet the pairs of t values to see if the mid value is also on the curve. If so, mark
+ // the span as coincident
+ if (fUsed >= 2 && !coincidentUsed()) {
+ int last = fUsed - 1;
+ int match = 0;
+ for (int index = 0; index < last; ++index) {
+ double mid1 = (fT[0][index] + fT[0][index + 1]) / 2;
+ double mid2 = (fT[1][index] + fT[1][index + 1]) / 2;
+ pt[0] = c1.xyAtT(mid1);
+ pt[1] = c2.xyAtT(mid2);
+ if (pt[0].approximatelyEqual(pt[1])) {
+ match |= 1 << index;
+ }
+ }
+ if (match) {
+ if (((match + 1) & match) != 0) {
+ SkDebugf("%s coincident hole\n", __FUNCTION__);
+ }
+ // for now, assume that everything from start to finish is coincident
+ if (fUsed > 2) {
+ fPt[1] = fPt[last];
+ fT[0][1] = fT[0][last];
+ fT[1][1] = fT[1][last];
+ fIsCoincident[0] = 0x03;
+ fIsCoincident[1] = 0x03;
+ fUsed = 2;
+ }
+ }
+ }
return fUsed;
}
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index b1e1783..13c0dbb 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -34,6 +34,47 @@
return fUsed;
}
+int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
+ double axLen = a[1].fX - a[0].fX;
+ double ayLen = a[1].fY - a[0].fY;
+ double bxLen = b[1].fX - b[0].fX;
+ double byLen = b[1].fY - b[0].fY;
+ /* Slopes match when denom goes to zero:
+ axLen / ayLen == bxLen / byLen
+ (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
+ byLen * axLen == ayLen * bxLen
+ byLen * axLen - ayLen * bxLen == 0 ( == denom )
+ */
+ double denom = byLen * axLen - ayLen * bxLen;
+ double ab0y = a[0].fY - b[0].fY;
+ double ab0x = a[0].fX - b[0].fX;
+ double numerA = ab0y * bxLen - byLen * ab0x;
+ double numerB = ab0y * axLen - ayLen * ab0x;
+ numerA /= denom;
+ numerB /= denom;
+ int used;
+ if (!approximately_zero(denom)) {
+ fT[0][0] = numerA;
+ fT[1][0] = numerB;
+ used = 1;
+ } else {
+ /* See if the axis intercepts match:
+ ay - ax * ayLen / axLen == by - bx * ayLen / axLen
+ axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
+ axLen * ay - ax * ayLen == axLen * by - bx * ayLen
+ */
+ if (!AlmostEqualUlps(axLen * a[0].fY - ayLen * a[0].fX,
+ axLen * b[0].fY - ayLen * b[0].fX)) {
+ return fUsed = 0;
+ }
+ // there's no great answer for intersection points for coincident rays, but return something
+ fT[0][0] = fT[1][0] = 0;
+ fT[1][0] = fT[1][1] = 1;
+ used = 2;
+ }
+ return computePoints(a, used);
+}
+
/*
Determine the intersection point of two line segments
Return FALSE if the lines don't intersect
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index 5df08ac..b6a1761 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -19,12 +19,14 @@
* 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D(at^2+bt+c)+E(dt^2+et+f)+F
*/
-static int findRoots(const SkDQuadImplicit& i, const SkDQuad& q2, double roots[4],
- bool oneHint, int firstCubicRoot) {
+static int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots[4],
+ bool oneHint, bool flip, int firstCubicRoot) {
+ SkDQuad flipped;
+ const SkDQuad& q = flip ? (flipped = quad.flip()) : quad;
double a, b, c;
- SkDQuad::SetABC(&q2[0].fX, &a, &b, &c);
+ SkDQuad::SetABC(&q[0].fX, &a, &b, &c);
double d, e, f;
- SkDQuad::SetABC(&q2[0].fY, &d, &e, &f);
+ SkDQuad::SetABC(&q[0].fY, &d, &e, &f);
const double t4 = i.x2() * a * a
+ i.xy() * a * d
+ i.y2() * d * d;
@@ -48,10 +50,15 @@
+ i.y() * f
+ i.c();
int rootCount = SkReducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots);
- if (rootCount >= 0) {
- return rootCount;
+ if (rootCount < 0) {
+ rootCount = SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots);
}
- return SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots);
+ if (flip) {
+ for (int index = 0; index < rootCount; ++index) {
+ roots[index] = 1 - roots[index];
+ }
+ }
+ return rootCount;
}
static int addValidRoots(const double roots[4], const int count, double valid[4]) {
@@ -403,9 +410,11 @@
return fUsed;
}
int index;
- bool useCubic = q1[0] == q2[0] || q1[0] == q2[2] || q1[2] == q2[0];
+ bool flip1 = q1[2] == q2[0];
+ bool flip2 = q1[0] == q2[2];
+ bool useCubic = q1[0] == q2[0];
double roots1[4];
- int rootCount = findRoots(i2, q1, roots1, useCubic, 0);
+ int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
// OPTIMIZATION: could short circuit here if all roots are < 0 or > 1
double roots1Copy[4];
int r1Count = addValidRoots(roots1, rootCount, roots1Copy);
@@ -414,7 +423,7 @@
pts1[index] = q1.xyAtT(roots1Copy[index]);
}
double roots2[4];
- int rootCount2 = findRoots(i1, q2, roots2, useCubic, 0);
+ int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
double roots2Copy[4];
int r2Count = addValidRoots(roots2, rootCount2, roots2Copy);
SkDPoint pts2[4];
@@ -427,9 +436,9 @@
insert(roots1Copy[0], roots2Copy[0], pts1[0]);
} else if (pts1[0].moreRoughlyEqual(pts2[0])) {
// experiment: try to find intersection by chasing t
- rootCount = findRoots(i2, q1, roots1, useCubic, 0);
+ rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
(void) addValidRoots(roots1, rootCount, roots1Copy);
- rootCount2 = findRoots(i1, q2, roots2, useCubic, 0);
+ rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
(void) addValidRoots(roots2, rootCount2, roots2Copy);
if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) {
insert(roots1Copy[0], roots2Copy[0], pts1[0]);
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index 72f801b..ace8474 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -23,7 +23,7 @@
int SkIntersections::coincidentUsed() const {
if (!fIsCoincident[0]) {
- SkASSERT(!fIsCoincident[0]);
+ SkASSERT(!fIsCoincident[1]);
return 0;
}
int count = 0;
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index 83ff6b1..23470d7 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -207,9 +207,10 @@
int intersect(const SkDCubic&, const SkDLine&);
int intersect(const SkDCubic&, const SkDQuad&);
int intersect(const SkDCubic&, const SkDCubic&);
- int intersectRay(const SkDCubic& , const SkDLine&);
- int intersectRay(const SkDQuad& , const SkDLine&);
- static SkDPoint Line(const SkDLine& , const SkDLine&);
+ int intersectRay(const SkDLine&, const SkDLine&);
+ int intersectRay(const SkDQuad&, const SkDLine&);
+ int intersectRay(const SkDCubic&, const SkDLine&);
+ static SkDPoint Line(const SkDLine&, const SkDLine&);
void offset(int base, double start, double end);
void quickRemoveOne(int index, int replace);
static bool Test(const SkDLine& , const SkDLine&);
diff --git a/src/pathops/SkLineParameters.h b/src/pathops/SkLineParameters.h
index 5139c6c..8824e54 100644
--- a/src/pathops/SkLineParameters.h
+++ b/src/pathops/SkLineParameters.h
@@ -24,28 +24,37 @@
class SkLineParameters {
public:
void cubicEndPoints(const SkDCubic& pts) {
- cubicEndPoints(pts, 0, 3);
+ cubicEndPoints(pts, 0, 1);
+ if (dx() == 0 && dy() == 0) {
+ cubicEndPoints(pts, 0, 2);
+ if (dx() == 0 && dy() == 0) {
+ cubicEndPoints(pts, 0, 3);
+ }
+ }
}
void cubicEndPoints(const SkDCubic& pts, int s, int e) {
- a = approximately_pin(pts[s].fY - pts[e].fY);
- b = approximately_pin(pts[e].fX - pts[s].fX);
+ a = pts[s].fY - pts[e].fY;
+ b = pts[e].fX - pts[s].fX;
c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
}
void lineEndPoints(const SkDLine& pts) {
- a = approximately_pin(pts[0].fY - pts[1].fY);
- b = approximately_pin(pts[1].fX - pts[0].fX);
+ a = pts[0].fY - pts[1].fY;
+ b = pts[1].fX - pts[0].fX;
c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
}
void quadEndPoints(const SkDQuad& pts) {
- quadEndPoints(pts, 0, 2);
+ quadEndPoints(pts, 0, 1);
+ if (dx() == 0 && dy() == 0) {
+ quadEndPoints(pts, 0, 2);
+ }
}
void quadEndPoints(const SkDQuad& pts, int s, int e) {
- a = approximately_pin(pts[s].fY - pts[e].fY);
- b = approximately_pin(pts[e].fX - pts[s].fX);
+ a = pts[s].fY - pts[e].fY;
+ b = pts[e].fX - pts[s].fX;
c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
}
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index dee2906..c295bfb 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -6,95 +6,169 @@
*/
#include "SkIntersections.h"
#include "SkOpAngle.h"
+#include "SkOpSegment.h"
#include "SkPathOpsCurve.h"
#include "SkTSort.h"
-#if DEBUG_SORT || DEBUG_SORT_SINGLE
-#include "SkOpSegment.h"
+#if DEBUG_ANGLE
+#include "SkString.h"
+
+static const char funcName[] = "SkOpSegment::operator<";
+static const int bugChar = strlen(funcName) + 1;
#endif
-// FIXME: this is bogus for quads and cubics
-// if the quads and cubics' line from end pt to ctrl pt are coincident,
-// there's no obvious way to determine the curve ordering from the
-// derivatives alone. In particular, if one quadratic's coincident tangent
-// is longer than the other curve, the final control point can place the
-// longer curve on either side of the shorter one.
-// Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
-// may provide some help, but nothing has been figured out yet.
+/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
+ positive y. The largest angle has a positive x and a zero y. */
-/*(
+#if DEBUG_ANGLE
+ static bool CompareResult(SkString* bugOut, const char* append, bool compare) {
+ bugOut->appendf(append);
+ bugOut->writable_str()[bugChar] = "><"[compare];
+ SkDebugf("%s\n", bugOut->c_str());
+ return compare;
+ }
+
+ #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare)
+#else
+ #define COMPARE_RESULT(append, compare) compare
+#endif
+
+bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{
+ double absX = fabs(x);
+ double absY = fabs(y);
+ double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
+ int exponent;
+ (void) frexp(length, &exponent);
+ double epsilon = ldexp(FLT_EPSILON, exponent);
+ SkPath::Verb verb = fSegment->verb();
+ SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb);
+ // FIXME: the quad and cubic factors are made up ; determine actual values
+ double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon;
+ double xSlop = slop;
+ double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
+ double x1 = x - xSlop;
+ double y1 = y + ySlop;
+ double x_ry1 = x1 * ry;
+ double rx_y1 = rx * y1;
+ *result = x_ry1 < rx_y1;
+ double x2 = x + xSlop;
+ double y2 = y - ySlop;
+ double x_ry2 = x2 * ry;
+ double rx_y2 = rx * y2;
+ bool less2 = x_ry2 < rx_y2;
+ return *result == less2;
+}
+
+/*
for quads and cubics, set up a parameterized line (e.g. LineParameters )
for points [0] to [1]. See if point [2] is on that line, or on one side
or the other. If it both quads' end points are on the same side, choose
the shorter tangent. If the tangents are equal, choose the better second
tangent angle
-maybe I could set up LineParameters lazily
+FIXME: maybe I could set up LineParameters lazily
*/
-static int simple_compare(double x, double y, double rx, double ry) {
- if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?
- return y < 0;
- }
- if (y == 0 && ry == 0 && x * rx < 0) {
- return x < rx;
- }
- double x_ry = x * ry;
- double rx_y = rx * y;
- double cmp = x_ry - rx_y;
- if (!approximately_zero(cmp)) {
- return cmp < 0;
- }
- if (approximately_zero(x_ry) && approximately_zero(rx_y)
- && !approximately_zero_squared(cmp)) {
- return cmp < 0;
- }
- return -1;
-}
-
-bool SkOpAngle::operator<(const SkOpAngle& rh) const {
- double x = dx();
+bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand
double y = dy();
- double rx = rh.dx();
double ry = rh.dy();
- int simple = simple_compare(x, y, rx, ry);
- if (simple >= 0) {
- return simple;
+#if DEBUG_ANGLE
+ SkString bugOut;
+ bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g"
+ " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName,
+ fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd),
+ rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd));
+#endif
+ double y_ry = y * ry;
+ if (y_ry < 0) { // if y's are opposite signs, we can do a quick return
+ return COMPARE_RESULT("1 y * ry < 0", y < 0);
}
- // at this point, the initial tangent line is coincident
- // see if edges curl away from each other
- if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)
- || !approximately_zero(rh.fSide))) {
- // FIXME: running demo will trigger this assertion
- // (don't know if commenting out will trigger further assertion or not)
- // commenting it out allows demo to run in release, though
- return fSide < rh.fSide;
+ // at this point, both y's must be the same sign, or one (or both) is zero
+ double x = dx();
+ double rx = rh.dx();
+ if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half
+ if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive
+ return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0);
+ }
+ if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative
+ return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0);
+ }
+ SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller
+ return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0);
}
- // see if either curve can be lengthened and try the tangent compare again
- if (/* cmp && */ (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical
- && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting
+ // at this point, both x's must be the same sign, or one (or both) is zero
+ if (y_ry == 0) { // if either y is zero
+ if (y + ry < 0) { // if the other y is less than zero, it must be smaller
+ return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0);
+ }
+ if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller
+ return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0));
+ }
+ // at this point, both y's are zero, so lines are coincident or one is degenerate
+ SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far
+ }
+ // see if either curve can be lengthened before trying the tangent
+ if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical
+ && rh.fSegment->other(rh.fEnd) != fSegment) { // and not intersecting
SkOpAngle longer = *this;
SkOpAngle rhLonger = rh;
- if (longer.lengthen() | rhLonger.lengthen()) {
- return longer < rhLonger;
+ if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both
+ && (fUnorderable || !longer.fUnorderable)
+ && (rh.fUnorderable || !rhLonger.fUnorderable)) {
+#if DEBUG_ANGLE
+ bugOut.prepend(" ");
+#endif
+ return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger);
}
}
- if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
- || (rh.fVerb == SkPath::kLine_Verb
- && approximately_zero(rx) && approximately_zero(ry))) {
+ if (y_ry != 0) { // if they aren't coincident, look for a stable cross product
+ // at this point, y's are the same sign, neither is zero
+ // and x's are the same sign, or one (or both) is zero
+ double x_ry = x * ry;
+ double rx_y = rx * y;
+ if (!fComputed && !rh.fComputed) {
+ if (!AlmostEqualUlps(x_ry, rx_y)) {
+ return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y);
+ }
+ } else {
+ // if the vector was a result of subdividing a curve, see if it is stable
+ bool sloppy1 = x_ry < rx_y;
+ bool sloppy2 = !sloppy1;
+ if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1))
+ && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2))
+ && sloppy1 != sloppy2) {
+ return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1);
+ }
+ }
+ }
+ if (fSide * rh.fSide == 0) {
+ SkASSERT(fSide + rh.fSide != 0);
+ return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide);
+ }
+ // at this point, the initial tangent line is nearly coincident
+ // see if edges curl away from each other
+ if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) {
+ return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide);
+ }
+ if (fUnsortable || rh.fUnsortable) {
+ // even with no solution, return a stable sort
+ return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh);
+ }
+ SkPath::Verb verb = fSegment->verb();
+ SkPath::Verb rVerb = rh.fSegment->verb();
+ if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x))
+ || (rVerb == SkPath::kLine_Verb
+ && approximately_zero(ry) && approximately_zero(rx))) {
// See general unsortable comment below. This case can happen when
// one line has a non-zero change in t but no change in x and y.
fUnsortable = true;
- rh.fUnsortable = true;
- return this < &rh; // even with no solution, return a stable sort
+ return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh);
}
- if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny
- || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {
+ if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) {
fUnsortable = true;
- rh.fUnsortable = true;
- return this < &rh; // even with no solution, return a stable sort
+ return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh);
}
- SkASSERT(fVerb >= SkPath::kQuad_Verb);
- SkASSERT(rh.fVerb >= SkPath::kQuad_Verb);
+ SkASSERT(verb >= SkPath::kQuad_Verb);
+ SkASSERT(rVerb >= SkPath::kQuad_Verb);
// FIXME: until I can think of something better, project a ray from the
// end of the shorter tangent to midway between the end points
// through both curves and use the resulting angle to sort
@@ -110,22 +184,20 @@
do {
useThis = (len < rlen) ^ flip;
const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart;
- SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb;
+ SkPath::Verb partVerb = useThis ? verb : rVerb;
ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
part[2] : part[1];
- ray[1].fX = (part[0].fX + part[SkPathOpsVerbToPoints(partVerb)].fX) / 2;
- ray[1].fY = (part[0].fY + part[SkPathOpsVerbToPoints(partVerb)].fY) / 2;
+ ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]);
SkASSERT(ray[0] != ray[1]);
- roots = (i.*CurveRay[SkPathOpsVerbToPoints(fVerb)])(fPts, ray);
- rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rh.fVerb)])(rh.fPts, ray);
+ roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray);
+ rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray);
} while ((roots == 0 || rroots == 0) && (flip ^= true));
if (roots == 0 || rroots == 0) {
// FIXME: we don't have a solution in this case. The interim solution
// is to mark the edges as unsortable, exclude them from this and
// future computations, and allow the returned path to be fragmented
fUnsortable = true;
- rh.fUnsortable = true;
- return this < &rh; // even with no solution, return a stable sort
+ return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh);
}
SkASSERT(fSide != 0 && rh.fSide != 0);
SkASSERT(fSide * rh.fSide > 0); // both are the same sign
@@ -164,105 +236,96 @@
break;
}
}
- #if 0
- SkDVector lRay = lLoc - fCurvePart[0];
- SkDVector rRay = rLoc - fCurvePart[0];
- int rayDir = simple_compare(lRay.fX, lRay.fY, rRay.fX, rRay.fY);
- SkASSERT(rayDir >= 0);
- if (rayDir < 0) {
- fUnsortable = true;
- rh.fUnsortable = true;
- return this < &rh; // even with no solution, return a stable sort
- }
-#endif
- if (flip) {
+ if (flip) {
leftLessThanRight = !leftLessThanRight;
- // rayDir = !rayDir;
}
-#if 0 && (DEBUG_SORT || DEBUG_SORT_SINGLE)
- SkDebugf("%d %c %d (fSide %c 0) loc={{%1.9g,%1.9g}, {%1.9g,%1.9g}} flip=%d rayDir=%d\n",
- fSegment->debugID(), "><"[leftLessThanRight], rh.fSegment->debugID(),
- "<>"[fSide > 0], lLoc.fX, lLoc.fY, rLoc.fX, rLoc.fY, flip, rayDir);
-#endif
-// SkASSERT(leftLessThanRight == (bool) rayDir);
- return leftLessThanRight;
+ return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight);
}
-bool SkOpAngle::lengthen() {
- int newEnd = fEnd;
- if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
- fEnd = newEnd;
- setSpans();
- return true;
- }
- return false;
+bool SkOpAngle::isHorizontal() const {
+ return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb;
}
-bool SkOpAngle::reverseLengthen() {
- if (fReversed) {
+// lengthen cannot cross opposite angle
+bool SkOpAngle::lengthen(const SkOpAngle& opp) {
+ if (fSegment->other(fEnd) == opp.fSegment) {
return false;
}
- int newEnd = fStart;
- if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
+ // FIXME: make this a while loop instead and make it as large as possible?
+ int newEnd = fEnd;
+ if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) {
fEnd = newEnd;
- fReversed = true;
setSpans();
return true;
}
return false;
}
-void SkOpAngle::set(const SkPoint* orig, SkPath::Verb verb, const SkOpSegment* segment,
- int start, int end, const SkTDArray<SkOpSpan>& spans) {
+void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
fSegment = segment;
fStart = start;
fEnd = end;
- fPts = orig;
- fVerb = verb;
- fSpans = &spans;
- fReversed = false;
- fUnsortable = false;
setSpans();
}
-
void SkOpAngle::setSpans() {
- double startT = (*fSpans)[fStart].fT;
- double endT = (*fSpans)[fEnd].fT;
- switch (fVerb) {
+ fUnorderable = false;
+ if (fSegment->verb() == SkPath::kLine_Verb) {
+ fUnsortable = false;
+ } else {
+ // if start-1 exists and is tiny, then start pt may have moved
+ int smaller = SkMin32(fStart, fEnd);
+ int tinyCheck = smaller;
+ while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) {
+ --tinyCheck;
+ }
+ if ((fUnsortable = smaller > 0 && tinyCheck == 0)) {
+ return;
+ }
+ int larger = SkMax32(fStart, fEnd);
+ tinyCheck = larger;
+ int max = fSegment->count() - 1;
+ while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) {
+ ++tinyCheck;
+ }
+ if ((fUnsortable = larger < max && tinyCheck == max)) {
+ return;
+ }
+ }
+ fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart);
+ // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try
+ // rounding the curve part to float precision here
+ // fCurvePart.round(fSegment->verb());
+ switch (fSegment->verb()) {
case SkPath::kLine_Verb: {
- SkDLine l = SkDLine::SubDivide(fPts, startT, endT);
// OPTIMIZATION: for pure line compares, we never need fTangent1.c
- fTangent1.lineEndPoints(l);
+ fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart));
fSide = 0;
} break;
case SkPath::kQuad_Verb: {
SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart);
- quad = SkDQuad::SubDivide(fPts, startT, endT);
- fTangent1.quadEndPoints(quad, 0, 1);
- if (dx() == 0 && dy() == 0) {
- fTangent1.quadEndPoints(quad);
- }
+ fTangent1.quadEndPoints(quad);
fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
- } break;
- case SkPath::kCubic_Verb: {
- // int nextC = 2;
- fCurvePart = SkDCubic::SubDivide(fPts, startT, endT);
- fTangent1.cubicEndPoints(fCurvePart, 0, 1);
- if (dx() == 0 && dy() == 0) {
- fTangent1.cubicEndPoints(fCurvePart, 0, 2);
- // nextC = 3;
- if (dx() == 0 && dy() == 0) {
- fTangent1.cubicEndPoints(fCurvePart, 0, 3);
+ if (fComputed && dx() > 0 && approximately_zero(dy())) {
+ SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
+ int last = fSegment->count() - 1;
+ fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
+ SkLineParameters origTan;
+ origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve));
+ if ((fUnorderable = origTan.dx() <= 0
+ || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match?
+ return;
}
}
- // fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only
- // if (nextC == 2 && approximately_zero(fSide)) {
- // fSide = -fTangent1.pointDistance(fCurvePart[3]);
- // }
+ } break;
+ case SkPath::kCubic_Verb: {
+ fTangent1.cubicEndPoints(fCurvePart);
double testTs[4];
// OPTIMIZATION: keep inflections precomputed with cubic segment?
- int testCount = SkDCubic::FindInflections(fPts, testTs);
+ const SkPoint* pts = fSegment->pts();
+ int testCount = SkDCubic::FindInflections(pts, testTs);
+ double startT = fSegment->t(fStart);
+ double endT = fSegment->t(fEnd);
double limitT = endT;
int index;
for (index = 0; index < testCount; ++index) {
@@ -287,35 +350,62 @@
testT = (testT + testTs[testIndex + 1]) / 2;
}
// OPTIMIZE: could avoid call for t == startT, endT
- SkDPoint pt = dcubic_xy_at_t(fPts, testT);
+ SkDPoint pt = dcubic_xy_at_t(pts, testT);
double testSide = fTangent1.pointDistance(pt);
if (fabs(bestSide) < fabs(testSide)) {
bestSide = testSide;
}
}
fSide = -bestSide; // compare sign only
+ if (fComputed && dx() > 0 && approximately_zero(dy())) {
+ SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
+ int last = fSegment->count() - 1;
+ fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
+ SkLineParameters origTan;
+ origTan.cubicEndPoints(origCurve);
+ if ((fUnorderable = origTan.dx() <= 0)) {
+ fUnsortable = fSegment->isTiny(this);
+ return;
+ }
+ // if one is < 0 and the other is >= 0
+ if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) {
+ fUnsortable = fSegment->isTiny(this);
+ return;
+ }
+ SkDCubicPair split = origCurve.chopAt(startT);
+ SkLineParameters splitTan;
+ splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first());
+ if ((fUnorderable = splitTan.dx() <= 0)) {
+ fUnsortable = fSegment->isTiny(this);
+ return;
+ }
+ // if one is < 0 and the other is >= 0
+ if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) {
+ fUnsortable = fSegment->isTiny(this);
+ return;
+ }
+ }
} break;
default:
SkASSERT(0);
}
- fUnsortable = dx() == 0 && dy() == 0;
- if (fUnsortable) {
+ if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) {
return;
}
SkASSERT(fStart != fEnd);
int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
for (int index = fStart; index != fEnd; index += step) {
#if 1
- const SkOpSpan& thisSpan = (*fSpans)[index];
- const SkOpSpan& nextSpan = (*fSpans)[index + step];
+ const SkOpSpan& thisSpan = fSegment->span(index);
+ const SkOpSpan& nextSpan = fSegment->span(index + step);
if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
continue;
}
fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
#if DEBUG_UNSORTABLE
if (fUnsortable) {
- SkPoint iPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, thisSpan.fT);
- SkPoint ePt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, nextSpan.fT);
+ SkPoint iPt = fSegment->xyAtT(index);
+ SkPoint ePt = fSegment->xyAtT(index + step);
SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
}
@@ -330,8 +420,8 @@
}
#if 1
#if DEBUG_UNSORTABLE
- SkPoint iPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, startT);
- SkPoint ePt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, endT);
+ SkPoint iPt = fSegment->xyAtT(fStart);
+ SkPoint ePt = fSegment->xyAtT(fEnd);
SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
#endif
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index 00520ec..cca1a22 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -8,10 +8,10 @@
#define SkOpAngle_DEFINED
#include "SkLineParameters.h"
-#include "SkOpSpan.h"
#include "SkPath.h"
#include "SkPathOpsCubic.h"
-#include "SkTDArray.h"
+
+class SkOpSegment;
// sorting angles
// given angles of {dx dy ddx ddy dddx dddy} sort them
@@ -19,6 +19,8 @@
public:
bool operator<(const SkOpAngle& rh) const;
+ bool calcSlop(double x, double y, double rx, double ry, bool* result) const;
+
double dx() const {
return fTangent1.dx();
}
@@ -31,17 +33,9 @@
return fEnd;
}
- bool isHorizontal() const {
- return dy() == 0 && fVerb == SkPath::kLine_Verb;
- }
+ bool isHorizontal() const;
- bool lengthen();
- bool reverseLengthen();
-
- void set(const SkPoint* orig, SkPath::Verb verb, const SkOpSegment* segment,
- int start, int end, const SkTDArray<SkOpSpan>& spans);
-
- void setSpans();
+ void set(const SkOpSegment* segment, int start, int end);
SkOpSegment* segment() const {
return const_cast<SkOpSegment*>(fSegment);
@@ -51,44 +45,47 @@
return SkSign32(fStart - fEnd);
}
- const SkTDArray<SkOpSpan>* spans() const {
- return fSpans;
- }
-
int start() const {
return fStart;
}
+ bool unorderable() const {
+ return fUnorderable;
+ }
+
bool unsortable() const {
return fUnsortable;
}
#if DEBUG_ANGLE
- const SkPoint* pts() const {
- return fPts;
- }
-
- SkPath::Verb verb() const {
- return fVerb;
- }
-
void debugShow(const SkPoint& a) const {
SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
}
+
+ void setID(int id) {
+ fID = id;
+ }
#endif
private:
- const SkPoint* fPts;
+ bool lengthen(const SkOpAngle& );
+ void setSpans();
+
SkDCubic fCurvePart;
- SkPath::Verb fVerb;
double fSide;
SkLineParameters fTangent1;
- const SkTDArray<SkOpSpan>* fSpans;
const SkOpSegment* fSegment;
int fStart;
int fEnd;
- bool fReversed;
+ bool fComputed; // tangent is computed, may contain some error
+ // if subdividing a quad or cubic causes the tangent to go from the maximum angle to the
+ // minimum, mark it unorderable. It still can be sorted, which is good enough for find-top
+ // but can't be ordered, and therefore can't be used to compute winding
+ bool fUnorderable;
mutable bool fUnsortable; // this alone is editable by the less than operator
+#if DEBUG_ANGLE
+ int fID;
+#endif
};
#endif
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 817732e..a9e20fd 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -209,19 +209,22 @@
SkOpAngle* angle = anglesPtr->append();
#if DEBUG_ANGLE
SkTDArray<SkOpAngle>& angles = *anglesPtr;
- if (angles.count() > 1 && !fTs[start].fTiny) {
- SkPoint angle0Pt = (*CurvePointAtT[SkPathOpsVerbToPoints(angles[0].verb())])(angles[0].pts(),
- (*angles[0].spans())[angles[0].start()].fT);
- SkPoint newPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[start].fT);
- bool match = AlmostEqualUlps(angle0Pt.fX, newPt.fX);
- match &= AlmostEqualUlps(angle0Pt.fY, newPt.fY);
- if (!match) {
- SkDebugf("%s no match\n", __FUNCTION__);
- SkASSERT(0);
+ if (angles.count() > 1) {
+ const SkOpSegment* aSeg = angles[0].segment();
+ int aStart = angles[0].start();
+ if (!aSeg->fTs[aStart].fTiny) {
+ const SkPoint& angle0Pt = aSeg->xyAtT(aStart);
+ SkDPoint newPt = (*CurveDPointAtT[SkPathOpsVerbToPoints(aSeg->fVerb)])(aSeg->fPts,
+ aSeg->fTs[aStart].fT);
+#if ONE_OFF_DEBUG
+ SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g)\n", __FUNCTION__,
+ aSeg->fTs[aStart].fT, newPt.fX, newPt.fY, angle0Pt.fX, angle0Pt.fY);
+#endif
+ SkASSERT(newPt.approximatelyEqual(angle0Pt));
}
}
#endif
- angle->set(fPts, fVerb, this, start, end, fTs);
+ angle->set(this, start, end);
}
void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd) {
@@ -853,7 +856,8 @@
// OPTIMIZATION: check all angles to see if any have computed wind sum
// before sorting (early exit if none)
SkTDArray<SkOpAngle*> sorted;
- bool sortable = SortAngles(angles, &sorted);
+ // FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ...
+ bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
#if DEBUG_SORT
sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
#endif
@@ -979,7 +983,8 @@
SkIntersections intersections;
// OPTIMIZE: use specialty function that intersects ray with curve,
// returning t values only for curve (we don't care about t on ray)
- int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, top, bottom, basePt.fX, false);
+ int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
+ (fPts, top, bottom, basePt.fX, false);
if (pts == 0 || (current && pts == 1)) {
return bestTIndex;
}
@@ -1126,6 +1131,9 @@
}
while (precisely_zero(startT - other->fTs[*nextEnd].fT));
SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
+ if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
+ return NULL;
+ }
return other;
}
// more than one viable candidate -- measure angles to find best
@@ -1135,7 +1143,7 @@
addTwoAngles(startIndex, end, &angles);
buildAngles(end, &angles, true);
SkTDArray<SkOpAngle*> sorted;
- bool sortable = SortAngles(angles, &sorted);
+ bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
@@ -1177,12 +1185,12 @@
if (activeAngle) {
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
- if (nextSegment->tiny(nextAngle)) {
+ if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
return NULL;
}
foundAngle = nextAngle;
- foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
+ foundDone = nextSegment->done(nextAngle) && !nextSegment->isTiny(nextAngle);
}
}
if (nextSegment->done()) {
@@ -1257,7 +1265,7 @@
addTwoAngles(startIndex, end, &angles);
buildAngles(end, &angles, true);
SkTDArray<SkOpAngle*> sorted;
- bool sortable = SortAngles(angles, &sorted);
+ bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
@@ -1294,7 +1302,7 @@
if (activeAngle) {
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
- if (nextSegment->tiny(nextAngle)) {
+ if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
return NULL;
}
@@ -1386,7 +1394,7 @@
addTwoAngles(startIndex, end, &angles);
buildAngles(end, &angles, false);
SkTDArray<SkOpAngle*> sorted;
- bool sortable = SortAngles(angles, &sorted);
+ bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
if (!sortable) {
*unsortable = true;
#if DEBUG_SORT
@@ -1416,7 +1424,7 @@
nextSegment = nextAngle->segment();
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
- if (nextSegment->tiny(nextAngle)) {
+ if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
return NULL;
}
@@ -1628,7 +1636,7 @@
addTwoAngles(end, firstT, &angles);
buildAngles(firstT, &angles, true);
SkTDArray<SkOpAngle*> sorted;
- bool sortable = SortAngles(angles, &sorted);
+ bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
int first = SK_MaxS32;
SkScalar top = SK_ScalarMax;
int count = sorted.count();
@@ -2081,7 +2089,8 @@
SkASSERT(fVerb != SkPath::kLine_Verb);
SkPoint edge[4];
subDivide(tStart, tEnd, edge);
- double sum = (edge[0].fX - edge[SkPathOpsVerbToPoints(fVerb)].fX) * (edge[0].fY + edge[SkPathOpsVerbToPoints(fVerb)].fY);
+ int points = SkPathOpsVerbToPoints(fVerb);
+ double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
if (fVerb == SkPath::kCubic_Verb) {
SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
if (edge[1].fY < lesser && edge[2].fY < lesser) {
@@ -2095,7 +2104,7 @@
}
}
}
- for (int idx = 0; idx < SkPathOpsVerbToPoints(fVerb); ++idx){
+ for (int idx = 0; idx < points; ++idx){
sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
}
return sum <= 0;
@@ -2334,8 +2343,8 @@
// exclusion in find top and others. This could be optimized to only mark
// adjacent spans that unsortable. However, this makes it difficult to later
// determine starting points for edge detection in find top and the like.
-bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles,
- SkTDArray<SkOpAngle*>* angleList) {
+bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList,
+ SortAngleKind orderKind) {
bool sortable = true;
int angleCount = angles.count();
int angleIndex;
@@ -2343,12 +2352,17 @@
for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
const SkOpAngle& angle = angles[angleIndex];
*angleList->append() = const_cast<SkOpAngle*>(&angle);
- sortable &= !angle.unsortable();
+#if DEBUG_ANGLE
+ (*(angleList->end() - 1))->setID(angleIndex);
+#endif
+ sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
+ && angle.unorderable()));
}
if (sortable) {
SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
- if (angles[angleIndex].unsortable()) {
+ if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
+ && angles[angleIndex].unorderable())) {
sortable = false;
break;
}
@@ -2363,20 +2377,80 @@
return sortable;
}
-void SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
+// return true if midpoints were computed
+bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
+ SkASSERT(start != end);
edge[0] = fTs[start].fPt;
- edge[SkPathOpsVerbToPoints(fVerb)] = fTs[end].fPt;
- if (fVerb == SkPath::kQuad_Verb || fVerb == SkPath::kCubic_Verb) {
- SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[SkPathOpsVerbToPoints(fVerb)].fX, edge[SkPathOpsVerbToPoints(fVerb)].fY }};
- if (fVerb == SkPath::kQuad_Verb) {
- edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], fTs[start].fT,
- fTs[end].fT).asSkPoint();
- } else {
- SkDCubic::SubDivide(fPts, sub[0], sub[1], fTs[start].fT, fTs[end].fT, sub);
- edge[1] = sub[0].asSkPoint();
- edge[2] = sub[1].asSkPoint();
- }
+ int points = SkPathOpsVerbToPoints(fVerb);
+ edge[points] = fTs[end].fPt;
+ if (fVerb == SkPath::kLine_Verb) {
+ return false;
}
+ double startT = fTs[start].fT;
+ double endT = fTs[end].fT;
+ if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
+ // don't compute midpoints if we already have them
+ if (fVerb == SkPath::kQuad_Verb) {
+ edge[1] = fPts[1];
+ return false;
+ }
+ SkASSERT(fVerb == SkPath::kCubic_Verb);
+ if (start < end) {
+ edge[1] = fPts[1];
+ edge[2] = fPts[2];
+ return false;
+ }
+ edge[1] = fPts[2];
+ edge[2] = fPts[1];
+ return false;
+ }
+ const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
+ if (fVerb == SkPath::kQuad_Verb) {
+ edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
+ } else {
+ SkASSERT(fVerb == SkPath::kCubic_Verb);
+ SkDPoint ctrl[2];
+ SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
+ edge[1] = ctrl[0].asSkPoint();
+ edge[2] = ctrl[1].asSkPoint();
+ }
+ return true;
+}
+
+// return true if midpoints were computed
+bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
+ SkASSERT(start != end);
+ (*result)[0].set(fTs[start].fPt);
+ int points = SkPathOpsVerbToPoints(fVerb);
+ (*result)[points].set(fTs[end].fPt);
+ if (fVerb == SkPath::kLine_Verb) {
+ return false;
+ }
+ double startT = fTs[start].fT;
+ double endT = fTs[end].fT;
+ if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
+ // don't compute midpoints if we already have them
+ if (fVerb == SkPath::kQuad_Verb) {
+ (*result)[1].set(fPts[1]);
+ return false;
+ }
+ SkASSERT(fVerb == SkPath::kCubic_Verb);
+ if (start < end) {
+ (*result)[1].set(fPts[1]);
+ (*result)[2].set(fPts[2]);
+ return false;
+ }
+ (*result)[1].set(fPts[2]);
+ (*result)[2].set(fPts[1]);
+ return false;
+ }
+ if (fVerb == SkPath::kQuad_Verb) {
+ (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
+ } else {
+ SkASSERT(fVerb == SkPath::kCubic_Verb);
+ SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
+ }
+ return true;
}
void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
@@ -2385,13 +2459,17 @@
(bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
}
-bool SkOpSegment::tiny(const SkOpAngle* angle) const {
+bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
int start = angle->start();
int end = angle->end();
const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
return mSpan.fTiny;
}
+bool SkOpSegment::isTiny(int index) const {
+ return fTs[index].fTiny;
+}
+
void SkOpSegment::TrackOutside(SkTDArray<double>* outsideTs, double end, double start) {
int outCount = outsideTs->count();
if (outCount == 0 || !approximately_negative(end - (*outsideTs)[outCount - 2])) {
@@ -2735,8 +2813,8 @@
}
SkDebugf("%s [%d] %s", __FUNCTION__, index,
angle.unsortable() ? "*** UNSORTABLE *** " : "");
- #if COMPACT_DEBUG_SORT
- SkDebugf("id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)",
+ #if DEBUG_SORT_COMPACT
+ SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)",
segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)],
start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
segment.xAtT(&eSpan), segment.yAtT(&eSpan));
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index e489acf..b26bad1 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -8,6 +8,7 @@
#define SkOpSegment_DEFINE
#include "SkOpAngle.h"
+#include "SkOpSpan.h"
#include "SkPathOpsBounds.h"
#include "SkPathOpsCurve.h"
#include "SkTDArray.h"
@@ -40,6 +41,10 @@
return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
}
+ int count() const {
+ return fTs.count();
+ }
+
bool done() const {
SkASSERT(fDoneSpans <= fTs.count());
return fDoneSpans == fTs.count();
@@ -120,6 +125,10 @@
return fTs[lesser].fOppValue;
}
+ const SkOpSegment* other(int index) const {
+ return fTs[index].fOther;
+ }
+
const SkPoint* pts() const {
return fPts;
}
@@ -262,6 +271,8 @@
bool isLinear(int start, int end) const;
bool isMissing(double startT) const;
bool isSimple(int end) const;
+ bool isTiny(const SkOpAngle* angle) const;
+ bool isTiny(int index) const;
SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
@@ -279,8 +290,14 @@
int nextSpan(int from, int step) const;
void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
- static bool SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList);
- void subDivide(int start, int end, SkPoint edge[4]) const;
+ enum SortAngleKind {
+ kMustBeOrdered_SortAngleKind, // required for winding calc
+ kMayBeUnordered_SortAngleKind // ok for find top
+ };
+ static bool SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList,
+ SortAngleKind );
+ bool subDivide(int start, int end, SkPoint edge[4]) const;
+ bool subDivide(int start, int end, SkDCubic* result) const;
void undoneSpan(int* start, int* end);
int updateOppWindingReverse(const SkOpAngle* angle) const;
int updateWindingReverse(const SkOpAngle* angle) const;
@@ -348,7 +365,6 @@
SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
bool serpentine(int tStart, int tEnd) const;
void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
- bool tiny(const SkOpAngle* angle) const;
static void TrackOutside(SkTDArray<double>* outsideTs, double end, double start);
int updateOppWinding(int index, int endIndex) const;
int updateOppWinding(const SkOpAngle* angle) const;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index a089d7c..9215cbc 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -134,7 +134,8 @@
continue;
}
SkTDArray<SkOpAngle*> sorted;
- bool sortable = SkOpSegment::SortAngles(angles, &sorted);
+ bool sortable = SkOpSegment::SortAngles(angles, &sorted,
+ SkOpSegment::kMayBeUnordered_SortAngleKind);
int angleCount = sorted.count();
#if DEBUG_SORT
sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index 674213c..c644a67 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -403,11 +403,23 @@
/* by = */ dst[1].fY = (my * 2 - ny) / 18;
/* cx = */ dst[2].fX = (nx * 2 - mx) / 18;
/* cy = */ dst[2].fY = (ny * 2 - my) / 18;
+ // FIXME: call align() ?
return dst;
}
+void SkDCubic::align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const {
+ if (fPts[endIndex].fX == fPts[ctrlIndex].fX) {
+ dstPt->fX = fPts[endIndex].fX;
+ }
+ if (fPts[endIndex].fY == fPts[ctrlIndex].fY) {
+ dstPt->fY = fPts[endIndex].fY;
+ }
+}
+
void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d,
double t1, double t2, SkDPoint dst[2]) const {
+ SkASSERT(t1 != t2);
+#if 0
double ex = interp_cubic_coords(&fPts[0].fX, (t1 * 2 + t2) / 3);
double ey = interp_cubic_coords(&fPts[0].fY, (t1 * 2 + t2) / 3);
double fx = interp_cubic_coords(&fPts[0].fX, (t1 + t2 * 2) / 3);
@@ -420,6 +432,30 @@
/* by = */ dst[0].fY = (my * 2 - ny) / 18;
/* cx = */ dst[1].fX = (nx * 2 - mx) / 18;
/* cy = */ dst[1].fY = (ny * 2 - my) / 18;
+#else
+ // this approach assumes that the control points computed directly are accurate enough
+ SkDCubic sub = subDivide(t1, t2);
+ dst[0] = sub[1] + (a - sub[0]);
+ dst[1] = sub[2] + (d - sub[3]);
+#endif
+ if (t1 == 0 || t2 == 0) {
+ align(0, 1, t1 == 0 ? &dst[0] : &dst[1]);
+ }
+ if (t1 == 1 || t2 == 1) {
+ align(3, 2, t1 == 1 ? &dst[0] : &dst[1]);
+ }
+ if (precisely_subdivide_equal(dst[0].fX, a.fX)) {
+ dst[0].fX = a.fX;
+ }
+ if (precisely_subdivide_equal(dst[0].fY, a.fY)) {
+ dst[0].fY = a.fY;
+ }
+ if (precisely_subdivide_equal(dst[1].fX, d.fX)) {
+ dst[1].fX = d.fX;
+ }
+ if (precisely_subdivide_equal(dst[1].fY, d.fY)) {
+ dst[1].fY = d.fY;
+ }
}
/* classic one t subdivision */
diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h
index 37492dd..c884ea9 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -8,6 +8,7 @@
#ifndef SkPathOpsCubic_DEFINED
#define SkPathOpsCubic_DEFINED
+#include "SkPath.h"
#include "SkPathOpsPoint.h"
#include "SkTDArray.h"
@@ -32,6 +33,7 @@
const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 4); return fPts[n]; }
SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 4); return fPts[n]; }
+ void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const;
double calcPrecision() const;
SkDCubicPair chopAt(double t) const;
bool clockwise() const;
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 2d0962b..6c8ca95 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -68,21 +68,21 @@
while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
switch (verb) {
case SkPath::kMove_Verb:
- SkDebugf("%s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY);
+ SkDebugf(" %s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY);
continue;
case SkPath::kLine_Verb:
- SkDebugf("%s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY);
+ SkDebugf(" %s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY);
break;
case SkPath::kQuad_Verb:
- SkDebugf("%s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName,
+ SkDebugf(" %s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName,
pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
break;
case SkPath::kCubic_Verb:
- SkDebugf("%s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n",
+ SkDebugf(" %s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n",
pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY);
break;
case SkPath::kClose_Verb:
- SkDebugf("%s.close();\n", pathName);
+ SkDebugf(" %s.close();\n", pathName);
break;
default:
SkDEBUGFAIL("bad verb");
@@ -98,12 +98,17 @@
"kInverseEvenOdd_FillType"
};
+
+void ShowFunctionHeader() {
+ SkDebugf("\nstatic void test#(skiatest::Reporter* reporter) {\n");
+}
+
void ShowPath(const SkPath& path, const char* pathName) {
SkPath::Iter iter(path, true);
SkPath::FillType fillType = path.getFillType();
SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
- SkDebugf("SkPath %s;\n", pathName);
- SkDebugf("%s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]);
+ SkDebugf(" SkPath %s;\n", pathName);
+ SkDebugf(" %s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]);
iter.setPath(path, true);
showPathContours(iter, pathName);
}
@@ -117,8 +122,7 @@
};
void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo) {
- SkDebugf("SkPath result;\n");
- SkDebugf("bool success = Op(%s, %s, %s, &result);\n", pathOne, pathTwo, gOpStrs[op]);
- SkDebugf("SkASSERT(success);\n");
+ SkDebugf(" testPathOp(reporter, %s, %s, %s);\n", pathOne, pathTwo, gOpStrs[op]);
+ SkDebugf("}\n");
}
#endif
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 61b59c3..cc1b8ea 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -61,6 +61,7 @@
#define DEBUG_SHOW_TEST_PROGRESS 0
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 0
+#define DEBUG_SORT_COMPACT 0
#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 0
#define DEBUG_UNSORTABLE 0
@@ -73,7 +74,7 @@
#define DEBUG_ACTIVE_OP 1
#define DEBUG_ACTIVE_SPANS 1
#define DEBUG_ACTIVE_SPANS_FIRST_ONLY 0
-#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
+#define DEBUG_ACTIVE_SPANS_SHORT_FORM 1
#define DEBUG_ADD_INTERSECTING_TS 1
#define DEBUG_ADD_T_PAIR 1
#define DEBUG_ANGLE 1
@@ -90,6 +91,7 @@
#define DEBUG_SHOW_TEST_PROGRESS 1
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 1
+#define DEBUG_SORT_COMPACT 0
#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 1
@@ -144,6 +146,7 @@
#endif
#if DEBUG_SHOW_PATH
+void ShowFunctionHeader();
void ShowPath(const SkPath& path, const char* pathName);
void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo);
#endif
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index db55635..f030765 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -37,7 +37,8 @@
continue;
}
SkTDArray<SkOpAngle*> sorted;
- bool sortable = SkOpSegment::SortAngles(angles, &sorted);
+ bool sortable = SkOpSegment::SortAngles(angles, &sorted,
+ SkOpSegment::kMayBeUnordered_SortAngleKind);
int angleCount = sorted.count();
#if DEBUG_SORT
sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0);
@@ -232,6 +233,7 @@
bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
#if DEBUG_SHOW_PATH
+ ShowFunctionHeader();
ShowPath(one, "path");
ShowPath(two, "pathB");
ShowOp(op, "path", "pathB");
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index 23734c9..534154f 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -117,8 +117,8 @@
return true;
}
double inv = 1 / denom;
- return approximately_equal(fX * inv, a.fX * inv)
- && approximately_equal(fY * inv, a.fY * inv);
+ return approximately_equal_double(fX * inv, a.fX * inv)
+ && approximately_equal_double(fY * inv, a.fY * inv);
}
bool approximatelyEqualHalf(const SkDPoint& a) const {
@@ -151,6 +151,13 @@
return temp.lengthSquared();
}
+ static SkDPoint Mid(const SkDPoint& a, const SkDPoint& b) {
+ SkDPoint result;
+ result.fX = (a.fX + b.fX) / 2;
+ result.fY = (a.fY + b.fY) / 2;
+ return result;
+ }
+
double moreRoughlyEqual(const SkDPoint& a) const {
return more_roughly_equal(a.fY, fY) && more_roughly_equal(a.fX, fX);
}
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index 685f49e..ce89469 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -4,6 +4,7 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
+#include "SkIntersections.h"
#include "SkLineParameters.h"
#include "SkPathOpsCubic.h"
#include "SkPathOpsQuad.h"
@@ -220,12 +221,53 @@
return dst;
}
+void SkDQuad::align(int endIndex, SkDPoint* dstPt) const {
+ if (fPts[endIndex].fX == fPts[1].fX) {
+ dstPt->fX = fPts[endIndex].fX;
+ }
+ if (fPts[endIndex].fY == fPts[1].fY) {
+ dstPt->fY = fPts[endIndex].fY;
+ }
+}
+
SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const {
+ SkASSERT(t1 != t2);
SkDPoint b;
+#if 0
+ // this approach assumes that the control point computed directly is accurate enough
double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2);
double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2);
b.fX = 2 * dx - (a.fX + c.fX) / 2;
b.fY = 2 * dy - (a.fY + c.fY) / 2;
+#else
+ SkDQuad sub = subDivide(t1, t2);
+ SkDLine b0 = {{a, sub[1] + (a - sub[0])}};
+ SkDLine b1 = {{c, sub[1] + (c - sub[2])}};
+ SkIntersections i;
+ i.intersectRay(b0, b1);
+ if (i.used() == 1) {
+ b = i.pt(0);
+ } else {
+ SkASSERT(i.used() == 2 || i.used() == 0);
+ b = SkDPoint::Mid(b0[1], b1[1]);
+ }
+#endif
+ if (t1 == 0 || t2 == 0) {
+ align(0, &b);
+ }
+ if (t1 == 1 || t2 == 1) {
+ align(2, &b);
+ }
+ if (precisely_subdivide_equal(b.fX, a.fX)) {
+ b.fX = a.fX;
+ } else if (precisely_subdivide_equal(b.fX, c.fX)) {
+ b.fX = c.fX;
+ }
+ if (precisely_subdivide_equal(b.fY, a.fY)) {
+ b.fY = a.fY;
+ } else if (precisely_subdivide_equal(b.fY, c.fY)) {
+ b.fY = c.fY;
+ }
return b;
}
diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index d5ca0c7..d06f344 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -19,6 +19,11 @@
struct SkDQuad {
SkDPoint fPts[3];
+ SkDQuad flip() const {
+ SkDQuad result = {{fPts[2], fPts[1], fPts[0]}};
+ return result;
+ }
+
void set(const SkPoint pts[3]) {
fPts[0] = pts[0];
fPts[1] = pts[1];
@@ -29,6 +34,7 @@
SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 3); return fPts[n]; }
static int AddValidTs(double s[], int realRoots, double* t);
+ void align(int endIndex, SkDPoint* dstPt) const;
SkDQuadPair chopAt(double t) const;
SkDVector dxdyAtT(double t) const;
static int FindExtrema(double a, double b, double c, double tValue[1]);
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index 199d7be..b071ca5 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -4,36 +4,31 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
+#include "SkFloatBits.h"
#include "SkPathOpsTypes.h"
const int UlpsEpsilon = 16;
// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
-union SkPathOpsUlpsFloat {
- int32_t fInt;
- float fFloat;
-
- SkPathOpsUlpsFloat(float num = 0.0f) : fFloat(num) {}
- bool negative() const { return fInt < 0; }
-};
-
+// FIXME: move to SkFloatBits.h
bool AlmostEqualUlps(float A, float B) {
- SkPathOpsUlpsFloat uA(A);
- SkPathOpsUlpsFloat uB(B);
+ SkFloatIntUnion floatIntA, floatIntB;
+ floatIntA.fFloat = A;
+ floatIntB.fFloat = B;
// Different signs means they do not match.
- if (uA.negative() != uB.negative())
+ if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0))
{
// Check for equality to make sure +0 == -0
return A == B;
}
// Find the difference in ULPs.
- int ulpsDiff = abs(uA.fInt - uB.fInt);
+ int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
return ulpsDiff <= UlpsEpsilon;
}
// cube root approximation using bit hack for 64-bit float
// adapted from Kahan's cbrt
-static double cbrt_5d(double d) {
+static double cbrt_5d(double d) {
const unsigned int B1 = 715094163;
double t = 0.0;
unsigned int* pt = (unsigned int*) &t;
@@ -43,7 +38,7 @@
}
// iterative cube root approximation using Halley's method (double)
-static double cbrta_halleyd(const double a, const double R) {
+static double cbrta_halleyd(const double a, const double R) {
const double a3 = a * a * a;
const double b = a * (a3 + R + R) / (a3 + a3 + R);
return b;
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 0f689d8..6ead794 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -7,8 +7,6 @@
#ifndef SkPathOpsTypes_DEFINED
#define SkPathOpsTypes_DEFINED
-#define SK_CONIC_SUPPORT_ENABLED 1
-
#include <float.h> // for FLT_EPSILON
#include <math.h> // for fabs, sqrt
@@ -25,7 +23,7 @@
};
// Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
-extern bool AlmostEqualUlps(float A, float B);
+bool AlmostEqualUlps(float A, float B);
inline bool AlmostEqualUlps(double A, double B) {
return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
}
@@ -34,10 +32,12 @@
// DBL_EPSILON == 2.22045e-16
const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
+const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2;
const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error
+const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
const double ROUGH_EPSILON = FLT_EPSILON * 64;
const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
@@ -49,6 +49,10 @@
return fabs(x) < DBL_EPSILON_ERR;
}
+inline bool precisely_subdivide_zero(double x) {
+ return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR;
+}
+
inline bool approximately_zero(float x) {
return fabs(x) < FLT_EPSILON;
}
@@ -61,6 +65,10 @@
return fabs(x) < FLT_EPSILON_HALF;
}
+inline bool approximately_zero_double(double x) {
+ return fabs(x) < FLT_EPSILON_DOUBLE;
+}
+
inline bool approximately_zero_squared(double x) {
return fabs(x) < FLT_EPSILON_SQUARED;
}
@@ -69,6 +77,10 @@
return fabs(x) < FLT_EPSILON_SQRT;
}
+inline bool roughly_zero(double x) {
+ return fabs(x) < ROUGH_EPSILON;
+}
+
inline bool approximately_zero_inverse(double x) {
return fabs(x) > FLT_EPSILON_INVERSE;
}
@@ -88,10 +100,18 @@
return precisely_zero(x - y);
}
+inline bool precisely_subdivide_equal(double x, double y) {
+ return precisely_subdivide_zero(x - y);
+}
+
inline bool approximately_equal_half(double x, double y) {
return approximately_zero_half(x - y);
}
+inline bool approximately_equal_double(double x, double y) {
+ return approximately_zero_double(x - y);
+}
+
inline bool approximately_equal_squared(double x, double y) {
return approximately_equal(x, y);
}
@@ -112,14 +132,6 @@
return x - FLT_EPSILON < y;
}
-inline double approximately_pin(double x) {
- return approximately_zero(x) ? 0 : x;
-}
-
-inline float approximately_pin(float x) {
- return approximately_zero(x) ? 0 : x;
-}
-
inline bool approximately_greater_than_one(double x) {
return x > 1 - FLT_EPSILON;
}
@@ -192,8 +204,6 @@
struct SkDCubic;
struct SkDRect;
-#if SK_CONIC_SUPPORT_ENABLED
-
inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
int verb = (1 << points) >> 1;
#ifdef SK_DEBUG
@@ -221,18 +231,6 @@
return points;
}
-#else
-
-inline SkPath::Verb SkOpPointsToVerb(int points) {
- return (SkPath::Verb) (points);
-}
-
-inline SkPath::Verb SkOpVerbToPoints(SkPath::Verb verb) {
- return (int) verb ;
-}
-
-#endif
-
inline double SkDInterp(double A, double B, double t) {
return A + (B - A) * t;
}
diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp
index 003b8c8..ad91c87 100644
--- a/tests/PathOpsAngleTest.cpp
+++ b/tests/PathOpsAngleTest.cpp
@@ -5,6 +5,7 @@
* found in the LICENSE file.
*/
#include "SkOpSegment.h"
+#include "SkTArray.h"
#include "Test.h"
static const SkPoint cubics[][4] = {
@@ -22,11 +23,18 @@
/* 10 */ {{0,1}, {1,3}, {1,0}, {6,4}},
/* 11 */ {{0,1}, {2,3}, {2,1}, {4,3}},
/* 12 */ {{1,2}, {3,4}, {1,0}, {3,2}},
+/* 13 */ {{0,1}, {4,6}, {4,3}, {5,4}},
+/* 14 */ {{806,11419}, {806.962890625,11419}, {807.76690673828125,11418.3193359375}, {807.957275390625,11417.4130859375}},
+/* 15 */ {{808,11417}, {808,11418.1044921875}, {807.10455322265625,11419}, {806,11419}},
+/* 16 */ {{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}},
+/* 17 */ {{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}},
};
static const SkPoint quads[][3] = {
/* 0 */ {{12.3423996f, 228.342407f}, {10, 230.686295f}, {10, 234}},
/* 1 */ {{304.24319458007812f,591.75677490234375f}, {306,593.51470947265625f}, {306,596}},
+/* 2 */ {{0,0}, {3,1}, {0,3}},
+/* 3 */ {{0,1}, {3,1}, {0,2}},
};
static const SkPoint lines[][2] = {
@@ -40,6 +48,7 @@
/* 7 */ {{192,4}, {243,4}},
/* 8 */ {{4,3}, {0,1}},
/* 9 */ {{3,2}, {1,2}},
+/* 10 */ {{6,4}, {3,4}},
};
struct SortSet {
@@ -47,133 +56,214 @@
int ptCount;
double tStart;
double tEnd;
+ SkPoint endPt;
};
static const SortSet set1[] = {
- {cubics[0], 4, 0.66666987081928919, 0.875},
- {lines[0], 2, 0.574070336, 0.388888889},
- {cubics[0], 4, 0.66666987081928919, 0.4050371120499307 },
- {lines[0], 2, 0.574070336, 0.9140625},
+ {cubics[0], 4, 0.66666987081928919, 0.875, {0, 0}},
+ {lines[0], 2, 0.574070336, 0.388888889, {0, 0}},
+ {cubics[0], 4, 0.66666987081928919, 0.4050371120499307, {0, 0}},
+ {lines[0], 2, 0.574070336, 0.9140625, {0, 0}},
+};
+
+static const SortSet set1a[] = {
+ {cubics[0], 4, 0.666666667, 0.405037112, {4.58007812f,2.83203125f}},
+ {lines[0], 2, 0.574074074, 0.9140625, {4.44444466f,2.77777767f}},
};
static const SortSet set2[] = {
- {cubics[0], 4, 0.666666667, 0.875},
- {lines[0], 2, 0.574074074, 0.388888889},
- {cubics[0], 4, 0.666666667, 0.405037112},
- {lines[0], 2, 0.574074074, 0.9140625},
+ {cubics[0], 4, 0.666666667, 0.875, {0, 0}},
+ {lines[0], 2, 0.574074074, 0.388888889, {0, 0}},
+ {cubics[0], 4, 0.666666667, 0.405037112, {0, 0}},
+ {lines[0], 2, 0.574074074, 0.9140625, {0, 0}},
};
static const SortSet set3[] = {
- {cubics[1], 4, 0, 1},
- {quads[0], 3, 1, 0},
+ {cubics[1], 4, 0, 1, {0, 0}},
+ {quads[0], 3, 1, 0, {0, 0}},
};
static const SortSet set4[] = {
- {cubics[2], 4, 0.812114222, 1},
- {cubics[3], 4, 0.0684734759, 0},
+ {cubics[2], 4, 0.812114222, 1, {0, 0}},
+ {cubics[3], 4, 0.0684734759, 0, {0, 0}},
};
static const SortSet set5[] = {
- {lines[1], 2, 0.777777778, 1},
- {quads[1], 3, 1, 4.34137342e-06},
- {lines[2], 2, 0, 1},
+ {lines[1], 2, 0.777777778, 1, {0, 0}},
+ {quads[1], 3, 1, 4.34137342e-06, {0, 0}},
+ {lines[2], 2, 0, 1, {0, 0}},
+};
+
+static const SortSet set5a[] = {
+ {lines[1], 2, 0.777777778, 1, {306,590}},
+ {quads[1], 3, 1, 4.34137342e-06, {304.243195f,591.756775f}},
+ {lines[2], 2, 0, 1, {306,617}},
};
static const SortSet set6[] = {
- {lines[3], 2, 0.407407407, 0.554627832},
- {cubics[4], 4, 0.666666667, 0.548022446},
- {lines[3], 2, 0.407407407, 0},
- {cubics[4], 4, 0.666666667, 1},
+ {lines[3], 2, 0.407407407, 0.554627832, {0, 0}},
+ {cubics[4], 4, 0.666666667, 0.548022446, {0, 0}},
+ {lines[3], 2, 0.407407407, 0, {0, 0}},
+ {cubics[4], 4, 0.666666667, 1, {0, 0}},
+};
+
+static const SortSet set6a[] = {
+ {lines[3], 2, 0.407407407, 0.554627832, {2.6722331f,2.33611655f}},
+ {cubics[4], 4, 0.666666667, 0.548022446, {2.61642241f,2.83718514f}},
+ {lines[3], 2, 0.407407407, 0, {6,4}},
+ {cubics[4], 4, 0.666666667, 1, {6,4}},
};
static const SortSet set7[] = {
- {cubics[5], 4, 0.545233342, 0.545454545},
- {cubics[6], 4, 0.484938134, 0.484805744},
- {cubics[5], 4, 0.545233342, 0},
- {cubics[6], 4, 0.484938134, 0.545454545},
+ {cubics[5], 4, 0.545233342, 0.545454545, {0, 0}},
+ {cubics[6], 4, 0.484938134, 0.484805744, {0, 0}},
+ {cubics[5], 4, 0.545233342, 0, {0, 0}},
+ {cubics[6], 4, 0.484938134, 0.545454545, {0, 0}},
};
static const SortSet set8[] = {
- {cubics[7], 4, 0.5, 0.522986744 },
- {lines[4], 2, 0.75, 1},
- {cubics[7], 4, 0.5, 0},
- {lines[4], 2, 0.75, 0.737654321},
+ {cubics[7], 4, 0.5, 0.522986744, {0, 0}},
+ {lines[4], 2, 0.75, 1, {0, 0}},
+ {cubics[7], 4, 0.5, 0, {0, 0}},
+ {lines[4], 2, 0.75, 0.737654321, {0, 0}},
+};
+
+static const SortSet set8a[] = {
+ {cubics[7], 4, 0.5, 0.522986744, {1.60668361f,0.965592742f}},
+ {lines[4], 2, 0.75, 1, {0,1}},
+ {cubics[7], 4, 0.5, 0, {0,1}},
+ {lines[4], 2, 0.75, 0.737654321, {1.57407403f,1}},
};
static const SortSet set9[] = {
- {cubics[8], 4, 0.4, 1},
- {lines[5], 2, 0.36, 0},
- {cubics[8], 4, 0.4, 0.394675838},
- {lines[5], 2, 0.36, 0.363999782},
+ {cubics[8], 4, 0.4, 1, {0, 0}},
+ {lines[5], 2, 0.36, 0, {0, 0}},
+ {cubics[8], 4, 0.4, 0.394675838, {0, 0}},
+ {lines[5], 2, 0.36, 0.363999782, {0, 0}},
};
static const SortSet set10[] = {
- {lines[6], 2, 0.947368421, 1},
- {cubics[9], 4, 1, 0.500000357},
- {lines[7], 2, 0, 1},
+ {lines[6], 2, 0.947368421, 1, {0, 0}},
+ {cubics[9], 4, 1, 0.500000357, {0, 0}},
+ {lines[7], 2, 0, 1, {0, 0}},
};
static const SortSet set11[] = {
- {lines[3], 2, 0.75, 1},
- {cubics[10], 4, 0.5, 0.228744269},
- {lines[3], 2, 0.75, 0.627112191},
- {cubics[10], 4, 0.5, 0.6339746},
+ {lines[3], 2, 0.75, 1, {0, 0}},
+ {cubics[10], 4, 0.5, 0.228744269, {0, 0}},
+ {lines[3], 2, 0.75, 0.627112191, {0, 0}},
+ {cubics[10], 4, 0.5, 0.6339746, {0, 0}},
};
static const SortSet set12[] = {
- {cubics[12], 4, 0.5, 1},
- {lines[8], 2, 0.5, 1},
- {cubics[11], 4, 0.5, 0},
- {lines[9], 2, 0.5, 1},
- {cubics[12], 4, 0.5, 0},
- {lines[8], 2, 0.5, 0},
- {cubics[11], 4, 0.5, 1},
- {lines[9], 2, 0.5, 0},
+ {cubics[12], 4, 0.5, 1, {0, 0}},
+ {lines[8], 2, 0.5, 1, {0, 0}},
+ {cubics[11], 4, 0.5, 0, {0, 0}},
+ {lines[9], 2, 0.5, 1, {0, 0}},
+ {cubics[12], 4, 0.5, 0, {0, 0}},
+ {lines[8], 2, 0.5, 0, {0, 0}},
+ {cubics[11], 4, 0.5, 1, {0, 0}},
+ {lines[9], 2, 0.5, 0, {0, 0}},
+};
+
+static const SortSet set13[] = {
+ {cubics[13], 4, 0.5, 0.400631046, {0, 0}},
+ {lines[10], 2, 0.791666667, 0.928, {0, 0}},
+ {lines[10], 2, 0.791666667, 0.333333333, {0, 0}},
+ {cubics[13], 4, 0.5, 0.866666667, {0, 0}},
+};
+
+static const SortSet set14[] = {
+ {quads[2], 3, 0.5, 0.310102051, {0, 0}},
+ {quads[3], 3, 0.5, 0.2, {0, 0}},
+ {quads[3], 3, 0.5, 0.770156212, {0, 0}},
+ {quads[2], 3, 0.5, 0.7, {0, 0}},
+};
+
+static const SortSet set15[] = {
+ {cubics[14], 4, 0.93081374, 1, {0, 0}},
+ {cubics[15], 4, 0.188518131, 0, {0, 0}},
+ {cubics[14], 4, 0.93081374, 0, {0, 0}},
+};
+
+static const SortSet set16[] = {
+ {cubics[17], 4, 0.0682619216, 0, {130.042755f,11417.4131f}},
+ {cubics[16], 4, 0.812302088, 1, {130,11417}},
+ {cubics[17], 4, 0.0682619216, 1, {132,11419}},
};
struct SortSetTests {
+ const char* name;
const SortSet* set;
size_t count;
+ SkPoint startPt;
};
+#define TEST_ENTRY(name) #name, name, SK_ARRAY_COUNT(name)
+
static const SortSetTests tests[] = {
- { set12, SK_ARRAY_COUNT(set12) },
- { set11, SK_ARRAY_COUNT(set11) },
- { set10, SK_ARRAY_COUNT(set10) },
- { set9, SK_ARRAY_COUNT(set9) },
- { set8, SK_ARRAY_COUNT(set8) },
- { set7, SK_ARRAY_COUNT(set7) },
- { set6, SK_ARRAY_COUNT(set6) },
- { set2, SK_ARRAY_COUNT(set2) },
- { set5, SK_ARRAY_COUNT(set5) },
- { set4, SK_ARRAY_COUNT(set4) },
- { set3, SK_ARRAY_COUNT(set3) },
- { set1, SK_ARRAY_COUNT(set1) },
+ { TEST_ENTRY(set16), {130.090179f,11417.5957f} },
+// { TEST_ENTRY(set15), {0, 0}},
+ { TEST_ENTRY(set14), {0, 0}},
+ { TEST_ENTRY(set13), {0, 0}},
+ { TEST_ENTRY(set12), {0, 0}},
+ { TEST_ENTRY(set11), {0, 0}},
+ { TEST_ENTRY(set10), {0, 0}},
+ { TEST_ENTRY(set9), {0, 0}},
+ { TEST_ENTRY(set6a), {3.55555558f,2.77777767f} },
+ { TEST_ENTRY(set8a), {1.5f,1} },
+ { TEST_ENTRY(set8), {0, 0}},
+ { TEST_ENTRY(set7), {0, 0}},
+ { TEST_ENTRY(set6a), {3.55555558f,2.77777767f} },
+ { TEST_ENTRY(set6), {0, 0}},
+ { TEST_ENTRY(set5a), {306,596} },
+ { TEST_ENTRY(set5), {0, 0}},
+// { TEST_ENTRY(set4), {0, 0}},
+ { TEST_ENTRY(set3), {0, 0}},
+ { TEST_ENTRY(set2), {0, 0}},
+// { TEST_ENTRY(set1a), {3.70370364f,3.14814806f} },
+ { TEST_ENTRY(set1), {0, 0}},
};
-static void setup(const SortSet* set, const size_t idx, SkPoint const ** data,
- SkOpSegment* seg, int* ts) {
+#undef TEST_ENTRY
+
+static void setup(const SortSet* set, const size_t idx,
+ SkOpSegment* seg, int* ts, const SkPoint& startPt) {
SkPoint start, end;
- *data = set[idx].ptData;
+ const SkPoint* data = set[idx].ptData;
+ bool useIntersectPt = startPt.fX != 0 || startPt.fY != 0;
+ if (useIntersectPt) {
+ start = startPt;
+ end = set[idx].endPt;
+ }
switch(set[idx].ptCount) {
case 2: {
- seg->addLine(*data, false, false);
+ seg->addLine(data, false, false);
SkDLine dLine;
dLine.set(set[idx].ptData);
+ if (useIntersectPt) {
+ break;
+ }
start = dLine.xyAtT(set[idx].tStart).asSkPoint();
end = dLine.xyAtT(set[idx].tEnd).asSkPoint();
} break;
case 3: {
- seg->addQuad(*data, false, false);
+ seg->addQuad(data, false, false);
SkDQuad dQuad;
dQuad.set(set[idx].ptData);
+ if (useIntersectPt) {
+ break;
+ }
start = dQuad.xyAtT(set[idx].tStart).asSkPoint();
end = dQuad.xyAtT(set[idx].tEnd).asSkPoint();
} break;
case 4: {
- seg->addCubic(*data, false, false);
+ seg->addCubic(data, false, false);
SkDCubic dCubic;
dCubic.set(set[idx].ptData);
+ if (useIntersectPt) {
+ break;
+ }
start = dCubic.xyAtT(set[idx].tStart).asSkPoint();
end = dCubic.xyAtT(set[idx].tEnd).asSkPoint();
} break;
@@ -182,13 +272,11 @@
double tEnd = set[idx].tEnd;
seg->addT(NULL, start, tStart);
seg->addT(NULL, end, tEnd);
- double tLeft = tStart < tEnd ? 0 : 1;
- if (tStart != tLeft && tEnd != tLeft) {
- seg->addT(NULL, set[idx].ptData[0], tLeft);
+ if (tStart != 0 && tEnd != 0) {
+ seg->addT(NULL, set[idx].ptData[0], 0);
}
- double tRight = tStart < tEnd ? 1 : 0;
- if (tStart != tRight && tEnd != tRight) {
- seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], tRight);
+ if (tStart != 1 && tEnd != 1) {
+ seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1);
}
int tIndex = 0;
do {
@@ -207,30 +295,153 @@
static void PathOpsAngleTest(skiatest::Reporter* reporter) {
for (size_t index = 0; index < SK_ARRAY_COUNT(tests); ++index) {
const SortSetTests& test = tests[index];
- for (size_t idxL = 0; idxL < test.count - 1; ++idxL) {
- SkOpSegment lesser, greater;
- int lesserTs[2], greaterTs[2];
- const SkPoint* lesserData, * greaterData;
+ SkTDArray<SkOpAngle> angles;
+ bool unsortable = false;
+ bool unorderable = false;
+ SkTArray<SkOpSegment> segs;
+ for (size_t idx = 0; idx < test.count; ++idx) {
+ int ts[2];
const SortSet* set = test.set;
- setup(set, idxL, &lesserData, &lesser, lesserTs);
- size_t idxG = idxL + 1;
- setup(set, idxG, &greaterData, &greater, greaterTs);
- SkOpAngle first, second;
- first.set(lesserData, SkPathOpsPointsToVerb(set[idxL].ptCount - 1), &lesser,
- lesserTs[0], lesserTs[1], lesser.spans());
- second.set(greaterData, SkPathOpsPointsToVerb(set[idxG].ptCount - 1), &greater,
- greaterTs[0], greaterTs[1], greater.spans());
- bool compare = first < second;
- if (!compare) {
- SkDebugf("%s test[%d]: lesser[%d] > greater[%d]\n", __FUNCTION__,
- index, idxL, idxG);
- compare = first < second;
+ SkOpSegment& seg = segs.push_back();
+ setup(set, idx, &seg, ts, test.startPt);
+ SkOpAngle* angle = angles.append();
+ angle->set(&seg, ts[0], ts[1]);
+#if DEBUG_ANGLE
+ angle->setID(idx);
+#endif
+ if (angle->unsortable()) {
+#if DEBUG_ANGLE
+ SkDebugf("%s test[%s]: angle[%d] unsortable\n", __FUNCTION__, test.name, idx);
+#endif
+ unsortable = true;
}
- REPORTER_ASSERT(reporter, compare);
+ if (angle->unorderable()) {
+#if DEBUG_ANGLE
+ SkDebugf("%s test[%s]: angle[%d] unorderable\n", __FUNCTION__, test.name, idx);
+#endif
+ unorderable = true;
+ }
reporter->bumpTestCount();
}
+ if (unsortable || unorderable) {
+ continue;
+ }
+#if DEBUG_ANGLE
+ SkDebugf("%s test[%s]\n", __FUNCTION__, test.name);
+#endif
+ for (size_t idxL = 0; idxL < test.count; ++idxL) {
+ const SkOpAngle& first = angles[idxL];
+ for (size_t idxG = 0; idxG < test.count; ++idxG) {
+ if (idxL == idxG) {
+ continue;
+ }
+ const SkOpAngle& second = angles[idxG];
+ bool compare = first < second;
+ if (idxL < idxG) {
+ if (!compare) {
+ SkDebugf("%s test[%s]: first[%d] > second[%d]\n", __FUNCTION__,
+ test.name, idxL, idxG);
+ compare = first < second;
+ }
+ REPORTER_ASSERT(reporter, compare);
+ } else {
+ SkASSERT(idxL > idxG);
+ if (compare) {
+ SkDebugf("%s test[%s]: first[%d] < second[%d]\n", __FUNCTION__,
+ test.name, idxL, idxG);
+ compare = first < second;
+ }
+ REPORTER_ASSERT(reporter, !compare);
+ }
+ compare = second < first;
+ if (idxL < idxG) {
+ if (compare) {
+ SkDebugf("%s test[%s]: second[%d] < first[%d]\n", __FUNCTION__,
+ test.name, idxL, idxG);
+ compare = second < first;
+ }
+ REPORTER_ASSERT(reporter, !compare);
+ } else {
+ SkASSERT(idxL > idxG);
+ if (!compare) {
+ SkDebugf("%s test[%s]: second[%d] > first[%d]\n", __FUNCTION__,
+ test.name, idxL, idxG);
+ compare = second < first;
+ }
+ REPORTER_ASSERT(reporter, compare);
+ }
+ }
+ }
+ reporter->bumpTestCount();
}
}
+#if 0
+static int find_slop(double x, double y, double rx, double ry) {
+ int slopBits = 0;
+ bool less1, less2;
+ double absX = fabs(x);
+ double absY = fabs(y);
+ double length = absX < absY ? absX / 2 + absY : absX + absY / 2;
+ int exponent;
+ (void) frexp(length, &exponent);
+ double epsilon = ldexp(FLT_EPSILON, exponent);
+ do {
+ // get the length as the larger plus half the smaller (both same signs)
+ // find the ulps of the length
+ // compute the offsets from there
+ double xSlop = epsilon * slopBits;
+ double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ?
+ double x1 = x - xSlop;
+ double y1 = y + ySlop;
+ double x_ry1 = x1 * ry;
+ double rx_y1 = rx * y1;
+ less1 = x_ry1 < rx_y1;
+ double x2 = x + xSlop;
+ double y2 = y - ySlop;
+ double x_ry2 = x2 * ry;
+ double rx_y2 = rx * y2;
+ less2 = x_ry2 < rx_y2;
+ } while (less1 == less2 && ++slopBits);
+ return slopBits;
+}
+
+// from http://stackoverflow.com/questions/1427422/cheap-algorithm-to-find-measure-of-angle-between-vectors
+static double diamond_angle(double y, double x)
+{
+ if (y >= 0)
+ return (x >= 0 ? y/(x+y) : 1-x/(-x+y));
+ else
+ return (x < 0 ? 2-y/(-x-y) : 3+x/(x-y));
+}
+
+static const double slopTests[][4] = {
+ // x y rx ry
+ {-0.058554756452593892, -0.18804585843827226, -0.018568569646021160, -0.059615294434479438},
+ {-0.0013717412948608398, 0.0041152238845825195, -0.00045837944195925573, 0.0013753175735478074},
+ {-2.1033774145221198, -1.4046019261273715e-008, -0.70062688352066704, -1.2706324683777995e-008},
+};
+
+static void PathOpsAngleFindSlop(skiatest::Reporter* reporter) {
+ for (size_t index = 0; index < SK_ARRAY_COUNT(slopTests); ++index) {
+ const double* slopTest = slopTests[index];
+ double x = slopTest[0];
+ double y = slopTest[1];
+ double rx = slopTest[2];
+ double ry = slopTest[3];
+ SkDebugf("%s xy %d=%d\n", __FUNCTION__, (int) index, find_slop(x, y, rx, ry));
+ SkDebugf("%s rxy %d=%d\n", __FUNCTION__, (int) index, find_slop(rx, ry, x, y));
+ double angle = diamond_angle(y, x);
+ double rAngle = diamond_angle(ry, rx);
+ double diff = fabs(angle - rAngle);
+ SkDebugf("%s diamond xy=%1.9g rxy=%1.9g diff=%1.9g factor=%d\n", __FUNCTION__,
+ angle, rAngle, diff, (int) (diff / FLT_EPSILON));
+
+ }
+}
+#endif
+
#include "TestClassDef.h"
DEFINE_TESTCLASS_SHORT(PathOpsAngleTest)
+
+// DEFINE_TESTCLASS_SHORT(PathOpsAngleFindSlop)
diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp
index 58d7d98..b0d6bd8 100644
--- a/tests/PathOpsCubicIntersectionTest.cpp
+++ b/tests/PathOpsCubicIntersectionTest.cpp
@@ -163,6 +163,12 @@
const size_t testSetCount = SK_ARRAY_COUNT(testSet);
static const SkDCubic newTestSet[] = {
+{{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}},
+{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
+
+{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
+{{{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}}},
+
{{{0, 1}, {2, 3}, {5, 1}, {4, 3}}},
{{{1, 5}, {3, 4}, {1, 0}, {3, 2}}},
@@ -231,10 +237,10 @@
static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const SkDCubic& cubic2) {
#if ONE_OFF_DEBUG
SkDebugf("computed quadratics given\n");
- SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n",
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY,
cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY);
- SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n",
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY,
cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY);
#endif
@@ -244,7 +250,7 @@
SkDebugf("computed quadratics set 1\n");
for (int index = 0; index < quads1.count(); ++index) {
const SkDQuad& q = quads1[index];
- SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX, q[0].fY,
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY,
q[1].fX, q[1].fY, q[2].fX, q[2].fY);
}
#endif
@@ -254,7 +260,7 @@
SkDebugf("computed quadratics set 2\n");
for (int index = 0; index < quads2.count(); ++index) {
const SkDQuad& q = quads2[index];
- SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX, q[0].fY,
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY,
q[1].fX, q[1].fY, q[2].fX, q[2].fY);
}
#endif
@@ -267,12 +273,15 @@
xy1 = cubic1.xyAtT(tt1);
tt2 = intersections[1][pt3];
xy2 = cubic2.xyAtT(tt2);
+ const SkDPoint& iPt = intersections.pt(pt3);
#if ONE_OFF_DEBUG
SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
- __FUNCTION__, tt1, xy1.fX, xy1.fY, intersections.pt(pt3).fX,
- intersections.pt(pt3).fY, xy2.fX, xy2.fY, tt2);
+ __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX,
+ iPt.fY, xy2.fX, xy2.fY, tt2);
#endif
- REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
+ REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt));
+ REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt));
+ REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
}
}
diff --git a/tests/PathOpsCubicToQuadsTest.cpp b/tests/PathOpsCubicToQuadsTest.cpp
index f18784f..f738e07 100644
--- a/tests/PathOpsCubicToQuadsTest.cpp
+++ b/tests/PathOpsCubicToQuadsTest.cpp
@@ -20,7 +20,7 @@
double precision = cubic.calcPrecision();
SkTDArray<SkDQuad> quads;
CubicToQuads(cubic, precision, quads);
- if (quads.count() != 1) {
+ if (quads.count() != 1 && quads.count() != 2) {
SkDebugf("%s [%d] cubic to quadratics failed count=%d\n", name, static_cast<int>(index),
quads.count());
}
@@ -36,11 +36,11 @@
double precision = cubic.calcPrecision();
SkTDArray<SkDQuad> quads;
CubicToQuads(cubic, precision, quads);
- if (quads.count() != 1) {
+ if (quads.count() != 1 && quads.count() != 2) {
SkDebugf("%s [%d] cubic to quadratics failed count=%d\n", name, static_cast<int>(index),
quads.count());
}
- REPORTER_ASSERT(reporter, quads.count() == 1);
+ REPORTER_ASSERT(reporter, quads.count() <= 2);
}
}
diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp
index 71631c1..a9ca58b 100644
--- a/tests/PathOpsExtendedTest.cpp
+++ b/tests/PathOpsExtendedTest.cpp
@@ -45,27 +45,27 @@
static bool gComparePathsAssert = true;
static bool gPathStrAssert = true;
-static void showPathContours(SkPath::Iter& iter) {
+static void showPathContours(SkPath::Iter& iter, const char* suffix) {
uint8_t verb;
SkPoint pts[4];
while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
switch (verb) {
case SkPath::kMove_Verb:
- SkDebugf("path.moveTo(%1.9g,%1.9g);\n", pts[0].fX, pts[0].fY);
+ SkDebugf(" path%s.moveTo(%1.9g,%1.9g);\n", suffix, pts[0].fX, pts[0].fY);
continue;
case SkPath::kLine_Verb:
- SkDebugf("path.lineTo(%1.9g,%1.9g);\n", pts[1].fX, pts[1].fY);
+ SkDebugf(" path%s.lineTo(%1.9g,%1.9g);\n", suffix, pts[1].fX, pts[1].fY);
break;
case SkPath::kQuad_Verb:
- SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
+ SkDebugf(" path%s.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", suffix,
pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
break;
case SkPath::kCubic_Verb:
- SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
+ SkDebugf(" path%s.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", suffix,
pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY);
break;
case SkPath::kClose_Verb:
- SkDebugf("path.close();\n");
+ SkDebugf(" path%s.close();\n", suffix);
break;
default:
SkDEBUGFAIL("bad verb");
@@ -74,11 +74,6 @@
}
}
-void showPath(const SkPath& path, const char* str) {
- SkDebugf("%s\n", !str ? "original:" : str);
- showPath(path);
-}
-
static const char* fillTypeStr[] = {
"kWinding_FillType",
"kEvenOdd_FillType",
@@ -86,7 +81,7 @@
"kInverseEvenOdd_FillType"
};
-void showPath(const SkPath& path) {
+static void showPath(const SkPath& path, const char* suffix) {
SkPath::Iter iter(path, true);
#define SUPPORT_RECT_CONTOUR_DETECTION 0
#if SUPPORT_RECT_CONTOUR_DETECTION
@@ -108,12 +103,13 @@
#endif
SkPath::FillType fillType = path.getFillType();
SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
- SkDebugf("path.setFillType(%s);\n", fillTypeStr[fillType]);
+ SkDebugf(" path%s.setFillType(SkPath::%s);\n", suffix, fillTypeStr[fillType]);
iter.setPath(path, true);
- showPathContours(iter);
+ showPathContours(iter, suffix);
}
-void showPathData(const SkPath& path) {
+#if DEBUG_SHOW_TEST_NAME
+static void showPathData(const SkPath& path) {
SkPath::Iter iter(path, true);
uint8_t verb;
SkPoint pts[4];
@@ -142,6 +138,7 @@
}
}
}
+#endif
void showOp(const SkPathOp op) {
switch (op) {
@@ -165,6 +162,7 @@
}
}
+#if 0
static void showPath(const SkPath& path, const char* str, const SkMatrix& scale) {
SkPath scaled;
SkMatrix inverse;
@@ -175,6 +173,7 @@
path.transform(inverse, &scaled);
showPath(scaled, str);
}
+#endif
#if DEBUG_SHOW_TEST_NAME
static char hexorator(int x) {
@@ -326,8 +325,8 @@
static void showSimplifiedPath(const SkPath& one, const SkPath& two,
const SkPath& scaledOne, const SkPath& scaledTwo) {
- showPath(one, "original:");
- showPath(two, "simplified:");
+ showPath(one, "");
+ // showPath(two, "simplified:");
drawAsciiPaths(scaledOne, scaledTwo, true);
}
@@ -355,12 +354,15 @@
const SkPath& scaledOne, const SkPath& scaledTwo, const SkPathOp shapeOp,
const SkMatrix& scale) {
SkASSERT((unsigned) shapeOp < SK_ARRAY_COUNT(opStrs));
- showPath(a, "minuend:");
- SkDebugf("op: %s\n", opStrs[shapeOp]);
- showPath(b, "subtrahend:");
+ SkDebugf("static void xOp#%s(skiatest::Reporter* reporter) {\n", opSuffixes[shapeOp]);
+ SkDebugf(" SkPath path, pathB;\n");
+ showPath(a, "");
+ showPath(b, "B");
+ SkDebugf(" testPathOp(reporter, path, pathB, %s);\n", opStrs[shapeOp]);
+ SkDebugf("}\n");
// the region often isn't very helpful since it approximates curves with a lot of line-tos
- if (0) showPath(scaledOne, "region:", scale);
- showPath(two, "op result:");
+ // if (0) showPath(scaledOne, "region:", scale);
+ // showPath(two, "op result:");
drawAsciiPaths(scaledOne, scaledTwo, true);
}
@@ -448,7 +450,7 @@
SkPath::FillType fillType = useXor ? SkPath::kEvenOdd_FillType : SkPath::kWinding_FillType;
path.setFillType(fillType);
if (gShowPath) {
- showPath(path);
+ showPath(path, "");
}
if (!Simplify(path, &out)) {
SkDebugf("%s did not expect failure\n", __FUNCTION__);
diff --git a/tests/PathOpsExtendedTest.h b/tests/PathOpsExtendedTest.h
index 5644c94..5e91dc1 100644
--- a/tests/PathOpsExtendedTest.h
+++ b/tests/PathOpsExtendedTest.h
@@ -26,9 +26,6 @@
extern int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap);
extern bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths);
extern void showOp(const SkPathOp op);
-extern void showPath(const SkPath& path, const char* str);
-extern void showPath(const SkPath& path);
-extern void showPathData(const SkPath& path);
extern bool testPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkPath& b,
const SkPathOp );
extern bool testSimplify(SkPath& path, bool useXor, SkPath& out, PathOpsThreadState& state,
diff --git a/tests/PathOpsLineParametetersTest.cpp b/tests/PathOpsLineParametetersTest.cpp
index 0361e1a..3b223ae 100644
--- a/tests/PathOpsLineParametetersTest.cpp
+++ b/tests/PathOpsLineParametetersTest.cpp
@@ -40,7 +40,7 @@
for (size_t index = 0; index < tests_count; ++index) {
SkLineParameters lineParameters;
const SkDCubic& cubic = tests[index];
- lineParameters.cubicEndPoints(cubic);
+ lineParameters.cubicEndPoints(cubic, 0, 3);
double denormalizedDistance[2];
denormalizedDistance[0] = lineParameters.controlPtDistance(cubic, 1);
denormalizedDistance[1] = lineParameters.controlPtDistance(cubic, 2);
diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp
index 48ed866..9a48f78 100644
--- a/tests/PathOpsOpTest.cpp
+++ b/tests/PathOpsOpTest.cpp
@@ -1385,6 +1385,21 @@
testPathOp(reporter, path, pathB, kDifference_PathOp);
}
+static void cubicOp74d(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,5, 5,1, 5,1);
+ path.lineTo(0,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,5);
+ pathB.cubicTo(1,5, 1,0, 5,1);
+ pathB.lineTo(1,5);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kDifference_PathOp);
+}
+
static void cubicOp75d(skiatest::Reporter* reporter) {
SkPath path, pathB;
path.setFillType(SkPath::kWinding_FillType);
@@ -1400,6 +1415,19 @@
testPathOp(reporter, path, pathB, kDifference_PathOp);
}
+static void cubicOp76u(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(0,2, 2,0, 5,3);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(3,5, 1,0, 2,0);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kUnion_PathOp);
+}
+
static void cubicOp77i(skiatest::Reporter* reporter) {
SkPath path, pathB;
path.setFillType(SkPath::kEvenOdd_FillType);
@@ -1430,19 +1458,6 @@
testPathOp(reporter, path, pathB, kUnion_PathOp);
}
-static void cubicOp79d(skiatest::Reporter* reporter) {
- SkPath path, pathB;
- path.setFillType(SkPath::kWinding_FillType);
- path.moveTo(0,2);
- path.cubicTo(0,1, 3,-0.1f, 1,0);
- path.close();
- pathB.setFillType(SkPath::kWinding_FillType);
- pathB.moveTo(0,3);
- pathB.cubicTo(0,1, 2,0, 1,0);
- pathB.close();
- testPathOp(reporter, path, pathB, kDifference_PathOp);
-}
-
static void cubicOp79u(skiatest::Reporter* reporter) {
SkPath path, pathB;
path.setFillType(SkPath::kWinding_FillType);
@@ -1471,6 +1486,19 @@
testPathOp(reporter, path, pathB, kIntersect_PathOp);
}
+static void cubicOp81d(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(4,6, 4,3, 5,4);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(3,4);
+ pathB.cubicTo(4,5, 1,0, 6,4);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kDifference_PathOp);
+}
+
static void cubicOp82i(skiatest::Reporter* reporter) {
SkPath path, pathB;
path.setFillType(SkPath::kEvenOdd_FillType);
@@ -1486,30 +1514,110 @@
testPathOp(reporter, path, pathB, kIntersect_PathOp);
}
-static void cubicOp81d(skiatest::Reporter* reporter) {
+static void cubicOp83i(skiatest::Reporter* reporter) {
SkPath path, pathB;
path.setFillType(SkPath::kWinding_FillType);
path.moveTo(0,1);
- path.cubicTo(4,6, 4,3, 5,4);
+ path.cubicTo(0,3, 2,1, 4,1);
+ path.lineTo(0,1);
path.close();
pathB.setFillType(SkPath::kWinding_FillType);
- pathB.moveTo(3,4);
- pathB.cubicTo(4,5, 1,0, 6,4);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(1,4, 1,0, 3,0);
+ pathB.lineTo(1,2);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void cubicOp84d(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,4);
+ path.cubicTo(2,3, 6,3, 3,2);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(3,6);
+ pathB.cubicTo(2,3, 4,0, 3,2);
pathB.close();
testPathOp(reporter, path, pathB, kDifference_PathOp);
}
-static void (*firstTest)(skiatest::Reporter* ) = cubicOp81d;
+static void skpClip1(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(1126.17114f, 877.171204f);
+ path.quadTo(1127.34314f, 876.000000f, 1129.00000f, 876.000000f);
+ path.lineTo(1243.00000f, 876.000000f);
+ path.quadTo(1244.65686f, 876.000000f, 1245.82886f, 877.171204f);
+ path.quadTo(1247.00000f, 878.343140f, 1247.00000f, 880.000000f);
+ path.lineTo(1247.00000f, 907.000000f);
+ path.lineTo(1246.00000f, 907.000000f);
+ path.lineTo(1246.00000f, 880.000000f);
+ path.cubicTo(1246.00000f, 878.343140f, 1244.65686f, 877.000000f, 1243.00000f, 877.000000f);
+ path.lineTo(1129.00000f, 877.000000f);
+ path.cubicTo(1127.34314f, 877.000000f, 1126.00000f, 878.343140f, 1126.00000f, 880.000000f);
+ path.lineTo(1126.00000f, 907.000000f);
+ path.lineTo(1125.00000f, 907.000000f);
+ path.lineTo(1125.00000f, 880.000000f);
+ path.quadTo(1125.00000f, 878.343140f, 1126.17114f, 877.171204f);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1247.00000f, 876.000000f);
+ pathB.lineTo(1231.00000f, 892.000000f);
+ pathB.lineTo(1246.00000f, 907.000000f);
+ pathB.lineTo(1247.00000f, 907.000000f);
+ pathB.lineTo(1247.00000f, 876.000000f);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+#if 1 // FIXME: work in progress -- coincident cubic undetected
+static void skpClip2(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(134.000000f, 11414.0000f);
+ path.cubicTo(131.990234f, 11414.0000f, 130.326660f, 11415.4824f, 130.042755f, 11417.4131f);
+ path.cubicTo(130.233124f, 11418.3193f, 131.037079f, 11419.0000f, 132.000000f, 11419.0000f);
+ path.lineTo(806.000000f, 11419.0000f);
+ path.cubicTo(806.962891f, 11419.0000f, 807.766907f, 11418.3193f, 807.957275f, 11417.4131f);
+ path.cubicTo(807.673401f, 11415.4824f, 806.009766f, 11414.0000f, 804.000000f, 11414.0000f);
+ path.lineTo(134.000000f, 11414.0000f);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kInverseWinding_FillType);
+ pathB.moveTo(132.000000f, 11415.0000f);
+ pathB.lineTo(806.000000f, 11415.0000f);
+ pathB.cubicTo(807.104553f, 11415.0000f, 808.000000f, 11415.4473f, 808.000000f, 11416.0000f);
+ pathB.lineTo(808.000000f, 11417.0000f);
+ pathB.cubicTo(808.000000f, 11418.1045f, 807.104553f, 11419.0000f, 806.000000f, 11419.0000f);
+ pathB.lineTo(132.000000f, 11419.0000f);
+ pathB.cubicTo(130.895432f, 11419.0000f, 130.000000f, 11418.1045f, 130.000000f, 11417.0000f);
+ pathB.lineTo(130.000000f, 11416.0000f);
+ pathB.cubicTo(130.000000f, 11415.4473f, 130.895432f, 11415.0000f, 132.000000f, 11415.0000f);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+#endif
+
+static void (*firstTest)(skiatest::Reporter* ) = 0;
static struct TestDesc tests[] = {
+#if 1 // FIXME: work in progress -- coincident cubic undetected
+ TEST(skpClip2),
+#endif
+ TEST(skpClip1),
+ TEST(cubicOp84d),
+ TEST(cubicOp83i),
TEST(cubicOp82i),
TEST(cubicOp81d),
TEST(cubicOp80i),
TEST(cubicOp79u),
- TEST(cubicOp79d),
TEST(cubicOp78u),
TEST(cubicOp77i),
+ TEST(cubicOp76u),
TEST(cubicOp75d),
+ TEST(cubicOp74d),
TEST(cubicOp73d),
TEST(cubicOp72i),
TEST(cubicOp71d),
diff --git a/tests/PathOpsQuadIntersectionTest.cpp b/tests/PathOpsQuadIntersectionTest.cpp
index 4276051..4bb0b34 100644
--- a/tests/PathOpsQuadIntersectionTest.cpp
+++ b/tests/PathOpsQuadIntersectionTest.cpp
@@ -50,6 +50,19 @@
}
static const SkDQuad testSet[] = {
+ {{{131.37418,11414.9825}, {130.28798,11415.9328}, {130.042755,11417.4131}}},
+ {{{130.585787,11418.4142}, {130.021447,11417.8498}, {130,11417}}},
+
+ {{{130.73167037963867, 11418.546386718750}, {131.26360225677490, 11418.985778808592},
+ {132, 11419 }}},
+ {{{132, 11419}, {131.15012693405151, 11418.978546142578},
+ {130.58578681945801, 11418.414184570313}}},
+
+ {{{132, 11419},
+ {130.73167037963867, 11418.546386718750}, {131.26360225677490, 11418.985778808592}}},
+ {{{131.15012693405151, 11418.978546142578},
+ {130.58578681945801, 11418.414184570313}, {132, 11419}}},
+
{{{3.0774019473063863, 3.35198509346713}, {3.0757503498668397, 3.327320623945933},
{3.0744102085015879, 3.3025879417907196}}},
{{{3.053913680774329, 3.3310471586283938}, {3.0758730889691694, 3.3273466070370152},
@@ -252,7 +265,7 @@
}
static void QuadraticIntersection_OneOffTest(skiatest::Reporter* reporter) {
- oneOffTest1(reporter, 43, 47);
+ oneOffTest1(reporter, 0, 1);
}
static void oneOffTests(skiatest::Reporter* reporter) {
diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp
index f4a332e..fe5f4e1 100644
--- a/tests/PathOpsSimplifyTest.cpp
+++ b/tests/PathOpsSimplifyTest.cpp
@@ -3772,9 +3772,51 @@
testSimplify(reporter, path);
}
-static void (*firstTest)(skiatest::Reporter* ) = testQuadratic85;
+static void testQuadLineIntersect1(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(3, 1, 0, 3);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(0, 1);
+ path.quadTo(3, 1, 0, 2);
+ path.close();
+ testSimplify(reporter, path);
+}
+
+static void testQuadLineIntersect2(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(3, 1, 0, 3);
+ path.lineTo(0, 3);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(0, 1);
+ path.quadTo(3, 1, 0, 2);
+ path.close();
+ testSimplify(reporter, path);
+}
+
+static void testQuadLineIntersect3(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(3, 1, 0, 3);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(0, 1);
+ path.quadTo(3, 1, 0, 2);
+ path.close();
+ testSimplify(reporter, path);
+}
+
+static void (*firstTest)(skiatest::Reporter* ) = 0;
static TestDesc tests[] = {
+ TEST(testQuadLineIntersect1),
+ TEST(testQuadLineIntersect2),
+ TEST(testQuadLineIntersect3),
TEST(testQuad7),
TEST(testQuad6),
TEST(testQuad5),
diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp
index d14cde5..98e5553 100644
--- a/tests/PathOpsSkpClipTest.cpp
+++ b/tests/PathOpsSkpClipTest.cpp
@@ -1,6 +1,7 @@
#include "SkBitmap.h"
#include "SkDevice.h"
#include "SkCanvas.h"
+#include "SkImageDecoder.h"
#include "SkImageEncoder.h"
#include "SkStream.h"
#include "SkOSFile.h"
@@ -18,14 +19,14 @@
}
static void PathOpsSkpClipTest(skiatest::Reporter* reporter) {
-const char pictDir[] = "C:\\Users\\caryclark\\skp";
- const char outSkpClipDir[] = "C:\\Users\\caryclark\\skpClip";
- const char outOldClipDir[] = "C:\\Users\\caryclark\\oldClip";
+ const char pictDir[] = "D:\\skp";
+ const char outSkpClipDir[] = "D:\\skpClip";
+ const char outOldClipDir[] = "D:\\oldClip";
SkOSFile::Iter iter(pictDir, "skp");
SkString filename;
while (iter.next(&filename)) {
-#if 0
- if (strcmp(filename.c_str(), "tabl_androidpolice.skp")) {
+#if 01
+ if (strcmp(filename.c_str(), "desk_15min-lt.skp")) {
continue;
}
#endif
@@ -35,7 +36,11 @@
if (!stream.isValid()) {
continue;
}
- SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream));
+ bool success;
+ SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream, &success, &SkImageDecoder::DecodeMemory));
+ if (!success) {
+ continue;
+ }
int width = pic->width();
int height = pic->height();
SkBitmap bitmap;
diff --git a/tests/PathOpsTestCommon.cpp b/tests/PathOpsTestCommon.cpp
index 86f6859..aab7d6e 100644
--- a/tests/PathOpsTestCommon.cpp
+++ b/tests/PathOpsTestCommon.cpp
@@ -10,7 +10,7 @@
void CubicToQuads(const SkDCubic& cubic, double precision, SkTDArray<SkDQuad>& quads) {
SkTDArray<double> ts;
cubic.toQuadraticTs(precision, &ts);
- if (ts.count() <= 1) {
+ if (ts.count() <= 0) {
SkDQuad quad = cubic.toQuad();
*quads.append() = quad;
return;