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 8 #include "Simplify.h" 9 10 namespace Op { 11 12 #define INCLUDED_BY_SHAPE_OPS 1 13 14 #include "Simplify.cpp" 15 16 // FIXME: this and find chase should be merge together, along with 17 // other code that walks winding in angles 18 // OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure 19 // so it isn't duplicated by walkers like this one 20 static Segment* findChaseOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd) { 21 while (chase.count()) { 22 Span* span; 23 chase.pop(&span); 24 const Span& backPtr = span->fOther->span(span->fOtherIndex); 25 Segment* segment = backPtr.fOther; 26 nextStart = backPtr.fOtherIndex; 27 SkTDArray<Angle> angles; 28 int done = 0; 29 if (segment->activeAngle(nextStart, done, angles)) { 30 Angle* last = angles.end() - 1; 31 nextStart = last->start(); 32 nextEnd = last->end(); 33 #if TRY_ROTATE 34 *chase.insert(0) = span; 35 #else 36 *chase.append() = span; 37 #endif 38 return last->segment(); 39 } 40 if (done == angles.count()) { 41 continue; 42 } 43 SkTDArray<Angle*> sorted; 44 bool sortable = Segment::SortAngles(angles, sorted); 45 int angleCount = sorted.count(); 46 #if DEBUG_SORT 47 sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0); 48 #endif 49 if (!sortable) { 50 continue; 51 } 52 // find first angle, initialize winding to computed fWindSum 53 int firstIndex = -1; 54 const Angle* angle; 55 do { 56 angle = sorted[++firstIndex]; 57 segment = angle->segment(); 58 } while (segment->windSum(angle) == SK_MinS32); 59 #if DEBUG_SORT 60 segment->debugShowSort(__FUNCTION__, sorted, firstIndex); 61 #endif 62 int sumMiWinding = segment->updateWindingReverse(angle); 63 int sumSuWinding = segment->updateOppWindingReverse(angle); 64 if (segment->operand()) { 65 SkTSwap<int>(sumMiWinding, sumSuWinding); 66 } 67 int nextIndex = firstIndex + 1; 68 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 69 Segment* first = NULL; 70 do { 71 SkASSERT(nextIndex != firstIndex); 72 if (nextIndex == angleCount) { 73 nextIndex = 0; 74 } 75 angle = sorted[nextIndex]; 76 segment = angle->segment(); 77 int start = angle->start(); 78 int end = angle->end(); 79 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 80 segment->setUpWindings(start, end, sumMiWinding, sumSuWinding, 81 maxWinding, sumWinding, oppMaxWinding, oppSumWinding); 82 if (!segment->done(angle)) { 83 if (!first) { 84 first = segment; 85 nextStart = start; 86 nextEnd = end; 87 } 88 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, 89 oppSumWinding, true, angle); 90 } 91 } while (++nextIndex != lastIndex); 92 if (first) { 93 #if TRY_ROTATE 94 *chase.insert(0) = span; 95 #else 96 *chase.append() = span; 97 #endif 98 return first; 99 } 100 } 101 return NULL; 102 } 103 104 /* 105 static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding, 106 bool windingIsOp, ShapeOp op) { 107 bool active = windingIsActive(winding, spanWinding); 108 if (!active) { 109 return false; 110 } 111 if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) { 112 switch (op) { 113 case kIntersect_Op: 114 case kUnion_Op: 115 return true; 116 case kDifference_Op: { 117 int absSpan = abs(spanWinding); 118 int absOpp = abs(oppSpanWinding); 119 return windingIsOp ? absSpan < absOpp : absSpan > absOpp; 120 } 121 case kXor_Op: 122 return spanWinding != oppSpanWinding; 123 default: 124 SkASSERT(0); 125 } 126 } 127 bool opActive = oppWinding != 0; 128 return gOpLookup[op][opActive][windingIsOp]; 129 } 130 */ 131 132 static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, 133 const int xorMask, const int xorOpMask, PathWrapper& simple) { 134 bool firstContour = true; 135 bool unsortable = false; 136 bool topUnsortable = false; 137 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; 138 do { 139 int index, endIndex; 140 bool done; 141 Segment* current = findSortableTop(contourList, firstContour, index, endIndex, topLeft, 142 topUnsortable, done, true); 143 if (!current) { 144 if (topUnsortable || !done) { 145 topUnsortable = false; 146 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); 147 topLeft.fX = topLeft.fY = SK_ScalarMin; 148 continue; 149 } 150 break; 151 } 152 SkTDArray<Span*> chaseArray; 153 do { 154 if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { 155 do { 156 #if DEBUG_ACTIVE_SPANS 157 if (!unsortable && current->done()) { 158 debugShowActiveSpans(contourList); 159 } 160 #endif 161 SkASSERT(unsortable || !current->done()); 162 int nextStart = index; 163 int nextEnd = endIndex; 164 Segment* next = current->findNextOp(chaseArray, nextStart, nextEnd, 165 unsortable, op, xorMask, xorOpMask); 166 if (!next) { 167 if (!unsortable && simple.hasMove() 168 && current->verb() != SkPath::kLine_Verb 169 && !simple.isClosed()) { 170 current->addCurveTo(index, endIndex, simple, true); 171 SkASSERT(simple.isClosed()); 172 } 173 break; 174 } 175 #if DEBUG_FLOW 176 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__, 177 current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY, 178 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY); 179 #endif 180 current->addCurveTo(index, endIndex, simple, true); 181 current = next; 182 index = nextStart; 183 endIndex = nextEnd; 184 } while (!simple.isClosed() && ((!unsortable) 185 || !current->done(SkMin32(index, endIndex)))); 186 if (current->activeWinding(index, endIndex) && !simple.isClosed()) { 187 SkASSERT(unsortable); 188 int min = SkMin32(index, endIndex); 189 if (!current->done(min)) { 190 current->addCurveTo(index, endIndex, simple, true); 191 current->markDoneBinary(min); 192 } 193 } 194 simple.close(); 195 } else { 196 Span* last = current->markAndChaseDoneBinary(index, endIndex); 197 if (last && !last->fLoop) { 198 *chaseArray.append() = last; 199 } 200 } 201 current = findChaseOp(chaseArray, index, endIndex); 202 #if DEBUG_ACTIVE_SPANS 203 debugShowActiveSpans(contourList); 204 #endif 205 if (!current) { 206 break; 207 } 208 } while (true); 209 } while (true); 210 return simple.someAssemblyRequired(); 211 } 212 213 } // end of Op namespace 214 215 216 void operate(const SkPath& one, const SkPath& two, ShapeOp op, SkPath& result) { 217 #if DEBUG_SORT || DEBUG_SWAP_TOP 218 Op::gDebugSortCount = Op::gDebugSortCountDefault; 219 #endif 220 result.reset(); 221 result.setFillType(SkPath::kEvenOdd_FillType); 222 // turn path into list of segments 223 SkTArray<Op::Contour> contours; 224 // FIXME: add self-intersecting cubics' T values to segment 225 Op::EdgeBuilder builder(one, contours); 226 const int xorMask = builder.xorMask(); 227 builder.addOperand(two); 228 builder.finish(); 229 const int xorOpMask = builder.xorMask(); 230 SkTDArray<Op::Contour*> contourList; 231 makeContourList(contours, contourList, xorMask == kEvenOdd_Mask, 232 xorOpMask == kEvenOdd_Mask); 233 Op::Contour** currentPtr = contourList.begin(); 234 if (!currentPtr) { 235 return; 236 } 237 Op::Contour** listEnd = contourList.end(); 238 // find all intersections between segments 239 do { 240 Op::Contour** nextPtr = currentPtr; 241 Op::Contour* current = *currentPtr++; 242 if (current->containsCubics()) { 243 addSelfIntersectTs(current); 244 } 245 Op::Contour* next; 246 do { 247 next = *nextPtr++; 248 } while (addIntersectTs(current, next) && nextPtr != listEnd); 249 } while (currentPtr != listEnd); 250 // eat through coincident edges 251 252 int total = 0; 253 int index; 254 for (index = 0; index < contourList.count(); ++index) { 255 total += contourList[index]->segments().count(); 256 } 257 #if DEBUG_SHOW_WINDING 258 Op::Contour::debugShowWindingValues(contourList); 259 #endif 260 coincidenceCheck(contourList, total); 261 #if DEBUG_SHOW_WINDING 262 Op::Contour::debugShowWindingValues(contourList); 263 #endif 264 fixOtherTIndex(contourList); 265 sortSegments(contourList); 266 #if DEBUG_ACTIVE_SPANS 267 debugShowActiveSpans(contourList); 268 #endif 269 // construct closed contours 270 Op::PathWrapper wrapper(result); 271 bridgeOp(contourList, op, xorMask, xorOpMask, wrapper); 272 { // if some edges could not be resolved, assemble remaining fragments 273 SkPath temp; 274 temp.setFillType(SkPath::kEvenOdd_FillType); 275 Op::PathWrapper assembled(temp); 276 assemble(wrapper, assembled); 277 result = *assembled.nativePath(); 278 } 279 } 280
