1
2/*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8#include "SkMath.h"
9#include "SkPoint.h"
10#include "SkScalar.h"
11#include "Test.h"
12
13/*
14   Duplicates lots of code from gpu/src/GrPathUtils.cpp
15   It'd be nice not to do so, but that code's set up currently to only have
16   a single implementation.
17*/
18
19// Sk uses 6, Gr (implicitly) used 10, both apparently arbitrarily.
20#define MAX_COEFF_SHIFT     6
21static const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT;
22
23// 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.
28static inline int cheap_distance(SkScalar dx, SkScalar dy) {
29    int idx = SkAbs32(SkScalarRound(dx));
30    int idy = SkAbs32(SkScalarRound(dy));
31    if (idx > idy) {
32        idx += idy >> 1;
33    } else {
34        idx = idy + (idx >> 1);
35    }
36    return idx;
37}
38
39static 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);
42}
43
44static inline SkScalar compute_distance(const SkPoint points[]) {
45    return points[1].distanceToLineSegmentBetween(points[0], points[2]);
46}
47
48static 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);
53    if (shift > MAX_COEFF_SHIFT) {
54        shift = MAX_COEFF_SHIFT;
55    }
56    return 1 << shift;
57}
58
59static inline uint32_t compute_pointCount(SkScalar d, SkScalar tol) {
60    if (d < tol) {
61       return 1;
62    } else {
63       int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
64       uint32_t count = SkMinScalar(SkNextPow2(temp), MAX_POINTS_PER_CURVE);
65       return count;
66    }
67}
68
69uint32_t quadraticPointCount_EE(const SkPoint points[], SkScalar tol) {
70    int distance = estimate_distance(points);
71    return estimate_pointCount(distance);
72}
73
74uint32_t quadraticPointCount_EC(const SkPoint points[], SkScalar tol) {
75    int distance = estimate_distance(points);
76    return compute_pointCount(SkIntToScalar(distance), tol);
77}
78
79uint32_t quadraticPointCount_CE(const SkPoint points[], SkScalar tol) {
80    SkScalar distance = compute_distance(points);
81    return estimate_pointCount(SkScalarRound(distance));
82}
83
84uint32_t quadraticPointCount_CC(const SkPoint points[], SkScalar tol) {
85    SkScalar distance = compute_distance(points);
86    return compute_pointCount(distance, tol);
87}
88
89// 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;
117    for (unsigned i = 4; i < count; i += 2) {
118        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 =
123            quadraticPointCount_CC(path, SkIntToScalar(1));
124        uint32_t estimatedCount =
125            quadraticPointCount_EE(path, SkIntToScalar(1));
126        // Allow estimated to be high by a factor of two, but no less than
127        // the computed value.
128        bool isAccurate = (estimatedCount >= computedCount) &&
129            (estimatedCount <= 2 * computedCount);
130
131        if (!isAccurate) {
132            SkString errorDescription;
133            errorDescription.printf(
134                "Curve from %.2f %.2f through %.2f %.2f to %.2f %.2f "
135                "computes %d, estimates %d\n",
136                path[0].fX, path[0].fY, path[1].fX, path[1].fY,
137                path[2].fX, path[2].fY, computedCount, estimatedCount);
138            numErrors++;
139            reporter->reportFailed(errorDescription);
140        }
141    }
142
143    return (numErrors == 0);
144}
145
146
147
148static void TestQuadPointCount(skiatest::Reporter* reporter) {
149    one_d_pe(gXY, SK_ARRAY_COUNT(gXY), reporter);
150    one_d_pe(gSawtooth, SK_ARRAY_COUNT(gSawtooth), reporter);
151    one_d_pe(gOvalish, SK_ARRAY_COUNT(gOvalish), reporter);
152    one_d_pe(gSharpSawtooth, SK_ARRAY_COUNT(gSharpSawtooth), reporter);
153    one_d_pe(gRibbon, SK_ARRAY_COUNT(gRibbon), reporter);
154}
155
156static void TestPathCoverage(skiatest::Reporter* reporter) {
157    TestQuadPointCount(reporter);
158
159}
160
161#include "TestClassDef.h"
162DEFINE_TESTCLASS("PathCoverage", PathCoverageTestClass, TestPathCoverage)
163