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
closestTo(double rangeStart,double rangeEnd,const SkDPoint & testPt,double * closestDist) const10 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 }
24 }
25 return closest;
26 }
27
flip()28 void SkIntersections::flip() {
29 for (int index = 0; index < fUsed; ++index) {
30 fT[1][index] = 1 - fT[1][index];
31 }
32 }
33
insert(double one,double two,const SkDPoint & pt)34 int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
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 }
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];
44 if (one == oldOne && two == oldTwo) {
45 return -1;
46 }
47 if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
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))) {
52 SkASSERT(one >= 0 && one <= 1);
53 SkASSERT(two >= 0 && two <= 1);
54 fT[0][index] = one;
55 fT[1][index] = two;
56 fPt[index] = pt;
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 }
69 if (fUsed >= fMax) {
70 SkOPASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must
71 // be propagated all the way back down to the caller, and return failure.
72 fUsed = 0;
73 return 0;
74 }
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);
80 int clearMask = ~((1 << index) - 1);
81 fIsCoincident[0] += fIsCoincident[0] & clearMask;
82 fIsCoincident[1] += fIsCoincident[1] & clearMask;
83 }
84 fPt[index] = pt;
85 if (one < 0 || one > 1) {
86 return -1;
87 }
88 if (two < 0 || two > 1) {
89 return -1;
90 }
91 fT[0][index] = one;
92 fT[1][index] = two;
93 ++fUsed;
94 SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt));
95 return index;
96 }
97
insertNear(double one,double two,const SkDPoint & pt1,const SkDPoint & pt2)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);
102 fNearlySame[one ? 1 : 0] = true;
103 (void) insert(one, two, pt1);
104 fPt2[one ? 1 : 0] = pt2;
105 }
106
insertCoincident(double one,double two,const SkDPoint & pt)107 int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
108 int index = insertSwap(one, two, pt);
109 if (index >= 0) {
110 setCoincident(index);
111 }
112 return index;
113 }
114
setCoincident(int index)115 void SkIntersections::setCoincident(int index) {
116 SkASSERT(index >= 0);
117 int bit = 1 << index;
118 fIsCoincident[0] |= bit;
119 fIsCoincident[1] |= bit;
120 }
121
merge(const SkIntersections & a,int aIndex,const SkIntersections & b,int bIndex)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;
130 }
131
mostOutside(double rangeStart,double rangeEnd,const SkDPoint & origin) const132 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
removeOne(int index)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);
159 // SkASSERT(fIsCoincident[0] == 0);
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;
164 }
165