• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
append(const SkIntersections & i)10 void SkIntersections::append(const SkIntersections& i) {
11     for (int index = 0; index < i.fUsed; ++index) {
12         insert(i[0][index], i[1][index], i.pt(index));
13     }
14 }
15 
16 int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
17     NULL,
18     &SkIntersections::verticalLine,
19     &SkIntersections::verticalQuad,
20     &SkIntersections::verticalCubic
21 };
22 
23 int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = {
24     NULL,
25     &SkIntersections::lineRay,
26     &SkIntersections::quadRay,
27     &SkIntersections::cubicRay
28 };
29 
coincidentUsed() const30 int SkIntersections::coincidentUsed() const {
31     if (!fIsCoincident[0]) {
32         SkASSERT(!fIsCoincident[1]);
33         return 0;
34     }
35     int count = 0;
36     SkDEBUGCODE(int count2 = 0;)
37     for (int index = 0; index < fUsed; ++index) {
38         if (fIsCoincident[0] & (1 << index)) {
39             ++count;
40         }
41 #ifdef SK_DEBUG
42         if (fIsCoincident[1] & (1 << index)) {
43             ++count2;
44         }
45 #endif
46     }
47     SkASSERT(count == count2);
48     return count;
49 }
50 
cubicRay(const SkPoint pts[4],const SkDLine & line)51 int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) {
52     SkDCubic cubic;
53     cubic.set(pts);
54     fMax = 3;
55     return intersectRay(cubic, line);
56 }
57 
flip()58 void SkIntersections::flip() {
59     for (int index = 0; index < fUsed; ++index) {
60         fT[1][index] = 1 - fT[1][index];
61     }
62 }
63 
insert(double one,double two,const SkDPoint & pt)64 int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
65     if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
66         // For now, don't allow a mix of coincident and non-coincident intersections
67         return -1;
68     }
69     SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
70     int index;
71     for (index = 0; index < fUsed; ++index) {
72         double oldOne = fT[0][index];
73         double oldTwo = fT[1][index];
74         if (one == oldOne && two == oldTwo) {
75             return -1;
76         }
77         if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
78             if ((precisely_zero(one) && !precisely_zero(oldOne))
79                     || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
80                     || (precisely_zero(two) && !precisely_zero(oldTwo))
81                     || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
82                 fT[0][index] = one;
83                 fT[1][index] = two;
84                 fPt[index] = pt;
85             }
86             return -1;
87         }
88     #if ONE_OFF_DEBUG
89         if (pt.roughlyEqual(fPt[index])) {
90             SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
91         }
92     #endif
93         if (fT[0][index] > one) {
94             break;
95         }
96     }
97     if (fUsed >= fMax) {
98         SkASSERT(0);  // FIXME : this error, if it is to be handled at runtime in release, must
99                       // be propagated all the way back down to the caller, and return failure.
100         fUsed = 0;
101         return 0;
102     }
103     int remaining = fUsed - index;
104     if (remaining > 0) {
105         memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
106         memmove(&fPt2[index + 1], &fPt2[index], sizeof(fPt2[0]) * remaining);
107         memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
108         memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
109         int clearMask = ~((1 << index) - 1);
110         fIsCoincident[0] += fIsCoincident[0] & clearMask;
111         fIsCoincident[1] += fIsCoincident[1] & clearMask;
112     }
113     fPt[index] = pt;
114     fT[0][index] = one;
115     fT[1][index] = two;
116     ++fUsed;
117     return index;
118 }
119 
insertNear(double one,double two,const SkDPoint & pt1,const SkDPoint & pt2)120 void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) {
121     SkASSERT(one == 0 || one == 1);
122     SkASSERT(two == 0 || two == 1);
123     SkASSERT(pt1 != pt2);
124     SkASSERT(fNearlySame[(int) one]);
125     (void) insert(one, two, pt1);
126     fPt2[one ? fUsed - 1 : 0] = pt2;
127 }
128 
insertCoincident(double one,double two,const SkDPoint & pt)129 void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
130     int index = insertSwap(one, two, pt);
131     int bit = 1 << index;
132     fIsCoincident[0] |= bit;
133     fIsCoincident[1] |= bit;
134 }
135 
lineRay(const SkPoint pts[2],const SkDLine & line)136 int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) {
137     SkDLine l;
138     l.set(pts);
139     fMax = 2;
140     return intersectRay(l, line);
141 }
142 
offset(int base,double start,double end)143 void SkIntersections::offset(int base, double start, double end) {
144     for (int index = base; index < fUsed; ++index) {
145         double val = fT[fSwap][index];
146         val *= end - start;
147         val += start;
148         fT[fSwap][index] = val;
149     }
150 }
151 
quadRay(const SkPoint pts[3],const SkDLine & line)152 int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) {
153     SkDQuad quad;
154     quad.set(pts);
155     fMax = 2;
156     return intersectRay(quad, line);
157 }
158 
quickRemoveOne(int index,int replace)159 void SkIntersections::quickRemoveOne(int index, int replace) {
160     if (index < replace) {
161         fT[0][index] = fT[0][replace];
162     }
163 }
164 
removeOne(int index)165 void SkIntersections::removeOne(int index) {
166     int remaining = --fUsed - index;
167     if (remaining <= 0) {
168         return;
169     }
170     memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
171     memmove(&fPt2[index], &fPt2[index + 1], sizeof(fPt2[0]) * remaining);
172     memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
173     memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
174     SkASSERT(fIsCoincident[0] == 0);
175     int coBit = fIsCoincident[0] & (1 << index);
176     fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
177     SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
178     fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
179 }
180 
swapPts()181 void SkIntersections::swapPts() {
182     int index;
183     for (index = 0; index < fUsed; ++index) {
184         SkTSwap(fT[0][index], fT[1][index]);
185     }
186 }
187 
verticalLine(const SkPoint a[2],SkScalar top,SkScalar bottom,SkScalar x,bool flipped)188 int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom,
189         SkScalar x, bool flipped) {
190     SkDLine line;
191     line.set(a);
192     return vertical(line, top, bottom, x, flipped);
193 }
194 
verticalQuad(const SkPoint a[3],SkScalar top,SkScalar bottom,SkScalar x,bool flipped)195 int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom,
196         SkScalar x, bool flipped) {
197     SkDQuad quad;
198     quad.set(a);
199     return vertical(quad, top, bottom, x, flipped);
200 }
201 
verticalCubic(const SkPoint a[4],SkScalar top,SkScalar bottom,SkScalar x,bool flipped)202 int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom,
203         SkScalar x, bool flipped) {
204     SkDCubic cubic;
205     cubic.set(a);
206     return vertical(cubic, top, bottom, x, flipped);
207 }
208