src/org/xwt/VectorGraphics.java

   1 // FIXME
   2 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
   3 package org.xwt;
   4 import org.xwt.util.*;
   5 import java.util.*;
   6
   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?
   9
  10 /*
  11     v1.0
  12     - textpath
  13     - gradients
  14     - patterns
  15     - clipping/masking
  16     - filters (filtering of a group must be performed AFTER the group is assembled; sep. canvas)
  17
  18     v1.1
  19     - bump caps [requires Paint that can fill circles...] [remember to distinguish between closed/unclosed]
  20     - line joins
  21         - mitre    (hard)
  22         - bevel    (easy)
  23         - bump     (easy, but requires 'round' Paint)
  24     - subtree sharing? otherwise the memory consumption might be outrageous... clone="" attribute?
  25     - better clipping
  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
  30 */
  31
  32 /** XWT's fully conformant Static SVG Viewer; see SVG spec, section G.7 */
  33 public final class VectorGraphics {
  34
  35     // Private Constants ///////////////////////////////////////////////////////////////////
  36
  37     private static final int DEFAULT_PATHLEN = 1000;
  38     private static final float PI = (float)Math.PI;
  39
  40
  41     // Public entry points /////////////////////////////////////////////////////////////////
  42
  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';
  48         boolean first = true;
  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'");
  52             first = false;
  53             boolean relative = Character.toLowerCase(command) == command;
  54             command = Character.toLowerCase(command);
  55             ret.parseSingleCommandAndArguments(t, command, relative);
  56             last_command = command;
  57         }
  58         return ret;
  59     }
  60
  61
  62     // Affine //////////////////////////////////////////////////////////////////////////////
  63
  64     /** an affine transform; all operations are destructive */
  65     public static final class Affine {
  66
  67         //  [ a b e ]
  68         //  [ c d f ]
  69         //  [ 0 0 1 ]
  70         public float a, b, c, d, e, f;
  71
  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; }
  84
  85         public boolean equals(Object o) {
  86             if (!(o instanceof Affine)) return false;
  87             Affine x = (Affine)o;
  88             return a == x.a && b == x.b && c == x.c && d == x.d && e == x.e && f == x.f;
  89         }
  90
  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);
  95         }
  96
  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;
 106             return this;
 107         }
 108
 109         public void invert() {
 110             float det = 1 / (a * d - b * c);
 111             float _a = d * det;
 112             float _b = -1 * b * det;
 113             float _c = -1 * c * det;
 114             float _d = a * 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;
 118         }
 119     }
 120
 121
 122     // PathTokenizer //////////////////////////////////////////////////////////////////////////////
 123
 124     public static Affine parseTransform(String t) {
 125         if (t == null) return null;
 126         t = t.trim();
 127         Affine ret = VectorGraphics.Affine.identity();
 128         while (t.length() > 0) {
 129             if (t.startsWith("skewX(")) {
 130                 // FIXME
 131
 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(')')))));
 135
 136             } else if (t.startsWith("skewY(")) {
 137                 // FIXME
 138
 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));
 150                 } else {
 151                     ret.multiply(VectorGraphics.Affine.rotate(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(')')))));
 152                 }
 153
 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(')')))));
 159                 } else {
 160                     ret.multiply(VectorGraphics.Affine.translate(Float.parseFloat(t.substring(t.indexOf('(') + 1, t.indexOf(','))), 0));
 161                 }
 162
 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")));
 166
 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(')')))));
 172                 } else {
 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(',')))));
 175                 }
 176
 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]));
 184             }
 185             t = t.substring(t.indexOf(')') + 1).trim();
 186         }
 187         return ret;
 188     }
 189
 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;
 193
 194     public static class PathTokenizer {
 195         // FIXME: check array bounds exception for improperly terminated string
 196         String s;
 197         int i = 0;
 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++;
 204         }
 205         public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
 206         public char parseCommand() {
 207             consumeWhitespace();
 208             char c = s.charAt(i);
 209             if (!Character.isLetter(c)) return lastCommand;
 210             i++;
 211             return lastCommand = c;
 212         }
 213         public float parseFloat() {
 214             consumeWhitespace();
 215             int start = i;
 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");
 232                 }
 233             }
 234             if (start == i) throw new RuntimeException("FIXME");
 235             return Float.parseFloat(s.substring(start, i)) * multiplier;
 236         }
 237     }
 238
 239
 240     // Abstract Path //////////////////////////////////////////////////////////////////////////////
 241
 242     /** an abstract path; may contain splines and arcs */
 243     public static class VectorPath {
 244
 245         // the number of vertices on this path
 246         int numvertices = 0;
 247
 248         // the vertices of the path
 249         float[] x = new float[DEFAULT_PATHLEN];
 250         float[] y = new float[DEFAULT_PATHLEN];
 251
 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];
 254
 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)
 260
 261         boolean closed = false;
 262
 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;
 268
 269         /** Creates a concrete vector path transformed through the given matrix. */
 270         public RasterPath realize(Affine a) {
 271
 272             RasterPath ret = new RasterPath();
 273             int NUMSTEPS = 5;  // FIXME
 274             ret.numvertices = 1;
 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]));
 277
 278             for(int i=1; i<numvertices; i++) {
 279                 if (type[i] == TYPE_LINETO) {
 280                     float rx = x[i];
 281                     float ry = y[i];
 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++;
 285
 286                 } else if (type[i] == TYPE_MOVETO) {
 287                     float rx = x[i];
 288                     float ry = y[i];
 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));
 291                     ret.numvertices++;
 292
 293                 } else if (type[i] == TYPE_ARCTO) {
 294                     float rx = c1x[i];
 295                     float ry = c1y[i];
 296                     float phi = c2x[i];
 297                     float fa = ((int)c2y[i]) >> 1;
 298                     float fs = ((int)c2y[i]) & 1;
 299                     float x1 = x[i];
 300                     float y1 = y[i];
 301                     float x2 = x[i+1];
 302                     float y2 = y[i+1];
 303
 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;
 313
 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);
 327
 328                     if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
 329                     if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
 330
 331                     if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
 332                     else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
 333
 334                     // FIXME: integrate F.6.6
 335                     // FIXME: isn't quite ending where it should...
 336
 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;
 348                     }
 349
 350                 } else if (type[i] == TYPE_CUBIC) {
 351
 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];
 355                     float dx = 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];
 359                     float dy = y[i];
 360
 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++;
 367                     }
 368
 369
 370                 } else if (type[i] == TYPE_QUADRADIC) {
 371
 372                     float bx = x[i+1] - 2 * c1x[i] + x[i];
 373                     float cx = 2 * c1x[i] - 2 * x[i];
 374                     float dx = x[i];
 375                     float by = y[i+1] - 2 * c1y[i] + y[i];
 376                     float cy = 2 * c1y[i] - 2 * y[i];
 377                     float dy = y[i];
 378
 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++;
 385                     }
 386
 387                 }
 388
 389             }
 390
 391             if (ret.numedges > 0) ret.sort(0, ret.numedges - 1, false);
 392             return ret;
 393         }
 394
 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;
 400             }
 401             switch(command) {
 402             case 'z': {
 403                 int where;
 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];
 409                 numvertices++;
 410                 closed = true;
 411                 break;
 412             }
 413
 414             case 'm': {
 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);
 418                 numvertices++;
 419                 break;
 420             }
 421
 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];
 429                 } else {
 430                     second = t.parseFloat();
 431                 }
 432                 x[numvertices] = first + (relative ? x[numvertices - 1] : 0);
 433                 y[numvertices] = second + (relative ? y[numvertices - 1] : 0);
 434                 numvertices++;
 435                 break;
 436             }
 437
 438             case 'a': {
 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);
 446                 numvertices++;
 447                 break;
 448             }
 449
 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];
 458                 } else {
 459                     c1x[numvertices-1] = x[numvertices-1];
 460                     c1y[numvertices-1] = y[numvertices-1];
 461                 }
 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);
 466                 numvertices++;
 467                 break;
 468             }
 469
 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];
 478                 } else {
 479                     c1x[numvertices-1] = x[numvertices-1];
 480                     c1y[numvertices-1] = y[numvertices-1];
 481                 }
 482                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 483                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 484                 numvertices++;
 485                 break;
 486             }
 487
 488             default:
 489                 // FIXME
 490             }
 491
 492             /*
 493             // invariant: after this loop, no two lines intersect other than at a vertex
 494             // FIXME: cleanup
 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++) {
 498
 499                     // I'm not sure how to deal with vertical lines...
 500                     if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
 501
 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
 505
 506                     float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
 507                     float _y = islope * (_x - x[i]) + y[i];
 508
 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]; }
 513                         x[i+1] = _x;
 514                         y[i+1] = _y;
 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++;
 518                         index++;
 519                         break;  // actually 'continue' the outermost loop
 520                     }
 521                 }
 522             }
 523             */
 524
 525         }
 526     }
 527
 528
 529
 530
 531     // Rasterized Vector Path //////////////////////////////////////////////////////////////////////////////
 532
 533     /** a vector path */
 534     public static class RasterPath {
 535
 536         // the vertices of this path
 537         int[] x = new int[DEFAULT_PATHLEN];
 538         int[] y = new int[DEFAULT_PATHLEN];
 539         int numvertices = 0;
 540
 541         /**
 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
 545          */
 546         int[] edges = new int[DEFAULT_PATHLEN];
 547         int numedges = 0;
 548
 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; } }
 551
 552         /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */
 553         int sort(int left, int right, boolean partition) {
 554             if (partition) {
 555                 int i, j, middle;
 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]]);
 561                     if (i >= j) break;
 562                     s = edges[i]; edges[i] = edges[j]; edges[j] = s;
 563                 }
 564                 s = edges[right]; edges[right] = edges[i]; edges[i] = s;
 565                 return i;
 566             } else {
 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);
 571                 return 0;
 572             }
 573         }
 574
 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]);
 583         }
 584
 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;
 590
 591             // we iterate over all endpoints in increasing y-coordinate order
 592             for(int index = 1; index<numedges; index++) {
 593                 int count = 0;
 594
 595                 // we now examine the horizontal band between y=y0 and y=y1
 596                 y0 = y1;
 597                 y1 = y[edges[index]];
 598                 if (y0 == y1) continue;
 599
 600                 // within this band, we iterate over all edges
 601                 int x0 = Integer.MIN_VALUE;
 602                 int leftSegment = -1;
 603                 while(true) {
 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;
 618                         rightSegment = i;
 619                         x1 = midpoint;
 620                     }
 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,
 628                                                 buf);
 629                     if (useEvenOdd) count++;
 630                     else count += (y[edges[rightSegment]] < y[edges[rightSegment]+1]) ? -1 : 1;
 631                     leftSegment = rightSegment; x0 = x1;
 632                 }
 633             }
 634         }
 635
 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) {
 639
 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);
 644                 return;
 645             }
 646
 647             float ratio = 1;
 648             if (segLength > 0) {
 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;
 654                     int x1 = x[i];
 655                     int x2 = x[i + 1];
 656                     int y1 = y[i];
 657                     int y2 = y[i + 1];
 658                     actualLength += java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
 659                 }
 660                 ratio = actualLength / segLength;
 661             }
 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();
 667             float length = 0;
 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;
 674                 int x1 = (int)x[i];
 675                 int x2 = (int)x[i + 1];
 676                 int y1 = (int)y[i];
 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;
 680                 float pos = 0;
 681                 do {
 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);
 687                     on = !on;
 688                     _x1 = _x2; _y1 = _y2;
 689                 } while(pos < segmentLength);
 690             }
 691         }
 692
 693         // FEATURE: make this faster and cache it; also deal with negative coordinates
 694         public int boundingBoxWidth() {
 695             int ret = 0;
 696             for(int i=0; i<numvertices; i++) ret = Math.max(ret, x[i]);
 697             return ret;
 698         }
 699
 700         // FEATURE: make this faster and cache it; also deal with negative coordinates
 701         public int boundingBoxHeight() {
 702             int ret = 0;
 703             for(int i=0; i<numvertices; i++) ret = Math.max(ret, y[i]);
 704             return ret;
 705         }
 706     }
 707
 708
 709     // Paint //////////////////////////////////////////////////////////////////////////////
 710
 711     public static interface Paint {
 712         public abstract void
 713             fillTrapezoid(int tx1, int tx2, int ty1, int tx3, int tx4, int ty2, PixelBuffer buf);
 714     }
 715
 716     public static class SingleColorPaint implements Paint {
 717         int color;
 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);
 721         }
 722     }
 723
 724 }
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734     /*
 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;
 742         }
 743         Affine gradientTransform = Affine.identity();
 744         boolean useBoundingBox = false;            // FIXME not supported
 745         boolean patternUseBoundingBox = false;     // FIXME not supported
 746
 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
 750         int[] stop_colors;
 751         float[] stop_offsets;
 752
 753         public void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf) {
 754             Affine a = buf.a;
 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; }
 762
 763                 for(float x=_x1; x<_x2; x++) {
 764
 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)) :
 768
 769                         // radial form is simple! FIXME, not quite right
 770                         (float)Math.sqrt((x - cx) * (x - cx) + (y - cy) * (y - cy));
 771
 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;
 774
 775                     // FIXME: handle points beyond the bounds
 776                     if (i < 0 || i >= stop_offsets.length) continue;
 777
 778                     // gradate from offsets[i - 1] to offsets[i]
 779                     float percentage = ((distance - stop_offsets[i - 1]) / (stop_offsets[i] - stop_offsets[i - 1]));
 780
 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);
 791                 }
 792             }
 793         }
 794     }
 795
 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;
 801         }
 802         float x1 = 0, y1 = 0, x2 = 300, y2 = 300;
 803     }
 804
 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;
 810         }
 811
 812         float cx, cy, r, fx, fy;
 813
 814     }
 815     */
 816