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

Side by Side Diff: src/pathops/SkPathOpsWinding.cpp

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 2015 Google Inc. 2 * Copyright 2015 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 7
8 // given a prospective edge, compute its initial winding by projecting a ray 8 // given a prospective edge, compute its initial winding by projecting a ray
9 // if the ray hits another edge 9 // if the ray hits another edge
10 // if the edge doesn't have a winding yet, hop up to that edge and start ove r 10 // if the edge doesn't have a winding yet, hop up to that edge and start ove r
(...skipping 174 matching lines...) Expand 10 before | Expand all | Expand 10 after
185 } 185 }
186 } 186 }
187 187
188 SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) { 188 SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) {
189 SkOpSpan* span = &fHead; 189 SkOpSpan* span = &fHead;
190 SkOpSpanBase* next; 190 SkOpSpanBase* next;
191 do { 191 do {
192 next = span->next(); 192 next = span->next();
193 if (approximately_equal(tHit, next->t())) { 193 if (approximately_equal(tHit, next->t())) {
194 return nullptr; 194 return nullptr;
195 } 195 }
196 if (tHit < next->t()) { 196 if (tHit < next->t()) {
197 return span; 197 return span;
198 } 198 }
199 } while (!next->final() && (span = next->upCast())); 199 } while (!next->final() && (span = next->upCast()));
200 return nullptr; 200 return nullptr;
201 } 201 }
202 202
203 static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { 203 static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
204 return a->fPt.fX < b->fPt.fX; 204 return a->fPt.fX < b->fPt.fX;
205 } 205 }
(...skipping 30 matching lines...) Expand all
236 SkChunkAlloc allocator(1024); 236 SkChunkAlloc allocator(1024);
237 int dirOffset; 237 int dirOffset;
238 double t = get_t_guess(fTopTTry++, &dirOffset); 238 double t = get_t_guess(fTopTTry++, &dirOffset);
239 SkOpRayHit hitBase; 239 SkOpRayHit hitBase;
240 SkOpRayDir dir = hitBase.makeTestBase(this, t); 240 SkOpRayDir dir = hitBase.makeTestBase(this, t);
241 if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) { 241 if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) {
242 return false; 242 return false;
243 } 243 }
244 SkOpRayHit* hitHead = &hitBase; 244 SkOpRayHit* hitHead = &hitBase;
245 dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset); 245 dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset);
246 if (hitBase.fSpan && hitBase.fSpan->segment()->verb() > SkPath::kLine_Verb
247 && !pt_yx(hitBase.fSlope.asSkVector(), dir)) {
248 return false;
249 }
246 SkOpContour* contour = contourHead; 250 SkOpContour* contour = contourHead;
247 do { 251 do {
248 contour->rayCheck(hitBase, dir, &hitHead, &allocator); 252 contour->rayCheck(hitBase, dir, &hitHead, &allocator);
249 } while ((contour = contour->next())); 253 } while ((contour = contour->next()));
250 // sort hits 254 // sort hits
251 SkSTArray<1, SkOpRayHit*> sorted; 255 SkSTArray<1, SkOpRayHit*> sorted;
252 SkOpRayHit* hit = hitHead; 256 SkOpRayHit* hit = hitHead;
253 while (hit) { 257 while (hit) {
254 sorted.push_back(hit); 258 sorted.push_back(hit);
255 hit = hit->fNext; 259 hit = hit->fNext;
256 } 260 }
257 int count = sorted.count(); 261 int count = sorted.count();
258 SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir) 262 SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir)
259 ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y 263 ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y
260 : less_than(dir) ? hit_compare_x : reverse_hit_compare_x); 264 : less_than(dir) ? hit_compare_x : reverse_hit_compare_x);
261 // verify windings 265 // verify windings
262 #if DEBUG_WINDING 266 #if DEBUG_WINDING
263 SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, 267 SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__,
264 gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->d ebugID(), 268 gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->d ebugID(),
265 hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY); 269 hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY);
266 for (int index = 0; index < count; ++index) { 270 for (int index = 0; index < count; ++index) {
267 hit = sorted[index]; 271 hit = sorted[index];
268 SkOpSpan* span = hit->fSpan; 272 SkOpSpan* span = hit->fSpan;
269 SkOpSegment* hitSegment = span ? span->segment() : nullptr; 273 SkOpSegment* hitSegment = span ? span->segment() : nullptr;
270 bool operand = span ? hitSegment->operand() : false; 274 bool operand = span ? hitSegment->operand() : false;
271 bool ccw = ccw_dxdy(hit->fSlope, dir); 275 bool ccw = ccw_dxdy(hit->fSlope, dir);
272 SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, in dex, 276 SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, in dex,
273 hit->fValid, operand, span ? span->debugID() : -1, ccw); 277 hit->fValid, operand, span ? span->debugID() : -1, ccw);
(...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after
371 } 375 }
372 if (span->sortableTop(contourHead)) { 376 if (span->sortableTop(contourHead)) {
373 return span; 377 return span;
374 } 378 }
375 } while (!next->final() && (span = next->upCast())); 379 } while (!next->final() && (span = next->upCast()));
376 return nullptr; 380 return nullptr;
377 } 381 }
378 382
379 SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { 383 SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) {
380 SkOpSegment* testSegment = &fHead; 384 SkOpSegment* testSegment = &fHead;
385 bool allDone = true;
381 do { 386 do {
382 if (testSegment->done()) { 387 if (testSegment->done()) {
383 continue; 388 continue;
384 } 389 }
390 allDone = false;
385 SkOpSpan* result = testSegment->findSortableTop(contourHead); 391 SkOpSpan* result = testSegment->findSortableTop(contourHead);
386 if (result) { 392 if (result) {
387 return result; 393 return result;
388 } 394 }
389 } while ((testSegment = testSegment->next())); 395 } while ((testSegment = testSegment->next()));
396 if (allDone) {
397 fDone = true;
398 }
390 return nullptr; 399 return nullptr;
391 } 400 }
392 401
393 SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { 402 SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) {
394 for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) { 403 for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) {
395 SkOpContour* contour = contourHead; 404 SkOpContour* contour = contourHead;
396 do { 405 do {
397 if (contour->done()) { 406 if (contour->done()) {
398 continue; 407 continue;
399 } 408 }
400 SkOpSpan* result = contour->findSortableTop(contourHead); 409 SkOpSpan* result = contour->findSortableTop(contourHead);
401 if (result) { 410 if (result) {
402 return result; 411 return result;
403 } 412 }
404 } while ((contour = contour->next())); 413 } while ((contour = contour->next()));
405 } 414 }
406 return nullptr; 415 return nullptr;
407 } 416 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698