2 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
7 // FIXME: offer a "subpixel" mode where we pass floats to the Platform and don't do any snapping
8 // FIXME: fracture when realizing instead of when parsing?
16 - filters (filtering of a group must be performed AFTER the group is assembled; sep. canvas)
19 - bump caps [requires Paint that can fill circles...] [remember to distinguish between closed/unclosed]
23 - bump (easy, but requires 'round' Paint)
24 - subtree sharing? otherwise the memory consumption might be outrageous... clone="" attribute?
26 - intersect clip regions (linearity)
27 - clip on trapezoids, not pixels
28 - faster gradients and patterns:
29 - transform each corner of the trapezoid and then interpolate
32 /** XWT's fully conformant Static SVG Viewer; see SVG spec, section G.7 */
33 public final class VectorGraphics {
35 // Private Constants ///////////////////////////////////////////////////////////////////
37 private static final int DEFAULT_PATHLEN = 1000;
38 private static final float PI = (float)Math.PI;
41 // Public entry points /////////////////////////////////////////////////////////////////
43 public static VectorPath parseVectorPath(String s) {
44 if (s == null) return null;
45 PathTokenizer t = new PathTokenizer(s);
46 VectorPath ret = new VectorPath();
47 char last_command = 'M';
49 while(t.hasMoreTokens()) {
50 char command = t.parseCommand();
51 if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
53 boolean relative = Character.toLowerCase(command) == command;
54 command = Character.toLowerCase(command);
55 ret.parseSingleCommandAndArguments(t, command, relative);
56 last_command = command;
62 // Affine //////////////////////////////////////////////////////////////////////////////
64 /** an affine transform; all operations are destructive */
65 public static final class Affine {
70 public float a, b, c, d, e, f;
72 Affine(float _a, float _b, float _c, float _d, float _e, float _f) { a = _a; b = _b; c = _c; d = _d; e = _e; f = _f; }
73 public String toString() { return "[ " + a + ", " + b + ", " + c + ", " + d + ", " + e + ", " + f + " ]"; }
74 public Affine copy() { return new Affine(a, b, c, d, e, f); }
75 public static Affine identity() { return new Affine(1, 0, 0, 1, 0, 0); }
76 public static Affine scale(float sx, float sy) { return new Affine(sx, 0, 0, sy, 0, 0); }
77 public static Affine shear(float degrees) {
78 return new Affine(1, 0, (float)Math.tan(degrees * (float)(Math.PI / 180.0)), 1, 0, 0); }
79 public static Affine translate(float tx, float ty) { return new Affine(1, 0, 0, 1, tx, ty); }
80 public static Affine flip(boolean horiz, boolean vert) { return new Affine(horiz ? -1 : 1, 0, 0, vert ? -1 : 1, 0, 0); }
81 public float multiply_px(float x, float y) { return x * a + y * c + e; }
82 public float multiply_py(float x, float y) { return x * b + y * d + f; }
83 public boolean equalsIgnoringTranslation(Affine x) { return a == x.a && b == x.b && c == x.c && d == x.d; }
85 public boolean equals(Object o) {
86 if (!(o instanceof Affine)) return false;
88 return a == x.a && b == x.b && c == x.c && d == x.d && e == x.e && f == x.f;
91 public static Affine rotate(float degrees) {
92 float s = (float)Math.sin(degrees * (float)(Math.PI / 180.0));
93 float c = (float)Math.cos(degrees * (float)(Math.PI / 180.0));
94 return new Affine(c, s, -s, c, 0, 0);
97 /** this = this * a */
98 public Affine multiply(Affine A) {
99 float _a = this.a * A.a + this.b * A.c;
100 float _b = this.a * A.b + this.b * A.d;
101 float _c = this.c * A.a + this.d * A.c;
102 float _d = this.c * A.b + this.d * A.d;
103 float _e = this.e * A.a + this.f * A.c + A.e;
104 float _f = this.e * A.b + this.f * A.d + A.f;
105 a = _a; b = _b; c = _c; d = _d; e = _e; f = _f;
109 public void invert() {
110 float det = 1 / (a * d - b * c);
112 float _b = -1 * b * det;
113 float _c = -1 * c * det;
115 float _e = -1 * e * a - f * c;
116 float _f = -1 * e * b - f * d;
117 a = _a; b = _b; c = _c; d = _d; e = _e; f = _f;
122 // PathTokenizer //////////////////////////////////////////////////////////////////////////////
124 public static Affine parseTransform(String t) {
125 if (t == null) return null;
127 Affine ret = VectorGraphics.Affine.identity();
128 while (t.length() > 0) {
129 if (t.startsWith("skewX(")) {
132 } else if (t.startsWith("shear(")) {
133 // FIXME: nonstandard; remove this
134 ret.multiply(VectorGraphics.Affine.shear(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(')')))));
136 } else if (t.startsWith("skewY(")) {
139 } else if (t.startsWith("rotate(")) {
140 String sub = t.substring(t.indexOf('(') + 1, t.indexOf(')'));
141 if (sub.indexOf(',') != -1) {
142 float angle = Float.parseFloat(sub.substring(0, sub.indexOf(',')));
143 sub = sub.substring(sub.indexOf(',') + 1);
144 float cx = Float.parseFloat(sub.substring(0, sub.indexOf(',')));
145 sub = sub.substring(sub.indexOf(',') + 1);
146 float cy = Float.parseFloat(sub);
147 ret.multiply(VectorGraphics.Affine.translate(cx, cy));
148 ret.multiply(VectorGraphics.Affine.rotate(angle));
149 ret.multiply(VectorGraphics.Affine.translate(-1 * cx, -1 * cy));
151 ret.multiply(VectorGraphics.Affine.rotate(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(')')))));
154 } else if (t.startsWith("translate(")) {
155 String sub = t.substring(t.indexOf('(') + 1, t.indexOf(')'));
156 if (sub.indexOf(',') > -1) {
157 ret.multiply(VectorGraphics.Affine.translate(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(','))),
158 Float.parseFloat(t.substring(t.indexOf(',') + 1, t.indexOf(')')))));
160 ret.multiply(VectorGraphics.Affine.translate(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(','))), 0));
163 } else if (t.startsWith("flip(")) {
164 String which = t.substring(t.indexOf('(') + 1, t.indexOf(')'));
165 ret.multiply(VectorGraphics.Affine.flip(which.equals("horizontal"), which.equals("vertical")));
167 } else if (t.startsWith("scale(")) {
168 String sub = t.substring(t.indexOf('(') + 1, t.indexOf(')'));
169 if (sub.indexOf(',') > -1) {
170 ret.multiply(VectorGraphics.Affine.scale(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(','))),
171 Float.parseFloat(t.substring(t.indexOf(',') + 1, t.indexOf(')')))));
173 ret.multiply(VectorGraphics.Affine.scale(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(','))),
174 Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(',')))));
177 } else if (t.startsWith("matrix(")) {
178 // FIXME: is this mapped right?
179 float d[] = new float[6];
180 StringTokenizer st = new StringTokenizer(t, ",", false);
181 for(int i=0; i<6; i++)
182 d[i] = Float.parseFloat(st.nextToken());
183 ret.multiply(new VectorGraphics.Affine(d[0], d[1], d[2], d[3], d[4], d[5]));
185 t = t.substring(t.indexOf(')') + 1).trim();
190 public static final float PX_PER_INCH = 72;
191 public static final float INCHES_PER_CM = (float)0.3937;
192 public static final float INCHES_PER_MM = INCHES_PER_CM / 10;
194 public static class PathTokenizer {
195 // FIXME: check array bounds exception for improperly terminated string
198 char lastCommand = 'M';
199 public PathTokenizer(String s) { this.s = s; }
200 private void consumeWhitespace() {
201 while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
202 if (i < s.length() && s.charAt(i) == ',') i++;
203 while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
205 public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
206 public char parseCommand() {
208 char c = s.charAt(i);
209 if (!Character.isLetter(c)) return lastCommand;
211 return lastCommand = c;
213 public float parseFloat() {
216 float multiplier = 1;
217 for(; i < s.length(); i++) {
218 char c = s.charAt(i);
219 if (Character.isWhitespace(c) || c == ',' || (c == '-' && i != start)) break;
220 if (!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E' || c == '-')) {
221 if (c == '%') { // FIXME
222 } else if (s.regionMatches(i, "pt", 0, i+2)) { // FIXME
223 } else if (s.regionMatches(i, "em", 0, i+2)) { // FIXME
224 } else if (s.regionMatches(i, "pc", 0, i+2)) { // FIXME
225 } else if (s.regionMatches(i, "ex", 0, i+2)) { // FIXME
226 } else if (s.regionMatches(i, "mm", 0, i+2)) { i += 2; multiplier = INCHES_PER_MM * PX_PER_INCH; break;
227 } else if (s.regionMatches(i, "cm", 0, i+2)) { i += 2; multiplier = INCHES_PER_CM * PX_PER_INCH; break;
228 } else if (s.regionMatches(i, "in", 0, i+2)) { i += 2; multiplier = PX_PER_INCH; break;
229 } else if (s.regionMatches(i, "px", 0, i+2)) { i += 2; break;
230 } else if (Character.isLetter(c)) break;
231 throw new RuntimeException("didn't expect character \"" + c + "\" in a numeric constant");
234 if (start == i) throw new RuntimeException("FIXME");
235 return Float.parseFloat(s.substring(start, i)) * multiplier;
240 // Abstract Path //////////////////////////////////////////////////////////////////////////////
242 /** an abstract path; may contain splines and arcs */
243 public static class VectorPath {
245 // the number of vertices on this path
248 // the vertices of the path
249 float[] x = new float[DEFAULT_PATHLEN];
250 float[] y = new float[DEFAULT_PATHLEN];
252 // 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]
253 byte[] type = new byte[DEFAULT_PATHLEN];
255 // bezier control points
256 float[] c1x = new float[DEFAULT_PATHLEN]; // or rx (arcto)
257 float[] c1y = new float[DEFAULT_PATHLEN]; // or ry (arcto)
258 float[] c2x = new float[DEFAULT_PATHLEN]; // or x-axis-rotation (arcto)
259 float[] c2y = new float[DEFAULT_PATHLEN]; // or large-arc << 1 | sweep (arcto)
261 boolean closed = false;
263 static final byte TYPE_MOVETO = 0;
264 static final byte TYPE_LINETO = 1;
265 static final byte TYPE_ARCTO = 2;
266 static final byte TYPE_CUBIC = 3;
267 static final byte TYPE_QUADRADIC = 4;
269 /** Creates a concrete vector path transformed through the given matrix. */
270 public RasterPath realize(Affine a) {
272 RasterPath ret = new RasterPath();
273 int NUMSTEPS = 5; // FIXME
275 ret.x[0] = (int)Math.round(a.multiply_px(x[0], y[0]));
276 ret.y[0] = (int)Math.round(a.multiply_py(x[0], y[0]));
278 for(int i=1; i<numvertices; i++) {
279 if (type[i] == TYPE_LINETO) {
282 ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
283 ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
284 ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
286 } else if (type[i] == TYPE_MOVETO) {
289 ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
290 ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
293 } else if (type[i] == TYPE_ARCTO) {
297 float fa = ((int)c2y[i]) >> 1;
298 float fs = ((int)c2y[i]) & 1;
304 // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
305 float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
306 float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
307 float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
308 (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
309 float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
310 float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
311 float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
312 float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
314 // F.6.4 Conversion from center to endpoint parameterization
315 float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
316 float det = ux * vy - uy * vx;
317 float theta1 = (det < 0 ? -1 : 1) *
318 (float)Math.acos((ux * vx + uy * vy) /
319 ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
320 ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
321 vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
322 det = ux * vy - uy * vx;
323 float dtheta = (det < 0 ? -1 : 1) *
324 (float)Math.acos((ux * vx + uy * vy) /
325 ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
326 dtheta = dtheta % (float)(2 * Math.PI);
328 if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
329 if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
331 if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
332 else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
334 // FIXME: integrate F.6.6
335 // FIXME: isn't quite ending where it should...
337 // F.6.3: Parameterization alternatives
338 float theta = theta1;
339 for(int j=0; j<NUMSTEPS; j++) {
340 float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
341 ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
342 float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
343 ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
344 ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rasterx, rastery));
345 ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rasterx, rastery));
346 ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
347 theta += dtheta / NUMSTEPS;
350 } else if (type[i] == TYPE_CUBIC) {
352 float ax = x[i+1] - 3 * c2x[i] + 3 * c1x[i] - x[i];
353 float bx = 3 * c2x[i] - 6 * c1x[i] + 3 * x[i];
354 float cx = 3 * c1x[i] - 3 * x[i];
356 float ay = y[i+1] - 3 * c2y[i] + 3 * c1y[i] - y[i];
357 float by = 3 * c2y[i] - 6 * c1y[i] + 3 * y[i];
358 float cy = 3 * c1y[i] - 3 * y[i];
361 for(float t=0; t<1; t += 1 / (float)NUMSTEPS) {
362 float rx = ax * t * t * t + bx * t * t + cx * t + dx;
363 float ry = ay * t * t * t + by * t * t + cy * t + dy;
364 ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
365 ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
366 ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
370 } else if (type[i] == TYPE_QUADRADIC) {
372 float bx = x[i+1] - 2 * c1x[i] + x[i];
373 float cx = 2 * c1x[i] - 2 * x[i];
375 float by = y[i+1] - 2 * c1y[i] + y[i];
376 float cy = 2 * c1y[i] - 2 * y[i];
379 for(float t=0; t<1; t += 1 / (float)NUMSTEPS) {
380 float rx = bx * t * t + cx * t + dx;
381 float ry = by * t * t + cy * t + dy;
382 ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
383 ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
384 ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
391 if (ret.numedges > 0) ret.sort(0, ret.numedges - 1, false);
395 protected void parseSingleCommandAndArguments(PathTokenizer t, char command, boolean relative) {
396 if (numvertices == 0 && command != 'm') throw new RuntimeException("first command MUST be an 'm'");
397 if (numvertices > x.length - 2) {
398 float[] new_x = new float[x.length * 2]; System.arraycopy(x, 0, new_x, 0, x.length); x = new_x;
399 float[] new_y = new float[y.length * 2]; System.arraycopy(y, 0, new_y, 0, y.length); y = new_y;
404 type[numvertices-1] = TYPE_LINETO;
405 for(where = numvertices - 1; where > 0; where--)
406 if (type[where - 1] == TYPE_MOVETO) break;
407 x[numvertices] = x[where];
408 y[numvertices] = y[where];
415 if (numvertices > 0) type[numvertices-1] = TYPE_MOVETO;
416 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
417 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
422 case 'l': case 'h': case 'v': {
423 type[numvertices-1] = TYPE_LINETO;
424 float first = t.parseFloat(), second;
425 if (command == 'h') {
426 second = relative ? 0 : y[numvertices - 1];
427 } else if (command == 'v') {
428 second = first; first = relative ? 0 : x[numvertices - 1];
430 second = t.parseFloat();
432 x[numvertices] = first + (relative ? x[numvertices - 1] : 0);
433 y[numvertices] = second + (relative ? y[numvertices - 1] : 0);
439 type[numvertices-1] = TYPE_ARCTO;
440 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
441 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
442 c2x[numvertices-1] = (t.parseFloat() / 360) * 2 * PI;
443 c2y[numvertices-1] = (((int)t.parseFloat()) << 1) | (int)t.parseFloat();
444 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
445 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
450 case 's': case 'c': {
451 type[numvertices-1] = TYPE_CUBIC;
452 if (command == 'c') {
453 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
454 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
455 } else if (numvertices > 1 && type[numvertices-2] == TYPE_CUBIC) {
456 c1x[numvertices-1] = 2 * x[numvertices - 1] - c2x[numvertices-2];
457 c1y[numvertices-1] = 2 * y[numvertices - 1] - c2y[numvertices-2];
459 c1x[numvertices-1] = x[numvertices-1];
460 c1y[numvertices-1] = y[numvertices-1];
462 c2x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
463 c2y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
464 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
465 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
470 case 't': case 'q': {
471 type[numvertices-1] = TYPE_QUADRADIC;
472 if (command == 'q') {
473 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
474 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
475 } else if (numvertices > 1 && type[numvertices-2] == TYPE_QUADRADIC) {
476 c1x[numvertices-1] = 2 * x[numvertices - 1] - c1x[numvertices-2];
477 c1y[numvertices-1] = 2 * y[numvertices - 1] - c1y[numvertices-2];
479 c1x[numvertices-1] = x[numvertices-1];
480 c1y[numvertices-1] = y[numvertices-1];
482 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
483 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
493 // invariant: after this loop, no two lines intersect other than at a vertex
495 int index = numvertices - 2;
496 for(int i=0; i<Math.min(numvertices - 3, index); i++) {
497 for(int j = index; j < numvertices - 1; j++) {
499 // I'm not sure how to deal with vertical lines...
500 if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
502 float islope = (y[i+1] - y[i]) / (x[i+1] - x[i]);
503 float jslope = (y[j+1] - y[j]) / (x[j+1] - x[j]);
504 if (islope == jslope) continue; // parallel lines can't intersect
506 float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
507 float _y = islope * (_x - x[i]) + y[i];
509 if (_x > Math.min(x[i+1], x[i]) && _x < Math.max(x[i+1], x[i]) &&
510 _x > Math.min(x[j+1], x[j]) && _x < Math.max(x[j+1], x[j])) {
511 // FIXME: something's not right in here. See if we can do without fracturing line 'i'.
512 for(int k = ++numvertices; k>i; k--) { x[k] = x[k - 1]; y[k] = y[k - 1]; }
515 x[numvertices] = x[numvertices - 1]; x[numvertices - 1] = _x;
516 y[numvertices] = y[numvertices - 1]; y[numvertices - 1] = _y;
517 edges[numedges++] = numvertices - 1; numvertices++;
519 break; // actually 'continue' the outermost loop
531 // Rasterized Vector Path //////////////////////////////////////////////////////////////////////////////
534 public static class RasterPath {
536 // the vertices of this path
537 int[] x = new int[DEFAULT_PATHLEN];
538 int[] y = new int[DEFAULT_PATHLEN];
542 * A list of the vertices on this path which *start* an *edge* (rather than a moveto), sorted by increasing y.
543 * example: x[edges[1]],y[edges[1]] - x[edges[i]+1],y[edges[i]+1] is the second-topmost edge
544 * note that if x[i],y[i] - x[i+1],y[i+1] is a MOVETO, then no element in edges will be equal to i
546 int[] edges = new int[DEFAULT_PATHLEN];
549 /** translate a rasterized path */
550 public void translate(int dx, int dy) { for(int i=0; i<numvertices; i++) { x[i] += dx; y[i] += dy; } }
552 /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */
553 int sort(int left, int right, boolean partition) {
556 middle = (left + right) / 2;
557 int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;
558 for (i = left - 1, j = right; ; ) {
559 while (y[edges[++i]] < y[edges[right]]);
560 while (j > left && y[edges[--j]] > y[edges[right]]);
562 s = edges[i]; edges[i] = edges[j]; edges[j] = s;
564 s = edges[right]; edges[right] = edges[i]; edges[i] = s;
567 if (left >= right) return 0;
568 int p = sort(left, right, true);
569 sort(left, p - 1, false);
570 sort(p + 1, right, false);
575 /** finds the x value at which the line intercepts the line y=_y */
576 private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {
577 if (includeTop ? (_y < Math.min(y[i], y[i+1])) : (_y <= Math.min(y[i], y[i+1])))
578 return Integer.MIN_VALUE;
579 if (includeBottom ? (_y > Math.max(y[i], y[i+1])) : (_y >= Math.max(y[i], y[i+1])))
580 return Integer.MIN_VALUE;
581 return (int)Math.round((((float)(x[i + 1] - x[i])) /
582 ((float)(y[i + 1] - y[i])) ) * ((float)(_y - y[i])) + x[i]);
585 /** fill the interior of the path */
586 public void fill(PixelBuffer buf, Paint paint) {
587 if (numedges == 0) return;
588 int y0 = y[edges[0]], y1 = y0;
589 boolean useEvenOdd = false;
591 // we iterate over all endpoints in increasing y-coordinate order
592 for(int index = 1; index<numedges; index++) {
595 // we now examine the horizontal band between y=y0 and y=y1
597 y1 = y[edges[index]];
598 if (y0 == y1) continue;
600 // within this band, we iterate over all edges
601 int x0 = Integer.MIN_VALUE;
602 int leftSegment = -1;
604 int x1 = Integer.MAX_VALUE;
605 int rightSegment = Integer.MAX_VALUE;
606 for(int i=0; i<numedges; i++) {
607 if (y[edges[i]] == y[edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.
608 // we order the segments by the x-coordinate of their midpoint;
609 // since segments cannot intersect, this is a well-ordering
610 int i0 = intercept(edges[i], y0, true, false);
611 int i1 = intercept(edges[i], y1, false, true);
612 if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;
613 int midpoint = i0 + i1;
614 if (midpoint < x0) continue;
615 if (midpoint == x0 && i <= leftSegment) continue;
616 if (midpoint > x1) continue;
617 if (midpoint == x1 && i >= rightSegment) continue;
621 if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;
622 if (leftSegment != -1)
623 if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0))
624 paint.fillTrapezoid(intercept(edges[leftSegment], y0, true, true),
625 intercept(edges[rightSegment], y0, true, true), y0,
626 intercept(edges[leftSegment], y1, true, true),
627 intercept(edges[rightSegment], y1, true, true), y1,
629 if (useEvenOdd) count++;
630 else count += (y[edges[rightSegment]] < y[edges[rightSegment]+1]) ? -1 : 1;
631 leftSegment = rightSegment; x0 = x1;
636 /** stroke the outline of the path */
637 public void stroke(PixelBuffer buf, int width, int color) { stroke(buf, width, color, null, 0, 0); }
638 public void stroke(PixelBuffer buf, int width, int color, String dashArray, int dashOffset, float segLength) {
640 if (dashArray == null) {
641 for(int i=0; i<numedges; i++)
642 buf.drawLine((int)x[edges[i]],
643 (int)y[edges[i]], (int)x[edges[i]+1], (int)y[edges[i]+1], width, color, false);
649 float actualLength = 0;
650 for(int i=0; i<numvertices; i++) {
651 // skip over MOVETOs -- they do not contribute to path length
652 if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
653 if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
658 actualLength += java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
660 ratio = actualLength / segLength;
662 PathTokenizer pt = new PathTokenizer(dashArray);
663 Vector v = new Vector();
664 while (pt.hasMoreTokens()) v.addElement(new Float(pt.parseFloat()));
665 float[] dashes = new float[v.size() % 2 == 0 ? v.size() : 2 * v.size()];
666 for(int i=0; i<dashes.length; i++) dashes[i] = ((Float)v.elementAt(i % v.size())).floatValue();
668 int dashpos = dashOffset;
669 boolean on = dashpos % 2 == 0;
670 for(int i=0; i<numvertices; i++) {
671 // skip over MOVETOs -- they do not contribute to path length
672 if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
673 if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
675 int x2 = (int)x[i + 1];
677 int y2 = (int)y[i + 1];
678 float segmentLength = (float)java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
679 int _x1 = x1, _y1 = y1;
682 pos = Math.min(segmentLength, pos + dashes[dashpos] * ratio);
683 if (pos != segmentLength) dashpos = (dashpos + 1) % dashes.length;
684 int _x2 = (int)((x2 * pos + x1 * (segmentLength - pos)) / segmentLength);
685 int _y2 = (int)((y2 * pos + y1 * (segmentLength - pos)) / segmentLength);
686 if (on) buf.drawLine(_x1, _y1, _x2, _y2, width, color, false);
688 _x1 = _x2; _y1 = _y2;
689 } while(pos < segmentLength);
693 // FEATURE: make this faster and cache it; also deal with negative coordinates
694 public int boundingBoxWidth() {
696 for(int i=0; i<numvertices; i++) ret = Math.max(ret, x[i]);
700 // FEATURE: make this faster and cache it; also deal with negative coordinates
701 public int boundingBoxHeight() {
703 for(int i=0; i<numvertices; i++) ret = Math.max(ret, y[i]);
709 // Paint //////////////////////////////////////////////////////////////////////////////
711 public static interface Paint {
713 fillTrapezoid(int tx1, int tx2, int ty1, int tx3, int tx4, int ty2, PixelBuffer buf);
716 public static class SingleColorPaint implements Paint {
718 public SingleColorPaint(int color) { this.color = color; }
719 public void fillTrapezoid(int x1, int x2, int y1, int x3, int x4, int y2, PixelBuffer buf) {
720 buf.fillTrapezoid(x1, x2, y1, x3, x4, y2, color);
735 public static abstract class GradientPaint extends Paint {
736 public GradientPaint(boolean reflect, boolean repeat, Affine gradientTransform,
737 int[] stop_colors, float[] stop_offsets) {
738 this.reflect = reflect; this.repeat = repeat;
739 this.gradientTransform = gradientTransform;
740 this.stop_colors = stop_colors;
741 this.stop_offsets = stop_offsets;
743 Affine gradientTransform = Affine.identity();
744 boolean useBoundingBox = false; // FIXME not supported
745 boolean patternUseBoundingBox = false; // FIXME not supported
747 // it's invalid for both of these to be true
748 boolean reflect = false; // FIXME not supported
749 boolean repeat = false; // FIXME not supported
751 float[] stop_offsets;
753 public void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf) {
755 Affine inverse = a.copy().invert();
756 float slope1 = (tx3 - tx1) / (ty2 - ty1);
757 float slope2 = (tx4 - tx2) / (ty2 - ty1);
758 for(float y=ty1; y<ty2; y++) {
759 float _x1 = (y - ty1) * slope1 + tx1;
760 float _x2 = (y - ty1) * slope2 + tx2;
761 if (_x1 > _x2) { float _x0 = _x1; _x1 = _x2; _x2 = _x0; }
763 for(float x=_x1; x<_x2; x++) {
765 float distance = isLinear ?
766 // length of projection of <x,y> onto the gradient vector == {<x,y> \dot {grad \over |grad|}}
767 (x * (x2 - x1) + y * (y2 - y1)) / (float)Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) :
769 // radial form is simple! FIXME, not quite right
770 (float)Math.sqrt((x - cx) * (x - cx) + (y - cy) * (y - cy));
772 // FIXME: offsets are 0..1, not 0..length(gradient)
773 int i = 0; for(; i<stop_offsets.length; i++) if (distance < stop_offsets[i]) break;
775 // FIXME: handle points beyond the bounds
776 if (i < 0 || i >= stop_offsets.length) continue;
778 // gradate from offsets[i - 1] to offsets[i]
779 float percentage = ((distance - stop_offsets[i - 1]) / (stop_offsets[i] - stop_offsets[i - 1]));
781 int a = (int)((((stop_colors[i] >> 24) & 0xff) - ((stop_colors[i - 1] >> 24) & 0xff)) * percentage) +
782 ((stop_colors[i - 1] >> 24) & 0xff);
783 int r = (int)((((stop_colors[i] >> 16) & 0xff) - ((stop_colors[i - 1] >> 16) & 0xff)) * percentage) +
784 ((stop_colors[i - 1] >> 16) & 0xff);
785 int g = (int)((((stop_colors[i] >> 8) & 0xff) - ((stop_colors[i - 1] >> 8) & 0xff)) * percentage) +
786 ((stop_colors[i - 1] >> 8) & 0xff);
787 int b = (int)((((stop_colors[i] >> 0) & 0xff) - ((stop_colors[i - 1] >> 0) & 0xff)) * percentage) +
788 ((stop_colors[i - 1] >> 0) & 0xff);
789 int argb = (a << 24) | (r << 16) | (g << 8) | b;
790 buf.drawPoint((int)x, (int)Math.floor(y), argb);
796 public static class LinearGradientPaint extends GradientPaint {
797 public LinearGradientPaint(float x1, float y1, float x2, float y2, boolean reflect, boolean repeat,
798 Affine gradientTransform, int[] stop_colors, float[] stop_offsets) {
799 super(reflect, repeat, gradientTransform, stop_colors, stop_offsets);
800 this.x1 = x1; this.x2 = x2; this.y1 = y1; this.y2 = y2;
802 float x1 = 0, y1 = 0, x2 = 300, y2 = 300;
805 public static class RadialGradientPaint extends GradientPaint {
806 public RadialGradientPaint(float cx, float cy, float fx, float fy, float r, boolean reflect, boolean repeat,
807 Affine gradientTransform, int[] stop_colors, float[] stop_offsets) {
808 super(reflect, repeat, gradientTransform, stop_colors, stop_offsets);
809 this.cx = cx; this.cy = cy; this.fx = fx; this.fy = fy; this.r = r;
812 float cx, cy, r, fx, fy;