SkPathOpsWinding.cpp revision 2af4599b5c514933bf997d4837ddaaf24fc61cd7
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; 195624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 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); 246624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpContour* contour = contourHead; 247624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 248624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark contour->rayCheck(hitBase, dir, &hitHead, &allocator); 249624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while ((contour = contour->next())); 250624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // sort hits 251624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkSTArray<1, SkOpRayHit*> sorted; 252624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpRayHit* hit = hitHead; 253624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark while (hit) { 254624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark sorted.push_back(hit); 255624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit = hit->fNext; 256624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 257624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int count = sorted.count(); 258624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir) 259624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y 260624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark : less_than(dir) ? hit_compare_x : reverse_hit_compare_x); 261624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // verify windings 262624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#if DEBUG_WINDING 263624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, 264624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(), 265624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY); 266624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark for (int index = 0; index < count; ++index) { 267624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit = sorted[index]; 268624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = hit->fSpan; 26996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkOpSegment* hitSegment = span ? span->segment() : nullptr; 270624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool operand = span ? hitSegment->operand() : false; 271624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool ccw = ccw_dxdy(hit->fSlope, dir); 272624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index, 273624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit->fValid, operand, span ? span->debugID() : -1, ccw); 274624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span) { 275624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hitSegment->dumpPtsInner(); 276624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 277624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT, 278624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY); 279624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 280624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#endif 28196fcdcc219d2a0d3579719b84b28bede76efba64halcanary const SkPoint* last = nullptr; 282624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int wind = 0; 283624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oppWind = 0; 284624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark for (int index = 0; index < count; ++index) { 285624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark hit = sorted[index]; 286624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!hit->fValid) { 287624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 288624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 289624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool ccw = ccw_dxdy(hit->fSlope, dir); 290ed0935a28a29af7d3b16ac8d9365f291a335c6bdcaryclark// SkASSERT(!approximately_zero(hit->fT) || !hit->fValid); 291624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = hit->fSpan; 292624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (!span) { 293624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 294624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 2952af4599b5c514933bf997d4837ddaaf24fc61cd7lsalzman SkOpSegment* hitSegment = span->segment(); 296624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->windValue() == 0 && span->oppValue() == 0) { 297624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 298624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 299624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) { 300624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 301624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 302624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (index < count - 1) { 303624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark const SkPoint& next = sorted[index + 1]->fPt; 304624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) { 305624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return false; 306624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 307624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 308624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool operand = hitSegment->operand(); 309624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (operand) { 310624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkTSwap(wind, oppWind); 311624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 312624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int lastWind = wind; 313624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int lastOpp = oppWind; 314624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int windValue = ccw ? -span->windValue() : span->windValue(); 315624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oppValue = ccw ? -span->oppValue() : span->oppValue(); 316624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark wind += windValue; 317624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark oppWind += oppValue; 318624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark bool sumSet = false; 319624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int spanSum = span->windSum(); 320624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind; 321624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (spanSum == SK_MinS32) { 322624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark span->setWindSum(windSum); 323624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark sumSet = true; 324624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else { 325624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // the need for this condition suggests that UseInnerWinding is flawed 326624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark // happened when last = 1 wind = -1 327624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#if 0 328624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum) 329624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark || (abs(wind) == abs(lastWind) 330624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark && (windSum ^ wind ^ lastWind) == spanSum)); 331624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#endif 332624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 333624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oSpanSum = span->oppSum(); 334624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp; 335624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (oSpanSum == SK_MinS32) { 336624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark span->setOppSum(oppSum); 337624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else { 338624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#if 0 339624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum 340624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark || (abs(oppWind) == abs(lastOpp) 341624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark && (oppSum ^ oppWind ^ lastOpp) == oSpanSum)); 342624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark#endif 343624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 344624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (sumSet) { 3455b5ddd73b4baf22752924bf20d097e96236c36f8caryclark if (this->globalState()->phase() == SkOpGlobalState::kFixWinding) { 3465b5ddd73b4baf22752924bf20d097e96236c36f8caryclark hitSegment->contour()->setCcw(ccw); 3475b5ddd73b4baf22752924bf20d097e96236c36f8caryclark } else { 34896fcdcc219d2a0d3579719b84b28bede76efba64halcanary (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr); 34996fcdcc219d2a0d3579719b84b28bede76efba64halcanary (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr); 3505b5ddd73b4baf22752924bf20d097e96236c36f8caryclark } 351624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 352624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (operand) { 353624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkTSwap(wind, oppWind); 354624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 355624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark last = &hit->fPt; 3564e1a4c9399b8bb0897218f3ec10c254d3bb97463caryclark this->globalState()->bumpNested(); 357624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 358624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return true; 359624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 360624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 361624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkSkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) { 362624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* span = &fHead; 363624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpanBase* next; 364624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 365624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark next = span->next(); 366624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->done()) { 367624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 368624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 369624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->windSum() != SK_MinS32) { 370624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return span; 371624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 372624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (span->sortableTop(contourHead)) { 373624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return span; 374624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 375624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while (!next->final() && (span = next->upCast())); 37696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 377624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 378624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 379624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkSkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { 380624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSegment* testSegment = &fHead; 381624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 382624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (testSegment->done()) { 383624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 384624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 385624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* result = testSegment->findSortableTop(contourHead); 386624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (result) { 387624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return result; 388624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 389624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while ((testSegment = testSegment->next())); 39096fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 391624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 392624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 393624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkSkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { 394624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) { 395624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpContour* contour = contourHead; 396624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark do { 397624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (contour->done()) { 398624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark continue; 399624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 400624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkOpSpan* result = contour->findSortableTop(contourHead); 401624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (result) { 402624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return result; 403624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 404624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } while ((contour = contour->next())); 405624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 40696fcdcc219d2a0d3579719b84b28bede76efba64halcanary return nullptr; 407624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 408