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