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 "SkOpEdgeBuilder.h"
9#include "SkPathOpsCommon.h"
10#include "SkPathWriter.h"
11
12static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) {
13    while (chase.count()) {
14        SkOpSpan* span;
15        chase.pop(&span);
16        const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
17        SkOpSegment* segment = backPtr.fOther;
18        *tIndex = backPtr.fOtherIndex;
19        bool sortable = true;
20        bool done = true;
21        *endIndex = -1;
22        if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
23                &sortable)) {
24            if (last->unorderable()) {
25                continue;
26            }
27            *tIndex = last->start();
28            *endIndex = last->end();
29   #if TRY_ROTATE
30            *chase.insert(0) = span;
31   #else
32            *chase.append() = span;
33   #endif
34            return last->segment();
35        }
36        if (done) {
37            continue;
38        }
39        if (!sortable) {
40            continue;
41        }
42        // find first angle, initialize winding to computed fWindSum
43        const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
44        if (!angle) {
45            continue;
46        }
47        const SkOpAngle* firstAngle = angle;
48        SkDEBUGCODE(bool loop = false);
49        int winding;
50        do {
51            angle = angle->next();
52            SkASSERT(angle != firstAngle || !loop);
53            SkDEBUGCODE(loop |= angle == firstAngle);
54            segment = angle->segment();
55            winding = segment->windSum(angle);
56        } while (winding == SK_MinS32);
57        int sumMiWinding = segment->updateWindingReverse(angle);
58        int sumSuWinding = segment->updateOppWindingReverse(angle);
59        if (segment->operand()) {
60            SkTSwap<int>(sumMiWinding, sumSuWinding);
61        }
62        SkOpSegment* first = NULL;
63        while ((angle = angle->next()) != firstAngle) {
64            segment = angle->segment();
65            int start = angle->start();
66            int end = angle->end();
67            int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
68            segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
69                    &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
70            if (!segment->done(angle)) {
71                if (!first) {
72                    first = segment;
73                    *tIndex = start;
74                    *endIndex = end;
75                }
76                // OPTIMIZATION: should this also add to the chase?
77                (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
78                    oppSumWinding, angle);
79            }
80        }
81        if (first) {
82       #if TRY_ROTATE
83            *chase.insert(0) = span;
84       #else
85            *chase.append() = span;
86       #endif
87            return first;
88        }
89    }
90    return NULL;
91}
92
93/*
94static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
95        bool windingIsOp, PathOp op) {
96    bool active = windingIsActive(winding, spanWinding);
97    if (!active) {
98        return false;
99    }
100    if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
101        switch (op) {
102            case kIntersect_Op:
103            case kUnion_Op:
104                return true;
105            case kDifference_Op: {
106                int absSpan = abs(spanWinding);
107                int absOpp = abs(oppSpanWinding);
108                return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
109            }
110            case kXor_Op:
111                return spanWinding != oppSpanWinding;
112            default:
113                SkASSERT(0);
114        }
115    }
116    bool opActive = oppWinding != 0;
117    return gOpLookup[op][opActive][windingIsOp];
118}
119*/
120
121static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
122        const int xorMask, const int xorOpMask, SkPathWriter* simple) {
123    bool firstContour = true;
124    bool unsortable = false;
125    bool topUnsortable = false;
126    bool firstPass = true;
127    SkPoint lastTopLeft;
128    SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
129    do {
130        int index, endIndex;
131        bool topDone;
132        bool onlyVertical = false;
133        lastTopLeft = topLeft;
134        SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
135                &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
136        if (!current) {
137            if ((!topUnsortable || firstPass) && !topDone) {
138                SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
139                if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) {
140                    if (firstPass) {
141                        firstPass = false;
142                    } else {
143                        break;
144                    }
145                }
146                topLeft.fX = topLeft.fY = SK_ScalarMin;
147                continue;
148            }
149            break;
150        } else if (onlyVertical) {
151            break;
152        }
153        firstPass = !topUnsortable || lastTopLeft != topLeft;
154        SkTDArray<SkOpSpan*> chase;
155        do {
156            if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
157                do {
158                    if (!unsortable && current->done()) {
159                        break;
160                    }
161                    SkASSERT(unsortable || !current->done());
162                    int nextStart = index;
163                    int nextEnd = endIndex;
164                    SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
165                            &unsortable, op, xorMask, xorOpMask);
166                    if (!next) {
167                        if (!unsortable && simple->hasMove()
168                                && current->verb() != SkPath::kLine_Verb
169                                && !simple->isClosed()) {
170                            current->addCurveTo(index, endIndex, simple, true);
171                    #if DEBUG_ACTIVE_SPANS
172                            if (!simple->isClosed()) {
173                                DebugShowActiveSpans(contourList);
174                            }
175                    #endif
176//                            SkASSERT(simple->isClosed());
177                        }
178                        break;
179                    }
180        #if DEBUG_FLOW
181            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
182                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
183                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
184        #endif
185                    current->addCurveTo(index, endIndex, simple, true);
186                    current = next;
187                    index = nextStart;
188                    endIndex = nextEnd;
189                } while (!simple->isClosed() && (!unsortable
190                        || !current->done(SkMin32(index, endIndex))));
191                if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
192                    // FIXME : add to simplify, xor cpaths
193                    int min = SkMin32(index, endIndex);
194                    if (!unsortable && !simple->isEmpty()) {
195                        unsortable = current->checkSmall(min);
196                    }
197                    if (!current->done(min)) {
198                        current->addCurveTo(index, endIndex, simple, true);
199                        current->markDoneBinary(min);
200                    }
201                }
202                simple->close();
203            } else {
204                SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
205                if (last && !last->fChased && !last->fLoop) {
206                    last->fChased = true;
207                    SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
208                    *chase.append() = last;
209#if DEBUG_WINDING
210                    SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
211                            last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
212                            last->fSmall);
213#endif
214                }
215            }
216            current = findChaseOp(chase, &index, &endIndex);
217        #if DEBUG_ACTIVE_SPANS
218            DebugShowActiveSpans(contourList);
219        #endif
220            if (!current) {
221                break;
222            }
223        } while (true);
224    } while (true);
225    return simple->someAssemblyRequired();
226}
227
228// pretty picture:
229// https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
230static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
231//                  inside minuend                               outside minuend
232//     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
233    {{ kDifference_PathOp,    kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
234    {{ kIntersect_PathOp,    kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
235    {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp,    kIntersect_PathOp }},
236    {{ kXOR_PathOp,                 kXOR_PathOp }, { kXOR_PathOp,                 kXOR_PathOp }},
237    {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp,    kDifference_PathOp }},
238};
239
240static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
241    {{ false, false }, { true, false }},  // diff
242    {{ false, false }, { false, true }},  // sect
243    {{ false, true }, { true, true }},    // union
244    {{ false, true }, { true, false }},   // xor
245    {{ false, true }, { false, false }},  // rev diff
246};
247
248bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
249#if DEBUG_SHOW_TEST_NAME
250    char* debugName = DEBUG_FILENAME_STRING;
251    if (debugName && debugName[0]) {
252        SkPathOpsDebug::BumpTestName(debugName);
253        SkPathOpsDebug::ShowPath(one, two, op, debugName);
254    }
255#endif
256    op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
257    SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
258            ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
259    const SkPath* minuend = &one;
260    const SkPath* subtrahend = &two;
261    if (op == kReverseDifference_PathOp) {
262        minuend = &two;
263        subtrahend = &one;
264        op = kDifference_PathOp;
265    }
266#if DEBUG_SORT || DEBUG_SWAP_TOP
267    SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
268#endif
269    // turn path into list of segments
270    SkTArray<SkOpContour> contours;
271    // FIXME: add self-intersecting cubics' T values to segment
272    SkOpEdgeBuilder builder(*minuend, contours);
273    const int xorMask = builder.xorMask();
274    builder.addOperand(*subtrahend);
275    if (!builder.finish()) {
276        return false;
277    }
278    result->reset();
279    result->setFillType(fillType);
280    const int xorOpMask = builder.xorMask();
281    SkTArray<SkOpContour*, true> contourList;
282    MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
283            xorOpMask == kEvenOdd_PathOpsMask);
284    SkOpContour** currentPtr = contourList.begin();
285    if (!currentPtr) {
286        return true;
287    }
288    SkOpContour** listEnd = contourList.end();
289    // find all intersections between segments
290    do {
291        SkOpContour** nextPtr = currentPtr;
292        SkOpContour* current = *currentPtr++;
293        if (current->containsCubics()) {
294            AddSelfIntersectTs(current);
295        }
296        SkOpContour* next;
297        do {
298            next = *nextPtr++;
299        } while (AddIntersectTs(current, next) && nextPtr != listEnd);
300    } while (currentPtr != listEnd);
301    // eat through coincident edges
302
303    int total = 0;
304    int index;
305    for (index = 0; index < contourList.count(); ++index) {
306        total += contourList[index]->segments().count();
307    }
308    if (!HandleCoincidence(&contourList, total)) {
309        return false;
310    }
311    // construct closed contours
312    SkPathWriter wrapper(*result);
313    bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
314    {  // if some edges could not be resolved, assemble remaining fragments
315        SkPath temp;
316        temp.setFillType(fillType);
317        SkPathWriter assembled(temp);
318        Assemble(wrapper, &assembled);
319        *result = *assembled.nativePath();
320        result->setFillType(fillType);
321    }
322    return true;
323}
324