1/*
2 * Copyright 2013 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 SkOpContour_DEFINED
8#define SkOpContour_DEFINED
9
10#include "include/private/SkTDArray.h"
11#include "src/core/SkTSort.h"
12#include "src/pathops/SkOpSegment.h"
13
14enum class SkOpRayDir;
15struct SkOpRayHit;
16class SkPathWriter;
17
18class SkOpContour {
19public:
20 SkOpContour() {
21 reset();
22 }
23
24 bool operator<(const SkOpContour& rh) const {
25 return fBounds.fTop == rh.fBounds.fTop
26 ? fBounds.fLeft < rh.fBounds.fLeft
27 : fBounds.fTop < rh.fBounds.fTop;
28 }
29
30 void addConic(SkPoint pts[3], SkScalar weight) {
31 appendSegment().addConic(pts, weight, this);
32 }
33
34 void addCubic(SkPoint pts[4]) {
35 appendSegment().addCubic(pts, this);
36 }
37
38 SkOpSegment* addLine(SkPoint pts[2]) {
39 SkASSERT(pts[0] != pts[1]);
40 return appendSegment().addLine(pts, this);
41 }
42
43 void addQuad(SkPoint pts[3]) {
44 appendSegment().addQuad(pts, this);
45 }
46
47 SkOpSegment& appendSegment() {
48 SkOpSegment* result = fCount++ ? this->globalState()->allocator()->make<SkOpSegment>()
49 : &fHead;
50 result->setPrev(fTail);
51 if (fTail) {
52 fTail->setNext(result);
53 }
54 fTail = result;
55 return *result;
56 }
57
58 const SkPathOpsBounds& bounds() const {
59 return fBounds;
60 }
61
62 void calcAngles() {
63 SkASSERT(fCount > 0);
64 SkOpSegment* segment = &fHead;
65 do {
66 segment->calcAngles();
67 } while ((segment = segment->next()));
68 }
69
70 void complete() {
71 setBounds();
72 }
73
74 int count() const {
75 return fCount;
76 }
77
78 int debugID() const {
79 return SkDEBUGRELEASE(fID, -1);
80 }
81
82 int debugIndent() const {
83 return SkDEBUGRELEASE(fDebugIndent, 0);
84 }
85
86
87 const SkOpAngle* debugAngle(int id) const {
88 return SkDEBUGRELEASE(this->globalState()->debugAngle(id), nullptr);
89 }
90
91 const SkOpCoincidence* debugCoincidence() const {
92 return this->globalState()->coincidence();
93 }
94
95#if DEBUG_COIN
96 void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const;
97#endif
98
99 SkOpContour* debugContour(int id) const {
100 return SkDEBUGRELEASE(this->globalState()->debugContour(id), nullptr);
101 }
102
103#if DEBUG_COIN
104 void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const;
105 void debugMoveMultiples(SkPathOpsDebug::GlitchLog* ) const;
106 void debugMoveNearby(SkPathOpsDebug::GlitchLog* log) const;
107#endif
108
109 const SkOpPtT* debugPtT(int id) const {
110 return SkDEBUGRELEASE(this->globalState()->debugPtT(id), nullptr);
111 }
112
113 const SkOpSegment* debugSegment(int id) const {
114 return SkDEBUGRELEASE(this->globalState()->debugSegment(id), nullptr);
115 }
116
117#if DEBUG_ACTIVE_SPANS
118 void debugShowActiveSpans(SkString* str) {
119 SkOpSegment* segment = &fHead;
120 do {
121 segment->debugShowActiveSpans(str);
122 } while ((segment = segment->next()));
123 }
124#endif
125
126 const SkOpSpanBase* debugSpan(int id) const {
127 return SkDEBUGRELEASE(this->globalState()->debugSpan(id), nullptr);
128 }
129
130 SkOpGlobalState* globalState() const {
131 return fState;
132 }
133
134 void debugValidate() const {
135#if DEBUG_VALIDATE
136 const SkOpSegment* segment = &fHead;
137 const SkOpSegment* prior = nullptr;
138 do {
139 segment->debugValidate();
140 SkASSERT(segment->prev() == prior);
141 prior = segment;
142 } while ((segment = segment->next()));
143 SkASSERT(prior == fTail);
144#endif
145 }
146
147 bool done() const {
148 return fDone;
149 }
150
151 void dump() const;
152 void dumpAll() const;
153 void dumpAngles() const;
154 void dumpContours() const;
155 void dumpContoursAll() const;
156 void dumpContoursAngles() const;
157 void dumpContoursPts() const;
158 void dumpContoursPt(int segmentID) const;
159 void dumpContoursSegment(int segmentID) const;
160 void dumpContoursSpan(int segmentID) const;
161 void dumpContoursSpans() const;
162 void dumpPt(int ) const;
163 void dumpPts(const char* prefix = "seg") const;
164 void dumpPtsX(const char* prefix) const;
165 void dumpSegment(int ) const;
166 void dumpSegments(const char* prefix = "seg", SkPathOp op = (SkPathOp) -1) const;
167 void dumpSpan(int ) const;
168 void dumpSpans() const;
169
170 const SkPoint& end() const {
171 return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())];
172 }
173
174 SkOpSpan* findSortableTop(SkOpContour* );
175
176 SkOpSegment* first() {
177 SkASSERT(fCount > 0);
178 return &fHead;
179 }
180
181 const SkOpSegment* first() const {
182 SkASSERT(fCount > 0);
183 return &fHead;
184 }
185
186 void indentDump() const {
187 SkDEBUGCODE(fDebugIndent += 2);
188 }
189
190 void init(SkOpGlobalState* globalState, bool operand, bool isXor) {
191 fState = globalState;
192 fOperand = operand;
193 fXor = isXor;
194 SkDEBUGCODE(fID = globalState->nextContourID());
195 }
196
197 int isCcw() const {
198 return fCcw;
199 }
200
201 bool isXor() const {
202 return fXor;
203 }
204
205 void joinSegments() {
206 SkOpSegment* segment = &fHead;
207 SkOpSegment* next;
208 do {
209 next = segment->next();
210 segment->joinEnds(next ? next : &fHead);
211 } while ((segment = next));
212 }
213
214 void markAllDone() {
215 SkOpSegment* segment = &fHead;
216 do {
217 segment->markAllDone();
218 } while ((segment = segment->next()));
219 }
220
221 // Please keep this aligned with debugMissingCoincidence()
222 bool missingCoincidence() {
223 SkASSERT(fCount > 0);
224 SkOpSegment* segment = &fHead;
225 bool result = false;
226 do {
227 if (segment->missingCoincidence()) {
228 result = true;
229 }
230 segment = segment->next();
231 } while (segment);
232 return result;
233 }
234
235 bool moveMultiples() {
236 SkASSERT(fCount > 0);
237 SkOpSegment* segment = &fHead;
238 do {
239 if (!segment->moveMultiples()) {
240 return false;
241 }
242 } while ((segment = segment->next()));
243 return true;
244 }
245
246 bool moveNearby() {
247 SkASSERT(fCount > 0);
248 SkOpSegment* segment = &fHead;
249 do {
250 if (!segment->moveNearby()) {
251 return false;
252 }
253 } while ((segment = segment->next()));
254 return true;
255 }
256
257 SkOpContour* next() {
258 return fNext;
259 }
260
261 const SkOpContour* next() const {
262 return fNext;
263 }
264
265 bool operand() const {
266 return fOperand;
267 }
268
269 bool oppXor() const {
270 return fOppXor;
271 }
272
273 void outdentDump() const {
274 SkDEBUGCODE(fDebugIndent -= 2);
275 }
276
277 void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkArenaAlloc*);
278
279 void reset() {
280 fTail = nullptr;
281 fNext = nullptr;
282 fCount = 0;
283 fDone = false;
284 SkDEBUGCODE(fBounds.setLTRB(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin));
285 SkDEBUGCODE(fFirstSorted = -1);
286 SkDEBUGCODE(fDebugIndent = 0);
287 }
288
289 void resetReverse() {
290 SkOpContour* next = this;
291 do {
292 if (!next->count()) {
293 continue;
294 }
295 next->fCcw = -1;
296 next->fReverse = false;
297 } while ((next = next->next()));
298 }
299
300 bool reversed() const {
301 return fReverse;
302 }
303
304 void setBounds() {
305 SkASSERT(fCount > 0);
306 const SkOpSegment* segment = &fHead;
307 fBounds = segment->bounds();
308 while ((segment = segment->next())) {
309 fBounds.add(segment->bounds());
310 }
311 }
312
313 void setCcw(int ccw) {
314 fCcw = ccw;
315 }
316
317 void setGlobalState(SkOpGlobalState* state) {
318 fState = state;
319 }
320
321 void setNext(SkOpContour* contour) {
322// SkASSERT(!fNext == !!contour);
323 fNext = contour;
324 }
325
326 void setOperand(bool isOp) {
327 fOperand = isOp;
328 }
329
330 void setOppXor(bool isOppXor) {
331 fOppXor = isOppXor;
332 }
333
334 void setReverse() {
335 fReverse = true;
336 }
337
338 void setXor(bool isXor) {
339 fXor = isXor;
340 }
341
342 bool sortAngles() {
343 SkASSERT(fCount > 0);
344 SkOpSegment* segment = &fHead;
345 do {
346 FAIL_IF(!segment->sortAngles());
347 } while ((segment = segment->next()));
348 return true;
349 }
350
351 const SkPoint& start() const {
352 return fHead.pts()[0];
353 }
354
355 void toPartialBackward(SkPathWriter* path) const {
356 const SkOpSegment* segment = fTail;
357 do {
358 SkAssertResult(segment->addCurveTo(segment->tail(), segment->head(), path));
359 } while ((segment = segment->prev()));
360 }
361
362 void toPartialForward(SkPathWriter* path) const {
363 const SkOpSegment* segment = &fHead;
364 do {
365 SkAssertResult(segment->addCurveTo(segment->head(), segment->tail(), path));
366 } while ((segment = segment->next()));
367 }
368
369 void toReversePath(SkPathWriter* path) const;
370 void toPath(SkPathWriter* path) const;
371 SkOpSpan* undoneSpan();
372
373protected:
374 SkOpGlobalState* fState;
375 SkOpSegment fHead;
376 SkOpSegment* fTail;
377 SkOpContour* fNext;
378 SkPathOpsBounds fBounds;
379 int fCcw;
380 int fCount;
381 int fFirstSorted;
382 bool fDone; // set by find top segment
383 bool fOperand; // true for the second argument to a binary operator
384 bool fReverse; // true if contour should be reverse written to path (used only by fix winding)
385 bool fXor; // set if original path had even-odd fill
386 bool fOppXor; // set if opposite path had even-odd fill
387 SkDEBUGCODE(int fID);
388 SkDEBUGCODE(mutable int fDebugIndent);
389};
390
391class SkOpContourHead : public SkOpContour {
392public:
393 SkOpContour* appendContour() {
394 SkOpContour* contour = this->globalState()->allocator()->make<SkOpContour>();
395 contour->setNext(nullptr);
396 SkOpContour* prev = this;
397 SkOpContour* next;
398 while ((next = prev->next())) {
399 prev = next;
400 }
401 prev->setNext(contour);
402 return contour;
403 }
404
405 void joinAllSegments() {
406 SkOpContour* next = this;
407 do {
408 if (!next->count()) {
409 continue;
410 }
411 next->joinSegments();
412 } while ((next = next->next()));
413 }
414
415 void remove(SkOpContour* contour) {
416 if (contour == this) {
417 SkASSERT(this->count() == 0);
418 return;
419 }
420 SkASSERT(contour->next() == nullptr);
421 SkOpContour* prev = this;
422 SkOpContour* next;
423 while ((next = prev->next()) != contour) {
424 SkASSERT(next);
425 prev = next;
426 }
427 SkASSERT(prev);
428 prev->setNext(nullptr);
429 }
430
431};
432
433class SkOpContourBuilder {
434public:
435 SkOpContourBuilder(SkOpContour* contour)
436 : fContour(contour)
437 , fLastIsLine(false) {
438 }
439
440 void addConic(SkPoint pts[3], SkScalar weight);
441 void addCubic(SkPoint pts[4]);
442 void addCurve(SkPath::Verb verb, const SkPoint pts[4], SkScalar weight = 1);
443 void addLine(const SkPoint pts[2]);
444 void addQuad(SkPoint pts[3]);
445 void flush();
446 SkOpContour* contour() { return fContour; }
447 void setContour(SkOpContour* contour) { flush(); fContour = contour; }
448protected:
449 SkOpContour* fContour;
450 SkPoint fLastLine[2];
451 bool fLastIsLine;
452};
453
454#endif
455