OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #ifndef SkPathOpsTypes_DEFINED | 7 #ifndef SkPathOpsTypes_DEFINED |
8 #define SkPathOpsTypes_DEFINED | 8 #define SkPathOpsTypes_DEFINED |
9 | 9 |
10 #include <float.h> // for FLT_EPSILON | 10 #include <float.h> // for FLT_EPSILON |
11 #include <math.h> // for fabs, sqrt | 11 #include <math.h> // for fabs, sqrt |
12 | 12 |
13 #include "SkFloatingPoint.h" | 13 #include "SkFloatingPoint.h" |
14 #include "SkPath.h" | 14 #include "SkPath.h" |
15 #include "SkPathOps.h" | 15 #include "SkPathOps.h" |
16 #include "SkPathOpsDebug.h" | 16 #include "SkPathOpsDebug.h" |
17 #include "SkScalar.h" | 17 #include "SkScalar.h" |
18 | 18 |
19 enum SkPathOpsMask { | 19 enum SkPathOpsMask { |
20 kWinding_PathOpsMask = -1, | 20 kWinding_PathOpsMask = -1, |
21 kNo_PathOpsMask = 0, | 21 kNo_PathOpsMask = 0, |
22 kEvenOdd_PathOpsMask = 1 | 22 kEvenOdd_PathOpsMask = 1 |
23 }; | 23 }; |
24 | 24 |
| 25 class SkChunkAlloc; |
25 class SkOpCoincidence; | 26 class SkOpCoincidence; |
26 class SkOpContour; | 27 class SkOpContour; |
27 class SkOpContourHead; | 28 class SkOpContourHead; |
28 class SkIntersections; | 29 class SkIntersections; |
29 class SkIntersectionHelper; | 30 class SkIntersectionHelper; |
30 | 31 |
31 class SkOpGlobalState { | 32 class SkOpGlobalState { |
32 public: | 33 public: |
33 SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* head | 34 SkOpGlobalState(SkOpContourHead* head, |
34 SkDEBUGPARAMS(bool debugSkipAssert) | 35 SkChunkAlloc* allocator SkDEBUGPARAMS(bool debugSkipAssert) |
35 SkDEBUGPARAMS(const char* testName)); | 36 SkDEBUGPARAMS(const char* testName)); |
36 | 37 |
37 enum Phase { | 38 enum Phase { |
38 kIntersecting, | 39 kIntersecting, |
39 kWalking, | 40 kWalking, |
40 kFixWinding, | 41 kFixWinding, |
41 }; | 42 }; |
42 | 43 |
43 enum { | 44 enum { |
44 kMaxWindingTries = 10 | 45 kMaxWindingTries = 10 |
45 }; | 46 }; |
46 | 47 |
| 48 SkChunkAlloc* allocator() { |
| 49 return fAllocator; |
| 50 } |
| 51 |
47 bool angleCoincidence() const { | 52 bool angleCoincidence() const { |
48 return fAngleCoincidence; | 53 return fAngleCoincidence; |
49 } | 54 } |
50 | 55 |
51 void bumpNested() { | 56 void bumpNested() { |
52 ++fNested; | 57 ++fNested; |
53 } | 58 } |
54 | 59 |
55 void clearNested() { | 60 void clearNested() { |
56 fNested = 0; | 61 fNested = 0; |
57 } | 62 } |
58 | 63 |
59 SkOpCoincidence* coincidence() { | 64 SkOpCoincidence* coincidence() { |
60 return fCoincidence; | 65 return fCoincidence; |
61 } | 66 } |
62 | 67 |
63 SkOpContourHead* contourHead() { | 68 SkOpContourHead* contourHead() { |
64 return fContourHead; | 69 return fContourHead; |
65 } | 70 } |
66 | 71 |
67 #ifdef SK_DEBUG | 72 #ifdef SK_DEBUG |
68 const struct SkOpAngle* debugAngle(int id) const; | 73 const class SkOpAngle* debugAngle(int id) const; |
| 74 const SkOpCoincidence* debugCoincidence() const; |
69 SkOpContour* debugContour(int id); | 75 SkOpContour* debugContour(int id); |
70 const class SkOpPtT* debugPtT(int id) const; | 76 const class SkOpPtT* debugPtT(int id) const; |
71 bool debugRunFail() const; | 77 bool debugRunFail() const; |
72 const class SkOpSegment* debugSegment(int id) const; | 78 const class SkOpSegment* debugSegment(int id) const; |
73 bool debugSkipAssert() const { return fDebugSkipAssert; } | 79 bool debugSkipAssert() const { return fDebugSkipAssert; } |
74 const class SkOpSpanBase* debugSpan(int id) const; | 80 const class SkOpSpanBase* debugSpan(int id) const; |
75 const char* debugTestName() const { return fDebugTestName; } | 81 const char* debugTestName() const { return fDebugTestName; } |
76 #endif | 82 #endif |
77 | 83 |
78 #if DEBUG_T_SECT_LOOP_COUNT | 84 #if DEBUG_T_SECT_LOOP_COUNT |
79 void debugAddLoopCount(SkIntersections* , const SkIntersectionHelper& , | 85 void debugAddLoopCount(SkIntersections* , const SkIntersectionHelper& , |
80 const SkIntersectionHelper& ); | 86 const SkIntersectionHelper& ); |
81 void debugDoYourWorst(SkOpGlobalState* ); | 87 void debugDoYourWorst(SkOpGlobalState* ); |
82 void debugLoopReport(); | 88 void debugLoopReport(); |
83 void debugResetLoopCounts(); | 89 void debugResetLoopCounts(); |
84 #endif | 90 #endif |
85 | 91 |
| 92 #if DEBUG_COINCIDENCE |
| 93 void debugSetCheckHealth(bool check) { fDebugCheckHealth = check; } |
| 94 bool debugCheckHealth() const { return fDebugCheckHealth; } |
| 95 #endif |
| 96 |
86 int nested() const { | 97 int nested() const { |
87 return fNested; | 98 return fNested; |
88 } | 99 } |
89 | 100 |
90 #ifdef SK_DEBUG | 101 #ifdef SK_DEBUG |
91 int nextAngleID() { | 102 int nextAngleID() { |
92 return ++fAngleID; | 103 return ++fAngleID; |
93 } | 104 } |
94 | 105 |
95 int nextCoinID() { | 106 int nextCoinID() { |
(...skipping 17 matching lines...) Expand all Loading... |
113 } | 124 } |
114 #endif | 125 #endif |
115 | 126 |
116 Phase phase() const { | 127 Phase phase() const { |
117 return fPhase; | 128 return fPhase; |
118 } | 129 } |
119 | 130 |
120 void setAngleCoincidence() { | 131 void setAngleCoincidence() { |
121 fAngleCoincidence = true; | 132 fAngleCoincidence = true; |
122 } | 133 } |
| 134 |
| 135 void setCoincidence(SkOpCoincidence* coincidence) { |
| 136 fCoincidence = coincidence; |
| 137 } |
123 | 138 |
124 void setContourHead(SkOpContourHead* contourHead) { | 139 void setContourHead(SkOpContourHead* contourHead) { |
125 fContourHead = contourHead; | 140 fContourHead = contourHead; |
126 } | 141 } |
127 | 142 |
128 void setPhase(Phase phase) { | 143 void setPhase(Phase phase) { |
129 SkASSERT(fPhase != phase); | 144 SkASSERT(fPhase != phase); |
130 fPhase = phase; | 145 fPhase = phase; |
131 } | 146 } |
132 | 147 |
133 // called in very rare cases where angles are sorted incorrectly -- signfies
op will fail | 148 // called in very rare cases where angles are sorted incorrectly -- signfies
op will fail |
134 void setWindingFailed() { | 149 void setWindingFailed() { |
135 fWindingFailed = true; | 150 fWindingFailed = true; |
136 } | 151 } |
137 | 152 |
138 bool windingFailed() const { | 153 bool windingFailed() const { |
139 return fWindingFailed; | 154 return fWindingFailed; |
140 } | 155 } |
141 | 156 |
142 private: | 157 private: |
| 158 SkChunkAlloc* fAllocator; |
143 SkOpCoincidence* fCoincidence; | 159 SkOpCoincidence* fCoincidence; |
144 SkOpContourHead* fContourHead; | 160 SkOpContourHead* fContourHead; |
145 int fNested; | 161 int fNested; |
146 bool fWindingFailed; | 162 bool fWindingFailed; |
147 bool fAngleCoincidence; | 163 bool fAngleCoincidence; |
148 Phase fPhase; | 164 Phase fPhase; |
149 #ifdef SK_DEBUG | 165 #ifdef SK_DEBUG |
150 const char* fDebugTestName; | 166 const char* fDebugTestName; |
151 int fAngleID; | 167 int fAngleID; |
152 int fCoinID; | 168 int fCoinID; |
153 int fContourID; | 169 int fContourID; |
154 int fPtTID; | 170 int fPtTID; |
155 int fSegmentID; | 171 int fSegmentID; |
156 int fSpanID; | 172 int fSpanID; |
157 bool fDebugSkipAssert; | 173 bool fDebugSkipAssert; |
158 #endif | 174 #endif |
159 #if DEBUG_T_SECT_LOOP_COUNT | 175 #if DEBUG_T_SECT_LOOP_COUNT |
160 int fDebugLoopCount[3]; | 176 int fDebugLoopCount[3]; |
161 SkPath::Verb fDebugWorstVerb[6]; | 177 SkPath::Verb fDebugWorstVerb[6]; |
162 SkPoint fDebugWorstPts[24]; | 178 SkPoint fDebugWorstPts[24]; |
163 float fDebugWorstWeight[6]; | 179 float fDebugWorstWeight[6]; |
164 #endif | 180 #endif |
| 181 #if DEBUG_COINCIDENCE |
| 182 bool fDebugCheckHealth; |
| 183 #endif |
165 }; | 184 }; |
166 | 185 |
167 // Use Almost Equal when comparing coordinates. Use epsilon to compare T values. | 186 // Use Almost Equal when comparing coordinates. Use epsilon to compare T values. |
168 bool AlmostEqualUlps(float a, float b); | 187 bool AlmostEqualUlps(float a, float b); |
169 inline bool AlmostEqualUlps(double a, double b) { | 188 inline bool AlmostEqualUlps(double a, double b) { |
170 return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); | 189 return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); |
171 } | 190 } |
172 | 191 |
| 192 bool AlmostEqualUlpsNoNormalCheck(float a, float b); |
| 193 inline bool AlmostEqualUlpsNoNormalCheck(double a, double b) { |
| 194 return AlmostEqualUlpsNoNormalCheck(SkDoubleToScalar(a), SkDoubleToScalar(b)
); |
| 195 } |
| 196 |
173 bool AlmostEqualUlps_Pin(float a, float b); | 197 bool AlmostEqualUlps_Pin(float a, float b); |
174 inline bool AlmostEqualUlps_Pin(double a, double b) { | 198 inline bool AlmostEqualUlps_Pin(double a, double b) { |
175 return AlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b)); | 199 return AlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b)); |
176 } | 200 } |
177 | 201 |
178 // Use Almost Dequal when comparing should not special case denormalized values. | 202 // Use Almost Dequal when comparing should not special case denormalized values. |
179 bool AlmostDequalUlps(float a, float b); | 203 bool AlmostDequalUlps(float a, float b); |
180 bool AlmostDequalUlps(double a, double b); | 204 bool AlmostDequalUlps(double a, double b); |
181 | 205 |
182 bool NotAlmostEqualUlps(float a, float b); | 206 bool NotAlmostEqualUlps(float a, float b); |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
239 const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; | 263 const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; |
240 const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); | 264 const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); |
241 const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; | 265 const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; |
242 const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few b
its of error | 266 const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few b
its of error |
243 const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; | 267 const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; |
244 const double ROUGH_EPSILON = FLT_EPSILON * 64; | 268 const double ROUGH_EPSILON = FLT_EPSILON * 64; |
245 const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; | 269 const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; |
246 const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048; | 270 const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048; |
247 const double BUMP_EPSILON = FLT_EPSILON * 4096; | 271 const double BUMP_EPSILON = FLT_EPSILON * 4096; |
248 | 272 |
| 273 const SkScalar INVERSE_NUMBER_RANGE = FLT_EPSILON_ORDERABLE_ERR; |
| 274 |
249 inline bool zero_or_one(double x) { | 275 inline bool zero_or_one(double x) { |
250 return x == 0 || x == 1; | 276 return x == 0 || x == 1; |
251 } | 277 } |
252 | 278 |
253 inline bool approximately_zero(double x) { | 279 inline bool approximately_zero(double x) { |
254 return fabs(x) < FLT_EPSILON; | 280 return fabs(x) < FLT_EPSILON; |
255 } | 281 } |
256 | 282 |
257 inline bool precisely_zero(double x) { | 283 inline bool precisely_zero(double x) { |
258 return fabs(x) < DBL_EPSILON_ERR; | 284 return fabs(x) < DBL_EPSILON_ERR; |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
291 } | 317 } |
292 | 318 |
293 inline bool roughly_zero(double x) { | 319 inline bool roughly_zero(double x) { |
294 return fabs(x) < ROUGH_EPSILON; | 320 return fabs(x) < ROUGH_EPSILON; |
295 } | 321 } |
296 | 322 |
297 inline bool approximately_zero_inverse(double x) { | 323 inline bool approximately_zero_inverse(double x) { |
298 return fabs(x) > FLT_EPSILON_INVERSE; | 324 return fabs(x) > FLT_EPSILON_INVERSE; |
299 } | 325 } |
300 | 326 |
301 // OPTIMIZATION: if called multiple times with the same denom, we want to pass 1
/y instead | |
302 inline bool approximately_zero_when_compared_to(double x, double y) { | 327 inline bool approximately_zero_when_compared_to(double x, double y) { |
303 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); | 328 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); |
304 } | 329 } |
305 | 330 |
306 inline bool precisely_zero_when_compared_to(double x, double y) { | 331 inline bool precisely_zero_when_compared_to(double x, double y) { |
307 return x == 0 || fabs(x) < fabs(y * DBL_EPSILON); | 332 return x == 0 || fabs(x) < fabs(y * DBL_EPSILON); |
308 } | 333 } |
309 | 334 |
| 335 inline bool roughly_zero_when_compared_to(double x, double y) { |
| 336 return x == 0 || fabs(x) < fabs(y * ROUGH_EPSILON); |
| 337 } |
| 338 |
310 // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger
and smaller) use | 339 // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger
and smaller) use |
311 // AlmostEqualUlps instead. | 340 // AlmostEqualUlps instead. |
312 inline bool approximately_equal(double x, double y) { | 341 inline bool approximately_equal(double x, double y) { |
313 return approximately_zero(x - y); | 342 return approximately_zero(x - y); |
314 } | 343 } |
315 | 344 |
316 inline bool precisely_equal(double x, double y) { | 345 inline bool precisely_equal(double x, double y) { |
317 return precisely_zero(x - y); | 346 return precisely_zero(x - y); |
318 } | 347 } |
319 | 348 |
(...skipping 219 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
539 */ | 568 */ |
540 inline int SkDSideBit(double x) { | 569 inline int SkDSideBit(double x) { |
541 return 1 << SKDSide(x); | 570 return 1 << SKDSide(x); |
542 } | 571 } |
543 | 572 |
544 inline double SkPinT(double t) { | 573 inline double SkPinT(double t) { |
545 return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 :
t; | 574 return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 :
t; |
546 } | 575 } |
547 | 576 |
548 #endif | 577 #endif |
OLD | NEW |