michael@0: /*
michael@0:  * Copyright 2013 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #ifndef SkOpContour_DEFINED
michael@0: #define SkOpContour_DEFINED
michael@0: 
michael@0: #include "SkOpSegment.h"
michael@0: #include "SkTArray.h"
michael@0: 
michael@0: class SkIntersections;
michael@0: class SkOpContour;
michael@0: class SkPathWriter;
michael@0: 
michael@0: struct SkCoincidence {
michael@0:     SkOpContour* fOther;
michael@0:     int fSegments[2];
michael@0:     double fTs[2][2];
michael@0:     SkPoint fPts[2];
michael@0: };
michael@0: 
michael@0: class SkOpContour {
michael@0: public:
michael@0:     SkOpContour() {
michael@0:         reset();
michael@0: #ifdef SK_DEBUG
michael@0:         fID = ++SkPathOpsDebug::gContourID;
michael@0: #endif
michael@0:     }
michael@0: 
michael@0:     bool operator<(const SkOpContour& rh) const {
michael@0:         return fBounds.fTop == rh.fBounds.fTop
michael@0:                 ? fBounds.fLeft < rh.fBounds.fLeft
michael@0:                 : fBounds.fTop < rh.fBounds.fTop;
michael@0:     }
michael@0: 
michael@0:     bool addCoincident(int index, SkOpContour* other, int otherIndex,
michael@0:                        const SkIntersections& ts, bool swap);
michael@0:     void addCoincidentPoints();
michael@0: 
michael@0:     void addCross(const SkOpContour* crosser) {
michael@0: #ifdef DEBUG_CROSS
michael@0:         for (int index = 0; index < fCrosses.count(); ++index) {
michael@0:             SkASSERT(fCrosses[index] != crosser);
michael@0:         }
michael@0: #endif
michael@0:         fCrosses.push_back(crosser);
michael@0:     }
michael@0: 
michael@0:     void addCubic(const SkPoint pts[4]) {
michael@0:         fSegments.push_back().addCubic(pts, fOperand, fXor);
michael@0:         fContainsCurves = fContainsCubics = true;
michael@0:     }
michael@0: 
michael@0:     int addLine(const SkPoint pts[2]) {
michael@0:         fSegments.push_back().addLine(pts, fOperand, fXor);
michael@0:         return fSegments.count();
michael@0:     }
michael@0: 
michael@0:     void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
michael@0:         fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
michael@0:     }
michael@0: 
michael@0:     bool addPartialCoincident(int index, SkOpContour* other, int otherIndex,
michael@0:                        const SkIntersections& ts, int ptIndex, bool swap);
michael@0: 
michael@0:     int addQuad(const SkPoint pts[3]) {
michael@0:         fSegments.push_back().addQuad(pts, fOperand, fXor);
michael@0:         fContainsCurves = true;
michael@0:         return fSegments.count();
michael@0:     }
michael@0: 
michael@0:     int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
michael@0:         setContainsIntercepts();
michael@0:         return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
michael@0:     }
michael@0: 
michael@0:     int addSelfT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
michael@0:         setContainsIntercepts();
michael@0:         return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, newT);
michael@0:     }
michael@0: 
michael@0:     const SkPathOpsBounds& bounds() const {
michael@0:         return fBounds;
michael@0:     }
michael@0: 
michael@0:     void calcCoincidentWinding();
michael@0:     void calcPartialCoincidentWinding();
michael@0: 
michael@0:     void checkEnds() {
michael@0:         if (!fContainsCurves) {
michael@0:             return;
michael@0:         }
michael@0:         int segmentCount = fSegments.count();
michael@0:         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
michael@0:             SkOpSegment* segment = &fSegments[sIndex];
michael@0:             if (segment->verb() == SkPath::kLine_Verb) {
michael@0:                 continue;
michael@0:             }
michael@0:             if (segment->done()) {
michael@0:                 continue;   // likely coincident, nothing to do
michael@0:             }
michael@0:             segment->checkEnds();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // if same point has different T values, choose a common T
michael@0:     void checkTiny() {
michael@0:         int segmentCount = fSegments.count();
michael@0:         if (segmentCount <= 2) {
michael@0:             return;
michael@0:         }
michael@0:         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
michael@0:             fSegments[sIndex].checkTiny();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void complete() {
michael@0:         setBounds();
michael@0:         fContainsIntercepts = false;
michael@0:     }
michael@0: 
michael@0:     bool containsCubics() const {
michael@0:         return fContainsCubics;
michael@0:     }
michael@0: 
michael@0:     bool crosses(const SkOpContour* crosser) const {
michael@0:         for (int index = 0; index < fCrosses.count(); ++index) {
michael@0:             if (fCrosses[index] == crosser) {
michael@0:                 return true;
michael@0:             }
michael@0:         }
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     bool done() const {
michael@0:         return fDone;
michael@0:     }
michael@0: 
michael@0:     const SkPoint& end() const {
michael@0:         const SkOpSegment& segment = fSegments.back();
michael@0:         return segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
michael@0:     }
michael@0: 
michael@0:     void fixOtherTIndex() {
michael@0:         int segmentCount = fSegments.count();
michael@0:         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
michael@0:             fSegments[sIndex].fixOtherTIndex();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void joinCoincidence() {
michael@0:         joinCoincidence(fCoincidences, false);
michael@0:         joinCoincidence(fPartialCoincidences, true);
michael@0:     }
michael@0: 
michael@0:     SkOpSegment* nonVerticalSegment(int* start, int* end);
michael@0: 
michael@0:     bool operand() const {
michael@0:         return fOperand;
michael@0:     }
michael@0: 
michael@0:     void reset() {
michael@0:         fSegments.reset();
michael@0:         fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
michael@0:         fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false;
michael@0:     }
michael@0: 
michael@0:     SkTArray<SkOpSegment>& segments() {
michael@0:         return fSegments;
michael@0:     }
michael@0: 
michael@0:     void setContainsIntercepts() {
michael@0:         fContainsIntercepts = true;
michael@0:     }
michael@0: 
michael@0:     void setOperand(bool isOp) {
michael@0:         fOperand = isOp;
michael@0:     }
michael@0: 
michael@0:     void setOppXor(bool isOppXor) {
michael@0:         fOppXor = isOppXor;
michael@0:         int segmentCount = fSegments.count();
michael@0:         for (int test = 0; test < segmentCount; ++test) {
michael@0:             fSegments[test].setOppXor(isOppXor);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void setXor(bool isXor) {
michael@0:         fXor = isXor;
michael@0:     }
michael@0: 
michael@0:     void sortSegments();
michael@0: 
michael@0:     const SkPoint& start() const {
michael@0:         return fSegments.front().pts()[0];
michael@0:     }
michael@0: 
michael@0:     void toPath(SkPathWriter* path) const;
michael@0: 
michael@0:     void toPartialBackward(SkPathWriter* path) const {
michael@0:         int segmentCount = fSegments.count();
michael@0:         for (int test = segmentCount - 1; test >= 0; --test) {
michael@0:             fSegments[test].addCurveTo(1, 0, path, true);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void toPartialForward(SkPathWriter* path) const {
michael@0:         int segmentCount = fSegments.count();
michael@0:         for (int test = 0; test < segmentCount; ++test) {
michael@0:             fSegments[test].addCurveTo(0, 1, path, true);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, SkOpSegment** topStart);
michael@0:     SkOpSegment* undoneSegment(int* start, int* end);
michael@0: 
michael@0:     int updateSegment(int index, const SkPoint* pts) {
michael@0:         SkOpSegment& segment = fSegments[index];
michael@0:         segment.updatePts(pts);
michael@0:         return SkPathOpsVerbToPoints(segment.verb()) + 1;
michael@0:     }
michael@0: 
michael@0: #if DEBUG_TEST
michael@0:     SkTArray<SkOpSegment>& debugSegments() {
michael@0:         return fSegments;
michael@0:     }
michael@0: #endif
michael@0: 
michael@0: #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
michael@0:     void debugShowActiveSpans() {
michael@0:         for (int index = 0; index < fSegments.count(); ++index) {
michael@0:             fSegments[index].debugShowActiveSpans();
michael@0:         }
michael@0:     }
michael@0: #endif
michael@0: 
michael@0: #if DEBUG_SHOW_WINDING
michael@0:     int debugShowWindingValues(int totalSegments, int ofInterest);
michael@0:     static void debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList);
michael@0: #endif
michael@0: 
michael@0: private:
michael@0:     void calcCommonCoincidentWinding(const SkCoincidence& );
michael@0:     void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
michael@0:     void setBounds();
michael@0: 
michael@0:     SkTArray<SkOpSegment> fSegments;
michael@0:     SkTArray<SkOpSegment*, true> fSortedSegments;
michael@0:     int fFirstSorted;
michael@0:     SkTArray<SkCoincidence, true> fCoincidences;
michael@0:     SkTArray<SkCoincidence, true> fPartialCoincidences;
michael@0:     SkTArray<const SkOpContour*, true> fCrosses;
michael@0:     SkPathOpsBounds fBounds;
michael@0:     bool fContainsIntercepts;  // FIXME: is this used by anybody?
michael@0:     bool fContainsCubics;
michael@0:     bool fContainsCurves;
michael@0:     bool fDone;
michael@0:     bool fOperand;  // true for the second argument to a binary operator
michael@0:     bool fXor;
michael@0:     bool fOppXor;
michael@0: #ifdef SK_DEBUG
michael@0:     int fID;
michael@0: #endif
michael@0: };
michael@0: 
michael@0: #endif