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