1/*
2 * Copyright 2014 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
8#include "SkArenaAlloc.h"
9#include "SkMatrix.h"
10#include "SkOpEdgeBuilder.h"
11#include "SkPathPriv.h"
12#include "SkPathOps.h"
13#include "SkPathOpsCommon.h"
14
15static bool one_contour(const SkPath& path) {
16    char storage[256];
17    SkArenaAlloc allocator(storage);
18    int verbCount = path.countVerbs();
19    uint8_t* verbs = (uint8_t*) allocator.makeArrayDefault<uint8_t>(verbCount);
20    (void) path.getVerbs(verbs, verbCount);
21    for (int index = 1; index < verbCount; ++index) {
22        if (verbs[index] == SkPath::kMove_Verb) {
23            return false;
24        }
25    }
26    return true;
27}
28
29void SkOpBuilder::ReversePath(SkPath* path) {
30    SkPath temp;
31    SkPoint lastPt;
32    SkAssertResult(path->getLastPt(&lastPt));
33    temp.moveTo(lastPt);
34    temp.reversePathTo(*path);
35    temp.close();
36    *path = temp;
37}
38
39bool SkOpBuilder::FixWinding(SkPath* path) {
40    SkPath::FillType fillType = path->getFillType();
41    if (fillType == SkPath::kInverseEvenOdd_FillType) {
42        fillType = SkPath::kInverseWinding_FillType;
43    } else if (fillType == SkPath::kEvenOdd_FillType) {
44        fillType = SkPath::kWinding_FillType;
45    }
46    SkPathPriv::FirstDirection dir;
47    if (one_contour(*path) && SkPathPriv::CheapComputeFirstDirection(*path, &dir)) {
48        if (dir != SkPathPriv::kCCW_FirstDirection) {
49            ReversePath(path);
50        }
51        path->setFillType(fillType);
52        return true;
53    }
54    char storage[4096];
55    SkArenaAlloc allocator(storage);
56    SkOpContourHead contourHead;
57    SkOpGlobalState globalState(&contourHead, &allocator  SkDEBUGPARAMS(false)
58            SkDEBUGPARAMS(nullptr));
59    SkOpEdgeBuilder builder(*path, &contourHead, &globalState);
60    if (builder.unparseable() || !builder.finish()) {
61        return false;
62    }
63    if (!contourHead.count()) {
64        return true;
65    }
66    if (!contourHead.next()) {
67        return false;
68    }
69    contourHead.joinAllSegments();
70    contourHead.resetReverse();
71    bool writePath = false;
72    SkOpSpan* topSpan;
73    globalState.setPhase(SkOpPhase::kFixWinding);
74    while ((topSpan = FindSortableTop(&contourHead))) {
75        SkOpSegment* topSegment = topSpan->segment();
76        SkOpContour* topContour = topSegment->contour();
77        SkASSERT(topContour->isCcw() >= 0);
78#if DEBUG_WINDING
79        SkDebugf("%s id=%d nested=%d ccw=%d\n",  __FUNCTION__,
80                topSegment->debugID(), globalState.nested(), topContour->isCcw());
81#endif
82        if ((globalState.nested() & 1) != SkToBool(topContour->isCcw())) {
83            topContour->setReverse();
84            writePath = true;
85        }
86        topContour->markAllDone();
87        globalState.clearNested();
88    }
89    if (!writePath) {
90        path->setFillType(fillType);
91        return true;
92    }
93    SkPath empty;
94    SkPathWriter woundPath(empty);
95    SkOpContour* test = &contourHead;
96    do {
97        if (!test->count()) {
98            continue;
99        }
100        if (test->reversed()) {
101            test->toReversePath(&woundPath);
102        } else {
103            test->toPath(&woundPath);
104        }
105    } while ((test = test->next()));
106    *path = *woundPath.nativePath();
107    path->setFillType(fillType);
108    return true;
109}
110
111void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
112    if (0 == fOps.count() && op != kUnion_SkPathOp) {
113        fPathRefs.push_back() = SkPath();
114        *fOps.append() = kUnion_SkPathOp;
115    }
116    fPathRefs.push_back() = path;
117    *fOps.append() = op;
118}
119
120void SkOpBuilder::reset() {
121    fPathRefs.reset();
122    fOps.reset();
123}
124
125/* OPTIMIZATION: Union doesn't need to be all-or-nothing. A run of three or more convex
126   paths with union ops could be locally resolved and still improve over doing the
127   ops one at a time. */
128bool SkOpBuilder::resolve(SkPath* result) {
129    SkPath original = *result;
130    int count = fOps.count();
131    bool allUnion = true;
132    SkPathPriv::FirstDirection firstDir = SkPathPriv::kUnknown_FirstDirection;
133    for (int index = 0; index < count; ++index) {
134        SkPath* test = &fPathRefs[index];
135        if (kUnion_SkPathOp != fOps[index] || test->isInverseFillType()) {
136            allUnion = false;
137            break;
138        }
139        // If all paths are convex, track direction, reversing as needed.
140        if (test->isConvex()) {
141            SkPathPriv::FirstDirection dir;
142            if (!SkPathPriv::CheapComputeFirstDirection(*test, &dir)) {
143                allUnion = false;
144                break;
145            }
146            if (firstDir == SkPathPriv::kUnknown_FirstDirection) {
147                firstDir = dir;
148            } else if (firstDir != dir) {
149                ReversePath(test);
150            }
151            continue;
152        }
153        // If the path is not convex but its bounds do not intersect the others, simplify is enough.
154        const SkRect& testBounds = test->getBounds();
155        for (int inner = 0; inner < index; ++inner) {
156            // OPTIMIZE: check to see if the contour bounds do not intersect other contour bounds?
157            if (SkRect::Intersects(fPathRefs[inner].getBounds(), testBounds)) {
158                allUnion = false;
159                break;
160            }
161        }
162    }
163    if (!allUnion) {
164        *result = fPathRefs[0];
165        for (int index = 1; index < count; ++index) {
166            if (!Op(*result, fPathRefs[index], fOps[index], result)) {
167                reset();
168                *result = original;
169                return false;
170            }
171        }
172        reset();
173        return true;
174    }
175    SkPath sum;
176    for (int index = 0; index < count; ++index) {
177        if (!Simplify(fPathRefs[index], &fPathRefs[index])) {
178            reset();
179            *result = original;
180            return false;
181        }
182        if (!fPathRefs[index].isEmpty()) {
183            // convert the even odd result back to winding form before accumulating it
184            if (!FixWinding(&fPathRefs[index])) {
185                *result = original;
186                return false;
187            }
188            sum.addPath(fPathRefs[index]);
189        }
190    }
191    reset();
192    bool success = Simplify(sum, result);
193    if (!success) {
194        *result = original;
195    }
196    return success;
197}
198