1 /*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7 #include "include/core/SkString.h"
8 #include "src/pathops/SkIntersections.h"
9 #include "src/pathops/SkPathOpsLine.h"
10 #include "src/pathops/SkPathOpsQuad.h"
11 #include "src/pathops/SkReduceOrder.h"
12 #include "tests/PathOpsExtendedTest.h"
13 #include "tests/PathOpsTestCommon.h"
14 #include "tests/PathOpsThreadedCommon.h"
15
16 #include <utility>
17
doIntersect(SkIntersections & intersections,const SkDQuad & quad,const SkDLine & line,bool & flipped)18 static int doIntersect(SkIntersections& intersections, const SkDQuad& quad, const SkDLine& line,
19 bool& flipped) {
20 int result;
21 flipped = false;
22 if (line[0].fX == line[1].fX) {
23 double top = line[0].fY;
24 double bottom = line[1].fY;
25 flipped = top > bottom;
26 if (flipped) {
27 using std::swap;
28 swap(top, bottom);
29 }
30 result = intersections.vertical(quad, top, bottom, line[0].fX, flipped);
31 } else if (line[0].fY == line[1].fY) {
32 double left = line[0].fX;
33 double right = line[1].fX;
34 flipped = left > right;
35 if (flipped) {
36 using std::swap;
37 swap(left, right);
38 }
39 result = intersections.horizontal(quad, left, right, line[0].fY, flipped);
40 } else {
41 intersections.intersect(quad, line);
42 result = intersections.used();
43 }
44 return result;
45 }
46
testLineIntersect(skiatest::Reporter * reporter,const SkDQuad & quad,const SkDLine & line,const double x,const double y)47 static void testLineIntersect(skiatest::Reporter* reporter, const SkDQuad& quad,
48 const SkDLine& line, const double x, const double y) {
49 SkString pathStr;
50 pathStr.appendf(" path.moveTo(%1.9g, %1.9g);\n", quad[0].fX, quad[0].fY);
51 pathStr.appendf(" path.quadTo(%1.9g, %1.9g, %1.9g, %1.9g);\n", quad[1].fX,
52 quad[1].fY, quad[2].fX, quad[2].fY);
53 pathStr.appendf(" path.moveTo(%1.9g, %1.9g);\n", line[0].fX, line[0].fY);
54 pathStr.appendf(" path.lineTo(%1.9g, %1.9g);\n", line[1].fX, line[1].fY);
55
56 SkIntersections intersections;
57 bool flipped = false;
58 int result = doIntersect(intersections, quad, line, flipped);
59 bool found = false;
60 for (int index = 0; index < result; ++index) {
61 double quadT = intersections[0][index];
62 SkDPoint quadXY = quad.ptAtT(quadT);
63 double lineT = intersections[1][index];
64 SkDPoint lineXY = line.ptAtT(lineT);
65 if (quadXY.approximatelyEqual(lineXY)) {
66 found = true;
67 }
68 }
69 REPORTER_ASSERT(reporter, found);
70 }
71
72 // find a point on a quad by choosing a t from 0 to 1
73 // create a vertical span above and below the point
74 // verify that intersecting the vertical span and the quad returns t
75 // verify that a vertical span starting at quad[0] intersects at t=0
76 // verify that a vertical span starting at quad[2] intersects at t=1
testQuadLineIntersectMain(PathOpsThreadState * data)77 static void testQuadLineIntersectMain(PathOpsThreadState* data)
78 {
79 PathOpsThreadState& state = *data;
80 REPORTER_ASSERT(state.fReporter, data);
81 int ax = state.fA & 0x03;
82 int ay = state.fA >> 2;
83 int bx = state.fB & 0x03;
84 int by = state.fB >> 2;
85 int cx = state.fC & 0x03;
86 int cy = state.fC >> 2;
87 QuadPts q = {{{(double) ax, (double) ay}, {(double) bx, (double) by},
88 {(double) cx, (double) cy}}};
89 SkDQuad quad;
90 quad.debugSet(q.fPts);
91 SkReduceOrder reducer;
92 int order = reducer.reduce(quad);
93 if (order < 3) {
94 return;
95 }
96 for (int tIndex = 0; tIndex <= 4; ++tIndex) {
97 SkDPoint xy = quad.ptAtT(tIndex / 4.0);
98 for (int h = -2; h <= 2; ++h) {
99 for (int v = -2; v <= 2; ++v) {
100 if (h == v && SkTAbs(h) != 1) {
101 continue;
102 }
103 double x = xy.fX;
104 double y = xy.fY;
105 SkDLine line = {{{x - h, y - v}, {x, y}}};
106 testLineIntersect(state.fReporter, quad, line, x, y);
107 state.fReporter->bumpTestCount();
108 SkDLine line2 = {{{x, y}, {x + h, y + v}}};
109 testLineIntersect(state.fReporter, quad, line2, x, y);
110 state.fReporter->bumpTestCount();
111 SkDLine line3 = {{{x - h, y - v}, {x + h, y + v}}};
112 testLineIntersect(state.fReporter, quad, line3, x, y);
113 state.fReporter->bumpTestCount();
114 }
115 }
116 }
117 }
118
DEF_TEST(PathOpsQuadLineIntersectionThreaded,reporter)119 DEF_TEST(PathOpsQuadLineIntersectionThreaded, reporter) {
120 initializeTests(reporter, "testQuadLineIntersect");
121 PathOpsThreadedTestRunner testRunner(reporter);
122 for (int a = 0; a < 16; ++a) {
123 for (int b = 0 ; b < 16; ++b) {
124 for (int c = 0 ; c < 16; ++c) {
125 *testRunner.fRunnables.append() = new PathOpsThreadedRunnable(
126 &testQuadLineIntersectMain, a, b, c, 0, &testRunner);
127 }
128 if (!reporter->allowExtendedTest()) goto finish;
129 }
130 }
131 finish:
132 testRunner.render();
133 }
134