1 /*
2 * Copyright 2020 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
8 #include "include/utils/SkRandom.h"
9 #include "src/core/SkGeometry.h"
10 #include "src/gpu/geometry/GrPathUtils.h"
11 #include "tests/Test.h"
12
is_linear(SkPoint p0,SkPoint p1,SkPoint p2)13 static bool is_linear(SkPoint p0, SkPoint p1, SkPoint p2) {
14 return SkScalarNearlyZero((p0 - p1).cross(p2 - p1));
15 }
16
is_linear(const SkPoint p[4])17 static bool is_linear(const SkPoint p[4]) {
18 return is_linear(p[0],p[1],p[2]) && is_linear(p[0],p[2],p[3]) && is_linear(p[1],p[2],p[3]);
19 }
20
check_cubic_convex_180(skiatest::Reporter * r,const SkPoint p[4])21 static void check_cubic_convex_180(skiatest::Reporter* r, const SkPoint p[4]) {
22 bool areCusps = false;
23 float inflectT[2], convex180T[2];
24 if (int inflectN = SkFindCubicInflections(p, inflectT)) {
25 // The curve has inflections. findCubicConvex180Chops should return the inflection
26 // points.
27 int convex180N = GrPathUtils::findCubicConvex180Chops(p, convex180T, &areCusps);
28 REPORTER_ASSERT(r, inflectN == convex180N);
29 if (!areCusps) {
30 REPORTER_ASSERT(r, inflectN == 1 ||
31 fabsf(inflectT[0] - inflectT[1]) >= SK_ScalarNearlyZero);
32 }
33 for (int i = 0; i < convex180N; ++i) {
34 REPORTER_ASSERT(r, SkScalarNearlyEqual(inflectT[i], convex180T[i]));
35 }
36 } else {
37 float totalRotation = SkMeasureNonInflectCubicRotation(p);
38 int convex180N = GrPathUtils::findCubicConvex180Chops(p, convex180T, &areCusps);
39 SkPoint chops[10];
40 SkChopCubicAt(p, chops, convex180T, convex180N);
41 float radsSum = 0;
42 for (int i = 0; i <= convex180N; ++i) {
43 float rads = SkMeasureNonInflectCubicRotation(chops + i*3);
44 SkASSERT(rads < SK_ScalarPI + SK_ScalarNearlyZero);
45 radsSum += rads;
46 }
47 if (totalRotation < SK_ScalarPI - SK_ScalarNearlyZero) {
48 // The curve should never chop if rotation is <180 degrees.
49 REPORTER_ASSERT(r, convex180N == 0);
50 } else if (!is_linear(p)) {
51 REPORTER_ASSERT(r, SkScalarNearlyEqual(radsSum, totalRotation));
52 if (totalRotation > SK_ScalarPI + SK_ScalarNearlyZero) {
53 REPORTER_ASSERT(r, convex180N == 1);
54 // This works because cusps take the "inflection" path above, so we don't get
55 // non-lilnear curves that lose rotation when chopped.
56 REPORTER_ASSERT(r, SkScalarNearlyEqual(
57 SkMeasureNonInflectCubicRotation(chops), SK_ScalarPI));
58 REPORTER_ASSERT(r, SkScalarNearlyEqual(
59 SkMeasureNonInflectCubicRotation(chops + 3), totalRotation - SK_ScalarPI));
60 }
61 REPORTER_ASSERT(r, !areCusps);
62 } else {
63 REPORTER_ASSERT(r, areCusps);
64 }
65 }
66 }
67
DEF_TEST(GrPathUtils_findCubicConvex180Chops,r)68 DEF_TEST(GrPathUtils_findCubicConvex180Chops, r) {
69 // Test all combinations of corners from the square [0,0,1,1]. This covers every cubic type as
70 // well as a wide variety of special cases for cusps, lines, loops, and inflections.
71 for (int i = 0; i < (1 << 8); ++i) {
72 SkPoint p[4] = {SkPoint::Make((i>>0)&1, (i>>1)&1),
73 SkPoint::Make((i>>2)&1, (i>>3)&1),
74 SkPoint::Make((i>>4)&1, (i>>5)&1),
75 SkPoint::Make((i>>6)&1, (i>>7)&1)};
76 check_cubic_convex_180(r, p);
77 }
78
79 {
80 // This cubic has a convex-180 chop at T=1-"epsilon"
81 static const uint32_t hexPts[] = {0x3ee0ac74, 0x3f1e061a, 0x3e0fc408, 0x3f457230,
82 0x3f42ac7c, 0x3f70d76c, 0x3f4e6520, 0x3f6acafa};
83 SkPoint p[4];
84 memcpy(p, hexPts, sizeof(p));
85 check_cubic_convex_180(r, p);
86 }
87
88 // Now test an exact quadratic.
89 SkPoint quad[4] = {{0,0}, {2,2}, {4,2}, {6,0}};
90 float T[2];
91 bool areCusps;
92 REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(quad, T, &areCusps) == 0);
93
94 // Now test that cusps and near-cusps get flagged as cusps.
95 SkPoint cusp[4] = {{0,0}, {1,1}, {1,0}, {0,1}};
96 REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(cusp, T, &areCusps) == 1);
97 REPORTER_ASSERT(r, areCusps == true);
98
99 // Find the height of the right side of "cusp" at which the distance between its inflection
100 // points is kEpsilon (in parametric space).
101 constexpr static double kEpsilon = 1.0 / (1 << 11);
102 constexpr static double kEpsilonSquared = kEpsilon * kEpsilon;
103 double h = (1 - kEpsilonSquared) / (3 * kEpsilonSquared + 1);
104 double dy = (1 - h) / 2;
105 cusp[1].fY = (float)(1 - dy);
106 cusp[2].fY = (float)(0 + dy);
107 REPORTER_ASSERT(r, SkFindCubicInflections(cusp, T) == 2);
108 REPORTER_ASSERT(r, SkScalarNearlyEqual(T[1] - T[0], (float)kEpsilon, (float)kEpsilonSquared));
109
110 // Ensure two inflection points barely more than kEpsilon apart do not get flagged as cusps.
111 cusp[1].fY = (float)(1 - 1.1 * dy);
112 cusp[2].fY = (float)(0 + 1.1 * dy);
113 REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(cusp, T, &areCusps) == 2);
114 REPORTER_ASSERT(r, areCusps == false);
115
116 // Ensure two inflection points barely less than kEpsilon apart do get flagged as cusps.
117 cusp[1].fY = (float)(1 - .9 * dy);
118 cusp[2].fY = (float)(0 + .9 * dy);
119 REPORTER_ASSERT(r, GrPathUtils::findCubicConvex180Chops(cusp, T, &areCusps) == 1);
120 REPORTER_ASSERT(r, areCusps == true);
121 }
122
DEF_TEST(GrPathUtils_convertToCubic,r)123 DEF_TEST(GrPathUtils_convertToCubic, r) {
124 SkPoint cubic[4];
125 GrPathUtils::convertLineToCubic({0,0}, {3,6}, cubic);
126 REPORTER_ASSERT(r, cubic[0] == SkPoint::Make(0,0));
127 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fX, 1));
128 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fY, 2));
129 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fX, 2));
130 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fY, 4));
131 REPORTER_ASSERT(r, cubic[3] == SkPoint::Make(3,6));
132
133 SkPoint quad[3] = {{0,0}, {3,3}, {6,0}};
134 GrPathUtils::convertQuadToCubic(quad, cubic);
135 REPORTER_ASSERT(r, cubic[0] == SkPoint::Make(0,0));
136 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fX, 2));
137 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[1].fY, 2));
138 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fX, 4));
139 REPORTER_ASSERT(r, SkScalarNearlyEqual(cubic[2].fY, 2));
140 REPORTER_ASSERT(r, cubic[3] == SkPoint::Make(6,0));
141 }
142