Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(393)

Side by Side Diff: src/pathops/SkPathOpsTypes.h

Issue 2128633003: pathops coincidence and security rewrite (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: require resulting t to be between 0 and 1 Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698