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 bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
13    bool firstContour = true;
14    bool unsortable = false;
15    bool topUnsortable = false;
16    bool firstPass = true;
17    SkPoint lastTopLeft;
18    SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
19    do {
20        int index, endIndex;
21        bool topDone;
22        bool onlyVertical = false;
23        lastTopLeft = topLeft;
24        SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
25                &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
26        if (!current) {
27            if ((!topUnsortable || firstPass) && !topDone) {
28                SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
29                topLeft.fX = topLeft.fY = SK_ScalarMin;
30                continue;
31            }
32            break;
33        } else if (onlyVertical) {
34            break;
35        }
36        firstPass = !topUnsortable || lastTopLeft != topLeft;
37        SkTDArray<SkOpSpan*> chase;
38        do {
39            if (current->activeWinding(index, endIndex)) {
40                do {
41                    if (!unsortable && current->done()) {
42                          break;
43                    }
44                    SkASSERT(unsortable || !current->done());
45                    int nextStart = index;
46                    int nextEnd = endIndex;
47                    SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
48                            &unsortable);
49                    if (!next) {
50                        if (!unsortable && simple->hasMove()
51                                && current->verb() != SkPath::kLine_Verb
52                                && !simple->isClosed()) {
53                            current->addCurveTo(index, endIndex, simple, true);
54                            SkASSERT(simple->isClosed());
55                        }
56                        break;
57                    }
58        #if DEBUG_FLOW
59            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
60                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
61                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
62        #endif
63                    current->addCurveTo(index, endIndex, simple, true);
64                    current = next;
65                    index = nextStart;
66                    endIndex = nextEnd;
67                } while (!simple->isClosed() && (!unsortable
68                        || !current->done(SkMin32(index, endIndex))));
69                if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
70//                    SkASSERT(unsortable || simple->isEmpty());
71                    int min = SkMin32(index, endIndex);
72                    if (!current->done(min)) {
73                        current->addCurveTo(index, endIndex, simple, true);
74                        current->markDoneUnary(min);
75                    }
76                }
77                simple->close();
78            } else {
79                SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
80                if (last && !last->fChased && !last->fLoop) {
81                    last->fChased = true;
82                    SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
83                    // assert that last isn't already in array
84                    *chase.append() = last;
85#if DEBUG_WINDING
86                    SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
87                            last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
88                            last->fSmall);
89#endif
90                }
91            }
92            current = FindChase(&chase, &index, &endIndex);
93        #if DEBUG_ACTIVE_SPANS
94            DebugShowActiveSpans(contourList);
95        #endif
96            if (!current) {
97                break;
98            }
99        } while (true);
100    } while (true);
101    return simple->someAssemblyRequired();
102}
103
104// returns true if all edges were processed
105static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
106    SkOpSegment* current;
107    int start, end;
108    bool unsortable = false;
109    bool closable = true;
110    while ((current = FindUndone(contourList, &start, &end))) {
111        do {
112    #if DEBUG_ACTIVE_SPANS
113            if (!unsortable && current->done()) {
114                DebugShowActiveSpans(contourList);
115            }
116    #endif
117            SkASSERT(unsortable || !current->done());
118            int nextStart = start;
119            int nextEnd = end;
120            SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
121            if (!next) {
122                if (!unsortable && simple->hasMove()
123                        && current->verb() != SkPath::kLine_Verb
124                        && !simple->isClosed()) {
125                    current->addCurveTo(start, end, simple, true);
126                    SkASSERT(simple->isClosed());
127                }
128                break;
129            }
130        #if DEBUG_FLOW
131            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
132                    current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
133                    current->xyAtT(end).fX, current->xyAtT(end).fY);
134        #endif
135            current->addCurveTo(start, end, simple, true);
136            current = next;
137            start = nextStart;
138            end = nextEnd;
139        } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
140        if (!simple->isClosed()) {
141            SkASSERT(unsortable);
142            int min = SkMin32(start, end);
143            if (!current->done(min)) {
144                current->addCurveTo(start, end, simple, true);
145                current->markDone(min, 1);
146            }
147            closable = false;
148        }
149        simple->close();
150    #if DEBUG_ACTIVE_SPANS
151        DebugShowActiveSpans(contourList);
152    #endif
153    }
154    return closable;
155}
156
157// FIXME : add this as a member of SkPath
158bool Simplify(const SkPath& path, SkPath* result) {
159#if DEBUG_SORT || DEBUG_SWAP_TOP
160    SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
161#endif
162    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
163    SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
164            : SkPath::kEvenOdd_FillType;
165
166    // turn path into list of segments
167    SkTArray<SkOpContour> contours;
168    SkOpEdgeBuilder builder(path, contours);
169    if (!builder.finish()) {
170        return false;
171    }
172    SkTArray<SkOpContour*, true> contourList;
173    MakeContourList(contours, contourList, false, false);
174    SkOpContour** currentPtr = contourList.begin();
175    result->reset();
176    result->setFillType(fillType);
177    if (!currentPtr) {
178        return true;
179    }
180    SkOpContour** listEnd = contourList.end();
181    // find all intersections between segments
182    do {
183        SkOpContour** nextPtr = currentPtr;
184        SkOpContour* current = *currentPtr++;
185        if (current->containsCubics()) {
186            AddSelfIntersectTs(current);
187        }
188        SkOpContour* next;
189        do {
190            next = *nextPtr++;
191        } while (AddIntersectTs(current, next) && nextPtr != listEnd);
192    } while (currentPtr != listEnd);
193    if (!HandleCoincidence(&contourList, 0)) {
194        return false;
195    }
196    // construct closed contours
197    SkPathWriter simple(*result);
198    if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
199                : !bridgeXor(contourList, &simple))
200    {  // if some edges could not be resolved, assemble remaining fragments
201        SkPath temp;
202        temp.setFillType(fillType);
203        SkPathWriter assembled(temp);
204        Assemble(simple, &assembled);
205        *result = *assembled.nativePath();
206        result->setFillType(fillType);
207    }
208    return true;
209}
210