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