caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
| 8 | #include "SkIntersections.h" |
| 9 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 10 | int SkIntersections::closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, |
| 11 | double* closestDist) const { |
| 12 | int closest = -1; |
| 13 | *closestDist = SK_ScalarMax; |
| 14 | for (int index = 0; index < fUsed; ++index) { |
| 15 | if (!between(rangeStart, fT[0][index], rangeEnd)) { |
| 16 | continue; |
| 17 | } |
| 18 | const SkDPoint& iPt = fPt[index]; |
| 19 | double dist = testPt.distanceSquared(iPt); |
| 20 | if (*closestDist > dist) { |
| 21 | *closestDist = dist; |
| 22 | closest = index; |
| 23 | } |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 24 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 25 | return closest; |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 26 | } |
| 27 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 28 | void SkIntersections::flip() { |
| 29 | for (int index = 0; index < fUsed; ++index) { |
| 30 | fT[1][index] = 1 - fT[1][index]; |
| 31 | } |
| 32 | } |
| 33 | |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 34 | int SkIntersections::insert(double one, double two, const SkDPoint& pt) { |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 35 | if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { |
| 36 | // For now, don't allow a mix of coincident and non-coincident intersections |
| 37 | return -1; |
| 38 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 39 | SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]); |
| 40 | int index; |
| 41 | for (index = 0; index < fUsed; ++index) { |
| 42 | double oldOne = fT[0][index]; |
| 43 | double oldTwo = fT[1][index]; |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 44 | if (one == oldOne && two == oldTwo) { |
| 45 | return -1; |
| 46 | } |
| 47 | if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 48 | if ((precisely_zero(one) && !precisely_zero(oldOne)) |
| 49 | || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1)) |
| 50 | || (precisely_zero(two) && !precisely_zero(oldTwo)) |
| 51 | || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) { |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 52 | SkASSERT(one >= 0 && one <= 1); |
| 53 | SkASSERT(two >= 0 && two <= 1); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 54 | fT[0][index] = one; |
| 55 | fT[1][index] = two; |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 56 | fPt[index] = pt; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 57 | } |
| 58 | return -1; |
| 59 | } |
| 60 | #if ONE_OFF_DEBUG |
| 61 | if (pt.roughlyEqual(fPt[index])) { |
| 62 | SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); |
| 63 | } |
| 64 | #endif |
| 65 | if (fT[0][index] > one) { |
| 66 | break; |
| 67 | } |
| 68 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 69 | if (fUsed >= fMax) { |
caryclark | 595ac28 | 2016-10-24 08:41:45 -0700 | [diff] [blame] | 70 | SkOPASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 71 | // be propagated all the way back down to the caller, and return failure. |
| 72 | fUsed = 0; |
| 73 | return 0; |
| 74 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 75 | int remaining = fUsed - index; |
| 76 | if (remaining > 0) { |
| 77 | memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); |
| 78 | memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); |
| 79 | memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 80 | int clearMask = ~((1 << index) - 1); |
| 81 | fIsCoincident[0] += fIsCoincident[0] & clearMask; |
| 82 | fIsCoincident[1] += fIsCoincident[1] & clearMask; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 83 | } |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 84 | fPt[index] = pt; |
Cary Clark | 8af026e | 2017-03-01 14:02:02 -0500 | [diff] [blame] | 85 | if (one < 0 || one > 1) { |
| 86 | return -1; |
| 87 | } |
| 88 | if (two < 0 || two > 1) { |
| 89 | return -1; |
| 90 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 91 | fT[0][index] = one; |
| 92 | fT[1][index] = two; |
| 93 | ++fUsed; |
caryclark | 94c902e | 2015-08-18 07:12:43 -0700 | [diff] [blame] | 94 | SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt)); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 95 | return index; |
| 96 | } |
| 97 | |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 98 | void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) { |
| 99 | SkASSERT(one == 0 || one == 1); |
| 100 | SkASSERT(two == 0 || two == 1); |
| 101 | SkASSERT(pt1 != pt2); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 102 | fNearlySame[one ? 1 : 0] = true; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 103 | (void) insert(one, two, pt1); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 104 | fPt2[one ? 1 : 0] = pt2; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 105 | } |
| 106 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 107 | int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 108 | int index = insertSwap(one, two, pt); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 109 | if (index >= 0) { |
| 110 | setCoincident(index); |
| 111 | } |
| 112 | return index; |
| 113 | } |
| 114 | |
| 115 | void SkIntersections::setCoincident(int index) { |
| 116 | SkASSERT(index >= 0); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 117 | int bit = 1 << index; |
| 118 | fIsCoincident[0] |= bit; |
| 119 | fIsCoincident[1] |= bit; |
| 120 | } |
| 121 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 122 | void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b, |
| 123 | int bIndex) { |
| 124 | this->reset(); |
| 125 | fT[0][0] = a.fT[0][aIndex]; |
| 126 | fT[1][0] = b.fT[0][bIndex]; |
| 127 | fPt[0] = a.fPt[aIndex]; |
| 128 | fPt2[0] = b.fPt[bIndex]; |
| 129 | fUsed = 1; |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 130 | } |
| 131 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 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 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 147 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 148 | return result; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 149 | } |
| 150 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 151 | void SkIntersections::removeOne(int index) { |
| 152 | int remaining = --fUsed - index; |
| 153 | if (remaining <= 0) { |
| 154 | return; |
| 155 | } |
| 156 | memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); |
| 157 | memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); |
| 158 | memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 159 | // SkASSERT(fIsCoincident[0] == 0); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 160 | int coBit = fIsCoincident[0] & (1 << index); |
| 161 | fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; |
| 162 | SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); |
| 163 | fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 164 | } |