src/org/ibex/graphics/Path.java

   1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
   2 // Licensed under the GNU General Public License version 2 ("the License").
   3 // You may not use this file except in compliance with the License.
   4
   5 // FIXME
   6 package org.ibex.graphics;
   7 import java.util.*;
   8 import org.ibex.util.*;
   9
  10 /** an abstract path; may contain splines and arcs */
  11 public class Path {
  12
  13     public static final float PX_PER_INCH = 72;
  14     public static final float INCHES_PER_CM = (float)0.3937;
  15     public static final float INCHES_PER_MM = INCHES_PER_CM / 10;
  16     private static final int DEFAULT_PATHLEN = 1000;
  17     private static final float PI = (float)Math.PI;
  18
  19     // the number of vertices on this path
  20     int numvertices = 0;
  21
  22     // the vertices of the path
  23     float[] x = new float[DEFAULT_PATHLEN];
  24     float[] y = new float[DEFAULT_PATHLEN];
  25
  26     // the type of each edge; type[i] is the type of the edge from x[i],y[i] to x[i+1],y[i+1]
  27     byte[] type = new byte[DEFAULT_PATHLEN];
  28
  29     // bezier control points
  30     float[] c1x = new float[DEFAULT_PATHLEN];  // or rx (arcto)
  31     float[] c1y = new float[DEFAULT_PATHLEN];  // or ry (arcto)
  32     float[] c2x = new float[DEFAULT_PATHLEN];  // or x-axis-rotation (arcto)
  33     float[] c2y = new float[DEFAULT_PATHLEN];  // or large-arc << 1 | sweep (arcto)
  34
  35     boolean closed = false;
  36
  37     static final byte TYPE_MOVETO = 0;
  38     static final byte TYPE_LINETO = 1;
  39     static final byte TYPE_ARCTO = 2;
  40     static final byte TYPE_CUBIC = 3;
  41     static final byte TYPE_QUADRADIC = 4;
  42
  43     // FIXME: hack
  44     private String toString;
  45     public String toString() { return toString; }
  46
  47     public Path(String s) {
  48         this.toString = s;
  49         Tokenizer t = new Tokenizer(s);
  50         char last_command = 'M';
  51         boolean first = true;
  52         while(t.hasMoreTokens()) {
  53             char command = t.parseCommand();
  54             if (first && command == 'm') command = 'M';
  55             if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
  56             first = false;
  57             boolean relative = Character.toLowerCase(command) == command;
  58             command = Character.toLowerCase(command);
  59             parseSingleCommandAndArguments(t, command, relative);
  60             last_command = command;
  61         }
  62     }
  63
  64     //#repeat width/height multiply_px/multiply_py horizontalBounds/verticalBounds
  65     public long horizontalBounds(Affine a) {
  66         // FIXME wrong
  67         float min = Float.MAX_VALUE;
  68         float max = Float.MIN_VALUE;
  69         for(int i=0; i<numvertices; i++) {
  70             min = Math.min(min, a.multiply_px(x[i], y[i]));
  71             max = Math.max(max, a.multiply_px(x[i], y[i]));
  72         }
  73         return Encode.twoFloatsToLong(max, min);
  74     }
  75     //#end
  76
  77     public long transform(Affine a, boolean forReal) { return transform(a, forReal, true); }
  78     public long transform(Affine a, boolean forReal, boolean widthheight) {
  79         float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
  80         float maxx = Integer.MIN_VALUE; float maxy = Integer.MIN_VALUE;
  81         for(int i=0; i<numvertices; i++) {
  82             if (type[i] == TYPE_ARCTO) { /* FIXME!!! WRONG!!!! */ continue; }
  83             float x   = a.multiply_px(this.x[i],   this.y[i]);    if (x>maxx) maxx = x; if (x<minx) minx = x;
  84             float y   = a.multiply_py(this.x[i],   this.y[i]);    if (y>maxy) maxy = y; if (y<miny) miny = y;
  85             float c1x = a.multiply_px(this.c1x[i], this.c1y[i]);  if (c1x>maxx) maxx = c1x; if (c1x<minx) minx = c1x;
  86             float c1y = a.multiply_py(this.c1x[i], this.c1y[i]);  if (c1y>maxy) maxy = c1y; if (c1y<miny) miny = c1y;
  87             float c2x = a.multiply_px(this.c2x[i], this.c2y[i]);  if (c2x>maxx) maxx = c2x; if (c2x<minx) minx = c2x;
  88             float c2y = a.multiply_py(this.c2x[i], this.c2y[i]);  if (c2y>maxy) maxy = c2y; if (c2y<miny) miny = c2y;
  89             if (forReal) {
  90                 this.x[i] = x; this.y[i] = y;
  91                 this.c1x[i] = c1x; this.c1y[i] = c1y;
  92                 this.c2x[i] = c2x; this.c2y[i] = c2y;
  93             }
  94         }
  95         if (widthheight) return ((((long)Float.floatToIntBits(maxx - minx)) << 32) | ((long)Float.floatToIntBits(maxy - miny)));
  96         else return ((((long)Float.floatToIntBits(minx)) << 32) | ((long)Float.floatToIntBits(miny)));
  97     }
  98
  99     public void alignToOrigin() {
 100         float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
 101         for(int i=0; i<numvertices; i++) { if (x[i] < minx) minx = x[i]; if (y[i] < miny) miny = y[i]; }
 102         for(int i=0; i<numvertices; i++) {
 103             x[i] -= minx; y[i] -= miny;
 104             if (type[i] == TYPE_ARCTO) continue;
 105             c1x[i] -= minx; c2x[i] -= minx; c1y[i] -= miny; c2y[i] -= miny;
 106         }
 107     }
 108
 109
 110     public static class Tokenizer {
 111         // FIXME: check array bounds exception for improperly terminated string
 112         String s;
 113         int i = 0;
 114         char lastCommand = 'M';
 115         public Tokenizer(String s) { this.s = s; }
 116
 117         public static Path parse(String s) {
 118             if (s == null) return null;
 119             Tokenizer t = new Tokenizer(s);
 120             Path ret = new Path(s);
 121             char last_command = 'M';
 122             boolean first = true;
 123             while(t.hasMoreTokens()) {
 124                 char command = t.parseCommand();
 125                 if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
 126                 first = false;
 127                 boolean relative = Character.toLowerCase(command) == command;
 128                 command = Character.toLowerCase(command);
 129                 ret.parseSingleCommandAndArguments(t, command, relative);
 130                 last_command = command;
 131             }
 132             return ret;
 133         }
 134
 135         private void consumeWhitespace() {
 136             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
 137             if (i < s.length() && s.charAt(i) == ',') i++;
 138             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
 139         }
 140         public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
 141         public char parseCommand() {
 142             consumeWhitespace();
 143             char c = s.charAt(i);
 144             if (!Character.isLetter(c)) return lastCommand;
 145             i++;
 146             return lastCommand = c;
 147         }
 148         public float parseFloat() {
 149             consumeWhitespace();
 150             int start = i;
 151             float multiplier = 1;
 152             for(; i < s.length(); i++) {
 153                 char c = s.charAt(i);
 154                 if (Character.isWhitespace(c) || c == ',' || (c == '-' && i != start)) break;
 155                 if (!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E' || c == '-')) {
 156                     if (c == '%') {                                // FIXME
 157                     } else if (s.regionMatches(i, "pt", 0, i+2)) { // FIXME
 158                     } else if (s.regionMatches(i, "em", 0, i+2)) { // FIXME
 159                     } else if (s.regionMatches(i, "pc", 0, i+2)) { // FIXME
 160                     } else if (s.regionMatches(i, "ex", 0, i+2)) { // FIXME
 161                     } else if (s.regionMatches(i, "mm", 0, i+2)) { i += 2; multiplier = INCHES_PER_MM * PX_PER_INCH; break;
 162                     } else if (s.regionMatches(i, "cm", 0, i+2)) { i += 2; multiplier = INCHES_PER_CM * PX_PER_INCH; break;
 163                     } else if (s.regionMatches(i, "in", 0, i+2)) { i += 2; multiplier = PX_PER_INCH; break;
 164                     } else if (s.regionMatches(i, "px", 0, i+2)) { i += 2; break;
 165                     } else if (Character.isLetter(c)) break;
 166                     throw new RuntimeException("didn't expect character \"" + c + "\" in a numeric constant");
 167                 }
 168             }
 169             //if (start == i) throw new RuntimeException("FIXME");
 170             if (start == i) return (float)0.0;
 171             try {
 172                 return Float.parseFloat(s.substring(start, i)) * multiplier;
 173             } catch (NumberFormatException nfe) {
 174                 Log.warn(Path.class, "offending string was \"" + s.substring(start, i) + "\"");
 175                 throw nfe;
 176             }
 177         }
 178     }
 179
 180     /** Creates a concrete vector path transformed through the given matrix. */
 181     public void addTo(Polygon ret, Affine a) {
 182         float NUMSTEPS = 5;  // FIXME
 183         ret.x[0] = a.multiply_px(x[0], y[0]);
 184         ret.y[0] = a.multiply_py(x[0], y[0]);
 185
 186         for(int i=0; i<numvertices; i++) {
 187             if (type[i] == TYPE_LINETO) {
 188                 float rx = x[i+1];
 189                 float ry = y[i+1];
 190                 ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
 191
 192             } else if (type[i] == TYPE_MOVETO) {
 193                 float rx = x[i+1];
 194                 float ry = y[i+1];
 195                 ret.newcontour();
 196                 ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
 197
 198             } else if (type[i] == TYPE_ARCTO) {
 199                 float rx = c1x[i];
 200                 float ry = c1y[i];
 201                 float phi = c2x[i];
 202                 float fa = ((int)c2y[i]) >> 1;
 203                 float fs = ((int)c2y[i]) & 1;
 204                 float x1 = x[i];
 205                 float y1 = y[i];
 206                 float x2 = x[i+1];
 207                 float y2 = y[i+1];
 208
 209                 // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
 210                 float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
 211                 float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
 212                 float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
 213                                              (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
 214                 float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
 215                 float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
 216                 float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
 217                 float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
 218
 219                 // F.6.4 Conversion from center to endpoint parameterization
 220                 float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
 221                 float det = ux * vy - uy * vx;
 222                 float theta1 = (det < 0 ? -1 : 1) *
 223                     (float)Math.acos((ux * vx + uy * vy) /
 224                                      ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
 225                 ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
 226                 vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
 227                 det = ux * vy - uy * vx;
 228                 float dtheta = (det < 0 ? -1 : 1) *
 229                     (float)Math.acos((ux * vx + uy * vy) /
 230                                      ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
 231                 dtheta = dtheta % (float)(2 * Math.PI);
 232
 233                 if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
 234                 if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
 235
 236                 if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
 237                 else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
 238
 239                 // FIXME: integrate F.6.6
 240                 // FIXME: isn't quite ending where it should...
 241
 242                 // F.6.3: Parameterization alternatives
 243                 float theta = theta1;
 244                 for(int j=0; j<NUMSTEPS; j++) {
 245                     float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
 246                         ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
 247                     float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
 248                         ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
 249                     ret.add(a.multiply_px(rasterx, rastery), a.multiply_py(rasterx, rastery));
 250                     theta += dtheta / NUMSTEPS;
 251                 }
 252
 253             } else if (type[i] == TYPE_CUBIC) {
 254
 255                 float ax = x[i+1] - 3 * c2x[i] + 3 * c1x[i] - x[i];
 256                 float bx = 3 * c2x[i] - 6 * c1x[i] + 3 * x[i];
 257                 float cx = 3 * c1x[i] - 3 * x[i];
 258                 float dx = x[i];
 259                 float ay = y[i+1] - 3 * c2y[i] + 3 * c1y[i] - y[i];
 260                 float by = 3 * c2y[i] - 6 * c1y[i] + 3 * y[i];
 261                 float cy = 3 * c1y[i] - 3 * y[i];
 262                 float dy = y[i];
 263
 264                 float x0 = a.multiply_px(x[i], y[i]);
 265                 float y0 = a.multiply_py(x[i], y[i]);
 266                 float x1 = a.multiply_px(x[i+1], y[i+1]);
 267                 float y1 = a.multiply_py(x[i+1], y[i+1]);
 268                 float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
 269
 270                 for(float t=0; t<1; t += 1 / (steps/20)) {
 271                     float rx = ax * t * t * t + bx * t * t + cx * t + dx;
 272                     float ry = ay * t * t * t + by * t * t + cy * t + dy;
 273                     ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
 274                 }
 275
 276
 277             } else if (type[i] == TYPE_QUADRADIC) {
 278
 279                 float bx = x[i+1] - 2 * c1x[i] + x[i];
 280                 float cx = 2 * c1x[i] - 2 * x[i];
 281                 float dx = x[i];
 282                 float by = y[i+1] - 2 * c1y[i] + y[i];
 283                 float cy = 2 * c1y[i] - 2 * y[i];
 284                 float dy = y[i];
 285
 286                 float x0 = a.multiply_px(x[i], y[i]);
 287                 float y0 = a.multiply_py(x[i], y[i]);
 288                 float x1 = a.multiply_px(x[i+1], y[i+1]);
 289                 float y1 = a.multiply_py(x[i+1], y[i+1]);
 290                 float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
 291
 292                 for(float t=0; t<1; t += 1 / (steps/20)) {
 293                     float rx = bx * t * t + cx * t + dx;
 294                     float ry = by * t * t + cy * t + dy;
 295                     ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
 296                 }
 297
 298             }
 299         }
 300     }
 301
 302     protected void parseSingleCommandAndArguments(Tokenizer t, char command, boolean relative) {
 303         if (numvertices == 0 && command != 'm')
 304             throw new RuntimeException("first command MUST be an 'm', not a " + command);
 305         if (numvertices > x.length - 2) {
 306             float[] new_x = new float[x.length * 2]; System.arraycopy(x, 0, new_x, 0, x.length); x = new_x;
 307             float[] new_y = new float[y.length * 2]; System.arraycopy(y, 0, new_y, 0, y.length); y = new_y;
 308         }
 309         switch(command) {
 310             case 'z': {
 311                 int where;
 312                 type[numvertices-1] = TYPE_LINETO;
 313                 for(where = numvertices-2; where >= 0 && type[where] != TYPE_MOVETO; where--);
 314                 x[numvertices] = x[where+1];
 315                 y[numvertices] = y[where+1];
 316                 numvertices++;
 317                 closed = true;
 318                 // FIXME: actually, we should search back to the last 'z' or 'm', not just 'm'
 319                 break;
 320             }
 321
 322             case 'm': {
 323                 if (numvertices > 0) type[numvertices-1] = TYPE_MOVETO;
 324                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 325                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 326                 if (numvertices > 2 && type[numvertices-2] == TYPE_MOVETO) {
 327                     x[numvertices-1] = x[numvertices];
 328                     y[numvertices-1] = y[numvertices];
 329                 } else {
 330                     numvertices++;
 331                 }
 332                 break;
 333             }
 334
 335             case 'l': case 'h': case 'v': {
 336                 type[numvertices-1] = TYPE_LINETO;
 337                 float first = t.parseFloat(), second;
 338                 if (command == 'h') {
 339                     second = relative ? 0 : y[numvertices - 1];
 340                 } else if (command == 'v') {
 341                     second = first; first = relative ? 0 : x[numvertices - 1];
 342                 } else {
 343                     second = t.parseFloat();
 344                 }
 345                 x[numvertices] = first + (relative ? x[numvertices - 1] : 0);
 346                 y[numvertices] = second + (relative ? y[numvertices - 1] : 0);
 347                 numvertices++;
 348                 break;
 349             }
 350
 351             case 'a': {
 352                 type[numvertices-1] = TYPE_ARCTO;
 353                 c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 354                 c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 355                 c2x[numvertices-1] = (t.parseFloat() / 360) * 2 * PI;
 356                 c2y[numvertices-1] = (((int)t.parseFloat()) << 1) | (int)t.parseFloat();
 357                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 358                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 359                 numvertices++;
 360                 break;
 361             }
 362
 363             case 's': case 'c': {
 364                 type[numvertices-1] = TYPE_CUBIC;
 365                 if (command == 'c') {
 366                     c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 367                     c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 368                 } else if (numvertices > 1 && type[numvertices-2] == TYPE_CUBIC) {
 369                     c1x[numvertices-1] = 2 * x[numvertices - 1] - c2x[numvertices-2];
 370                     c1y[numvertices-1] = 2 * y[numvertices - 1] - c2y[numvertices-2];
 371                 } else {
 372                     c1x[numvertices-1] = x[numvertices-1];
 373                     c1y[numvertices-1] = y[numvertices-1];
 374                 }
 375                 c2x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 376                 c2y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 377                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 378                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 379                 numvertices++;
 380                 break;
 381             }
 382
 383             case 't': case 'q': {
 384                 type[numvertices-1] = TYPE_QUADRADIC;
 385                 if (command == 'q') {
 386                     c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 387                     c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 388                 } else if (numvertices > 1 && type[numvertices-2] == TYPE_QUADRADIC) {
 389                     c1x[numvertices-1] = 2 * x[numvertices - 1] - c1x[numvertices-2];
 390                     c1y[numvertices-1] = 2 * y[numvertices - 1] - c1y[numvertices-2];
 391                 } else {
 392                     c1x[numvertices-1] = x[numvertices-1];
 393                     c1y[numvertices-1] = y[numvertices-1];
 394                 }
 395                 x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
 396                 y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
 397                 numvertices++;
 398                 break;
 399             }
 400
 401             default:
 402                 // FIXME
 403         }
 404
 405         /*
 406         // invariant: after this loop, no two lines intersect other than at a vertex
 407         // FIXME: cleanup
 408         int index = numvertices - 2;
 409         for(int i=0; i<Math.min(numvertices - 3, index); i++) {
 410         for(int j = index; j < numvertices - 1; j++) {
 411
 412         // I'm not sure how to deal with vertical lines...
 413         if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
 414
 415         float islope = (y[i+1] - y[i]) / (x[i+1] - x[i]);
 416         float jslope = (y[j+1] - y[j]) / (x[j+1] - x[j]);
 417         if (islope == jslope) continue;   // parallel lines can't intersect
 418
 419         float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
 420         float _y = islope * (_x - x[i]) + y[i];
 421
 422         if (_x > Math.min(x[i+1], x[i]) && _x < Math.max(x[i+1], x[i]) &&
 423         _x > Math.min(x[j+1], x[j]) && _x < Math.max(x[j+1], x[j])) {
 424         // FIXME: something's not right in here.  See if we can do without fracturing line 'i'.
 425         for(int k = ++numvertices; k>i; k--) { x[k] = x[k - 1]; y[k] = y[k - 1]; }
 426         x[i+1] = _x;
 427         y[i+1] = _y;
 428         x[numvertices] = x[numvertices - 1];  x[numvertices - 1] = _x;
 429         y[numvertices] = y[numvertices - 1];  y[numvertices - 1] = _y;
 430         edges[numedges++] = numvertices - 1; numvertices++;
 431         index++;
 432         break;  // actually 'continue' the outermost loop
 433         }
 434         }
 435         }
 436         */
 437
 438     }
 439
 440 }