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 |
27 |
27 |
28 final class Curve { |
28 final class Curve { |
29 |
29 |
30 float ax, ay, bx, by, cx, cy, dx, dy; |
30 float ax, ay, bx, by, cx, cy, dx, dy; |
31 float dax, day, dbx, dby; |
31 float dax, day, dbx, dby; |
32 // shared iterator instance |
|
33 private final BreakPtrIterator iterator = new BreakPtrIterator(); |
|
34 |
32 |
35 Curve() { |
33 Curve() { |
36 } |
34 } |
37 |
35 |
38 void set(float[] points, int type) { |
36 void set(float[] points, int type) { |
56 void set(float x1, float y1, |
54 void set(float x1, float y1, |
57 float x2, float y2, |
55 float x2, float y2, |
58 float x3, float y3, |
56 float x3, float y3, |
59 float x4, float y4) |
57 float x4, float y4) |
60 { |
58 { |
61 ax = 3f * (x2 - x3) + x4 - x1; |
59 ax = 3.0f * (x2 - x3) + x4 - x1; |
62 ay = 3f * (y2 - y3) + y4 - y1; |
60 ay = 3.0f * (y2 - y3) + y4 - y1; |
63 bx = 3f * (x1 - 2f * x2 + x3); |
61 bx = 3.0f * (x1 - 2.0f * x2 + x3); |
64 by = 3f * (y1 - 2f * y2 + y3); |
62 by = 3.0f * (y1 - 2.0f * y2 + y3); |
65 cx = 3f * (x2 - x1); |
63 cx = 3.0f * (x2 - x1); |
66 cy = 3f * (y2 - y1); |
64 cy = 3.0f * (y2 - y1); |
67 dx = x1; |
65 dx = x1; |
68 dy = y1; |
66 dy = y1; |
69 dax = 3f * ax; day = 3f * ay; |
67 dax = 3.0f * ax; day = 3.0f * ay; |
70 dbx = 2f * bx; dby = 2f * by; |
68 dbx = 2.0f * bx; dby = 2.0f * by; |
71 } |
69 } |
72 |
70 |
73 void set(float x1, float y1, |
71 void set(float x1, float y1, |
74 float x2, float y2, |
72 float x2, float y2, |
75 float x3, float y3) |
73 float x3, float y3) |
76 { |
74 { |
77 ax = 0f; ay = 0f; |
75 ax = 0.0f; ay = 0.0f; |
78 bx = x1 - 2f * x2 + x3; |
76 bx = x1 - 2.0f * x2 + x3; |
79 by = y1 - 2f * y2 + y3; |
77 by = y1 - 2.0f * y2 + y3; |
80 cx = 2f * (x2 - x1); |
78 cx = 2.0f * (x2 - x1); |
81 cy = 2f * (y2 - y1); |
79 cy = 2.0f * (y2 - y1); |
82 dx = x1; |
80 dx = x1; |
83 dy = y1; |
81 dy = y1; |
84 dax = 0f; day = 0f; |
82 dax = 0.0f; day = 0.0f; |
85 dbx = 2f * bx; dby = 2f * by; |
83 dbx = 2.0f * bx; dby = 2.0f * by; |
86 } |
84 } |
87 |
85 |
88 float xat(float t) { |
86 float xat(float t) { |
89 return t * (t * (t * ax + bx) + cx) + dx; |
87 return t * (t * (t * ax + bx) + cx) + dx; |
90 } |
88 } |
111 int infPoints(float[] pts, int off) { |
109 int infPoints(float[] pts, int off) { |
112 // inflection point at t if -f'(t)x*f''(t)y + f'(t)y*f''(t)x == 0 |
110 // inflection point at t if -f'(t)x*f''(t)y + f'(t)y*f''(t)x == 0 |
113 // Fortunately, this turns out to be quadratic, so there are at |
111 // Fortunately, this turns out to be quadratic, so there are at |
114 // most 2 inflection points. |
112 // most 2 inflection points. |
115 final float a = dax * dby - dbx * day; |
113 final float a = dax * dby - dbx * day; |
116 final float b = 2f * (cy * dax - day * cx); |
114 final float b = 2.0f * (cy * dax - day * cx); |
117 final float c = cy * dbx - cx * dby; |
115 final float c = cy * dbx - cx * dby; |
118 |
116 |
119 return Helpers.quadraticRoots(a, b, c, pts, off); |
117 return Helpers.quadraticRoots(a, b, c, pts, off); |
120 } |
118 } |
121 |
119 |
126 assert pts.length >= off + 4; |
124 assert pts.length >= off + 4; |
127 |
125 |
128 // these are the coefficients of some multiple of g(t) (not g(t), |
126 // these are the coefficients of some multiple of g(t) (not g(t), |
129 // because the roots of a polynomial are not changed after multiplication |
127 // because the roots of a polynomial are not changed after multiplication |
130 // by a constant, and this way we save a few multiplications). |
128 // by a constant, and this way we save a few multiplications). |
131 final float a = 2f * (dax*dax + day*day); |
129 final float a = 2.0f * (dax*dax + day*day); |
132 final float b = 3f * (dax*dbx + day*dby); |
130 final float b = 3.0f * (dax*dbx + day*dby); |
133 final float c = 2f * (dax*cx + day*cy) + dbx*dbx + dby*dby; |
131 final float c = 2.0f * (dax*cx + day*cy) + dbx*dbx + dby*dby; |
134 final float d = dbx*cx + dby*cy; |
132 final float d = dbx*cx + dby*cy; |
135 return Helpers.cubicRootsInAB(a, b, c, d, pts, off, 0f, 1f); |
133 return Helpers.cubicRootsInAB(a, b, c, d, pts, off, 0.0f, 1.0f); |
136 } |
134 } |
137 |
135 |
138 // Tries to find the roots of the function ROC(t)-w in [0, 1). It uses |
136 // Tries to find the roots of the function ROC(t)-w in [0, 1). It uses |
139 // a variant of the false position algorithm to find the roots. False |
137 // a variant of the false position algorithm to find the roots. False |
140 // position requires that 2 initial values x0,x1 be given, and that the |
138 // position requires that 2 initial values x0,x1 be given, and that the |
151 int rootsOfROCMinusW(float[] roots, int off, final float w, final float err) { |
149 int rootsOfROCMinusW(float[] roots, int off, final float w, final float err) { |
152 // no OOB exception, because by now off<=6, and roots.length >= 10 |
150 // no OOB exception, because by now off<=6, and roots.length >= 10 |
153 assert off <= 6 && roots.length >= 10; |
151 assert off <= 6 && roots.length >= 10; |
154 int ret = off; |
152 int ret = off; |
155 int numPerpdfddf = perpendiculardfddf(roots, off); |
153 int numPerpdfddf = perpendiculardfddf(roots, off); |
156 float t0 = 0, ft0 = ROCsq(t0) - w*w; |
154 float t0 = 0.0f, ft0 = ROCsq(t0) - w*w; |
157 roots[off + numPerpdfddf] = 1f; // always check interval end points |
155 roots[off + numPerpdfddf] = 1.0f; // always check interval end points |
158 numPerpdfddf++; |
156 numPerpdfddf++; |
159 for (int i = off; i < off + numPerpdfddf; i++) { |
157 for (int i = off; i < off + numPerpdfddf; i++) { |
160 float t1 = roots[i], ft1 = ROCsq(t1) - w*w; |
158 float t1 = roots[i], ft1 = ROCsq(t1) - w*w; |
161 if (ft0 == 0f) { |
159 if (ft0 == 0.0f) { |
162 roots[ret++] = t0; |
160 roots[ret++] = t0; |
163 } else if (ft1 * ft0 < 0f) { // have opposite signs |
161 } else if (ft1 * ft0 < 0.0f) { // have opposite signs |
164 // (ROC(t)^2 == w^2) == (ROC(t) == w) is true because |
162 // (ROC(t)^2 == w^2) == (ROC(t) == w) is true because |
165 // ROC(t) >= 0 for all t. |
163 // ROC(t) >= 0 for all t. |
166 roots[ret++] = falsePositionROCsqMinusX(t0, t1, w*w, err); |
164 roots[ret++] = falsePositionROCsqMinusX(t0, t1, w*w, err); |
167 } |
165 } |
168 t0 = t1; |
166 t0 = t1; |
218 return r; |
216 return r; |
219 } |
217 } |
220 |
218 |
221 private static boolean sameSign(float x, float y) { |
219 private static boolean sameSign(float x, float y) { |
222 // another way is to test if x*y > 0. This is bad for small x, y. |
220 // another way is to test if x*y > 0. This is bad for small x, y. |
223 return (x < 0f && y < 0f) || (x > 0f && y > 0f); |
221 return (x < 0.0f && y < 0.0f) || (x > 0.0f && y > 0.0f); |
224 } |
222 } |
225 |
223 |
226 // returns the radius of curvature squared at t of this curve |
224 // returns the radius of curvature squared at t of this curve |
227 // see http://en.wikipedia.org/wiki/Radius_of_curvature_(applications) |
225 // see http://en.wikipedia.org/wiki/Radius_of_curvature_(applications) |
228 private float ROCsq(final float t) { |
226 private float ROCsq(final float t) { |
229 // dx=xat(t) and dy=yat(t). These calls have been inlined for efficiency |
227 // dx=xat(t) and dy=yat(t). These calls have been inlined for efficiency |
230 final float dx = t * (t * dax + dbx) + cx; |
228 final float dx = t * (t * dax + dbx) + cx; |
231 final float dy = t * (t * day + dby) + cy; |
229 final float dy = t * (t * day + dby) + cy; |
232 final float ddx = 2f * dax * t + dbx; |
230 final float ddx = 2.0f * dax * t + dbx; |
233 final float ddy = 2f * day * t + dby; |
231 final float ddy = 2.0f * day * t + dby; |
234 final float dx2dy2 = dx*dx + dy*dy; |
232 final float dx2dy2 = dx*dx + dy*dy; |
235 final float ddx2ddy2 = ddx*ddx + ddy*ddy; |
233 final float ddx2ddy2 = ddx*ddx + ddy*ddy; |
236 final float ddxdxddydy = ddx*dx + ddy*dy; |
234 final float ddxdxddydy = ddx*dx + ddy*dy; |
237 return dx2dy2*((dx2dy2*dx2dy2) / (dx2dy2 * ddx2ddy2 - ddxdxddydy*ddxdxddydy)); |
235 return dx2dy2*((dx2dy2*dx2dy2) / (dx2dy2 * ddx2ddy2 - ddxdxddydy*ddxdxddydy)); |
238 } |
236 } |
239 |
|
240 // curve to be broken should be in pts |
|
241 // this will change the contents of pts but not Ts |
|
242 // TODO: There's no reason for Ts to be an array. All we need is a sequence |
|
243 // of t values at which to subdivide. An array statisfies this condition, |
|
244 // but is unnecessarily restrictive. Ts should be an Iterator<Float> instead. |
|
245 // Doing this will also make dashing easier, since we could easily make |
|
246 // LengthIterator an Iterator<Float> and feed it to this function to simplify |
|
247 // the loop in Dasher.somethingTo. |
|
248 BreakPtrIterator breakPtsAtTs(final float[] pts, final int type, |
|
249 final float[] Ts, final int numTs) |
|
250 { |
|
251 assert pts.length >= 2*type && numTs <= Ts.length; |
|
252 |
|
253 // initialize shared iterator: |
|
254 iterator.init(pts, type, Ts, numTs); |
|
255 |
|
256 return iterator; |
|
257 } |
|
258 |
|
259 static final class BreakPtrIterator { |
|
260 private int nextCurveIdx; |
|
261 private int curCurveOff; |
|
262 private float prevT; |
|
263 private float[] pts; |
|
264 private int type; |
|
265 private float[] ts; |
|
266 private int numTs; |
|
267 |
|
268 void init(final float[] pts, final int type, |
|
269 final float[] ts, final int numTs) { |
|
270 this.pts = pts; |
|
271 this.type = type; |
|
272 this.ts = ts; |
|
273 this.numTs = numTs; |
|
274 |
|
275 nextCurveIdx = 0; |
|
276 curCurveOff = 0; |
|
277 prevT = 0f; |
|
278 } |
|
279 |
|
280 public boolean hasNext() { |
|
281 return nextCurveIdx <= numTs; |
|
282 } |
|
283 |
|
284 public int next() { |
|
285 int ret; |
|
286 if (nextCurveIdx < numTs) { |
|
287 float curT = ts[nextCurveIdx]; |
|
288 float splitT = (curT - prevT) / (1f - prevT); |
|
289 Helpers.subdivideAt(splitT, |
|
290 pts, curCurveOff, |
|
291 pts, 0, |
|
292 pts, type, type); |
|
293 prevT = curT; |
|
294 ret = 0; |
|
295 curCurveOff = type; |
|
296 } else { |
|
297 ret = curCurveOff; |
|
298 } |
|
299 nextCurveIdx++; |
|
300 return ret; |
|
301 } |
|
302 } |
|
303 } |
237 } |
304 |
|