caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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" |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 8 | #include "SkOpCoincidence.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 9 | #include "SkOpEdgeBuilder.h" |
| 10 | #include "SkPathOpsCommon.h" |
| 11 | #include "SkPathWriter.h" |
| 12 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 13 | static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 14 | SkChunkAlloc* allocator) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 15 | bool unsortable = false; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 16 | do { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 17 | SkOpSpan* span = FindSortableTop(contourList); |
| 18 | if (!span) { |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 19 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 20 | } |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 21 | SkOpSegment* current = span->segment(); |
| 22 | SkOpSpanBase* start = span->next(); |
| 23 | SkOpSpanBase* end = span; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 24 | SkTDArray<SkOpSpanBase*> chase; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 25 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 26 | if (current->activeWinding(start, end)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 27 | do { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 28 | if (!unsortable && current->done()) { |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 29 | break; |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 30 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 31 | SkASSERT(unsortable || !current->done()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 32 | SkOpSpanBase* nextStart = start; |
| 33 | SkOpSpanBase* nextEnd = end; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 34 | SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd, |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 35 | &unsortable); |
| 36 | if (!next) { |
| 37 | if (!unsortable && simple->hasMove() |
| 38 | && current->verb() != SkPath::kLine_Verb |
| 39 | && !simple->isClosed()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 40 | current->addCurveTo(start, end, simple, true); |
| 41 | #if DEBUG_ACTIVE_SPANS |
| 42 | if (!simple->isClosed()) { |
| 43 | DebugShowActiveSpans(contourList); |
| 44 | } |
| 45 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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__, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 51 | current->debugID(), start->pt().fX, start->pt().fY, |
| 52 | end->pt().fX, end->pt().fY); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 53 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 54 | current->addCurveTo(start, end, simple, true); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 55 | current = next; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 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); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 64 | } |
| 65 | } |
| 66 | simple->close(); |
| 67 | } else { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 68 | SkOpSpanBase* last = current->markAndChaseDone(start, end); |
| 69 | if (last && !last->chased()) { |
| 70 | last->setChased(true); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 71 | SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 72 | *chase.append() = last; |
| 73 | #if DEBUG_WINDING |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 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"); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 79 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 80 | } |
| 81 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 82 | current = FindChase(&chase, &start, &end); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 95 | static bool bridgeXor(SkOpContourHead* contourList, SkPathWriter* simple, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 96 | SkChunkAlloc* allocator) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 97 | SkOpSegment* current; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 98 | SkOpSpanBase* start; |
| 99 | SkOpSpanBase* end; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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()); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 110 | SkOpSpanBase* nextStart = start; |
| 111 | SkOpSpanBase* nextEnd = end; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 118 | #if DEBUG_ACTIVE_SPANS |
| 119 | if (!simple->isClosed()) { |
| 120 | DebugShowActiveSpans(contourList); |
| 121 | } |
| 122 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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__, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 128 | current->debugID(), start->pt().fX, start->pt().fY, |
| 129 | end->pt().fX, end->pt().fY); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 130 | #endif |
| 131 | current->addCurveTo(start, end, simple, true); |
| 132 | current = next; |
| 133 | start = nextStart; |
| 134 | end = nextEnd; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 135 | } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done())); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 136 | if (!simple->isClosed()) { |
| 137 | SkASSERT(unsortable); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 138 | SkOpSpan* spanStart = start->starter(end); |
| 139 | if (!spanStart->done()) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 140 | current->addCurveTo(start, end, simple, true); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 141 | current->markDone(spanStart); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 154 | bool Simplify(const SkPath& path, SkPath* result) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 155 | SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 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; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 159 | if (path.isConvex()) { |
| 160 | if (result != &path) { |
| 161 | *result = path; |
| 162 | } |
| 163 | result->setFillType(fillType); |
| 164 | return true; |
| 165 | } |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 166 | // turn path into list of segments |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 167 | SkOpCoincidence coincidence; |
| 168 | SkOpContour contour; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 169 | SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 170 | SkOpGlobalState globalState(&coincidence, contourList SkDEBUGPARAMS(nullptr)); |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 171 | #if DEBUG_SORT |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 172 | SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; |
| 173 | #endif |
| 174 | SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); |
| 175 | if (!builder.finish(&allocator)) { |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 176 | return false; |
| 177 | } |
caryclark | 03b03ca | 2015-04-23 09:13:37 -0700 | [diff] [blame] | 178 | #if DEBUG_DUMP_SEGMENTS |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame^] | 179 | contour.dumpSegments(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 180 | #endif |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 181 | if (!SortContourList(&contourList, false, false)) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 182 | result->reset(); |
| 183 | result->setFillType(fillType); |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 184 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 185 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 186 | // find all intersections between segments |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 187 | SkOpContour* current = contourList; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 188 | do { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 189 | SkOpContour* next = current; |
| 190 | while (AddIntersectTs(current, next, &coincidence, &allocator) |
| 191 | && (next = next->next())); |
| 192 | } while ((current = current->next())); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 193 | #if DEBUG_VALIDATE |
| 194 | globalState.setPhase(SkOpGlobalState::kWalking); |
| 195 | #endif |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 196 | if (!HandleCoincidence(contourList, &coincidence, &allocator)) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 197 | return false; |
| 198 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame^] | 199 | #if DEBUG_DUMP_ALIGNMENT |
| 200 | contour.dumpSegments("aligned"); |
| 201 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 202 | // construct closed contours |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 203 | result->reset(); |
| 204 | result->setFillType(fillType); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 205 | SkPathWriter wrapper(*result); |
| 206 | if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &wrapper, &allocator) |
| 207 | : !bridgeXor(contourList, &wrapper, &allocator)) |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 208 | { // if some edges could not be resolved, assemble remaining fragments |
| 209 | SkPath temp; |
caryclark@google.com | 7dfbb07 | 2013-04-22 14:37:05 +0000 | [diff] [blame] | 210 | temp.setFillType(fillType); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 211 | SkPathWriter assembled(temp); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 212 | Assemble(wrapper, &assembled); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 213 | *result = *assembled.nativePath(); |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 214 | result->setFillType(fillType); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 215 | } |
caryclark@google.com | 66560ca | 2013-04-26 19:51:16 +0000 | [diff] [blame] | 216 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 217 | } |
caryclark | 5b5ddd7 | 2015-05-18 05:12:56 -0700 | [diff] [blame] | 218 | |