107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkIntersections.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCubic.h" 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsPoint.h" 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsQuad.h" 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsRect.h" 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkReduceOrder.h" 15b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org#include "SkTSort.h" 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if ONE_OFF_DEBUG 187eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comstatic const double tLimits1[2][2] = {{0.3, 0.4}, {0.8, 0.9}}; 197eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comstatic const double tLimits2[2][2] = {{-0.8, -0.9}, {-0.8, -0.9}}; 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 22fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com#define DEBUG_QUAD_PART ONE_OFF_DEBUG && 1 23fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com#define DEBUG_QUAD_PART_SHOW_SIMPLE DEBUG_QUAD_PART && 0 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define SWAP_TOP_DEBUG 0 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 26d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.comstatic const int kCubicToQuadSubdivisionDepth = 8; // slots reserved for cubic to quads subdivision 27d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic int quadPart(const SkDCubic& cubic, double tStart, double tEnd, SkReduceOrder* reducer) { 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic part = cubic.subDivide(tStart, tEnd); 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad quad = part.toQuad(); 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME: should reduceOrder be looser in this use case if quartic is going to blow up on an 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // extremely shallow quadratic? 33927b7028d44c46e9cbc18368f16ec2262d59d94dcaryclark@google.com int order = reducer->reduce(quad); 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#if DEBUG_QUAD_PART 35fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDebugf("%s cubic=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" 36fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com " t=(%1.9g,%1.9g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY, 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY, 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic[3].fX, cubic[3].fY, tStart, tEnd); 39fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n" 40fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com " {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com part[0].fX, part[0].fY, part[1].fX, part[1].fY, part[2].fX, part[2].fY, 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com part[3].fX, part[3].fY, quad[0].fX, quad[0].fY, 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY); 44fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com#if DEBUG_QUAD_PART_SHOW_SIMPLE 45fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDebugf("%s simple=(%1.9g,%1.9g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY); 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (order > 1) { 47fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDebugf(" %1.9g,%1.9g", reducer->fQuad[1].fX, reducer->fQuad[1].fY); 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (order > 2) { 50fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDebugf(" %1.9g,%1.9g", reducer->fQuad[2].fX, reducer->fQuad[2].fY); 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf(")\n"); 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(order < 4 && order > 0); 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 55fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com#endif 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return order; 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 5807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic void intersectWithOrder(const SkDQuad& simple1, int order1, const SkDQuad& simple2, 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int order2, SkIntersections& i) { 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (order1 == 3 && order2 == 3) { 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.intersect(simple1, simple2); 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else if (order1 <= 2 && order2 <= 2) { 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.intersect((const SkDLine&) simple1, (const SkDLine&) simple2); 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else if (order1 == 3 && order2 <= 2) { 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.intersect(simple1, (const SkDLine&) simple2); 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(order1 <= 2 && order2 == 3); 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.intersect(simple2, (const SkDLine&) simple1); 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.swapPts(); 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 7307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// this flavor centers potential intersections recursively. In contrast, '2' may inadvertently 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// chase intersections near quadratic ends, requiring odd hacks to find them. 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDCubic& cubic2, 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t2s, double t2e, double precisionScale, SkIntersections& i) { 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.upDepth(); 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic c1 = cubic1.subDivide(t1s, t1e); 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic c2 = cubic2.subDivide(t2s, t2e); 81d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com SkSTArray<kCubicToQuadSubdivisionDepth, double, true> ts1; 8207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // OPTIMIZE: if c1 == c2, call once (happens when detecting self-intersection) 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1.toQuadraticTs(c1.calcPrecision() * precisionScale, &ts1); 84d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com SkSTArray<kCubicToQuadSubdivisionDepth, double, true> ts2; 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c2.toQuadraticTs(c2.calcPrecision() * precisionScale, &ts2); 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t1Start = t1s; 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int ts1Count = ts1.count(); 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int i1 = 0; i1 <= ts1Count; ++i1) { 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double tEnd1 = i1 < ts1Count ? ts1[i1] : 1; 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double t1 = t1s + (t1e - t1s) * tEnd1; 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkReduceOrder s1; 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int o1 = quadPart(cubic1, t1Start, t1, &s1); 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double t2Start = t2s; 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int ts2Count = ts2.count(); 9507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int i2 = 0; i2 <= ts2Count; ++i2) { 9607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double tEnd2 = i2 < ts2Count ? ts2[i2] : 1; 9707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double t2 = t2s + (t2e - t2s) * tEnd2; 9807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (&cubic1 == &cubic2 && t1Start >= t2Start) { 9907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t2Start = t2; 10007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 10107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkReduceOrder s2; 10307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int o2 = quadPart(cubic2, t2Start, t2, &s2); 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com char tab[] = " "; 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tLimits1[0][0] >= t1Start && tLimits1[0][1] <= t1 10707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && tLimits1[1][0] >= t2Start && tLimits1[1][1] <= t2) { 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()*2, tab, 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, t1Start, t1, t2Start, t2); 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections xlocals; 111570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com xlocals.allowNear(false); 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, xlocals); 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf(" xlocals.fUsed=%d\n", xlocals.used()); 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections locals; 117570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com locals.allowNear(false); 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals); 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int tCount = locals.used(); 12007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int tIdx = 0; tIdx < tCount; ++tIdx) { 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double to1 = t1Start + (t1 - t1Start) * locals[0][tIdx]; 12207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double to2 = t2Start + (t2 - t2Start) * locals[1][tIdx]; 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // if the computed t is not sufficiently precise, iterate 1244fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint p1 = cubic1.ptAtT(to1); 1254fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint p2 = cubic2.ptAtT(to2); 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (p1.approximatelyEqual(p2)) { 1277eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // FIXME: local edge may be coincident -- experiment with not propagating coincidence to caller 1287eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com// SkASSERT(!locals.isCoincident(tIdx)); 1294fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (&cubic1 != &cubic2 || !approximately_equal(to1, to2)) { 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (i.swapped()) { // FIXME: insert should respect swap 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.insert(to2, to1, p1); 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.insert(to1, to2, p1); 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 1374431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org/*for random cubics, 16 below catches 99.997% of the intersections. To test for the remaining 0.003% 1384431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org look for nearly coincident curves. and check each 1/16th section. 1394431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org*/ 1404431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double offset = precisionScale / 16; // FIXME: const is arbitrary: test, refine 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double c1Bottom = tIdx == 0 ? 0 : 14207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (t1Start + (t1 - t1Start) * locals[0][tIdx - 1] + to1) / 2; 1433b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com double c1Min = SkTMax(c1Bottom, to1 - offset); 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double c1Top = tIdx == tCount - 1 ? 1 : 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (t1Start + (t1 - t1Start) * locals[0][tIdx + 1] + to1) / 2; 1463b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com double c1Max = SkTMin(c1Top, to1 + offset); 1473b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com double c2Min = SkTMax(0., to2 - offset); 1483b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com double c2Max = SkTMin(1., to2 + offset); 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 1 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab, 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max, 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset, 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max, 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset); 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 1 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g" 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n", 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.depth()*2, tab, __FUNCTION__, c1Bottom, c1Top, 0., 1., 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset); 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 1 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g" 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min, 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Max, c2Min, c2Max); 16707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 16807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i); 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 1 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__, 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1); 17207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 17307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tCount > 1) { 1743b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com c1Min = SkTMax(0., to1 - offset); 1753b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com c1Max = SkTMin(1., to1 + offset); 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double c2Bottom = tIdx == 0 ? to2 : 17707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (t2Start + (t2 - t2Start) * locals[1][tIdx - 1] + to2) / 2; 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double c2Top = tIdx == tCount - 1 ? to2 : 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (t2Start + (t2 - t2Start) * locals[1][tIdx + 1] + to2) / 2; 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (c2Bottom > c2Top) { 18107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap(c2Bottom, c2Top); 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (c2Bottom == to2) { 18407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c2Bottom = 0; 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (c2Top == to2) { 18707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c2Top = 1; 18807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 1893b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com c2Min = SkTMax(c2Bottom, to2 - offset); 1903b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com c2Max = SkTMin(c2Top, to2 + offset); 19107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 19207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 2 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab, 19307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, 19407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max, 19607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset, 19807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max 19907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max, 20007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset 20107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset); 20207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 2 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g" 20307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n", 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top, 20507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset); 20607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 2 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g" 20707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min, 20807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Max, c2Min, c2Max); 20907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 21007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i); 21107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 2 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__, 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1); 21407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 2153b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com c1Min = SkTMax(c1Bottom, to1 - offset); 2163b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com c1Max = SkTMin(c1Top, to1 + offset); 21707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 21807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 3 contains1=%d/%d contains2=%d/%d\n", i.depth()*2, tab, 21907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com __FUNCTION__, 22007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Min <= tLimits1[0][1] && tLimits1[0][0] <= c1Max 22107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && c2Min <= tLimits1[1][1] && tLimits1[1][0] <= c2Max, 22207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset <= tLimits1[0][1] && tLimits1[0][0] <= to1 + offset 22307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && to2 - offset <= tLimits1[1][1] && tLimits1[1][0] <= to2 + offset, 22407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Min <= tLimits2[0][1] && tLimits2[0][0] <= c1Max 22507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && c2Min <= tLimits2[1][1] && tLimits2[1][0] <= c2Max, 22607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset <= tLimits2[0][1] && tLimits2[0][0] <= to1 + offset 22707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && to2 - offset <= tLimits2[1][1] && tLimits2[1][0] <= to2 + offset); 22807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 3 c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g" 22907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n", 23007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.depth()*2, tab, __FUNCTION__, 0., 1., c2Bottom, c2Top, 23107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset); 23207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 3 to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g" 23307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com " c2Max=%1.9g\n", i.depth()*2, tab, __FUNCTION__, to1, to2, c1Min, 23407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com c1Max, c2Min, c2Max); 23507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 23607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i); 23707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 23807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%.*s %s 3 i.used=%d t=%1.9g\n", i.depth()*2, tab, __FUNCTION__, 23907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1); 24007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 24107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 242fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i); 24307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME: if no intersection is found, either quadratics intersected where 24407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // cubics did not, or the intersection was missed. In the former case, expect 24507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // the quadratics to be nearly parallel at the point of intersection, and check 24607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // for that. 24707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 24807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 24907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t2Start = t2; 25007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 25107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com t1Start = t1; 25207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 25307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com i.downDepth(); 25407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 25507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2567eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // if two ends intersect, check middle for coincidence 2577eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.combool SkIntersections::cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2) { 2587eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (fUsed < 2) { 2597eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return false; 2607eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 2617eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int last = fUsed - 1; 2627eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double tRange1 = fT[0][last] - fT[0][0]; 2637eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double tRange2 = fT[1][last] - fT[1][0]; 2647eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com for (int index = 1; index < 5; ++index) { 2657eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double testT1 = fT[0][0] + tRange1 * index / 5; 2667eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double testT2 = fT[1][0] + tRange2 * index / 5; 2677eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkDPoint testPt1 = c1.ptAtT(testT1); 2687eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkDPoint testPt2 = c2.ptAtT(testT2); 2697eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (!testPt1.approximatelyEqual(testPt2)) { 2707eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return false; 2717eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 2727eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 2737eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (fUsed > 2) { 2747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fPt[1] = fPt[last]; 2757eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fT[0][1] = fT[0][last]; 2767eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fT[1][1] = fT[1][last]; 2777eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fUsed = 2; 2787eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 2797eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fIsCoincident[0] = fIsCoincident[1] = 0x03; 2807eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return true; 2817eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 2827eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 28307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define LINE_FRACTION 0.1 28407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 28507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// intersect the end of the cubic with the other. Try lines from the end to control and opposite 28607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// end to determine range of t on opposite cubic. 2877eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.combool SkIntersections::cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2) { 28807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int t1Index = start ? 0 : 3; 2894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double testT = (double) !start; 2907eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool swap = swapped(); 2914fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // quad/quad at this point checks to see if exact matches have already been found 2924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // cubic/cubic can't reject so easily since cubics can intersect same point more than once 2937eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkDLine tmpLine; 2947eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com tmpLine[0] = tmpLine[1] = cubic2[t1Index]; 2957eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY; 2967eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX; 2977eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkIntersections impTs; 298a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com impTs.allowNear(false); 2997eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com impTs.intersectRay(cubic1, tmpLine); 3007eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com for (int index = 0; index < impTs.used(); ++index) { 3017eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkDPoint realPt = impTs.pt(index); 3027eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (!tmpLine[0].approximatelyEqual(realPt)) { 3037eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com continue; 3047eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 3057eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (swap) { 306dac1d17027dcaa5596885a9f333979418b35001ccaryclark cubicInsert(testT, impTs[0][index], tmpLine[0], cubic2, cubic1); 3077eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } else { 308dac1d17027dcaa5596885a9f333979418b35001ccaryclark cubicInsert(impTs[0][index], testT, tmpLine[0], cubic1, cubic2); 3094fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 3107eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return true; 3114fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 3127eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return false; 3137eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 3147eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 315dac1d17027dcaa5596885a9f333979418b35001ccaryclark 316dac1d17027dcaa5596885a9f333979418b35001ccaryclarkvoid SkIntersections::cubicInsert(double one, double two, const SkDPoint& pt, 317dac1d17027dcaa5596885a9f333979418b35001ccaryclark const SkDCubic& cubic1, const SkDCubic& cubic2) { 318dac1d17027dcaa5596885a9f333979418b35001ccaryclark for (int index = 0; index < fUsed; ++index) { 319dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (fT[0][index] == one) { 320dac1d17027dcaa5596885a9f333979418b35001ccaryclark double oldTwo = fT[1][index]; 321dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (oldTwo == two) { 322dac1d17027dcaa5596885a9f333979418b35001ccaryclark return; 323dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 324dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDPoint mid = cubic2.ptAtT((oldTwo + two) / 2); 325dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (mid.approximatelyEqual(fPt[index])) { 326dac1d17027dcaa5596885a9f333979418b35001ccaryclark return; 327dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 328dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 329dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (fT[1][index] == two) { 330dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDPoint mid = cubic1.ptAtT((fT[0][index] + two) / 2); 331dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (mid.approximatelyEqual(fPt[index])) { 332dac1d17027dcaa5596885a9f333979418b35001ccaryclark return; 333dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 334dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 335dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 336dac1d17027dcaa5596885a9f333979418b35001ccaryclark insert(one, two, pt); 337dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 338dac1d17027dcaa5596885a9f333979418b35001ccaryclark 3397eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comvoid SkIntersections::cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, 3407eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com const SkDRect& bounds2) { 3417eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkDLine line; 3427eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int t1Index = start ? 0 : 3; 3437eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com double testT = (double) !start; 3447eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // don't bother if the two cubics are connnected 345d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com static const int kPointsInCubic = 4; // FIXME: move to DCubic, replace '4' with this 346d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com static const int kMaxLineCubicIntersections = 3; 347d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com SkSTArray<(kMaxLineCubicIntersections - 1) * kMaxLineCubicIntersections, double, true> tVals; 348a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com line[0] = cubic1[t1Index]; 349a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com // this variant looks for intersections with the end point and lines parallel to other points 350d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com for (int index = 0; index < kPointsInCubic; ++index) { 35107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (index == t1Index) { 35207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 35307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 35407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector dxy1 = cubic1[index] - line[0]; 35507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com dxy1 /= SkDCubic::gPrecisionUnit; 35607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line[1] = line[0] + dxy1; 35707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDRect lineBounds; 35807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com lineBounds.setBounds(line); 35907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!bounds2.intersects(&lineBounds)) { 36007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 36107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 36207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections local; 36307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (!local.intersect(cubic2, line)) { 36407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 36507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 36607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int idx2 = 0; idx2 < local.used(); ++idx2) { 36707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double foundT = local[0][idx2]; 36807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_less_than_zero(foundT) 36907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com || approximately_greater_than_one(foundT)) { 37007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 37107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 37207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (local.pt(idx2).approximatelyEqual(line[0])) { 3737eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (swapped()) { // FIXME: insert should respect swap 3747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert(foundT, testT, line[0]); 37507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 3767eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert(testT, foundT, line[0]); 37707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 37807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 379d892bd8ba676d34d4ce4a73ac7aad88e102fad70caryclark@google.com tVals.push_back(foundT); 38007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 38107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 38207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 38307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (tVals.count() == 0) { 38407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 38507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 386b76d3b677713693137936ff813b92c4be48af173commit-bot@chromium.org SkTQSort<double>(tVals.begin(), tVals.end() - 1); 38707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tMin1 = start ? 0 : 1 - LINE_FRACTION; 38807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double tMax1 = start ? LINE_FRACTION : 1; 38907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int tIdx = 0; 39007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com do { 39107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int tLast = tIdx; 39207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com while (tLast + 1 < tVals.count() && roughly_equal(tVals[tLast + 1], tVals[tIdx])) { 39307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++tLast; 39407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3953b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com double tMin2 = SkTMax(tVals[tIdx] - LINE_FRACTION, 0.0); 3963b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com double tMax2 = SkTMin(tVals[tLast] + LINE_FRACTION, 1.0); 3977eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int lastUsed = used(); 398dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (start ? tMax1 < tMin2 : tMax2 < tMin1) { 399dac1d17027dcaa5596885a9f333979418b35001ccaryclark ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); 400dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 4017eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (lastUsed == used()) { 4023b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com tMin2 = SkTMax(tVals[tIdx] - (1.0 / SkDCubic::gPrecisionUnit), 0.0); 4033b97af5add04489d57c7926ba6dc6f0013daf40fcaryclark@google.com tMax2 = SkTMin(tVals[tLast] + (1.0 / SkDCubic::gPrecisionUnit), 1.0); 404dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (start ? tMax1 < tMin2 : tMax2 < tMin1) { 405dac1d17027dcaa5596885a9f333979418b35001ccaryclark ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); 406dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 40707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 40807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com tIdx = tLast + 1; 40907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } while (tIdx < tVals.count()); 41007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 41107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 41207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 41307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comconst double CLOSE_ENOUGH = 0.001; 41407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 41507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool closeStart(const SkDCubic& cubic, int cubicIndex, SkIntersections& i, SkDPoint& pt) { 41607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (i[cubicIndex][0] != 0 || i[cubicIndex][1] > CLOSE_ENOUGH) { 41707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 41807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4194fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com pt = cubic.ptAtT((i[cubicIndex][0] + i[cubicIndex][1]) / 2); 42007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 42107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 42207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 42307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool closeEnd(const SkDCubic& cubic, int cubicIndex, SkIntersections& i, SkDPoint& pt) { 42407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int last = i.used() - 1; 42507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (i[cubicIndex][last] != 1 || i[cubicIndex][last - 1] < 1 - CLOSE_ENOUGH) { 42607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 42707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 4284fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com pt = cubic.ptAtT((i[cubicIndex][last] + i[cubicIndex][last - 1]) / 2); 42907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 43007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 43107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4324fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comstatic bool only_end_pts_in_common(const SkDCubic& c1, const SkDCubic& c2) { 4334fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com// the idea here is to see at minimum do a quick reject by rotating all points 4344fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com// to either side of the line formed by connecting the endpoints 4354fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com// if the opposite curves points are on the line or on the other side, the 4364fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com// curves at most intersect at the endpoints 4374fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int oddMan = 0; oddMan < 4; ++oddMan) { 4384fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com const SkDPoint* endPt[3]; 4394fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int opp = 1; opp < 4; ++opp) { 4404fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com int end = oddMan ^ opp; // choose a value not equal to oddMan 4414fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com endPt[opp - 1] = &c1[end]; 4424fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4434fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int triTest = 0; triTest < 3; ++triTest) { 4444fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double origX = endPt[triTest]->fX; 4454fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double origY = endPt[triTest]->fY; 4464fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com int oppTest = triTest + 1; 4474fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (3 == oppTest) { 4484fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com oppTest = 0; 4494fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4504fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double adj = endPt[oppTest]->fX - origX; 4514fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double opp = endPt[oppTest]->fY - origY; 452dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (adj == 0 && opp == 0) { // if the other point equals the test point, ignore it 453dac1d17027dcaa5596885a9f333979418b35001ccaryclark continue; 454dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 4554fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double sign = (c1[oddMan].fY - origY) * adj - (c1[oddMan].fX - origX) * opp; 4564fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (approximately_zero(sign)) { 4574fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com goto tryNextHalfPlane; 4584fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4594fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int n = 0; n < 4; ++n) { 4604fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double test = (c2[n].fY - origY) * adj - (c2[n].fX - origX) * opp; 4614fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (test * sign > 0 && !precisely_zero(test)) { 4624fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com goto tryNextHalfPlane; 4634fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4644fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4654fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4664fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return true; 4674fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.comtryNextHalfPlane: 4684fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com ; 4694fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4704fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return false; 4714fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com} 4724fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com 47307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { 4747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (fMax == 0) { 4757eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 9; 4767eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 4774fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com bool selfIntersect = &c1 == &c2; 4784fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (selfIntersect) { 4797eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (c1[0].approximatelyEqual(c1[3])) { 4804fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com insert(0, 1, c1[0]); 4817eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return fUsed; 4824fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4834fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } else { 484a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com // OPTIMIZATION: set exact end bits here to avoid cubic exact end later 4854fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int i1 = 0; i1 < 4; i1 += 3) { 4864fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com for (int i2 = 0; i2 < 4; i2 += 3) { 4877eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (c1[i1].approximatelyEqual(c2[i2])) { 4884fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com insert(i1 >> 1, i2 >> 1, c1[i1]); 4894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4904fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4914fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4934fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkASSERT(fUsed < 4); 4944fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (!selfIntersect) { 4954fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (only_end_pts_in_common(c1, c2)) { 4964fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fUsed; 4974fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 4984fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (only_end_pts_in_common(c2, c1)) { 4994fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fUsed; 5004fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 5014fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 5024fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // quad/quad does linear test here -- cubic does not 5034fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // cubics which are really lines should have been detected in reduce step earlier 5047eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com int exactEndBits = 0; 5054fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (selfIntersect) { 5064fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (fUsed) { 5074fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fUsed; 5084fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 5094fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } else { 5107eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com exactEndBits |= cubicExactEnd(c1, false, c2) << 0; 5117eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com exactEndBits |= cubicExactEnd(c1, true, c2) << 1; 51207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com swap(); 5137eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com exactEndBits |= cubicExactEnd(c2, false, c1) << 2; 5147eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com exactEndBits |= cubicExactEnd(c2, true, c1) << 3; 51507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com swap(); 51607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5177eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (cubicCheckCoincidence(c1, c2)) { 5184fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkASSERT(!selfIntersect); 5197eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return fUsed; 5207eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 5217eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // FIXME: pass in cached bounds from caller 522a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com SkDRect c2Bounds; 5237eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com c2Bounds.setBounds(c2); 524a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!(exactEndBits & 4)) { 5257eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com cubicNearEnd(c1, false, c2, c2Bounds); 5267eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 527a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!(exactEndBits & 8)) { 5288cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (selfIntersect && fUsed) { 5298cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return fUsed; 5308cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 5317eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com cubicNearEnd(c1, true, c2, c2Bounds); 5328cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (selfIntersect && fUsed && ((approximately_less_than_zero(fT[0][0]) 5338cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org && approximately_less_than_zero(fT[1][0])) 5348cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org || (approximately_greater_than_one(fT[0][0]) 5358cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org && approximately_greater_than_one(fT[1][0])))) { 5368cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org SkASSERT(fUsed == 1); 5378cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org fUsed = 0; 5388cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return fUsed; 5398cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 5407eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 5417eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (!selfIntersect) { 542a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com SkDRect c1Bounds; 543a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ? 5447eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com swap(); 545a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!(exactEndBits & 1)) { 5467eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com cubicNearEnd(c2, false, c1, c1Bounds); 5474fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 548a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!(exactEndBits & 2)) { 5497eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com cubicNearEnd(c2, true, c1, c1Bounds); 5504fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 5517eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com swap(); 5527eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 5537eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (cubicCheckCoincidence(c1, c2)) { 5547eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkASSERT(!selfIntersect); 5554fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fUsed; 5564fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 557a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com SkIntersections i; 558a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com i.fAllowNear = false; 559a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com i.fMax = 9; 560a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com ::intersect(c1, 0, 1, c2, 0, 1, 1, i); 561a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com int compCount = i.used(); 562a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (compCount) { 563a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com int exactCount = used(); 564a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (exactCount == 0) { 565dac1d17027dcaa5596885a9f333979418b35001ccaryclark *this = i; 566a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } else { 567a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com // at least one is exact or near, and at least one was computed. Eliminate duplicates 568a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com for (int exIdx = 0; exIdx < exactCount; ++exIdx) { 569a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com for (int cpIdx = 0; cpIdx < compCount; ) { 570a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (fT[0][0] == i[0][0] && fT[1][0] == i[1][0]) { 571a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com i.removeOne(cpIdx); 572a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com --compCount; 573a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com continue; 574a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 575a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com double tAvg = (fT[0][exIdx] + i[0][cpIdx]) / 2; 576a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com SkDPoint pt = c1.ptAtT(tAvg); 577a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!pt.approximatelyEqual(fPt[exIdx])) { 578a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com ++cpIdx; 579a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com continue; 580a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 581a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com tAvg = (fT[1][exIdx] + i[1][cpIdx]) / 2; 582a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com pt = c2.ptAtT(tAvg); 583a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!pt.approximatelyEqual(fPt[exIdx])) { 584a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com ++cpIdx; 585a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com continue; 586a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 587a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com i.removeOne(cpIdx); 588a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com --compCount; 589a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 590a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 591a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com // if mid t evaluates to nearly the same point, skip the t 592a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com for (int cpIdx = 0; cpIdx < compCount - 1; ) { 593a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com double tAvg = (fT[0][cpIdx] + i[0][cpIdx + 1]) / 2; 594a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com SkDPoint pt = c1.ptAtT(tAvg); 595a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!pt.approximatelyEqual(fPt[cpIdx])) { 596a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com ++cpIdx; 597a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com continue; 598a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 599a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com tAvg = (fT[1][cpIdx] + i[1][cpIdx + 1]) / 2; 600a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com pt = c2.ptAtT(tAvg); 601a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (!pt.approximatelyEqual(fPt[cpIdx])) { 602a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com ++cpIdx; 603a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com continue; 604a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 605a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com i.removeOne(cpIdx); 606a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com --compCount; 607a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 608a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com // in addition to adding below missing function, think about how to say 609a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com append(i); 610a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 611a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 61207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // If an end point and a second point very close to the end is returned, the second 61307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // point may have been detected because the approximate quads 61407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // intersected at the end and close to it. Verify that the second point is valid. 6154fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (fUsed <= 1) { 61607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 61707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 61807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint pt[2]; 61907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (closeStart(c1, 0, *this, pt[0]) && closeStart(c2, 1, *this, pt[1]) 62007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && pt[0].approximatelyEqual(pt[1])) { 62107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com removeOne(1); 62207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 62307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (closeEnd(c1, 0, *this, pt[0]) && closeEnd(c2, 1, *this, pt[1]) 62407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && pt[0].approximatelyEqual(pt[1])) { 62507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com removeOne(used() - 2); 62607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 627cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // vet the pairs of t values to see if the mid value is also on the curve. If so, mark 628cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // the span as coincident 629cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fUsed >= 2 && !coincidentUsed()) { 630cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int last = fUsed - 1; 631cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int match = 0; 632cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com for (int index = 0; index < last; ++index) { 633cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double mid1 = (fT[0][index] + fT[0][index + 1]) / 2; 634cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com double mid2 = (fT[1][index] + fT[1][index + 1]) / 2; 6354fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com pt[0] = c1.ptAtT(mid1); 6364fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com pt[1] = c2.ptAtT(mid2); 637cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (pt[0].approximatelyEqual(pt[1])) { 638cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com match |= 1 << index; 639cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 640cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 641cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (match) { 6427eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com#if DEBUG_CONCIDENT 643cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (((match + 1) & match) != 0) { 644cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com SkDebugf("%s coincident hole\n", __FUNCTION__); 645cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 6467eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com#endif 647cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // for now, assume that everything from start to finish is coincident 648cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (fUsed > 2) { 649cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fPt[1] = fPt[last]; 650cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fT[0][1] = fT[0][last]; 651cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fT[1][1] = fT[1][last]; 652cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fIsCoincident[0] = 0x03; 653cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fIsCoincident[1] = 0x03; 654cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fUsed = 2; 655cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 656cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 657cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 65807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 65907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 66007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 66107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Up promote the quad to a cubic. 66207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// OPTIMIZATION If this is a common use case, optimize by duplicating 66307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// the intersect 3 loop to avoid the promotion / demotion code 66407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) { 6657eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 6; 66607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic up = quad.toCubic(); 66707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (void) intersect(cubic, up); 66807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return used(); 66907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 67007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 67107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* http://www.ag.jku.at/compass/compasssample.pdf 67207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com( Self-Intersection Problems and Approximate Implicitization by Jan B. Thomassen 67307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comCentre of Mathematics for Applications, University of Oslo http://www.cma.uio.no janbth@math.uio.no 67407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSINTEF Applied Mathematics http://www.sintef.no ) 67507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comdescribes a method to find the self intersection of a cubic by taking the gradient of the implicit 67607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comform dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/ 67707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 67807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::intersect(const SkDCubic& c) { 6797eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 1; 68007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // check to see if x or y end points are the extrema. Are other quick rejects possible? 68107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (c.endsAreExtremaInXOrY()) { 68207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 68307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 684e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark // OPTIMIZATION: could quick reject if neither end point tangent ray intersected the line 685e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark // segment formed by the opposite end point to the control point 68607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (void) intersect(c, c); 68707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (used() > 0) { 688e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark if (approximately_equal_double(fT[0][0], fT[1][0])) { 689e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark fUsed = 0; 690e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } else { 691e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark SkASSERT(used() == 1); 692e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark if (fT[0][0] > fT[1][0]) { 693e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark swapPts(); 694e4097e3a0b10bb0047a45b6949ca01826f0807a7caryclark } 69507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 69607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 69707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return used(); 69807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 699