1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkIntersections.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,210 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#include "SkIntersections.h"
1.12 +
1.13 +void SkIntersections::append(const SkIntersections& i) {
1.14 + for (int index = 0; index < i.fUsed; ++index) {
1.15 + insert(i[0][index], i[1][index], i.pt(index));
1.16 + }
1.17 +}
1.18 +
1.19 +int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
1.20 + NULL,
1.21 + &SkIntersections::verticalLine,
1.22 + &SkIntersections::verticalQuad,
1.23 + &SkIntersections::verticalCubic
1.24 +};
1.25 +
1.26 +int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = {
1.27 + NULL,
1.28 + &SkIntersections::lineRay,
1.29 + &SkIntersections::quadRay,
1.30 + &SkIntersections::cubicRay
1.31 +};
1.32 +
1.33 +int SkIntersections::coincidentUsed() const {
1.34 + if (!fIsCoincident[0]) {
1.35 + SkASSERT(!fIsCoincident[1]);
1.36 + return 0;
1.37 + }
1.38 + int count = 0;
1.39 + SkDEBUGCODE(int count2 = 0;)
1.40 + for (int index = 0; index < fUsed; ++index) {
1.41 + if (fIsCoincident[0] & (1 << index)) {
1.42 + ++count;
1.43 + }
1.44 +#ifdef SK_DEBUG
1.45 + if (fIsCoincident[1] & (1 << index)) {
1.46 + ++count2;
1.47 + }
1.48 +#endif
1.49 + }
1.50 + SkASSERT(count == count2);
1.51 + return count;
1.52 +}
1.53 +
1.54 +int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) {
1.55 + SkDCubic cubic;
1.56 + cubic.set(pts);
1.57 + fMax = 3;
1.58 + return intersectRay(cubic, line);
1.59 +}
1.60 +
1.61 +void SkIntersections::flip() {
1.62 + for (int index = 0; index < fUsed; ++index) {
1.63 + fT[1][index] = 1 - fT[1][index];
1.64 + }
1.65 +}
1.66 +
1.67 +int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
1.68 + if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
1.69 + // For now, don't allow a mix of coincident and non-coincident intersections
1.70 + return -1;
1.71 + }
1.72 + SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
1.73 + int index;
1.74 + for (index = 0; index < fUsed; ++index) {
1.75 + double oldOne = fT[0][index];
1.76 + double oldTwo = fT[1][index];
1.77 + if (one == oldOne && two == oldTwo) {
1.78 + return -1;
1.79 + }
1.80 + if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
1.81 + if ((precisely_zero(one) && !precisely_zero(oldOne))
1.82 + || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
1.83 + || (precisely_zero(two) && !precisely_zero(oldTwo))
1.84 + || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
1.85 + fT[0][index] = one;
1.86 + fT[1][index] = two;
1.87 + fPt[index] = pt;
1.88 + }
1.89 + return -1;
1.90 + }
1.91 + #if ONE_OFF_DEBUG
1.92 + if (pt.roughlyEqual(fPt[index])) {
1.93 + SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
1.94 + }
1.95 + #endif
1.96 + if (fT[0][index] > one) {
1.97 + break;
1.98 + }
1.99 + }
1.100 + if (fUsed >= fMax) {
1.101 + SkASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must
1.102 + // be propagated all the way back down to the caller, and return failure.
1.103 + fUsed = 0;
1.104 + return 0;
1.105 + }
1.106 + int remaining = fUsed - index;
1.107 + if (remaining > 0) {
1.108 + memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
1.109 + memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
1.110 + memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
1.111 + int clearMask = ~((1 << index) - 1);
1.112 + fIsCoincident[0] += fIsCoincident[0] & clearMask;
1.113 + fIsCoincident[1] += fIsCoincident[1] & clearMask;
1.114 + }
1.115 + fPt[index] = pt;
1.116 + fT[0][index] = one;
1.117 + fT[1][index] = two;
1.118 + ++fUsed;
1.119 + return index;
1.120 +}
1.121 +
1.122 +void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
1.123 + int index = insertSwap(one, two, pt);
1.124 + int bit = 1 << index;
1.125 + fIsCoincident[0] |= bit;
1.126 + fIsCoincident[1] |= bit;
1.127 +}
1.128 +
1.129 +int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) {
1.130 + SkDLine l;
1.131 + l.set(pts);
1.132 + fMax = 2;
1.133 + return intersectRay(l, line);
1.134 +}
1.135 +
1.136 +void SkIntersections::offset(int base, double start, double end) {
1.137 + for (int index = base; index < fUsed; ++index) {
1.138 + double val = fT[fSwap][index];
1.139 + val *= end - start;
1.140 + val += start;
1.141 + fT[fSwap][index] = val;
1.142 + }
1.143 +}
1.144 +
1.145 +int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) {
1.146 + SkDQuad quad;
1.147 + quad.set(pts);
1.148 + fMax = 2;
1.149 + return intersectRay(quad, line);
1.150 +}
1.151 +
1.152 +void SkIntersections::quickRemoveOne(int index, int replace) {
1.153 + if (index < replace) {
1.154 + fT[0][index] = fT[0][replace];
1.155 + }
1.156 +}
1.157 +
1.158 +#if 0
1.159 +void SkIntersections::remove(double one, double two, const SkDPoint& startPt,
1.160 + const SkDPoint& endPt) {
1.161 + for (int index = fUsed - 1; index >= 0; --index) {
1.162 + if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two)
1.163 + || startPt.approximatelyEqual(fPt[index])
1.164 + || endPt.approximatelyEqual(fPt[index]))) {
1.165 + SkASSERT(fUsed > 0);
1.166 + removeOne(index);
1.167 + }
1.168 + }
1.169 +}
1.170 +#endif
1.171 +
1.172 +void SkIntersections::removeOne(int index) {
1.173 + int remaining = --fUsed - index;
1.174 + if (remaining <= 0) {
1.175 + return;
1.176 + }
1.177 + memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
1.178 + memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
1.179 + memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
1.180 + SkASSERT(fIsCoincident[0] == 0);
1.181 + int coBit = fIsCoincident[0] & (1 << index);
1.182 + fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
1.183 + SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
1.184 + fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
1.185 +}
1.186 +
1.187 +void SkIntersections::swapPts() {
1.188 + int index;
1.189 + for (index = 0; index < fUsed; ++index) {
1.190 + SkTSwap(fT[0][index], fT[1][index]);
1.191 + }
1.192 +}
1.193 +
1.194 +int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom,
1.195 + SkScalar x, bool flipped) {
1.196 + SkDLine line;
1.197 + line.set(a);
1.198 + return vertical(line, top, bottom, x, flipped);
1.199 +}
1.200 +
1.201 +int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom,
1.202 + SkScalar x, bool flipped) {
1.203 + SkDQuad quad;
1.204 + quad.set(a);
1.205 + return vertical(quad, top, bottom, x, flipped);
1.206 +}
1.207 +
1.208 +int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom,
1.209 + SkScalar x, bool flipped) {
1.210 + SkDCubic cubic;
1.211 + cubic.set(a);
1.212 + return vertical(cubic, top, bottom, x, flipped);
1.213 +}
