1*c8dee2aaSAndroid Build Coastguard Worker /*
2*c8dee2aaSAndroid Build Coastguard Worker * Copyright 2012 Google Inc.
3*c8dee2aaSAndroid Build Coastguard Worker *
4*c8dee2aaSAndroid Build Coastguard Worker * Use of this source code is governed by a BSD-style license that can be
5*c8dee2aaSAndroid Build Coastguard Worker * found in the LICENSE file.
6*c8dee2aaSAndroid Build Coastguard Worker */
7*c8dee2aaSAndroid Build Coastguard Worker #include "include/core/SkTypes.h"
8*c8dee2aaSAndroid Build Coastguard Worker #include "include/private/base/SkDebug.h"
9*c8dee2aaSAndroid Build Coastguard Worker #include "src/pathops/SkIntersections.h"
10*c8dee2aaSAndroid Build Coastguard Worker #include "src/pathops/SkPathOpsLine.h"
11*c8dee2aaSAndroid Build Coastguard Worker #include "src/pathops/SkPathOpsPoint.h"
12*c8dee2aaSAndroid Build Coastguard Worker #include "src/pathops/SkPathOpsQuad.h"
13*c8dee2aaSAndroid Build Coastguard Worker #include "src/pathops/SkReduceOrder.h"
14*c8dee2aaSAndroid Build Coastguard Worker #include "tests/PathOpsTestCommon.h"
15*c8dee2aaSAndroid Build Coastguard Worker #include "tests/Test.h"
16*c8dee2aaSAndroid Build Coastguard Worker
17*c8dee2aaSAndroid Build Coastguard Worker #include <array>
18*c8dee2aaSAndroid Build Coastguard Worker #include <cstddef>
19*c8dee2aaSAndroid Build Coastguard Worker #include <utility>
20*c8dee2aaSAndroid Build Coastguard Worker
21*c8dee2aaSAndroid Build Coastguard Worker static struct lineQuad {
22*c8dee2aaSAndroid Build Coastguard Worker QuadPts quad;
23*c8dee2aaSAndroid Build Coastguard Worker SkDLine line;
24*c8dee2aaSAndroid Build Coastguard Worker int result;
25*c8dee2aaSAndroid Build Coastguard Worker SkDPoint expected[2];
26*c8dee2aaSAndroid Build Coastguard Worker } lineQuadTests[] = {
27*c8dee2aaSAndroid Build Coastguard Worker // quad line results
28*c8dee2aaSAndroid Build Coastguard Worker {{{{1, 1}, {2, 1}, {0, 2}}}, {{{0, 0}, {1, 1}}}, 1, {{1, 1}, {0, 0}} },
29*c8dee2aaSAndroid Build Coastguard Worker {{{{0, 0}, {1, 1}, {3, 1}}}, {{{0, 0}, {3, 1}}}, 2, {{0, 0}, {3, 1}} },
30*c8dee2aaSAndroid Build Coastguard Worker {{{{2, 0}, {1, 1}, {2, 2}}}, {{{0, 0}, {0, 2}}}, 0, {{0, 0}, {0, 0}} },
31*c8dee2aaSAndroid Build Coastguard Worker {{{{4, 0}, {0, 1}, {4, 2}}}, {{{3, 1}, {4, 1}}}, 0, {{0, 0}, {0, 0}} },
32*c8dee2aaSAndroid Build Coastguard Worker {{{{0, 0}, {0, 1}, {1, 1}}}, {{{0, 1}, {1, 0}}}, 1, {{.25, .75}, {0, 0}} },
33*c8dee2aaSAndroid Build Coastguard Worker };
34*c8dee2aaSAndroid Build Coastguard Worker
35*c8dee2aaSAndroid Build Coastguard Worker static size_t lineQuadTests_count = std::size(lineQuadTests);
36*c8dee2aaSAndroid Build Coastguard Worker
doIntersect(SkIntersections & intersections,const SkDQuad & quad,const SkDLine & line,bool & flipped)37*c8dee2aaSAndroid Build Coastguard Worker static int doIntersect(SkIntersections& intersections, const SkDQuad& quad, const SkDLine& line,
38*c8dee2aaSAndroid Build Coastguard Worker bool& flipped) {
39*c8dee2aaSAndroid Build Coastguard Worker int result;
40*c8dee2aaSAndroid Build Coastguard Worker flipped = false;
41*c8dee2aaSAndroid Build Coastguard Worker if (line[0].fX == line[1].fX) {
42*c8dee2aaSAndroid Build Coastguard Worker double top = line[0].fY;
43*c8dee2aaSAndroid Build Coastguard Worker double bottom = line[1].fY;
44*c8dee2aaSAndroid Build Coastguard Worker flipped = top > bottom;
45*c8dee2aaSAndroid Build Coastguard Worker if (flipped) {
46*c8dee2aaSAndroid Build Coastguard Worker using std::swap;
47*c8dee2aaSAndroid Build Coastguard Worker swap(top, bottom);
48*c8dee2aaSAndroid Build Coastguard Worker }
49*c8dee2aaSAndroid Build Coastguard Worker result = intersections.vertical(quad, top, bottom, line[0].fX, flipped);
50*c8dee2aaSAndroid Build Coastguard Worker } else if (line[0].fY == line[1].fY) {
51*c8dee2aaSAndroid Build Coastguard Worker double left = line[0].fX;
52*c8dee2aaSAndroid Build Coastguard Worker double right = line[1].fX;
53*c8dee2aaSAndroid Build Coastguard Worker flipped = left > right;
54*c8dee2aaSAndroid Build Coastguard Worker if (flipped) {
55*c8dee2aaSAndroid Build Coastguard Worker using std::swap;
56*c8dee2aaSAndroid Build Coastguard Worker swap(left, right);
57*c8dee2aaSAndroid Build Coastguard Worker }
58*c8dee2aaSAndroid Build Coastguard Worker result = intersections.horizontal(quad, left, right, line[0].fY, flipped);
59*c8dee2aaSAndroid Build Coastguard Worker } else {
60*c8dee2aaSAndroid Build Coastguard Worker intersections.intersect(quad, line);
61*c8dee2aaSAndroid Build Coastguard Worker result = intersections.used();
62*c8dee2aaSAndroid Build Coastguard Worker }
63*c8dee2aaSAndroid Build Coastguard Worker return result;
64*c8dee2aaSAndroid Build Coastguard Worker }
65*c8dee2aaSAndroid Build Coastguard Worker
66*c8dee2aaSAndroid Build Coastguard Worker static struct oneLineQuad {
67*c8dee2aaSAndroid Build Coastguard Worker QuadPts quad;
68*c8dee2aaSAndroid Build Coastguard Worker SkDLine line;
69*c8dee2aaSAndroid Build Coastguard Worker } oneOffs[] = {
70*c8dee2aaSAndroid Build Coastguard Worker {{{{97.9337616,100}, {88,112.94265}, {88,130}}},
71*c8dee2aaSAndroid Build Coastguard Worker {{{88.919838,120}, {107.058823,120}}}},
72*c8dee2aaSAndroid Build Coastguard Worker {{{{447.96701049804687, 894.4381103515625}, {448.007080078125, 894.4239501953125},
73*c8dee2aaSAndroid Build Coastguard Worker {448.0140380859375, 894.4215087890625}}},
74*c8dee2aaSAndroid Build Coastguard Worker {{{490.43548583984375, 879.40740966796875}, {405.59262084960937, 909.435546875}}}},
75*c8dee2aaSAndroid Build Coastguard Worker {{{{142.589081, 102.283646}, {149.821579, 100}, {158, 100}}},
76*c8dee2aaSAndroid Build Coastguard Worker {{{90, 230}, {160, 60}}}},
77*c8dee2aaSAndroid Build Coastguard Worker {{{{1101, 10}, {1101, 8.3431453704833984}, {1099.828857421875, 7.1711997985839844}}},
78*c8dee2aaSAndroid Build Coastguard Worker {{{1099.828857421875,7.1711711883544922}, {1099.121337890625,7.8786783218383789}}}},
79*c8dee2aaSAndroid Build Coastguard Worker {{{{973, 507}, {973, 508.24264526367187}, {972.12158203125, 509.12161254882812}}},
80*c8dee2aaSAndroid Build Coastguard Worker {{{930, 467}, {973, 510}}}},
81*c8dee2aaSAndroid Build Coastguard Worker {{{{369.848602, 145.680267}, {382.360413, 121.298294}, {406.207703, 121.298294}}},
82*c8dee2aaSAndroid Build Coastguard Worker {{{406.207703, 121.298294}, {348.781738, 123.864815}}}},
83*c8dee2aaSAndroid Build Coastguard Worker };
84*c8dee2aaSAndroid Build Coastguard Worker
85*c8dee2aaSAndroid Build Coastguard Worker static size_t oneOffs_count = std::size(oneOffs);
86*c8dee2aaSAndroid Build Coastguard Worker
testOneOffs(skiatest::Reporter * reporter)87*c8dee2aaSAndroid Build Coastguard Worker static void testOneOffs(skiatest::Reporter* reporter) {
88*c8dee2aaSAndroid Build Coastguard Worker bool flipped = false;
89*c8dee2aaSAndroid Build Coastguard Worker for (size_t index = 0; index < oneOffs_count; ++index) {
90*c8dee2aaSAndroid Build Coastguard Worker const QuadPts& q = oneOffs[index].quad;
91*c8dee2aaSAndroid Build Coastguard Worker SkDQuad quad;
92*c8dee2aaSAndroid Build Coastguard Worker quad.debugSet(q.fPts);
93*c8dee2aaSAndroid Build Coastguard Worker SkASSERT(ValidQuad(quad));
94*c8dee2aaSAndroid Build Coastguard Worker const SkDLine& line = oneOffs[index].line;
95*c8dee2aaSAndroid Build Coastguard Worker SkASSERT(ValidLine(line));
96*c8dee2aaSAndroid Build Coastguard Worker SkIntersections intersections;
97*c8dee2aaSAndroid Build Coastguard Worker int result = doIntersect(intersections, quad, line, flipped);
98*c8dee2aaSAndroid Build Coastguard Worker for (int inner = 0; inner < result; ++inner) {
99*c8dee2aaSAndroid Build Coastguard Worker double quadT = intersections[0][inner];
100*c8dee2aaSAndroid Build Coastguard Worker SkDPoint quadXY = quad.ptAtT(quadT);
101*c8dee2aaSAndroid Build Coastguard Worker double lineT = intersections[1][inner];
102*c8dee2aaSAndroid Build Coastguard Worker SkDPoint lineXY = line.ptAtT(lineT);
103*c8dee2aaSAndroid Build Coastguard Worker if (!quadXY.approximatelyEqual(lineXY)) {
104*c8dee2aaSAndroid Build Coastguard Worker quadXY.approximatelyEqual(lineXY);
105*c8dee2aaSAndroid Build Coastguard Worker }
106*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, quadXY.approximatelyEqual(lineXY));
107*c8dee2aaSAndroid Build Coastguard Worker }
108*c8dee2aaSAndroid Build Coastguard Worker }
109*c8dee2aaSAndroid Build Coastguard Worker }
110*c8dee2aaSAndroid Build Coastguard Worker
DEF_TEST(PathOpsQuadLineIntersectionOneOff,reporter)111*c8dee2aaSAndroid Build Coastguard Worker DEF_TEST(PathOpsQuadLineIntersectionOneOff, reporter) {
112*c8dee2aaSAndroid Build Coastguard Worker testOneOffs(reporter);
113*c8dee2aaSAndroid Build Coastguard Worker }
114*c8dee2aaSAndroid Build Coastguard Worker
DEF_TEST(PathOpsQuadLineIntersection,reporter)115*c8dee2aaSAndroid Build Coastguard Worker DEF_TEST(PathOpsQuadLineIntersection, reporter) {
116*c8dee2aaSAndroid Build Coastguard Worker for (size_t index = 0; index < lineQuadTests_count; ++index) {
117*c8dee2aaSAndroid Build Coastguard Worker int iIndex = static_cast<int>(index);
118*c8dee2aaSAndroid Build Coastguard Worker const QuadPts& q = lineQuadTests[index].quad;
119*c8dee2aaSAndroid Build Coastguard Worker SkDQuad quad;
120*c8dee2aaSAndroid Build Coastguard Worker quad.debugSet(q.fPts);
121*c8dee2aaSAndroid Build Coastguard Worker SkASSERT(ValidQuad(quad));
122*c8dee2aaSAndroid Build Coastguard Worker const SkDLine& line = lineQuadTests[index].line;
123*c8dee2aaSAndroid Build Coastguard Worker SkASSERT(ValidLine(line));
124*c8dee2aaSAndroid Build Coastguard Worker SkReduceOrder reducer1, reducer2;
125*c8dee2aaSAndroid Build Coastguard Worker int order1 = reducer1.reduce(quad);
126*c8dee2aaSAndroid Build Coastguard Worker int order2 = reducer2.reduce(line);
127*c8dee2aaSAndroid Build Coastguard Worker if (order1 < 3) {
128*c8dee2aaSAndroid Build Coastguard Worker SkDebugf("%s [%d] quad order=%d\n", __FUNCTION__, iIndex, order1);
129*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, 0);
130*c8dee2aaSAndroid Build Coastguard Worker }
131*c8dee2aaSAndroid Build Coastguard Worker if (order2 < 2) {
132*c8dee2aaSAndroid Build Coastguard Worker SkDebugf("%s [%d] line order=%d\n", __FUNCTION__, iIndex, order2);
133*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, 0);
134*c8dee2aaSAndroid Build Coastguard Worker }
135*c8dee2aaSAndroid Build Coastguard Worker SkIntersections intersections;
136*c8dee2aaSAndroid Build Coastguard Worker bool flipped = false;
137*c8dee2aaSAndroid Build Coastguard Worker int result = doIntersect(intersections, quad, line, flipped);
138*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, result == lineQuadTests[index].result);
139*c8dee2aaSAndroid Build Coastguard Worker if (intersections.used() <= 0) {
140*c8dee2aaSAndroid Build Coastguard Worker continue;
141*c8dee2aaSAndroid Build Coastguard Worker }
142*c8dee2aaSAndroid Build Coastguard Worker for (int pt = 0; pt < result; ++pt) {
143*c8dee2aaSAndroid Build Coastguard Worker double tt1 = intersections[0][pt];
144*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, tt1 >= 0 && tt1 <= 1);
145*c8dee2aaSAndroid Build Coastguard Worker SkDPoint t1 = quad.ptAtT(tt1);
146*c8dee2aaSAndroid Build Coastguard Worker double tt2 = intersections[1][pt];
147*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, tt2 >= 0 && tt2 <= 1);
148*c8dee2aaSAndroid Build Coastguard Worker SkDPoint t2 = line.ptAtT(tt2);
149*c8dee2aaSAndroid Build Coastguard Worker if (!t1.approximatelyEqual(t2)) {
150*c8dee2aaSAndroid Build Coastguard Worker SkDebugf("%s [%d,%d] x!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n",
151*c8dee2aaSAndroid Build Coastguard Worker __FUNCTION__, iIndex, pt, tt1, t1.fX, t1.fY, tt2, t2.fX, t2.fY);
152*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, 0);
153*c8dee2aaSAndroid Build Coastguard Worker }
154*c8dee2aaSAndroid Build Coastguard Worker if (!t1.approximatelyEqual(lineQuadTests[index].expected[0])
155*c8dee2aaSAndroid Build Coastguard Worker && (lineQuadTests[index].result == 1
156*c8dee2aaSAndroid Build Coastguard Worker || !t1.approximatelyEqual(lineQuadTests[index].expected[1]))) {
157*c8dee2aaSAndroid Build Coastguard Worker SkDebugf("%s t1=(%1.9g,%1.9g)\n", __FUNCTION__, t1.fX, t1.fY);
158*c8dee2aaSAndroid Build Coastguard Worker REPORTER_ASSERT(reporter, 0);
159*c8dee2aaSAndroid Build Coastguard Worker }
160*c8dee2aaSAndroid Build Coastguard Worker }
161*c8dee2aaSAndroid Build Coastguard Worker }
162*c8dee2aaSAndroid Build Coastguard Worker }
163