180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2011 Google Inc. 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 7910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 8910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger#include "Test.h" 9910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger#include "TestClassDef.h" 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkMath.h" 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkPoint.h" 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkScalar.h" 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Duplicates lots of code from gpu/src/GrPathUtils.cpp 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru It'd be nice not to do so, but that code's set up currently to only have 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru a single implementation. 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru*/ 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Sk uses 6, Gr (implicitly) used 10, both apparently arbitrarily. 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define MAX_COEFF_SHIFT 6 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic const uint32_t MAX_POINTS_PER_CURVE = 1 << MAX_COEFF_SHIFT; 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// max + 0.5 min has error [0.0, 0.12] 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// max + 0.375 min has error [-.03, 0.07] 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 0.96043387 max + 0.397824735 min has error [-.06, +.05] 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// For determining the maximum possible number of points to use in 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// drawing a quadratic, we want to err on the high side. 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline int cheap_distance(SkScalar dx, SkScalar dy) { 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int idx = SkAbs32(SkScalarRound(dx)); 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int idy = SkAbs32(SkScalarRound(dy)); 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (idx > idy) { 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru idx += idy >> 1; 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru idx = idy + (idx >> 1); 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return idx; 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline int estimate_distance(const SkPoint points[]) { 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return cheap_distance(points[1].fX * 2 - points[2].fX - points[0].fX, 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru points[1].fY * 2 - points[2].fY - points[0].fY); 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline SkScalar compute_distance(const SkPoint points[]) { 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return points[1].distanceToLineSegmentBetween(points[0], points[2]); 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline uint32_t estimate_pointCount(int distance) { 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Includes -2 bias because this estimator runs 4x high? 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int shift = 30 - SkCLZ(distance); 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Clamp to zero if above subtraction went negative. 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shift &= ~(shift>>31); 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (shift > MAX_COEFF_SHIFT) { 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shift = MAX_COEFF_SHIFT; 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 1 << shift; 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline uint32_t compute_pointCount(SkScalar d, SkScalar tol) { 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (d < tol) { 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 1; 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol))); 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t count = SkMin32(SkNextPow2(temp), MAX_POINTS_PER_CURVE); 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return count; 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 70096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenbergerstatic uint32_t quadraticPointCount_EE(const SkPoint points[]) { 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int distance = estimate_distance(points); 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return estimate_pointCount(distance); 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic uint32_t quadraticPointCount_EC(const SkPoint points[], SkScalar tol) { 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int distance = estimate_distance(points); 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return compute_pointCount(SkIntToScalar(distance), tol); 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 80096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenbergerstatic uint32_t quadraticPointCount_CE(const SkPoint points[]) { 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar distance = compute_distance(points); 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return estimate_pointCount(SkScalarRound(distance)); 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic uint32_t quadraticPointCount_CC(const SkPoint points[], SkScalar tol) { 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar distance = compute_distance(points); 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return compute_pointCount(distance, tol); 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Curve from samplecode/SampleSlides.cpp 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic const int gXY[] = { 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4, 0, 0, -4, 8, -4, 12, 0, 8, 4, 0, 4 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic const int gSawtooth[] = { 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0, 0, 10, 10, 20, 20, 30, 10, 40, 0, 50, -10, 60, -20, 70, -10, 80, 0 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic const int gOvalish[] = { 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0, 0, 5, 15, 20, 20, 35, 15, 40, 0 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic const int gSharpSawtooth[] = { 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0, 0, 1, 10, 2, 0, 3, -10, 4, 0 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Curve crosses back over itself around 0,10 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic const int gRibbon[] = { 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru -4, 0, 4, 20, 0, 25, -4, 20, 4, 0 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool one_d_pe(const int* array, const unsigned int count, 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru skiatest::Reporter* reporter) { 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint path [3]; 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path[1] = SkPoint::Make(SkIntToScalar(array[0]), SkIntToScalar(array[1])); 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path[2] = SkPoint::Make(SkIntToScalar(array[2]), SkIntToScalar(array[3])); 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int numErrors = 0; 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (unsigned i = 4; i < count; i += 2) { 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path[0] = path[1]; 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path[1] = path[2]; 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path[2] = SkPoint::Make(SkIntToScalar(array[i]), 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkIntToScalar(array[i+1])); 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t computedCount = 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru quadraticPointCount_CC(path, SkIntToScalar(1)); 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t estimatedCount = 126096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger quadraticPointCount_EE(path); 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (false) { // avoid bit rot, suppress warning 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru computedCount = 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru quadraticPointCount_EC(path, SkIntToScalar(1)); 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru estimatedCount = 132096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger quadraticPointCount_CE(path); 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Allow estimated to be high by a factor of two, but no less than 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // the computed value. 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool isAccurate = (estimatedCount >= computedCount) && 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru (estimatedCount <= 2 * computedCount); 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!isAccurate) { 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkString errorDescription; 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru errorDescription.printf( 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru "Curve from %.2f %.2f through %.2f %.2f to %.2f %.2f " 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru "computes %d, estimates %d\n", 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path[0].fX, path[0].fY, path[1].fX, path[1].fY, 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path[2].fX, path[2].fY, computedCount, estimatedCount); 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru numErrors++; 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru reporter->reportFailed(errorDescription); 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (numErrors == 0); 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void TestQuadPointCount(skiatest::Reporter* reporter) { 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru one_d_pe(gXY, SK_ARRAY_COUNT(gXY), reporter); 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru one_d_pe(gSawtooth, SK_ARRAY_COUNT(gSawtooth), reporter); 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru one_d_pe(gOvalish, SK_ARRAY_COUNT(gOvalish), reporter); 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru one_d_pe(gSharpSawtooth, SK_ARRAY_COUNT(gSharpSawtooth), reporter); 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru one_d_pe(gRibbon, SK_ARRAY_COUNT(gRibbon), reporter); 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 164910f694aefb0b671dd8522a9afe9b6be645701c1Derek SollenbergerDEF_TEST(PathCoverage, reporter) { 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru TestQuadPointCount(reporter); 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 168