1 /* 2 * Copyright 2011 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 "SkGeometry.h" 9 #include "SkPointPriv.h" 10 #include "SkRandom.h" 11 #include "Test.h" 12 #include <array> 13 #include <numeric> 14 15 static bool nearly_equal(const SkPoint& a, const SkPoint& b) { 16 return SkScalarNearlyEqual(a.fX, b.fX) && SkScalarNearlyEqual(a.fY, b.fY); 17 } 18 19 static void testChopCubic(skiatest::Reporter* reporter) { 20 /* 21 Inspired by this test, which used to assert that the tValues had dups 22 23 <path stroke="#202020" d="M0,0 C0,0 1,1 2190,5130 C2190,5070 2220,5010 2205,4980" /> 24 */ 25 const SkPoint src[] = { 26 { SkIntToScalar(2190), SkIntToScalar(5130) }, 27 { SkIntToScalar(2190), SkIntToScalar(5070) }, 28 { SkIntToScalar(2220), SkIntToScalar(5010) }, 29 { SkIntToScalar(2205), SkIntToScalar(4980) }, 30 }; 31 SkPoint dst[13]; 32 SkScalar tValues[3]; 33 // make sure we don't assert internally 34 int count = SkChopCubicAtMaxCurvature(src, dst, tValues); 35 if (false) { // avoid bit rot, suppress warning 36 REPORTER_ASSERT(reporter, count); 37 } 38 } 39 40 static void check_pairs(skiatest::Reporter* reporter, int index, SkScalar t, const char name[], 41 SkScalar x0, SkScalar y0, SkScalar x1, SkScalar y1) { 42 bool eq = SkScalarNearlyEqual(x0, x1) && SkScalarNearlyEqual(y0, y1); 43 if (!eq) { 44 SkDebugf("%s [%d %g] p0 [%10.8f %10.8f] p1 [%10.8f %10.8f]\n", 45 name, index, t, x0, y0, x1, y1); 46 REPORTER_ASSERT(reporter, eq); 47 } 48 } 49 50 static void test_evalquadat(skiatest::Reporter* reporter) { 51 SkRandom rand; 52 for (int i = 0; i < 1000; ++i) { 53 SkPoint pts[3]; 54 for (int j = 0; j < 3; ++j) { 55 pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100); 56 } 57 const SkScalar dt = SK_Scalar1 / 128; 58 SkScalar t = dt; 59 for (int j = 1; j < 128; ++j) { 60 SkPoint r0; 61 SkEvalQuadAt(pts, t, &r0); 62 SkPoint r1 = SkEvalQuadAt(pts, t); 63 check_pairs(reporter, i, t, "quad-pos", r0.fX, r0.fY, r1.fX, r1.fY); 64 65 SkVector v0; 66 SkEvalQuadAt(pts, t, nullptr, &v0); 67 SkVector v1 = SkEvalQuadTangentAt(pts, t); 68 check_pairs(reporter, i, t, "quad-tan", v0.fX, v0.fY, v1.fX, v1.fY); 69 70 t += dt; 71 } 72 } 73 } 74 75 static void test_conic_eval_pos(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) { 76 SkPoint p0, p1; 77 conic.evalAt(t, &p0, nullptr); 78 p1 = conic.evalAt(t); 79 check_pairs(reporter, 0, t, "conic-pos", p0.fX, p0.fY, p1.fX, p1.fY); 80 } 81 82 static void test_conic_eval_tan(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) { 83 SkVector v0, v1; 84 conic.evalAt(t, nullptr, &v0); 85 v1 = conic.evalTangentAt(t); 86 check_pairs(reporter, 0, t, "conic-tan", v0.fX, v0.fY, v1.fX, v1.fY); 87 } 88 89 static void test_conic(skiatest::Reporter* reporter) { 90 SkRandom rand; 91 for (int i = 0; i < 1000; ++i) { 92 SkPoint pts[3]; 93 for (int j = 0; j < 3; ++j) { 94 pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100); 95 } 96 for (int k = 0; k < 10; ++k) { 97 SkScalar w = rand.nextUScalar1() * 2; 98 SkConic conic(pts, w); 99 100 const SkScalar dt = SK_Scalar1 / 128; 101 SkScalar t = dt; 102 for (int j = 1; j < 128; ++j) { 103 test_conic_eval_pos(reporter, conic, t); 104 test_conic_eval_tan(reporter, conic, t); 105 t += dt; 106 } 107 } 108 } 109 } 110 111 static void test_quad_tangents(skiatest::Reporter* reporter) { 112 SkPoint pts[] = { 113 {10, 20}, {10, 20}, {20, 30}, 114 {10, 20}, {15, 25}, {20, 30}, 115 {10, 20}, {20, 30}, {20, 30}, 116 }; 117 int count = (int) SK_ARRAY_COUNT(pts) / 3; 118 for (int index = 0; index < count; ++index) { 119 SkConic conic(&pts[index * 3], 0.707f); 120 SkVector start = SkEvalQuadTangentAt(&pts[index * 3], 0); 121 SkVector mid = SkEvalQuadTangentAt(&pts[index * 3], .5f); 122 SkVector end = SkEvalQuadTangentAt(&pts[index * 3], 1); 123 REPORTER_ASSERT(reporter, start.fX && start.fY); 124 REPORTER_ASSERT(reporter, mid.fX && mid.fY); 125 REPORTER_ASSERT(reporter, end.fX && end.fY); 126 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid))); 127 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end))); 128 } 129 } 130 131 static void test_conic_tangents(skiatest::Reporter* reporter) { 132 SkPoint pts[] = { 133 { 10, 20}, {10, 20}, {20, 30}, 134 { 10, 20}, {15, 25}, {20, 30}, 135 { 10, 20}, {20, 30}, {20, 30} 136 }; 137 int count = (int) SK_ARRAY_COUNT(pts) / 3; 138 for (int index = 0; index < count; ++index) { 139 SkConic conic(&pts[index * 3], 0.707f); 140 SkVector start = conic.evalTangentAt(0); 141 SkVector mid = conic.evalTangentAt(.5f); 142 SkVector end = conic.evalTangentAt(1); 143 REPORTER_ASSERT(reporter, start.fX && start.fY); 144 REPORTER_ASSERT(reporter, mid.fX && mid.fY); 145 REPORTER_ASSERT(reporter, end.fX && end.fY); 146 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid))); 147 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end))); 148 } 149 } 150 151 static void test_this_conic_to_quad(skiatest::Reporter* r, const SkPoint pts[3], SkScalar w) { 152 SkAutoConicToQuads quadder; 153 const SkPoint* qpts = quadder.computeQuads(pts, w, 0.25); 154 const int qcount = quadder.countQuads(); 155 const int pcount = qcount * 2 + 1; 156 157 REPORTER_ASSERT(r, SkPointPriv::AreFinite(qpts, pcount)); 158 } 159 160 /** 161 * We need to ensure that when a conic is approximated by quads, that we always return finite 162 * values in the quads. 163 * 164 * Inspired by crbug_627414 165 */ 166 static void test_conic_to_quads(skiatest::Reporter* reporter) { 167 const SkPoint triples[] = { 168 { 0, 0 }, { 1, 0 }, { 1, 1 }, 169 { 0, 0 }, { 3.58732e-43f, 2.72084f }, { 3.00392f, 3.00392f }, 170 { 0, 0 }, { 100000, 0 }, { 100000, 100000 }, 171 { 0, 0 }, { 1e30f, 0 }, { 1e30f, 1e30f }, 172 }; 173 const int N = sizeof(triples) / sizeof(SkPoint); 174 175 for (int i = 0; i < N; i += 3) { 176 const SkPoint* pts = &triples[i]; 177 178 SkRect bounds; 179 bounds.set(pts, 3); 180 181 SkScalar w = 1e30f; 182 do { 183 w *= 2; 184 test_this_conic_to_quad(reporter, pts, w); 185 } while (SkScalarIsFinite(w)); 186 test_this_conic_to_quad(reporter, pts, SK_ScalarNaN); 187 } 188 } 189 190 static void test_cubic_tangents(skiatest::Reporter* reporter) { 191 SkPoint pts[] = { 192 { 10, 20}, {10, 20}, {20, 30}, {30, 40}, 193 { 10, 20}, {15, 25}, {20, 30}, {30, 40}, 194 { 10, 20}, {20, 30}, {30, 40}, {30, 40}, 195 }; 196 int count = (int) SK_ARRAY_COUNT(pts) / 4; 197 for (int index = 0; index < count; ++index) { 198 SkConic conic(&pts[index * 3], 0.707f); 199 SkVector start, mid, end; 200 SkEvalCubicAt(&pts[index * 4], 0, nullptr, &start, nullptr); 201 SkEvalCubicAt(&pts[index * 4], .5f, nullptr, &mid, nullptr); 202 SkEvalCubicAt(&pts[index * 4], 1, nullptr, &end, nullptr); 203 REPORTER_ASSERT(reporter, start.fX && start.fY); 204 REPORTER_ASSERT(reporter, mid.fX && mid.fY); 205 REPORTER_ASSERT(reporter, end.fX && end.fY); 206 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid))); 207 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end))); 208 } 209 } 210 211 static void check_cubic_type(skiatest::Reporter* reporter, 212 const std::array<SkPoint, 4>& bezierPoints, SkCubicType expectedType, 213 bool undefined = false) { 214 // Classify the cubic even if the results will be undefined: check for crashes and asserts. 215 SkCubicType actualType = SkClassifyCubic(bezierPoints.data()); 216 if (!undefined) { 217 REPORTER_ASSERT(reporter, actualType == expectedType); 218 } 219 } 220 221 static void check_cubic_around_rect(skiatest::Reporter* reporter, 222 float x1, float y1, float x2, float y2, 223 bool undefined = false) { 224 static constexpr SkCubicType expectations[24] = { 225 SkCubicType::kLoop, 226 SkCubicType::kCuspAtInfinity, 227 SkCubicType::kLocalCusp, 228 SkCubicType::kLocalCusp, 229 SkCubicType::kCuspAtInfinity, 230 SkCubicType::kLoop, 231 SkCubicType::kCuspAtInfinity, 232 SkCubicType::kLoop, 233 SkCubicType::kCuspAtInfinity, 234 SkCubicType::kLoop, 235 SkCubicType::kLocalCusp, 236 SkCubicType::kLocalCusp, 237 SkCubicType::kLocalCusp, 238 SkCubicType::kLocalCusp, 239 SkCubicType::kLoop, 240 SkCubicType::kCuspAtInfinity, 241 SkCubicType::kLoop, 242 SkCubicType::kCuspAtInfinity, 243 SkCubicType::kLoop, 244 SkCubicType::kCuspAtInfinity, 245 SkCubicType::kLocalCusp, 246 SkCubicType::kLocalCusp, 247 SkCubicType::kCuspAtInfinity, 248 SkCubicType::kLoop, 249 }; 250 SkPoint points[] = {{x1, y1}, {x2, y1}, {x2, y2}, {x1, y2}}; 251 std::array<SkPoint, 4> bezier; 252 for (int i=0; i < 4; ++i) { 253 bezier[0] = points[i]; 254 for (int j=0; j < 3; ++j) { 255 int jidx = (j < i) ? j : j+1; 256 bezier[1] = points[jidx]; 257 for (int k=0, kidx=0; k < 2; ++k, ++kidx) { 258 for (int n = 0; n < 2; ++n) { 259 kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx; 260 } 261 bezier[2] = points[kidx]; 262 for (int l = 0; l < 4; ++l) { 263 if (l != i && l != jidx && l != kidx) { 264 bezier[3] = points[l]; 265 break; 266 } 267 } 268 check_cubic_type(reporter, bezier, expectations[i*6 + j*2 + k], undefined); 269 } 270 } 271 } 272 for (int i=0; i < 4; ++i) { 273 bezier[0] = points[i]; 274 for (int j=0; j < 3; ++j) { 275 int jidx = (j < i) ? j : j+1; 276 bezier[1] = points[jidx]; 277 bezier[2] = points[jidx]; 278 for (int k=0, kidx=0; k < 2; ++k, ++kidx) { 279 for (int n = 0; n < 2; ++n) { 280 kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx; 281 } 282 bezier[3] = points[kidx]; 283 check_cubic_type(reporter, bezier, SkCubicType::kSerpentine, undefined); 284 } 285 } 286 } 287 } 288 289 static void test_classify_cubic(skiatest::Reporter* reporter) { 290 check_cubic_type(reporter, {{{149.325f, 107.705f}, {149.325f, 103.783f}, 291 {151.638f, 100.127f}, {156.263f, 96.736f}}}, 292 SkCubicType::kSerpentine); 293 check_cubic_type(reporter, {{{225.694f, 223.15f}, {209.831f, 224.837f}, 294 {195.994f, 230.237f}, {184.181f, 239.35f}}}, 295 SkCubicType::kSerpentine); 296 check_cubic_type(reporter, {{{4.873f, 5.581f}, {5.083f, 5.2783f}, 297 {5.182f, 4.8593f}, {5.177f, 4.3242f}}}, 298 SkCubicType::kSerpentine); 299 check_cubic_around_rect(reporter, 0, 0, 1, 1); 300 check_cubic_around_rect(reporter, 301 -std::numeric_limits<float>::max(), 302 -std::numeric_limits<float>::max(), 303 +std::numeric_limits<float>::max(), 304 +std::numeric_limits<float>::max()); 305 check_cubic_around_rect(reporter, 1, 1, 306 +std::numeric_limits<float>::min(), 307 +std::numeric_limits<float>::max()); 308 check_cubic_around_rect(reporter, 309 -std::numeric_limits<float>::min(), 310 -std::numeric_limits<float>::min(), 311 +std::numeric_limits<float>::min(), 312 +std::numeric_limits<float>::min()); 313 check_cubic_around_rect(reporter, +1, -std::numeric_limits<float>::min(), -1, -1); 314 check_cubic_around_rect(reporter, 315 -std::numeric_limits<float>::infinity(), 316 -std::numeric_limits<float>::infinity(), 317 +std::numeric_limits<float>::infinity(), 318 +std::numeric_limits<float>::infinity(), 319 true); 320 check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::infinity(), true); 321 check_cubic_around_rect(reporter, 322 -std::numeric_limits<float>::quiet_NaN(), 323 -std::numeric_limits<float>::quiet_NaN(), 324 +std::numeric_limits<float>::quiet_NaN(), 325 +std::numeric_limits<float>::quiet_NaN(), 326 true); 327 check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::quiet_NaN(), true); 328 } 329 330 DEF_TEST(Geometry, reporter) { 331 SkPoint pts[3], dst[5]; 332 333 pts[0].set(0, 0); 334 pts[1].set(100, 50); 335 pts[2].set(0, 100); 336 337 int count = SkChopQuadAtMaxCurvature(pts, dst); 338 REPORTER_ASSERT(reporter, count == 1 || count == 2); 339 340 pts[0].set(0, 0); 341 pts[1].set(3, 0); 342 pts[2].set(3, 3); 343 SkConvertQuadToCubic(pts, dst); 344 const SkPoint cubic[] = { 345 { 0, 0, }, { 2, 0, }, { 3, 1, }, { 3, 3 }, 346 }; 347 for (int i = 0; i < 4; ++i) { 348 REPORTER_ASSERT(reporter, nearly_equal(cubic[i], dst[i])); 349 } 350 351 testChopCubic(reporter); 352 test_evalquadat(reporter); 353 test_conic(reporter); 354 test_cubic_tangents(reporter); 355 test_quad_tangents(reporter); 356 test_conic_tangents(reporter); 357 test_conic_to_quads(reporter); 358 test_classify_cubic(reporter); 359 } 360
