The Tor Browser / file comparison
comparison: gfx/skia/trunk/src/pathops/SkPathOpsSimplify.cpp
gfx/skia/trunk/src/pathops/SkPathOpsSimplify.cpp
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:17e12545d6f7 |
|---|---|
| 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, SkOpAngle::kUnaryWinding, &firstContour, | |
| 21 &index, &endIndex, &topLeft, &topUnsortable, &topDone); | |
| 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 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; | |
| 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 HandleCoincidence(&contourList, 0); | |
| 186 // construct closed contours | |
| 187 SkPathWriter simple(*result); | |
| 188 if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple) | |
| 189 : !bridgeXor(contourList, &simple)) | |
| 190 { // if some edges could not be resolved, assemble remaining fragments | |
| 191 SkPath temp; | |
| 192 temp.setFillType(fillType); | |
| 193 SkPathWriter assembled(temp); | |
| 194 Assemble(simple, &assembled); | |
| 195 *result = *assembled.nativePath(); | |
| 196 result->setFillType(fillType); | |
| 197 } | |
| 198 return true; | |
| 199 } |
