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