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