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 bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple) {
14    bool unsortable = false;
15    do {
16        SkOpSpan* span = FindSortableTop(contourList);
17        if (!span) {
18            break;
19        }
20        SkOpSegment* current = span->segment();
21        SkOpSpanBase* start = span->next();
22        SkOpSpanBase* end = span;
23        SkTDArray<SkOpSpanBase*> chase;
24        do {
25            if (current->activeWinding(start, end)) {
26                do {
27                    if (!unsortable && current->done()) {
28                          break;
29                    }
30                    SkASSERT(unsortable || !current->done());
31                    SkOpSpanBase* nextStart = start;
32                    SkOpSpanBase* nextEnd = end;
33                    SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
34                            &unsortable);
35                    if (!next) {
36                        break;
37                    }
38        #if DEBUG_FLOW
39            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
40                    current->debugID(), start->pt().fX, start->pt().fY,
41                    end->pt().fX, end->pt().fY);
42        #endif
43                    if (!current->addCurveTo(start, end, simple)) {
44                        return false;
45                    }
46                    current = next;
47                    start = nextStart;
48                    end = nextEnd;
49                } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
50                if (current->activeWinding(start, end) && !simple->isClosed()) {
51                    SkOpSpan* spanStart = start->starter(end);
52                    if (!spanStart->done()) {
53                        if (!current->addCurveTo(start, end, simple)) {
54                            return false;
55                        }
56                        current->markDone(spanStart);
57                    }
58                }
59                simple->finishContour();
60            } else {
61                SkOpSpanBase* last = current->markAndChaseDone(start, end);
62                if (last && !last->chased()) {
63                    last->setChased(true);
64                    SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
65                    *chase.append() = last;
66#if DEBUG_WINDING
67                    SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
68                    if (!last->final()) {
69                         SkDebugf(" windSum=%d", last->upCast()->windSum());
70                    }
71                    SkDebugf("\n");
72#endif
73                }
74            }
75            current = FindChase(&chase, &start, &end);
76            SkPathOpsDebug::ShowActiveSpans(contourList);
77            if (!current) {
78                break;
79            }
80        } while (true);
81    } while (true);
82    return true;
83}
84
85// returns true if all edges were processed
86static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple) {
87    bool unsortable = false;
88    do {
89        SkOpSpan* span = FindUndone(contourList);
90        if (!span) {
91            break;
92        }
93        SkOpSegment* current = span->segment();
94        SkOpSpanBase* start = span->next();
95        SkOpSpanBase* end = span;
96        do {
97            if (!unsortable && current->done()) {
98                break;
99            }
100            SkASSERT(unsortable || !current->done());
101            SkOpSpanBase* nextStart = start;
102            SkOpSpanBase* nextEnd = end;
103            SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd,
104                    &unsortable);
105            if (!next) {
106                break;
107            }
108        #if DEBUG_FLOW
109            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
110                    current->debugID(), start->pt().fX, start->pt().fY,
111                    end->pt().fX, end->pt().fY);
112        #endif
113            if (!current->addCurveTo(start, end, simple)) {
114                return false;
115            }
116            current = next;
117            start = nextStart;
118            end = nextEnd;
119        } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
120        if (!simple->isClosed()) {
121            SkOpSpan* spanStart = start->starter(end);
122            if (!spanStart->done()) {
123                if (!current->addCurveTo(start, end, simple)) {
124                    return false;
125                }
126                current->markDone(spanStart);
127            }
128        }
129        simple->finishContour();
130        SkPathOpsDebug::ShowActiveSpans(contourList);
131    } while (true);
132    return true;
133}
134
135// FIXME : add this as a member of SkPath
136bool SimplifyDebug(const SkPath& path, SkPath* result
137        SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
138    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
139    SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
140            : SkPath::kEvenOdd_FillType;
141    if (path.isConvex()) {
142        if (result != &path) {
143            *result = path;
144        }
145        result->setFillType(fillType);
146        return true;
147    }
148    // turn path into list of segments
149    SkSTArenaAlloc<4096> allocator;  // FIXME: constant-ize, tune
150    SkOpContour contour;
151    SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
152    SkOpGlobalState globalState(contourList, &allocator
153            SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
154    SkOpCoincidence coincidence(&globalState);
155#if DEBUG_DUMP_VERIFY
156#ifndef SK_DEBUG
157    const char* testName = "release";
158#endif
159    if (SkPathOpsDebug::gDumpOp) {
160        SkPathOpsDebug::DumpSimplify(path, testName);
161    }
162#endif
163    SkScalar scaleFactor = ScaleFactor(path);
164    SkPath scaledPath;
165    const SkPath* workingPath;
166    if (scaleFactor > SK_Scalar1) {
167        ScalePath(path, 1.f / scaleFactor, &scaledPath);
168        workingPath = &scaledPath;
169    } else {
170        workingPath = &path;
171    }
172#if DEBUG_SORT
173    SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
174#endif
175    SkOpEdgeBuilder builder(*workingPath, contourList, &globalState);
176    if (!builder.finish()) {
177        return false;
178    }
179#if DEBUG_DUMP_SEGMENTS
180    contour.dumpSegments();
181#endif
182    if (!SortContourList(&contourList, false, false)) {
183        result->reset();
184        result->setFillType(fillType);
185        return true;
186    }
187    // find all intersections between segments
188    SkOpContour* current = contourList;
189    do {
190        SkOpContour* next = current;
191        while (AddIntersectTs(current, next, &coincidence)
192                && (next = next->next()));
193    } while ((current = current->next()));
194#if DEBUG_VALIDATE
195    globalState.setPhase(SkOpPhase::kWalking);
196#endif
197    bool success = HandleCoincidence(contourList, &coincidence);
198#if DEBUG_COIN
199    globalState.debugAddToGlobalCoinDicts();
200#endif
201    if (!success) {
202        return false;
203    }
204#if DEBUG_DUMP_ALIGNMENT
205    contour.dumpSegments("aligned");
206#endif
207    // construct closed contours
208    result->reset();
209    result->setFillType(fillType);
210    SkPathWriter wrapper(*result);
211    if (builder.xorMask() == kWinding_PathOpsMask ? !bridgeWinding(contourList, &wrapper)
212            : !bridgeXor(contourList, &wrapper)) {
213        return false;
214    }
215    wrapper.assemble();  // if some edges could not be resolved, assemble remaining
216    if (scaleFactor > 1) {
217        ScalePath(*result, scaleFactor, result);
218    }
219    return true;
220}
221
222bool Simplify(const SkPath& path, SkPath* result) {
223#if DEBUG_DUMP_VERIFY
224    if (SkPathOpsDebug::gVerifyOp) {
225        if (!SimplifyDebug(path, result  SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
226            SkPathOpsDebug::ReportSimplifyFail(path);
227            return false;
228        }
229        SkPathOpsDebug::VerifySimplify(path, *result);
230        return true;
231    }
232#endif
233    return SimplifyDebug(path, result  SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
234}
235