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#ifndef SkIntersections_DEFINE 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#define SkIntersections_DEFINE 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCubic.h" 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsPoint.h" 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsQuad.h" 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comclass SkIntersections { 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.compublic: 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkIntersections() 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com : fSwap(0) 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#ifdef SK_DEBUG 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com , fDepth(0) 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com { 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com sk_bzero(fPt, sizeof(fPt)); 24dac1d17027dcaa5596885a9f333979418b35001ccaryclark sk_bzero(fPt2, sizeof(fPt2)); 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com sk_bzero(fT, sizeof(fT)); 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com sk_bzero(fIsCoincident, sizeof(fIsCoincident)); 27dac1d17027dcaa5596885a9f333979418b35001ccaryclark sk_bzero(fNearlySame, sizeof(fNearlySame)); 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com reset(); 297eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 0; // require that the caller set the max 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com class TArray { 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com public: 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com explicit TArray(const double ts[9]) : fTArray(ts) {} 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double operator[](int n) const { 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fTArray[n]; 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const double* fTArray; 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com }; 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com TArray operator[](int n) const { return TArray(fT[n]); } 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 42fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void allowNear(bool nearAllowed) { 43fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fAllowNear = nearAllowed; 44fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 45fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int cubic(const SkPoint a[4]) { 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic cubic; 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic.set(a); 497eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 1; // self intersect 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return intersect(cubic); 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int cubicCubic(const SkPoint a[4], const SkPoint b[4]) { 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic aCubic; 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com aCubic.set(a); 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic bCubic; 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bCubic.set(b); 587eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 9; 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return intersect(aCubic, bCubic); 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y, 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool flipped) { 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic cubic; 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic.set(a); 667eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 3; 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return horizontal(cubic, left, right, y, flipped); 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic cubic; 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic.set(a); 737eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 3; 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return vertical(cubic, top, bottom, x, flipped); 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int cubicLine(const SkPoint a[4], const SkPoint b[2]) { 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic cubic; 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic.set(a); 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine line; 8107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line.set(b); 827eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 3; 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return intersect(cubic, line); 8407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int cubicQuad(const SkPoint a[4], const SkPoint b[3]) { 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDCubic cubic; 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com cubic.set(a); 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad quad; 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad.set(b); 917eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 6; 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return intersect(cubic, quad); 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 95fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com bool hasT(double t) const { 96fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkASSERT(t == 0 || t == 1); 97fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1); 98fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 99fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 10007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int insertSwap(double one, double two, const SkDPoint& pt) { 10107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fSwap) { 10207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return insert(two, one, pt); 10307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } else { 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return insert(one, two, pt); 10507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool isCoincident(int index) { 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return (fIsCoincident[0] & 1 << index) != 0; 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y, 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool flipped) { 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine line; 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line.set(a); 1167eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return horizontal(line, left, right, y, flipped); 11807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 12007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine line; 12207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line.set(a); 1237eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return vertical(line, top, bottom, x, flipped); 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int lineLine(const SkPoint a[2], const SkPoint b[2]) { 12807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine aLine, bLine; 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com aLine.set(a); 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bLine.set(b); 1317eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return intersect(aLine, bLine); 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 135dac1d17027dcaa5596885a9f333979418b35001ccaryclark bool nearlySame(int index) const { 136dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(index == 0 || index == 1); 137dac1d17027dcaa5596885a9f333979418b35001ccaryclark return fNearlySame[index]; 138dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 139dac1d17027dcaa5596885a9f333979418b35001ccaryclark 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com const SkDPoint& pt(int index) const { 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fPt[index]; 14207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 144dac1d17027dcaa5596885a9f333979418b35001ccaryclark const SkDPoint& pt2(int index) const { 145dac1d17027dcaa5596885a9f333979418b35001ccaryclark return fPt2[index]; 146dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 147dac1d17027dcaa5596885a9f333979418b35001ccaryclark 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y, 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool flipped) { 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad quad; 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad.set(a); 1527eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return horizontal(quad, left, right, y, flipped); 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad quad; 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad.set(a); 1597eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return vertical(quad, top, bottom, x, flipped); 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int quadLine(const SkPoint a[3], const SkPoint b[2]) { 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad quad; 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad.set(a); 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDLine line; 16707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com line.set(b); 1688cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org fMax = 3; // 2; permit small coincident segment + non-coincident intersection 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return intersect(quad, line); 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 17207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int quadQuad(const SkPoint a[3], const SkPoint b[3]) { 17307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad aQuad; 17407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com aQuad.set(a); 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDQuad bQuad; 17607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bQuad.set(b); 1777eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 4; 17807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return intersect(aQuad, bQuad); 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 181dac1d17027dcaa5596885a9f333979418b35001ccaryclark // leaves swap, max alone 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void reset() { 183fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fAllowNear = true; 18407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fUsed = 0; 18507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 187dac1d17027dcaa5596885a9f333979418b35001ccaryclark void set(bool swap, int tIndex, double t) { 188dac1d17027dcaa5596885a9f333979418b35001ccaryclark fT[(int) swap][tIndex] = t; 189dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 190dac1d17027dcaa5596885a9f333979418b35001ccaryclark 1917eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com void setMax(int max) { 1927eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = max; 1937eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 1947eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void swap() { 19607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fSwap ^= true; 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 19807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void swapPts(); 20007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 20107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool swapped() const { 20207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fSwap; 20307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 20507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int used() const { 20607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fUsed; 20707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 20807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 20907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void downDepth() { 21007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(--fDepth >= 0); 21107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void upDepth() { 21407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(++fDepth < 16); 21507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 217a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com void append(const SkIntersections& ); 2187eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com void cleanUpCoincidence(); 21907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int coincidentUsed() const; 220dac1d17027dcaa5596885a9f333979418b35001ccaryclark void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1, 221dac1d17027dcaa5596885a9f333979418b35001ccaryclark const SkDCubic& c2); 22207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int cubicRay(const SkPoint pts[4], const SkDLine& line); 22307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void flip(); 22407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontal(const SkDLine&, double y); 22507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontal(const SkDLine&, double left, double right, double y, bool flipped); 22607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontal(const SkDQuad&, double left, double right, double y, bool flipped); 22707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]); 22807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontal(const SkDCubic&, double y, double tRange[3]); 22907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontal(const SkDCubic&, double left, double right, double y, bool flipped); 23007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]); 23107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // FIXME : does not respect swap 23207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int insert(double one, double two, const SkDPoint& pt); 233dac1d17027dcaa5596885a9f333979418b35001ccaryclark void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2); 23407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // start if index == 0 : end if index == 1 23507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void insertCoincident(double one, double two, const SkDPoint& pt); 23607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect(const SkDLine&, const SkDLine&); 23707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect(const SkDQuad&, const SkDLine&); 23807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect(const SkDQuad&, const SkDQuad&); 23907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect(const SkDCubic&); // return true if cubic self-intersects 24007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect(const SkDCubic&, const SkDLine&); 24107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect(const SkDCubic&, const SkDQuad&); 24207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect(const SkDCubic&, const SkDCubic&); 243cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int intersectRay(const SkDLine&, const SkDLine&); 244cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int intersectRay(const SkDQuad&, const SkDLine&); 245cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int intersectRay(const SkDCubic&, const SkDLine&); 246cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com static SkDPoint Line(const SkDLine&, const SkDLine&); 247a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com int lineRay(const SkPoint pts[2], const SkDLine& line); 24807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void offset(int base, double start, double end); 24907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void quickRemoveOne(int index, int replace); 250a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com int quadRay(const SkPoint pts[3], const SkDLine& line); 251a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com void removeOne(int index); 25207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com static bool Test(const SkDLine& , const SkDLine&); 25307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int vertical(const SkDLine&, double x); 25407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int vertical(const SkDLine&, double top, double bottom, double x, bool flipped); 25507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped); 25607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped); 25707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped); 25807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped); 25907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped); 26007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 26107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int depth() const { 26207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#ifdef SK_DEBUG 26307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return fDepth; 26407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#else 26507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return 0; 26607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 26707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 26807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 26907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comprivate: 2707eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2); 2717eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2); 2727eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& ); 2737eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com void cleanUpParallelLines(bool parallel); 2747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com void computePoints(const SkDLine& line, int used); 27507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 276570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also 277dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkDPoint fPt2[9]; // used by nearly same to store alternate intersection point 27807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double fT[2][9]; 279570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com uint16_t fIsCoincident[2]; // bit set for each curve's coincident T 280dac1d17027dcaa5596885a9f333979418b35001ccaryclark bool fNearlySame[2]; // true if end points nearly match 28107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com unsigned char fUsed; 2827eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com unsigned char fMax; 283fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com bool fAllowNear; 28407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool fSwap; 28507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#ifdef SK_DEBUG 28607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int fDepth; 28707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 28807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 28907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2902e40381060794745562c4a26896970406114b07acaryclarkextern int (SkIntersections::* const CurveRay[])(const SkPoint[], const SkDLine& ); 2912e40381060794745562c4a26896970406114b07acaryclarkextern int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar top, SkScalar bottom, 29207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkScalar x, bool flipped); 29307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 29407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#endif 295