Line data Source code
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 :
10 0 : int SkIntersections::closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt,
11 : double* closestDist) const {
12 0 : int closest = -1;
13 0 : *closestDist = SK_ScalarMax;
14 0 : for (int index = 0; index < fUsed; ++index) {
15 0 : if (!between(rangeStart, fT[0][index], rangeEnd)) {
16 0 : continue;
17 : }
18 0 : const SkDPoint& iPt = fPt[index];
19 0 : double dist = testPt.distanceSquared(iPt);
20 0 : if (*closestDist > dist) {
21 0 : *closestDist = dist;
22 0 : closest = index;
23 : }
24 : }
25 0 : return closest;
26 : }
27 :
28 0 : void SkIntersections::flip() {
29 0 : for (int index = 0; index < fUsed; ++index) {
30 0 : fT[1][index] = 1 - fT[1][index];
31 : }
32 0 : }
33 :
34 0 : int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
35 0 : 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 0 : return -1;
38 : }
39 0 : SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
40 : int index;
41 0 : for (index = 0; index < fUsed; ++index) {
42 0 : double oldOne = fT[0][index];
43 0 : double oldTwo = fT[1][index];
44 0 : if (one == oldOne && two == oldTwo) {
45 0 : return -1;
46 : }
47 0 : if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
48 0 : if ((precisely_zero(one) && !precisely_zero(oldOne))
49 0 : || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
50 0 : || (precisely_zero(two) && !precisely_zero(oldTwo))
51 0 : || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
52 0 : SkASSERT(one >= 0 && one <= 1);
53 0 : SkASSERT(two >= 0 && two <= 1);
54 0 : fT[0][index] = one;
55 0 : fT[1][index] = two;
56 0 : fPt[index] = pt;
57 : }
58 0 : 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 0 : if (fT[0][index] > one) {
66 0 : break;
67 : }
68 : }
69 0 : if (fUsed >= fMax) {
70 0 : 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 0 : fUsed = 0;
73 0 : return 0;
74 : }
75 0 : int remaining = fUsed - index;
76 0 : if (remaining > 0) {
77 0 : memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
78 0 : memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
79 0 : memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
80 0 : int clearMask = ~((1 << index) - 1);
81 0 : fIsCoincident[0] += fIsCoincident[0] & clearMask;
82 0 : fIsCoincident[1] += fIsCoincident[1] & clearMask;
83 : }
84 0 : fPt[index] = pt;
85 0 : if (one < 0 || one > 1) {
86 0 : return -1;
87 : }
88 0 : if (two < 0 || two > 1) {
89 0 : return -1;
90 : }
91 0 : fT[0][index] = one;
92 0 : fT[1][index] = two;
93 0 : ++fUsed;
94 0 : SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt));
95 0 : return index;
96 : }
97 :
98 0 : void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) {
99 0 : SkASSERT(one == 0 || one == 1);
100 0 : SkASSERT(two == 0 || two == 1);
101 0 : SkASSERT(pt1 != pt2);
102 0 : fNearlySame[one ? 1 : 0] = true;
103 0 : (void) insert(one, two, pt1);
104 0 : fPt2[one ? 1 : 0] = pt2;
105 0 : }
106 :
107 0 : int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
108 0 : int index = insertSwap(one, two, pt);
109 0 : if (index >= 0) {
110 0 : setCoincident(index);
111 : }
112 0 : return index;
113 : }
114 :
115 0 : void SkIntersections::setCoincident(int index) {
116 0 : SkASSERT(index >= 0);
117 0 : int bit = 1 << index;
118 0 : fIsCoincident[0] |= bit;
119 0 : fIsCoincident[1] |= bit;
120 0 : }
121 :
122 0 : void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b,
123 : int bIndex) {
124 0 : this->reset();
125 0 : fT[0][0] = a.fT[0][aIndex];
126 0 : fT[1][0] = b.fT[0][bIndex];
127 0 : fPt[0] = a.fPt[aIndex];
128 0 : fPt2[0] = b.fPt[bIndex];
129 0 : fUsed = 1;
130 0 : }
131 :
132 0 : int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const {
133 0 : int result = -1;
134 0 : for (int index = 0; index < fUsed; ++index) {
135 0 : if (!between(rangeStart, fT[0][index], rangeEnd)) {
136 0 : continue;
137 : }
138 0 : if (result < 0) {
139 0 : result = index;
140 0 : continue;
141 : }
142 0 : SkDVector best = fPt[result] - origin;
143 0 : SkDVector test = fPt[index] - origin;
144 0 : if (test.crossCheck(best) < 0) {
145 0 : result = index;
146 : }
147 : }
148 0 : return result;
149 : }
150 :
151 0 : void SkIntersections::removeOne(int index) {
152 0 : int remaining = --fUsed - index;
153 0 : if (remaining <= 0) {
154 0 : return;
155 : }
156 0 : memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
157 0 : memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
158 0 : memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
159 : // SkASSERT(fIsCoincident[0] == 0);
160 0 : int coBit = fIsCoincident[0] & (1 << index);
161 0 : fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
162 0 : SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
163 0 : fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
164 : }
|
