caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
| 8 | #ifndef SkPathOpsCubic_DEFINED |
| 9 | #define SkPathOpsCubic_DEFINED |
| 10 | |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 11 | #include "SkPath.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 12 | #include "SkPathOpsPoint.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 13 | |
caryclark | 4209dcb | 2016-10-20 10:11:27 -0700 | [diff] [blame] | 14 | struct SkDCubicPair; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 15 | |
| 16 | struct SkDCubic { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 17 | static const int kPointCount = 4; |
| 18 | static const int kPointLast = kPointCount - 1; |
| 19 | static const int kMaxIntersections = 9; |
| 20 | |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 21 | enum SearchAxis { |
| 22 | kXAxis, |
| 23 | kYAxis |
| 24 | }; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 25 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 26 | bool collapsed() const { |
| 27 | return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]) |
| 28 | && fPts[0].approximatelyEqual(fPts[3]); |
| 29 | } |
| 30 | |
| 31 | bool controlsInside() const { |
| 32 | SkDVector v01 = fPts[0] - fPts[1]; |
| 33 | SkDVector v02 = fPts[0] - fPts[2]; |
| 34 | SkDVector v03 = fPts[0] - fPts[3]; |
| 35 | SkDVector v13 = fPts[1] - fPts[3]; |
| 36 | SkDVector v23 = fPts[2] - fPts[3]; |
| 37 | return v03.dot(v01) > 0 && v03.dot(v02) > 0 && v03.dot(v13) > 0 && v03.dot(v23) > 0; |
| 38 | } |
| 39 | |
caryclark | ed0935a | 2015-10-22 07:23:52 -0700 | [diff] [blame] | 40 | static bool IsConic() { return false; } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 41 | |
| 42 | const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } |
| 43 | SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 44 | |
skia.committer@gmail.com | 8f6ef40 | 2013-06-05 07:01:06 +0000 | [diff] [blame] | 45 | void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const; |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 46 | double binarySearch(double min, double max, double axisIntercept, SearchAxis xAxis) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 47 | double calcPrecision() const; |
| 48 | SkDCubicPair chopAt(double t) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 49 | static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D); |
Cary Clark | 7eb01e0 | 2016-12-08 14:36:32 -0500 | [diff] [blame] | 50 | static int ComplexBreak(const SkPoint pts[4], SkScalar* t); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 51 | int convexHull(char order[kPointCount]) const; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 52 | |
| 53 | void debugInit() { |
| 54 | sk_bzero(fPts, sizeof(fPts)); |
| 55 | } |
| 56 | |
caryclark | a35ab3e | 2016-10-20 08:32:18 -0700 | [diff] [blame] | 57 | void debugSet(const SkDPoint* pts); |
| 58 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 59 | void dump() const; // callable from the debugger when the implementation code is linked in |
| 60 | void dumpID(int id) const; |
| 61 | void dumpInner() const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 62 | SkDVector dxdyAtT(double t) const; |
| 63 | bool endsAreExtremaInXOrY() const; |
caryclark | aec2510 | 2015-04-29 08:28:30 -0700 | [diff] [blame] | 64 | static int FindExtrema(const double src[], double tValue[2]); |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 65 | int findInflections(double tValues[2]) const; |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 66 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 67 | static int FindInflections(const SkPoint a[kPointCount], double tValues[2]) { |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 68 | SkDCubic cubic; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 69 | return cubic.set(a).findInflections(tValues); |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 70 | } |
| 71 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 72 | int findMaxCurvature(double tValues[]) const; |
caryclark | a35ab3e | 2016-10-20 08:32:18 -0700 | [diff] [blame] | 73 | |
| 74 | #ifdef SK_DEBUG |
| 75 | SkOpGlobalState* globalState() const { return fDebugGlobalState; } |
| 76 | #endif |
| 77 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 78 | bool hullIntersects(const SkDCubic& c2, bool* isLinear) const; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 79 | bool hullIntersects(const SkDConic& c, bool* isLinear) const; |
| 80 | bool hullIntersects(const SkDQuad& c2, bool* isLinear) const; |
| 81 | bool hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 82 | bool isLinear(int startIndex, int endIndex) const; |
caryclark | aec2510 | 2015-04-29 08:28:30 -0700 | [diff] [blame] | 83 | bool monotonicInX() const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 84 | bool monotonicInY() const; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 85 | void otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const; |
caryclark@google.com | 4fdbb22 | 2013-07-23 15:27:41 +0000 | [diff] [blame] | 86 | SkDPoint ptAtT(double t) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 87 | static int RootsReal(double A, double B, double C, double D, double t[3]); |
| 88 | static int RootsValidT(const double A, const double B, const double C, double D, double s[3]); |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 89 | |
| 90 | int searchRoots(double extremes[6], int extrema, double axisIntercept, |
| 91 | SearchAxis xAxis, double* validRoots) const; |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 92 | |
Cary Clark | 7eb01e0 | 2016-12-08 14:36:32 -0500 | [diff] [blame] | 93 | bool toFloatPoints(SkPoint* ) const; |
reed | dc30885 | 2015-04-30 07:47:13 -0700 | [diff] [blame] | 94 | /** |
| 95 | * Return the number of valid roots (0 < root < 1) for this cubic intersecting the |
| 96 | * specified horizontal line. |
| 97 | */ |
| 98 | int horizontalIntersect(double yIntercept, double roots[3]) const; |
| 99 | /** |
| 100 | * Return the number of valid roots (0 < root < 1) for this cubic intersecting the |
| 101 | * specified vertical line. |
| 102 | */ |
| 103 | int verticalIntersect(double xIntercept, double roots[3]) const; |
| 104 | |
caryclark | a35ab3e | 2016-10-20 08:32:18 -0700 | [diff] [blame] | 105 | // add debug only global pointer so asserts can be skipped by fuzzers |
| 106 | const SkDCubic& set(const SkPoint pts[kPointCount] |
| 107 | SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) { |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 108 | fPts[0] = pts[0]; |
| 109 | fPts[1] = pts[1]; |
| 110 | fPts[2] = pts[2]; |
| 111 | fPts[3] = pts[3]; |
caryclark | a35ab3e | 2016-10-20 08:32:18 -0700 | [diff] [blame] | 112 | SkDEBUGCODE(fDebugGlobalState = state); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 113 | return *this; |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 114 | } |
| 115 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 116 | SkDCubic subDivide(double t1, double t2) const; |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 117 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 118 | static SkDCubic SubDivide(const SkPoint a[kPointCount], double t1, double t2) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 119 | SkDCubic cubic; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 120 | return cubic.set(a).subDivide(t1, t2); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 121 | } |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 122 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 123 | void subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint p[2]) const; |
| 124 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 125 | static void SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& d, double t1, |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 126 | double t2, SkDPoint p[2]) { |
| 127 | SkDCubic cubic; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 128 | cubic.set(pts).subDivide(a, d, t1, t2, p); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 129 | } |
| 130 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 131 | double top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 132 | SkDQuad toQuad() const; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 133 | |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 134 | static const int gPrecisionUnit; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 135 | SkDPoint fPts[kPointCount]; |
caryclark | a35ab3e | 2016-10-20 08:32:18 -0700 | [diff] [blame] | 136 | SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 137 | }; |
| 138 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 139 | /* Given the set [0, 1, 2, 3], and two of the four members, compute an XOR mask |
| 140 | that computes the other two. Note that: |
| 141 | |
| 142 | one ^ two == 3 for (0, 3), (1, 2) |
| 143 | one ^ two < 3 for (0, 1), (0, 2), (1, 3), (2, 3) |
| 144 | 3 - (one ^ two) is either 0, 1, or 2 |
| 145 | 1 >> (3 - (one ^ two)) is either 0 or 1 |
| 146 | thus: |
| 147 | returned == 2 for (0, 3), (1, 2) |
| 148 | returned == 3 for (0, 1), (0, 2), (1, 3), (2, 3) |
| 149 | given that: |
| 150 | (0, 3) ^ 2 -> (2, 1) (1, 2) ^ 2 -> (3, 0) |
| 151 | (0, 1) ^ 3 -> (3, 2) (0, 2) ^ 3 -> (3, 1) (1, 3) ^ 3 -> (2, 0) (2, 3) ^ 3 -> (1, 0) |
| 152 | */ |
| 153 | inline int other_two(int one, int two) { |
| 154 | return 1 >> (3 - (one ^ two)) ^ 3; |
| 155 | } |
| 156 | |
caryclark | 4209dcb | 2016-10-20 10:11:27 -0700 | [diff] [blame] | 157 | struct SkDCubicPair { |
| 158 | const SkDCubic first() const { |
| 159 | #ifdef SK_DEBUG |
| 160 | SkDCubic result; |
| 161 | result.debugSet(&pts[0]); |
| 162 | return result; |
| 163 | #else |
| 164 | return (const SkDCubic&) pts[0]; |
| 165 | #endif |
| 166 | } |
| 167 | const SkDCubic second() const { |
| 168 | #ifdef SK_DEBUG |
| 169 | SkDCubic result; |
| 170 | result.debugSet(&pts[3]); |
| 171 | return result; |
| 172 | #else |
| 173 | return (const SkDCubic&) pts[3]; |
| 174 | #endif |
| 175 | } |
| 176 | SkDPoint pts[7]; |
| 177 | }; |
| 178 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 179 | #endif |