1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkDCubicIntersection.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,647 @@
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 +#include "SkPathOpsCubic.h"
1.13 +#include "SkPathOpsLine.h"
1.14 +#include "SkPathOpsPoint.h"
1.15 +#include "SkPathOpsQuad.h"
1.16 +#include "SkPathOpsRect.h"
1.17 +#include "SkReduceOrder.h"
1.18 +#include "SkTSort.h"
1.19 +
1.20 +#if ONE_OFF_DEBUG
1.21 +static const double tLimits1[2][2] = {{0.3, 0.4}, {0.8, 0.9}};
1.22 +static const double tLimits2[2][2] = {{-0.8, -0.9}, {-0.8, -0.9}};
1.23 +#endif
1.24 +
1.25 +#define DEBUG_QUAD_PART ONE_OFF_DEBUG && 1
1.26 +#define DEBUG_QUAD_PART_SHOW_SIMPLE DEBUG_QUAD_PART && 0
1.27 +#define SWAP_TOP_DEBUG 0
1.28 +
1.29 +static const int kCubicToQuadSubdivisionDepth = 8; // slots reserved for cubic to quads subdivision
1.30 +
1.31 +static int quadPart(const SkDCubic& cubic, double tStart, double tEnd, SkReduceOrder* reducer) {
1.32 + SkDCubic part = cubic.subDivide(tStart, tEnd);
1.33 + SkDQuad quad = part.toQuad();
1.34 + // FIXME: should reduceOrder be looser in this use case if quartic is going to blow up on an
1.35 + // extremely shallow quadratic?
1.36 + int order = reducer->reduce(quad);
1.37 +#if DEBUG_QUAD_PART
1.38 + SkDebugf("%s cubic=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
1.39 + " t=(%1.9g,%1.9g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY,
1.40 + cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY,
1.41 + cubic[3].fX, cubic[3].fY, tStart, tEnd);
1.42 + SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
1.43 + " {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
1.44 + part[0].fX, part[0].fY, part[1].fX, part[1].fY, part[2].fX, part[2].fY,
1.45 + part[3].fX, part[3].fY, quad[0].fX, quad[0].fY,
1.46 + quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
1.47 +#if DEBUG_QUAD_PART_SHOW_SIMPLE
1.48 + SkDebugf("%s simple=(%1.9g,%1.9g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY);
1.49 + if (order > 1) {
1.50 + SkDebugf(" %1.9g,%1.9g", reducer->fQuad[1].fX, reducer->fQuad[1].fY);
1.51 + }
1.52 + if (order > 2) {
1.53 + SkDebugf(" %1.9g,%1.9g", reducer->fQuad[2].fX, reducer->fQuad[2].fY);
1.54 + }
1.55 + SkDebugf(")\n");
1.56 + SkASSERT(order < 4 && order > 0);
1.57 +#endif
1.58 +#endif
1.59 + return order;
1.60 +}
1.61 +
1.62 +static void intersectWithOrder(const SkDQuad& simple1, int order1, const SkDQuad& simple2,
1.63 + int order2, SkIntersections& i) {
1.64 + if (order1 == 3 && order2 == 3) {
1.65 + i.intersect(simple1, simple2);
1.66 + } else if (order1 <= 2 && order2 <= 2) {
1.67 + i.intersect((const SkDLine&) simple1, (const SkDLine&) simple2);
1.68 + } else if (order1 == 3 && order2 <= 2) {
1.69 + i.intersect(simple1, (const SkDLine&) simple2);
1.70 + } else {
1.71 + SkASSERT(order1 <= 2 && order2 == 3);
1.72 + i.intersect(simple2, (const SkDLine&) simple1);
1.73 + i.swapPts();
1.74 + }
1.75 +}
1.76 +
1.77 +// this flavor centers potential intersections recursively. In contrast, '2' may inadvertently
1.78 +// chase intersections near quadratic ends, requiring odd hacks to find them.
1.79 +static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDCubic& cubic2,
1.80 + double t2s, double t2e, double precisionScale, SkIntersections& i) {
1.81 + i.upDepth();
1.82 + SkDCubic c1 = cubic1.subDivide(t1s, t1e);
1.83 + SkDCubic c2 = cubic2.subDivide(t2s, t2e);
1.84 + SkSTArray<kCubicToQuadSubdivisionDepth, double, true> ts1;
1.85 + // OPTIMIZE: if c1 == c2, call once (happens when detecting self-intersection)
1.86 + c1.toQuadraticTs(c1.calcPrecision() * precisionScale, &ts1);
1.87 + SkSTArray<kCubicToQuadSubdivisionDepth, double, true> ts2;
1.88 + c2.toQuadraticTs(c2.calcPrecision() * precisionScale, &ts2);
1.89 + double t1Start = t1s;
1.90 + int ts1Count = ts1.count();
1.91 + for (int i1 = 0; i1 <= ts1Count; ++i1) {
1.92 + const double tEnd1 = i1 < ts1Count ? ts1[i1] : 1;
1.93 + const double t1 = t1s + (t1e - t1s) * tEnd1;
1.94 + SkReduceOrder s1;
1.95 + int o1 = quadPart(cubic1, t1Start, t1, &s1);
1.96 + double t2Start = t2s;
1.97 + int ts2Count = ts2.count();
1.98 + for (int i2 = 0; i2 <= ts2Count; ++i2) {
1.99 + const double tEnd2 = i2 < ts2Count ? ts2[i2] : 1;
1.100 + const double t2 = t2s + (t2e - t2s) * tEnd2;
1.101 + if (&cubic1 == &cubic2 && t1Start >= t2Start) {
1.102 + t2Start = t2;
1.103 + continue;
1.104 + }
1.105 + SkReduceOrder s2;
1.106 + int o2 = quadPart(cubic2, t2Start, t2, &s2);
1.107 + #if ONE_OFF_DEBUG
1.108 + char tab[] = " ";
1.109 + if (tLimits1[0][0] >= t1Start && tLimits1[0][1] <= t1
1.110 + && tLimits1[1][0] >= t2Start && tLimits1[1][1] <= t2) {
1.111 + SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()*2, tab,
1.112 + __FUNCTION__, t1Start, t1, t2Start, t2);
1.113 + SkIntersections xlocals;
1.114 + xlocals.allowNear(false);
1.115 + intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, xlocals);
1.116 + SkDebugf(" xlocals.fUsed=%d\n", xlocals.used());
1.117 + }
1.118 + #endif
1.119 + SkIntersections locals;
1.120 + locals.allowNear(false);
1.121 + intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals);
1.122 + int tCount = locals.used();
1.123 + for (int tIdx = 0; tIdx < tCount; ++tIdx) {
1.124 + double to1 = t1Start + (t1 - t1Start) * locals[0][tIdx];
1.125 + double to2 = t2Start + (t2 - t2Start) * locals[1][tIdx];
1.126 + // if the computed t is not sufficiently precise, iterate
1.127 + SkDPoint p1 = cubic1.ptAtT(to1);
1.128 + SkDPoint p2 = cubic2.ptAtT(to2);
1.129 + if (p1.approximatelyEqual(p2)) {
1.130 + // FIXME: local edge may be coincident -- experiment with not propagating coincidence to caller
1.131 +// SkASSERT(!locals.isCoincident(tIdx));
1.132 + if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) {
1.133 + if (i.swapped()) { // FIXME: insert should respect swap
1.134 + i.insert(to2, to1, p1);
1.135 + } else {
1.136 + i.insert(to1, to2, p1);
1.137 + }
1.138 + }
1.139 + } else {
1.140 + double offset = precisionScale / 16; // FIME: const is arbitrary: test, refine
1.141 + double c1Bottom = tIdx == 0 ? 0 :
1.142 + (t1Start + (t1 - t1Start) * locals[0][tIdx - 1] + to1) / 2;
1.143 + double c1Min = SkTMax(c1Bottom, to1 - offset);
1.144 + double c1Top = tIdx == tCount - 1 ? 1 :
1.145 + (t1Start + (t1 - t1Start) * locals[0][tIdx + 1] + to1) / 2;
1.146 + double c1Max = SkTMin(c1Top, to1 + offset);
1.147 + double c2Min = SkTMax(0., to2 - offset);
1.148 + double c2Max = SkTMin(1., to2 + offset);
1.149 + #if ONE_OFF_DEBUG
1.150 + SkDebugf("%.*s %s 1 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab,
1.151 + __FUNCTION__,
1.152 + c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
1.153 + && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
1.154 + to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
1.155 + && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
1.156 + c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
1.157 + && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
1.158 + to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
1.159 + && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
1.160 + SkDebugf("%.*s %s 1 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
1.161 + " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
1.162 + i.depth()*2, tab, __FUNCTION__, c1Bottom, c1Top, 0., 1.,
1.163 + to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
1.164 + SkDebugf("%.*s %s 1 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
1.165 + " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min,
1.166 + c1Max, c2Min, c2Max);
1.167 + #endif
1.168 + intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
1.169 + #if ONE_OFF_DEBUG
1.170 + SkDebugf("%.*s %s 1 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__,
1.171 + i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
1.172 + #endif
1.173 + if (tCount > 1) {
1.174 + c1Min = SkTMax(0., to1 - offset);
1.175 + c1Max = SkTMin(1., to1 + offset);
1.176 + double c2Bottom = tIdx == 0 ? to2 :
1.177 + (t2Start + (t2 - t2Start) * locals[1][tIdx - 1] + to2) / 2;
1.178 + double c2Top = tIdx == tCount - 1 ? to2 :
1.179 + (t2Start + (t2 - t2Start) * locals[1][tIdx + 1] + to2) / 2;
1.180 + if (c2Bottom > c2Top) {
1.181 + SkTSwap(c2Bottom, c2Top);
1.182 + }
1.183 + if (c2Bottom == to2) {
1.184 + c2Bottom = 0;
1.185 + }
1.186 + if (c2Top == to2) {
1.187 + c2Top = 1;
1.188 + }
1.189 + c2Min = SkTMax(c2Bottom, to2 - offset);
1.190 + c2Max = SkTMin(c2Top, to2 + offset);
1.191 + #if ONE_OFF_DEBUG
1.192 + SkDebugf("%.*s %s 2 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab,
1.193 + __FUNCTION__,
1.194 + c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
1.195 + && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
1.196 + to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
1.197 + && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
1.198 + c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
1.199 + && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
1.200 + to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
1.201 + && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
1.202 + SkDebugf("%.*s %s 2 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
1.203 + " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
1.204 + i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top,
1.205 + to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
1.206 + SkDebugf("%.*s %s 2 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
1.207 + " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min,
1.208 + c1Max, c2Min, c2Max);
1.209 + #endif
1.210 + intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
1.211 + #if ONE_OFF_DEBUG
1.212 + SkDebugf("%.*s %s 2 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__,
1.213 + i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
1.214 + #endif
1.215 + c1Min = SkTMax(c1Bottom, to1 - offset);
1.216 + c1Max = SkTMin(c1Top, to1 + offset);
1.217 + #if ONE_OFF_DEBUG
1.218 + SkDebugf("%.*s %s 3 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab,
1.219 + __FUNCTION__,
1.220 + c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max
1.221 + && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max,
1.222 + to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset
1.223 + && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset,
1.224 + c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max
1.225 + && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max,
1.226 + to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset
1.227 + && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset);
1.228 + SkDebugf("%.*s %s 3 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
1.229 + " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
1.230 + i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top,
1.231 + to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
1.232 + SkDebugf("%.*s %s 3 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
1.233 + " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min,
1.234 + c1Max, c2Min, c2Max);
1.235 + #endif
1.236 + intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
1.237 + #if ONE_OFF_DEBUG
1.238 + SkDebugf("%.*s %s 3 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__,
1.239 + i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
1.240 + #endif
1.241 + }
1.242 + // intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
1.243 + // FIXME: if no intersection is found, either quadratics intersected where
1.244 + // cubics did not, or the intersection was missed. In the former case, expect
1.245 + // the quadratics to be nearly parallel at the point of intersection, and check
1.246 + // for that.
1.247 + }
1.248 + }
1.249 + t2Start = t2;
1.250 + }
1.251 + t1Start = t1;
1.252 + }
1.253 + i.downDepth();
1.254 +}
1.255 +
1.256 + // if two ends intersect, check middle for coincidence
1.257 +bool SkIntersections::cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2) {
1.258 + if (fUsed < 2) {
1.259 + return false;
1.260 + }
1.261 + int last = fUsed - 1;
1.262 + double tRange1 = fT[0][last] - fT[0][0];
1.263 + double tRange2 = fT[1][last] - fT[1][0];
1.264 + for (int index = 1; index < 5; ++index) {
1.265 + double testT1 = fT[0][0] + tRange1 * index / 5;
1.266 + double testT2 = fT[1][0] + tRange2 * index / 5;
1.267 + SkDPoint testPt1 = c1.ptAtT(testT1);
1.268 + SkDPoint testPt2 = c2.ptAtT(testT2);
1.269 + if (!testPt1.approximatelyEqual(testPt2)) {
1.270 + return false;
1.271 + }
1.272 + }
1.273 + if (fUsed > 2) {
1.274 + fPt[1] = fPt[last];
1.275 + fT[0][1] = fT[0][last];
1.276 + fT[1][1] = fT[1][last];
1.277 + fUsed = 2;
1.278 + }
1.279 + fIsCoincident[0] = fIsCoincident[1] = 0x03;
1.280 + return true;
1.281 +}
1.282 +
1.283 +#define LINE_FRACTION 0.1
1.284 +
1.285 +// intersect the end of the cubic with the other. Try lines from the end to control and opposite
1.286 +// end to determine range of t on opposite cubic.
1.287 +bool SkIntersections::cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2) {
1.288 + int t1Index = start ? 0 : 3;
1.289 + double testT = (double) !start;
1.290 + bool swap = swapped();
1.291 + // quad/quad at this point checks to see if exact matches have already been found
1.292 + // cubic/cubic can't reject so easily since cubics can intersect same point more than once
1.293 + SkDLine tmpLine;
1.294 + tmpLine[0] = tmpLine[1] = cubic2[t1Index];
1.295 + tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY;
1.296 + tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX;
1.297 + SkIntersections impTs;
1.298 + impTs.allowNear(false);
1.299 + impTs.intersectRay(cubic1, tmpLine);
1.300 + for (int index = 0; index < impTs.used(); ++index) {
1.301 + SkDPoint realPt = impTs.pt(index);
1.302 + if (!tmpLine[0].approximatelyEqual(realPt)) {
1.303 + continue;
1.304 + }
1.305 + if (swap) {
1.306 + insert(testT, impTs[0][index], tmpLine[0]);
1.307 + } else {
1.308 + insert(impTs[0][index], testT, tmpLine[0]);
1.309 + }
1.310 + return true;
1.311 + }
1.312 + return false;
1.313 +}
1.314 +
1.315 +void SkIntersections::cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2,
1.316 + const SkDRect& bounds2) {
1.317 + SkDLine line;
1.318 + int t1Index = start ? 0 : 3;
1.319 + double testT = (double) !start;
1.320 + // don't bother if the two cubics are connnected
1.321 + static const int kPointsInCubic = 4; // FIXME: move to DCubic, replace '4' with this
1.322 + static const int kMaxLineCubicIntersections = 3;
1.323 + SkSTArray<(kMaxLineCubicIntersections - 1) * kMaxLineCubicIntersections, double, true> tVals;
1.324 + line[0] = cubic1[t1Index];
1.325 + // this variant looks for intersections with the end point and lines parallel to other points
1.326 + for (int index = 0; index < kPointsInCubic; ++index) {
1.327 + if (index == t1Index) {
1.328 + continue;
1.329 + }
1.330 + SkDVector dxy1 = cubic1[index] - line[0];
1.331 + dxy1 /= SkDCubic::gPrecisionUnit;
1.332 + line[1] = line[0] + dxy1;
1.333 + SkDRect lineBounds;
1.334 + lineBounds.setBounds(line);
1.335 + if (!bounds2.intersects(&lineBounds)) {
1.336 + continue;
1.337 + }
1.338 + SkIntersections local;
1.339 + if (!local.intersect(cubic2, line)) {
1.340 + continue;
1.341 + }
1.342 + for (int idx2 = 0; idx2 < local.used(); ++idx2) {
1.343 + double foundT = local[0][idx2];
1.344 + if (approximately_less_than_zero(foundT)
1.345 + || approximately_greater_than_one(foundT)) {
1.346 + continue;
1.347 + }
1.348 + if (local.pt(idx2).approximatelyEqual(line[0])) {
1.349 + if (swapped()) { // FIXME: insert should respect swap
1.350 + insert(foundT, testT, line[0]);
1.351 + } else {
1.352 + insert(testT, foundT, line[0]);
1.353 + }
1.354 + } else {
1.355 + tVals.push_back(foundT);
1.356 + }
1.357 + }
1.358 + }
1.359 + if (tVals.count() == 0) {
1.360 + return;
1.361 + }
1.362 + SkTQSort<double>(tVals.begin(), tVals.end() - 1);
1.363 + double tMin1 = start ? 0 : 1 - LINE_FRACTION;
1.364 + double tMax1 = start ? LINE_FRACTION : 1;
1.365 + int tIdx = 0;
1.366 + do {
1.367 + int tLast = tIdx;
1.368 + while (tLast + 1 < tVals.count() && roughly_equal(tVals[tLast + 1], tVals[tIdx])) {
1.369 + ++tLast;
1.370 + }
1.371 + double tMin2 = SkTMax(tVals[tIdx] - LINE_FRACTION, 0.0);
1.372 + double tMax2 = SkTMin(tVals[tLast] + LINE_FRACTION, 1.0);
1.373 + int lastUsed = used();
1.374 + ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
1.375 + if (lastUsed == used()) {
1.376 + tMin2 = SkTMax(tVals[tIdx] - (1.0 / SkDCubic::gPrecisionUnit), 0.0);
1.377 + tMax2 = SkTMin(tVals[tLast] + (1.0 / SkDCubic::gPrecisionUnit), 1.0);
1.378 + ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
1.379 + }
1.380 + tIdx = tLast + 1;
1.381 + } while (tIdx < tVals.count());
1.382 + return;
1.383 +}
1.384 +
1.385 +const double CLOSE_ENOUGH = 0.001;
1.386 +
1.387 +static bool closeStart(const SkDCubic& cubic, int cubicIndex, SkIntersections& i, SkDPoint& pt) {
1.388 + if (i[cubicIndex][0] != 0 || i[cubicIndex][1] > CLOSE_ENOUGH) {
1.389 + return false;
1.390 + }
1.391 + pt = cubic.ptAtT((i[cubicIndex][0] + i[cubicIndex][1]) / 2);
1.392 + return true;
1.393 +}
1.394 +
1.395 +static bool closeEnd(const SkDCubic& cubic, int cubicIndex, SkIntersections& i, SkDPoint& pt) {
1.396 + int last = i.used() - 1;
1.397 + if (i[cubicIndex][last] != 1 || i[cubicIndex][last - 1] < 1 - CLOSE_ENOUGH) {
1.398 + return false;
1.399 + }
1.400 + pt = cubic.ptAtT((i[cubicIndex][last] + i[cubicIndex][last - 1]) / 2);
1.401 + return true;
1.402 +}
1.403 +
1.404 +static bool only_end_pts_in_common(const SkDCubic& c1, const SkDCubic& c2) {
1.405 +// the idea here is to see at minimum do a quick reject by rotating all points
1.406 +// to either side of the line formed by connecting the endpoints
1.407 +// if the opposite curves points are on the line or on the other side, the
1.408 +// curves at most intersect at the endpoints
1.409 + for (int oddMan = 0; oddMan < 4; ++oddMan) {
1.410 + const SkDPoint* endPt[3];
1.411 + for (int opp = 1; opp < 4; ++opp) {
1.412 + int end = oddMan ^ opp; // choose a value not equal to oddMan
1.413 + endPt[opp - 1] = &c1[end];
1.414 + }
1.415 + for (int triTest = 0; triTest < 3; ++triTest) {
1.416 + double origX = endPt[triTest]->fX;
1.417 + double origY = endPt[triTest]->fY;
1.418 + int oppTest = triTest + 1;
1.419 + if (3 == oppTest) {
1.420 + oppTest = 0;
1.421 + }
1.422 + double adj = endPt[oppTest]->fX - origX;
1.423 + double opp = endPt[oppTest]->fY - origY;
1.424 + double sign = (c1[oddMan].fY - origY) * adj - (c1[oddMan].fX - origX) * opp;
1.425 + if (approximately_zero(sign)) {
1.426 + goto tryNextHalfPlane;
1.427 + }
1.428 + for (int n = 0; n < 4; ++n) {
1.429 + double test = (c2[n].fY - origY) * adj - (c2[n].fX - origX) * opp;
1.430 + if (test * sign > 0 && !precisely_zero(test)) {
1.431 + goto tryNextHalfPlane;
1.432 + }
1.433 + }
1.434 + }
1.435 + return true;
1.436 +tryNextHalfPlane:
1.437 + ;
1.438 + }
1.439 + return false;
1.440 +}
1.441 +
1.442 +int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
1.443 + if (fMax == 0) {
1.444 + fMax = 9;
1.445 + }
1.446 + bool selfIntersect = &c1 == &c2;
1.447 + if (selfIntersect) {
1.448 + if (c1[0].approximatelyEqual(c1[3])) {
1.449 + insert(0, 1, c1[0]);
1.450 + return fUsed;
1.451 + }
1.452 + } else {
1.453 + // OPTIMIZATION: set exact end bits here to avoid cubic exact end later
1.454 + for (int i1 = 0; i1 < 4; i1 += 3) {
1.455 + for (int i2 = 0; i2 < 4; i2 += 3) {
1.456 + if (c1[i1].approximatelyEqual(c2[i2])) {
1.457 + insert(i1 >> 1, i2 >> 1, c1[i1]);
1.458 + }
1.459 + }
1.460 + }
1.461 + }
1.462 + SkASSERT(fUsed < 4);
1.463 + if (!selfIntersect) {
1.464 + if (only_end_pts_in_common(c1, c2)) {
1.465 + return fUsed;
1.466 + }
1.467 + if (only_end_pts_in_common(c2, c1)) {
1.468 + return fUsed;
1.469 + }
1.470 + }
1.471 + // quad/quad does linear test here -- cubic does not
1.472 + // cubics which are really lines should have been detected in reduce step earlier
1.473 + int exactEndBits = 0;
1.474 + if (selfIntersect) {
1.475 + if (fUsed) {
1.476 + return fUsed;
1.477 + }
1.478 + } else {
1.479 + exactEndBits |= cubicExactEnd(c1, false, c2) << 0;
1.480 + exactEndBits |= cubicExactEnd(c1, true, c2) << 1;
1.481 + swap();
1.482 + exactEndBits |= cubicExactEnd(c2, false, c1) << 2;
1.483 + exactEndBits |= cubicExactEnd(c2, true, c1) << 3;
1.484 + swap();
1.485 + }
1.486 + if (cubicCheckCoincidence(c1, c2)) {
1.487 + SkASSERT(!selfIntersect);
1.488 + return fUsed;
1.489 + }
1.490 + // FIXME: pass in cached bounds from caller
1.491 + SkDRect c2Bounds;
1.492 + c2Bounds.setBounds(c2);
1.493 + if (!(exactEndBits & 4)) {
1.494 + cubicNearEnd(c1, false, c2, c2Bounds);
1.495 + }
1.496 + if (!(exactEndBits & 8)) {
1.497 + cubicNearEnd(c1, true, c2, c2Bounds);
1.498 + }
1.499 + if (!selfIntersect) {
1.500 + SkDRect c1Bounds;
1.501 + c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
1.502 + swap();
1.503 + if (!(exactEndBits & 1)) {
1.504 + cubicNearEnd(c2, false, c1, c1Bounds);
1.505 + }
1.506 + if (!(exactEndBits & 2)) {
1.507 + cubicNearEnd(c2, true, c1, c1Bounds);
1.508 + }
1.509 + swap();
1.510 + }
1.511 + if (cubicCheckCoincidence(c1, c2)) {
1.512 + SkASSERT(!selfIntersect);
1.513 + return fUsed;
1.514 + }
1.515 + SkIntersections i;
1.516 + i.fAllowNear = false;
1.517 + i.fMax = 9;
1.518 + ::intersect(c1, 0, 1, c2, 0, 1, 1, i);
1.519 + int compCount = i.used();
1.520 + if (compCount) {
1.521 + int exactCount = used();
1.522 + if (exactCount == 0) {
1.523 + set(i);
1.524 + } else {
1.525 + // at least one is exact or near, and at least one was computed. Eliminate duplicates
1.526 + for (int exIdx = 0; exIdx < exactCount; ++exIdx) {
1.527 + for (int cpIdx = 0; cpIdx < compCount; ) {
1.528 + if (fT[0][0] == i[0][0] && fT[1][0] == i[1][0]) {
1.529 + i.removeOne(cpIdx);
1.530 + --compCount;
1.531 + continue;
1.532 + }
1.533 + double tAvg = (fT[0][exIdx] + i[0][cpIdx]) / 2;
1.534 + SkDPoint pt = c1.ptAtT(tAvg);
1.535 + if (!pt.approximatelyEqual(fPt[exIdx])) {
1.536 + ++cpIdx;
1.537 + continue;
1.538 + }
1.539 + tAvg = (fT[1][exIdx] + i[1][cpIdx]) / 2;
1.540 + pt = c2.ptAtT(tAvg);
1.541 + if (!pt.approximatelyEqual(fPt[exIdx])) {
1.542 + ++cpIdx;
1.543 + continue;
1.544 + }
1.545 + i.removeOne(cpIdx);
1.546 + --compCount;
1.547 + }
1.548 + }
1.549 + // if mid t evaluates to nearly the same point, skip the t
1.550 + for (int cpIdx = 0; cpIdx < compCount - 1; ) {
1.551 + double tAvg = (fT[0][cpIdx] + i[0][cpIdx + 1]) / 2;
1.552 + SkDPoint pt = c1.ptAtT(tAvg);
1.553 + if (!pt.approximatelyEqual(fPt[cpIdx])) {
1.554 + ++cpIdx;
1.555 + continue;
1.556 + }
1.557 + tAvg = (fT[1][cpIdx] + i[1][cpIdx + 1]) / 2;
1.558 + pt = c2.ptAtT(tAvg);
1.559 + if (!pt.approximatelyEqual(fPt[cpIdx])) {
1.560 + ++cpIdx;
1.561 + continue;
1.562 + }
1.563 + i.removeOne(cpIdx);
1.564 + --compCount;
1.565 + }
1.566 + // in addition to adding below missing function, think about how to say
1.567 + append(i);
1.568 + }
1.569 + }
1.570 + // If an end point and a second point very close to the end is returned, the second
1.571 + // point may have been detected because the approximate quads
1.572 + // intersected at the end and close to it. Verify that the second point is valid.
1.573 + if (fUsed <= 1) {
1.574 + return fUsed;
1.575 + }
1.576 + SkDPoint pt[2];
1.577 + if (closeStart(c1, 0, *this, pt[0]) && closeStart(c2, 1, *this, pt[1])
1.578 + && pt[0].approximatelyEqual(pt[1])) {
1.579 + removeOne(1);
1.580 + }
1.581 + if (closeEnd(c1, 0, *this, pt[0]) && closeEnd(c2, 1, *this, pt[1])
1.582 + && pt[0].approximatelyEqual(pt[1])) {
1.583 + removeOne(used() - 2);
1.584 + }
1.585 + // vet the pairs of t values to see if the mid value is also on the curve. If so, mark
1.586 + // the span as coincident
1.587 + if (fUsed >= 2 && !coincidentUsed()) {
1.588 + int last = fUsed - 1;
1.589 + int match = 0;
1.590 + for (int index = 0; index < last; ++index) {
1.591 + double mid1 = (fT[0][index] + fT[0][index + 1]) / 2;
1.592 + double mid2 = (fT[1][index] + fT[1][index + 1]) / 2;
1.593 + pt[0] = c1.ptAtT(mid1);
1.594 + pt[1] = c2.ptAtT(mid2);
1.595 + if (pt[0].approximatelyEqual(pt[1])) {
1.596 + match |= 1 << index;
1.597 + }
1.598 + }
1.599 + if (match) {
1.600 +#if DEBUG_CONCIDENT
1.601 + if (((match + 1) & match) != 0) {
1.602 + SkDebugf("%s coincident hole\n", __FUNCTION__);
1.603 + }
1.604 +#endif
1.605 + // for now, assume that everything from start to finish is coincident
1.606 + if (fUsed > 2) {
1.607 + fPt[1] = fPt[last];
1.608 + fT[0][1] = fT[0][last];
1.609 + fT[1][1] = fT[1][last];
1.610 + fIsCoincident[0] = 0x03;
1.611 + fIsCoincident[1] = 0x03;
1.612 + fUsed = 2;
1.613 + }
1.614 + }
1.615 + }
1.616 + return fUsed;
1.617 +}
1.618 +
1.619 +// Up promote the quad to a cubic.
1.620 +// OPTIMIZATION If this is a common use case, optimize by duplicating
1.621 +// the intersect 3 loop to avoid the promotion / demotion code
1.622 +int SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) {
1.623 + fMax = 6;
1.624 + SkDCubic up = quad.toCubic();
1.625 + (void) intersect(cubic, up);
1.626 + return used();
1.627 +}
1.628 +
1.629 +/* http://www.ag.jku.at/compass/compasssample.pdf
1.630 +( Self-Intersection Problems and Approximate Implicitization by Jan B. Thomassen
1.631 +Centre of Mathematics for Applications, University of Oslo http://www.cma.uio.no janbth@math.uio.no
1.632 +SINTEF Applied Mathematics http://www.sintef.no )
1.633 +describes a method to find the self intersection of a cubic by taking the gradient of the implicit
1.634 +form dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/
1.635 +
1.636 +int SkIntersections::intersect(const SkDCubic& c) {
1.637 + fMax = 1;
1.638 + // check to see if x or y end points are the extrema. Are other quick rejects possible?
1.639 + if (c.endsAreExtremaInXOrY()) {
1.640 + return false;
1.641 + }
1.642 + (void) intersect(c, c);
1.643 + if (used() > 0) {
1.644 + SkASSERT(used() == 1);
1.645 + if (fT[0][0] > fT[1][0]) {
1.646 + swapPts();
1.647 + }
1.648 + }
1.649 + return used();
1.650 +}
