blob: 541cfb0ab6740ed7592267f0f5c764b517e32769 [file] [log] [blame]
caryclark@google.com07393ca2013-04-08 11:47:37 +00001/*
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
caryclark54359292015-03-26 07:52:43 -070010int 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.coma2bbc6e2013-11-01 17:36:03 +000024 }
caryclark54359292015-03-26 07:52:43 -070025 return closest;
caryclark@google.coma2bbc6e2013-11-01 17:36:03 +000026}
27
caryclark@google.com07393ca2013-04-08 11:47:37 +000028void SkIntersections::flip() {
29 for (int index = 0; index < fUsed; ++index) {
30 fT[1][index] = 1 - fT[1][index];
31 }
32}
33
caryclark@google.comfa2aeee2013-07-15 13:29:13 +000034int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
caryclark@google.comb3f09212013-04-17 15:49:16 +000035 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.com07393ca2013-04-08 11:47:37 +000039 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.comfa2aeee2013-07-15 13:29:13 +000044 if (one == oldOne && two == oldTwo) {
45 return -1;
46 }
47 if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
Cary Clark74b42902018-03-09 07:38:47 -050048 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 return -1;
caryclark@google.com07393ca2013-04-08 11:47:37 +000053 }
Cary Clark74b42902018-03-09 07:38:47 -050054 SkASSERT(one >= 0 && one <= 1);
55 SkASSERT(two >= 0 && two <= 1);
56 // remove this and reinsert below in case replacing would make list unsorted
57 int remaining = fUsed - index - 1;
58 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
59 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
60 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
61 int clearMask = ~((1 << index) - 1);
62 fIsCoincident[0] -= (fIsCoincident[0] >> 1) & clearMask;
63 fIsCoincident[1] -= (fIsCoincident[1] >> 1) & clearMask;
64 --fUsed;
65 break;
caryclark@google.com07393ca2013-04-08 11:47:37 +000066 }
67 #if ONE_OFF_DEBUG
68 if (pt.roughlyEqual(fPt[index])) {
69 SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
70 }
71 #endif
Cary Clark74b42902018-03-09 07:38:47 -050072 }
73 for (index = 0; index < fUsed; ++index) {
caryclark@google.com07393ca2013-04-08 11:47:37 +000074 if (fT[0][index] > one) {
75 break;
76 }
77 }
caryclark@google.com7eaa53d2013-10-02 14:49:34 +000078 if (fUsed >= fMax) {
caryclark595ac282016-10-24 08:41:45 -070079 SkOPASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must
caryclark@google.com7eaa53d2013-10-02 14:49:34 +000080 // be propagated all the way back down to the caller, and return failure.
81 fUsed = 0;
82 return 0;
83 }
caryclark@google.com07393ca2013-04-08 11:47:37 +000084 int remaining = fUsed - index;
85 if (remaining > 0) {
86 memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
87 memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
88 memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
caryclark@google.com570863f2013-09-16 15:55:01 +000089 int clearMask = ~((1 << index) - 1);
90 fIsCoincident[0] += fIsCoincident[0] & clearMask;
91 fIsCoincident[1] += fIsCoincident[1] & clearMask;
caryclark@google.com07393ca2013-04-08 11:47:37 +000092 }
caryclark@google.comfa2aeee2013-07-15 13:29:13 +000093 fPt[index] = pt;
Cary Clark8af026e2017-03-01 14:02:02 -050094 if (one < 0 || one > 1) {
95 return -1;
96 }
97 if (two < 0 || two > 1) {
98 return -1;
99 }
caryclark@google.com07393ca2013-04-08 11:47:37 +0000100 fT[0][index] = one;
101 fT[1][index] = two;
102 ++fUsed;
caryclark94c902e2015-08-18 07:12:43 -0700103 SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt));
caryclark@google.com07393ca2013-04-08 11:47:37 +0000104 return index;
105}
106
caryclarkdac1d172014-06-17 05:15:38 -0700107void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) {
108 SkASSERT(one == 0 || one == 1);
109 SkASSERT(two == 0 || two == 1);
110 SkASSERT(pt1 != pt2);
caryclark54359292015-03-26 07:52:43 -0700111 fNearlySame[one ? 1 : 0] = true;
caryclarkdac1d172014-06-17 05:15:38 -0700112 (void) insert(one, two, pt1);
caryclark54359292015-03-26 07:52:43 -0700113 fPt2[one ? 1 : 0] = pt2;
caryclarkdac1d172014-06-17 05:15:38 -0700114}
115
caryclark54359292015-03-26 07:52:43 -0700116int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
caryclark@google.com07393ca2013-04-08 11:47:37 +0000117 int index = insertSwap(one, two, pt);
caryclark54359292015-03-26 07:52:43 -0700118 if (index >= 0) {
119 setCoincident(index);
120 }
121 return index;
122}
123
124void SkIntersections::setCoincident(int index) {
125 SkASSERT(index >= 0);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000126 int bit = 1 << index;
127 fIsCoincident[0] |= bit;
128 fIsCoincident[1] |= bit;
129}
130
caryclark54359292015-03-26 07:52:43 -0700131void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b,
132 int bIndex) {
133 this->reset();
134 fT[0][0] = a.fT[0][aIndex];
135 fT[1][0] = b.fT[0][bIndex];
136 fPt[0] = a.fPt[aIndex];
137 fPt2[0] = b.fPt[bIndex];
138 fUsed = 1;
caryclark@google.coma2bbc6e2013-11-01 17:36:03 +0000139}
140
caryclark54359292015-03-26 07:52:43 -0700141int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const {
142 int result = -1;
143 for (int index = 0; index < fUsed; ++index) {
144 if (!between(rangeStart, fT[0][index], rangeEnd)) {
145 continue;
146 }
147 if (result < 0) {
148 result = index;
149 continue;
150 }
151 SkDVector best = fPt[result] - origin;
152 SkDVector test = fPt[index] - origin;
153 if (test.crossCheck(best) < 0) {
154 result = index;
155 }
caryclark@google.com07393ca2013-04-08 11:47:37 +0000156 }
caryclark54359292015-03-26 07:52:43 -0700157 return result;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000158}
159
caryclark@google.com07393ca2013-04-08 11:47:37 +0000160void SkIntersections::removeOne(int index) {
161 int remaining = --fUsed - index;
162 if (remaining <= 0) {
163 return;
164 }
165 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
166 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
167 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
caryclark65f55312014-11-13 06:58:52 -0800168// SkASSERT(fIsCoincident[0] == 0);
caryclark@google.com07393ca2013-04-08 11:47:37 +0000169 int coBit = fIsCoincident[0] & (1 << index);
170 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
171 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
172 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000173}