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