19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 7198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comadd unit test for quadratic horizontal intersection 8198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comadd unit test for cubic horizontal intersection with left/right 9198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comadd unit test for ActiveEdge::calcLeft (can currently loop forever) 10198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comdoes ActiveEdge::isCoincidentWith need to support quad, cubic? 11198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comfigure out why variation in ActiveEdge::tooCloseToCall isn't better 12198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comwhy does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22? 13198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comadd code to promote quad to cubic, or add quad/cubic intersection 14198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comfigure out why testSimplifySkinnyTriangle13 fails 15198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com 16198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comfor quadratics and cubics, once various T values are added, see if consecutive 17198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comTs have ys that go up instead of down. If so, the edge needs to be broken. 18198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com 19198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comwhen splitting curves at inflection pts, should I retain the original curve 20198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comdata and note that the first/last T are no longer 0/1 ? 21198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comI need to figure this out before I can proceed 22198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com 23198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comwould it make sense to leave the InEdge alone, and add multiple copies of 24198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comActiveEdge, pointing to the same InEdge, where the copy has only the subset 25198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comof Ts that need to be walked in reverse order? 26198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com 2715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 2815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com-- A Digression Which Shows Why Resolving Coincidence Does Not Make Sense -- 2915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 3015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comConsider the following fine ASCII art: 3115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 3215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com +------>-------+ +------>-------+ 3315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | | | 3415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com ^ V ^ V 3515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | | | 3615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com +------<-------+ +------<-------+ 3715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com +------>-------+ +------<-------+ 3815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | | | 3915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com ^ V V ^ 4015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | | | 4115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com +------<-------+ +------>-------+ 4215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 4315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com(assume the bottom and top of the stacked rectangles are coincident) 4415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 4515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comSimplifying said rectangles, regardless of rectangle direction, and regardless 4615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comof winding or even/odd, eliminates the coincident edge, i.e., the result is 4715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comalways: 4815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 4915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com +------>-------+ 5015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | 5115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | 5215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | 5315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com ^ V 5415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | 5515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | 5615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com | | 5715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com +------<-------+ 5815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 5915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comBut when the rectangles are enclosed in a larger rectangle: 6015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 6115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com+-------->---------+ +-------->---------+ 6215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| +------>-------+ | | +------>-------+ | 6315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 6415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| ^ V | | ^ V | 6515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 6615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| +------<-------+ | | +------<-------+ | 6715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| +------>-------+ | | +------<-------+ | 6815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 6915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| ^ V | | V ^ | 7015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 7115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| +------<-------+ | | +------>-------+ | 7215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com+--------<---------+ +--------<---------+ 7315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 7415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comSimplifying them gives different results depending on the winding setting: 7515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 7615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comwinding: 7715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com+-------->---------+ +-------->---------+ 7815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | 7915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | 8015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | 8115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | 8215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | +------<-------+ | 8315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | 8415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | V ^ | 8515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | 8615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | +------>-------+ | 8715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com+--------<---------+ +--------<---------+ 8815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 8915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comeven odd: 9015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com+-------->---------+ +-------->---------+ 9115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| +------<-------+ | | +------<-------+ | 9215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 9315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 9415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 9515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 9615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| V ^ | | V ^ | 9715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 9815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 9915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| | | | | | | | 10015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com| +------>-------+ | | +------>-------+ | 10115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com+--------<---------+ +--------<---------+ 10215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 10315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comSo, given the inner rectangles alone (e.g., given coincident pairs in some local 10415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comcontext), we can't know whether to keep the coincident edges or not. 10515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 10615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 10715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com-- Thoughts About Sortless Ops -- 10815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 10915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comI can't come up with anything truly sortless. It seems that the crossings need 11015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comto be sorted to know which segment is next on the outside, although sometimes 11115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comwe can use that it is not coincident just to follow the direction. 11215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 11315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comIf it is coincident or if there's more than two crossing segments, sorting 11415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comseems inevitable. 11515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 11615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comLikewise, to resolve whether one contour is inside another, it seems that 11715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comsorting is required. Given a pair of segments on different contours, to know 11815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comif one is inside of the other, I need to know for each which side of the edge 11915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comis the inside/filled side. When the outer contour is walked, it seems like I 12015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comcould record the inside info. I guess when the inner contour is found, its 12115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.cominside sense is reversed (inside is above the top). But how do I know if the 12215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comnext contour is inside another? Maybe shoot out a line and brute-force 12315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comintersect it with all the segments in all the other contours? If every contour 12415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comhas an extra segment when the intersections are computed, this may not be as 12515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comcrazy as it seems. 12615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 12715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comSuppose each contour has one extra segment shooting straight up from the top 12815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com(or straight up from any point on the segment). This ray is not intersected 12915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comwith the home contour, but is intersected with all other contours as part of 13015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comthe normal intersection engine. If it is possible to get from the T values to 13115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comthe other segments to the other contours, it would be straightforward to 13215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comcount the contour crossings and determine if the home contour is in another 13315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comcontour or not (if the count is even, not, if odd, is inside). By itself that 13415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comdoesn't tell us about winding, but it's a start. 13515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 13615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 13715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comSince intersecting these rays is unrelated to computing other intersections, 13815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comit can be lazily done once the contour is found. 13915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.com 14015fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comSo 14115fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comrepeat the following 14215fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comfind the top segment of all contours 14315fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comtrace the outside, marking touching first and last segments as inside 14415fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comcontinue tracing the touched segments with reversed outside/inside sense 14515fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comonce the edges are exhausted, remaining must be disjoint contours 14615fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comsend a ray from a disjoint point through all other contours 14715fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.comcount the crossings, determine if disjoint is inside or outside, then continue 148b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com 149b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com=== 150b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com 151b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comOn Quadratic (and Cubic) Intersections 152b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com 153b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comCurrently, if only the end points touch, QuadracticIntersections does a lot of 154b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comwork to figure that out. Can I test for that up front, then short circuit the 155b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comrecursive search for the end points? 156b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com 157b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comOr, is there something defective in the current approach that makes the end 158b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.compoint recursion go so deep? I'm seeing 56 stack frames (about 28 divides, but 159b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comthankfully, no splits) to find one matching endpoint. 160b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com 161b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com 162b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comBezier curve focus may allow more quickly determining that end points with 163b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comidentical tangents are practically coicident for some range of T, but I don't 164b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comunderstand the math yet to know. 165b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com 166b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comAnother approach is to determine how flat the curve is to make good guesses 167b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comabout how far to move away in T before doing the intersection for the remainder 168b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comand/or to determine whether one curve is to the inside or outside of another. 169b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comAccording to Mike/Rob, the flatness for quadratics increases by 4 for each 170b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.comsubdivision, and a crude guess of the curvature can be had by comparing P1 to 171b45a1b46ee25e9b19800b028bb1ca925212ac7b4caryclark@google.com(P0+P2)/2. By looking at the ULPS of the numbers, I can guess what value of 172a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.comT may be far enough that the curves diverge but don't cross. 1738dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1748dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com==== 1758dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1768dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.comCode I May Not Need Any More 1778dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1788dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com static bool CoincidentCandidate(const Angle* current) { 1798dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Segment* segment = current->segment(); 1808dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int min = SkMin32(current->start(), current->end()); 1818dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com do { 1828dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& span = segment->fTs[min]; 1838dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (span.fCoincident == Span::kStart_Coincidence) { 1848dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return true; 1858dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 1868dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } while (--min >= 0); 1878dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return false; 1888dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 1898dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1908dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com static bool CoincidentHalf(const Angle* current, const Angle* next) { 1918dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Segment* other = next->segment(); 1928dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Segment* segment = current->segment(); 1938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int min = SkMin32(current->start(), current->end()); 1948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& minSpan = segment->fTs[min]; 1958dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (minSpan.fOther == other) { 1968dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return minSpan.fCoincident == Span::kStart_Coincidence; 1978dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 1988dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int index = min; 1998dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int spanCount = segment->fTs.count(); 2008dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com while (++index < spanCount) { 2018dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& span = segment->fTs[index]; 2028dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (minSpan.fT != span.fT) { 2038dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com break; 2048dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2058dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (span.fOther != other) { 2068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 2078dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return span.fCoincident == Span::kStart_Coincidence; 2098dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com index = min; 2118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com while (--index >= 0) { 2128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& span = segment->fTs[index]; 2138dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (span.fOther != other) { 2148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 2158dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2168dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return span.fCoincident == Span::kStart_Coincidence; 2178dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2188dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return false; 2198dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2208dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 2218dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com static bool Coincident(const Angle* current, const Angle* next) { 2228dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return CoincidentHalf(current, next) && 2238dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com CoincidentHalf(next, current); 2248dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2258dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 2268dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // If three lines cancel in a - b - c order, a - b may or may not 2278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // eliminate the edge that describes the b - c cancellation. Check done to 2288dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // determine this. 2298dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com static bool CoincidentCancels(const Angle* current, const Angle* next) { 2308dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int curMin = SkMin32(current->start(), current->end()); 2318dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (current->segment()->fTs[curMin].fDone) { 2328dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return false; 2338dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2348dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int nextMin = SkMin32(next->start(), next->end()); 2358dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (next->segment()->fTs[nextMin].fDone) { 2368dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return false; 2378dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2388dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return SkSign32(current->start() - current->end()) 2398dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com != SkSign32(next->start() - next->end()); 2408dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2418dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 2428dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // FIXME: at this point, just have two functions for the different steps 2438dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int coincidentEnd(int from, int step) const { 2448dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double fromT = fTs[from].fT; 2458dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int count = fTs.count(); 2468dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int to = from; 2478dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com while (step > 0 ? ++to < count : --to >= 0) { 2488dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& span = fTs[to]; 2498dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if ((step > 0 ? span.fT - fromT : fromT - span.fT) >= FLT_EPSILON ) { 2508dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // FIXME: we assume that if the T changes, we don't care about 2518dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // coincident -- but in nextSpan, we require that both the T 2528dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // and actual loc change to represent a span. This asymettry may 2538dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // be OK or may be trouble -- if trouble, probably will need to 2548dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // detect coincidence earlier or sort differently 2558dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com break; 2568dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2578dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#if 01 2588dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (span.fCoincident == (step < 0 ? Span::kStart_Coincidence : 2598dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Span::kEnd_Coincidence)) { 2608dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com from = to; 2618dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2628dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#else 2638dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com from = to; 2648dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com#endif 2658dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2668dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return from; 2678dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2688dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 2698dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // once past current span, if step>0, look for coicident==1 2708dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // if step<0, look for coincident==-1 2718dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int nextSpanEnd(int from, int step) const { 2728dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int result = nextSpan(from, step); 2738dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (result < 0) { 2748dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return result; 2758dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2768dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return coincidentEnd(result, step); 2778dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2788dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 2798dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 2808dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com void adjustFirst(const SkTDArray<Angle*>& sorted, int& first, int& winding, 2818dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool outside) { 2828dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int firstIndex = first; 2838dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int angleCount = sorted.count(); 2848dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (true || outside) { 2858dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Angle* angle = sorted[firstIndex]; 2868dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int prior = firstIndex; 2878dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com do { 2888dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (--prior < 0) { 2898dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com prior = angleCount - 1; 2908dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2918dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (prior == firstIndex) { // all are coincident with each other 2928dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 2938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (!Coincident(sorted[prior], sorted[first])) { 2958dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 2968dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 2978dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com winding += angle->sign(); 2988dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com first = prior; 2998dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com angle = sorted[prior]; 3008dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com winding -= angle->sign(); 3018dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } while (true); 3028dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3038dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com do { 3048dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int next = first + 1; 3058dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (next == angleCount) { 3068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com next = 0; 3078dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (next == firstIndex) { // all are coincident with each other 3098dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 3108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (!Coincident(sorted[first], sorted[next])) { 3128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 3138dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com first = next; 3158dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } while (true); 3168dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3178dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 3188dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool nextIsCoincident = CoincidentCandidate(nextAngle); 3198dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool finalOrNoCoincident = true; 3208dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool pairCoincides = false; 3218dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool pairCancels = false; 3228dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (nextIsCoincident) { 3238dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int followIndex = nextIndex + 1; 3248dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (followIndex == angleCount) { 3258dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com followIndex = 0; 3268dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Angle* followAngle = sorted[followIndex]; 3288dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com finalOrNoCoincident = !Coincident(nextAngle, followAngle); 3298dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if ((pairCoincides = Coincident(angle, nextAngle))) { 3308dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com pairCancels = CoincidentCancels(angle, nextAngle); 3318dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3328dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3338dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (pairCancels && !foundAngle && !nextSegment->done()) { 3348dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Segment* aSeg = angle->segment(); 3358dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // alreadyMarked |= aSeg == sorted[firstIndex]->segment(); 3368dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com aSeg->markAndChaseCoincident(angle->start(), angle->end(), 3378dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com nextSegment); 3388dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (firstEdge) { 3398dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return NULL; 3408dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3418dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3428dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (pairCoincides) { 3438dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (pairCancels) { 3448dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com goto doNext; 3458dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3468dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int minT = SkMin32(nextAngle->start(), nextAngle->end()); 3478dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool markNext = abs(maxWinding) < abs(winding); 3488dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (markNext) { 3498dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com nextSegment->markDone(minT, winding); 3508dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3518dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int oldMinT = SkMin32(angle->start(), angle->end()); 3528dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (true || !foundAngle) { 3538dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // SkASSERT(0); // do we ever get here? 3548dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Segment* aSeg = angle->segment(); 3558dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // alreadyMarked |= aSeg == sorted[firstIndex]->segment(); 3568dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com aSeg->markDone(oldMinT, maxWinding); 3578dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3588dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3598dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 3608dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // OPTIMIZATION: uses tail recursion. Unwise? 3618dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com void innerCoincidentChase(int step, Segment* other) { 3628dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // find other at index 3638dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // SkASSERT(!done()); 3648dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span* start = NULL; 3658dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span* end = NULL; 3668dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int index, startIndex, endIndex; 3678dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int count = fTs.count(); 3688dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com for (index = 0; index < count; ++index) { 3698dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& span = fTs[index]; 3708dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (!span.fCoincident || span.fOther != other) { 3718dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 3728dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3738dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (!start) { 3748dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com startIndex = index; 3758dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com start = &span; 3768dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } else { 3778dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com SkASSERT(!end); 3788dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com endIndex = index; 3798dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com end = &span; 3808dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3818dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3828dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (!end) { 3838dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 3848dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3858dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool thisDone = fTs[SkMin32(startIndex, endIndex)].fDone; 3868dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool otherDone = other->fTs[SkMin32(start->fOtherIndex, 3878dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com end->fOtherIndex)].fDone; 3888dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (thisDone && otherDone) { 3898dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 3908dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 3918dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Segment* next; 3928dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Segment* nextOther; 3938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (step < 0) { 3948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com next = start->fT == 0 ? NULL : this; 3958dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com nextOther = other->fTs[start->fOtherIndex].fT > 1 - FLT_EPSILON ? NULL : other; 3968dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } else { 3978dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com next = end->fT == 1 ? NULL : this; 3988dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com nextOther = other->fTs[end->fOtherIndex].fT < FLT_EPSILON ? NULL : other; 3998dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4008dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com SkASSERT(!next || !nextOther); 4018dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com for (index = 0; index < count; ++index) { 4028dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& span = fTs[index]; 4038dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (span.fCoincident || span.fOther == other) { 4048dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 4058dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool checkNext = !next && (step < 0 ? span.fT < FLT_EPSILON 4078dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com && span.fOtherT > 1 - FLT_EPSILON : span.fT > 1 - FLT_EPSILON 4088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com && span.fOtherT < FLT_EPSILON); 4098dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool checkOther = !nextOther && (step < 0 ? fabs(span.fT - start->fT) < FLT_EPSILON 4108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com && span.fOtherT < FLT_EPSILON : fabs(span.fT - end->fT) < FLT_EPSILON 4118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com && span.fOtherT > 1 - FLT_EPSILON); 4128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (!checkNext && !checkOther) { 4138dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 4148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4158dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Segment* oSegment = span.fOther; 4168dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (oSegment->done()) { 4178dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 4188dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4198dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int oCount = oSegment->fTs.count(); 4208dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com for (int oIndex = 0; oIndex < oCount; ++oIndex) { 4218dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const Span& oSpan = oSegment->fTs[oIndex]; 4228dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (oSpan.fT >= FLT_EPSILON && oSpan.fT <= 1 - FLT_EPSILON) { 4238dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 4248dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4258dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (!oSpan.fCoincident) { 4268dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com continue; 4278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4288dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (checkNext && (oSpan.fT < FLT_EPSILON ^ step < 0)) { 4298dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com next = oSegment; 4308dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com checkNext = false; 4318dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4328dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (checkOther && (oSpan.fT > 1 - FLT_EPSILON ^ step < 0)) { 4338dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com nextOther = oSegment; 4348dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com checkOther = false; 4358dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4368dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4378dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4388dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // this needs to walk both spans in lock step, skipping edges that 4398dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // are already marked done on one or the other 4408dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com markCanceled(startIndex, endIndex); 4418dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (next && nextOther) { 4428dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com next->innerCoincidentChase(step, nextOther); 4438dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4448dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4458dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 4468dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // cancel coincident edges in lock step 4478dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com void markCanceled(int start, int end) { 4488dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (done()) { 4498dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 4508dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4518dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Segment* other = fTs[start].fOther; 4528dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (other->done()) { 4538dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return; 4548dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4558dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (start > end) { 4568dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com SkTSwap<int>(start, end); 4578dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4588dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double maxT = fTs[end].fT - FLT_EPSILON; 4598dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int spanCount = fTs.count(); 4608dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // since these cancel, this walks up and other walks down 4618dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int oStart = fTs[start].fOtherIndex; 4628dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double oStartT = other->fTs[oStart].fT; 4638dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com while (oStartT - other->fTs[--oStart].fT < FLT_EPSILON) 4648dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com ; 4658dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double startT = fTs[start].fT; 4668dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com while (start > 0 && startT - fTs[start - 1].fT < FLT_EPSILON) { 4678dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com --start; 4688dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4698dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com do { 4708dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Span* span = &fTs[start]; 4718dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com Span* oSpan = &other->fTs[oStart]; 4728dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // find start of each, and see if both are not done 4738dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool markDone = !span->fDone && !oSpan->fDone; 4748dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double spanT = span->fT; 4758dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com do { 4768dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (markDone) { 4778dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com span->fCanceled = true; 4788dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #if DEBUG_MARK_DONE 4798dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const SkPoint& pt = xyAtT(span); 4808dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", 4818dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com __FUNCTION__, fID, start, span->fT, pt.fX, pt.fY); 4828dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #endif 4838dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com SkASSERT(!span->fDone); 4848dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com span->fDone = true; 4858dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com span->fWinding = 0; 4868dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com fDoneSpans++; 4878dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4888dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (++start == spanCount) { 4898dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com break; 4908dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 4918dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com span = &fTs[start]; 4928dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } while (span->fT - spanT < FLT_EPSILON); 4938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double oSpanT = oSpan->fT; 4948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com do { 4958dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (markDone) { 4968dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com oSpan->fCanceled = true; 4978dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #if DEBUG_MARK_DONE 4988dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com const SkPoint& oPt = xyAtT(oSpan); 4998dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", 5008dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com __FUNCTION__, other->fID, oStart, oSpan->fT, 5018dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com oPt.fX, oPt.fY); 5028dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #endif 5038dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com SkASSERT(!oSpan->fDone); 5048dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com oSpan->fDone = true; 5058dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com oSpan->fWinding = 0; 5068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com other->fDoneSpans++; 5078dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 5088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if (--oStart < 0) { 5098dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com break; 5108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 5118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com oSpan = &other->fTs[oStart]; 5128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } while (oSpanT - oSpan->fT < FLT_EPSILON); 5138dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } while (fTs[start].fT <= maxT); 5148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 5158dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 5168dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool canceled(int start, int end) const { 5178dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int min = SkMin32(start, end); 5188dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return fTs[min].fCanceled; 5198dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 5208dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 5218dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com void markAndChaseCoincident(int index, int endIndex, Segment* other) { 5228dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int step = SkSign32(endIndex - index); 5238dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com innerCoincidentChase(step, other); 5248dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 5258dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 526