aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--experimental/Intersection/DataTypes.h9
-rw-r--r--experimental/Intersection/EdgeDemo.cpp26
-rw-r--r--experimental/Intersection/EdgeDemoApp.mm2
-rw-r--r--experimental/Intersection/Intersection_Tests.cpp3
-rw-r--r--experimental/Intersection/Intersection_Tests.h1
-rw-r--r--experimental/Intersection/MiniSimplify_Test.cpp89
-rw-r--r--experimental/Intersection/QuadraticIntersection_Test.cpp71
-rw-r--r--experimental/Intersection/QuarticRoot.cpp17
-rw-r--r--experimental/Intersection/Simplify.cpp152
-rw-r--r--experimental/Intersection/bc.htm11
-rw-r--r--experimental/Intersection/op.htm193
11 files changed, 478 insertions, 96 deletions
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index 6c2ac53595..e9543d1a5d 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -69,6 +69,11 @@ inline bool approximately_zero(double x) {
return fabs(x) < FLT_EPSILON;
}
+inline bool precisely_zero(double x) {
+
+ return fabs(x) < DBL_EPSILON;
+}
+
inline bool approximately_zero(float x) {
return fabs(x) < FLT_EPSILON;
@@ -118,6 +123,10 @@ inline bool approximately_negative(double x) {
return x < FLT_EPSILON;
}
+inline bool precisely_negative(double x) {
+ return x < DBL_EPSILON;
+}
+
inline bool approximately_one_or_less(double x) {
return x < 1 + FLT_EPSILON;
}
diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp
index 329f8e3b92..7870764e05 100644
--- a/experimental/Intersection/EdgeDemo.cpp
+++ b/experimental/Intersection/EdgeDemo.cpp
@@ -220,23 +220,22 @@ static void tryRoncoOnce(const SkPath& path, const SkRect& target, bool show) {
if (!closed) {
tiny.close();
}
- if (show) {
+ if (false && show) {
showPath(tiny, NULL);
SkDebugf("simplified:\n");
}
- SkPath out;
- simplifyx(tiny, out);
+ testSimplifyx(tiny);
}
static void tryRonco(const SkPath& path) {
const SkRect& overall = path.getBounds();
- const int divs = 50;
+ const int divs = 4;
SkScalar cellWidth = overall.width() / divs * 2;
SkScalar cellHeight = overall.height() / divs * 2;
SkRect target;
if (true) {
- int xDiv = 21;
- int yDiv = 9;
+ int xDiv = 1;
+ int yDiv = 2;
target.setXYWH(overall.fLeft + (overall.width() - cellWidth) * xDiv / divs,
overall.fTop + (overall.height() - cellHeight) * yDiv / divs,
cellWidth, cellHeight);
@@ -247,7 +246,7 @@ static void tryRonco(const SkPath& path) {
target.setXYWH(overall.fLeft + (overall.width() - cellWidth) * xDiv / divs,
overall.fTop + (overall.height() - cellHeight) * yDiv / divs,
cellWidth, cellHeight);
- tryRoncoOnce(path, target, false);
+ tryRoncoOnce(path, target, true);
}
}
}
@@ -281,22 +280,21 @@ static bool drawLetters(SkCanvas* canvas, int step, bool useOld)
#if 0
for (int mask = 0; mask < 1 << testStrLen; ++mask) {
char maskStr[testStrLen];
- // mask = 26;
+ mask = 12;
for (int letter = 0; letter < testStrLen; ++letter) {
maskStr[letter] = mask & (1 << letter) ? testStr[letter] : ' ';
}
paint.getPosTextPath(maskStr, testStrLen, textPos, &path);
- showPath(path, NULL);
- SkDebugf("%d simplified:\n", mask);
- SkPath out;
- simplifyx(path, out);
+ // showPath(path, NULL);
+ // SkDebugf("%d simplified:\n", mask);
+ testSimplifyx(path);
}
#endif
paint.getPosTextPath(testStr, testStrLen, textPos, &path);
-#if 1
+#if 0
tryRonco(path);
#endif
-#if 1
+#if 0
showPath(path, NULL);
SkDebugf("simplified:\n");
#endif
diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm
index 340ded56c2..77e5e3edb0 100644
--- a/experimental/Intersection/EdgeDemoApp.mm
+++ b/experimental/Intersection/EdgeDemoApp.mm
@@ -16,7 +16,7 @@ public:
};
protected:
virtual void onDraw(SkCanvas* canvas) {
- static int step = 15064; // drawLetters first error
+ static int step = 0 ; // 17904; // drawLetters first error
// drawStars triggers error at 23275
// error is not easy to debug in its current state
static double seconds;
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index b3dcb06cc5..69c464a421 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -14,8 +14,9 @@ void cubecode_test(int test);
void Intersection_Tests() {
int testsRun = 0;
- SimplifyNew_Test();
QuadraticIntersection_Test();
+ MiniSimplify_Test();
+ SimplifyNew_Test();
SimplifyAngle_Test();
QuarticRoot_Test();
// QuadraticIntersection_Test();
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index 6e6aa89732..094e8445a5 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -22,6 +22,7 @@ void LineCubicIntersection_Test();
void LineIntersection_Test();
void LineParameter_Test();
void LineQuadraticIntersection_Test();
+void MiniSimplify_Test();
void SimplifyAddIntersectingTs_Test();
void SimplifyAngle_Test();
void SimplifyDegenerate4x4TrianglesThreaded_Test(int& );
diff --git a/experimental/Intersection/MiniSimplify_Test.cpp b/experimental/Intersection/MiniSimplify_Test.cpp
new file mode 100644
index 0000000000..4662381ec3
--- /dev/null
+++ b/experimental/Intersection/MiniSimplify_Test.cpp
@@ -0,0 +1,89 @@
+#include "EdgeWalker_Test.h"
+#include "Intersection_Tests.h"
+#include "ShapeOps.h"
+
+bool gShowOriginal = true;
+
+struct curve {
+ SkPath::Verb verb;
+ SkPoint pts[4];
+};
+
+struct curve test1[] = {
+{SkPath::kQuad_Verb, {{366.608826f, 151.196014f}, {378.803101f, 136.674606f}, {398.164948f, 136.674606f}}},
+{SkPath::kLine_Verb, {{354.009216f, 208.816208f}, {393.291473f, 102.232819f}}},
+{SkPath::kQuad_Verb, {{359.978058f, 136.581512f}, {378.315979f, 136.581512f}, {388.322723f, 149.613556f}}},
+{SkPath::kQuad_Verb, {{364.390686f, 157.898193f}, {375.281769f, 136.674606f}, {396.039917f, 136.674606f}}},
+{SkPath::kLine_Verb, {{396.039917f, 136.674606f}, {350, 120}}},
+{SkPath::kDone_Verb}
+};
+
+struct curve* testSet[] = {
+ test1
+};
+
+size_t testSet_count = sizeof(testSet) / sizeof(testSet[0]);
+
+static void construct() {
+ for (size_t idx = 0; idx < testSet_count; ++idx) {
+ const curve* test = testSet[idx];
+ SkPath path;
+ bool pathComplete = false;
+ bool first = true;
+ do {
+ if (first) {
+ path.moveTo(test->pts[0].fX, test->pts[0].fY);
+ first = false;
+ } else if (test->verb != SkPath::kDone_Verb) {
+ path.lineTo(test->pts[0].fX, test->pts[0].fY);
+ }
+ switch (test->verb) {
+ case SkPath::kDone_Verb:
+ pathComplete = true;
+ break;
+ case SkPath::kLine_Verb:
+ path.lineTo(test->pts[1].fX, test->pts[1].fY);
+ break;
+ case SkPath::kQuad_Verb:
+ path.quadTo(test->pts[1].fX, test->pts[1].fY, test->pts[2].fX, test->pts[2].fY);
+ break;
+ case SkPath::kCubic_Verb:
+ path.cubicTo(test->pts[1].fX, test->pts[1].fY, test->pts[2].fX, test->pts[2].fY, test->pts[3].fX, test->pts[3].fY);
+ break;
+ }
+ test++;
+ } while (!pathComplete);
+ path.close();
+ if (gShowOriginal) {
+ showPath(path, NULL);
+ SkDebugf("simplified:\n");
+ }
+ testSimplifyx(path);
+ }
+}
+
+static void (*tests[])() = {
+ construct,
+};
+
+static const size_t testCount = sizeof(tests) / sizeof(tests[0]);
+
+static void (*firstTest)() = 0;
+static bool skipAll = false;
+
+void MiniSimplify_Test() {
+ if (skipAll) {
+ return;
+ }
+ size_t index = 0;
+ if (firstTest) {
+ while (index < testCount && tests[index] != firstTest) {
+ ++index;
+ }
+ }
+ bool firstTestComplete = false;
+ for ( ; index < testCount; ++index) {
+ (*tests[index])();
+ firstTestComplete = true;
+ }
+}
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index e077bd5f93..799287ddfd 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -59,6 +59,13 @@ static void standardTestCases() {
}
static const Quadratic testSet[] = {
+
+{{369.8543701171875, 145.66734313964844}, {382.36788940429688, 121.28203582763672}, {406.21844482421875, 121.28203582763672}},
+{{369.96469116210938, 137.96672058105469}, {383.97555541992188, 121.28203582763672}, {406.2218017578125, 121.28203582763672}},
+
+ {{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}},
+ {{369.962311, 137.976044}, {383.971893, 121.29287}, {406.216125, 121.29287}},
+
{{400.121704, 149.468719}, {391.949493, 161.037186}, {391.949493, 181.202423}},
{{391.946747, 181.839218}, {391.946747, 155.62442}, {406.115479, 138.855438}},
{{360.048828125, 229.2578125}, {360.048828125, 224.4140625}, {362.607421875, 221.3671875}},
@@ -76,44 +83,8 @@ static void oneOffTest() {
const Quadratic& quad1 = testSet[outer];
const Quadratic& quad2 = testSet[inner];
double tt1, tt2;
- #if 0 // enable to test bezier clip style intersection
- Intersections intersections;
- intersect(quad1, quad2, intersections);
- if (!intersections.intersected()) {
- SkDebugf("%s no intersection!\n", __FUNCTION__);
- }
- for (int pt = 0; pt < intersections.used(); ++pt) {
- tt1 = intersections.fT[0][pt];
- double tx1, ty1;
- xy_at_t(quad1, tt1, tx1, ty1);
- tt2 = intersections.fT[1][pt];
- double tx2, ty2;
- xy_at_t(quad2, tt2, tx2, ty2);
- if (!approximately_equal(tx1, tx2)) {
- SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
- __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2);
- SkASSERT(0);
- }
- if (!approximately_equal(ty1, ty2)) {
- SkDebugf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
- __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2);
- SkASSERT(0);
- }
- SkDebugf("%s [%d][%d] t1=%1.9g (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__,
- outer, inner, tt1, tx1, tx2, tt2);
- }
- #endif
Intersections intersections2;
intersect2(quad1, quad2, intersections2);
- #if 0
- SkASSERT(intersections.used() == intersections2.used());
- for (int pt = 0; pt < intersections2.used(); ++pt) {
- tt1 = intersections2.fT[0][pt];
- SkASSERT(approximately_equal(intersections.fT[0][pt], tt1));
- tt2 = intersections2.fT[1][pt];
- SkASSERT(approximately_equal(intersections.fT[1][pt], tt2));
- }
- #endif
for (int pt = 0; pt < intersections2.used(); ++pt) {
tt1 = intersections2.fT[0][pt];
double tx1, ty1;
@@ -140,6 +111,8 @@ static void oneOffTest() {
}
static const Quadratic coincidentTestSet[] = {
+ {{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}},
+ {{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}},
{{8, 8}, {10, 10}, {8, -10}},
{{8, -10}, {10, 10}, {8, 8}},
};
@@ -150,28 +123,14 @@ static void coincidentTest() {
for (size_t testIndex = 0; testIndex < coincidentTestSetCount - 1; testIndex += 2) {
const Quadratic& quad1 = coincidentTestSet[testIndex];
const Quadratic& quad2 = coincidentTestSet[testIndex + 1];
- Intersections intersections, intersections2;
- intersect(quad1, quad2, intersections);
- SkASSERT(intersections.coincidentUsed() == 2);
- int pt;
- double tt1, tt2;
- for (pt = 0; pt < intersections.coincidentUsed(); ++pt) {
- tt1 = intersections.fT[0][pt];
- double tx1, ty1;
- xy_at_t(quad1, tt1, tx1, ty1);
- tt2 = intersections.fT[1][pt];
- double tx2, ty2;
- xy_at_t(quad2, tt2, tx2, ty2);
- SkDebugf("%s [%d,%d] t1=%g (%g,%g) t2=%g (%g,%g)\n",
- __FUNCTION__, (int)testIndex, pt, tt1, tx1, ty1, tt2, tx2, ty2);
- }
+ Intersections intersections2;
intersect2(quad1, quad2, intersections2);
SkASSERT(intersections2.coincidentUsed() == 2);
- for (pt = 0; pt < intersections2.coincidentUsed(); ++pt) {
- tt1 = intersections2.fT[0][pt];
- SkASSERT(approximately_equal(intersections.fT[0][pt], tt1));
- tt2 = intersections2.fT[1][pt];
- SkASSERT(approximately_equal(intersections.fT[1][pt], tt2));
+ for (int pt = 0; pt < intersections2.coincidentUsed(); ++pt) {
+ double tt1 = intersections2.fT[0][pt];
+ double tt2 = intersections2.fT[1][pt];
+ // SkASSERT(approximately_equal(intersections.fT[0][pt], tt1));
+ // SkASSERT(approximately_equal(intersections.fT[1][pt], tt2));
}
}
}
diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp
index b2e73cba50..f16c332c69 100644
--- a/experimental/Intersection/QuarticRoot.cpp
+++ b/experimental/Intersection/QuarticRoot.cpp
@@ -47,18 +47,17 @@ static int quadraticRootsX(const double A, const double B, const double C,
const double p = B / (2 * A);
const double q = C / A;
const double D = p * p - q;
- if (approximately_zero(D)) {
+ if (D < 0) {
+ return 0;
+ }
+ double sqrt_D = sqrt(D);
+ if (approximately_less_than_zero(sqrt_D)) {
s[0] = -p;
return 1;
- } else if (D < 0) {
- return 0;
- } else {
- assert(D > 0);
- double sqrt_D = sqrt(D);
- s[0] = sqrt_D - p;
- s[1] = -sqrt_D - p;
- return 2;
}
+ s[0] = sqrt_D - p;
+ s[1] = -sqrt_D - p;
+ return 2;
}
#define USE_GEMS 0
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 2409da30a8..788da5e923 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -25,9 +25,11 @@ int gDebugMaxWindSum = SK_MaxS32;
int gDebugMaxWindValue = SK_MaxS32;
#endif
+#define PRECISE_T_SORT 1
+
#define DEBUG_UNUSED 0 // set to expose unused functions
-#if 0 // set to 1 for multiple thread -- no debugging
+#if 1 // set to 1 for multiple thread -- no debugging
const bool gRunTestsInOneThread = false;
@@ -38,7 +40,7 @@ const bool gRunTestsInOneThread = false;
#define DEBUG_CONCIDENT 0
#define DEBUG_CROSS 0
#define DEBUG_MARK_DONE 0
-#define DEBUG_PATH_CONSTRUCTION 1
+#define DEBUG_PATH_CONSTRUCTION 0
#define DEBUG_SORT 0
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 0
@@ -47,7 +49,7 @@ const bool gRunTestsInOneThread = false;
const bool gRunTestsInOneThread = true;
-#define DEBUG_ACTIVE_SPANS 1
+#define DEBUG_ACTIVE_SPANS 0
#define DEBUG_ADD_INTERSECTING_TS 1
#define DEBUG_ADD_T_PAIR 1
#define DEBUG_ANGLE 1
@@ -533,6 +535,12 @@ public:
if (longer.lengthen() | rhLonger.lengthen()) {
return longer < rhLonger;
}
+ // what if we extend in the other direction?
+ longer = *this;
+ rhLonger = rh;
+ if (longer.reverseLengthen() | rhLonger.reverseLengthen()) {
+ return longer < rhLonger;
+ }
}
// at this point, the initial tangent line is coincident
if (fSide * rh.fSide <= 0) {
@@ -618,6 +626,20 @@ public:
return false;
}
+ bool reverseLengthen() {
+ if (fReversed) {
+ return false;
+ }
+ int newEnd = fStart;
+ if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
+ fEnd = newEnd;
+ fReversed = true;
+ setSpans();
+ return true;
+ }
+ return false;
+ }
+
void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
int start, int end, const SkTDArray<Span>& spans) {
fSegment = segment;
@@ -626,6 +648,7 @@ public:
fPts = orig;
fVerb = verb;
fSpans = &spans;
+ fReversed = false;
setSpans();
}
@@ -696,6 +719,7 @@ private:
const Segment* fSegment;
int fStart;
int fEnd;
+ bool fReversed;
};
static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) {
@@ -1332,7 +1356,7 @@ public:
}
// add edge leading away from junction
int step = SkSign32(end - start);
- int tIndex = nextSpan(end, step);
+ int tIndex = nextExactSpan(end, step);
if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) {
addAngle(angles, end, tIndex);
}
@@ -1345,12 +1369,21 @@ public:
void buildAngles(int index, SkTDArray<Angle>& angles) const {
double referenceT = fTs[index].fT;
int lesser = index;
+ #if PRECISE_T_SORT
+ while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
+ buildAnglesInner(lesser, angles);
+ }
+ do {
+ buildAnglesInner(index, angles);
+ } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
+ #else
while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
buildAnglesInner(lesser, angles);
}
do {
buildAnglesInner(index, angles);
} while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
+ #endif
}
void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
@@ -1363,10 +1396,18 @@ public:
int oIndex = span->fOtherIndex;
// if done == -1, prior span has already been processed
int step = 1;
+ #if PRECISE_T_SORT
+ int next = other->nextExactSpan(oIndex, step);
+ #else
int next = other->nextSpan(oIndex, step);
- if (next < 0) {
+ #endif
+ if (next < 0) {
step = -step;
+ #if PRECISE_T_SORT
+ next = other->nextExactSpan(oIndex, step);
+ #else
next = other->nextSpan(oIndex, step);
+ #endif
}
// add candidate into and away from junction
other->addTwoAngles(next, oIndex, angles);
@@ -1628,7 +1669,11 @@ public:
SkASSERT(startIndex < endIndex ? startIndex < count - 1
: startIndex > 0);
int step = SkSign32(endIndex - startIndex);
+ #if PRECISE_T_SORT
+ int end = nextExactSpan(startIndex, step);
+ #else
int end = nextSpan(startIndex, step);
+ #endif
SkASSERT(end >= 0);
Span* endSpan = &fTs[end];
Segment* other;
@@ -1645,7 +1690,12 @@ public:
nextEnd = nextStart;
do {
nextEnd += step;
- } while (approximately_zero(startT - other->fTs[nextEnd].fT));
+ }
+ #if PRECISE_T_SORT
+ while (precisely_zero(startT - other->fTs[nextEnd].fT));
+ #else
+ while (approximately_zero(startT - other->fTs[nextEnd].fT));
+ #endif
SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
return other;
}
@@ -1850,7 +1900,11 @@ public:
SkASSERT(startIndex < endIndex ? startIndex < count - 1
: startIndex > 0);
int step = SkSign32(endIndex - startIndex);
+ #if PRECISE_T_SORT
+ int end = nextExactSpan(startIndex, step);
+ #else
int end = nextSpan(startIndex, step);
+ #endif
SkASSERT(end >= 0);
Span* endSpan = &fTs[end];
Segment* other;
@@ -1867,7 +1921,12 @@ public:
nextEnd = nextStart;
do {
nextEnd += step;
- } while (approximately_zero(startT - other->fTs[nextEnd].fT));
+ }
+ #if PRECISE_T_SORT
+ while (precisely_zero(startT - other->fTs[nextEnd].fT));
+ #else
+ while (approximately_zero(startT - other->fTs[nextEnd].fT));
+ #endif
SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
return other;
}
@@ -2017,7 +2076,11 @@ public:
SkASSERT(startIndex < endIndex ? startIndex < count - 1
: startIndex > 0);
int step = SkSign32(endIndex - startIndex);
+ #if PRECISE_T_SORT
+ int end = nextExactSpan(startIndex, step);
+ #else
int end = nextSpan(startIndex, step);
+ #endif
SkASSERT(end >= 0);
Span* endSpan = &fTs[end];
Segment* other;
@@ -2039,7 +2102,12 @@ public:
nextEnd = nextStart;
do {
nextEnd += step;
- } while (approximately_zero(startT - other->fTs[nextEnd].fT));
+ }
+ #if PRECISE_T_SORT
+ while (precisely_zero(startT - other->fTs[nextEnd].fT));
+ #else
+ while (approximately_zero(startT - other->fTs[nextEnd].fT));
+ #endif
if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {
break;
}
@@ -2455,12 +2523,21 @@ public:
SkASSERT(winding);
double referenceT = fTs[index].fT;
int lesser = index;
+ #if PRECISE_T_SORT
+ while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
+ markOneDone(__FUNCTION__, lesser, winding);
+ }
+ do {
+ markOneDone(__FUNCTION__, index, winding);
+ } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
+ #else
while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
markOneDone(__FUNCTION__, lesser, winding);
}
do {
markOneDone(__FUNCTION__, index, winding);
} while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
+ #endif
}
void markOneDone(const char* funName, int tIndex, int winding) {
@@ -2493,12 +2570,21 @@ public:
SkASSERT(winding);
double referenceT = fTs[index].fT;
int lesser = index;
+ #if PRECISE_T_SORT
+ while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
+ markOneWinding(__FUNCTION__, lesser, winding);
+ }
+ do {
+ markOneWinding(__FUNCTION__, index, winding);
+ } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
+ #else
while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
markOneWinding(__FUNCTION__, lesser, winding);
}
do {
markOneWinding(__FUNCTION__, index, winding);
} while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
+ #endif
}
void matchWindingValue(int tIndex, double t, bool borrowWind) {
@@ -2559,6 +2645,7 @@ public:
return -1;
}
+#if PRECISE_T_SORT
// FIXME
// this returns at any difference in T, vs. a preset minimum. It may be
// that all callers to nextSpan should use this instead.
@@ -2568,13 +2655,14 @@ public:
int to = from;
while (step > 0 ? ++to < count : --to >= 0) {
const Span& span = fTs[to];
- if (span.fT == fromSpan.fT) {
+ if (precisely_zero(span.fT - fromSpan.fT)) {
continue;
}
return to;
}
return -1;
}
+#endif
bool operand() const {
return fOperand;
@@ -3627,18 +3715,50 @@ static void debugShowLineIntersection(int pts, const Work& wt,
SkPoint wtOutPt, wnOutPt;
LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
- SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)",
+ SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
__FUNCTION__,
wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
if (pts == 2) {
- SkDebugf(" wtTs[1]=%g", wtTs[1]);
+ SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
}
- SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)",
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
if (pts == 2) {
- SkDebugf(" wnTs[1]=%g", wnTs[1]);
+ SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowQuadIntersection(int pts, const Work& wt,
+ const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ if (!pts) {
+ SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
+ " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
+ __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
+ wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
+ wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
+ wt.pts()[2].fX, wt.pts()[2].fY );
+ return;
+ }
+ SkPoint wtOutPt, wnOutPt;
+ QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
+ QuadXYAtT(wn.pts(), wnTs[0], &wnOutPt);
+ SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
+ __FUNCTION__,
+ wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
+ wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
+ wtOutPt.fX, wtOutPt.fY);
+ if (pts == 2) {
+ SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
+ }
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
+ wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
+ wn.pts()[1].fX, wn.pts()[1].fY, wn.pts()[2].fX, wn.pts()[2].fY,
+ wnOutPt.fX, wnOutPt.fY);
+ if (pts == 2) {
+ SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
}
SkDebugf("\n");
}
@@ -3646,6 +3766,10 @@ static void debugShowLineIntersection(int pts, const Work& wt,
static void debugShowLineIntersection(int , const Work& ,
const Work& , const double [2], const double [2]) {
}
+
+static void debugShowQuadIntersection(int , const Work& ,
+ const Work& , const double [2], const double [2]) {
+}
#endif
static bool addIntersectTs(Contour* test, Contour* next) {
@@ -3777,6 +3901,8 @@ static bool addIntersectTs(Contour* test, Contour* next) {
}
case Work::kQuad_Segment: {
pts = QuadIntersect(wt.pts(), wn.pts(), ts);
+ debugShowQuadIntersection(pts, wt, wn,
+ ts.fT[1], ts.fT[0]);
break;
}
case Work::kCubic_Segment: {
diff --git a/experimental/Intersection/bc.htm b/experimental/Intersection/bc.htm
index e0784bdbbf..15601def03 100644
--- a/experimental/Intersection/bc.htm
+++ b/experimental/Intersection/bc.htm
@@ -114,12 +114,23 @@ $3 = {{
{{x = 362.607421875, y = 221.3671875}, {x = 365.166015625, y = 218.3203125}, {x = 369.228515625, y = 218.3203125}}
</div>
+<div id="quad38">
+$2 = {{fX = 369.969421, fY = 137.94809}, {fX = 383.982849, fY = 121.260353}, {fX = 406.233154, fY = 121.260353}}
+$4 = {{fX = 406.232788, fY = 121.260353}, {fX = 409.441956, fY = 121.260353}, {fX = 412.972046, fY = 121.795212}}
+</div>
+
+<div id="quad39">
+{{x = 406.233154296875, y = 121.26035308837891}, {x = 406.23153587045397, y = 121.26035308837891}, {x = 406.22991748761177, y = 121.26035317666889}},
+{{x = 406.23295158013377, y = 121.26035308872596}, {x = 406.2328698329315, y = 121.26035308837889}, {x = 406.2327880859375, y = 121.26035308837891}},
+</div>
</div>
<script type="text/javascript">
var testDivs = [
+ quad39,
+ quad38,
quad37,
quad36,
quad21g,
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index fabd0ef9cc..d6ff6f98a9 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -2084,9 +2084,194 @@ path.lineTo(369.22699,150.14563);
path.quadTo(373.524384,144.511566, 378.917297,141.233871);
path.lineTo(380.33902,137.376312);
path.close();
+path.moveTo(380.33902, 137.376312);
+path.lineTo(378.917297,141.233856);
+path.quadTo(375.048248,138.978912, 370.480499,137.816925);
+path.lineTo(380.33902,137.376312);
+path.close();
path.moveTo(392.55661, 136.830276);
-path.quadTo(385.032623,137.51709, 378.917297,141.233856);
-path.quadTo(378.917297,141.233856, 378.917297,141.233856);
+path.lineTo(380.33902,137.376312);
+</div>
+
+<div id="testQuadratic45o">
+path.moveTo(315.843994, 102.232819);
+path.lineTo(354.009216, 208.816208);
+path.lineTo(393.291473, 102.232819);
+path.lineTo(399.248962, 127.92453);
+path.lineTo(361.269928, 230.784485);
+path.lineTo(342.373474, 230.784485);
+path.lineTo(305.511444, 127.645271);
+path.lineTo(315.843994, 102.232819);
+path.close();
+path.moveTo(366.307892, 242.327148);
+path.quadTo(343.967255, 242.327148, 329.864746, 227.479935);
+path.quadTo(315.762238, 212.632736, 315.762238, 188.988907);
+path.quadTo(315.762238, 165.996674, 328.189209, 151.289093);
+path.quadTo(340.61618, 136.581512, 359.978058, 136.581512);
+path.quadTo(378.315979, 136.581512, 388.322723, 149.613556);
+path.quadTo(398.329468, 162.645584, 398.329468, 186.661758);
+path.lineTo(398.236359, 192.339996);
+path.lineTo(334.472504, 192.339996);
+path.quadTo(338.475189, 228.364258, 369.752075, 228.364258);
+path.quadTo(381.20163, 228.364258, 397.864014, 222.220581);
+path.lineTo(366.307892, 242.327148);
+path.close();
+path.moveTo(335.310272, 178.563278);
+path.lineTo(379.898438, 178.563278);
+path.quadTo(379.898438, 150.358246, 358.861023, 150.358246);
+path.quadTo(337.730499, 150.358246, 335.310272, 178.563278);
+path.close();
+path.moveTo(346.052765, 240);
+path.lineTo(346.052765, 138.908661);
+path.lineTo(364.390686, 138.908661);
+path.lineTo(364.390686, 157.898193);
+path.quadTo(375.281769, 136.674606, 396.039917, 136.674606);
+path.lineTo(401.904327, 154.267853);
+path.quadTo(397.156952, 152.685394, 393.526611, 152.685394);
+path.quadTo(376.119537, 152.685394, 364.390686, 173.350464);
+path.lineTo(364.390686, 240);
+path.lineTo(346.052765, 240);
+path.close();
+path.moveTo(396.303253, 265.226288);
+path.quadTo(427.300842, 265.226288, 427.300842, 232.366959);
+path.lineTo(427.300842, 216.449265);
+path.quadTo(417.15448, 237.672852, 393.976105, 237.672852);
+path.quadTo(375.824341, 237.672852, 365.119446, 224.454651);
+path.quadTo(354.414581, 211.23645, 354.414581, 188.802734);
+path.quadTo(354.414581, 165.717422, 366.608826, 151.196014);
+path.quadTo(378.803101, 136.674606, 398.164948, 136.674606);
+path.lineTo(396.303253, 265.226288);
+path.close();
+path.moveTo(400.95755, 150.451324);
+path.quadTo(388.297852, 150.451324, 381.130249, 160.597687);
+path.quadTo(373.962616, 170.744064, 373.962616, 188.430389);
+path.quadTo(373.962616, 221.662079, 397.327179, 221.662079);
+path.lineTo(400.95755, 150.451324);
+path.close();
+path.moveTo(429.901642, 242.327148);
+path.quadTo(407.561005, 242.327148, 393.458496, 227.479935);
+path.quadTo(379.355988, 212.632736, 379.355988, 188.988907);
+path.quadTo(379.355988, 165.996674, 391.782959, 151.289093);
+path.quadTo(404.20993, 136.581512, 423.571808, 136.581512);
+path.lineTo(429.901642, 242.327148);
+path.close();
+</div>
+
+<div id="testQuadratic45s">
+path.moveTo(305.511444, 127.645271);
+path.lineTo(315.843994,102.232819);
+path.lineTo(331.979736,147.294876);
+path.quadTo(343.453125,136.581512, 359.978058,136.581512);
+path.quadTo(370.869446,136.581512, 378.822021,141.178574);
+path.quadTo(378.893585,141.140915, 378.965302,141.103577);
+path.lineTo(393.291473,102.232819);
+path.lineTo(399.248962,127.92453);
+path.lineTo(396.018158,136.674606);
+path.quadTo(396.029053,136.674606, 396.039917,136.674606);
+path.lineTo(396.054596,136.718628);
+path.quadTo(397.098907,136.674606, 398.164948,136.674606);
+path.lineTo(398.076477,142.784256);
+path.lineTo(398.697632,144.647751);
+path.quadTo(409.233032,136.581512, 423.571808,136.581512);
+path.lineTo(429.901642,242.327148);
+path.quadTo(428.161621,242.327148, 426.471558,242.237076);
+path.quadTo(427.300842,237.741562, 427.300842,232.366959);
+path.lineTo(427.300842,216.449265);
+path.quadTo(419.710114,232.327133, 404.8255,236.326401);
+path.quadTo(400.557983,233.971252, 396.803375,230.691772);
+path.lineTo(396.7034,237.596863);
+path.quadTo(395.363068,237.672852, 393.976105,237.672852);
+path.quadTo(385.309937,237.672852, 378.341187,234.659912);
+path.lineTo(366.307892,242.327148);
+path.quadTo(357.463165,242.327148, 349.909637,240);
+path.lineTo(346.052765,240);
+path.lineTo(346.052765,238.625916);
+path.quadTo(336.926056,234.914124, 329.864746,227.479935);
+path.quadTo(315.762238,212.632736, 315.762238,188.988907);
+path.quadTo(315.762238,176.540054, 319.405273,166.519882);
+path.lineTo(305.511444,127.645271);
+path.close();
+path.moveTo(375.464813, 192.339996);
+path.lineTo(374.267029,195.583939);
+path.quadTo(375.987579,214.575378, 387.432068,219.736267);
+path.quadTo(380.122528,208.101486, 379.428741,192.339996);
+path.lineTo(375.464813,192.339996);
+path.close();
+path.moveTo(397.925934, 153.178131);
+path.lineTo(397.615479,174.615356);
+path.quadTo(398.329468,180.246704, 398.329468,186.661758);
+path.lineTo(398.236359,192.339996);
+path.lineTo(397.358795,192.339996);
+path.lineTo(396.934174,221.659714);
+path.quadTo(397.129852,221.662079, 397.327179,221.662079);
+path.lineTo(400.781189,153.910889);
+path.quadTo(399.295654,153.462463, 397.925934,153.178131);
+path.close();
+path.moveTo(400.914398, 151.298019);
+path.lineTo(400.632721,150.453003);
+path.quadTo(400.794678,150.451324, 400.95755,150.451324);
+path.lineTo(400.914398,151.298019);
+path.close();
+path.moveTo(368.744965, 228.354782);
+path.quadTo(366.836426,226.574738, 365.119446,224.454651);
+path.quadTo(364.748657,223.996796, 364.390686,223.527878);
+path.lineTo(364.390686,228.077774);
+path.quadTo(366.495239,228.312164, 368.744965,228.354782);
+path.close();
+path.moveTo(346.052765, 178.563278);
+path.lineTo(346.052765,154.02713);
+path.quadTo(340.97113,157.621338, 338.22525,164.736588);
+path.lineTo(343.1763,178.563278);
+path.lineTo(346.052765,178.563278);
+path.close();
+path.moveTo(364.390686, 150.922379);
+path.lineTo(364.390686,154.048065);
+path.quadTo(365.340851,152.726639, 366.38147,151.468765);
+path.quadTo(365.420258,151.14975, 364.390686,150.922379);
+path.close();
+path.moveTo(367.863586, 152.032623);
+path.quadTo(367.144043,151.721848, 366.38147,151.468765);
+</div>
+
+<div id="testQuadratic46o">
+path.moveTo(366.608826, 151.196014);
+path.quadTo(378.803101, 136.674606, 398.164948, 136.674606);
+path.lineTo(354.009216, 208.816208);
+path.lineTo(393.291473, 102.232819);
+path.lineTo(359.978058, 136.581512);
+path.quadTo(378.315979, 136.581512, 388.322723, 149.613556);
+path.lineTo(364.390686, 157.898193);
+path.quadTo(375.281769, 136.674606, 396.039917, 136.674606);
+path.lineTo(350, 120);
+path.lineTo(366.608826, 151.196014);
+path.close();
+</div>
+
+<div id="testQuadratic46s">
+path.moveTo(369.285553, 126.984779);
+path.lineTo(393.291473,102.232819);
+path.lineTo(382.416199,131.740402);
+path.lineTo(396.039917,136.674606);
+path.quadTo(387.290802,136.674606, 380.294495,140.44487);
+path.quadTo(379.623352,140.760971, 378.965302,141.103577);
+path.lineTo(378.917297,141.233856);
+path.quadTo(378.86972,141.206131, 378.822021,141.178574);
+path.quadTo(372.011871,144.761871, 366.608826,151.196014);
+path.lineTo(350,120);
+path.lineTo(369.285553,126.984779);
+path.close();
+path.moveTo(374.00174, 154.571106);
+path.lineTo(378.917297,141.233871);
+path.quadTo(378.917297,141.233871, 378.917297,141.233856);
+path.quadTo(384.294891,144.368011, 388.322723,149.613556);
+path.lineTo(374.00174,154.571106);
+path.close();
+path.moveTo(378.917297, 141.233871);
+path.quadTo(370.233887,146.511475, 364.390686,157.898193);
+path.lineTo(374.00174,154.571106);
+path.lineTo(354.009216,208.816208);
+path.lineTo(398.164948,136.674606);
+path.quadTo(388.299255,136.674606, 380.294495,140.44487);
</div>
</div>
@@ -2094,6 +2279,10 @@ path.quadTo(378.917297,141.233856, 378.917297,141.233856);
<script type="text/javascript">
var testDivs = [
+ testQuadratic46o,
+ testQuadratic46s,
+ testQuadratic45o,
+ testQuadratic45s,
testQuadratic44o,
testQuadratic44s,
testQuadratic43o,
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-12 01:15:17 +0000