Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(829)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: tests/PathOpsAngleTest.cpp

Issue 15338003: path ops -- rewrite angle sort (Closed) Base URL: http://skia.googlecode.com/svn/trunk/
Patch Set: Created 7 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/pathops/SkPathOpsTypes.cpp ('k') | tests/PathOpsCubicIntersectionTest.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: tests/PathOpsAngleTest.cpp
===================================================================
--- tests/PathOpsAngleTest.cpp (revision 9425)
+++ tests/PathOpsAngleTest.cpp (working copy)
@@ -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)
« no previous file with comments | « src/pathops/SkPathOpsTypes.cpp ('k') | tests/PathOpsCubicIntersectionTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698