1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkOpSegment.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,450 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#ifndef SkOpSegment_DEFINE
1.11 +#define SkOpSegment_DEFINE
1.12 +
1.13 +#include "SkOpAngle.h"
1.14 +#include "SkOpSpan.h"
1.15 +#include "SkPathOpsBounds.h"
1.16 +#include "SkPathOpsCurve.h"
1.17 +#include "SkTArray.h"
1.18 +#include "SkTDArray.h"
1.19 +
1.20 +class SkPathWriter;
1.21 +
1.22 +class SkOpSegment {
1.23 +public:
1.24 + SkOpSegment() {
1.25 +#ifdef SK_DEBUG
1.26 + fID = ++SkPathOpsDebug::gSegmentID;
1.27 +#endif
1.28 + }
1.29 +
1.30 + bool operator<(const SkOpSegment& rh) const {
1.31 + return fBounds.fTop < rh.fBounds.fTop;
1.32 + }
1.33 +
1.34 + const SkPathOpsBounds& bounds() const {
1.35 + return fBounds;
1.36 + }
1.37 +
1.38 + // OPTIMIZE
1.39 + // when the edges are initially walked, they don't automatically get the prior and next
1.40 + // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
1.41 + // and would additionally remove the need for similar checks in condition edges. It would
1.42 + // also allow intersection code to assume end of segment intersections (maybe?)
1.43 + bool complete() const {
1.44 + int count = fTs.count();
1.45 + return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
1.46 + }
1.47 +
1.48 + int count() const {
1.49 + return fTs.count();
1.50 + }
1.51 +
1.52 + bool done() const {
1.53 + SkASSERT(fDoneSpans <= fTs.count());
1.54 + return fDoneSpans == fTs.count();
1.55 + }
1.56 +
1.57 + bool done(int min) const {
1.58 + return fTs[min].fDone;
1.59 + }
1.60 +
1.61 + bool done(const SkOpAngle* angle) const {
1.62 + return done(SkMin32(angle->start(), angle->end()));
1.63 + }
1.64 +
1.65 + // used only by partial coincidence detection
1.66 + SkDPoint dPtAtT(double mid) const {
1.67 + return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
1.68 + }
1.69 +
1.70 + SkVector dxdy(int index) const {
1.71 + return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT);
1.72 + }
1.73 +
1.74 + SkScalar dy(int index) const {
1.75 + return dxdy(index).fY;
1.76 + }
1.77 +
1.78 + bool intersected() const {
1.79 + return fTs.count() > 0;
1.80 + }
1.81 +
1.82 + bool isCanceled(int tIndex) const {
1.83 + return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
1.84 + }
1.85 +
1.86 + bool isConnected(int startIndex, int endIndex) const {
1.87 + return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32;
1.88 + }
1.89 +
1.90 + bool isHorizontal() const {
1.91 + return fBounds.fTop == fBounds.fBottom;
1.92 + }
1.93 +
1.94 + bool isVertical() const {
1.95 + return fBounds.fLeft == fBounds.fRight;
1.96 + }
1.97 +
1.98 + bool isVertical(int start, int end) const {
1.99 + return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end);
1.100 + }
1.101 +
1.102 + bool operand() const {
1.103 + return fOperand;
1.104 + }
1.105 +
1.106 + int oppSign(const SkOpAngle* angle) const {
1.107 + SkASSERT(angle->segment() == this);
1.108 + return oppSign(angle->start(), angle->end());
1.109 + }
1.110 +
1.111 + int oppSign(int startIndex, int endIndex) const {
1.112 + int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue;
1.113 +#if DEBUG_WIND_BUMP
1.114 + SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
1.115 +#endif
1.116 + return result;
1.117 + }
1.118 +
1.119 + int oppSum(int tIndex) const {
1.120 + return fTs[tIndex].fOppSum;
1.121 + }
1.122 +
1.123 + int oppSum(const SkOpAngle* angle) const {
1.124 + int lesser = SkMin32(angle->start(), angle->end());
1.125 + return fTs[lesser].fOppSum;
1.126 + }
1.127 +
1.128 + int oppValue(int tIndex) const {
1.129 + return fTs[tIndex].fOppValue;
1.130 + }
1.131 +
1.132 + int oppValue(const SkOpAngle* angle) const {
1.133 + int lesser = SkMin32(angle->start(), angle->end());
1.134 + return fTs[lesser].fOppValue;
1.135 + }
1.136 +
1.137 + const SkOpSegment* other(int index) const {
1.138 + return fTs[index].fOther;
1.139 + }
1.140 +
1.141 + // was used only by right angle winding finding
1.142 + SkPoint ptAtT(double mid) const {
1.143 + return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
1.144 + }
1.145 +
1.146 + const SkPoint* pts() const {
1.147 + return fPts;
1.148 + }
1.149 +
1.150 + void reset() {
1.151 + init(NULL, (SkPath::Verb) -1, false, false);
1.152 + fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1.153 + fTs.reset();
1.154 + }
1.155 +
1.156 + void setOppXor(bool isOppXor) {
1.157 + fOppXor = isOppXor;
1.158 + }
1.159 +
1.160 + void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
1.161 + int deltaSum = spanSign(index, endIndex);
1.162 + *maxWinding = *sumWinding;
1.163 + *sumWinding -= deltaSum;
1.164 + }
1.165 +
1.166 + // OPTIMIZATION: mark as debugging only if used solely by tests
1.167 + const SkOpSpan& span(int tIndex) const {
1.168 + return fTs[tIndex];
1.169 + }
1.170 +
1.171 + // OPTIMIZATION: mark as debugging only if used solely by tests
1.172 + const SkTDArray<SkOpSpan>& spans() const {
1.173 + return fTs;
1.174 + }
1.175 +
1.176 + int spanSign(const SkOpAngle* angle) const {
1.177 + SkASSERT(angle->segment() == this);
1.178 + return spanSign(angle->start(), angle->end());
1.179 + }
1.180 +
1.181 + int spanSign(int startIndex, int endIndex) const {
1.182 + int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue;
1.183 +#if DEBUG_WIND_BUMP
1.184 + SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
1.185 +#endif
1.186 + return result;
1.187 + }
1.188 +
1.189 + double t(int tIndex) const {
1.190 + return fTs[tIndex].fT;
1.191 + }
1.192 +
1.193 + double tAtMid(int start, int end, double mid) const {
1.194 + return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
1.195 + }
1.196 +
1.197 + bool unsortable(int index) const {
1.198 + return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
1.199 + }
1.200 +
1.201 + void updatePts(const SkPoint pts[]) {
1.202 + fPts = pts;
1.203 + }
1.204 +
1.205 + SkPath::Verb verb() const {
1.206 + return fVerb;
1.207 + }
1.208 +
1.209 + int windSum(int tIndex) const {
1.210 + return fTs[tIndex].fWindSum;
1.211 + }
1.212 +
1.213 + int windValue(int tIndex) const {
1.214 + return fTs[tIndex].fWindValue;
1.215 + }
1.216 +
1.217 +#if defined(SK_DEBUG) || DEBUG_WINDING
1.218 + SkScalar xAtT(int index) const {
1.219 + return xAtT(&fTs[index]);
1.220 + }
1.221 +#endif
1.222 +
1.223 + const SkPoint& xyAtT(const SkOpSpan* span) const {
1.224 + return span->fPt;
1.225 + }
1.226 +
1.227 + const SkPoint& xyAtT(int index) const {
1.228 + return xyAtT(&fTs[index]);
1.229 + }
1.230 +
1.231 +#if defined(SK_DEBUG) || DEBUG_WINDING
1.232 + SkScalar yAtT(int index) const {
1.233 + return yAtT(&fTs[index]);
1.234 + }
1.235 +#endif
1.236 +
1.237 + bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);
1.238 + SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
1.239 + bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
1.240 + bool activeWinding(int index, int endIndex);
1.241 + void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
1.242 + void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;
1.243 + void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
1.244 + void addOtherT(int index, double otherT, int otherIndex);
1.245 + void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
1.246 + int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
1.247 + int addT(SkOpSegment* other, const SkPoint& pt, double newT);
1.248 + void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
1.249 + void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
1.250 + SkOpSegment* other);
1.251 + void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
1.252 + bool betweenTs(int lesser, double testT, int greater) const;
1.253 + void checkEnds();
1.254 + bool checkSmall(int index) const;
1.255 + void checkTiny();
1.256 + int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
1.257 + SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
1.258 + int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
1.259 + double mid, bool opp, bool current) const;
1.260 + bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd,
1.261 + int step, SkPoint* startPt, SkPoint* endPt, double* endT) const;
1.262 + SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
1.263 + bool* unsortable, SkPathOp op, const int xorMiMask,
1.264 + const int xorSuMask);
1.265 + SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
1.266 + bool* unsortable);
1.267 + SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
1.268 + int findT(double t, const SkOpSegment* ) const;
1.269 + SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
1.270 + void fixOtherTIndex();
1.271 + void initWinding(int start, int end);
1.272 + void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
1.273 + SkScalar hitOppDx);
1.274 + bool isMissing(double startT, const SkPoint& pt) const;
1.275 + bool isTiny(const SkOpAngle* angle) const;
1.276 + bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel);
1.277 + SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
1.278 + SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
1.279 + SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
1.280 + SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
1.281 + const SkOpAngle* angle);
1.282 + void markDone(int index, int winding);
1.283 + void markDoneBinary(int index);
1.284 + void markDoneUnary(int index);
1.285 + bool nextCandidate(int* start, int* end) const;
1.286 + int nextSpan(int from, int step) const;
1.287 + void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
1.288 + int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
1.289 + enum SortAngleKind {
1.290 + kMustBeOrdered_SortAngleKind, // required for winding calc
1.291 + kMayBeUnordered_SortAngleKind // ok for find top
1.292 + };
1.293 + static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, // FIXME: replace with
1.294 + SkTArray<SkOpAngle*, true>* angleList, // Sort Angles 2
1.295 + SortAngleKind );
1.296 + static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,
1.297 + SkTArray<SkOpAngle*, true>* angleList);
1.298 + bool subDivide(int start, int end, SkPoint edge[4]) const;
1.299 + bool subDivide(int start, int end, SkDCubic* result) const;
1.300 + void undoneSpan(int* start, int* end);
1.301 + int updateOppWindingReverse(const SkOpAngle* angle) const;
1.302 + int updateWindingReverse(const SkOpAngle* angle) const;
1.303 + static bool UseInnerWinding(int outerWinding, int innerWinding);
1.304 + int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
1.305 + int windSum(const SkOpAngle* angle) const;
1.306 +
1.307 +#ifdef SK_DEBUG
1.308 + int debugID() const {
1.309 + return fID;
1.310 + }
1.311 +#endif
1.312 +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
1.313 + void debugShowActiveSpans() const;
1.314 +#endif
1.315 +#if DEBUG_SORT || DEBUG_SWAP_TOP
1.316 + void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
1.317 + const int contourWinding, const int oppContourWinding, bool sortable) const;
1.318 + void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
1.319 + bool sortable);
1.320 +#endif
1.321 +#if DEBUG_CONCIDENT
1.322 + void debugShowTs(const char* prefix) const;
1.323 +#endif
1.324 +#if DEBUG_SHOW_WINDING
1.325 + int debugShowWindingValues(int slotCount, int ofInterest) const;
1.326 +#endif
1.327 +
1.328 +private:
1.329 + struct MissingSpan {
1.330 + double fT;
1.331 + double fEndT;
1.332 + SkOpSegment* fSegment;
1.333 + SkOpSegment* fOther;
1.334 + double fOtherT;
1.335 + SkPoint fPt;
1.336 + };
1.337 +
1.338 + bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
1.339 + bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
1.340 + bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
1.341 + int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
1.342 + int* oppMaxWinding, int* oppSumWinding);
1.343 + bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
1.344 + void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
1.345 + void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
1.346 + void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
1.347 + void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
1.348 + const SkPoint& oPt);
1.349 + void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
1.350 + bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
1.351 + bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
1.352 + void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
1.353 + void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
1.354 + SkTArray<SkPoint, true>* outsideTs);
1.355 + void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
1.356 + SkTArray<SkPoint, true>* outsideTs);
1.357 + bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
1.358 + bool clockwise(int tStart, int tEnd) const;
1.359 + static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1.360 + SkOpAngle::IncludeType );
1.361 + static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1.362 + SkOpAngle::IncludeType );
1.363 + bool decrementSpan(SkOpSpan* span);
1.364 + int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
1.365 + void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
1.366 + bool isSimple(int end) const;
1.367 + bool isTiny(int index) const;
1.368 + void matchWindingValue(int tIndex, double t, bool borrowWind);
1.369 + SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
1.370 + SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
1.371 + SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
1.372 + SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
1.373 + SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);
1.374 + void markDoneBinary(int index, int winding, int oppWinding);
1.375 + SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);
1.376 + void markOneDone(const char* funName, int tIndex, int winding);
1.377 + void markOneDoneBinary(const char* funName, int tIndex);
1.378 + void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);
1.379 + void markOneDoneUnary(const char* funName, int tIndex);
1.380 + SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
1.381 + SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
1.382 + void markWinding(int index, int winding);
1.383 + void markWinding(int index, int winding, int oppWinding);
1.384 + void markUnsortable(int start, int end);
1.385 + bool monotonicInY(int tStart, int tEnd) const;
1.386 + bool multipleSpans(int end) const;
1.387 + SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
1.388 + int nextExactSpan(int from, int step) const;
1.389 + bool serpentine(int tStart, int tEnd) const;
1.390 + void setUpWindings(int index, int endIndex, int* sumMiWinding,
1.391 + int* maxWinding, int* sumWinding);
1.392 + void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
1.393 + static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt,
1.394 + const SkPoint& startPt);
1.395 + static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt);
1.396 + int updateOppWinding(int index, int endIndex) const;
1.397 + int updateOppWinding(const SkOpAngle* angle) const;
1.398 + int updateWinding(int index, int endIndex) const;
1.399 + int updateWinding(const SkOpAngle* angle) const;
1.400 + int updateWindingReverse(int index, int endIndex) const;
1.401 + static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
1.402 + SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
1.403 + SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
1.404 +
1.405 + SkScalar xAtT(const SkOpSpan* span) const {
1.406 + return xyAtT(span).fX;
1.407 + }
1.408 +
1.409 + SkScalar yAtT(const SkOpSpan* span) const {
1.410 + return xyAtT(span).fY;
1.411 + }
1.412 +
1.413 + void zeroSpan(SkOpSpan* span);
1.414 +
1.415 +#if DEBUG_SWAP_TOP
1.416 + bool controlsContainedByEnds(int tStart, int tEnd) const;
1.417 +#endif
1.418 +#if DEBUG_CONCIDENT
1.419 + void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
1.420 +#endif
1.421 +#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
1.422 + void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
1.423 + void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);
1.424 +#endif
1.425 +#if DEBUG_WINDING
1.426 + static char as_digit(int value) {
1.427 + return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
1.428 + }
1.429 +#endif
1.430 + void debugValidate() const;
1.431 +#ifdef SK_DEBUG
1.432 + void dumpPts() const;
1.433 + void dumpDPts() const;
1.434 + void dumpSpans() const;
1.435 +#endif
1.436 +
1.437 + const SkPoint* fPts;
1.438 + SkPathOpsBounds fBounds;
1.439 + // FIXME: can't convert to SkTArray because it uses insert
1.440 + SkTDArray<SkOpSpan> fTs; // two or more (always includes t=0 t=1)
1.441 + // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
1.442 + int fDoneSpans; // quick check that segment is finished
1.443 + // OPTIMIZATION: force the following to be byte-sized
1.444 + SkPath::Verb fVerb;
1.445 + bool fOperand;
1.446 + bool fXor; // set if original contour had even-odd fill
1.447 + bool fOppXor; // set if opposite operand had even-odd fill
1.448 +#ifdef SK_DEBUG
1.449 + int fID;
1.450 +#endif
1.451 +};
1.452 +
1.453 +#endif
