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
8#include "Simplify.h"
9
10namespace Op {
11
12#define INCLUDED_BY_SHAPE_OPS 1
13
14#include "Simplify.cpp"
15
16// FIXME: this and find chase should be merge together, along with
17// other code that walks winding in angles
18// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure
19// so it isn't duplicated by walkers like this one
20static Segment* findChaseOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd) {
21    while (chase.count()) {
22        Span* span;
23        chase.pop(&span);
24        const Span& backPtr = span->fOther->span(span->fOtherIndex);
25        Segment* segment = backPtr.fOther;
26        nextStart = backPtr.fOtherIndex;
27        SkTDArray<Angle> angles;
28        int done = 0;
29        if (segment->activeAngle(nextStart, done, angles)) {
30            Angle* last = angles.end() - 1;
31            nextStart = last->start();
32            nextEnd = last->end();
33   #if TRY_ROTATE
34            *chase.insert(0) = span;
35   #else
36            *chase.append() = span;
37   #endif
38            return last->segment();
39        }
40        if (done == angles.count()) {
41            continue;
42        }
43        SkTDArray<Angle*> sorted;
44        bool sortable = Segment::SortAngles(angles, sorted);
45        int angleCount = sorted.count();
46#if DEBUG_SORT
47        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0);
48#endif
49        if (!sortable) {
50            continue;
51        }
52        // find first angle, initialize winding to computed fWindSum
53        int firstIndex = -1;
54        const Angle* angle;
55        do {
56            angle = sorted[++firstIndex];
57            segment = angle->segment();
58        } while (segment->windSum(angle) == SK_MinS32);
59    #if DEBUG_SORT
60        segment->debugShowSort(__FUNCTION__, sorted, firstIndex);
61    #endif
62        int sumMiWinding = segment->updateWindingReverse(angle);
63        int sumSuWinding = segment->updateOppWindingReverse(angle);
64        if (segment->operand()) {
65            SkTSwap<int>(sumMiWinding, sumSuWinding);
66        }
67        int nextIndex = firstIndex + 1;
68        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
69        Segment* first = NULL;
70        do {
71            SkASSERT(nextIndex != firstIndex);
72            if (nextIndex == angleCount) {
73                nextIndex = 0;
74            }
75            angle = sorted[nextIndex];
76            segment = angle->segment();
77            int start = angle->start();
78            int end = angle->end();
79            int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
80            segment->setUpWindings(start, end, sumMiWinding, sumSuWinding,
81                    maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
82            if (!segment->done(angle)) {
83                if (!first) {
84                    first = segment;
85                    nextStart = start;
86                    nextEnd = end;
87                }
88                (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
89                    oppSumWinding, true, angle);
90            }
91        } while (++nextIndex != lastIndex);
92        if (first) {
93       #if TRY_ROTATE
94            *chase.insert(0) = span;
95       #else
96            *chase.append() = span;
97       #endif
98            return first;
99        }
100    }
101    return NULL;
102}
103
104/*
105static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
106        bool windingIsOp, ShapeOp op) {
107    bool active = windingIsActive(winding, spanWinding);
108    if (!active) {
109        return false;
110    }
111    if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
112        switch (op) {
113            case kIntersect_Op:
114            case kUnion_Op:
115                return true;
116            case kDifference_Op: {
117                int absSpan = abs(spanWinding);
118                int absOpp = abs(oppSpanWinding);
119                return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
120            }
121            case kXor_Op:
122                return spanWinding != oppSpanWinding;
123            default:
124                SkASSERT(0);
125        }
126    }
127    bool opActive = oppWinding != 0;
128    return gOpLookup[op][opActive][windingIsOp];
129}
130*/
131
132static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
133        const int xorMask, const int xorOpMask, PathWrapper& simple) {
134    bool firstContour = true;
135    bool unsortable = false;
136    bool topUnsortable = false;
137    SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
138    do {
139        int index, endIndex;
140        bool done;
141        Segment* current = findSortableTop(contourList, firstContour, index, endIndex, topLeft,
142                topUnsortable, done, true);
143        if (!current) {
144            if (topUnsortable || !done) {
145                topUnsortable = false;
146                SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
147                topLeft.fX = topLeft.fY = SK_ScalarMin;
148                continue;
149            }
150            break;
151        }
152        SkTDArray<Span*> chaseArray;
153        do {
154            if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
155                do {
156            #if DEBUG_ACTIVE_SPANS
157                    if (!unsortable && current->done()) {
158                        debugShowActiveSpans(contourList);
159                    }
160            #endif
161                    SkASSERT(unsortable || !current->done());
162                    int nextStart = index;
163                    int nextEnd = endIndex;
164                    Segment* next = current->findNextOp(chaseArray, 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                            SkASSERT(simple.isClosed());
172                        }
173                        break;
174                    }
175        #if DEBUG_FLOW
176            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
177                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
178                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
179        #endif
180                    current->addCurveTo(index, endIndex, simple, true);
181                    current = next;
182                    index = nextStart;
183                    endIndex = nextEnd;
184                } while (!simple.isClosed() && ((!unsortable)
185                        || !current->done(SkMin32(index, endIndex))));
186                if (current->activeWinding(index, endIndex) && !simple.isClosed()) {
187                    SkASSERT(unsortable);
188                    int min = SkMin32(index, endIndex);
189                    if (!current->done(min)) {
190                        current->addCurveTo(index, endIndex, simple, true);
191                        current->markDoneBinary(min);
192                    }
193                }
194                simple.close();
195            } else {
196                Span* last = current->markAndChaseDoneBinary(index, endIndex);
197                if (last && !last->fLoop) {
198                    *chaseArray.append() = last;
199                }
200            }
201            current = findChaseOp(chaseArray, index, endIndex);
202        #if DEBUG_ACTIVE_SPANS
203            debugShowActiveSpans(contourList);
204        #endif
205            if (!current) {
206                break;
207            }
208        } while (true);
209    } while (true);
210    return simple.someAssemblyRequired();
211}
212
213} // end of Op namespace
214
215
216void operate(const SkPath& one, const SkPath& two, ShapeOp op, SkPath& result) {
217#if DEBUG_SORT || DEBUG_SWAP_TOP
218    Op::gDebugSortCount = Op::gDebugSortCountDefault;
219#endif
220    result.reset();
221    result.setFillType(SkPath::kEvenOdd_FillType);
222    // turn path into list of segments
223    SkTArray<Op::Contour> contours;
224    // FIXME: add self-intersecting cubics' T values to segment
225    Op::EdgeBuilder builder(one, contours);
226    const int xorMask = builder.xorMask();
227    builder.addOperand(two);
228    builder.finish();
229    const int xorOpMask = builder.xorMask();
230    SkTDArray<Op::Contour*> contourList;
231    makeContourList(contours, contourList, xorMask == kEvenOdd_Mask,
232            xorOpMask == kEvenOdd_Mask);
233    Op::Contour** currentPtr = contourList.begin();
234    if (!currentPtr) {
235        return;
236    }
237    Op::Contour** listEnd = contourList.end();
238    // find all intersections between segments
239    do {
240        Op::Contour** nextPtr = currentPtr;
241        Op::Contour* current = *currentPtr++;
242        if (current->containsCubics()) {
243            addSelfIntersectTs(current);
244        }
245        Op::Contour* next;
246        do {
247            next = *nextPtr++;
248        } while (addIntersectTs(current, next) && nextPtr != listEnd);
249    } while (currentPtr != listEnd);
250    // eat through coincident edges
251
252    int total = 0;
253    int index;
254    for (index = 0; index < contourList.count(); ++index) {
255        total += contourList[index]->segments().count();
256    }
257#if DEBUG_SHOW_WINDING
258    Op::Contour::debugShowWindingValues(contourList);
259#endif
260    coincidenceCheck(contourList, total);
261#if DEBUG_SHOW_WINDING
262    Op::Contour::debugShowWindingValues(contourList);
263#endif
264    fixOtherTIndex(contourList);
265    sortSegments(contourList);
266#if DEBUG_ACTIVE_SPANS
267    debugShowActiveSpans(contourList);
268#endif
269    // construct closed contours
270    Op::PathWrapper wrapper(result);
271    bridgeOp(contourList, op, xorMask, xorOpMask, wrapper);
272    { // if some edges could not be resolved, assemble remaining fragments
273        SkPath temp;
274        temp.setFillType(SkPath::kEvenOdd_FillType);
275        Op::PathWrapper assembled(temp);
276        assemble(wrapper, assembled);
277        result = *assembled.nativePath();
278    }
279}
280