Home | History | Annotate | Download | only in tests
      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 }
    164