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 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 
28 void SkIntersections::flip() {
29     for (int index = 0; index < fUsed; ++index) {
30         fT[1][index] = 1 - fT[1][index];
31     }
32 }
33 
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 
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 
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 
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 
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 
132 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 
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