SkPathOpsWinding.cpp revision 0eb6ed421ccd4f8a84ef5e5a11df73a00d210aec
1624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark/* 2624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark * Copyright 2015 Google Inc. 3624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark * 4624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark * Use of this source code is governed by a BSD-style license that can be 5624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark * found in the LICENSE file. 6624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark */ 7624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 8624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark// given a prospective edge, compute its initial winding by projecting a ray 9624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark// if the ray hits another edge 10624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // if the edge doesn't have a winding yet, hop up to that edge and start over 11624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // concern : check for hops forming a loop 12624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // if the edge is unsortable, or 13624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // the intersection is nearly at the ends, or 14624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // the tangent at the intersection is nearly coincident to the ray, 15624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // choose a different ray and try again 16624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // concern : if it is unable to succeed after N tries, try another edge? direction? 17624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark// if no edge is hit, compute the winding directly 18624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 19624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark// given the top span, project the most perpendicular ray and look for intersections 20624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // let's try up and then down. What the hey 21624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 22624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark// bestXY is initialized by caller with basePt 23624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 24624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#include "SkOpContour.h" 25624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#include "SkOpSegment.h" 26624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#include "SkPathOpsCurve.h" 27624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 28624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkenum class SkOpRayDir { 29624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark kLeft, 30624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark kTop, 31624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark kRight, 32624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark kBottom, 33624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark}; 34624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 35624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#if DEBUG_WINDING 36624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkconst char* gDebugRayDirName[] = { 37624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark "kLeft", 38624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark "kTop", 39624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark "kRight", 40624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark "kBottom" 41624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark}; 42624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#endif 43624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 44624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic int xy_index(SkOpRayDir dir) { 45624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return static_cast<int>(dir) & 1; 46624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 47624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 48624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) { 49624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return (&pt.fX)[xy_index(dir)]; 50624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 51624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 52624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) { 53624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return (&pt.fX)[!xy_index(dir)]; 54624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 55624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 56624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic double pt_dxdy(const SkDVector& v, SkOpRayDir dir) { 57624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return (&v.fX)[xy_index(dir)]; 58624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 59624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 60624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic double pt_dydx(const SkDVector& v, SkOpRayDir dir) { 61624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return (&v.fX)[!xy_index(dir)]; 62624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 63624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 64624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic SkScalar rect_side(const SkRect& r, SkOpRayDir dir) { 65624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return (&r.fLeft)[static_cast<int>(dir)]; 66624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 67624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 68624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) { 69624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int i = !xy_index(dir); 70624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]); 71624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 72624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 73624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic bool less_than(SkOpRayDir dir) { 74624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return static_cast<bool>((static_cast<int>(dir) & 2) == 0); 75624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 76624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 77624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) { 78624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool vPartPos = pt_dydx(v, dir) > 0; 79624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0; 80624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return vPartPos == leftBottom; 81624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 82624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 83624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstruct SkOpRayHit { 84624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayDir makeTestBase(SkOpSpan* span, double t) { 8596fcdcc219d2a0d3579719b84b28bede76efba64halcanary fNext = nullptr; 86624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fSpan = span; 87624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fT = span->t() * (1 - t) + span->next()->t() * t; 88624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* segment = span->segment(); 89624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fSlope = segment->dSlopeAtT(fT); 90624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fPt = segment->ptAtT(fT); 91624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark fValid = true; 92624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop; 93624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 94624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 95624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayHit* fNext; 96624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* fSpan; 97624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkPoint fPt; 98624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double fT; 99624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDVector fSlope; 100624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool fValid; 101624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark}; 102624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 103624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, 104624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkChunkAlloc* allocator) { 105624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // if the bounds extreme is outside the best, we're done 106624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkScalar baseXY = pt_xy(base.fPt, dir); 107624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkScalar boundsXY = rect_side(fBounds, dir); 108624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool checkLessThan = less_than(dir); 109624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { 110624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return; 111624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 112624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* testSegment = &fHead; 113624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 114624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark testSegment->rayCheck(base, dir, hits, allocator); 115624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while ((testSegment = testSegment->next())); 116624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 117624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 118624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkvoid SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, 119624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkChunkAlloc* allocator) { 120624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!sideways_overlap(fBounds, base.fPt, dir)) { 121624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return; 122624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 123624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkScalar baseXY = pt_xy(base.fPt, dir); 124624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkScalar boundsXY = rect_side(fBounds, dir); 125624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool checkLessThan = less_than(dir); 126624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { 127624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return; 128624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 129624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double tVals[3]; 130624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkScalar baseYX = pt_yx(base.fPt, dir); 131624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals); 132624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark for (int index = 0; index < roots; ++index) { 133624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double t = tVals[index]; 134624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) { 135624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 136624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 137624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDVector slope; 138624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkPoint pt; 139624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDEBUGCODE(sk_bzero(&slope, sizeof(slope))); 140624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool valid = false; 141624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (approximately_zero(t)) { 142624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark pt = fPts[0]; 143624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else if (approximately_equal(t, 1)) { 144624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark pt = fPts[SkPathOpsVerbToPoints(fVerb)]; 145624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else { 146624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkASSERT(between(0, t, 1)); 147624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark pt = this->ptAtT(t); 148624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) { 149624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (base.fSpan->segment() == this) { 150624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 151624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 152624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else { 153624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkScalar ptXY = pt_xy(pt, dir); 154624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) { 155624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 156624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 157624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark slope = this->dSlopeAtT(t); 158624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this 159624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark && roughly_equal(base.fT, t) 160624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark && SkDPoint::RoughlyEqual(pt, base.fPt)) { 161624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark #if DEBUG_WINDING 162624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDebugf("%s (rarely expect this)\n", __FUNCTION__); 163624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark #endif 164624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 165624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 166624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) { 167624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark valid = true; 168624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 169624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 170624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 171624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = this->windingSpanAtT(t); 172624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!span) { 173624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark valid = false; 174624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else if (!span->windValue() && !span->oppValue()) { 175624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 176624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 177624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayHit* newHit = SkOpTAllocator<SkOpRayHit>::Allocate(allocator); 178624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark newHit->fNext = *hits; 179624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark newHit->fPt = pt; 180624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark newHit->fSlope = slope; 181624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark newHit->fSpan = span; 182624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark newHit->fT = t; 183624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark newHit->fValid = valid; 184624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark *hits = newHit; 185624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 186624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 187624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 188624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkSkOpSpan* SkOpSegment::windingSpanAtT(double tHit) { 189624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = &fHead; 190624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* next; 191624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 192624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark next = span->next(); 193624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (approximately_equal(tHit, next->t())) { 19496fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 19555888e44171ffd48b591d19256884a969fe4da17caryclark } 196624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (tHit < next->t()) { 197624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return span; 198624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 199624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while (!next->final() && (span = next->upCast())); 20096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 201624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 202624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 203624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { 204624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return a->fPt.fX < b->fPt.fX; 205624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 206624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 207624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { 208624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return b->fPt.fX < a->fPt.fX; 209624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 210624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 211624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { 212624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return a->fPt.fY < b->fPt.fY; 213624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 214624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 215624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { 216624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return b->fPt.fY < a->fPt.fY; 217624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 218624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 219624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkstatic double get_t_guess(int tTry, int* dirOffset) { 220624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double t = 0.5; 221624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark *dirOffset = tTry & 1; 222624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int tBase = tTry >> 1; 223624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int tBits = 0; 224624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark while (tTry >>= 1) { 225624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark t /= 2; 226624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark ++tBits; 227624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 228624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (tBits) { 229624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int tIndex = (tBase - 1) & ((1 << tBits) - 1); 230624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark t += t * 2 * tIndex; 231624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 232624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return t; 233624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 234624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 235624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkbool SkOpSpan::sortableTop(SkOpContour* contourHead) { 236624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkChunkAlloc allocator(1024); 237624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int dirOffset; 238624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double t = get_t_guess(fTopTTry++, &dirOffset); 239624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayHit hitBase; 240624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayDir dir = hitBase.makeTestBase(this, t); 241624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) { 242624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 243624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 244624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayHit* hitHead = &hitBase; 245624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset); 24655888e44171ffd48b591d19256884a969fe4da17caryclark if (hitBase.fSpan && hitBase.fSpan->segment()->verb() > SkPath::kLine_Verb 24755888e44171ffd48b591d19256884a969fe4da17caryclark && !pt_yx(hitBase.fSlope.asSkVector(), dir)) { 24855888e44171ffd48b591d19256884a969fe4da17caryclark return false; 24955888e44171ffd48b591d19256884a969fe4da17caryclark } 250624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpContour* contour = contourHead; 251624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 252624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark contour->rayCheck(hitBase, dir, &hitHead, &allocator); 253624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while ((contour = contour->next())); 254624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // sort hits 255624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkSTArray<1, SkOpRayHit*> sorted; 256624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayHit* hit = hitHead; 257624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark while (hit) { 258624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark sorted.push_back(hit); 259624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit = hit->fNext; 260624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 261624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int count = sorted.count(); 262624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir) 26355888e44171ffd48b591d19256884a969fe4da17caryclark ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y 264624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark : less_than(dir) ? hit_compare_x : reverse_hit_compare_x); 265624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // verify windings 266624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#if DEBUG_WINDING 26755888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, 268624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(), 269624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY); 270624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark for (int index = 0; index < count; ++index) { 271624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit = sorted[index]; 272624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = hit->fSpan; 27396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSegment* hitSegment = span ? span->segment() : nullptr; 274624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool operand = span ? hitSegment->operand() : false; 275624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool ccw = ccw_dxdy(hit->fSlope, dir); 276624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index, 277624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit->fValid, operand, span ? span->debugID() : -1, ccw); 278624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span) { 279624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hitSegment->dumpPtsInner(); 280624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 281624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT, 282624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY); 283624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 284624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#endif 28596fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkPoint* last = nullptr; 286624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int wind = 0; 287624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oppWind = 0; 288624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark for (int index = 0; index < count; ++index) { 289624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit = sorted[index]; 290624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!hit->fValid) { 291624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 292624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 293624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool ccw = ccw_dxdy(hit->fSlope, dir); 294ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark// SkASSERT(!approximately_zero(hit->fT) || !hit->fValid); 295624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = hit->fSpan; 296624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!span) { 297624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 298624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 2992af4599b5c514933bf997d4837ddaaf24fc61cd7lsalzman SkOpSegment* hitSegment = span->segment(); 300624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->windValue() == 0 && span->oppValue() == 0) { 301624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 302624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 303624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) { 304624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 305624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 306624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (index < count - 1) { 307624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark const SkPoint& next = sorted[index + 1]->fPt; 308624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) { 309624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 310624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 311624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 312624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool operand = hitSegment->operand(); 313624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (operand) { 314624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkTSwap(wind, oppWind); 315624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 316624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int lastWind = wind; 317624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int lastOpp = oppWind; 318624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int windValue = ccw ? -span->windValue() : span->windValue(); 319624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oppValue = ccw ? -span->oppValue() : span->oppValue(); 320624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark wind += windValue; 321624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark oppWind += oppValue; 322624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool sumSet = false; 323624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int spanSum = span->windSum(); 324624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind; 325624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (spanSum == SK_MinS32) { 326624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark span->setWindSum(windSum); 327624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark sumSet = true; 328624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else { 329624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // the need for this condition suggests that UseInnerWinding is flawed 330624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // happened when last = 1 wind = -1 331624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#if 0 332624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum) 333624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark || (abs(wind) == abs(lastWind) 334624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark && (windSum ^ wind ^ lastWind) == spanSum)); 335624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#endif 336624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 337624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oSpanSum = span->oppSum(); 338624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp; 339624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (oSpanSum == SK_MinS32) { 340624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark span->setOppSum(oppSum); 341624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else { 342624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#if 0 343624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum 344624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark || (abs(oppWind) == abs(lastOpp) 345624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark && (oppSum ^ oppWind ^ lastOpp) == oSpanSum)); 346624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#endif 347624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 348624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (sumSet) { 349ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark if (this->globalState()->phase() == SkOpPhase::kFixWinding) { 3505b5ddd73b4baf22752924bf20d097e96236c36f8caryclark hitSegment->contour()->setCcw(ccw); 3515b5ddd73b4baf22752924bf20d097e96236c36f8caryclark } else { 35296fcdcc219d2a0d3579719b84b28bede76efba64halcanary (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr); 35396fcdcc219d2a0d3579719b84b28bede76efba64halcanary (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr); 3545b5ddd73b4baf22752924bf20d097e96236c36f8caryclark } 355624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 356624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (operand) { 357624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkTSwap(wind, oppWind); 358624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 359624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark last = &hit->fPt; 3604e1a4c9399b8bb0897218f3ec10c254d3bb97463caryclark this->globalState()->bumpNested(); 361624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 362624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return true; 363624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 364624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 365624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkSkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) { 366624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = &fHead; 367624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* next; 368624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 369624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark next = span->next(); 370624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->done()) { 371624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 372624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 373624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->windSum() != SK_MinS32) { 374624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return span; 375624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 376624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->sortableTop(contourHead)) { 377624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return span; 378624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 379624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while (!next->final() && (span = next->upCast())); 38096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 381624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 382624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 383624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkSkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { 38455888e44171ffd48b591d19256884a969fe4da17caryclark bool allDone = true; 3850eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark if (fCount) { 3860eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark SkOpSegment* testSegment = &fHead; 3870eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark do { 3880eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark if (testSegment->done()) { 3890eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark continue; 3900eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark } 3910eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark allDone = false; 3920eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark SkOpSpan* result = testSegment->findSortableTop(contourHead); 3930eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark if (result) { 3940eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark return result; 3950eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark } 3960eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark } while ((testSegment = testSegment->next())); 3970eb6ed421ccd4f8a84ef5e5a11df73a00d210aecCary Clark } 39855888e44171ffd48b591d19256884a969fe4da17caryclark if (allDone) { 39955888e44171ffd48b591d19256884a969fe4da17caryclark fDone = true; 40055888e44171ffd48b591d19256884a969fe4da17caryclark } 40196fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 402624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 403624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 404624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkSkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { 405624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) { 406624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpContour* contour = contourHead; 407624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 408624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (contour->done()) { 409624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 410624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 411624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* result = contour->findSortableTop(contourHead); 412624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (result) { 413624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return result; 414624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 415624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while ((contour = contour->next())); 416624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 41796fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 418624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 419