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 bool firstPass = true; 17 SkPoint lastTopLeft; 18 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 19 do { 20 int index, endIndex; 21 bool topDone; 22 bool onlyVertical = false; 23 lastTopLeft = topLeft; 24 SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour, 25 &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass); 26 if (!current) { 27 if ((!topUnsortable || firstPass) && !topDone) { 28 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); 29 topLeft.fX = topLeft.fY = SK_ScalarMin; 30 continue; 31 } 32 break; 33 } else if (onlyVertical) { 34 break; 35 } 36 firstPass = !topUnsortable || lastTopLeft != topLeft; 37 SkTDArray<SkOpSpan*> chase; 38 do { 39 if (current->activeWinding(index, endIndex)) { 40 do { 41 if (!unsortable && current->done()) { 42 break; 43 } 44 SkASSERT(unsortable || !current->done()); 45 int nextStart = index; 46 int nextEnd = endIndex; 47 SkOpSegment* next = current->findNextWinding(&chase, &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->fChased && !last->fLoop) { 81 last->fChased = true; 82 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); 83 // assert that last isn't already in array 84 *chase.append() = last; 85 #if DEBUG_WINDING 86 SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, 87 last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum, 88 last->fSmall); 89 #endif 90 } 91 } 92 current = FindChase(&chase, &index, &endIndex); 93 #if DEBUG_ACTIVE_SPANS 94 DebugShowActiveSpans(contourList); 95 #endif 96 if (!current) { 97 break; 98 } 99 } while (true); 100 } while (true); 101 return simple->someAssemblyRequired(); 102 } 103 104 // returns true if all edges were processed 105 static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) { 106 SkOpSegment* current; 107 int start, end; 108 bool unsortable = false; 109 bool closable = true; 110 while ((current = FindUndone(contourList, &start, &end))) { 111 do { 112 #if DEBUG_ACTIVE_SPANS 113 if (!unsortable && current->done()) { 114 DebugShowActiveSpans(contourList); 115 } 116 #endif 117 SkASSERT(unsortable || !current->done()); 118 int nextStart = start; 119 int nextEnd = end; 120 SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable); 121 if (!next) { 122 if (!unsortable && simple->hasMove() 123 && current->verb() != SkPath::kLine_Verb 124 && !simple->isClosed()) { 125 current->addCurveTo(start, end, simple, true); 126 SkASSERT(simple->isClosed()); 127 } 128 break; 129 } 130 #if DEBUG_FLOW 131 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 132 current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY, 133 current->xyAtT(end).fX, current->xyAtT(end).fY); 134 #endif 135 current->addCurveTo(start, end, simple, true); 136 current = next; 137 start = nextStart; 138 end = nextEnd; 139 } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end)))); 140 if (!simple->isClosed()) { 141 SkASSERT(unsortable); 142 int min = SkMin32(start, end); 143 if (!current->done(min)) { 144 current->addCurveTo(start, end, simple, true); 145 current->markDone(min, 1); 146 } 147 closable = false; 148 } 149 simple->close(); 150 #if DEBUG_ACTIVE_SPANS 151 DebugShowActiveSpans(contourList); 152 #endif 153 } 154 return closable; 155 } 156 157 // FIXME : add this as a member of SkPath 158 bool Simplify(const SkPath& path, SkPath* result) { 159 #if DEBUG_SORT || DEBUG_SWAP_TOP 160 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 161 #endif 162 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 163 SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType 164 : SkPath::kEvenOdd_FillType; 165 166 // turn path into list of segments 167 SkTArray<SkOpContour> contours; 168 SkOpEdgeBuilder builder(path, contours); 169 if (!builder.finish()) { 170 return false; 171 } 172 SkTArray<SkOpContour*, true> contourList; 173 MakeContourList(contours, contourList, false, false); 174 SkOpContour** currentPtr = contourList.begin(); 175 result->reset(); 176 result->setFillType(fillType); 177 if (!currentPtr) { 178 return true; 179 } 180 SkOpContour** listEnd = contourList.end(); 181 // find all intersections between segments 182 do { 183 SkOpContour** nextPtr = currentPtr; 184 SkOpContour* current = *currentPtr++; 185 if (current->containsCubics()) { 186 AddSelfIntersectTs(current); 187 } 188 SkOpContour* next; 189 do { 190 next = *nextPtr++; 191 } while (AddIntersectTs(current, next) && nextPtr != listEnd); 192 } while (currentPtr != listEnd); 193 if (!HandleCoincidence(&contourList, 0)) { 194 return false; 195 } 196 // construct closed contours 197 SkPathWriter simple(*result); 198 if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple) 199 : !bridgeXor(contourList, &simple)) 200 { // if some edges could not be resolved, assemble remaining fragments 201 SkPath temp; 202 temp.setFillType(fillType); 203 SkPathWriter assembled(temp); 204 Assemble(simple, &assembled); 205 *result = *assembled.nativePath(); 206 result->setFillType(fillType); 207 } 208 return true; 209 } 210
