PathCoverageTest.cpp 5.2 KB

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