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