src/third_party/skia/tests/PathCoverageTest.cpp

   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 "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
  21 static 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.
  28 static inline int cheap_distance(SkScalar dx, SkScalar dy) {
  29     int idx = SkAbs32(SkScalarRoundToInt(dx));
  30     int idy = SkAbs32(SkScalarRoundToInt(dy));
  31     if (idx > idy) {
  32         idx += idy >> 1;
  33     } else {
  34         idx = idy + (idx >> 1);
  35     }
  36     return idx;
  37 }
  38
  39 static 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
  44 static inline SkScalar compute_distance(const SkPoint points[]) {
  45     return points[1].distanceToLineSegmentBetween(points[0], points[2]);
  46 }
  47
  48 static 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
  59 static inline uint32_t compute_pointCount(SkScalar d, SkScalar tol) {
  60     if (d < tol) {
  61        return 1;
  62     } else {
  63        int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol)));
  64        uint32_t count = SkMin32(SkNextPow2(temp), MAX_POINTS_PER_CURVE);
  65        return count;
  66     }
  67 }
  68
  69 static uint32_t quadraticPointCount_EE(const SkPoint points[]) {
  70     int distance = estimate_distance(points);
  71     return estimate_pointCount(distance);
  72 }
  73
  74 static uint32_t quadraticPointCount_EC(const SkPoint points[], SkScalar tol) {
  75     int distance = estimate_distance(points);
  76     return compute_pointCount(SkIntToScalar(distance), tol);
  77 }
  78
  79 static uint32_t quadraticPointCount_CE(const SkPoint points[]) {
  80     SkScalar distance = compute_distance(points);
  81     return estimate_pointCount(SkScalarRoundToInt(distance));
  82 }
  83
  84 static uint32_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
  90 static const int gXY[] = {
  91     4, 0, 0, -4, 8, -4, 12, 0, 8, 4, 0, 4
  92 };
  93
  94 static const int gSawtooth[] = {
  95     0, 0, 10, 10, 20, 20, 30, 10, 40, 0, 50, -10, 60, -20, 70, -10, 80, 0
  96 };
  97
  98 static const int gOvalish[] = {
  99     0, 0, 5, 15, 20, 20, 35, 15, 40, 0
 100 };
 101
 102 static 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
 107 static const int gRibbon[] = {
 108    -4, 0, 4, 20, 0, 25, -4, 20, 4, 0
 109 };
 110
 111 static 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);
 126
 127         if (false) { // avoid bit rot, suppress warning
 128             computedCount =
 129                     quadraticPointCount_EC(path, SkIntToScalar(1));
 130             estimatedCount =
 131                     quadraticPointCount_CE(path);
 132         }
 133         // 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) {
 139             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);
 143             numErrors++;
 144         }
 145     }
 146
 147     return (numErrors == 0);
 148 }
 149
 150
 151
 152 static 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
 160 DEF_TEST(PathCoverage, reporter) {
 161     TestQuadPointCount(reporter);
 162
 163 }