1 /*
2  * Copyright 2012 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 #ifndef SkOpSegment_DEFINE
8 #define SkOpSegment_DEFINE
9 
10 #include "SkOpAngle.h"
11 #include "SkOpSpan.h"
12 #include "SkOpTAllocator.h"
13 #include "SkPathOpsBounds.h"
14 #include "SkPathOpsCubic.h"
15 #include "SkPathOpsCurve.h"
16 
17 struct SkDCurve;
18 class SkOpCoincidence;
19 class SkOpContour;
20 enum class SkOpRayDir;
21 struct SkOpRayHit;
22 class SkPathWriter;
23 
24 class SkOpSegment {
25 public:
26     enum AllowAlias {
27         kAllowAlias,
28         kNoAlias
29     };
30 
31     bool operator<(const SkOpSegment& rh) const {
32         return fBounds.fTop < rh.fBounds.fTop;
33     }
34 
35     SkOpAngle* activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
36                             bool* done);
37     SkOpAngle* activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
38                                        SkOpSpanBase** endPtr, bool* done);
39     SkOpAngle* activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
40                                        SkOpSpanBase** endPtr, bool* done);
41     bool activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
42                   SkPathOp op);
43     bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op,
44                   int* sumMiWinding, int* sumSuWinding);
45 
46     bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end);
47     bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding);
48 
addConic(SkPoint pts[3],SkScalar weight,SkOpContour * parent)49     SkOpSegment* addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) {
50         init(pts, weight, parent, SkPath::kConic_Verb);
51         SkDCurve curve;
52         curve.fConic.set(pts, weight);
53         curve.setConicBounds(pts, weight, 0, 1, &fBounds);
54         return this;
55     }
56 
addCubic(SkPoint pts[4],SkOpContour * parent)57     SkOpSegment* addCubic(SkPoint pts[4], SkOpContour* parent) {
58         init(pts, 1, parent, SkPath::kCubic_Verb);
59         SkDCurve curve;
60         curve.fCubic.set(pts);
61         curve.setCubicBounds(pts, 1, 0, 1, &fBounds);
62         return this;
63     }
64 
65     void addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path,
66                     bool active) const;
67 
addEndSpan(SkChunkAlloc * allocator)68     SkOpAngle* addEndSpan(SkChunkAlloc* allocator) {
69         SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
70         angle->set(&fTail, fTail.prev());
71         fTail.setFromAngle(angle);
72         return angle;
73     }
74 
addLine(SkPoint pts[2],SkOpContour * parent)75     SkOpSegment* addLine(SkPoint pts[2], SkOpContour* parent) {
76         init(pts, 1, parent, SkPath::kLine_Verb);
77         fBounds.set(pts, 2);
78         return this;
79     }
80 
81     SkOpPtT* addMissing(double t, SkOpSegment* opp, SkChunkAlloc* );
82 
addStartSpan(SkChunkAlloc * allocator)83     SkOpAngle* addStartSpan(SkChunkAlloc* allocator) {
84         SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
85         angle->set(&fHead, fHead.next());
86         fHead.setToAngle(angle);
87         return angle;
88     }
89 
addQuad(SkPoint pts[3],SkOpContour * parent)90     SkOpSegment* addQuad(SkPoint pts[3], SkOpContour* parent) {
91         init(pts, 1, parent, SkPath::kQuad_Verb);
92         SkDCurve curve;
93         curve.fQuad.set(pts);
94         curve.setQuadBounds(pts, 1, 0, 1, &fBounds);
95         return this;
96     }
97 
98     SkOpPtT* addT(double t, AllowAlias , SkChunkAlloc* );
99 
100     void align();
101 
bounds()102     const SkPathOpsBounds& bounds() const {
103         return fBounds;
104     }
105 
bumpCount()106     void bumpCount() {
107         ++fCount;
108     }
109 
110     void calcAngles(SkChunkAlloc*);
111     void checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* allocator);
112     void checkNearCoincidence(SkOpAngle* );
113     bool collapsed() const;
114     static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
115                               SkOpAngle::IncludeType );
116     static void ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
117                                      SkOpAngle::IncludeType );
118     int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType);
119 
contour()120     SkOpContour* contour() const {
121         return fContour;
122     }
123 
count()124     int count() const {
125         return fCount;
126     }
127 
128     void debugAddAngle(double startT, double endT, SkChunkAlloc*);
129     const SkOpAngle* debugAngle(int id) const;
130     SkOpContour* debugContour(int id);
131 
debugID()132     int debugID() const {
133         return SkDEBUGRELEASE(fID, -1);
134     }
135 
136     SkOpAngle* debugLastAngle();
137     const SkOpPtT* debugPtT(int id) const;
138     void debugReset();
139     const SkOpSegment* debugSegment(int id) const;
140 
141 #if DEBUG_ACTIVE_SPANS
142     void debugShowActiveSpans() const;
143 #endif
144 #if DEBUG_MARK_DONE
145     void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding);
146     void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding);
147 #endif
148 
149     const SkOpSpanBase* debugSpan(int id) const;
150     void debugValidate() const;
151     void detach(const SkOpSpan* );
152     double distSq(double t, SkOpAngle* opp);
153 
done()154     bool done() const {
155         SkASSERT(fDoneCount <= fCount);
156         return fDoneCount == fCount;
157     }
158 
done(const SkOpAngle * angle)159     bool done(const SkOpAngle* angle) const {
160         return angle->start()->starter(angle->end())->done();
161     }
162 
dPtAtT(double mid)163     SkDPoint dPtAtT(double mid) const {
164         return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
165     }
166 
dSlopeAtT(double mid)167     SkDVector dSlopeAtT(double mid) const {
168         return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid);
169     }
170 
171     void dump() const;
172     void dumpAll() const;
173     void dumpAngles() const;
174     void dumpCoin() const;
175     void dumpPts() const;
176     void dumpPtsInner() const;
177 
178     SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
179                              SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op,
180                              int xorMiMask, int xorSuMask);
181     SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
182                                   SkOpSpanBase** nextEnd, bool* unsortable);
183     SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable);
184     SkOpSpan* findSortableTop(SkOpContour* );
185     SkOpGlobalState* globalState() const;
186 
head()187     const SkOpSpan* head() const {
188         return &fHead;
189     }
190 
head()191     SkOpSpan* head() {
192         return &fHead;
193     }
194 
195     void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
196 
insert(SkOpSpan * prev,SkChunkAlloc * allocator)197     SkOpSpan* insert(SkOpSpan* prev, SkChunkAlloc* allocator) {
198         SkOpSpan* result = SkOpTAllocator<SkOpSpan>::Allocate(allocator);
199         SkOpSpanBase* next = prev->next();
200         result->setPrev(prev);
201         prev->setNext(result);
202         SkDEBUGCODE(result->ptT()->fT = 0);
203         result->setNext(next);
204         if (next) {
205             next->setPrev(result);
206         }
207         return result;
208     }
209 
210     bool isClose(double t, const SkOpSegment* opp) const;
211 
isHorizontal()212     bool isHorizontal() const {
213         return fBounds.fTop == fBounds.fBottom;
214     }
215 
isSimple(SkOpSpanBase ** end,int * step)216     SkOpSegment* isSimple(SkOpSpanBase** end, int* step) {
217         return nextChase(end, step, NULL, NULL);
218     }
219 
isVertical()220     bool isVertical() const {
221         return fBounds.fLeft == fBounds.fRight;
222     }
223 
isVertical(SkOpSpanBase * start,SkOpSpanBase * end)224     bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const {
225         return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t());
226     }
227 
228     bool isXor() const;
229 
lastPt()230     const SkPoint& lastPt() const {
231         return fPts[SkPathOpsVerbToPoints(fVerb)];
232     }
233 
234     SkOpSpanBase* markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end);
235     bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
236             SkOpSpanBase** lastPtr);
237     bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
238             int oppWinding, SkOpSpanBase** lastPtr);
239     SkOpSpanBase* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);
240     SkOpSpanBase* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
241                          const SkOpAngle* angle);
242     void markDone(SkOpSpan* );
243     bool markWinding(SkOpSpan* , int winding);
244     bool markWinding(SkOpSpan* , int winding, int oppWinding);
245     bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const;
246     void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator);
247     void moveMultiples();
248     void moveNearby();
249 
next()250     SkOpSegment* next() const {
251         return fNext;
252     }
253 
254     SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
255     bool operand() const;
256 
OppSign(const SkOpSpanBase * start,const SkOpSpanBase * end)257     static int OppSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
258         int result = start->t() < end->t() ? -start->upCast()->oppValue()
259                 : end->upCast()->oppValue();
260         return result;
261     }
262 
263     bool oppXor() const;
264 
prev()265     const SkOpSegment* prev() const {
266         return fPrev;
267     }
268 
ptAtT(double mid)269     SkPoint ptAtT(double mid) const {
270         return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
271     }
272 
pts()273     const SkPoint* pts() const {
274         return fPts;
275     }
276 
ptsDisjoint(const SkOpPtT & span,const SkOpPtT & test)277     bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const {
278         return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt);
279     }
280 
ptsDisjoint(const SkOpPtT & span,double t,const SkPoint & pt)281     bool ptsDisjoint(const SkOpPtT& span, double t, const SkPoint& pt) const {
282         return ptsDisjoint(span.fT, span.fPt, t, pt);
283     }
284 
285     bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const;
286 
287     void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
288                   SkChunkAlloc* allocator);
289 
resetVisited()290     void resetVisited() {
291         fVisited = false;
292     }
293 
setContour(SkOpContour * contour)294     void setContour(SkOpContour* contour) {
295         fContour = contour;
296     }
297 
setCubicType(SkDCubic::CubicType cubicType)298     void setCubicType(SkDCubic::CubicType cubicType) {
299         fCubicType = cubicType;
300     }
301 
setNext(SkOpSegment * next)302     void setNext(SkOpSegment* next) {
303         fNext = next;
304     }
305 
setPrev(SkOpSegment * prev)306     void setPrev(SkOpSegment* prev) {
307         fPrev = prev;
308     }
309 
setVisited()310     void setVisited() {
311         fVisited = true;
312     }
313 
setUpWinding(SkOpSpanBase * start,SkOpSpanBase * end,int * maxWinding,int * sumWinding)314     void setUpWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* maxWinding, int* sumWinding) {
315         int deltaSum = SpanSign(start, end);
316         *maxWinding = *sumWinding;
317         *sumWinding -= deltaSum;
318     }
319 
320     void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
321                        int* maxWinding, int* sumWinding);
322     void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, int* sumSuWinding,
323                        int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
324     void sortAngles();
325 
SpanSign(const SkOpSpanBase * start,const SkOpSpanBase * end)326     static int SpanSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
327         int result = start->t() < end->t() ? -start->upCast()->windValue()
328                 : end->upCast()->windValue();
329         return result;
330     }
331 
spanToAngle(SkOpSpanBase * start,SkOpSpanBase * end)332     SkOpAngle* spanToAngle(SkOpSpanBase* start, SkOpSpanBase* end) {
333         SkASSERT(start != end);
334         return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle();
335     }
336 
337     bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const;
338     bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkOpCurve* result) const;
339 
tail()340     const SkOpSpanBase* tail() const {
341         return &fTail;
342     }
343 
tail()344     SkOpSpanBase* tail() {
345         return &fTail;
346     }
347 
348     void undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end);
349     int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const;
350     int updateOppWinding(const SkOpAngle* angle) const;
351     int updateOppWindingReverse(const SkOpAngle* angle) const;
352     int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end);
353     int updateWinding(SkOpAngle* angle);
354     int updateWindingReverse(const SkOpAngle* angle);
355 
356     static bool UseInnerWinding(int outerWinding, int innerWinding);
357 
verb()358     SkPath::Verb verb() const {
359         return fVerb;
360     }
361 
362     // look for two different spans that point to the same opposite segment
visited()363     bool visited() {
364         if (!fVisited) {
365             fVisited = true;
366             return false;
367         }
368         return true;
369     }
370 
weight()371     SkScalar weight() const {
372         return fWeight;
373     }
374 
375     SkOpSpan* windingSpanAtT(double tHit);
376     int windSum(const SkOpAngle* angle) const;
377 
writablePt(bool end)378     SkPoint* writablePt(bool end) {
379         return &fPts[end ? SkPathOpsVerbToPoints(fVerb) : 0];
380     }
381 
382 private:
383     SkOpSpan fHead;  // the head span always has its t set to zero
384     SkOpSpanBase fTail;  // the tail span always has its t set to one
385     SkOpContour* fContour;
386     SkOpSegment* fNext;  // forward-only linked list used by contour to walk the segments
387     const SkOpSegment* fPrev;
388     SkPoint* fPts;  // pointer into array of points owned by edge builder that may be tweaked
389     SkPathOpsBounds fBounds;  // tight bounds
390     SkScalar fWeight;
391     int fCount;  // number of spans (one for a non-intersecting segment)
392     int fDoneCount;  // number of processed spans (zero initially)
393     SkPath::Verb fVerb;
394     SkDCubic::CubicType fCubicType;
395     bool fTopsFound;
396     bool fVisited;  // used by missing coincidence check
397     SkDEBUGCODE(int fID);
398 };
399 
400 #endif
401