SkIntersections.cpp 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173
  1. /*
  2. * Copyright 2012 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 "src/pathops/SkIntersections.h"
  8. int SkIntersections::closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt,
  9. double* closestDist) const {
  10. int closest = -1;
  11. *closestDist = SK_ScalarMax;
  12. for (int index = 0; index < fUsed; ++index) {
  13. if (!between(rangeStart, fT[0][index], rangeEnd)) {
  14. continue;
  15. }
  16. const SkDPoint& iPt = fPt[index];
  17. double dist = testPt.distanceSquared(iPt);
  18. if (*closestDist > dist) {
  19. *closestDist = dist;
  20. closest = index;
  21. }
  22. }
  23. return closest;
  24. }
  25. void SkIntersections::flip() {
  26. for (int index = 0; index < fUsed; ++index) {
  27. fT[1][index] = 1 - fT[1][index];
  28. }
  29. }
  30. int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
  31. if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
  32. // For now, don't allow a mix of coincident and non-coincident intersections
  33. return -1;
  34. }
  35. SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
  36. int index;
  37. for (index = 0; index < fUsed; ++index) {
  38. double oldOne = fT[0][index];
  39. double oldTwo = fT[1][index];
  40. if (one == oldOne && two == oldTwo) {
  41. return -1;
  42. }
  43. if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
  44. if ((!precisely_zero(one) || precisely_zero(oldOne))
  45. && (!precisely_equal(one, 1) || precisely_equal(oldOne, 1))
  46. && (!precisely_zero(two) || precisely_zero(oldTwo))
  47. && (!precisely_equal(two, 1) || precisely_equal(oldTwo, 1))) {
  48. return -1;
  49. }
  50. SkASSERT(one >= 0 && one <= 1);
  51. SkASSERT(two >= 0 && two <= 1);
  52. // remove this and reinsert below in case replacing would make list unsorted
  53. int remaining = fUsed - index - 1;
  54. memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
  55. memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
  56. memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
  57. int clearMask = ~((1 << index) - 1);
  58. fIsCoincident[0] -= (fIsCoincident[0] >> 1) & clearMask;
  59. fIsCoincident[1] -= (fIsCoincident[1] >> 1) & clearMask;
  60. --fUsed;
  61. break;
  62. }
  63. #if ONE_OFF_DEBUG
  64. if (pt.roughlyEqual(fPt[index])) {
  65. SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
  66. }
  67. #endif
  68. }
  69. for (index = 0; index < fUsed; ++index) {
  70. if (fT[0][index] > one) {
  71. break;
  72. }
  73. }
  74. if (fUsed >= fMax) {
  75. SkOPASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must
  76. // be propagated all the way back down to the caller, and return failure.
  77. fUsed = 0;
  78. return 0;
  79. }
  80. int remaining = fUsed - index;
  81. if (remaining > 0) {
  82. memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
  83. memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
  84. memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
  85. int clearMask = ~((1 << index) - 1);
  86. fIsCoincident[0] += fIsCoincident[0] & clearMask;
  87. fIsCoincident[1] += fIsCoincident[1] & clearMask;
  88. }
  89. fPt[index] = pt;
  90. if (one < 0 || one > 1) {
  91. return -1;
  92. }
  93. if (two < 0 || two > 1) {
  94. return -1;
  95. }
  96. fT[0][index] = one;
  97. fT[1][index] = two;
  98. ++fUsed;
  99. SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt));
  100. return index;
  101. }
  102. void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) {
  103. SkASSERT(one == 0 || one == 1);
  104. SkASSERT(two == 0 || two == 1);
  105. SkASSERT(pt1 != pt2);
  106. fNearlySame[one ? 1 : 0] = true;
  107. (void) insert(one, two, pt1);
  108. fPt2[one ? 1 : 0] = pt2;
  109. }
  110. int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
  111. int index = insertSwap(one, two, pt);
  112. if (index >= 0) {
  113. setCoincident(index);
  114. }
  115. return index;
  116. }
  117. void SkIntersections::setCoincident(int index) {
  118. SkASSERT(index >= 0);
  119. int bit = 1 << index;
  120. fIsCoincident[0] |= bit;
  121. fIsCoincident[1] |= bit;
  122. }
  123. void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b,
  124. int bIndex) {
  125. this->reset();
  126. fT[0][0] = a.fT[0][aIndex];
  127. fT[1][0] = b.fT[0][bIndex];
  128. fPt[0] = a.fPt[aIndex];
  129. fPt2[0] = b.fPt[bIndex];
  130. fUsed = 1;
  131. }
  132. int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const {
  133. int result = -1;
  134. for (int index = 0; index < fUsed; ++index) {
  135. if (!between(rangeStart, fT[0][index], rangeEnd)) {
  136. continue;
  137. }
  138. if (result < 0) {
  139. result = index;
  140. continue;
  141. }
  142. SkDVector best = fPt[result] - origin;
  143. SkDVector test = fPt[index] - origin;
  144. if (test.crossCheck(best) < 0) {
  145. result = index;
  146. }
  147. }
  148. return result;
  149. }
  150. void SkIntersections::removeOne(int index) {
  151. int remaining = --fUsed - index;
  152. if (remaining <= 0) {
  153. return;
  154. }
  155. memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
  156. memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
  157. memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
  158. // SkASSERT(fIsCoincident[0] == 0);
  159. int coBit = fIsCoincident[0] & (1 << index);
  160. fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
  161. SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
  162. fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
  163. }