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