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