diff options
Diffstat (limited to 'gfx/skia/skia/src/pathops/SkIntersections.cpp')
| -rw-r--r-- | gfx/skia/skia/src/pathops/SkIntersections.cpp | 175 |
1 files changed, 175 insertions, 0 deletions
diff --git a/gfx/skia/skia/src/pathops/SkIntersections.cpp b/gfx/skia/skia/src/pathops/SkIntersections.cpp new file mode 100644 index 0000000000..4e49ee21e8 --- /dev/null +++ b/gfx/skia/skia/src/pathops/SkIntersections.cpp @@ -0,0 +1,175 @@ +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#include "src/pathops/SkIntersections.h" + +#include <string> + +int SkIntersections::closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, + double* closestDist) const { + int closest = -1; + *closestDist = SK_ScalarMax; + for (int index = 0; index < fUsed; ++index) { + if (!between(rangeStart, fT[0][index], rangeEnd)) { + continue; + } + const SkDPoint& iPt = fPt[index]; + double dist = testPt.distanceSquared(iPt); + if (*closestDist > dist) { + *closestDist = dist; + closest = index; + } + } + return closest; +} + +void SkIntersections::flip() { + for (int index = 0; index < fUsed; ++index) { + fT[1][index] = 1 - fT[1][index]; + } +} + +int SkIntersections::insert(double one, double two, const SkDPoint& pt) { + if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { + // For now, don't allow a mix of coincident and non-coincident intersections + return -1; + } + SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]); + int index; + for (index = 0; index < fUsed; ++index) { + double oldOne = fT[0][index]; + double oldTwo = fT[1][index]; + if (one == oldOne && two == oldTwo) { + return -1; + } + if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) { + if ((!precisely_zero(one) || precisely_zero(oldOne)) + && (!precisely_equal(one, 1) || precisely_equal(oldOne, 1)) + && (!precisely_zero(two) || precisely_zero(oldTwo)) + && (!precisely_equal(two, 1) || precisely_equal(oldTwo, 1))) { + return -1; + } + SkASSERT(one >= 0 && one <= 1); + SkASSERT(two >= 0 && two <= 1); + // remove this and reinsert below in case replacing would make list unsorted + int remaining = fUsed - index - 1; + memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); + memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); + memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); + int clearMask = ~((1 << index) - 1); + fIsCoincident[0] -= (fIsCoincident[0] >> 1) & clearMask; + fIsCoincident[1] -= (fIsCoincident[1] >> 1) & clearMask; + --fUsed; + break; + } + #if ONE_OFF_DEBUG + if (pt.roughlyEqual(fPt[index])) { + SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); + } + #endif + } + for (index = 0; index < fUsed; ++index) { + if (fT[0][index] > one) { + break; + } + } + if (fUsed >= fMax) { + SkOPASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must + // be propagated all the way back down to the caller, and return failure. + fUsed = 0; + return 0; + } + int remaining = fUsed - index; + if (remaining > 0) { + memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); + memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); + memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); + int clearMask = ~((1 << index) - 1); + fIsCoincident[0] += fIsCoincident[0] & clearMask; + fIsCoincident[1] += fIsCoincident[1] & clearMask; + } + fPt[index] = pt; + if (one < 0 || one > 1) { + return -1; + } + if (two < 0 || two > 1) { + return -1; + } + fT[0][index] = one; + fT[1][index] = two; + ++fUsed; + SkASSERT(fUsed <= std::size(fPt)); + return index; +} + +void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) { + SkASSERT(one == 0 || one == 1); + SkASSERT(two == 0 || two == 1); + SkASSERT(pt1 != pt2); + fNearlySame[one ? 1 : 0] = true; + (void) insert(one, two, pt1); + fPt2[one ? 1 : 0] = pt2; +} + +int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { + int index = insertSwap(one, two, pt); + if (index >= 0) { + setCoincident(index); + } + return index; +} + +void SkIntersections::setCoincident(int index) { + SkASSERT(index >= 0); + int bit = 1 << index; + fIsCoincident[0] |= bit; + fIsCoincident[1] |= bit; +} + +void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b, + int bIndex) { + this->reset(); + fT[0][0] = a.fT[0][aIndex]; + fT[1][0] = b.fT[0][bIndex]; + fPt[0] = a.fPt[aIndex]; + fPt2[0] = b.fPt[bIndex]; + fUsed = 1; +} + +int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const { + int result = -1; + for (int index = 0; index < fUsed; ++index) { + if (!between(rangeStart, fT[0][index], rangeEnd)) { + continue; + } + if (result < 0) { + result = index; + continue; + } + SkDVector best = fPt[result] - origin; + SkDVector test = fPt[index] - origin; + if (test.crossCheck(best) < 0) { + result = index; + } + } + return result; +} + +void SkIntersections::removeOne(int index) { + int remaining = --fUsed - index; + if (remaining <= 0) { + return; + } + memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); + memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); + memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); +// SkASSERT(fIsCoincident[0] == 0); + int coBit = fIsCoincident[0] & (1 << index); + fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; + SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); + fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; +} |