| OLD | NEW |
|---|
| (Empty) |
| 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 st
ructure | |
| 19 // so it isn't duplicated by walkers like this one | |
| 20 static Segment* findChaseOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEn
d) { | |
| 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 op
pSpanWinding, | |
| 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, end
Index, topLeft, | |
| 142 topUnsortable, done, true); | |
| 143 if (!current) { | |
| 144 if (topUnsortable || !done) { | |
| 145 topUnsortable = false; | |
| 146 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMi
n); | |
| 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, n
extEnd, | |
| 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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 867213004:
remove prototype pathops code (Closed)
Base URL: https://skia.googlesource.com/skia.git@master