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