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