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     //#repeat width/height multiply_px/multiply_py horizontalBounds/verticalBounds
 191     public long horizontalBounds(Affine a) {
 192         // FIXME wrong
 193         float min = Float.MAX_VALUE;
 194         float max = Float.MIN_VALUE;
 195         for(Curve c = head; c != null; c = c.next) {
 196             min = Math.min(min, a.multiply_px(c.x, c.y));
 197             max = Math.max(max, a.multiply_px(c.x, c.y));
 198         }
 199         return Encode.twoFloatsToLong(max, min);
 200     }
 201     //#end
 202
 203     public long transform(Affine a, boolean forReal) { return transform(a, forReal, true); }
 204     public long transform(Affine a, boolean forReal, boolean widthheight) {
 205         float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
 206         float maxx = Integer.MIN_VALUE; float maxy = Integer.MIN_VALUE;
 207         for(Curve c = head; c != null; c = c.next) {
 208             if (c instanceof Arc) { /* FIXME!!! WRONG!!!! */ continue; }
 209             float x   = a.multiply_px(c.x,   c.y);    if (x>maxx) maxx = x; if (x<minx) minx = x;
 210             float y   = a.multiply_py(c.x,   c.y);    if (y>maxy) maxy = y; if (y<miny) miny = y;
 211             float c1x = a.multiply_px(c.c1x, c.c1y);  if (c1x>maxx) maxx = c1x; if (c1x<minx) minx = c1x;
 212             float c1y = a.multiply_py(c.c1x, c.c1y);  if (c1y>maxy) maxy = c1y; if (c1y<miny) miny = c1y;
 213             float c2x = a.multiply_px(c.c2x, c.c2y);  if (c2x>maxx) maxx = c2x; if (c2x<minx) minx = c2x;
 214             float c2y = a.multiply_py(c.c2x, c.c2y);  if (c2y>maxy) maxy = c2y; if (c2y<miny) miny = c2y;
 215             if (forReal) {
 216                 c.x = x; c.y = y;
 217                 c.c1x = c1x; c.c1y = c1y;
 218                 c.c2x = c2x; c.c2y = c2y;
 219             }
 220         }
 221         if (widthheight) return ((((long)Float.floatToIntBits(maxx - minx)) << 32) | ((long)Float.floatToIntBits(maxy - miny)));
 222         else return ((((long)Float.floatToIntBits(minx)) << 32) | ((long)Float.floatToIntBits(miny)));
 223     }
 224
 225     public void alignToOrigin() {
 226         float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
 227         for(Curve c = head; c != null; c = c.next) { if (c.x < minx) minx = c.x; if (c.y < miny) miny = c.y; }
 228         for(Curve c = head; c != null; c = c.next) {
 229             c.x -= minx; c.y -= miny;
 230             if (c instanceof Arc) continue;
 231             c.c1x -= minx; c.c2x -= minx; c.c1y -= miny; c.c2y -= miny;
 232         }
 233     }
 234
 235     public static class Tokenizer {
 236         // FIXME: check array bounds exception for improperly terminated string
 237         String s;
 238         int i = 0;
 239         char lastCommand = 'M';
 240         public Tokenizer(String s) { this.s = s; }
 241
 242         public static Path parse(String s) {
 243             if (s == null) return null;
 244             Tokenizer t = new Tokenizer(s);
 245             Path ret = new Path(s);
 246             return ret;/*
 247             char last_command = 'M';
 248             boolean first = true;
 249             while(t.hasMoreTokens()) {
 250                 char command = t.parseCommand();
 251                 if (first && command != 'M') throw new RuntimeException("the first command of a path must be 'M'");
 252                 first = false;
 253                 boolean relative = Character.toLowerCase(command) == command;
 254                 command = Character.toLowerCase(command);
 255                 ret.parseSingleCommandAndArguments(t, command, relative);
 256                 last_command = command;
 257             }
 258             return ret;*/
 259         }
 260         private void consumeWhitespace() {
 261             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
 262             if (i < s.length() && s.charAt(i) == ',') i++;
 263             while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
 264         }
 265         public boolean hasMoreTokens() { consumeWhitespace(); return i < s.length(); }
 266         public char parseCommand() {
 267             consumeWhitespace();
 268             char c = s.charAt(i);
 269             if (!Character.isLetter(c)) return lastCommand;
 270             i++;
 271             return lastCommand = c;
 272         }
 273         public float parseFloat() {
 274             consumeWhitespace();
 275             int start = i;
 276             float multiplier = 1;
 277             for(; i < s.length(); i++) {
 278                 char c = s.charAt(i);
 279                 if (Character.isWhitespace(c) || c == ',' || (c == '-' && i != start)) break;
 280                 if (!((c >= '0' && c <= '9') || c == '.' || c == 'e' || c == 'E' || c == '-')) {
 281                     if (c == '%') {                                // FIXME
 282                     } else if (s.regionMatches(i, "pt", 0, i+2)) { // FIXME
 283                     } else if (s.regionMatches(i, "em", 0, i+2)) { // FIXME
 284                     } else if (s.regionMatches(i, "pc", 0, i+2)) { // FIXME
 285                     } else if (s.regionMatches(i, "ex", 0, i+2)) { // FIXME
 286                     } else if (s.regionMatches(i, "mm", 0, i+2)) { i += 2; multiplier = INCHES_PER_MM * PX_PER_INCH; break;
 287                     } else if (s.regionMatches(i, "cm", 0, i+2)) { i += 2; multiplier = INCHES_PER_CM * PX_PER_INCH; break;
 288                     } else if (s.regionMatches(i, "in", 0, i+2)) { i += 2; multiplier = PX_PER_INCH; break;
 289                     } else if (s.regionMatches(i, "px", 0, i+2)) { i += 2; break;
 290                     } else if (Character.isLetter(c)) break;
 291                     throw new RuntimeException("didn't expect character \"" + c + "\" in a numeric constant");
 292                 }
 293             }
 294             //if (start == i) throw new RuntimeException("FIXME");
 295             if (start == i) return (float)0.0;
 296             try {
 297                 return Float.parseFloat(s.substring(start, i)) * multiplier;
 298             } catch (NumberFormatException nfe) {
 299                 Log.warn(Path.class, "offending string was \"" + s.substring(start, i) + "\"");
 300                 throw nfe;
 301             }
 302         }
 303     }
 304
 305     protected void parseSingleCommandAndArguments(Tokenizer t, char command, boolean relative) {
 306         if (tail==null && command!='m') throw new RuntimeException("first command MUST be an 'm', not a " + command);
 307         switch(command) {
 308             case 'z': {
 309                 Curve c;
 310                 for(c = tail.prev; c != null && !(c instanceof Move); c = c.prev);
 311                 Line ret = new Line();
 312                 ret.x = c.x;
 313                 ret.y = c.y;
 314                 add(ret);
 315                 Move mov = new Move();
 316                 mov.x = ret.x;
 317                 mov.y = ret.y;
 318                 add(mov);
 319                 closed = true;
 320                 // FIXME: actually, we should search back to the last 'z' or 'm', not just 'm'
 321                 break;
 322             }
 323
 324             case 'm': {
 325                 // feature: collapse consecutive movetos
 326                 Move ret = new Move();
 327                 ret.x = t.parseFloat() + (relative ? tail.y : 0);
 328                 ret.y = t.parseFloat() + (relative ? tail.y : 0);
 329                 add(ret);
 330                 break;
 331             }
 332
 333             case 'l': case 'h': case 'v': {
 334                 float first = t.parseFloat(), second;
 335                 if (command == 'h')      second = relative ? 0 : tail.y;
 336                 else if (command == 'v') { second = first; first = relative ? 0 : tail.x; }
 337                 else                     second = t.parseFloat();
 338                 Line ret = new Line();
 339                 ret.x = first + (relative ? tail.x : 0);
 340                 ret.y = second + (relative ? tail.y : 0);
 341                 add(ret);
 342                 break;
 343             }
 344
 345             case 'a': {
 346                 Arc ret = new Arc();
 347                 ret.c1x = t.parseFloat() + (relative ? tail.x : 0);
 348                 ret.c1y = t.parseFloat() + (relative ? tail.y : 0);
 349                 ret.c2x = (t.parseFloat() / 360) * 2 * PI;
 350                 ret.c2y = t.parseFloat();
 351                 ret.x = t.parseFloat() + (relative ? tail.x : 0);
 352                 ret.y = t.parseFloat() + (relative ? tail.y : 0);
 353                 add(ret);
 354                 break;
 355             }
 356
 357             case 's': case 'c': {
 358                 Bezier ret = new Bezier();
 359                 if (command == 'c') {
 360                     tail.c1x = t.parseFloat() + (relative ? tail.x : 0);
 361                     tail.c1y = t.parseFloat() + (relative ? tail.y : 0);
 362                 } else if (head != null && tail instanceof Bezier) {
 363                     tail.c1x = 2 * tail.x-((Bezier)tail).c2x;
 364                     tail.c1y = 2 * tail.y-((Bezier)tail).c2x;
 365                 } else {
 366                     tail.c1x = tail.x;
 367                     tail.c1y = tail.y;
 368                 }
 369                 tail.c2x = t.parseFloat() + (relative ? tail.x : 0);
 370                 tail.c2y = t.parseFloat() + (relative ? tail.y : 0);
 371                 ret.x = t.parseFloat() + (relative ? tail.x : 0);
 372                 ret.y = t.parseFloat() + (relative ? tail.y : 0);
 373                 add(ret);
 374                 break;
 375             }
 376
 377             case 't': case 'q': {
 378                 QuadBezier ret = new QuadBezier();
 379                 if (command == 'q') {
 380                     tail.c1x = t.parseFloat() + (relative ? tail.x : 0);
 381                     tail.c1y = t.parseFloat() + (relative ? tail.y : 0);
 382                 } else if (head != null && tail instanceof QuadBezier) {
 383                     tail.c1x = 2 * tail.x-((QuadBezier)tail).c1x;
 384                     tail.c1y = 2 * tail.y-((QuadBezier)tail).c1y;
 385                 } else {
 386                     tail.c1x = tail.x;
 387                     tail.c1y = tail.y;
 388                 }
 389                 ret.x = t.parseFloat() + (relative ? tail.x : 0);
 390                 ret.y = t.parseFloat() + (relative ? tail.y : 0);
 391                 add(ret);
 392                 break;
 393             }
 394
 395             default:
 396         }
 397
 398     }
 399
 400 }