xref: /aosp_15_r20/external/skia/tests/PathOpsQuadLineIntersectionTest.cpp (revision c8dee2aa9b3f27cf6c858bd81872bdeb2c07ed17)
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