1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
2 // Licensed under the GNU General Public License version 2 ("the License").
3 // You may not use this file except in compliance with the License.
6 package org.ibex.graphics;
8 import org.ibex.util.*;
10 /** an abstract path; may contain splines and arcs */
13 public static final float PX_PER_INCH = 72;
14 public static final float INCHES_PER_CM = (float)0.3937;
15 public static final float INCHES_PER_MM = INCHES_PER_CM / 10;
16 private static final int DEFAULT_PATHLEN = 1000;
17 private static final float PI = (float)Math.PI;
19 // the number of vertices on this path
22 // the vertices of the path
23 float[] x = new float[DEFAULT_PATHLEN];
24 float[] y = new float[DEFAULT_PATHLEN];
26 // the type of each edge; type[i] is the type of the edge from x[i],y[i] to x[i+1],y[i+1]
27 byte[] type = new byte[DEFAULT_PATHLEN];
29 // bezier control points
30 float[] c1x = new float[DEFAULT_PATHLEN]; // or rx (arcto)
31 float[] c1y = new float[DEFAULT_PATHLEN]; // or ry (arcto)
32 float[] c2x = new float[DEFAULT_PATHLEN]; // or x-axis-rotation (arcto)
33 float[] c2y = new float[DEFAULT_PATHLEN]; // or large-arc << 1 | sweep (arcto)
35 boolean closed = false;
37 static final byte TYPE_MOVETO = 0;
38 static final byte TYPE_LINETO = 1;
39 static final byte TYPE_ARCTO = 2;
40 static final byte TYPE_CUBIC = 3;
41 static final byte TYPE_QUADRADIC = 4;
44 private String toString;
45 public String toString() { return toString; }
47 public Path(String s) {
49 Tokenizer t = new Tokenizer(s);
50 char last_command = 'M';
52 while(t.hasMoreTokens()) {
53 char command = t.parseCommand();
54 if (first && command == 'm') command = 'M';
55 if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
57 boolean relative = Character.toLowerCase(command) == command;
58 command = Character.toLowerCase(command);
59 parseSingleCommandAndArguments(t, command, relative);
60 last_command = command;
64 //#repeat width/height multiply_px/multiply_py horizontalBounds/verticalBounds
65 public long horizontalBounds(Affine a) {
67 float min = Float.MAX_VALUE;
68 float max = Float.MIN_VALUE;
69 for(int i=0; i<numvertices; i++) {
70 min = Math.min(min, a.multiply_px(x[i], y[i]));
71 max = Math.max(max, a.multiply_px(x[i], y[i]));
73 return Encode.twoFloatsToLong(max, min);
77 public long transform(Affine a, boolean forReal) { return transform(a, forReal, true); }
78 public long transform(Affine a, boolean forReal, boolean widthheight) {
79 float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
80 float maxx = Integer.MIN_VALUE; float maxy = Integer.MIN_VALUE;
81 for(int i=0; i<numvertices; i++) {
82 if (type[i] == TYPE_ARCTO) { /* FIXME!!! WRONG!!!! */ continue; }
83 float x = a.multiply_px(this.x[i], this.y[i]); if (x>maxx) maxx = x; if (x<minx) minx = x;
84 float y = a.multiply_py(this.x[i], this.y[i]); if (y>maxy) maxy = y; if (y<miny) miny = y;
85 float c1x = a.multiply_px(this.c1x[i], this.c1y[i]); if (c1x>maxx) maxx = c1x; if (c1x<minx) minx = c1x;
86 float c1y = a.multiply_py(this.c1x[i], this.c1y[i]); if (c1y>maxy) maxy = c1y; if (c1y<miny) miny = c1y;
87 float c2x = a.multiply_px(this.c2x[i], this.c2y[i]); if (c2x>maxx) maxx = c2x; if (c2x<minx) minx = c2x;
88 float c2y = a.multiply_py(this.c2x[i], this.c2y[i]); if (c2y>maxy) maxy = c2y; if (c2y<miny) miny = c2y;
90 this.x[i] = x; this.y[i] = y;
91 this.c1x[i] = c1x; this.c1y[i] = c1y;
92 this.c2x[i] = c2x; this.c2y[i] = c2y;
95 if (widthheight) return ((((long)Float.floatToIntBits(maxx - minx)) << 32) | ((long)Float.floatToIntBits(maxy - miny)));
96 else return ((((long)Float.floatToIntBits(minx)) << 32) | ((long)Float.floatToIntBits(miny)));
99 public void alignToOrigin() {
100 float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
101 for(int i=0; i<numvertices; i++) { if (x[i] < minx) minx = x[i]; if (y[i] < miny) miny = y[i]; }
102 for(int i=0; i<numvertices; i++) {
103 x[i] -= minx; y[i] -= miny;
104 if (type[i] == TYPE_ARCTO) continue;
105 c1x[i] -= minx; c2x[i] -= minx; c1y[i] -= miny; c2y[i] -= miny;
110 public static class Tokenizer {
111 // FIXME: check array bounds exception for improperly terminated string
114 char lastCommand = 'M';
115 public Tokenizer(String s) { this.s = s; }
117 public static Path parse(String s) {
118 if (s == null) return null;
119 Tokenizer t = new Tokenizer(s);
120 Path ret = new Path(s);
121 char last_command = 'M';
122 boolean first = true;
123 while(t.hasMoreTokens()) {
124 char command = t.parseCommand();
125 if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
127 boolean relative = Character.toLowerCase(command) == command;
128 command = Character.toLowerCase(command);
129 ret.parseSingleCommandAndArguments(t, command, relative);
130 last_command = command;
135 private void consumeWhitespace() {
136 while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
137 if (i < s.length() && s.charAt(i) == ',') i++;
138 while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
140 public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
141 public char parseCommand() {
143 char c = s.charAt(i);
144 if (!Character.isLetter(c)) return lastCommand;
146 return lastCommand = c;
148 public float parseFloat() {
151 float multiplier = 1;
152 for(; i < s.length(); i++) {
153 char c = s.charAt(i);
154 if (Character.isWhitespace(c) || c == ',' || (c == '-' && i != start)) break;
155 if (!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E' || c == '-')) {
156 if (c == '%') { // FIXME
157 } else if (s.regionMatches(i, "pt", 0, i+2)) { // FIXME
158 } else if (s.regionMatches(i, "em", 0, i+2)) { // FIXME
159 } else if (s.regionMatches(i, "pc", 0, i+2)) { // FIXME
160 } else if (s.regionMatches(i, "ex", 0, i+2)) { // FIXME
161 } else if (s.regionMatches(i, "mm", 0, i+2)) { i += 2; multiplier = INCHES_PER_MM * PX_PER_INCH; break;
162 } else if (s.regionMatches(i, "cm", 0, i+2)) { i += 2; multiplier = INCHES_PER_CM * PX_PER_INCH; break;
163 } else if (s.regionMatches(i, "in", 0, i+2)) { i += 2; multiplier = PX_PER_INCH; break;
164 } else if (s.regionMatches(i, "px", 0, i+2)) { i += 2; break;
165 } else if (Character.isLetter(c)) break;
166 throw new RuntimeException("didn't expect character \"" + c + "\" in a numeric constant");
169 //if (start == i) throw new RuntimeException("FIXME");
170 if (start == i) return (float)0.0;
172 return Float.parseFloat(s.substring(start, i)) * multiplier;
173 } catch (NumberFormatException nfe) {
174 Log.warn(Path.class, "offending string was \"" + s.substring(start, i) + "\"");
180 /** Creates a concrete vector path transformed through the given matrix. */
181 public void addTo(Polygon ret, Affine a) {
182 float NUMSTEPS = 5; // FIXME
183 ret.x[0] = a.multiply_px(x[0], y[0]);
184 ret.y[0] = a.multiply_py(x[0], y[0]);
186 for(int i=0; i<numvertices; i++) {
187 if (type[i] == TYPE_LINETO) {
190 ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
192 } else if (type[i] == TYPE_MOVETO) {
196 ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
198 } else if (type[i] == TYPE_ARCTO) {
202 float fa = ((int)c2y[i]) >> 1;
203 float fs = ((int)c2y[i]) & 1;
209 // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
210 float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
211 float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
212 float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
213 (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
214 float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
215 float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
216 float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
217 float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
219 // F.6.4 Conversion from center to endpoint parameterization
220 float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
221 float det = ux * vy - uy * vx;
222 float theta1 = (det < 0 ? -1 : 1) *
223 (float)Math.acos((ux * vx + uy * vy) /
224 ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
225 ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
226 vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
227 det = ux * vy - uy * vx;
228 float dtheta = (det < 0 ? -1 : 1) *
229 (float)Math.acos((ux * vx + uy * vy) /
230 ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
231 dtheta = dtheta % (float)(2 * Math.PI);
233 if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
234 if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
236 if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
237 else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
239 // FIXME: integrate F.6.6
240 // FIXME: isn't quite ending where it should...
242 // F.6.3: Parameterization alternatives
243 float theta = theta1;
244 for(int j=0; j<NUMSTEPS; j++) {
245 float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
246 ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
247 float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
248 ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
249 ret.add(a.multiply_px(rasterx, rastery), a.multiply_py(rasterx, rastery));
250 theta += dtheta / NUMSTEPS;
253 } else if (type[i] == TYPE_CUBIC) {
255 float ax = x[i+1] - 3 * c2x[i] + 3 * c1x[i] - x[i];
256 float bx = 3 * c2x[i] - 6 * c1x[i] + 3 * x[i];
257 float cx = 3 * c1x[i] - 3 * x[i];
259 float ay = y[i+1] - 3 * c2y[i] + 3 * c1y[i] - y[i];
260 float by = 3 * c2y[i] - 6 * c1y[i] + 3 * y[i];
261 float cy = 3 * c1y[i] - 3 * y[i];
264 float x0 = a.multiply_px(x[i], y[i]);
265 float y0 = a.multiply_py(x[i], y[i]);
266 float x1 = a.multiply_px(x[i+1], y[i+1]);
267 float y1 = a.multiply_py(x[i+1], y[i+1]);
268 float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
270 for(float t=0; t<1; t += 1 / (steps/20)) {
271 float rx = ax * t * t * t + bx * t * t + cx * t + dx;
272 float ry = ay * t * t * t + by * t * t + cy * t + dy;
273 ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
277 } else if (type[i] == TYPE_QUADRADIC) {
279 float bx = x[i+1] - 2 * c1x[i] + x[i];
280 float cx = 2 * c1x[i] - 2 * x[i];
282 float by = y[i+1] - 2 * c1y[i] + y[i];
283 float cy = 2 * c1y[i] - 2 * y[i];
286 float x0 = a.multiply_px(x[i], y[i]);
287 float y0 = a.multiply_py(x[i], y[i]);
288 float x1 = a.multiply_px(x[i+1], y[i+1]);
289 float y1 = a.multiply_py(x[i+1], y[i+1]);
290 float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
292 for(float t=0; t<1; t += 1 / (steps/20)) {
293 float rx = bx * t * t + cx * t + dx;
294 float ry = by * t * t + cy * t + dy;
295 ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
302 protected void parseSingleCommandAndArguments(Tokenizer t, char command, boolean relative) {
303 if (numvertices == 0 && command != 'm')
304 throw new RuntimeException("first command MUST be an 'm', not a " + command);
305 if (numvertices > x.length - 2) {
306 float[] new_x = new float[x.length * 2]; System.arraycopy(x, 0, new_x, 0, x.length); x = new_x;
307 float[] new_y = new float[y.length * 2]; System.arraycopy(y, 0, new_y, 0, y.length); y = new_y;
312 type[numvertices-1] = TYPE_LINETO;
313 for(where = numvertices-2; where >= 0 && type[where] != TYPE_MOVETO; where--);
314 x[numvertices] = x[where+1];
315 y[numvertices] = y[where+1];
318 // FIXME: actually, we should search back to the last 'z' or 'm', not just 'm'
323 if (numvertices > 0) type[numvertices-1] = TYPE_MOVETO;
324 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
325 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
326 if (numvertices > 2 && type[numvertices-2] == TYPE_MOVETO) {
327 x[numvertices-1] = x[numvertices];
328 y[numvertices-1] = y[numvertices];
335 case 'l': case 'h': case 'v': {
336 type[numvertices-1] = TYPE_LINETO;
337 float first = t.parseFloat(), second;
338 if (command == 'h') {
339 second = relative ? 0 : y[numvertices - 1];
340 } else if (command == 'v') {
341 second = first; first = relative ? 0 : x[numvertices - 1];
343 second = t.parseFloat();
345 x[numvertices] = first + (relative ? x[numvertices - 1] : 0);
346 y[numvertices] = second + (relative ? y[numvertices - 1] : 0);
352 type[numvertices-1] = TYPE_ARCTO;
353 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
354 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
355 c2x[numvertices-1] = (t.parseFloat() / 360) * 2 * PI;
356 c2y[numvertices-1] = (((int)t.parseFloat()) << 1) | (int)t.parseFloat();
357 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
358 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
363 case 's': case 'c': {
364 type[numvertices-1] = TYPE_CUBIC;
365 if (command == 'c') {
366 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
367 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
368 } else if (numvertices > 1 && type[numvertices-2] == TYPE_CUBIC) {
369 c1x[numvertices-1] = 2 * x[numvertices - 1] - c2x[numvertices-2];
370 c1y[numvertices-1] = 2 * y[numvertices - 1] - c2y[numvertices-2];
372 c1x[numvertices-1] = x[numvertices-1];
373 c1y[numvertices-1] = y[numvertices-1];
375 c2x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
376 c2y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
377 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
378 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
383 case 't': case 'q': {
384 type[numvertices-1] = TYPE_QUADRADIC;
385 if (command == 'q') {
386 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
387 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
388 } else if (numvertices > 1 && type[numvertices-2] == TYPE_QUADRADIC) {
389 c1x[numvertices-1] = 2 * x[numvertices - 1] - c1x[numvertices-2];
390 c1y[numvertices-1] = 2 * y[numvertices - 1] - c1y[numvertices-2];
392 c1x[numvertices-1] = x[numvertices-1];
393 c1y[numvertices-1] = y[numvertices-1];
395 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
396 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
406 // invariant: after this loop, no two lines intersect other than at a vertex
408 int index = numvertices - 2;
409 for(int i=0; i<Math.min(numvertices - 3, index); i++) {
410 for(int j = index; j < numvertices - 1; j++) {
412 // I'm not sure how to deal with vertical lines...
413 if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
415 float islope = (y[i+1] - y[i]) / (x[i+1] - x[i]);
416 float jslope = (y[j+1] - y[j]) / (x[j+1] - x[j]);
417 if (islope == jslope) continue; // parallel lines can't intersect
419 float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
420 float _y = islope * (_x - x[i]) + y[i];
422 if (_x > Math.min(x[i+1], x[i]) && _x < Math.max(x[i+1], x[i]) &&
423 _x > Math.min(x[j+1], x[j]) && _x < Math.max(x[j+1], x[j])) {
424 // FIXME: something's not right in here. See if we can do without fracturing line 'i'.
425 for(int k = ++numvertices; k>i; k--) { x[k] = x[k - 1]; y[k] = y[k - 1]; }
428 x[numvertices] = x[numvertices - 1]; x[numvertices - 1] = _x;
429 y[numvertices] = y[numvertices - 1]; y[numvertices - 1] = _y;
430 edges[numedges++] = numvertices - 1; numvertices++;
432 break; // actually 'continue' the outermost loop