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 #include "SkPathOpsCubic.h" 8 #include "SkPathOpsLine.h" 9 #include "SkPathOpsQuad.h" 10 11 // Sources 12 // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549 13 // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 14 15 // This turns a line segment into a parameterized line, of the form 16 // ax + by + c = 0 17 // When a^2 + b^2 == 1, the line is normalized. 18 // The distance to the line for (x, y) is d(x,y) = ax + by + c 19 // 20 // Note that the distances below are not necessarily normalized. To get the true 21 // distance, it's necessary to either call normalize() after xxxEndPoints(), or 22 // divide the result of xxxDistance() by sqrt(normalSquared()) 23 24 class SkLineParameters { 25 public: 26 27 bool cubicEndPoints(const SkDCubic& pts) { 28 int endIndex = 1; 29 cubicEndPoints(pts, 0, endIndex); 30 if (dy() != 0) { 31 return true; 32 } 33 if (dx() == 0) { 34 cubicEndPoints(pts, 0, ++endIndex); 35 SkASSERT(endIndex == 2); 36 if (dy() != 0) { 37 return true; 38 } 39 if (dx() == 0) { 40 cubicEndPoints(pts, 0, ++endIndex); // line 41 SkASSERT(endIndex == 3); 42 return false; 43 } 44 } 45 // FIXME: after switching to round sort, remove bumping fA 46 if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie 47 return true; 48 } 49 // if cubic tangent is on x axis, look at next control point to break tie 50 // control point may be approximate, so it must move significantly to account for error 51 if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) { 52 if (pts[0].fY > pts[endIndex].fY) { 53 fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) 54 } 55 return true; 56 } 57 if (endIndex == 3) { 58 return true; 59 } 60 SkASSERT(endIndex == 2); 61 if (pts[0].fY > pts[3].fY) { 62 fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) 63 } 64 return true; 65 } 66 67 void cubicEndPoints(const SkDCubic& pts, int s, int e) { 68 fA = pts[s].fY - pts[e].fY; 69 fB = pts[e].fX - pts[s].fX; 70 fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; 71 } 72 73 double cubicPart(const SkDCubic& part) { 74 cubicEndPoints(part); 75 if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) { 76 return pointDistance(part[3]); 77 } 78 return pointDistance(part[2]); 79 } 80 81 void lineEndPoints(const SkDLine& pts) { 82 fA = pts[0].fY - pts[1].fY; 83 fB = pts[1].fX - pts[0].fX; 84 fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; 85 } 86 87 bool quadEndPoints(const SkDQuad& pts) { 88 quadEndPoints(pts, 0, 1); 89 if (dy() != 0) { 90 return true; 91 } 92 if (dx() == 0) { 93 quadEndPoints(pts, 0, 2); 94 return false; 95 } 96 if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie 97 return true; 98 } 99 // FIXME: after switching to round sort, remove this 100 if (pts[0].fY > pts[2].fY) { 101 fA = DBL_EPSILON; 102 } 103 return true; 104 } 105 106 void quadEndPoints(const SkDQuad& pts, int s, int e) { 107 fA = pts[s].fY - pts[e].fY; 108 fB = pts[e].fX - pts[s].fX; 109 fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; 110 } 111 112 double quadPart(const SkDQuad& part) { 113 quadEndPoints(part); 114 return pointDistance(part[2]); 115 } 116 117 double normalSquared() const { 118 return fA * fA + fB * fB; 119 } 120 121 bool normalize() { 122 double normal = sqrt(normalSquared()); 123 if (approximately_zero(normal)) { 124 fA = fB = fC = 0; 125 return false; 126 } 127 double reciprocal = 1 / normal; 128 fA *= reciprocal; 129 fB *= reciprocal; 130 fC *= reciprocal; 131 return true; 132 } 133 134 void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const { 135 double oneThird = 1 / 3.0; 136 for (int index = 0; index < 4; ++index) { 137 distance[index].fX = index * oneThird; 138 distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; 139 } 140 } 141 142 void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const { 143 double oneHalf = 1 / 2.0; 144 for (int index = 0; index < 3; ++index) { 145 distance[index].fX = index * oneHalf; 146 distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; 147 } 148 } 149 150 double controlPtDistance(const SkDCubic& pts, int index) const { 151 SkASSERT(index == 1 || index == 2); 152 return fA * pts[index].fX + fB * pts[index].fY + fC; 153 } 154 155 double controlPtDistance(const SkDQuad& pts) const { 156 return fA * pts[1].fX + fB * pts[1].fY + fC; 157 } 158 159 double pointDistance(const SkDPoint& pt) const { 160 return fA * pt.fX + fB * pt.fY + fC; 161 } 162 163 double dx() const { 164 return fB; 165 } 166 167 double dy() const { 168 return -fA; 169 } 170 171 private: 172 double fA; 173 double fB; 174 double fC; 175 }; 176
