src/org/ibex/graphics/Mesh.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 java.util.collections.*;
   8 import org.ibex.util.*;
   9
  10 // TODO:
  11 //  - allow edge-constraint removal
  12 //
  13 //  ~30% of our time spent finding vertices => use a balanced quadtree
  14 //
  15 //  - store "which curve is inside me" pointer in Triangle
  16 //      - split if two curves enter
  17 //  - go to treating Vertex as a value class (epsilon==0)
  18 //  - union()
  19 //  - subtract()
  20 //  - [??] preserve in/out-ness every time we delete() a triangle
  21
  22 /**
  23  *  An incremental, adaptive, addWeighted Delaunay Triangulation.
  24  *  @see Kallmann, Bieri, and Thalmann: Fully Dynamic AddWeighted Delaunay Triangulations
  25  */
  26 public final class Mesh {
  27
  28     private static final float epsilon = (float)0.0001;
  29     private static final float epsilon2 = (float)0.001;
  30     private static final boolean debug = false;
  31
  32     private  Vector    triangles   = new Vector();     /* we no longer need this */
  33     private  Hash      edges       = new Hash();       /* we no longer need this either */
  34     private  int       numvertices = 0;
  35     private  Triangle  triangle0   = null;
  36     private  Vertex    vertex0     = null;
  37     private  Vertex    vertex1     = null;
  38     private  Vertex    start       = null;
  39     private  Vertex    last        = null;
  40
  41     public Mesh copy() {
  42         Mesh m = new Mesh();
  43         m.vertex(triangle0.v(1));
  44         m.vertex(triangle0.v(2));
  45         m.vertex(triangle0.v(3));
  46         Object[] edges = this.edges.vals();
  47         for(int i=0; i<edges.length; i++) {
  48             Edge e = (Edge)edges[i];
  49             Vertex mv1 = m.vertex(e.v(1));
  50             Vertex mv2 = m.vertex(e.v(2));
  51             Edge me = m.getEdge(mv1, mv2);
  52             if (e.locked()) {
  53                 me.lock(mv1, 0);
  54                 me.weight = e.weight;
  55             }
  56         }
  57         m.setIn(true);
  58         return m;
  59     }
  60
  61     public void reset() {
  62         triangles.setSize(0);
  63         start = null;
  64         last = null;
  65     }
  66
  67     // Chain //////////////////////////////////////////////////////////////////////////////
  68
  69     public static interface Chain {
  70         public Mesh.Chain getMeshChainParent();
  71         public Affine     getAffine();
  72         public Mesh       getMesh();
  73     }
  74
  75     // Constructor //////////////////////////////////////////////////////////////////////////////
  76
  77     public Mesh() { }
  78     public Mesh(Path p, boolean evenOdd) { p.addTo(this, evenOdd); }
  79
  80     public void subtract(Mesh m, Affine a) { clipOp(m,a,true); }
  81     public void intersect(Mesh m, Affine a) { clipOp(m,a,false); }
  82     public void add(Mesh m, Affine a) { iterateTriangles(ITERATE_ADD, m, a); }
  83     public static long seekTime = 0;
  84
  85     public static final int ITERATE_SUBTRACT     = 1;
  86     public static final int ITERATE_INTERSECT    = 2;
  87     public static final int ITERATE_ADD          = 3;
  88     public static final int ITERATE_CLEAR_WASSET = 4;
  89     public static final int ITERATE_CLEAR        = 5;
  90     public static final int ITERATE_STROKE       = 6;
  91     int tick = 0;
  92     Triangle[] iter  = new Triangle[100];
  93
  94     private void iterateTriangles(int mode, Mesh m, Affine a) { iterateTriangles(mode, m, a, null, 0); }
  95     private void iterateTriangles(int mode, Mesh m, Affine a, PixelBuffer buf, int color) {
  96         tick++;
  97         int numiter = 0;
  98         if (iter.length < triangles.size()) iter = new Triangle[triangles.size()];
  99         iter[numiter++] = triangle0;
 100         while(numiter > 0) {
 101             Triangle t = iter[--numiter];
 102             if (t.tick >= this.tick) continue;
 103             switch(mode) {
 104                 case ITERATE_STROKE:          t.stroke(buf, a, color); break;
 105                 case ITERATE_CLEAR:           t.clear(); break;
 106                 case ITERATE_CLEAR_WASSET:    t.inWasSet = false; break;
 107                 case ITERATE_INTERSECT:
 108                 case ITERATE_SUBTRACT: {
 109                     if (!t.in) break;
 110                     boolean oin = m.queryPoint(t.c().multiply(a));
 111                     t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin);
 112                     break;
 113                     }
 114                 case ITERATE_ADD: {
 115                     for(int i=1; i<=3; i++) {
 116                         Edge e = t.e(i);
 117                         if (e.t1 != null && e.t1.tick >= this.tick) continue;
 118                         if (e.t2 != null && e.t2.tick >= this.tick) continue;
 119                         if (!e.locked()) continue;
 120                         if ((e.t1==null || !e.t1.in) && (e.t2==null || !e.t2.in)) continue;
 121                         Point p1 = e.v(1).multiply(a);
 122                         Point p2 = e.v(2).multiply(a);
 123                         Vertex v1=null, v2=null;
 124                             v1 = m.vertex(p1);
 125                             v2 = m.vertex(p2);
 126                         if (v1==v2) continue;
 127                         m.getEdge(v1, v2).lock(v1, 0);
 128                     }
 129                     break;
 130                 }
 131             }
 132             t.tick = this.tick;
 133             for(int i=1; i<=3; i++) {
 134                 Triangle ti = t.t(i);
 135                 if (ti == null) continue;
 136                 if (ti.tick >= this.tick) continue;
 137                 iter[numiter++] = ti;
 138             }
 139         }
 140     }
 141
 142     public void clipOp(Mesh m, Affine a, boolean subtract) {
 143         seekTime = 0;
 144         long start = System.currentTimeMillis();
 145         m.add(this, a);
 146         iterateTriangles(subtract ? ITERATE_SUBTRACT : ITERATE_INTERSECT, m, a.inverse());
 147         float total = (float)((System.currentTimeMillis() - start));
 148         float seek  = (float)seekTime;
 149         if (total > 80) System.out.println("clip in " + (100 * (seek/total)) + "%");
 150     }
 151
 152     // Geometry //////////////////////////////////////////////////////////////////////////////
 153
 154     public static double ddistance(double x1, double y1, double x2, double y2) {
 155         return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
 156     public static float area(Point p1, Point p2, Point p3) {
 157         float x1 = p1.x;
 158         float x2 = p2.x;
 159         float x3 = p3.x;
 160         float y1 = p1.y;
 161         float y2 = p2.y;
 162         float y3 = p3.y;
 163         double a = ddistance(x1,y1,x2,y2);
 164         double b = ddistance(x2,y2,x3,y3);
 165         double c = ddistance(x3,y3,x1,y1);
 166         double s = (a+b+c)/2;
 167         double t = s*(s-a)*(s-b)*(s-c);
 168         if (t < 0) return 0;
 169         return (float)Math.sqrt(t);
 170     }
 171
 172     public Point intersect(Point v1, Point v2, Point v3, Point v4) {
 173         double a1 = v2.y-v1.y;
 174         double a2 = v4.y-v3.y;
 175         double b1 = v1.x-v2.x;
 176         double b2 = v3.x-v4.x;
 177         double c1 = -1 * (a1*v1.x+b1*v1.y);
 178         double c2 = -1 * (a2*v3.x+b2*v3.y);
 179         double x = (b2*c1-c2*b1)/(b1*a2-b2*a1);
 180         double y = (a2*c1-c2*a1)/(a1*b2-a2*b1);
 181         if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n ");
 182         return point((float)x,(float)y);
 183     }
 184
 185     public static int side(Point p1, Point p2, Point p3) {
 186         float x0 = p1.x;
 187         float x = p2.x;
 188         float x2 = p3.x;
 189         float y0 = p1.y;
 190         float y = p2.y;
 191         float y2 = p3.y;
 192         // this MUST be done to double precision
 193         double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2);
 194         if (c > 0) return b>=0 ? -1 :  1;
 195         if (c < 0) return b>=0 ?  1 : -1;
 196         return 0;
 197     }
 198
 199     // Vertex //////////////////////////////////////////////////////////////////////////////
 200
 201     public Vertex vertex(Point p, Affine a) { return vertex(p.multiply(a)); }
 202     public Vertex vertex(Point p) {
 203         Vertex ret = null;
 204         switch(numvertices) {
 205             case 0: return (vertex0 = new Vertex(p));
 206             case 1: return vertex0.distance(p)<=epsilon ? vertex0 : (vertex1 = new Vertex(p));
 207             case 2: {
 208                 if (vertex0.distance(p)<=epsilon) return vertex0;
 209                 if (vertex1.distance(p)<=epsilon) return vertex1;
 210                 Vertex v2 = new Vertex(p);
 211                 triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0));
 212                 return v2;
 213             }
 214             default: {
 215                 Triangle t = null;
 216                     t = triangle0.seek(p);
 217                 for(int i=1; i<=3; i++)
 218                     for(int j=1; j<=2; j++)
 219                         if (t != null && t.e(i).v(j).distance(p)<=epsilon) return t.e(i).v(j);
 220                 Vertex v = new Vertex(p);
 221                 if      (t.e(3).intersects(p))          t.e(3).bisect(v);
 222                 else if (t.e(1).intersects(p))          t.e(1).bisect(v);
 223                 else if (t.e(2).intersects(p))          t.e(2).bisect(v);
 224                 else if (t.contains(v))                 t.trisect(v);
 225                 else                                    t.addHull(v);
 226                 return v;
 227             }
 228         }
 229     }
 230
 231     private Point point(float x, float y) { return new Point(x,y); }
 232     private Point point(Point a, Point b) { return new Point((a.x+b.x)/2,(a.y+b.y)/2); }
 233     private Point point(Point p, Affine a) { return point(p.x(a), p.y(a)); }
 234     private class Point {
 235         public float x;
 236         public float y;
 237         public String toString() { return "("+x+","+y+")"; }
 238         public Point multiply(Affine a) { return point(x(a),y(a)); }
 239         public Point(float x, float y) { this.x = x; this.y = y; }
 240         public Point(Point p) { this(p.x,p.y); }
 241         public boolean equals(float x, float y) { return distance(x,y) <= epsilon; }
 242         public boolean equals(Object o) { return (!(o instanceof Point)) ? false : ((Point)o).distance(this) <= epsilon; }
 243         public float distance(Point v) { return distance(v.x,v.y); }
 244         private float distance(float x, float y) { return (float)Math.sqrt(distance2(x, y)); }
 245         public float distance2(Point v) { return distance2(v.x, v.y); }
 246         private float distance2(float x, float y) { return (this.x-x)*(this.x-x)+(this.y-y)*(this.y-y); }
 247         public float x(Affine a) { return a.multiply_px(x,y); }
 248         public float y(Affine a) { return a.multiply_py(x,y); }
 249         public int xi(Affine a) { return (int)x(a); }
 250         public int yi(Affine a) { return (int)y(a); }
 251         public boolean intersects(Point p1, Point p2) {
 252             return
 253                 Mesh.side(p1,p2,this)==0 &&
 254                 x <= Math.max(p1.x,p2.x) &&
 255                 x >= Math.min(p1.x,p2.x) &&
 256                 y <= Math.max(p1.y,p2.y) &&
 257                 y >= Math.min(p1.y,p2.y);
 258         }
 259     }
 260
 261     private final class Vertex extends Point implements org.ibex.arenaj.Gladiator {
 262         public Vertex(Point p) { super(p); numvertices++; }
 263     }
 264
 265     // Edge //////////////////////////////////////////////////////////////////////////////
 266
 267     public Edge newEdge(Vertex v1, Vertex v2) {
 268         return getEdge(v1,v2);
 269         /*
 270         if (v1==v2) throw new Error();
 271         Edge ret = (Edge)edges.get(v1,v2);
 272         //if (ret != null) throw new Error("tried to get an edge that already exists!");
 273         if (ret == null) ret = new Edge(v1,v2);
 274         return ret;
 275         */
 276     }
 277
 278     public Edge getEdge(Vertex v1, Vertex v2) {
 279         if (v1==v2) throw new Error();
 280         //Edge ret = (Edge)edges.get(v1,v2);
 281         Edge ret = null;
 282         Triangle t = null;
 283         if (triangle0 != null) {
 284             t = triangle0.seek(point(v1,v2));
 285             if (t != null)
 286                 for(int i=1; i<=3; i++)
 287                     if (t.e(i).hasVertex(v1) && t.e(i).hasVertex(v2)) ret = t.e(i);
 288         }
 289         if (ret == null) {
 290             ret = (Edge)edges.get(v1,v2);
 291             if (ret != null && (ret.t1 != null || ret.t2 != null)) throw new Error("bah! " + ret);
 292         }
 293         if (ret == null) ret = new Edge(v1,v2);
 294         return ret;
 295     }
 296
 297     private final class Edge implements org.ibex.arenaj.Gladiator {
 298         private final Vertex v1;
 299         private final Vertex v2;
 300         Triangle t1 = null;
 301         Triangle t2 = null;
 302
 303         private int locks = 0;
 304         private int weight = 0;
 305
 306         public void delete() {
 307             if (t1!=null || t2!=null) throw new Error("tried to remove an edge before its triangles");
 308             edges.put(v1,v2,null);
 309             edges.put(v2,v1,null);
 310         }
 311
 312         public Vertex v(int i) { return i==1?v1:i==2?v2:null; }
 313
 314         public Edge rotate(Vertex v, boolean clockwise) {
 315             Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null;
 316             if (t==null) return null;
 317             for(int i=1; i<=3; i++) if (t.e(i)!=this && t.e(i).hasVertex(v)) return t.e(i);
 318             return null;
 319         }
 320         public Edge rotateHull(boolean clockwise) {
 321             if (t1!=null && t2!=null) throw new Error("nextHull() called on non-hull edge");
 322             Vertex v = rotate(v1, !clockwise) == null ? v2 : v1;
 323             Edge e = rotate(v, !clockwise);
 324             while(!e.hasTriangle(null) && e!=this) e = e.rotate(v, !clockwise);
 325             if (e==this) throw new Error("confused");
 326             return e;
 327         }
 328
 329         public boolean isNear(Point p) { return area(v1,v2,p) < epsilon2; }
 330         public Vertex commonVertex(Edge e) { return v1==e.v(1) || v1==e.v(2) ? v1 : v2==e.v(1) || v2==e.v(2) ? v2 : null; }
 331         public Vertex unCommonVertex(Edge e) { return v1!=e.v(1) && v1!=e.v(2) ? v1 : v2!=e.v(1) && v2!=e.v(2) ? v2 : null; }
 332         public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; }
 333         public int weight() { return weight; }
 334         public int weight(Vertex v) { return v==v1?weight:(-1*weight); }
 335         public boolean locked() { return locks > 0; }
 336         public boolean partitions(Point va, Point vb) { return side(va,vb)==-1; }
 337         public int     side(Point a, Point b) { return side(a) * side(b); }
 338         public int     side(Point a)          { return Mesh.side(v(1), v(2), a); }
 339         public boolean hasVertex(Vertex v) { return v1==v || v2==v; }
 340         public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; }
 341         public String toString() { return v(1) + "--" + v(2); }
 342         public void rmTriangle(Triangle t) {
 343             if (t1==t) t1 = null;
 344             else if (t2==t) t2 = null;
 345             else throw new Error();
 346             if (t1==null && t2==null) delete();
 347         }
 348         public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); }
 349
 350         public boolean colinear(Point v) { return area(v,v1,v2)<=epsilon; }
 351
 352         public boolean intersects(Point p) {
 353             return
 354                 side(p)==0 &&
 355                 p.x <= Math.max(v1.x,v2.x) &&
 356                 p.x >= Math.min(v1.x,v2.x) &&
 357                 p.y <= Math.max(v1.y,v2.y) &&
 358                 p.y >= Math.min(v1.y,v2.y);
 359         }
 360         public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); }
 361         public boolean intersects(Point va, Point vb) {
 362             return
 363                 !v1.equals(va) &&
 364                 !v1.equals(vb) &&
 365                 !v2.equals(va) &&
 366                 !v2.equals(vb) &&
 367                 partitions(va, vb) &&
 368                 Mesh.side(va, vb, v1) * Mesh.side(va, vb, v2) == -1;
 369         }
 370         public Triangle opposingTriangle(Triangle t) {
 371             if (t1 == t) return t2;
 372             if (t2 == t) return t1;
 373             throw new Error();
 374         }
 375         public void addTriangle(Triangle tnew) {
 376             if (t1==null) t1 = tnew;
 377             else if (t2==null) t2 = tnew;
 378             else throw new Error("attempted to addTriangle("+tnew+")\n  t1="+t1+"\n  t2="+t2);
 379             if (t1==t2) throw new Error("same triangle can't be both sides of an edge");
 380             if (v1.x==v2.x) {
 381                 boolean b  = side(t1.opposingVertex(this)) == side(point(Float.MAX_VALUE, v1.y));
 382                 Triangle right = b ? t1 : t2;       // right side
 383                 Triangle left  = b ? t2 : t1;       // left side
 384                 t1 = right;
 385                 t2 = left;
 386             } else {
 387                 boolean b       = side(t1.opposingVertex(this)) == side(point(0, Float.MAX_VALUE));
 388                 Triangle top    = b ? t1 : t2;
 389                 Triangle bottom = b ? t2 : t1;
 390                 if (v1.y==v2.y) {                         // horizontal
 391                     t1 = bottom;
 392                     t2 = top;
 393                 } else if (v1.x > v2.x) {                 // positive slope
 394                     t1 = top;
 395                     t2 = bottom;
 396                 } else {                                  // negative slope
 397                     t1 = bottom;
 398                     t2 = top;
 399                 }
 400             }
 401         }
 402         public void bisect(Vertex v) {
 403             Edge e = this;
 404             Triangle t1 = this.t1==null?this.t2:this.t1;
 405             Triangle t  = t1==this.t1?this.t2:this.t1;
 406             Vertex opposing = t1.opposingVertex(e);
 407             Triangle top = null, ton = null;
 408             Vertex left = e.v(1);
 409             Vertex right = e.v(2);
 410             Vertex tov = null;
 411             boolean in1 = t1.in;
 412             boolean in2 = false;
 413             Triangle opposingTriangleLeft = t1.opposingTriangle(left);
 414             Triangle opposingTriangleRight = t1.opposingTriangle(right);
 415             Edge right_v = newEdge(right, v);
 416             Edge left_v = newEdge(left, v);
 417             Edge opposing_v = newEdge(opposing, v);
 418             Edge tov_v = null;
 419             Edge right_tov = null;
 420             Edge left_tov = null;
 421             Edge right_opposing = t1.opposingEdge(left);
 422             Edge left_opposing = t1.opposingEdge(right);
 423             if (t != null) {
 424                 t.check();
 425                 right_tov = t.opposingEdge(left);
 426                 left_tov = t.opposingEdge(right);
 427                 top = t.opposingTriangle(left);
 428                 ton = t.opposingTriangle(right);
 429                 tov = t.opposingVertex(t1);
 430                 in2 = t.in;
 431                 tov_v = newEdge(tov, v);
 432                 if (top == t1) top = null;
 433                 if (ton == t1) ton = null;
 434                 if (opposingTriangleLeft == t) opposingTriangleLeft = null;
 435                 if (opposingTriangleRight == t) opposingTriangleRight = null;
 436                 t.delete();
 437             }
 438             t1.delete();
 439             Triangle ta, tb, tc, td;
 440             ta = triangle(right_opposing, opposing_v, right_v);
 441             tb = triangle(left_opposing, opposing_v, left_v);
 442             ta.in = in1;
 443             tb.in = in1;
 444             if (t != null) {
 445                 tc = triangle(left_tov, tov_v, left_v);
 446                 td = triangle(right_tov, tov_v, right_v);
 447                 tc.in = in2;
 448                 td.in = in2;
 449             }
 450             if (locked()) fracture(v);
 451             else ta.fixup();
 452         }
 453         public Edge flip() {
 454             if (locked()) throw new Error("attempted to remove a locked edge: " + this);
 455             boolean in = t1.in && t2.in;
 456
 457             Edge e3   = rotate(v1, true);
 458             Vertex vb = e3.unCommonVertex(this);
 459             Edge e6   = e3.rotate(vb, true);
 460
 461             Edge e4   = rotate(v2, true);
 462             Vertex va = e4.unCommonVertex(this);
 463             Edge e1   = e4.rotate(va, true);
 464
 465             Edge e    = newEdge(va, vb);
 466
 467             t1.delete();
 468             t2.delete();
 469             Triangle ta, tb;
 470             ta = triangle(e1, e, e3);
 471             tb = triangle(e4, e, e6);
 472             ta.in = in;
 473             tb.in = in;
 474             return ta.getSharedEdge(tb);
 475         }
 476         public void fracture(Vertex vx) {
 477             if (!locked()) throw new Error("attempt to fracture an edge which does not exist: " + v1 + " " + v2);
 478             // delete-me
 479             Edge v1vx = newEdge(v1, vx);
 480             Edge vxv2 = newEdge(vx, v2);
 481             v1vx.locks += locks;
 482             vxv2.locks += locks;
 483             locks = 0;
 484             v1vx.weight += v(1)==v1vx.v(1) ? weight : (-1 * weight);
 485             vxv2.weight += v(2)==vxv2.v(2) ? weight : (-1 * weight);
 486             weight = 0;
 487             v1vx.lock();
 488             vxv2.lock();
 489         }
 490         public void fracture(Edge e) {
 491             triangle0=e.t1==null?e.t2:e.t1;
 492             Vertex v0 = vertex(Mesh.this.intersect(v1,v2,e.v(1),e.v(2)));
 493             if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0);
 494             if (v0 != v1 && v0 != v2) fracture(v0);
 495         }
 496         public void lock(Vertex v1, int delta) {
 497             weight += this.v(1)==v1 ? delta : (-1 * delta);
 498             locks += 1;
 499             lock();
 500         }
 501         public void lock() {
 502             Triangle t = t1==null ? t2 : t1;
 503             if (t==null) t = triangle0.seek(v1);
 504             if (!t.hasVertex(v1)) throw new Error("this sucks balls");
 505             boolean skipfo = false;
 506             for(Triangle told = null; t != told; t = told==null ? t : t.followVector(v1,v2)) {
 507                 told = t;
 508                 if (!t.encounters(v1,v2)) break;
 509                 if (!t.encounters(v2,v1)) break;
 510                 Triangle tlast = t.followVector(v2,v1);
 511                 if (tlast == null) throw new Error("seek from: " + tlast + "\n  " + v1 + " -> " + v2);
 512                 if (tlast == t) { if (t.hasVertex(v1)) continue; throw new Error("no predecessor"); }
 513                 Edge e = t.getSharedEdge(tlast);
 514                 if (!e.convex()) continue;
 515                 if (e.v(1)==v1 || e.v(1)==v2 || e.v(2)==v1 || e.v(2)==v2) { continue; }
 516                 if (this.intersects(e.v(1))) { fracture(e.v(1)); return; }
 517                 if (this.intersects(e.v(2))) { fracture(e.v(2)); return; }
 518                 if (!this.intersects(e)) continue;
 519                 if (e.locked()) {
 520                     fracture(e);
 521                     return;
 522                 } else {
 523                     Edge eold = e = e.flip();
 524                     t = e.t1;
 525                     if (t==null || !t.intersects(this)) t = e.t2;
 526                     told = t;
 527                     if (eold.intersects(this)) {
 528                         t = t.followVector(v1,v2);
 529                         if (t != e.t1 && t != e.t2) t = told;
 530                         continue;
 531                     } else {
 532                         told = null;
 533                         while(t.intersects(this)) {
 534                             if (t==told) break;
 535                             told = t;
 536                             t = t.followVector(v2,v1);
 537                         }
 538                         t = told;
 539                         told = null;
 540                         continue;
 541                     }
 542                 }
 543             }
 544             if (t1!=null) t1.fixup();
 545             if (t2!=null) t2.fixup();
 546         }
 547
 548         public void stroke(PixelBuffer buf, Affine a, int color) {
 549             int c = debug
 550                 ? (weight() == 0 ? color : 0xffff0000)
 551                 : (weight() != 0 ? color : 0);
 552             if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c);
 553         }
 554         public Edge(Vertex v1, Vertex v2) {
 555             boolean b = v1.y < v2.y || (v1.y==v2.y && v1.x < v2.x);
 556             this.v1 = b ? v1 : v2;
 557             this.v2 = b ? v2 : v1;
 558             edges.put(v1, v2, this);
 559             edges.put(v2, v1, this);
 560         }
 561     }
 562
 563     // Triangle //////////////////////////////////////////////////////////////////////////////
 564
 565     public Triangle triangle(Edge e1, Edge e2, Edge e3) {
 566         float x = (e1.v(1).x+e1.v(2).x+e2.v(1).x+e2.v(2).x+e3.v(1).x+e3.v(2).x)/6;
 567         float y = (e1.v(1).y+e1.v(2).y+e2.v(1).y+e2.v(2).y+e3.v(1).y+e3.v(2).y)/6;
 568         Point p = point(x,y);
 569         Triangle t = triangle0==null ? null : triangle0.seek(p);
 570         if (t != null &&
 571             (t.contains(p) || t.intersects(p)) &&
 572             t.hasEdge(e1) &&
 573             t.hasEdge(e2) &&
 574             t.hasEdge(e3))
 575             return triangle0 = t;
 576         t = new Triangle(e1, e2, e3);
 577         if (debug) t.check();
 578         if (triangle0 == null) triangle0 = t;
 579         return t;
 580     }
 581
 582         public static boolean fixing = false;
 583     private final class Triangle implements org.ibex.arenaj.Gladiator {
 584
 585         final float r2;
 586         final Point cc;
 587
 588         private Edge e1, e2, e3;    // should be final =(
 589         public int tick;
 590
 591         boolean in = false;
 592         boolean inWasSet = false;
 593         boolean painted = false;
 594         boolean dirty = true;
 595
 596         public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; }
 597         public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); }
 598         public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; }
 599
 600         public boolean encounters(Point p1, Point p2) {
 601             for(int i=1; i<=3; i++) {
 602                 if (v(i).equals(p1)) return true;
 603                 if (v(i).equals(p2)) return true;
 604                 if (v(i).intersects(p1,p2)) return true;
 605                 if (e(i).intersects(p1,p2)) return true;
 606             }
 607             return contains(p1) || contains(p2);
 608         }
 609         public Edge getSharedEdge(Triangle t) { return e(1).t1==t||e(1).t2==t?e(1):e(2).t1==t||e(2).t2==t?e(2):e(3).t1==t||e(3).t2==t?e(3):null; }
 610         public boolean contains(Point p) { return e(1).side(v(1),p)==1 && e(2).side(v(2),p)==1 && e(3).side(v(3),p)==1; }
 611         public Point c()  { return point(cx(),cy()); }
 612         public float cx() { return (float)(((double)v(1).x+(double)v(2).x+(double)v(3).x)/3); }
 613         public float cy() { return (float)(((double)v(1).y+(double)v(2).y+(double)v(3).y)/3); }
 614         public boolean intersects(Vertex va, Vertex vb){return e(1).intersects(va,vb)||e(2).intersects(va,vb)||e(3).intersects(va,vb);}
 615         public boolean intersects(Edge e){ return intersects(e.v(1),e.v(2)); }
 616         public boolean intersects(Point p){ return e(1).intersects(p) || e(2).intersects(p) || e(3).intersects(p); }
 617         public boolean hasEdge(Edge e) { return e.t1==this || e.t2==this; }
 618         public boolean hasEdge(Vertex a, Vertex b) { return a!=b && (a==v(1)||a==v(2)||a==v(3)) && (b==v(1)||b==v(2)||b==v(3)); }
 619         public boolean hasVertex(Vertex a) { return a==v(1) || a==v(2) || a==v(3); }
 620         public Vertex opposingVertex(Triangle t) { return t(3)==t ? v(3) : t(1)==t ? v(1) : t(2)==t ? v(2) : null; }
 621         public Vertex opposingVertex(Edge e) { return e==e(1) ? v(1) : e==e(2) ? v(2) : e==e(3) ? v(3) : null; }
 622         public Edge   opposingEdge(Vertex v) { return v==v(1) ? e(1) : v==v(2) ? e(2) : v==v(3) ? e(3) : null; }
 623         public Triangle opposingTriangle(Vertex v) { return v(1)==v ? t(1) : v(2)==v ? t(2) : v(3)==v ? t(3) : null; }
 624         public String toString() { return "<<"+v(1)+""+v(2)+""+v(3)+">>"; }
 625
 626         public void stroke(PixelBuffer buf, Affine a, int color) {
 627             for(int i=1; i<=3; i++) if (in || debug) e(i).stroke(buf, a, color);
 628         }
 629         public Triangle fixup() {
 630             if (!dirty) return this;
 631             dirty = false;
 632             for(int i=1; i<=3; i++) {
 633                 Triangle t = t(i);
 634                 if (t==null) continue;
 635                 if (t.r2 <= v(i).distance2(t.cc)) continue;
 636                 Edge e = e(i);
 637                 if (e.locked()) { t.fixup(); continue; }
 638                 return e.flip().t1.fixup();
 639             }
 640             return this;
 641         }
 642         public void addHull(Vertex vnew) {
 643             Edge e = e(1).hasTriangle(null) ? e(1) : e(2).hasTriangle(null) ? e(2) : e(3).hasTriangle(null) ? e(3) : null;
 644             Triangle t = e.opposingTriangle(null), newt = null;
 645             while (!e.partitions(vnew, t.opposingVertex(e))) {
 646                 e = e.rotateHull(true);
 647                 t = e.opposingTriangle(null);
 648             }
 649             Edge ea = newEdge(e.v(1), vnew);
 650             Edge eb = newEdge(e.v(2), vnew);
 651             newt = triangle(e, ea, eb);
 652             if (ea.rotateHull(true) != eb) { Edge temp = ea; ea = eb; eb = temp; }
 653             for(int i=1; i<=2; i++)
 654                 for(Edge ex = i==1?eb:ea; ;) {
 655                     e = ex.rotateHull(i==1);
 656                     t = e.opposingTriangle(null);
 657                     if (!e.partitions(vnew, t.opposingVertex(e))) break;
 658                     Edge ep = newEdge(vnew, e.unCommonVertex(ex));
 659                     newt = triangle(e, ex, ep);
 660                     ex = ep;
 661                 }
 662             if (newt==null) throw new Error("couldn't find a place to add a triangle for " + vnew);
 663             newt.fixup();
 664         }
 665         public Triangle seek(Point p) {
 666             Triangle t = this;
 667             try {
 668             while (true) {
 669                 if      (t.contains(p) || t.intersects(p))  return t;
 670                 else if (t.e(3).intersects(p))                return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t;
 671                 else if (t.e(1).intersects(p))                return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t;
 672                 else if (t.e(2).intersects(p))                return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t;
 673                 else {
 674                     Triangle t2 = t.followVector(t.c(), p);
 675                     if (t2==null || t2==t) return t;
 676                     t = t2;
 677                 }
 678             }
 679             } finally { if (t!=null) triangle0 = t; }
 680         }
 681
 682         // gives the triangle across the edge through which the ray v(1)-->v(2) exits this triangle
 683         public Triangle followVector(Point p1, Point p2) {
 684             Triangle ret = followVector2(p1, p2);
 685             if (ret==null) return ret;
 686             triangle0 = ret;
 687             if (!ret.encounters(p1,p2)) return this;
 688             return ret;
 689         }
 690         public Triangle followVector2(Point p1, Point p2) {
 691             if (contains(p2) || intersects(p2) || v(1).equals(p2) || v(2).equals(p2) || v(3).equals(p2)) return this;
 692             for(int i=1; i<=3; i++) if (!v(i).equals(p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2);
 693             Triangle t1 = t(1);
 694             Triangle t2 = t(2);
 695             Triangle t3 = t(3);
 696             for(int i=1; i<=3; i++) {
 697                 int k1 = i==1?3:i==2?1:i==3?2:0;
 698                 int k2 = i==1?2:i==2?3:i==3?1:0;
 699                 int k3 = i==1?1:i==2?2:i==3?3:0;
 700                 if (v(i).equals(p1)) {
 701                     if (e(k1).partitions(v(k1),p2)) return t(k1);
 702                     if (e(k2).partitions(v(k2),p2)) return t(k2);
 703                     if (e(k3).partitions(v(k3),p2)) return t(k3);
 704                     throw new Error("bad!");
 705                 }
 706             }
 707             if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2))
 708                 throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" +
 709                                 "  p1=" + p1 + "\n" +
 710                                 "  p2=" + p2 + "\n" +
 711                                 "  t =" + this + " (area "+area(v(1),v(2),v(3))+")\n");
 712             for(int i=1; i<=3; i++) if (e(i).intersects(p1,p2) && e(i).side(v(i)) * e(i).side(p2) == -1) return t(i);
 713             throw new Error("giving up: \n  "+p1+" -> "+p2+"\n  " + this);
 714         }
 715
 716         public void check() {
 717             if (debug) {
 718                 for(int i=1; i<=3; i++) {
 719                     if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent");
 720                     if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent");
 721                     if (e(i).t1 == e(i).t2) throw new Error("same triangle on both sides of edge");
 722                 }
 723                 if (e(1)==e(2) || e(2)==e(3) || e(3)==e(1)) throw new Error("identical edges");
 724                 for(int i=1; i<=3; i++) {
 725                     if (t(i) != null) if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)");
 726                     if (t(i) != null) {
 727                         if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark");
 728                         if (!e(i).hasTriangle(t(i))) throw new Error("blark2");
 729                         if (!e(i).hasTriangle(this)) throw new Error("blark3");
 730                     }
 731                 }
 732                 // check that edges all join up
 733             }
 734         }
 735
 736         public void trisect(Vertex v) {
 737             if (!contains(v)) throw new Error("trisect(v) but I don't contain v = " + v);
 738             if (hasVertex(v)) throw new Error("attempt to trisect a triangle at one of its own vertices");
 739             for(int i=3; i>0; i--) if (e(i).isNear(v)) { e(i).bisect(v); return; }
 740             Triangle a=null,b=null,c=null;
 741
 742             boolean oldIn = in;
 743             Edge v1v = newEdge(v(1), v);
 744             Edge v2v = newEdge(v(2), v);
 745             Edge v3v = newEdge(v(3), v);
 746             Edge e1 = this.e(1);
 747             Edge e2 = this.e(2);
 748             Edge e3 = this.e(3);
 749             delete();
 750
 751             a = triangle(e3, v1v, v2v);
 752             b = triangle(e2, v1v, v3v);
 753             c = triangle(e1, v3v, v2v);
 754             a.in = oldIn;
 755             b.in = oldIn;
 756             c.in = oldIn;
 757             a.fixup();
 758         }
 759
 760         public void setIn(boolean evenOdd, int weight) {
 761             if (inWasSet) return;
 762             inWasSet = true;
 763             in = (evenOdd && weight%2!=0) || (!evenOdd && weight!=0);
 764             for(int i=1; i<=3; i++) if (t(i) != null) t(i).setIn(evenOdd, weight + e(i).weight());
 765         }
 766
 767         public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
 768             if (painted) return;
 769             painted = true;
 770             if (in) buf.fillTriangle(v(1).xi(a), v(1).yi(a), v(2).xi(a), v(2).yi(a), v(3).xi(a), v(3).yi(a), color);
 771             for(int i=1; i<=3; i++)
 772                 if (t(i) != null) {
 773                     boolean prepaint = t(i).painted;
 774                     if (debug) e(i).stroke(buf, a, color);
 775                     t(i).fill(buf, a, clip, color, strokeOnly);
 776                 }
 777         }
 778
 779         public Triangle(Edge e1, Edge e2, Edge e3) {
 780             this.e1 = e1;
 781             this.e2 = e2;
 782             this.e3 = e3;
 783             Vertex v1 = e(2).unCommonVertex(e(1));
 784             Vertex v2 = e(3).unCommonVertex(e(2));
 785             Vertex v3 = e(1).unCommonVertex(e(3));
 786             if (e(1).intersects(v1)) throw new Error("triangle points are colinear");
 787             if (e(2).intersects(v2)) throw new Error("triangle points are colinear");
 788             if (e(3).intersects(v3)) throw new Error("triangle points are colinear");
 789             e(1).addTriangle(this);
 790             e(2).addTriangle(this);
 791             e(3).addTriangle(this);
 792
 793             float a = 0;
 794             Q: for(int q=0; q<2; q++) {
 795                 for(int i=0; i<3; i++) {
 796                     if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q;
 797                     Vertex t = v2; v2=v3; v3=v1; v1 = t;
 798                 }
 799                 Vertex t = v2; v2=v3; v3=t;
 800             }
 801             if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
 802             float a1=(v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
 803             float a2=(v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
 804             cc=point((a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2, (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2);
 805             r2 = v1.distance2(cc);
 806             triangles.add(this);
 807         }
 808         public void clear() {
 809             if (!painted) return;
 810             painted = false;
 811             if (t(3) != null) t(3).clear();
 812             if (t(1) != null) t(1).clear();
 813             if (t(2) != null) t(2).clear();
 814         }
 815         public void delete() {
 816             if (triangle0 == this) {
 817                 if (t(1) != null) triangle0 = t(1);
 818                 else if (t(2) != null) triangle0 = t(2);
 819                 else if (t(3) != null) triangle0 = t(3);
 820                 else triangle0 = null;
 821             }
 822             triangles.remove(this);
 823             e(1).rmTriangle(this);
 824             e(2).rmTriangle(this);
 825             e(3).rmTriangle(this);
 826             e1 = null;
 827             e2 = null;
 828             e3 = null;
 829         }
 830     }
 831
 832     // Queries /////////////////////////////////////////////////////////////////////////////////
 833
 834     public boolean queryPoint(Point p) {
 835         if (triangle0==null) return false;
 836         Triangle ret = triangle0.seek(p);
 837         return (ret.contains(p) || ret.intersects(p)) && ret.in;
 838     }
 839
 840
 841     // Drawing //////////////////////////////////////////////////////////////////////////////
 842
 843     public void setIn(boolean evenOdd) {
 844         iterateTriangles(ITERATE_CLEAR_WASSET, null, null);
 845         triangle0.setIn(evenOdd, 1);
 846     }
 847
 848     public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
 849         if (triangle0==null) return;
 850         iterateTriangles(ITERATE_CLEAR, null, null);
 851         triangle0.fill(buf, a, clip, color, strokeOnly);
 852     }
 853
 854     public void stroke(PixelBuffer buf, Affine a, int color) {
 855         if (triangle0==null) return;
 856         iterateTriangles(ITERATE_STROKE, null, a, buf, color);
 857     }
 858
 859     public void newcontour() {
 860         if (start != null) add(start.x, start.y);
 861         start = null;
 862         last = null;
 863     }
 864
 865     public Mesh addRect(float x, float y, float w, float h) {
 866         if (w==0 || h==0) return this;
 867         Vertex v1 = vertex(point(x,y));
 868         Vertex v2 = vertex(point(x+w,y));
 869         Vertex v3 = vertex(point(x+w,y+h));
 870         Vertex v4 = vertex(point(x,y+h));
 871         newEdge(v1,v2).lock(v1,1);
 872         newEdge(v2,v3).lock(v2,1);
 873         newEdge(v3,v4).lock(v3,1);
 874         newEdge(v4,v1).lock(v4,1);
 875         setIn(true);
 876         return this;
 877     }
 878
 879     public void add(float x, float y) {
 880         Vertex vx = vertex(point(x,y));
 881         if (vx==last) return;
 882         if (start==null) start = vx;
 883         try {
 884             if (last==null) return;
 885             if (numvertices<3) return;
 886             if (numvertices==3) getEdge(start, last).lock(start,1);
 887             getEdge(last,vx).lock(last,1);
 888         } finally {
 889             last = vx;
 890         }
 891     }
 892
 893 }
 894
 895