blob: 255156394aecc19cc66677f1160131557b8923ca [file] [log] [blame]
epoger@google.comec3ed6a2011-07-28 14:26:00 +00001/*
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 */
tfarina@chromium.orge4fafb12013-12-12 21:11:12 +00007
halcanary4dbbd042016-06-07 17:21:10 -07008#include "SkMathPriv.h"
tomhudson@google.comddab2272011-06-08 14:46:28 +00009#include "SkPoint.h"
10#include "SkScalar.h"
tfarina@chromium.org8f6884a2014-01-24 20:56:26 +000011#include "Test.h"
tomhudson@google.comddab2272011-06-08 14:46:28 +000012
13/*
14 Duplicates lots of code from gpu/src/GrPathUtils.cpp
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000015 It'd be nice not to do so, but that code's set up currently to only have
16 a single implementation.
tomhudson@google.comddab2272011-06-08 14:46:28 +000017*/
18
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000019// Sk uses 6, Gr (implicitly) used 10, both apparently arbitrarily.
tomhudson@google.comddab2272011-06-08 14:46:28 +000020#define MAX_COEFF_SHIFT 6
21static const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT;
22
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000023// max + 0.5 min has error [0.0, 0.12]
24// max + 0.375 min has error [-.03, 0.07]
25// 0.96043387 max + 0.397824735 min has error [-.06, +.05]
26// For determining the maximum possible number of points to use in
27// drawing a quadratic, we want to err on the high side.
tomhudson@google.comddab2272011-06-08 14:46:28 +000028static inline int cheap_distance(SkScalar dx, SkScalar dy) {
reed@google.come1ca7052013-12-17 19:22:07 +000029 int idx = SkAbs32(SkScalarRoundToInt(dx));
30 int idy = SkAbs32(SkScalarRoundToInt(dy));
tomhudson@google.comddab2272011-06-08 14:46:28 +000031 if (idx > idy) {
32 idx += idy >> 1;
33 } else {
34 idx = idy + (idx >> 1);
35 }
36 return idx;
37}
38
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000039static inline int estimate_distance(const SkPoint points[]) {
40 return cheap_distance(points[1].fX * 2 - points[2].fX - points[0].fX,
41 points[1].fY * 2 - points[2].fY - points[0].fY);
tomhudson@google.comddab2272011-06-08 14:46:28 +000042}
43
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000044static inline SkScalar compute_distance(const SkPoint points[]) {
45 return points[1].distanceToLineSegmentBetween(points[0], points[2]);
46}
tomhudson@google.comddab2272011-06-08 14:46:28 +000047
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000048static inline uint32_t estimate_pointCount(int distance) {
49 // Includes -2 bias because this estimator runs 4x high?
50 int shift = 30 - SkCLZ(distance);
51 // Clamp to zero if above subtraction went negative.
52 shift &= ~(shift>>31);
tomhudson@google.comddab2272011-06-08 14:46:28 +000053 if (shift > MAX_COEFF_SHIFT) {
54 shift = MAX_COEFF_SHIFT;
55 }
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000056 return 1 << shift;
tomhudson@google.comddab2272011-06-08 14:46:28 +000057}
58
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000059static inline uint32_t compute_pointCount(SkScalar d, SkScalar tol) {
tomhudson@google.comddab2272011-06-08 14:46:28 +000060 if (d < tol) {
61 return 1;
62 } else {
reed80ea19c2015-05-12 10:37:34 -070063 int temp = SkScalarCeilToInt(SkScalarSqrt(d / tol));
robertphillips@google.com6853e802012-04-16 15:50:18 +000064 uint32_t count = SkMin32(SkNextPow2(temp), MAX_POINTS_PER_CURVE);
tomhudson@google.comddab2272011-06-08 14:46:28 +000065 return count;
66 }
67}
68
sugoi@google.com54f0d1b2013-02-27 19:17:41 +000069static uint32_t quadraticPointCount_EE(const SkPoint points[]) {
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000070 int distance = estimate_distance(points);
71 return estimate_pointCount(distance);
72}
73
caryclark@google.com42639cd2012-06-06 12:03:39 +000074static uint32_t quadraticPointCount_EC(const SkPoint points[], SkScalar tol) {
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000075 int distance = estimate_distance(points);
76 return compute_pointCount(SkIntToScalar(distance), tol);
77}
78
sugoi@google.com54f0d1b2013-02-27 19:17:41 +000079static uint32_t quadraticPointCount_CE(const SkPoint points[]) {
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000080 SkScalar distance = compute_distance(points);
reed@google.come1ca7052013-12-17 19:22:07 +000081 return estimate_pointCount(SkScalarRoundToInt(distance));
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000082}
83
caryclark@google.com42639cd2012-06-06 12:03:39 +000084static uint32_t quadraticPointCount_CC(const SkPoint points[], SkScalar tol) {
tomhudson@google.comfc1539a2011-06-24 15:43:24 +000085 SkScalar distance = compute_distance(points);
86 return compute_pointCount(distance, tol);
87}
88
tomhudson@google.comddab2272011-06-08 14:46:28 +000089// Curve from samplecode/SampleSlides.cpp
90static const int gXY[] = {
91 4, 0, 0, -4, 8, -4, 12, 0, 8, 4, 0, 4
92};
93
94static const int gSawtooth[] = {
95 0, 0, 10, 10, 20, 20, 30, 10, 40, 0, 50, -10, 60, -20, 70, -10, 80, 0
96};
97
98static const int gOvalish[] = {
99 0, 0, 5, 15, 20, 20, 35, 15, 40, 0
100};
101
102static const int gSharpSawtooth[] = {
103 0, 0, 1, 10, 2, 0, 3, -10, 4, 0
104};
105
106// Curve crosses back over itself around 0,10
107static const int gRibbon[] = {
108 -4, 0, 4, 20, 0, 25, -4, 20, 4, 0
109};
110
111static bool one_d_pe(const int* array, const unsigned int count,
112 skiatest::Reporter* reporter) {
113 SkPoint path [3];
114 path[1] = SkPoint::Make(SkIntToScalar(array[0]), SkIntToScalar(array[1]));
115 path[2] = SkPoint::Make(SkIntToScalar(array[2]), SkIntToScalar(array[3]));
116 int numErrors = 0;
tomhudson@google.comfc1539a2011-06-24 15:43:24 +0000117 for (unsigned i = 4; i < count; i += 2) {
tomhudson@google.comddab2272011-06-08 14:46:28 +0000118 path[0] = path[1];
119 path[1] = path[2];
120 path[2] = SkPoint::Make(SkIntToScalar(array[i]),
121 SkIntToScalar(array[i+1]));
122 uint32_t computedCount =
tomhudson@google.comfc1539a2011-06-24 15:43:24 +0000123 quadraticPointCount_CC(path, SkIntToScalar(1));
tomhudson@google.comddab2272011-06-08 14:46:28 +0000124 uint32_t estimatedCount =
sugoi@google.com54f0d1b2013-02-27 19:17:41 +0000125 quadraticPointCount_EE(path);
rmistry@google.comd6176b02012-08-23 18:14:13 +0000126
caryclark@google.com42639cd2012-06-06 12:03:39 +0000127 if (false) { // avoid bit rot, suppress warning
128 computedCount =
129 quadraticPointCount_EC(path, SkIntToScalar(1));
130 estimatedCount =
sugoi@google.com54f0d1b2013-02-27 19:17:41 +0000131 quadraticPointCount_CE(path);
caryclark@google.com42639cd2012-06-06 12:03:39 +0000132 }
tomhudson@google.comfc1539a2011-06-24 15:43:24 +0000133 // Allow estimated to be high by a factor of two, but no less than
134 // the computed value.
135 bool isAccurate = (estimatedCount >= computedCount) &&
136 (estimatedCount <= 2 * computedCount);
137
138 if (!isAccurate) {
halcanary@google.coma9325fa2014-01-10 14:58:10 +0000139 ERRORF(reporter, "Curve from %.2f %.2f through %.2f %.2f to "
140 "%.2f %.2f computes %d, estimates %d\n",
141 path[0].fX, path[0].fY, path[1].fX, path[1].fY,
142 path[2].fX, path[2].fY, computedCount, estimatedCount);
tomhudson@google.comddab2272011-06-08 14:46:28 +0000143 numErrors++;
tomhudson@google.comddab2272011-06-08 14:46:28 +0000144 }
145 }
146
tomhudson@google.comddab2272011-06-08 14:46:28 +0000147 return (numErrors == 0);
148}
149
150
151
152static void TestQuadPointCount(skiatest::Reporter* reporter) {
153 one_d_pe(gXY, SK_ARRAY_COUNT(gXY), reporter);
154 one_d_pe(gSawtooth, SK_ARRAY_COUNT(gSawtooth), reporter);
155 one_d_pe(gOvalish, SK_ARRAY_COUNT(gOvalish), reporter);
156 one_d_pe(gSharpSawtooth, SK_ARRAY_COUNT(gSharpSawtooth), reporter);
157 one_d_pe(gRibbon, SK_ARRAY_COUNT(gRibbon), reporter);
158}
159
tfarina@chromium.orge4fafb12013-12-12 21:11:12 +0000160DEF_TEST(PathCoverage, reporter) {
tomhudson@google.comddab2272011-06-08 14:46:28 +0000161 TestQuadPointCount(reporter);
162
163}