1 /* |
1 /* |
2 * Copyright (c) 2007, 2016, Oracle and/or its affiliates. All rights reserved. |
2 * Copyright (c) 2007, 2017, Oracle and/or its affiliates. All rights reserved. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * |
4 * |
5 * This code is free software; you can redistribute it and/or modify it |
5 * This code is free software; you can redistribute it and/or modify it |
6 * under the terms of the GNU General Public License version 2 only, as |
6 * under the terms of the GNU General Public License version 2 only, as |
7 * published by the Free Software Foundation. Oracle designates this |
7 * published by the Free Software Foundation. Oracle designates this |
50 static int quadraticRoots(final float a, final float b, |
50 static int quadraticRoots(final float a, final float b, |
51 final float c, float[] zeroes, final int off) |
51 final float c, float[] zeroes, final int off) |
52 { |
52 { |
53 int ret = off; |
53 int ret = off; |
54 float t; |
54 float t; |
55 if (a != 0f) { |
55 if (a != 0.0f) { |
56 final float dis = b*b - 4*a*c; |
56 final float dis = b*b - 4*a*c; |
57 if (dis > 0f) { |
57 if (dis > 0.0f) { |
58 final float sqrtDis = (float)Math.sqrt(dis); |
58 final float sqrtDis = (float) Math.sqrt(dis); |
59 // depending on the sign of b we use a slightly different |
59 // depending on the sign of b we use a slightly different |
60 // algorithm than the traditional one to find one of the roots |
60 // algorithm than the traditional one to find one of the roots |
61 // so we can avoid adding numbers of different signs (which |
61 // so we can avoid adding numbers of different signs (which |
62 // might result in loss of precision). |
62 // might result in loss of precision). |
63 if (b >= 0f) { |
63 if (b >= 0.0f) { |
64 zeroes[ret++] = (2f * c) / (-b - sqrtDis); |
64 zeroes[ret++] = (2.0f * c) / (-b - sqrtDis); |
65 zeroes[ret++] = (-b - sqrtDis) / (2f * a); |
65 zeroes[ret++] = (-b - sqrtDis) / (2.0f * a); |
66 } else { |
66 } else { |
67 zeroes[ret++] = (-b + sqrtDis) / (2f * a); |
67 zeroes[ret++] = (-b + sqrtDis) / (2.0f * a); |
68 zeroes[ret++] = (2f * c) / (-b + sqrtDis); |
68 zeroes[ret++] = (2.0f * c) / (-b + sqrtDis); |
69 } |
69 } |
70 } else if (dis == 0f) { |
70 } else if (dis == 0.0f) { |
71 t = (-b) / (2f * a); |
71 t = (-b) / (2.0f * a); |
72 zeroes[ret++] = t; |
72 zeroes[ret++] = t; |
73 } |
73 } |
74 } else { |
74 } else { |
75 if (b != 0f) { |
75 if (b != 0.0f) { |
76 t = (-c) / b; |
76 t = (-c) / b; |
77 zeroes[ret++] = t; |
77 zeroes[ret++] = t; |
78 } |
78 } |
79 } |
79 } |
80 return ret - off; |
80 return ret - off; |
83 // find the roots of g(t) = d*t^3 + a*t^2 + b*t + c in [A,B) |
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, |
84 static int cubicRootsInAB(float d, float a, float b, float c, |
85 float[] pts, final int off, |
85 float[] pts, final int off, |
86 final float A, final float B) |
86 final float A, final float B) |
87 { |
87 { |
88 if (d == 0f) { |
88 if (d == 0.0f) { |
89 int num = quadraticRoots(a, b, c, pts, off); |
89 int num = quadraticRoots(a, b, c, pts, off); |
90 return filterOutNotInAB(pts, off, num, A, B) - off; |
90 return filterOutNotInAB(pts, off, num, A, B) - off; |
91 } |
91 } |
92 // From Graphics Gems: |
92 // From Graphics Gems: |
93 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c |
93 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c |
107 // calculations that follow, we will calculate |
107 // calculations that follow, we will calculate |
108 // p = P/3 |
108 // p = P/3 |
109 // q = Q/2 |
109 // q = Q/2 |
110 // instead and use those values for simplicity of the code. |
110 // instead and use those values for simplicity of the code. |
111 double sq_A = a * a; |
111 double sq_A = a * a; |
112 double p = (1.0/3.0) * ((-1.0/3.0) * sq_A + b); |
112 double p = (1.0d/3.0d) * ((-1.0d/3.0d) * sq_A + b); |
113 double q = (1.0/2.0) * ((2.0/27.0) * a * sq_A - (1.0/3.0) * a * b + c); |
113 double q = (1.0d/2.0d) * ((2.0d/27.0d) * a * sq_A - (1.0d/3.0d) * a * b + c); |
114 |
114 |
115 // use Cardano's formula |
115 // use Cardano's formula |
116 |
116 |
117 double cb_p = p * p * p; |
117 double cb_p = p * p * p; |
118 double D = q * q + cb_p; |
118 double D = q * q + cb_p; |
119 |
119 |
120 int num; |
120 int num; |
121 if (D < 0.0) { |
121 if (D < 0.0d) { |
122 // see: http://en.wikipedia.org/wiki/Cubic_function#Trigonometric_.28and_hyperbolic.29_method |
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)); |
123 final double phi = (1.0d/3.0d) * acos(-q / sqrt(-cb_p)); |
124 final double t = 2.0 * sqrt(-p); |
124 final double t = 2.0d * sqrt(-p); |
125 |
125 |
126 pts[ off+0 ] = (float)( t * cos(phi)); |
126 pts[ off+0 ] = (float) ( t * cos(phi)); |
127 pts[ off+1 ] = (float)(-t * cos(phi + (PI / 3.0))); |
127 pts[ off+1 ] = (float) (-t * cos(phi + (PI / 3.0d))); |
128 pts[ off+2 ] = (float)(-t * cos(phi - (PI / 3.0))); |
128 pts[ off+2 ] = (float) (-t * cos(phi - (PI / 3.0d))); |
129 num = 3; |
129 num = 3; |
130 } else { |
130 } else { |
131 final double sqrt_D = sqrt(D); |
131 final double sqrt_D = sqrt(D); |
132 final double u = cbrt(sqrt_D - q); |
132 final double u = cbrt(sqrt_D - q); |
133 final double v = - cbrt(sqrt_D + q); |
133 final double v = - cbrt(sqrt_D + q); |
134 |
134 |
135 pts[ off ] = (float)(u + v); |
135 pts[ off ] = (float) (u + v); |
136 num = 1; |
136 num = 1; |
137 |
137 |
138 if (within(D, 0.0, 1e-8)) { |
138 if (within(D, 0.0d, 1e-8d)) { |
139 pts[off+1] = -(pts[off] / 2f); |
139 pts[off+1] = -(pts[off] / 2.0f); |
140 num = 2; |
140 num = 2; |
141 } |
141 } |
142 } |
142 } |
143 |
143 |
144 final float sub = (1f/3f) * a; |
144 final float sub = (1.0f/3.0f) * a; |
145 |
145 |
146 for (int i = 0; i < num; ++i) { |
146 for (int i = 0; i < num; ++i) { |
147 pts[ off+i ] -= sub; |
147 pts[ off+i ] -= sub; |
148 } |
148 } |
149 |
149 |
176 return ret; |
176 return ret; |
177 } |
177 } |
178 |
178 |
179 static float polyLineLength(float[] poly, final int off, final int nCoords) { |
179 static float polyLineLength(float[] poly, final int off, final int nCoords) { |
180 assert nCoords % 2 == 0 && poly.length >= off + nCoords : ""; |
180 assert nCoords % 2 == 0 && poly.length >= off + nCoords : ""; |
181 float acc = 0; |
181 float acc = 0.0f; |
182 for (int i = off + 2; i < off + nCoords; i += 2) { |
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]); |
183 acc += linelen(poly[i], poly[i+1], poly[i-2], poly[i-1]); |
184 } |
184 } |
185 return acc; |
185 return acc; |
186 } |
186 } |
187 |
187 |
188 static float linelen(float x1, float y1, float x2, float y2) { |
188 static float linelen(float x1, float y1, float x2, float y2) { |
189 final float dx = x2 - x1; |
189 final float dx = x2 - x1; |
190 final float dy = y2 - y1; |
190 final float dy = y2 - y1; |
191 return (float)Math.sqrt(dx*dx + dy*dy); |
191 return (float) Math.sqrt(dx*dx + dy*dy); |
192 } |
192 } |
193 |
193 |
194 static void subdivide(float[] src, int srcoff, float[] left, int leftoff, |
194 static void subdivide(float[] src, int srcoff, float[] left, int leftoff, |
195 float[] right, int rightoff, int type) |
195 float[] right, int rightoff, int type) |
196 { |
196 { |
216 a[j+1] = ai; |
216 a[j+1] = ai; |
217 } |
217 } |
218 } |
218 } |
219 |
219 |
220 // Most of these are copied from classes in java.awt.geom because we need |
220 // Most of these are copied from classes in java.awt.geom because we need |
221 // float versions of these functions, and Line2D, CubicCurve2D, |
221 // both single and double precision variants of these functions, and Line2D, |
222 // QuadCurve2D don't provide them. |
222 // CubicCurve2D, QuadCurve2D don't provide them. |
223 /** |
223 /** |
224 * Subdivides the cubic curve specified by the coordinates |
224 * Subdivides the cubic curve specified by the coordinates |
225 * stored in the <code>src</code> array at indices <code>srcoff</code> |
225 * stored in the <code>src</code> array at indices <code>srcoff</code> |
226 * through (<code>srcoff</code> + 7) and stores the |
226 * through (<code>srcoff</code> + 7) and stores the |
227 * resulting two subdivided curves into the two result arrays at the |
227 * resulting two subdivided curves into the two result arrays at the |
266 } |
266 } |
267 if (right != null) { |
267 if (right != null) { |
268 right[rightoff + 6] = x2; |
268 right[rightoff + 6] = x2; |
269 right[rightoff + 7] = y2; |
269 right[rightoff + 7] = y2; |
270 } |
270 } |
271 x1 = (x1 + ctrlx1) / 2f; |
271 x1 = (x1 + ctrlx1) / 2.0f; |
272 y1 = (y1 + ctrly1) / 2f; |
272 y1 = (y1 + ctrly1) / 2.0f; |
273 x2 = (x2 + ctrlx2) / 2f; |
273 x2 = (x2 + ctrlx2) / 2.0f; |
274 y2 = (y2 + ctrly2) / 2f; |
274 y2 = (y2 + ctrly2) / 2.0f; |
275 float centerx = (ctrlx1 + ctrlx2) / 2f; |
275 float centerx = (ctrlx1 + ctrlx2) / 2.0f; |
276 float centery = (ctrly1 + ctrly2) / 2f; |
276 float centery = (ctrly1 + ctrly2) / 2.0f; |
277 ctrlx1 = (x1 + centerx) / 2f; |
277 ctrlx1 = (x1 + centerx) / 2.0f; |
278 ctrly1 = (y1 + centery) / 2f; |
278 ctrly1 = (y1 + centery) / 2.0f; |
279 ctrlx2 = (x2 + centerx) / 2f; |
279 ctrlx2 = (x2 + centerx) / 2.0f; |
280 ctrly2 = (y2 + centery) / 2f; |
280 ctrly2 = (y2 + centery) / 2.0f; |
281 centerx = (ctrlx1 + ctrlx2) / 2f; |
281 centerx = (ctrlx1 + ctrlx2) / 2.0f; |
282 centery = (ctrly1 + ctrly2) / 2f; |
282 centery = (ctrly1 + ctrly2) / 2.0f; |
283 if (left != null) { |
283 if (left != null) { |
284 left[leftoff + 2] = x1; |
284 left[leftoff + 2] = x1; |
285 left[leftoff + 3] = y1; |
285 left[leftoff + 3] = y1; |
286 left[leftoff + 4] = ctrlx1; |
286 left[leftoff + 4] = ctrlx1; |
287 left[leftoff + 5] = ctrly1; |
287 left[leftoff + 5] = ctrly1; |
365 } |
365 } |
366 if (right != null) { |
366 if (right != null) { |
367 right[rightoff + 4] = x2; |
367 right[rightoff + 4] = x2; |
368 right[rightoff + 5] = y2; |
368 right[rightoff + 5] = y2; |
369 } |
369 } |
370 x1 = (x1 + ctrlx) / 2f; |
370 x1 = (x1 + ctrlx) / 2.0f; |
371 y1 = (y1 + ctrly) / 2f; |
371 y1 = (y1 + ctrly) / 2.0f; |
372 x2 = (x2 + ctrlx) / 2f; |
372 x2 = (x2 + ctrlx) / 2.0f; |
373 y2 = (y2 + ctrly) / 2f; |
373 y2 = (y2 + ctrly) / 2.0f; |
374 ctrlx = (x1 + x2) / 2f; |
374 ctrlx = (x1 + x2) / 2.0f; |
375 ctrly = (y1 + y2) / 2f; |
375 ctrly = (y1 + y2) / 2.0f; |
376 if (left != null) { |
376 if (left != null) { |
377 left[leftoff + 2] = x1; |
377 left[leftoff + 2] = x1; |
378 left[leftoff + 3] = y1; |
378 left[leftoff + 3] = y1; |
379 left[leftoff + 4] = ctrlx; |
379 left[leftoff + 4] = ctrlx; |
380 left[leftoff + 5] = ctrly; |
380 left[leftoff + 5] = ctrly; |