caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +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 | */ |
skia.committer@gmail.com | 055c7c2 | 2012-09-15 02:01:41 +0000 | [diff] [blame] | 7 | |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 8 | #include "DataTypes.h" |
| 9 | #include "Intersections.h" |
| 10 | |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 11 | void Intersections::insertCoincidentPair(double s1, double e1, double s2, double e2, |
| 12 | const _Point& startPt, const _Point& endPt) { |
| 13 | if (fSwap) { |
| 14 | remove(s2, e2, startPt, endPt); |
| 15 | } else { |
| 16 | remove(s1, e1, startPt, endPt); |
| 17 | } |
| 18 | SkASSERT(coincidentUsed() == fUsed); |
| 19 | SkASSERT((coincidentUsed() & 1) != 1); |
| 20 | int i1 = 0; |
| 21 | int i2 = 0; |
| 22 | do { |
| 23 | while (i1 < fUsed && !(fIsCoincident[fSwap] & (1 << i1))) { |
| 24 | ++i1; |
| 25 | } |
| 26 | if (i1 == fUsed) { |
| 27 | break; |
| 28 | } |
| 29 | SkASSERT(i1 < fUsed); |
| 30 | int iEnd1 = i1 + 1; |
| 31 | while (!(fIsCoincident[fSwap] & (1 << iEnd1))) { |
| 32 | ++iEnd1; |
| 33 | } |
| 34 | SkASSERT(iEnd1 < fUsed); |
| 35 | double cs1 = fT[fSwap][i1]; |
| 36 | double ce1 = fT[fSwap][iEnd1]; |
| 37 | bool s1in = between(cs1, s1, ce1) || startPt.approximatelyEqual(fPt[i1]) |
| 38 | || startPt.approximatelyEqual(fPt[iEnd1]); |
| 39 | bool e1in = between(cs1, e1, ce1) || endPt.approximatelyEqual(fPt[i1]) |
| 40 | || endPt.approximatelyEqual(fPt[iEnd1]); |
| 41 | while (i2 < fUsed && !(fIsCoincident[fSwap ^ 1] & (1 << i2))) { |
| 42 | ++i2; |
| 43 | } |
| 44 | int iEnd2 = i2 + 1; |
| 45 | while (!(fIsCoincident[fSwap ^ 1] & (1 << iEnd2))) { |
| 46 | ++iEnd2; |
| 47 | } |
| 48 | SkASSERT(iEnd2 < fUsed); |
| 49 | double cs2 = fT[fSwap ^ 1][i2]; |
| 50 | double ce2 = fT[fSwap ^ 1][iEnd2]; |
skia.committer@gmail.com | 044679e | 2013-02-15 07:16:57 +0000 | [diff] [blame] | 51 | bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2]) |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 52 | || startPt.approximatelyEqual(fPt[iEnd2]); |
| 53 | bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2]) |
| 54 | || endPt.approximatelyEqual(fPt[iEnd2]); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 55 | if ((s1in | e1in) & (s2in | e2in)) { |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 56 | if (s1 < cs1) { |
| 57 | fT[fSwap][i1] = s1; |
| 58 | fPt[i1] = startPt; |
| 59 | } else if (e1 < cs1) { |
| 60 | fT[fSwap][i1] = e1; |
| 61 | fPt[i1] = endPt; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 62 | } |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 63 | if (s1 > ce1) { |
| 64 | fT[fSwap][iEnd1] = s1; |
| 65 | fPt[iEnd1] = startPt; |
| 66 | } else if (e1 > ce1) { |
| 67 | fT[fSwap][iEnd1] = e1; |
| 68 | fPt[iEnd1] = endPt; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 69 | } |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 70 | if (s2 > e2) { |
| 71 | SkTSwap(cs2, ce2); |
| 72 | SkTSwap(i2, iEnd2); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 73 | } |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 74 | if (s2 < cs2) { |
| 75 | fT[fSwap ^ 1][i2] = s2; |
| 76 | } else if (e2 < cs2) { |
| 77 | fT[fSwap ^ 1][i2] = e2; |
| 78 | } |
| 79 | if (s2 > ce2) { |
| 80 | fT[fSwap ^ 1][iEnd2] = s2; |
| 81 | } else if (e2 > ce2) { |
| 82 | fT[fSwap ^ 1][iEnd2] = e2; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 83 | } |
| 84 | return; |
| 85 | } |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 86 | } while (true); |
| 87 | SkASSERT(fUsed < 9); |
| 88 | insertCoincident(s1, s2, startPt); |
| 89 | insertCoincident(e1, e2, endPt); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 90 | } |
| 91 | |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 92 | int Intersections::insert(double one, double two, const _Point& pt) { |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 93 | SkASSERT(fUsed <= 1 || fT[0][0] < fT[0][1]); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 94 | int index; |
| 95 | for (index = 0; index < fUsed; ++index) { |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 96 | if (approximately_equal(fT[0][index], one) || pt.approximatelyEqual(fPt[index])) { |
| 97 | return -1; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 98 | } |
| 99 | if (fT[0][index] > one) { |
| 100 | break; |
| 101 | } |
| 102 | } |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 103 | SkASSERT(fUsed < 9); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 104 | int remaining = fUsed - index; |
| 105 | if (remaining > 0) { |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 106 | memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 107 | memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); |
| 108 | memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 109 | fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1); |
| 110 | fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 111 | } |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 112 | fPt[index] = pt; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 113 | fT[0][index] = one; |
| 114 | fT[1][index] = two; |
| 115 | ++fUsed; |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 116 | return index; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 117 | } |
| 118 | |
caryclark@google.com | 45a8fc6 | 2013-02-14 15:29:11 +0000 | [diff] [blame] | 119 | void Intersections::remove(double one, double two, const _Point& startPt, const _Point& endPt) { |
| 120 | for (int index = fUsed - 1; index >= 0; --index) { |
| 121 | if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two) |
| 122 | || startPt.approximatelyEqual(fPt[index]) |
| 123 | || endPt.approximatelyEqual(fPt[index]))) { |
| 124 | SkASSERT(fUsed > 0); |
caryclark@google.com | 47d73da | 2013-02-17 01:41:25 +0000 | [diff] [blame] | 125 | removeOne(index); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 126 | } |
| 127 | } |
caryclark@google.com | beda389 | 2013-02-07 13:13:41 +0000 | [diff] [blame] | 128 | } |
caryclark@google.com | 47d73da | 2013-02-17 01:41:25 +0000 | [diff] [blame] | 129 | |
| 130 | void Intersections::removeOne(int index) { |
| 131 | int remaining = --fUsed - index; |
| 132 | if (remaining <= 0) { |
| 133 | return; |
| 134 | } |
| 135 | memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); |
| 136 | memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); |
| 137 | memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); |
| 138 | SkASSERT(fIsCoincident[0] == 0); |
| 139 | int coBit = fIsCoincident[0] & (1 << index); |
| 140 | fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; |
| 141 | SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); |
| 142 | fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; |
| 143 | } |