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 | |
| 14 | struct SkDCubicPair { |
| 15 | const SkDCubic& first() const { return (const SkDCubic&) pts[0]; } |
| 16 | const SkDCubic& second() const { return (const SkDCubic&) pts[3]; } |
| 17 | SkDPoint pts[7]; |
| 18 | }; |
| 19 | |
| 20 | struct SkDCubic { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 21 | static const int kPointCount = 4; |
| 22 | static const int kPointLast = kPointCount - 1; |
| 23 | static const int kMaxIntersections = 9; |
| 24 | |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 25 | enum SearchAxis { |
| 26 | kXAxis, |
| 27 | kYAxis |
| 28 | }; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 29 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 30 | bool collapsed() const { |
| 31 | return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]) |
| 32 | && fPts[0].approximatelyEqual(fPts[3]); |
| 33 | } |
| 34 | |
| 35 | bool controlsInside() const { |
| 36 | SkDVector v01 = fPts[0] - fPts[1]; |
| 37 | SkDVector v02 = fPts[0] - fPts[2]; |
| 38 | SkDVector v03 = fPts[0] - fPts[3]; |
| 39 | SkDVector v13 = fPts[1] - fPts[3]; |
| 40 | SkDVector v23 = fPts[2] - fPts[3]; |
| 41 | return v03.dot(v01) > 0 && v03.dot(v02) > 0 && v03.dot(v13) > 0 && v03.dot(v23) > 0; |
| 42 | } |
| 43 | |
caryclark | ed0935a | 2015-10-22 07:23:52 -0700 | [diff] [blame] | 44 | static bool IsConic() { return false; } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 45 | |
| 46 | const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } |
| 47 | 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] | 48 | |
skia.committer@gmail.com | 8f6ef40 | 2013-06-05 07:01:06 +0000 | [diff] [blame] | 49 | void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const; |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 50 | double binarySearch(double min, double max, double axisIntercept, SearchAxis xAxis) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 51 | double calcPrecision() const; |
| 52 | SkDCubicPair chopAt(double t) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 53 | static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D); |
caryclark | 6ff734b | 2015-09-04 05:00:15 -0700 | [diff] [blame] | 54 | static bool ComplexBreak(const SkPoint pts[4], SkScalar* t); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 55 | int convexHull(char order[kPointCount]) const; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 56 | |
| 57 | void debugInit() { |
| 58 | sk_bzero(fPts, sizeof(fPts)); |
| 59 | } |
| 60 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 61 | void dump() const; // callable from the debugger when the implementation code is linked in |
| 62 | void dumpID(int id) const; |
| 63 | void dumpInner() const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 64 | SkDVector dxdyAtT(double t) const; |
| 65 | bool endsAreExtremaInXOrY() const; |
caryclark | aec2510 | 2015-04-29 08:28:30 -0700 | [diff] [blame] | 66 | static int FindExtrema(const double src[], double tValue[2]); |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 67 | int findInflections(double tValues[2]) const; |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 68 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 69 | static int FindInflections(const SkPoint a[kPointCount], double tValues[2]) { |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 70 | SkDCubic cubic; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 71 | return cubic.set(a).findInflections(tValues); |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 72 | } |
| 73 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 74 | int findMaxCurvature(double tValues[]) const; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 75 | bool hullIntersects(const SkDCubic& c2, bool* isLinear) const; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 76 | bool hullIntersects(const SkDConic& c, bool* isLinear) const; |
| 77 | bool hullIntersects(const SkDQuad& c2, bool* isLinear) const; |
| 78 | bool hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 79 | bool isLinear(int startIndex, int endIndex) const; |
caryclark | aec2510 | 2015-04-29 08:28:30 -0700 | [diff] [blame] | 80 | bool monotonicInX() const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 81 | bool monotonicInY() const; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 82 | void otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const; |
caryclark@google.com | 4fdbb22 | 2013-07-23 15:27:41 +0000 | [diff] [blame] | 83 | SkDPoint ptAtT(double t) const; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 84 | static int RootsReal(double A, double B, double C, double D, double t[3]); |
| 85 | 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] | 86 | |
| 87 | int searchRoots(double extremes[6], int extrema, double axisIntercept, |
| 88 | SearchAxis xAxis, double* validRoots) const; |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 89 | |
reed | dc30885 | 2015-04-30 07:47:13 -0700 | [diff] [blame] | 90 | /** |
| 91 | * Return the number of valid roots (0 < root < 1) for this cubic intersecting the |
| 92 | * specified horizontal line. |
| 93 | */ |
| 94 | int horizontalIntersect(double yIntercept, double roots[3]) const; |
| 95 | /** |
| 96 | * Return the number of valid roots (0 < root < 1) for this cubic intersecting the |
| 97 | * specified vertical line. |
| 98 | */ |
| 99 | int verticalIntersect(double xIntercept, double roots[3]) const; |
| 100 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 101 | const SkDCubic& set(const SkPoint pts[kPointCount]) { |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 102 | fPts[0] = pts[0]; |
| 103 | fPts[1] = pts[1]; |
| 104 | fPts[2] = pts[2]; |
| 105 | fPts[3] = pts[3]; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 106 | return *this; |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 107 | } |
| 108 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 109 | SkDCubic subDivide(double t1, double t2) const; |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 110 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 111 | static SkDCubic SubDivide(const SkPoint a[kPointCount], double t1, double t2) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 112 | SkDCubic cubic; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 113 | return cubic.set(a).subDivide(t1, t2); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 114 | } |
caryclark@google.com | b3f0921 | 2013-04-17 15:49:16 +0000 | [diff] [blame] | 115 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 116 | void subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint p[2]) const; |
| 117 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 118 | 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] | 119 | double t2, SkDPoint p[2]) { |
| 120 | SkDCubic cubic; |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 121 | cubic.set(pts).subDivide(a, d, t1, t2, p); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 122 | } |
| 123 | |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 124 | 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] | 125 | SkDQuad toQuad() const; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 126 | |
commit-bot@chromium.org | 2db7fe7 | 2014-05-07 15:31:40 +0000 | [diff] [blame] | 127 | static const int gPrecisionUnit; |
| 128 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 129 | SkDPoint fPts[kPointCount]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 130 | }; |
| 131 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 132 | /* Given the set [0, 1, 2, 3], and two of the four members, compute an XOR mask |
| 133 | that computes the other two. Note that: |
| 134 | |
| 135 | one ^ two == 3 for (0, 3), (1, 2) |
| 136 | one ^ two < 3 for (0, 1), (0, 2), (1, 3), (2, 3) |
| 137 | 3 - (one ^ two) is either 0, 1, or 2 |
| 138 | 1 >> (3 - (one ^ two)) is either 0 or 1 |
| 139 | thus: |
| 140 | returned == 2 for (0, 3), (1, 2) |
| 141 | returned == 3 for (0, 1), (0, 2), (1, 3), (2, 3) |
| 142 | given that: |
| 143 | (0, 3) ^ 2 -> (2, 1) (1, 2) ^ 2 -> (3, 0) |
| 144 | (0, 1) ^ 3 -> (3, 2) (0, 2) ^ 3 -> (3, 1) (1, 3) ^ 3 -> (2, 0) (2, 3) ^ 3 -> (1, 0) |
| 145 | */ |
| 146 | inline int other_two(int one, int two) { |
| 147 | return 1 >> (3 - (one ^ two)) ^ 3; |
| 148 | } |
| 149 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 150 | #endif |