aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops/SkPathOpsCommon.cpp
blob: 9cdf8124a8e1bcb3fbb49ef445987dd0c43fe9a9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#include "SkAddIntersections.h"
#include "SkOpCoincidence.h"
#include "SkOpEdgeBuilder.h"
#include "SkPathOpsCommon.h"
#include "SkPathWriter.h"
#include "SkTSort.h"

SkScalar ScaleFactor(const SkPath& path) {
    static const SkScalar twoTo10 = 1024.f;
    SkScalar largest = 0;
    const SkScalar* oneBounds = &path.getBounds().fLeft;
    for (int index = 0; index < 4; ++index) {
        largest = SkTMax(largest, SkScalarAbs(oneBounds[index]));
    }
    SkScalar scale = twoTo10;
    SkScalar next;
    while ((next = scale * twoTo10) < largest) {
        scale = next;
    }
    return scale == twoTo10 ? SK_Scalar1 : scale;
}

void ScalePath(const SkPath& path, SkScalar scale, SkPath* scaled) {
    SkMatrix matrix;
    matrix.setScale(scale, scale);
    *scaled = path;
    scaled->transform(matrix);
}

const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
        bool* sortablePtr) {
    // find first angle, initialize winding to computed fWindSum
    SkOpSegment* segment = start->segment();
    const SkOpAngle* angle = segment->spanToAngle(start, end);
    if (!angle) {
        *windingPtr = SK_MinS32;
        return nullptr;
    }
    bool computeWinding = false;
    const SkOpAngle* firstAngle = angle;
    bool loop = false;
    bool unorderable = false;
    int winding = SK_MinS32;
    do {
        angle = angle->next();
        if (!angle) {
            return nullptr;
        }
        unorderable |= angle->unorderable();
        if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
            break;    // if we get here, there's no winding, loop is unorderable
        }
        loop |= angle == firstAngle;
        segment = angle->segment();
        winding = segment->windSum(angle);
    } while (winding == SK_MinS32);
    // if the angle loop contains an unorderable span, the angle order may be useless
    // directly compute the winding in this case for each span
    if (computeWinding) {
        firstAngle = angle;
        winding = SK_MinS32;
        do {
            SkOpSpanBase* startSpan = angle->start();
            SkOpSpanBase* endSpan = angle->end();
            SkOpSpan* lesser = startSpan->starter(endSpan);
            int testWinding = lesser->windSum();
            if (testWinding == SK_MinS32) {
                testWinding = lesser->computeWindSum();
            }
            if (testWinding != SK_MinS32) {
                segment = angle->segment();
                winding = testWinding;
            }
            angle = angle->next();
        } while (angle != firstAngle);
    }
    *sortablePtr = !unorderable;
    *windingPtr = winding;
    return angle;
}

SkOpSpan* FindUndone(SkOpContourHead* contourHead) {
    SkOpContour* contour = contourHead;
    do {
        if (contour->done()) {
            continue;
        }
        SkOpSpan* result = contour->undoneSpan();
        if (result) {
            return result;
        }
    } while ((contour = contour->next()));
    return nullptr;
}

SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
        SkOpSpanBase** endPtr) {
    while (chase->count()) {
        SkOpSpanBase* span;
        chase->pop(&span);
        SkOpSegment* segment = span->segment();
        *startPtr = span->ptT()->next()->span();
        bool done = true;
        *endPtr = nullptr;
        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
            *startPtr = last->start();
            *endPtr = last->end();
    #if TRY_ROTATE
            *chase->insert(0) = span;
    #else
            *chase->append() = span;
    #endif
            return last->segment();
        }
        if (done) {
            continue;
        }
        // find first angle, initialize winding to computed wind sum
        int winding;
        bool sortable;
        const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
        if (!angle) {
            return nullptr;
        }
        if (winding == SK_MinS32) {
            continue;
        }
        int sumWinding SK_INIT_TO_AVOID_WARNING;
        if (sortable) {
            segment = angle->segment();
            sumWinding = segment->updateWindingReverse(angle);
        }
        SkOpSegment* first = nullptr;
        const SkOpAngle* firstAngle = angle;
        while ((angle = angle->next()) != firstAngle) {
            segment = angle->segment();
            SkOpSpanBase* start = angle->start();
            SkOpSpanBase* end = angle->end();
            int maxWinding SK_INIT_TO_AVOID_WARNING;
            if (sortable) {
                segment->setUpWinding(start, end, &maxWinding, &sumWinding);
            }
            if (!segment->done(angle)) {
                if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
                    first = segment;
                    *startPtr = start;
                    *endPtr = end;
                }
                // OPTIMIZATION: should this also add to the chase?
                if (sortable) {
                    (void) segment->markAngle(maxWinding, sumWinding, angle);
                }
            }
        }
        if (first) {
       #if TRY_ROTATE
            *chase->insert(0) = span;
       #else
            *chase->append() = span;
       #endif
            return first;
        }
    }
    return nullptr;
}

bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
    SkTDArray<SkOpContour* > list;
    SkOpContour* contour = *contourList;
    do {
        if (contour->count()) {
            contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
            *list.append() = contour;
        }
    } while ((contour = contour->next()));
    int count = list.count();
    if (!count) {
        return false;
    }
    if (count > 1) {
        SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
    }
    contour = list[0];
    SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
    contour->globalState()->setContourHead(contourHead);
    *contourList = contourHead;
    for (int index = 1; index < count; ++index) {
        SkOpContour* next = list[index];
        contour->setNext(next);
        contour = next;
    }
    contour->setNext(nullptr);
    return true;
}

static void calc_angles(SkOpContourHead* contourList  DEBUG_COIN_DECLARE_PARAMS()) {
    DEBUG_STATIC_SET_PHASE(contourList);
    SkOpContour* contour = contourList;
    do {
        contour->calcAngles();
    } while ((contour = contour->next()));
}

static bool missing_coincidence(SkOpContourHead* contourList  DEBUG_COIN_DECLARE_PARAMS()) {
    DEBUG_STATIC_SET_PHASE(contourList);
    SkOpContour* contour = contourList;
    bool result = false;
    do {
        result |= contour->missingCoincidence();
    } while ((contour = contour->next()));
    return result;
}

static bool move_multiples(SkOpContourHead* contourList  DEBUG_COIN_DECLARE_PARAMS()) {
    DEBUG_STATIC_SET_PHASE(contourList);
    SkOpContour* contour = contourList;
    do {
        if (!contour->moveMultiples()) {
            return false;
        }
    } while ((contour = contour->next()));
    return true;
}

static bool move_nearby(SkOpContourHead* contourList  DEBUG_COIN_DECLARE_PARAMS()) {
    DEBUG_STATIC_SET_PHASE(contourList);
    SkOpContour* contour = contourList;
    do {
        if (!contour->moveNearby()) {
            return false;
        }
    } while ((contour = contour->next()));
    return true;
}

static bool sort_angles(SkOpContourHead* contourList) {
    SkOpContour* contour = contourList;
    do {
        if (!contour->sortAngles()) {
            return false;
        }
    } while ((contour = contour->next()));
    return true;
}

bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) {
    SkOpGlobalState* globalState = contourList->globalState();
    // match up points within the coincident runs
    if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kIntersecting))) {
        return false;
    }
    // combine t values when multiple intersections occur on some segments but not others
    if (!move_multiples(contourList  DEBUG_PHASE_PARAMS(kWalking))) {
        return false;
    }
    // move t values and points together to eliminate small/tiny gaps
    if (!move_nearby(contourList  DEBUG_COIN_PARAMS())) {
        return false;
    }
    // add coincidence formed by pairing on curve points and endpoints
    coincidence->correctEnds(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
    if (!coincidence->addEndMovedSpans(DEBUG_COIN_ONLY_PARAMS())) {
        return false;
    }
    const int SAFETY_COUNT = 3;
    int safetyHatch = SAFETY_COUNT;
    // look for coincidence present in A-B and A-C but missing in B-C
    do {
        bool added;
        if (!coincidence->addMissing(&added  DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
            return false;
        }
        if (!added) {
            break;
        }
        if (!--safetyHatch) {
            SkASSERT(globalState->debugSkipAssert());
            return false;
        }
        move_nearby(contourList  DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch - 1));
    } while (true);
    // check to see if, loosely, coincident ranges may be expanded
    if (coincidence->expand(DEBUG_COIN_ONLY_PARAMS())) {
        bool added;
        if (!coincidence->addMissing(&added  DEBUG_COIN_PARAMS())) {
            return false;
        }
        if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
            return false;
        }
        if (!move_multiples(contourList  DEBUG_COIN_PARAMS())) {
            return false;
        }
        move_nearby(contourList  DEBUG_COIN_PARAMS());
    }
    // the expanded ranges may not align -- add the missing spans
    if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
        return false;
    }
    // mark spans of coincident segments as coincident
    coincidence->mark(DEBUG_COIN_ONLY_PARAMS());
    // look for coincidence lines and curves undetected by intersection
    if (missing_coincidence(contourList  DEBUG_COIN_PARAMS())) {
        (void) coincidence->expand(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
        if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
            return false;
        }
        if (!coincidence->mark(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
            return false;
        }
    } else {
        (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
    }
    (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());

    SkOpCoincidence overlaps(globalState);
    safetyHatch = SAFETY_COUNT;
    do {
        SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
        // adjust the winding value to account for coincident edges
        if (!pairs->apply(DEBUG_ITER_ONLY_PARAMS(SAFETY_COUNT - safetyHatch))) {
            return false;
        } 
        // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
        // are different, construct a new pair to resolve their mutual span
        if (!pairs->findOverlaps(&overlaps  DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
            return false;
        }
        if (!--safetyHatch) {
            SkASSERT(globalState->debugSkipAssert());
            return false;
        }
    } while (!overlaps.isEmpty());
    calc_angles(contourList  DEBUG_COIN_PARAMS());
    if (!sort_angles(contourList)) {
        return false;
    }
#if DEBUG_COINCIDENCE_VERBOSE
    coincidence->debugShowCoincidence();
#endif
#if DEBUG_COINCIDENCE
    coincidence->debugValidate();
#endif
    SkPathOpsDebug::ShowActiveSpans(contourList);
    return true;
}