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#include "SkAddIntersections.h"
8#include "SkOpCoincidence.h"
9#include "SkOpEdgeBuilder.h"
10#include "SkPathOpsCommon.h"
11#include "SkPathWriter.h"
12
13static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
14        SkOpSpanBase** endPtr) {
15    while (chase.count()) {
16        SkOpSpanBase* span;
17        chase.pop(&span);
18        // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
19        *startPtr = span->ptT()->prev()->span();
20        SkOpSegment* segment = (*startPtr)->segment();
21        bool done = true;
22        *endPtr = nullptr;
23        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
24            *startPtr = last->start();
25            *endPtr = last->end();
26   #if TRY_ROTATE
27            *chase.insert(0) = span;
28   #else
29            *chase.append() = span;
30   #endif
31            return last->segment();
32        }
33        if (done) {
34            continue;
35        }
36        int winding;
37        bool sortable;
38        const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
39        if (!angle) {
40            return nullptr;
41        }
42        if (winding == SK_MinS32) {
43            continue;
44        }
45        int sumMiWinding, sumSuWinding;
46        if (sortable) {
47            segment = angle->segment();
48            sumMiWinding = segment->updateWindingReverse(angle);
49            if (sumMiWinding == SK_MinS32) {
50                SkASSERT(segment->globalState()->debugSkipAssert());
51                return nullptr;
52            }
53            sumSuWinding = segment->updateOppWindingReverse(angle);
54            if (sumSuWinding == SK_MinS32) {
55                SkASSERT(segment->globalState()->debugSkipAssert());
56                return nullptr;
57            }
58            if (segment->operand()) {
59                SkTSwap<int>(sumMiWinding, sumSuWinding);
60            }
61        }
62        SkOpSegment* first = nullptr;
63        const SkOpAngle* firstAngle = angle;
64        while ((angle = angle->next()) != firstAngle) {
65            segment = angle->segment();
66            SkOpSpanBase* start = angle->start();
67            SkOpSpanBase* end = angle->end();
68            int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
69            if (sortable) {
70                segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
71                        &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
72            }
73            if (!segment->done(angle)) {
74                if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
75                    first = segment;
76                    *startPtr = start;
77                    *endPtr = end;
78                }
79                // OPTIMIZATION: should this also add to the chase?
80                if (sortable) {
81                    (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
82                        oppSumWinding, angle);
83                }
84            }
85        }
86        if (first) {
87       #if TRY_ROTATE
88            *chase.insert(0) = span;
89       #else
90            *chase.append() = span;
91       #endif
92            return first;
93        }
94    }
95    return nullptr;
96}
97
98static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
99        const int xorMask, const int xorOpMask, SkPathWriter* simple) {
100    bool unsortable = false;
101    do {
102        SkOpSpan* span = FindSortableTop(contourList);
103        if (!span) {
104            break;
105        }
106        SkOpSegment* current = span->segment();
107        SkOpSpanBase* start = span->next();
108        SkOpSpanBase* end = span;
109        SkTDArray<SkOpSpanBase*> chase;
110        do {
111            if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
112                do {
113                    if (!unsortable && current->done()) {
114                        break;
115                    }
116                    SkASSERT(unsortable || !current->done());
117                    SkOpSpanBase* nextStart = start;
118                    SkOpSpanBase* nextEnd = end;
119                    SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
120                            &unsortable, op, xorMask, xorOpMask);
121                    if (!next) {
122                        if (!unsortable && simple->hasMove()
123                                && current->verb() != SkPath::kLine_Verb
124                                && !simple->isClosed()) {
125                            if (!current->addCurveTo(start, end, simple)) {
126                                return false;
127                            }
128                            if (!simple->isClosed()) {
129                                SkPathOpsDebug::ShowActiveSpans(contourList);
130                            }
131                        }
132                        break;
133                    }
134        #if DEBUG_FLOW
135                    SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
136                            current->debugID(), start->pt().fX, start->pt().fY,
137                            end->pt().fX, end->pt().fY);
138        #endif
139                    if (!current->addCurveTo(start, end, simple)) {
140                        return false;
141                    }
142                    current = next;
143                    start = nextStart;
144                    end = nextEnd;
145                } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
146                if (current->activeWinding(start, end) && !simple->isClosed()) {
147                    SkOpSpan* spanStart = start->starter(end);
148                    if (!spanStart->done()) {
149                        if (!current->addCurveTo(start, end, simple)) {
150                            return false;
151                        }
152                        current->markDone(spanStart);
153                    }
154                }
155                simple->finishContour();
156            } else {
157                SkOpSpanBase* last = current->markAndChaseDone(start, end);
158                if (last && !last->chased()) {
159                    last->setChased(true);
160                    SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
161                    *chase.append() = last;
162#if DEBUG_WINDING
163                    SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
164                    if (!last->final()) {
165                         SkDebugf(" windSum=%d", last->upCast()->windSum());
166                    }
167                    SkDebugf("\n");
168#endif
169                }
170            }
171            current = findChaseOp(chase, &start, &end);
172            SkPathOpsDebug::ShowActiveSpans(contourList);
173            if (!current) {
174                break;
175            }
176        } while (true);
177    } while (true);
178    return true;
179}
180
181// pretty picture:
182// https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
183static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
184//                  inside minuend                               outside minuend
185//     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
186{{ kDifference_SkPathOp,   kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
187{{ kIntersect_SkPathOp,   kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
188{{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp,   kIntersect_SkPathOp }},
189{{ kXOR_SkPathOp,                 kXOR_SkPathOp }, { kXOR_SkPathOp,                kXOR_SkPathOp }},
190{{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp,   kDifference_SkPathOp }},
191};
192
193static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
194    {{ false, false }, { true, false }},  // diff
195    {{ false, false }, { false, true }},  // sect
196    {{ false, true }, { true, true }},    // union
197    {{ false, true }, { true, false }},   // xor
198    {{ false, true }, { false, false }},  // rev diff
199};
200
201#if DEBUG_T_SECT_LOOP_COUNT
202
203#include "SkMutex.h"
204
205SK_DECLARE_STATIC_MUTEX(debugWorstLoop);
206
207SkOpGlobalState debugWorstState(nullptr, nullptr  SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr)
208        SkDEBUGPARAMS(nullptr));
209
210void ReportPathOpsDebugging() {
211    debugWorstState.debugLoopReport();
212}
213
214extern void (*gVerboseFinalize)();
215
216#endif
217
218bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
219        SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
220    char storage[4096];
221    SkArenaAlloc allocator(storage);  // FIXME: add a constant expression here, tune
222    SkOpContour contour;
223    SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
224    SkOpGlobalState globalState(contourList, &allocator
225            SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
226    SkOpCoincidence coincidence(&globalState);
227#if DEBUG_DUMP_VERIFY
228#ifndef SK_DEBUG
229    const char* testName = "release";
230#endif
231    if (SkPathOpsDebug::gDumpOp) {
232        SkPathOpsDebug::DumpOp(one, two, op, testName);
233    }
234#endif
235    op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
236    SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
237            ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
238    SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two));
239    SkPath scaledOne, scaledTwo;
240    const SkPath* minuend, * subtrahend;
241    if (scaleFactor > SK_Scalar1) {
242        ScalePath(one, 1.f / scaleFactor, &scaledOne);
243        minuend = &scaledOne;
244        ScalePath(two, 1.f / scaleFactor, &scaledTwo);
245        subtrahend = &scaledTwo;
246    } else {
247        minuend = &one;
248        subtrahend = &two;
249    }
250    if (op == kReverseDifference_SkPathOp) {
251        SkTSwap(minuend, subtrahend);
252        op = kDifference_SkPathOp;
253    }
254#if DEBUG_SORT
255    SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
256#endif
257    // turn path into list of segments
258    SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
259    if (builder.unparseable()) {
260        return false;
261    }
262    const int xorMask = builder.xorMask();
263    builder.addOperand(*subtrahend);
264    if (!builder.finish()) {
265        return false;
266    }
267#if DEBUG_DUMP_SEGMENTS
268    contourList->dumpSegments("seg", op);
269#endif
270
271    const int xorOpMask = builder.xorMask();
272    if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
273            xorOpMask == kEvenOdd_PathOpsMask)) {
274        result->reset();
275        result->setFillType(fillType);
276        return true;
277    }
278    // find all intersections between segments
279    SkOpContour* current = contourList;
280    do {
281        SkOpContour* next = current;
282        while (AddIntersectTs(current, next, &coincidence)
283                && (next = next->next()))
284            ;
285    } while ((current = current->next()));
286#if DEBUG_VALIDATE
287    globalState.setPhase(SkOpPhase::kWalking);
288#endif
289    bool success = HandleCoincidence(contourList, &coincidence);
290#if DEBUG_COIN
291    globalState.debugAddToGlobalCoinDicts();
292#endif
293    if (!success) {
294        return false;
295    }
296#if DEBUG_ALIGNMENT
297    contourList->dumpSegments("aligned");
298#endif
299    // construct closed contours
300    result->reset();
301    result->setFillType(fillType);
302    SkPathWriter wrapper(*result);
303    if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
304        return false;
305    }
306    wrapper.assemble();  // if some edges could not be resolved, assemble remaining
307#if DEBUG_T_SECT_LOOP_COUNT
308    {
309        SkAutoMutexAcquire autoM(debugWorstLoop);
310        if (!gVerboseFinalize) {
311            gVerboseFinalize = &ReportPathOpsDebugging;
312        }
313        debugWorstState.debugDoYourWorst(&globalState);
314    }
315#endif
316    if (scaleFactor > 1) {
317        ScalePath(*result, scaleFactor, result);
318    }
319    return true;
320}
321
322bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
323#if DEBUG_DUMP_VERIFY
324    if (SkPathOpsDebug::gVerifyOp) {
325        if (!OpDebug(one, two, op, result  SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
326            SkPathOpsDebug::ReportOpFail(one, two, op);
327            return false;
328        }
329        SkPathOpsDebug::VerifyOp(one, two, op, *result);
330        return true;
331    }
332#endif
333    return OpDebug(one, two, op, result  SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
334}
335