PathCoverageTest.cpp revision a9325fa237dde2654bc841c2bb0a05fc3e57696a 
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 "Test.h"
9#include "TestClassDef.h"
10#include "SkMath.h"
11#include "SkPoint.h"
12#include "SkScalar.h"
13
14/*
15   Duplicates lots of code from gpu/src/GrPathUtils.cpp
16   It'd be nice not to do so, but that code's set up currently to only have
17   a single implementation.
18*/
19
20// Sk uses 6, Gr (implicitly) used 10, both apparently arbitrarily.
21#define MAX_COEFF_SHIFT     6
22static const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT;
23
24// max + 0.5 min has error [0.0, 0.12]
25// max + 0.375 min has error [-.03, 0.07]
26// 0.96043387 max + 0.397824735 min has error [-.06, +.05]
27// For determining the maximum possible number of points to use in
28// drawing a quadratic, we want to err on the high side.
29static inline int cheap_distance(SkScalar dx, SkScalar dy) {
30    int idx = SkAbs32(SkScalarRoundToInt(dx));
31    int idy = SkAbs32(SkScalarRoundToInt(dy));
32    if (idx > idy) {
33        idx += idy >> 1;
34    } else {
35        idx = idy + (idx >> 1);
36    }
37    return idx;
38}
39
40static inline int estimate_distance(const SkPoint points[]) {
41    return cheap_distance(points[1].fX * 2 - points[2].fX - points[0].fX,
42                          points[1].fY * 2 - points[2].fY - points[0].fY);
43}
44
45static inline SkScalar compute_distance(const SkPoint points[]) {
46    return points[1].distanceToLineSegmentBetween(points[0], points[2]);
47}
48
49static inline uint32_t estimate_pointCount(int distance) {
50    // Includes -2 bias because this estimator runs 4x high?
51    int shift = 30 - SkCLZ(distance);
52    // Clamp to zero if above subtraction went negative.
53    shift &= ~(shift>>31);
54    if (shift > MAX_COEFF_SHIFT) {
55        shift = MAX_COEFF_SHIFT;
56    }
57    return 1 << shift;
58}
59
60static inline uint32_t compute_pointCount(SkScalar d, SkScalar tol) {
61    if (d < tol) {
62       return 1;
63    } else {
64       int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol)));
65       uint32_t count = SkMin32(SkNextPow2(temp), MAX_POINTS_PER_CURVE);
66       return count;
67    }
68}
69
70static uint32_t quadraticPointCount_EE(const SkPoint points[]) {
71    int distance = estimate_distance(points);
72    return estimate_pointCount(distance);
73}
74
75static uint32_t quadraticPointCount_EC(const SkPoint points[], SkScalar tol) {
76    int distance = estimate_distance(points);
77    return compute_pointCount(SkIntToScalar(distance), tol);
78}
79
80static uint32_t quadraticPointCount_CE(const SkPoint points[]) {
81    SkScalar distance = compute_distance(points);
82    return estimate_pointCount(SkScalarRoundToInt(distance));
83}
84
85static uint32_t quadraticPointCount_CC(const SkPoint points[], SkScalar tol) {
86    SkScalar distance = compute_distance(points);
87    return compute_pointCount(distance, tol);
88}
89
90// Curve from samplecode/SampleSlides.cpp
91static const int gXY[] = {
92    4, 0, 0, -4, 8, -4, 12, 0, 8, 4, 0, 4
93};
94
95static const int gSawtooth[] = {
96    0, 0, 10, 10, 20, 20, 30, 10, 40, 0, 50, -10, 60, -20, 70, -10, 80, 0
97};
98
99static const int gOvalish[] = {
100    0, 0, 5, 15, 20, 20, 35, 15, 40, 0
101};
102
103static const int gSharpSawtooth[] = {
104    0, 0, 1, 10, 2, 0, 3, -10, 4, 0
105};
106
107// Curve crosses back over itself around 0,10
108static const int gRibbon[] = {
109   -4, 0, 4, 20, 0, 25, -4, 20, 4, 0
110};
111
112static bool one_d_pe(const int* array, const unsigned int count,
113                     skiatest::Reporter* reporter) {
114    SkPoint path [3];
115    path[1] = SkPoint::Make(SkIntToScalar(array[0]), SkIntToScalar(array[1]));
116    path[2] = SkPoint::Make(SkIntToScalar(array[2]), SkIntToScalar(array[3]));
117    int numErrors = 0;
118    for (unsigned i = 4; i < count; i += 2) {
119        path[0] = path[1];
120        path[1] = path[2];
121        path[2] = SkPoint::Make(SkIntToScalar(array[i]),
122                                SkIntToScalar(array[i+1]));
123        uint32_t computedCount =
124            quadraticPointCount_CC(path, SkIntToScalar(1));
125        uint32_t estimatedCount =
126            quadraticPointCount_EE(path);
127
128        if (false) { // avoid bit rot, suppress warning
129            computedCount =
130                    quadraticPointCount_EC(path, SkIntToScalar(1));
131            estimatedCount =
132                    quadraticPointCount_CE(path);
133        }
134        // Allow estimated to be high by a factor of two, but no less than
135        // the computed value.
136        bool isAccurate = (estimatedCount >= computedCount) &&
137            (estimatedCount <= 2 * computedCount);
138
139        if (!isAccurate) {
140            ERRORF(reporter, "Curve from %.2f %.2f through %.2f %.2f to "
141                   "%.2f %.2f computes %d, estimates %d\n",
142                   path[0].fX, path[0].fY, path[1].fX, path[1].fY,
143                   path[2].fX, path[2].fY, computedCount, estimatedCount);
144            numErrors++;
145        }
146    }
147
148    return (numErrors == 0);
149}
150
151
152
153static void TestQuadPointCount(skiatest::Reporter* reporter) {
154    one_d_pe(gXY, SK_ARRAY_COUNT(gXY), reporter);
155    one_d_pe(gSawtooth, SK_ARRAY_COUNT(gSawtooth), reporter);
156    one_d_pe(gOvalish, SK_ARRAY_COUNT(gOvalish), reporter);
157    one_d_pe(gSharpSawtooth, SK_ARRAY_COUNT(gSharpSawtooth), reporter);
158    one_d_pe(gRibbon, SK_ARRAY_COUNT(gRibbon), reporter);
159}
160
161DEF_TEST(PathCoverage, reporter) {
162    TestQuadPointCount(reporter);
163
164}
165