| OLD | NEW |
|---|
| (Empty) |
| 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 "CurveIntersection.h" | |
| 8 #include "Extrema.h" | |
| 9 #include "IntersectionUtilities.h" | |
| 10 #include "LineParameters.h" | |
| 11 | |
| 12 static double interp_cubic_coords(const double* src, double t) | |
| 13 { | |
| 14 double ab = interp(src[0], src[2], t); | |
| 15 double bc = interp(src[2], src[4], t); | |
| 16 double cd = interp(src[4], src[6], t); | |
| 17 double abc = interp(ab, bc, t); | |
| 18 double bcd = interp(bc, cd, t); | |
| 19 return interp(abc, bcd, t); | |
| 20 } | |
| 21 | |
| 22 static int coincident_line(const Cubic& cubic, Cubic& reduction) { | |
| 23 reduction[0] = reduction[1] = cubic[0]; | |
| 24 return 1; | |
| 25 } | |
| 26 | |
| 27 static int vertical_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, Cub
ic& reduction) { | |
| 28 double tValues[2]; | |
| 29 reduction[0] = cubic[0]; | |
| 30 reduction[1] = cubic[3]; | |
| 31 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
| 32 return 2; | |
| 33 } | |
| 34 int smaller = reduction[1].y > reduction[0].y; | |
| 35 int larger = smaller ^ 1; | |
| 36 int roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tVal
ues); | |
| 37 for (int index = 0; index < roots; ++index) { | |
| 38 double yExtrema = interp_cubic_coords(&cubic[0].y, tValues[index]); | |
| 39 if (reduction[smaller].y > yExtrema) { | |
| 40 reduction[smaller].y = yExtrema; | |
| 41 continue; | |
| 42 } | |
| 43 if (reduction[larger].y < yExtrema) { | |
| 44 reduction[larger].y = yExtrema; | |
| 45 } | |
| 46 } | |
| 47 return 2; | |
| 48 } | |
| 49 | |
| 50 static int horizontal_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, C
ubic& reduction) { | |
| 51 double tValues[2]; | |
| 52 reduction[0] = cubic[0]; | |
| 53 reduction[1] = cubic[3]; | |
| 54 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
| 55 return 2; | |
| 56 } | |
| 57 int smaller = reduction[1].x > reduction[0].x; | |
| 58 int larger = smaller ^ 1; | |
| 59 int roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tVal
ues); | |
| 60 for (int index = 0; index < roots; ++index) { | |
| 61 double xExtrema = interp_cubic_coords(&cubic[0].x, tValues[index]); | |
| 62 if (reduction[smaller].x > xExtrema) { | |
| 63 reduction[smaller].x = xExtrema; | |
| 64 continue; | |
| 65 } | |
| 66 if (reduction[larger].x < xExtrema) { | |
| 67 reduction[larger].x = xExtrema; | |
| 68 } | |
| 69 } | |
| 70 return 2; | |
| 71 } | |
| 72 | |
| 73 // check to see if it is a quadratic or a line | |
| 74 static int check_quadratic(const Cubic& cubic, Cubic& reduction) { | |
| 75 double dx10 = cubic[1].x - cubic[0].x; | |
| 76 double dx23 = cubic[2].x - cubic[3].x; | |
| 77 double midX = cubic[0].x + dx10 * 3 / 2; | |
| 78 if (!AlmostEqualUlps(midX - cubic[3].x, dx23 * 3 / 2)) { | |
| 79 return 0; | |
| 80 } | |
| 81 double dy10 = cubic[1].y - cubic[0].y; | |
| 82 double dy23 = cubic[2].y - cubic[3].y; | |
| 83 double midY = cubic[0].y + dy10 * 3 / 2; | |
| 84 if (!AlmostEqualUlps(midY - cubic[3].y, dy23 * 3 / 2)) { | |
| 85 return 0; | |
| 86 } | |
| 87 reduction[0] = cubic[0]; | |
| 88 reduction[1].x = midX; | |
| 89 reduction[1].y = midY; | |
| 90 reduction[2] = cubic[3]; | |
| 91 return 3; | |
| 92 } | |
| 93 | |
| 94 static int check_linear(const Cubic& cubic, ReduceOrder_Styles reduceStyle, | |
| 95 int minX, int maxX, int minY, int maxY, Cubic& reduction) { | |
| 96 int startIndex = 0; | |
| 97 int endIndex = 3; | |
| 98 while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) { | |
| 99 --endIndex; | |
| 100 if (endIndex == 0) { | |
| 101 printf("%s shouldn't get here if all four points are about equal\n",
__FUNCTION__); | |
| 102 SkASSERT(0); | |
| 103 } | |
| 104 } | |
| 105 if (!isLinear(cubic, startIndex, endIndex)) { | |
| 106 return 0; | |
| 107 } | |
| 108 // four are colinear: return line formed by outside | |
| 109 reduction[0] = cubic[0]; | |
| 110 reduction[1] = cubic[3]; | |
| 111 if (reduceStyle == kReduceOrder_TreatAsFill) { | |
| 112 return 2; | |
| 113 } | |
| 114 int sameSide1; | |
| 115 int sameSide2; | |
| 116 bool useX = cubic[maxX].x - cubic[minX].x >= cubic[maxY].y - cubic[minY].y; | |
| 117 if (useX) { | |
| 118 sameSide1 = sign(cubic[0].x - cubic[1].x) + sign(cubic[3].x - cubic[1].x
); | |
| 119 sameSide2 = sign(cubic[0].x - cubic[2].x) + sign(cubic[3].x - cubic[2].x
); | |
| 120 } else { | |
| 121 sameSide1 = sign(cubic[0].y - cubic[1].y) + sign(cubic[3].y - cubic[1].y
); | |
| 122 sameSide2 = sign(cubic[0].y - cubic[2].y) + sign(cubic[3].y - cubic[2].y
); | |
| 123 } | |
| 124 if (sameSide1 == sameSide2 && (sameSide1 & 3) != 2) { | |
| 125 return 2; | |
| 126 } | |
| 127 double tValues[2]; | |
| 128 int roots; | |
| 129 if (useX) { | |
| 130 roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tVal
ues); | |
| 131 } else { | |
| 132 roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tVal
ues); | |
| 133 } | |
| 134 for (int index = 0; index < roots; ++index) { | |
| 135 _Point extrema; | |
| 136 extrema.x = interp_cubic_coords(&cubic[0].x, tValues[index]); | |
| 137 extrema.y = interp_cubic_coords(&cubic[0].y, tValues[index]); | |
| 138 // sameSide > 0 means mid is smaller than either [0] or [3], so replace
smaller | |
| 139 int replace; | |
| 140 if (useX) { | |
| 141 if (extrema.x < cubic[0].x ^ extrema.x < cubic[3].x) { | |
| 142 continue; | |
| 143 } | |
| 144 replace = (extrema.x < cubic[0].x | extrema.x < cubic[3].x) | |
| 145 ^ (cubic[0].x < cubic[3].x); | |
| 146 } else { | |
| 147 if (extrema.y < cubic[0].y ^ extrema.y < cubic[3].y) { | |
| 148 continue; | |
| 149 } | |
| 150 replace = (extrema.y < cubic[0].y | extrema.y < cubic[3].y) | |
| 151 ^ (cubic[0].y < cubic[3].y); | |
| 152 } | |
| 153 reduction[replace] = extrema; | |
| 154 } | |
| 155 return 2; | |
| 156 } | |
| 157 | |
| 158 bool isLinear(const Cubic& cubic, int startIndex, int endIndex) { | |
| 159 LineParameters lineParameters; | |
| 160 lineParameters.cubicEndPoints(cubic, startIndex, endIndex); | |
| 161 // FIXME: maybe it's possible to avoid this and compare non-normalized | |
| 162 lineParameters.normalize(); | |
| 163 double distance = lineParameters.controlPtDistance(cubic, 1); | |
| 164 if (!approximately_zero(distance)) { | |
| 165 return false; | |
| 166 } | |
| 167 distance = lineParameters.controlPtDistance(cubic, 2); | |
| 168 return approximately_zero(distance); | |
| 169 } | |
| 170 | |
| 171 /* food for thought: | |
| 172 http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piece
wise-degree-reduction-algos-2-a.html | |
| 173 | |
| 174 Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the | |
| 175 corresponding quadratic Bezier are (given in convex combinations of | |
| 176 points): | |
| 177 | |
| 178 q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4 | |
| 179 q2 = -c1 + (3/2)c2 + (3/2)c3 - c4 | |
| 180 q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4 | |
| 181 | |
| 182 Of course, this curve does not interpolate the end-points, but it would | |
| 183 be interesting to see the behaviour of such a curve in an applet. | |
| 184 | |
| 185 -- | |
| 186 Kalle Rutanen | |
| 187 http://kaba.hilvi.org | |
| 188 | |
| 189 */ | |
| 190 | |
| 191 // reduce to a quadratic or smaller | |
| 192 // look for identical points | |
| 193 // look for all four points in a line | |
| 194 // note that three points in a line doesn't simplify a cubic | |
| 195 // look for approximation with single quadratic | |
| 196 // save approximation with multiple quadratics for later | |
| 197 int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Quadratics all
owQuadratics, | |
| 198 ReduceOrder_Styles reduceStyle) { | |
| 199 int index, minX, maxX, minY, maxY; | |
| 200 int minXSet, minYSet; | |
| 201 minX = maxX = minY = maxY = 0; | |
| 202 minXSet = minYSet = 0; | |
| 203 for (index = 1; index < 4; ++index) { | |
| 204 if (cubic[minX].x > cubic[index].x) { | |
| 205 minX = index; | |
| 206 } | |
| 207 if (cubic[minY].y > cubic[index].y) { | |
| 208 minY = index; | |
| 209 } | |
| 210 if (cubic[maxX].x < cubic[index].x) { | |
| 211 maxX = index; | |
| 212 } | |
| 213 if (cubic[maxY].y < cubic[index].y) { | |
| 214 maxY = index; | |
| 215 } | |
| 216 } | |
| 217 for (index = 0; index < 4; ++index) { | |
| 218 double cx = cubic[index].x; | |
| 219 double cy = cubic[index].y; | |
| 220 double denom = SkTMax(fabs(cx), SkTMax(fabs(cy), | |
| 221 SkTMax(fabs(cubic[minX].x), fabs(cubic[minY].y)))); | |
| 222 if (denom == 0) { | |
| 223 minXSet |= 1 << index; | |
| 224 minYSet |= 1 << index; | |
| 225 continue; | |
| 226 } | |
| 227 double inv = 1 / denom; | |
| 228 if (approximately_equal_half(cx * inv, cubic[minX].x * inv)) { | |
| 229 minXSet |= 1 << index; | |
| 230 } | |
| 231 if (approximately_equal_half(cy * inv, cubic[minY].y * inv)) { | |
| 232 minYSet |= 1 << index; | |
| 233 } | |
| 234 } | |
| 235 if (minXSet == 0xF) { // test for vertical line | |
| 236 if (minYSet == 0xF) { // return 1 if all four are coincident | |
| 237 return coincident_line(cubic, reduction); | |
| 238 } | |
| 239 return vertical_line(cubic, reduceStyle, reduction); | |
| 240 } | |
| 241 if (minYSet == 0xF) { // test for horizontal line | |
| 242 return horizontal_line(cubic, reduceStyle, reduction); | |
| 243 } | |
| 244 int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, reduct
ion); | |
| 245 if (result) { | |
| 246 return result; | |
| 247 } | |
| 248 if (allowQuadratics == kReduceOrder_QuadraticsAllowed | |
| 249 && (result = check_quadratic(cubic, reduction))) { | |
| 250 return result; | |
| 251 } | |
| 252 memcpy(reduction, cubic, sizeof(Cubic)); | |
| 253 return 4; | |
| 254 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 867213004:
remove prototype pathops code (Closed)
Base URL: https://skia.googlesource.com/skia.git@master