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