src/org/xwt/VectorGraphics.java

   1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt;
   3 import org.xwt.util.*;
   4 import java.util.*;
   5
   6 // FIXME: offer a "subpixel" mode where we pass floats to the Platform and don't do any snapping
   7 // FIXME: fracture when realizing instead of when parsing?
   8
   9 /*
  10     v1.0
  11     - textpath
  12     - gradients
  13     - patterns
  14     - clipping/masking
  15     - filters (filtering of a group must be performed AFTER the group is assembled; sep. canvas)
  16
  17     v1.1
  18     - bump caps [requires Paint that can fill circles...] [remember to distinguish between closed/unclosed]
  19     - line joins
  20         - mitre    (hard)
  21         - bevel    (easy)
  22         - bump     (easy, but requires 'round' Paint)
  23     - subtree sharing? otherwise the memory consumption might be outrageous... clone="" attribute?
  24     - better clipping
  25         - intersect clip regions (linearity)
  26         - clip on trapezoids, not pixels
  27     - faster gradients and patterns:
  28         - transform each corner of the trapezoid and then interpolate
  29 */
  30
  31 /** XWT's fully conformant Static SVG Viewer; see SVG spec, section G.7 */
  32 public final class VectorGraphics {
  33
  34     // Private Constants ///////////////////////////////////////////////////////////////////
  35
  36     private static final int DEFAULT_PATHLEN = 1000;
  37     private static final float PI = (float)Math.PI;
  38
  39
  40     // Public entry points /////////////////////////////////////////////////////////////////
  41
  42     public static VectorPath parseVectorPath(String s) {
  43         PathTokenizer t = new PathTokenizer(s);
  44         VectorPath ret = new VectorPath();
  45         char last_command = 'M';
  46         boolean first = true;
  47         while(t.hasMoreTokens()) {
  48             char command = t.parseCommand();
  49             if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
  50             first = false;
  51             boolean relative = Character.toLowerCase(command) == command;
  52             command = Character.toLowerCase(command);
  53             ret.parseSingleCommandAndArguments(t, command, relative);
  54             last_command = command;
  55         }
  56         return ret;
  57     }
  58
  59
  60     // Affine //////////////////////////////////////////////////////////////////////////////
  61
  62     /** an affine transform; all operations are destructive */
  63     public static final class Affine {
  64
  65         //  [ a b e ]
  66         //  [ c d f ]
  67         //  [ 0 0 1 ]
  68         public float a, b, c, d, e, f;
  69
  70         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; }
  71         public String toString() { return "[ " + a + ", " + b + ", " + c + ", " + d + ", " + e + ", " + f + " ]"; }
  72         public Affine copy() { return new Affine(a, b, c, d, e, f); }
  73         public static Affine identity() { return new Affine(1, 0, 0, 1, 0, 0); }
  74         public static Affine scale(float sx, float sy) { return new Affine(sx, 0, 0, sy, 0, 0); }
  75         public static Affine shear(float degrees) {
  76             return new Affine(1, 0, (float)Math.tan(degrees * (float)(Math.PI / 180.0)), 1, 0, 0); }
  77         public static Affine translate(float tx, float ty) { return new Affine(1, 0, 0, 1, tx, ty); }
  78         public static Affine flip(boolean horiz, boolean vert) { return new Affine(horiz ? -1 : 1, 0, 0, vert ? -1 : 1, 0, 0); }
  79         public float multiply_px(float x, float y) { return x * a + y * c + e; }
  80         public float multiply_py(float x, float y) { return x * b + y * d + f; }
  81         public boolean equalsIgnoringTranslation(Affine x) { return a == x.a && b == x.b && c == x.c && d == x.d; }
  82
  83         public boolean equals(Object o) {
  84             if (!(o instanceof Affine)) return false;
  85             Affine x = (Affine)o;
  86             return a == x.a && b == x.b && c == x.c && d == x.d && e == x.e && f == x.f;
  87         }
  88
  89         public static Affine rotate(float degrees) {
  90             float s = (float)Math.sin(degrees * (float)(Math.PI / 180.0));
  91             float c = (float)Math.cos(degrees * (float)(Math.PI / 180.0));
  92             return new Affine(c, s, -s, c, 0, 0);
  93         }
  94
  95         /** this = this * a */
  96         public Affine multiply(Affine A) {
  97             float _a = this.a * A.a + this.b * A.c;
  98             float _b = this.a * A.b + this.b * A.d;
  99             float _c = this.c * A.a + this.d * A.c;
 100             float _d = this.c * A.b + this.d * A.d;
 101             float _e = this.e * A.a + this.f * A.c + A.e;
 102             float _f = this.e * A.b + this.f * A.d + A.f;
 103             a = _a; b = _b; c = _c; d = _d; e = _e; f = _f;
 104             return this;
 105         }
 106
 107         public void invert() {
 108             float det = 1 / (a * d - b * c);
 109             float _a = d * det;
 110             float _b = -1 * b * det;
 111             float _c = -1 * c * det;
 112             float _d = a * det;
 113             float _e = -1 * e * a - f * c;
 114             float _f = -1 * e * b - f * d;
 115             a = _a; b = _b; c = _c; d = _d; e = _e; f = _f;
 116         }
 117     }
 118
 119
 120     // PathTokenizer //////////////////////////////////////////////////////////////////////////////
 121
 122     public static final float PX_PER_INCH = 72;
 123     public static final float INCHES_PER_CM = (float)0.3937;
 124     public static final float INCHES_PER_MM = INCHES_PER_CM / 10;
 125
 126     public static class PathTokenizer {
 127         // FIXME: check array bounds exception for improperly terminated string
 128         String s;
 129         int i = 0;
 130         char lastCommand = 'M';
 131         public PathTokenizer(String s) { this.s = s; }
 132         private void consumeWhitespace() {
 133             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
 134             if (i < s.length() && s.charAt(i) == ',') i++;
 135             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
 136         }
 137         public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
 138         public char parseCommand() {
 139             consumeWhitespace();
 140             char c = s.charAt(i);
 141             if (!Character.isLetter(c)) return lastCommand;
 142             i++;
 143             return lastCommand = c;
 144         }
 145         public float parseFloat() {
 146             consumeWhitespace();
 147             int start = i;
 148             float multiplier = 1;
 149             for(; i < s.length(); i++) {
 150                 char c = s.charAt(i);
 151                 if (Character.isWhitespace(c) || c == ',' || (c == '-' && i != start)) break;
 152                 if (!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E' || c == '-')) {
 153                     if (c == '%') {                                // FIXME
 154                     } else if (s.regionMatches(i, "pt", 0, i+2)) { // FIXME
 155                     } else if (s.regionMatches(i, "em", 0, i+2)) { // FIXME
 156                     } else if (s.regionMatches(i, "pc", 0, i+2)) { // FIXME
 157                     } else if (s.regionMatches(i, "ex", 0, i+2)) { // FIXME
 158                     } else if (s.regionMatches(i, "mm", 0, i+2)) { i += 2; multiplier = INCHES_PER_MM * PX_PER_INCH; break;
 159                     } else if (s.regionMatches(i, "cm", 0, i+2)) { i += 2; multiplier = INCHES_PER_CM * PX_PER_INCH; break;
 160                     } else if (s.regionMatches(i, "in", 0, i+2)) { i += 2; multiplier = PX_PER_INCH; break;
 161                     } else if (s.regionMatches(i, "px", 0, i+2)) { i += 2; break;
 162                     } else if (Character.isLetter(c)) break;
 163                     throw new RuntimeException("didn't expect character \"" + c + "\" in a numeric constant");
 164                 }
 165             }
 166             if (start == i) throw new RuntimeException("FIXME");
 167             return Float.parseFloat(s.substring(start, i)) * multiplier;
 168         }
 169     }
 170
 171
 172     // Abstract Path //////////////////////////////////////////////////////////////////////////////
 173
 174     /** an abstract path; may contain splines and arcs */
 175     public static class VectorPath {
 176
 177         // the number of vertices on this path
 178         int numvertices = 0;
 179
 180         // the vertices of the path
 181         float[] x = new float[DEFAULT_PATHLEN];
 182         float[] y = new float[DEFAULT_PATHLEN];
 183
 184         // 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]
 185         byte[] type = new byte[DEFAULT_PATHLEN];
 186
 187         // bezier control points
 188         float[] c1x = new float[DEFAULT_PATHLEN];  // or rx (arcto)
 189         float[] c1y = new float[DEFAULT_PATHLEN];  // or ry (arcto)
 190         float[] c2x = new float[DEFAULT_PATHLEN];  // or x-axis-rotation (arcto)
 191         float[] c2y = new float[DEFAULT_PATHLEN];  // or large-arc << 1 | sweep (arcto)
 192
 193         boolean closed = false;
 194
 195         static final byte TYPE_MOVETO = 0;
 196         static final byte TYPE_LINETO = 1;
 197         static final byte TYPE_ARCTO = 2;
 198         static final byte TYPE_CUBIC = 3;
 199         static final byte TYPE_QUADRADIC = 4;
 200
 201         /** Creates a concrete vector path transformed through the given matrix. */
 202         public RasterPath realize(Affine a) {
 203
 204             RasterPath ret = new RasterPath();
 205             int NUMSTEPS = 5;  // FIXME
 206             ret.numvertices = 1;
 207             ret.x[0] = (int)Math.round(a.multiply_px(x[0], y[0]));
 208             ret.y[0] = (int)Math.round(a.multiply_py(x[0], y[0]));
 209
 210             for(int i=1; i<numvertices; i++) {
 211                 if (type[i] == TYPE_LINETO) {
 212                     float rx = x[i];
 213                     float ry = y[i];
 214                     ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 215                     ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 216                     ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 217
 218                 } else if (type[i] == TYPE_MOVETO) {
 219                     float rx = x[i];
 220                     float ry = y[i];
 221                     ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 222                     ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 223                     ret.numvertices++;
 224
 225                 } else if (type[i] == TYPE_ARCTO) {
 226                     float rx = c1x[i];
 227                     float ry = c1y[i];
 228                     float phi = c2x[i];
 229                     float fa = ((int)c2y[i]) >> 1;
 230                     float fs = ((int)c2y[i]) & 1;
 231                     float x1 = x[i];
 232                     float y1 = y[i];
 233                     float x2 = x[i+1];
 234                     float y2 = y[i+1];
 235
 236                     // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
 237                     float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
 238                     float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
 239                     float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
 240                                                  (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
 241                     float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
 242                     float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
 243                     float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
 244                     float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
 245
 246                     // F.6.4 Conversion from center to endpoint parameterization
 247                     float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
 248                     float det = ux * vy - uy * vx;
 249                     float theta1 = (det < 0 ? -1 : 1) *
 250                         (float)Math.acos((ux * vx + uy * vy) /
 251                                   ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
 252                     ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
 253                     vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
 254                     det = ux * vy - uy * vx;
 255                     float dtheta = (det < 0 ? -1 : 1) *
 256                         (float)Math.acos((ux * vx + uy * vy) /
 257                                   ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
 258                     dtheta = dtheta % (float)(2 * Math.PI);
 259
 260                     if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
 261                     if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
 262
 263                     if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
 264                     else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
 265
 266                     // FIXME: integrate F.6.6
 267                     // FIXME: isn't quite ending where it should...
 268
 269                     // F.6.3: Parameterization alternatives
 270                     float theta = theta1;
 271                     for(int j=0; j<NUMSTEPS; j++) {
 272                         float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
 273                             ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
 274                         float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
 275                             ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
 276                         ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rasterx, rastery));
 277                         ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rasterx, rastery));
 278                         ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 279                         theta += dtheta / NUMSTEPS;
 280                     }
 281
 282                 } else if (type[i] == TYPE_CUBIC) {
 283
 284                     float ax = x[i+1] - 3 * c2x[i] + 3 * c1x[i] - x[i];
 285                     float bx = 3 * c2x[i] - 6 * c1x[i] + 3 * x[i];
 286                     float cx = 3 * c1x[i] - 3 * x[i];
 287                     float dx = x[i];
 288                     float ay = y[i+1] - 3 * c2y[i] + 3 * c1y[i] - y[i];
 289                     float by = 3 * c2y[i] - 6 * c1y[i] + 3 * y[i];
 290                     float cy = 3 * c1y[i] - 3 * y[i];
 291                     float dy = y[i];
 292
 293                     for(float t=0; t<1; t += 1 / (float)NUMSTEPS) {
 294                         float rx = ax * t * t * t + bx * t * t + cx * t + dx;
 295                         float ry = ay * t * t * t + by * t * t + cy * t + dy;
 296                         ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 297                         ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 298                         ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 299                     }
 300
 301
 302                 } else if (type[i] == TYPE_QUADRADIC) {
 303
 304                     float bx = x[i+1] - 2 * c1x[i] + x[i];
 305                     float cx = 2 * c1x[i] - 2 * x[i];
 306                     float dx = x[i];
 307                     float by = y[i+1] - 2 * c1y[i] + y[i];
 308                     float cy = 2 * c1y[i] - 2 * y[i];
 309                     float dy = y[i];
 310
 311                     for(float t=0; t<1; t += 1 / (float)NUMSTEPS) {
 312                         float rx = bx * t * t + cx * t + dx;
 313                         float ry = by * t * t + cy * t + dy;
 314                         ret.x[ret.numvertices] = (int)Math.round(a.multiply_px(rx, ry));
 315                         ret.y[ret.numvertices] = (int)Math.round(a.multiply_py(rx, ry));
 316                         ret.edges[ret.numedges++] = ret.numvertices - 1; ret.numvertices++;
 317                     }
 318
 319                 }
 320
 321             }
 322
 323             if (ret.numedges > 0) ret.sort(0, ret.numedges - 1, false);
 324             return ret;
 325         }
 326
 327         protected void parseSingleCommandAndArguments(PathTokenizer t, char command, boolean relative) {
 328             if (numvertices == 0 && command != 'm') throw new RuntimeException("first command MUST be an 'm'");
 329             if (numvertices > x.length - 2) {
 330                 float[] new_x = new float[x.length * 2]; System.arraycopy(x, 0, new_x, 0, x.length); x = new_x;
 331                 float[] new_y = new float[y.length * 2]; System.arraycopy(y, 0, new_y, 0, y.length); y = new_y;
 332             }
 333             switch(command) {
 334             case 'z': {
 335                 int where;
 336                 type[numvertices-1] = TYPE_LINETO;
 337                 for(where = numvertices - 1; where > 0; where--)
 338                     if (type[where - 1] == TYPE_MOVETO) break;
 339                 x[numvertices] = x[where];
 340                 y[numvertices] = y[where];
 341                 numvertices++;
 342                 closed = true;
 343                 break;
 344             }
 345
 346             case 'm': {
 347                 if (numvertices > 0) type[numvertices-1] = TYPE_MOVETO;
 348                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 349                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 350                 numvertices++;
 351                 break;
 352             }
 353
 354             case 'l': case 'h': case 'v': {
 355                 type[numvertices-1] = TYPE_LINETO;
 356                 float first = t.parseFloat(), second;
 357                 if (command == 'h') {
 358                     second = relative ? 0 : y[numvertices - 1];
 359                 } else if (command == 'v') {
 360                     second = first; first = relative ? 0 : x[numvertices - 1];
 361                 } else {
 362                     second = t.parseFloat();
 363                 }
 364                 x[numvertices] = first + (relative ? x[numvertices - 1] : 0);
 365                 y[numvertices] = second + (relative ? y[numvertices - 1] : 0);
 366                 numvertices++;
 367                 break;
 368             }
 369
 370             case 'a': {
 371                 type[numvertices-1] = TYPE_ARCTO;
 372                 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 373                 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 374                 c2x[numvertices-1] = (t.parseFloat() / 360) * 2 * PI;
 375                 c2y[numvertices-1] = (((int)t.parseFloat()) << 1) | (int)t.parseFloat();
 376                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 377                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 378                 numvertices++;
 379                 break;
 380             }
 381
 382             case 's': case 'c': {
 383                 type[numvertices-1] = TYPE_CUBIC;
 384                 if (command == 'c') {
 385                     c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 386                     c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 387                 } else if (numvertices > 1 && type[numvertices-2] == TYPE_CUBIC) {
 388                     c1x[numvertices-1] = 2 * x[numvertices - 1] - c2x[numvertices-2];
 389                     c1y[numvertices-1] = 2 * y[numvertices - 1] - c2y[numvertices-2];
 390                 } else {
 391                     c1x[numvertices-1] = x[numvertices-1];
 392                     c1y[numvertices-1] = y[numvertices-1];
 393                 }
 394                 c2x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 395                 c2y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 396                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 397                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 398                 numvertices++;
 399                 break;
 400             }
 401
 402             case 't': case 'q': {
 403                 type[numvertices-1] = TYPE_QUADRADIC;
 404                 if (command == 'q') {
 405                     c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 406                     c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 407                 } else if (numvertices > 1 && type[numvertices-2] == TYPE_QUADRADIC) {
 408                     c1x[numvertices-1] = 2 * x[numvertices - 1] - c1x[numvertices-2];
 409                     c1y[numvertices-1] = 2 * y[numvertices - 1] - c1y[numvertices-2];
 410                 } else {
 411                     c1x[numvertices-1] = x[numvertices-1];
 412                     c1y[numvertices-1] = y[numvertices-1];
 413                 }
 414                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 415                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 416                 numvertices++;
 417                 break;
 418             }
 419
 420             default:
 421                 // FIXME
 422             }
 423
 424             /*
 425             // invariant: after this loop, no two lines intersect other than at a vertex
 426             // FIXME: cleanup
 427             int index = numvertices - 2;
 428             for(int i=0; i<Math.min(numvertices - 3, index); i++) {
 429                 for(int j = index; j < numvertices - 1; j++) {
 430
 431                     // I'm not sure how to deal with vertical lines...
 432                     if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
 433
 434                     float islope = (y[i+1] - y[i]) / (x[i+1] - x[i]);
 435                     float jslope = (y[j+1] - y[j]) / (x[j+1] - x[j]);
 436                     if (islope == jslope) continue;   // parallel lines can't intersect
 437
 438                     float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
 439                     float _y = islope * (_x - x[i]) + y[i];
 440
 441                     if (_x > Math.min(x[i+1], x[i]) && _x < Math.max(x[i+1], x[i]) &&
 442                         _x > Math.min(x[j+1], x[j]) && _x < Math.max(x[j+1], x[j])) {
 443                         // FIXME: something's not right in here.  See if we can do without fracturing line 'i'.
 444                         for(int k = ++numvertices; k>i; k--) { x[k] = x[k - 1]; y[k] = y[k - 1]; }
 445                         x[i+1] = _x;
 446                         y[i+1] = _y;
 447                         x[numvertices] = x[numvertices - 1];  x[numvertices - 1] = _x;
 448                         y[numvertices] = y[numvertices - 1];  y[numvertices - 1] = _y;
 449                         edges[numedges++] = numvertices - 1; numvertices++;
 450                         index++;
 451                         break;  // actually 'continue' the outermost loop
 452                     }
 453                 }
 454             }
 455             */
 456
 457         }
 458     }
 459
 460
 461
 462
 463     // Rasterized Vector Path //////////////////////////////////////////////////////////////////////////////
 464
 465     /** a vector path */
 466     public static class RasterPath {
 467
 468         // the vertices of this path
 469         int[] x = new int[DEFAULT_PATHLEN];
 470         int[] y = new int[DEFAULT_PATHLEN];
 471         int numvertices = 0;
 472
 473         /**
 474          *  A list of the vertices on this path which *start* an *edge* (rather than a moveto), sorted by increasing y.
 475          *  example: x[edges[1]],y[edges[1]] - x[edges[i]+1],y[edges[i]+1] is the second-topmost edge
 476          *  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
 477          */
 478         int[] edges = new int[DEFAULT_PATHLEN];
 479         int numedges = 0;
 480
 481         /** translate a rasterized path */
 482         public void translate(int dx, int dy) { for(int i=0; i<numvertices; i++) { x[i] += dx; y[i] += dy; } }
 483
 484         /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */
 485         int sort(int left, int right, boolean partition) {
 486             if (partition) {
 487                 int i, j, middle;
 488                 middle = (left + right) / 2;
 489                 int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;
 490                 for (i = left - 1, j = right; ; ) {
 491                     while (y[edges[++i]] < y[edges[right]]);
 492                     while (j > left && y[edges[--j]] > y[edges[right]]);
 493                     if (i >= j) break;
 494                     s = edges[i]; edges[i] = edges[j]; edges[j] = s;
 495                 }
 496                 s = edges[right]; edges[right] = edges[i]; edges[i] = s;
 497                 return i;
 498             } else {
 499                 if (left >= right) return 0;
 500                 int p = sort(left, right, true);
 501                 sort(left, p - 1, false);
 502                 sort(p + 1, right, false);
 503                 return 0;
 504             }
 505         }
 506
 507         /** finds the x value at which the line intercepts the line y=_y */
 508         private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {
 509             if (includeTop ? (_y < Math.min(y[i], y[i+1])) : (_y <= Math.min(y[i], y[i+1])))
 510                 return Integer.MIN_VALUE;
 511             if (includeBottom ? (_y > Math.max(y[i], y[i+1])) : (_y >= Math.max(y[i], y[i+1])))
 512                 return Integer.MIN_VALUE;
 513             return (int)Math.round((((float)(x[i + 1] - x[i])) /
 514                                     ((float)(y[i + 1] - y[i])) ) * ((float)(_y - y[i])) + x[i]);
 515         }
 516
 517         /** fill the interior of the path */
 518         public void fill(PixelBuffer buf, Paint paint) {
 519             if (numedges == 0) return;
 520             int y0 = y[edges[0]], y1 = y0;
 521             boolean useEvenOdd = false;
 522
 523             // we iterate over all endpoints in increasing y-coordinate order
 524             for(int index = 1; index<numedges; index++) {
 525                 int count = 0;
 526
 527                 // we now examine the horizontal band between y=y0 and y=y1
 528                 y0 = y1;
 529                 y1 = y[edges[index]];
 530                 if (y0 == y1) continue;
 531
 532                 // within this band, we iterate over all edges
 533                 int x0 = Integer.MIN_VALUE;
 534                 int leftSegment = -1;
 535                 while(true) {
 536                     int x1 = Integer.MAX_VALUE;
 537                     int rightSegment = Integer.MAX_VALUE;
 538                     for(int i=0; i<numedges; i++) {
 539                         if (y[edges[i]] == y[edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.
 540                         // we order the segments by the x-coordinate of their midpoint;
 541                         // since segments cannot intersect, this is a well-ordering
 542                         int i0 = intercept(edges[i], y0, true, false);
 543                         int i1 = intercept(edges[i], y1, false, true);
 544                         if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;
 545                         int midpoint = i0 + i1;
 546                         if (midpoint < x0) continue;
 547                         if (midpoint == x0 && i <= leftSegment) continue;
 548                         if (midpoint > x1) continue;
 549                         if (midpoint == x1 && i >= rightSegment) continue;
 550                         rightSegment = i;
 551                         x1 = midpoint;
 552                     }
 553                     if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;
 554                     if (leftSegment != -1)
 555                         if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0))
 556                             paint.fillTrapezoid(intercept(edges[leftSegment], y0, true, true),
 557                                                 intercept(edges[rightSegment], y0, true, true), y0,
 558                                                 intercept(edges[leftSegment], y1, true, true),
 559                                                 intercept(edges[rightSegment], y1, true, true), y1,
 560                                                 buf);
 561                     if (useEvenOdd) count++;
 562                     else count += (y[edges[rightSegment]] < y[edges[rightSegment]+1]) ? -1 : 1;
 563                     leftSegment = rightSegment; x0 = x1;
 564                 }
 565             }
 566         }
 567
 568         /** stroke the outline of the path */
 569         public void stroke(PixelBuffer buf, int width, int color) { stroke(buf, width, color, null, 0, 0); }
 570         public void stroke(PixelBuffer buf, int width, int color, String dashArray, int dashOffset, float segLength) {
 571
 572             if (dashArray == null) {
 573                 for(int i=0; i<numedges; i++)
 574                     buf.drawLine((int)x[edges[i]],
 575                                  (int)y[edges[i]], (int)x[edges[i]+1], (int)y[edges[i]+1], width, color, false);
 576                 return;
 577             }
 578
 579             float ratio = 1;
 580             if (segLength > 0) {
 581                 float actualLength = 0;
 582                 for(int i=0; i<numvertices; i++) {
 583                     // skip over MOVETOs -- they do not contribute to path length
 584                     if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
 585                     if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
 586                     int x1 = x[i];
 587                     int x2 = x[i + 1];
 588                     int y1 = y[i];
 589                     int y2 = y[i + 1];
 590                     actualLength += java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
 591                 }
 592                 ratio = actualLength / segLength;
 593             }
 594             PathTokenizer pt = new PathTokenizer(dashArray);
 595             Vector v = new Vector();
 596             while (pt.hasMoreTokens()) v.addElement(new Float(pt.parseFloat()));
 597             float[] dashes = new float[v.size() % 2 == 0 ? v.size() : 2 * v.size()];
 598             for(int i=0; i<dashes.length; i++) dashes[i] = ((Float)v.elementAt(i % v.size())).floatValue();
 599             float length = 0;
 600             int dashpos = dashOffset;
 601             boolean on = dashpos % 2 == 0;
 602             for(int i=0; i<numvertices; i++) {
 603                 // skip over MOVETOs -- they do not contribute to path length
 604                 if (x[i] == x[i+1] && y[i] == y[i+1]) continue;
 605                 if (x[i+1] == x[i+2] && y[i+1] == y[i+2]) continue;
 606                 int x1 = (int)x[i];
 607                 int x2 = (int)x[i + 1];
 608                 int y1 = (int)y[i];
 609                 int y2 = (int)y[i + 1];
 610                 float segmentLength = (float)java.lang.Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
 611                 int _x1 = x1, _y1 = y1;
 612                 float pos = 0;
 613                 do {
 614                     pos = Math.min(segmentLength, pos + dashes[dashpos] * ratio);
 615                     if (pos != segmentLength) dashpos = (dashpos + 1) % dashes.length;
 616                     int _x2 = (int)((x2 * pos + x1 * (segmentLength - pos)) / segmentLength);
 617                     int _y2 = (int)((y2 * pos + y1 * (segmentLength - pos)) / segmentLength);
 618                     if (on) buf.drawLine(_x1, _y1, _x2, _y2, width, color, false);
 619                     on = !on;
 620                     _x1 = _x2; _y1 = _y2;
 621                 } while(pos < segmentLength);
 622             }
 623         }
 624
 625         // FEATURE: make this faster and cache it; also deal with negative coordinates
 626         public int boundingBoxWidth() {
 627             int ret = 0;
 628             for(int i=0; i<numvertices; i++) ret = Math.max(ret, x[i]);
 629             return ret;
 630         }
 631
 632         // FEATURE: make this faster and cache it; also deal with negative coordinates
 633         public int boundingBoxHeight() {
 634             int ret = 0;
 635             for(int i=0; i<numvertices; i++) ret = Math.max(ret, y[i]);
 636             return ret;
 637         }
 638     }
 639
 640
 641     // Paint //////////////////////////////////////////////////////////////////////////////
 642
 643     public static interface Paint {
 644         public abstract void
 645             fillTrapezoid(int tx1, int tx2, int ty1, int tx3, int tx4, int ty2, PixelBuffer buf);
 646     }
 647
 648     public static class SingleColorPaint implements Paint {
 649         int color;
 650         public SingleColorPaint(int color) { this.color = color; }
 651         public void fillTrapezoid(int x1, int x2, int y1, int x3, int x4, int y2, PixelBuffer buf) {
 652             buf.fillTrapezoid(x1, x2, y1, x3, x4, y2, color);
 653         }
 654     }
 655
 656 }
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666     /*
 667     public static abstract class GradientPaint extends Paint {
 668         public GradientPaint(boolean reflect, boolean repeat, Affine gradientTransform,
 669                              int[] stop_colors, float[] stop_offsets) {
 670             this.reflect = reflect; this.repeat = repeat;
 671             this.gradientTransform = gradientTransform;
 672             this.stop_colors = stop_colors;
 673             this.stop_offsets = stop_offsets;
 674         }
 675         Affine gradientTransform = Affine.identity();
 676         boolean useBoundingBox = false;            // FIXME not supported
 677         boolean patternUseBoundingBox = false;     // FIXME not supported
 678
 679         // it's invalid for both of these to be true
 680         boolean reflect = false;                   // FIXME not supported
 681         boolean repeat = false;                    // FIXME not supported
 682         int[] stop_colors;
 683         float[] stop_offsets;
 684
 685         public void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf) {
 686             Affine a = buf.a;
 687             Affine inverse = a.copy().invert();
 688             float slope1 = (tx3 - tx1) / (ty2 - ty1);
 689             float slope2 = (tx4 - tx2) / (ty2 - ty1);
 690             for(float y=ty1; y<ty2; y++) {
 691                 float _x1 = (y - ty1) * slope1 + tx1;
 692                 float _x2 = (y - ty1) * slope2 + tx2;
 693                 if (_x1 > _x2) { float _x0 = _x1; _x1 = _x2; _x2 = _x0; }
 694
 695                 for(float x=_x1; x<_x2; x++) {
 696
 697                     float distance = isLinear ?
 698                         // length of projection of <x,y> onto the gradient vector == {<x,y> \dot {grad \over |grad|}}
 699                         (x * (x2 - x1) + y * (y2 - y1)) / (float)Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)) :
 700
 701                         // radial form is simple! FIXME, not quite right
 702                         (float)Math.sqrt((x - cx) * (x - cx) + (y - cy) * (y - cy));
 703
 704                     // FIXME: offsets are 0..1, not 0..length(gradient)
 705                     int i = 0; for(; i<stop_offsets.length; i++) if (distance < stop_offsets[i]) break;
 706
 707                     // FIXME: handle points beyond the bounds
 708                     if (i < 0 || i >= stop_offsets.length) continue;
 709
 710                     // gradate from offsets[i - 1] to offsets[i]
 711                     float percentage = ((distance - stop_offsets[i - 1]) / (stop_offsets[i] - stop_offsets[i - 1]));
 712
 713                     int a = (int)((((stop_colors[i] >> 24) & 0xff) - ((stop_colors[i - 1] >> 24) & 0xff)) * percentage) +
 714                         ((stop_colors[i - 1] >> 24) & 0xff);
 715                     int r = (int)((((stop_colors[i] >> 16) & 0xff) - ((stop_colors[i - 1] >> 16) & 0xff)) * percentage) +
 716                         ((stop_colors[i - 1] >> 16) & 0xff);
 717                     int g = (int)((((stop_colors[i] >> 8) & 0xff)  - ((stop_colors[i - 1] >> 8) & 0xff)) * percentage) +
 718                         ((stop_colors[i - 1] >> 8) & 0xff);
 719                     int b = (int)((((stop_colors[i] >> 0) & 0xff)  - ((stop_colors[i - 1] >> 0) & 0xff)) * percentage) +
 720                         ((stop_colors[i - 1] >> 0) & 0xff);
 721                     int argb = (a << 24) | (r << 16) | (g << 8) | b;
 722                     buf.drawPoint((int)x, (int)Math.floor(y), argb);
 723                 }
 724             }
 725         }
 726     }
 727
 728     public static class LinearGradientPaint extends GradientPaint {
 729         public LinearGradientPaint(float x1, float y1, float x2, float y2, boolean reflect, boolean repeat,
 730                                    Affine gradientTransform,  int[] stop_colors, float[] stop_offsets) {
 731             super(reflect, repeat, gradientTransform, stop_colors, stop_offsets);
 732             this.x1 = x1; this.x2 = x2; this.y1 = y1; this.y2 = y2;
 733         }
 734         float x1 = 0, y1 = 0, x2 = 300, y2 = 300;
 735     }
 736
 737     public static class RadialGradientPaint extends GradientPaint {
 738         public RadialGradientPaint(float cx, float cy, float fx, float fy, float r, boolean reflect, boolean repeat,
 739                              Affine gradientTransform, int[] stop_colors, float[] stop_offsets) {
 740             super(reflect, repeat, gradientTransform, stop_colors, stop_offsets);
 741             this.cx = cx; this.cy = cy; this.fx = fx; this.fy = fy; this.r = r;
 742         }
 743
 744         float cx, cy, r, fx, fy;
 745
 746     }
 747     */
 748