SkPathOpsSimplify.cpp revision 07393cab57ce74a4aae89a31fae9aaa9780fc19d 
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(SkTDArray<SkOpContour*>& 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, &firstContour, &index, &endIndex,
21                &topLeft, &topUnsortable, &topDone, false);
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 DEBUG_ACTIVE_SPANS
36                    if (!unsortable && current->done()) {
37                        DebugShowActiveSpans(contourList);
38                    }
39            #endif
40                    SkASSERT(unsortable || !current->done());
41                    int nextStart = index;
42                    int nextEnd = endIndex;
43                    SkOpSegment* next = current->findNextWinding(&chaseArray, &nextStart, &nextEnd,
44                            &unsortable);
45                    if (!next) {
46                        if (!unsortable && simple->hasMove()
47                                && current->verb() != SkPath::kLine_Verb
48                                && !simple->isClosed()) {
49                            current->addCurveTo(index, endIndex, simple, true);
50                            SkASSERT(simple->isClosed());
51                        }
52                        break;
53                    }
54        #if DEBUG_FLOW
55            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
56                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
57                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
58        #endif
59                    current->addCurveTo(index, endIndex, simple, true);
60                    current = next;
61                    index = nextStart;
62                    endIndex = nextEnd;
63                } while (!simple->isClosed() && (!unsortable
64                        || !current->done(SkMin32(index, endIndex))));
65                if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
66                    SkASSERT(unsortable);
67                    int min = SkMin32(index, endIndex);
68                    if (!current->done(min)) {
69                        current->addCurveTo(index, endIndex, simple, true);
70                        current->markDoneUnary(min);
71                    }
72                }
73                simple->close();
74            } else {
75                SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
76                if (last && !last->fLoop) {
77                    *chaseArray.append() = last;
78                }
79            }
80            current = FindChase(chaseArray, index, endIndex);
81        #if DEBUG_ACTIVE_SPANS
82            DebugShowActiveSpans(contourList);
83        #endif
84            if (!current) {
85                break;
86            }
87        } while (true);
88    } while (true);
89    return simple->someAssemblyRequired();
90}
91
92// returns true if all edges were processed
93static bool bridgeXor(SkTDArray<SkOpContour*>& contourList, SkPathWriter* simple) {
94    SkOpSegment* current;
95    int start, end;
96    bool unsortable = false;
97    bool closable = true;
98    while ((current = FindUndone(contourList, &start, &end))) {
99        do {
100    #if DEBUG_ACTIVE_SPANS
101            if (!unsortable && current->done()) {
102                DebugShowActiveSpans(contourList);
103            }
104    #endif
105            SkASSERT(unsortable || !current->done());
106            int nextStart = start;
107            int nextEnd = end;
108            SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
109            if (!next) {
110                if (!unsortable && simple->hasMove()
111                        && current->verb() != SkPath::kLine_Verb
112                        && !simple->isClosed()) {
113                    current->addCurveTo(start, end, simple, true);
114                    SkASSERT(simple->isClosed());
115                }
116                break;
117            }
118        #if DEBUG_FLOW
119            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
120                    current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
121                    current->xyAtT(end).fX, current->xyAtT(end).fY);
122        #endif
123            current->addCurveTo(start, end, simple, true);
124            current = next;
125            start = nextStart;
126            end = nextEnd;
127        } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
128        if (!simple->isClosed()) {
129            SkASSERT(unsortable);
130            int min = SkMin32(start, end);
131            if (!current->done(min)) {
132                current->addCurveTo(start, end, simple, true);
133                current->markDone(min, 1);
134            }
135            closable = false;
136        }
137        simple->close();
138    #if DEBUG_ACTIVE_SPANS
139        DebugShowActiveSpans(contourList);
140    #endif
141    }
142    return closable;
143}
144
145// FIXME : add this as a member of SkPath
146void Simplify(const SkPath& path, SkPath* result) {
147#if DEBUG_SORT || DEBUG_SWAP_TOP
148    gDebugSortCount = gDebugSortCountDefault;
149#endif
150    // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
151    result->reset();
152    result->setFillType(SkPath::kEvenOdd_FillType);
153    SkPathWriter simple(*result);
154
155    // turn path into list of segments
156    SkTArray<SkOpContour> contours;
157    SkOpEdgeBuilder builder(path, contours);
158    builder.finish();
159    SkTDArray<SkOpContour*> contourList;
160    MakeContourList(contours, contourList, false, false);
161    SkOpContour** currentPtr = contourList.begin();
162    if (!currentPtr) {
163        return;
164    }
165    SkOpContour** listEnd = contourList.end();
166    // find all intersections between segments
167    do {
168        SkOpContour** nextPtr = currentPtr;
169        SkOpContour* current = *currentPtr++;
170        if (current->containsCubics()) {
171            AddSelfIntersectTs(current);
172        }
173        SkOpContour* next;
174        do {
175            next = *nextPtr++;
176        } while (AddIntersectTs(current, next) && nextPtr != listEnd);
177    } while (currentPtr != listEnd);
178    // eat through coincident edges
179    CoincidenceCheck(&contourList, 0);
180    FixOtherTIndex(&contourList);
181    SortSegments(&contourList);
182#if DEBUG_ACTIVE_SPANS
183    DebugShowActiveSpans(contourList);
184#endif
185    // construct closed contours
186    if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
187                : !bridgeXor(contourList, &simple))
188    {  // if some edges could not be resolved, assemble remaining fragments
189        SkPath temp;
190        temp.setFillType(SkPath::kEvenOdd_FillType);
191        SkPathWriter assembled(temp);
192        Assemble(simple, &assembled);
193        *result = *assembled.nativePath();
194    }
195}
196