35 36 private Helpers() { 37 throw new Error("This is a non instantiable class"); 38 } 39 40 static boolean within(final float x, final float y, final float err) { 41 final float d = y - x; 42 return (d <= err && d >= -err); 43 } 44 45 static boolean within(final double x, final double y, final double err) { 46 final double d = y - x; 47 return (d <= err && d >= -err); 48 } 49 50 static int quadraticRoots(final float a, final float b, 51 final float c, float[] zeroes, final int off) 52 { 53 int ret = off; 54 float t; 55 if (a != 0f) { 56 final float dis = b*b - 4*a*c; 57 if (dis > 0f) { 58 final float sqrtDis = (float)Math.sqrt(dis); 59 // depending on the sign of b we use a slightly different 60 // algorithm than the traditional one to find one of the roots 61 // so we can avoid adding numbers of different signs (which 62 // might result in loss of precision). 63 if (b >= 0f) { 64 zeroes[ret++] = (2f * c) / (-b - sqrtDis); 65 zeroes[ret++] = (-b - sqrtDis) / (2f * a); 66 } else { 67 zeroes[ret++] = (-b + sqrtDis) / (2f * a); 68 zeroes[ret++] = (2f * c) / (-b + sqrtDis); 69 } 70 } else if (dis == 0f) { 71 t = (-b) / (2f * a); 72 zeroes[ret++] = t; 73 } 74 } else { 75 if (b != 0f) { 76 t = (-c) / b; 77 zeroes[ret++] = t; 78 } 79 } 80 return ret - off; 81 } 82 83 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B) 84 static int cubicRootsInAB(float d, float a, float b, float c, 85 float[] pts, final int off, 86 final float A, final float B) 87 { 88 if (d == 0f) { 89 int num = quadraticRoots(a, b, c, pts, off); 90 return filterOutNotInAB(pts, off, num, A, B) - off; 91 } 92 // From Graphics Gems: 93 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c 94 // (also from awt.geom.CubicCurve2D. But here we don't need as 95 // much accuracy and we don't want to create arrays so we use 96 // our own customized version). 97 98 // normal form: x^3 + ax^2 + bx + c = 0 99 a /= d; 100 b /= d; 101 c /= d; 102 103 // substitute x = y - A/3 to eliminate quadratic term: 104 // x^3 +Px + Q = 0 105 // 106 // Since we actually need P/3 and Q/2 for all of the 107 // calculations that follow, we will calculate 108 // p = P/3 109 // q = Q/2 110 // instead and use those values for simplicity of the code. 111 double sq_A = a * a; 112 double p = (1.0/3.0) * ((-1.0/3.0) * sq_A + b); 113 double q = (1.0/2.0) * ((2.0/27.0) * a * sq_A - (1.0/3.0) * a * b + c); 114 115 // use Cardano's formula 116 117 double cb_p = p * p * p; 118 double D = q * q + cb_p; 119 120 int num; 121 if (D < 0.0) { 122 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method 123 final double phi = (1.0/3.0) * acos(-q / sqrt(-cb_p)); 124 final double t = 2.0 * sqrt(-p); 125 126 pts[ off+0 ] = (float)( t * cos(phi)); 127 pts[ off+1 ] = (float)(-t * cos(phi + (PI / 3.0))); 128 pts[ off+2 ] = (float)(-t * cos(phi - (PI / 3.0))); 129 num = 3; 130 } else { 131 final double sqrt_D = sqrt(D); 132 final double u = cbrt(sqrt_D - q); 133 final double v = - cbrt(sqrt_D + q); 134 135 pts[ off ] = (float)(u + v); 136 num = 1; 137 138 if (within(D, 0.0, 1e-8)) { 139 pts[off+1] = -(pts[off] / 2f); 140 num = 2; 141 } 142 } 143 144 final float sub = (1f/3f) * a; 145 146 for (int i = 0; i < num; ++i) { 147 pts[ off+i ] -= sub; 148 } 149 150 return filterOutNotInAB(pts, off, num, A, B) - off; 151 } 152 153 static float evalCubic(final float a, final float b, 154 final float c, final float d, 155 final float t) 156 { 157 return t * (t * (t * a + b) + c) + d; 158 } 159 160 static float evalQuad(final float a, final float b, 161 final float c, final float t) 162 { 163 return t * (t * a + b) + c; 164 } 165 166 // returns the index 1 past the last valid element remaining after filtering 167 static int filterOutNotInAB(float[] nums, final int off, final int len, 168 final float a, final float b) 169 { 170 int ret = off; 171 for (int i = off, end = off + len; i < end; i++) { 172 if (nums[i] >= a && nums[i] < b) { 173 nums[ret++] = nums[i]; 174 } 175 } 176 return ret; 177 } 178 179 static float polyLineLength(float[] poly, final int off, final int nCoords) { 180 assert nCoords % 2 == 0 && poly.length >= off + nCoords : ""; 181 float acc = 0f; 182 for (int i = off + 2; i < off + nCoords; i += 2) { 183 acc += linelen(poly[i], poly[i+1], poly[i-2], poly[i-1]); 184 } 185 return acc; 186 } 187 188 static float linelen(float x1, float y1, float x2, float y2) { 189 final float dx = x2 - x1; 190 final float dy = y2 - y1; 191 return (float)Math.sqrt(dx*dx + dy*dy); 192 } 193 194 static void subdivide(float[] src, int srcoff, float[] left, int leftoff, 195 float[] right, int rightoff, int type) 196 { 197 switch(type) { 198 case 6: 199 Helpers.subdivideQuad(src, srcoff, left, leftoff, right, rightoff); 200 return; 201 case 8: 202 Helpers.subdivideCubic(src, srcoff, left, leftoff, right, rightoff); 203 return; 204 default: 205 throw new InternalError("Unsupported curve type"); 206 } 207 } 208 209 static void isort(float[] a, int off, int len) { 210 for (int i = off + 1, end = off + len; i < end; i++) { 211 float ai = a[i]; 212 int j = i - 1; 213 for (; j >= off && a[j] > ai; j--) { 214 a[j+1] = a[j]; 215 } 216 a[j+1] = ai; 217 } 218 } 219 220 // Most of these are copied from classes in java.awt.geom because we need 221 // float versions of these functions, and Line2D, CubicCurve2D, 222 // QuadCurve2D don't provide them. 223 /** 224 * Subdivides the cubic curve specified by the coordinates 225 * stored in the <code>src</code> array at indices <code>srcoff</code> 226 * through (<code>srcoff</code> + 7) and stores the 227 * resulting two subdivided curves into the two result arrays at the 228 * corresponding indices. 229 * Either or both of the <code>left</code> and <code>right</code> 230 * arrays may be <code>null</code> or a reference to the same array 231 * as the <code>src</code> array. 232 * Note that the last point in the first subdivided curve is the 233 * same as the first point in the second subdivided curve. Thus, 234 * it is possible to pass the same array for <code>left</code> 235 * and <code>right</code> and to use offsets, such as <code>rightoff</code> 236 * equals (<code>leftoff</code> + 6), in order 237 * to avoid allocating extra storage for this common point. 238 * @param src the array holding the coordinates for the source curve 239 * @param srcoff the offset into the array of the beginning of the 240 * the 6 source coordinates 241 * @param left the array for storing the coordinates for the first 242 * half of the subdivided curve 251 static void subdivideCubic(float[] src, int srcoff, 252 float[] left, int leftoff, 253 float[] right, int rightoff) 254 { 255 float x1 = src[srcoff + 0]; 256 float y1 = src[srcoff + 1]; 257 float ctrlx1 = src[srcoff + 2]; 258 float ctrly1 = src[srcoff + 3]; 259 float ctrlx2 = src[srcoff + 4]; 260 float ctrly2 = src[srcoff + 5]; 261 float x2 = src[srcoff + 6]; 262 float y2 = src[srcoff + 7]; 263 if (left != null) { 264 left[leftoff + 0] = x1; 265 left[leftoff + 1] = y1; 266 } 267 if (right != null) { 268 right[rightoff + 6] = x2; 269 right[rightoff + 7] = y2; 270 } 271 x1 = (x1 + ctrlx1) / 2f; 272 y1 = (y1 + ctrly1) / 2f; 273 x2 = (x2 + ctrlx2) / 2f; 274 y2 = (y2 + ctrly2) / 2f; 275 float centerx = (ctrlx1 + ctrlx2) / 2f; 276 float centery = (ctrly1 + ctrly2) / 2f; 277 ctrlx1 = (x1 + centerx) / 2f; 278 ctrly1 = (y1 + centery) / 2f; 279 ctrlx2 = (x2 + centerx) / 2f; 280 ctrly2 = (y2 + centery) / 2f; 281 centerx = (ctrlx1 + ctrlx2) / 2f; 282 centery = (ctrly1 + ctrly2) / 2f; 283 if (left != null) { 284 left[leftoff + 2] = x1; 285 left[leftoff + 3] = y1; 286 left[leftoff + 4] = ctrlx1; 287 left[leftoff + 5] = ctrly1; 288 left[leftoff + 6] = centerx; 289 left[leftoff + 7] = centery; 290 } 291 if (right != null) { 292 right[rightoff + 0] = centerx; 293 right[rightoff + 1] = centery; 294 right[rightoff + 2] = ctrlx2; 295 right[rightoff + 3] = ctrly2; 296 right[rightoff + 4] = x2; 297 right[rightoff + 5] = y2; 298 } 299 } 300 301 302 static void subdivideCubicAt(float t, float[] src, int srcoff, 350 } 351 352 static void subdivideQuad(float[] src, int srcoff, 353 float[] left, int leftoff, 354 float[] right, int rightoff) 355 { 356 float x1 = src[srcoff + 0]; 357 float y1 = src[srcoff + 1]; 358 float ctrlx = src[srcoff + 2]; 359 float ctrly = src[srcoff + 3]; 360 float x2 = src[srcoff + 4]; 361 float y2 = src[srcoff + 5]; 362 if (left != null) { 363 left[leftoff + 0] = x1; 364 left[leftoff + 1] = y1; 365 } 366 if (right != null) { 367 right[rightoff + 4] = x2; 368 right[rightoff + 5] = y2; 369 } 370 x1 = (x1 + ctrlx) / 2f; 371 y1 = (y1 + ctrly) / 2f; 372 x2 = (x2 + ctrlx) / 2f; 373 y2 = (y2 + ctrly) / 2f; 374 ctrlx = (x1 + x2) / 2f; 375 ctrly = (y1 + y2) / 2f; 376 if (left != null) { 377 left[leftoff + 2] = x1; 378 left[leftoff + 3] = y1; 379 left[leftoff + 4] = ctrlx; 380 left[leftoff + 5] = ctrly; 381 } 382 if (right != null) { 383 right[rightoff + 0] = ctrlx; 384 right[rightoff + 1] = ctrly; 385 right[rightoff + 2] = x2; 386 right[rightoff + 3] = y2; 387 } 388 } 389 390 static void subdivideQuadAt(float t, float[] src, int srcoff, 391 float[] left, int leftoff, 392 float[] right, int rightoff) 393 { 394 float x1 = src[srcoff + 0]; 395 float y1 = src[srcoff + 1]; | 35 36 private Helpers() { 37 throw new Error("This is a non instantiable class"); 38 } 39 40 static boolean within(final float x, final float y, final float err) { 41 final float d = y - x; 42 return (d <= err && d >= -err); 43 } 44 45 static boolean within(final double x, final double y, final double err) { 46 final double d = y - x; 47 return (d <= err && d >= -err); 48 } 49 50 static int quadraticRoots(final float a, final float b, 51 final float c, float[] zeroes, final int off) 52 { 53 int ret = off; 54 float t; 55 if (a != 0.0f) { 56 final float dis = b*b - 4*a*c; 57 if (dis > 0.0f) { 58 final float sqrtDis = (float) Math.sqrt(dis); 59 // depending on the sign of b we use a slightly different 60 // algorithm than the traditional one to find one of the roots 61 // so we can avoid adding numbers of different signs (which 62 // might result in loss of precision). 63 if (b >= 0.0f) { 64 zeroes[ret++] = (2.0f * c) / (-b - sqrtDis); 65 zeroes[ret++] = (-b - sqrtDis) / (2.0f * a); 66 } else { 67 zeroes[ret++] = (-b + sqrtDis) / (2.0f * a); 68 zeroes[ret++] = (2.0f * c) / (-b + sqrtDis); 69 } 70 } else if (dis == 0.0f) { 71 t = (-b) / (2.0f * a); 72 zeroes[ret++] = t; 73 } 74 } else { 75 if (b != 0.0f) { 76 t = (-c) / b; 77 zeroes[ret++] = t; 78 } 79 } 80 return ret - off; 81 } 82 83 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B) 84 static int cubicRootsInAB(float d, float a, float b, float c, 85 float[] pts, final int off, 86 final float A, final float B) 87 { 88 if (d == 0.0f) { 89 int num = quadraticRoots(a, b, c, pts, off); 90 return filterOutNotInAB(pts, off, num, A, B) - off; 91 } 92 // From Graphics Gems: 93 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c 94 // (also from awt.geom.CubicCurve2D. But here we don't need as 95 // much accuracy and we don't want to create arrays so we use 96 // our own customized version). 97 98 // normal form: x^3 + ax^2 + bx + c = 0 99 a /= d; 100 b /= d; 101 c /= d; 102 103 // substitute x = y - A/3 to eliminate quadratic term: 104 // x^3 +Px + Q = 0 105 // 106 // Since we actually need P/3 and Q/2 for all of the 107 // calculations that follow, we will calculate 108 // p = P/3 109 // q = Q/2 110 // instead and use those values for simplicity of the code. 111 double sq_A = a * a; 112 double p = (1.0d/3.0d) * ((-1.0d/3.0d) * sq_A + b); 113 double q = (1.0d/2.0d) * ((2.0d/27.0d) * a * sq_A - (1.0d/3.0d) * a * b + c); 114 115 // use Cardano's formula 116 117 double cb_p = p * p * p; 118 double D = q * q + cb_p; 119 120 int num; 121 if (D < 0.0d) { 122 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method 123 final double phi = (1.0d/3.0d) * acos(-q / sqrt(-cb_p)); 124 final double t = 2.0d * sqrt(-p); 125 126 pts[ off+0 ] = (float) ( t * cos(phi)); 127 pts[ off+1 ] = (float) (-t * cos(phi + (PI / 3.0d))); 128 pts[ off+2 ] = (float) (-t * cos(phi - (PI / 3.0d))); 129 num = 3; 130 } else { 131 final double sqrt_D = sqrt(D); 132 final double u = cbrt(sqrt_D - q); 133 final double v = - cbrt(sqrt_D + q); 134 135 pts[ off ] = (float) (u + v); 136 num = 1; 137 138 if (within(D, 0.0, 1e-8d)) { 139 pts[off+1] = -(pts[off] / 2.0f); 140 num = 2; 141 } 142 } 143 144 final float sub = (1.0f/3.0f) * a; 145 146 for (int i = 0; i < num; ++i) { 147 pts[ off+i ] -= sub; 148 } 149 150 return filterOutNotInAB(pts, off, num, A, B) - off; 151 } 152 153 static float evalCubic(final float a, final float b, 154 final float c, final float d, 155 final float t) 156 { 157 return t * (t * (t * a + b) + c) + d; 158 } 159 160 static float evalQuad(final float a, final float b, 161 final float c, final float t) 162 { 163 return t * (t * a + b) + c; 164 } 165 166 // returns the index 1 past the last valid element remaining after filtering 167 static int filterOutNotInAB(float[] nums, final int off, final int len, 168 final float a, final float b) 169 { 170 int ret = off; 171 for (int i = off, end = off + len; i < end; i++) { 172 if (nums[i] >= a && nums[i] < b) { 173 nums[ret++] = nums[i]; 174 } 175 } 176 return ret; 177 } 178 179 static float polyLineLength(float[] poly, final int off, final int nCoords) { 180 assert nCoords % 2 == 0 && poly.length >= off + nCoords : ""; 181 float acc = 0.0f; 182 for (int i = off + 2; i < off + nCoords; i += 2) { 183 acc += linelen(poly[i], poly[i+1], poly[i-2], poly[i-1]); 184 } 185 return acc; 186 } 187 188 static float linelen(float x1, float y1, float x2, float y2) { 189 final float dx = x2 - x1; 190 final float dy = y2 - y1; 191 return (float) Math.sqrt(dx*dx + dy*dy); 192 } 193 194 static void subdivide(float[] src, int srcoff, float[] left, int leftoff, 195 float[] right, int rightoff, int type) 196 { 197 switch(type) { 198 case 6: 199 Helpers.subdivideQuad(src, srcoff, left, leftoff, right, rightoff); 200 return; 201 case 8: 202 Helpers.subdivideCubic(src, srcoff, left, leftoff, right, rightoff); 203 return; 204 default: 205 throw new InternalError("Unsupported curve type"); 206 } 207 } 208 209 static void isort(float[] a, int off, int len) { 210 for (int i = off + 1, end = off + len; i < end; i++) { 211 float ai = a[i]; 212 int j = i - 1; 213 for (; j >= off && a[j] > ai; j--) { 214 a[j+1] = a[j]; 215 } 216 a[j+1] = ai; 217 } 218 } 219 220 // Most of these are copied from classes in java.awt.geom because we need 221 // both float and double versions of these functions, and Line2D, CubicCurve2D, 222 // QuadCurve2D don't provide the float version. 223 /** 224 * Subdivides the cubic curve specified by the coordinates 225 * stored in the <code>src</code> array at indices <code>srcoff</code> 226 * through (<code>srcoff</code> + 7) and stores the 227 * resulting two subdivided curves into the two result arrays at the 228 * corresponding indices. 229 * Either or both of the <code>left</code> and <code>right</code> 230 * arrays may be <code>null</code> or a reference to the same array 231 * as the <code>src</code> array. 232 * Note that the last point in the first subdivided curve is the 233 * same as the first point in the second subdivided curve. Thus, 234 * it is possible to pass the same array for <code>left</code> 235 * and <code>right</code> and to use offsets, such as <code>rightoff</code> 236 * equals (<code>leftoff</code> + 6), in order 237 * to avoid allocating extra storage for this common point. 238 * @param src the array holding the coordinates for the source curve 239 * @param srcoff the offset into the array of the beginning of the 240 * the 6 source coordinates 241 * @param left the array for storing the coordinates for the first 242 * half of the subdivided curve 251 static void subdivideCubic(float[] src, int srcoff, 252 float[] left, int leftoff, 253 float[] right, int rightoff) 254 { 255 float x1 = src[srcoff + 0]; 256 float y1 = src[srcoff + 1]; 257 float ctrlx1 = src[srcoff + 2]; 258 float ctrly1 = src[srcoff + 3]; 259 float ctrlx2 = src[srcoff + 4]; 260 float ctrly2 = src[srcoff + 5]; 261 float x2 = src[srcoff + 6]; 262 float y2 = src[srcoff + 7]; 263 if (left != null) { 264 left[leftoff + 0] = x1; 265 left[leftoff + 1] = y1; 266 } 267 if (right != null) { 268 right[rightoff + 6] = x2; 269 right[rightoff + 7] = y2; 270 } 271 x1 = (x1 + ctrlx1) / 2.0f; 272 y1 = (y1 + ctrly1) / 2.0f; 273 x2 = (x2 + ctrlx2) / 2.0f; 274 y2 = (y2 + ctrly2) / 2.0f; 275 float centerx = (ctrlx1 + ctrlx2) / 2.0f; 276 float centery = (ctrly1 + ctrly2) / 2.0f; 277 ctrlx1 = (x1 + centerx) / 2.0f; 278 ctrly1 = (y1 + centery) / 2.0f; 279 ctrlx2 = (x2 + centerx) / 2.0f; 280 ctrly2 = (y2 + centery) / 2.0f; 281 centerx = (ctrlx1 + ctrlx2) / 2.0f; 282 centery = (ctrly1 + ctrly2) / 2.0f; 283 if (left != null) { 284 left[leftoff + 2] = x1; 285 left[leftoff + 3] = y1; 286 left[leftoff + 4] = ctrlx1; 287 left[leftoff + 5] = ctrly1; 288 left[leftoff + 6] = centerx; 289 left[leftoff + 7] = centery; 290 } 291 if (right != null) { 292 right[rightoff + 0] = centerx; 293 right[rightoff + 1] = centery; 294 right[rightoff + 2] = ctrlx2; 295 right[rightoff + 3] = ctrly2; 296 right[rightoff + 4] = x2; 297 right[rightoff + 5] = y2; 298 } 299 } 300 301 302 static void subdivideCubicAt(float t, float[] src, int srcoff, 350 } 351 352 static void subdivideQuad(float[] src, int srcoff, 353 float[] left, int leftoff, 354 float[] right, int rightoff) 355 { 356 float x1 = src[srcoff + 0]; 357 float y1 = src[srcoff + 1]; 358 float ctrlx = src[srcoff + 2]; 359 float ctrly = src[srcoff + 3]; 360 float x2 = src[srcoff + 4]; 361 float y2 = src[srcoff + 5]; 362 if (left != null) { 363 left[leftoff + 0] = x1; 364 left[leftoff + 1] = y1; 365 } 366 if (right != null) { 367 right[rightoff + 4] = x2; 368 right[rightoff + 5] = y2; 369 } 370 x1 = (x1 + ctrlx) / 2.0f; 371 y1 = (y1 + ctrly) / 2.0f; 372 x2 = (x2 + ctrlx) / 2.0f; 373 y2 = (y2 + ctrly) / 2.0f; 374 ctrlx = (x1 + x2) / 2.0f; 375 ctrly = (y1 + y2) / 2.0f; 376 if (left != null) { 377 left[leftoff + 2] = x1; 378 left[leftoff + 3] = y1; 379 left[leftoff + 4] = ctrlx; 380 left[leftoff + 5] = ctrly; 381 } 382 if (right != null) { 383 right[rightoff + 0] = ctrlx; 384 right[rightoff + 1] = ctrly; 385 right[rightoff + 2] = x2; 386 right[rightoff + 3] = y2; 387 } 388 } 389 390 static void subdivideQuadAt(float t, float[] src, int srcoff, 391 float[] left, int leftoff, 392 float[] right, int rightoff) 393 { 394 float x1 = src[srcoff + 0]; 395 float y1 = src[srcoff + 1]; |