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 p, Affine a) { return point(p.x(a), p.y(a)); }
 233     private class Point {
 234         public float x;
 235         public float y;
 236         public String toString() { return "("+x+","+y+")"; }
 237         public Point multiply(Affine a) { return point(x(a),y(a)); }
 238         public Point(float x, float y) { this.x = x; this.y = y; }
 239         public Point(Point p) { this(p.x,p.y); }
 240         public boolean equals(float x, float y) { return distance(x,y) <= epsilon; }
 241         public boolean equals(Object o) { return (!(o instanceof Point)) ? false : ((Point)o).distance(this) <= epsilon; }
 242         public float distance(Point v) { return distance(v.x,v.y); }
 243         private float distance(float x, float y) { return (float)Math.sqrt(distance2(x, y)); }
 244         public float distance2(Point v) { return distance2(v.x, v.y); }
 245         private float distance2(float x, float y) { return (this.x-x)*(this.x-x)+(this.y-y)*(this.y-y); }
 246         public float x(Affine a) { return a.multiply_px(x,y); }
 247         public float y(Affine a) { return a.multiply_py(x,y); }
 248         public int xi(Affine a) { return (int)x(a); }
 249         public int yi(Affine a) { return (int)y(a); }
 250         public boolean intersects(Point p1, Point p2) {
 251             return
 252                 Mesh.side(p1,p2,this)==0 &&
 253                 x <= Math.max(p1.x,p2.x) &&
 254                 x >= Math.min(p1.x,p2.x) &&
 255                 y <= Math.max(p1.y,p2.y) &&
 256                 y >= Math.min(p1.y,p2.y);
 257         }
 258     }
 259
 260     private final class Vertex extends Point implements org.ibex.arenaj.Gladiator {
 261         public Vertex(Point p) { super(p); numvertices++; }
 262     }
 263
 264     // Edge //////////////////////////////////////////////////////////////////////////////
 265
 266     public Edge newEdge(Vertex v1, Vertex v2) {
 267         return getEdge(v1,v2);
 268         /*
 269         if (v1==v2) throw new Error();
 270         Edge ret = (Edge)edges.get(v1,v2);
 271         //if (ret != null) throw new Error("tried to get an edge that already exists!");
 272         if (ret == null) ret = new Edge(v1,v2);
 273         return ret;
 274     }
 275
 276     public Edge getEdge(Vertex v1, Vertex v2) {
 277         if (v1==v2) throw new Error();
 278         Edge ret = (Edge)edges.get(v1,v2);
 279         if (ret == null) ret = new Edge(v1,v2);
 280         return ret;
 281     }
 282
 283     private final class Edge implements org.ibex.arenaj.Gladiator {
 284         private final Vertex v1;
 285         private final Vertex v2;
 286         Triangle t1 = null;
 287         Triangle t2 = null;
 288
 289         private int locks = 0;
 290         private int weight = 0;
 291
 292         public void delete() {
 293             if (t1!=null || t2!=null) throw new Error("tried to remove an edge before its triangles");
 294             edges.put(v1,v2,null);
 295             edges.put(v2,v1,null);
 296         }
 297
 298         public Vertex v(int i) { return i==1?v1:i==2?v2:null; }
 299
 300         public Edge rotate(Vertex v, boolean clockwise) {
 301             Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null;
 302             if (t==null) return null;
 303             for(int i=1; i<=3; i++) if (t.e(i)!=this && t.e(i).hasVertex(v)) return t.e(i);
 304             return null;
 305         }
 306         public Edge rotateHull(boolean clockwise) {
 307             if (t1!=null && t2!=null) throw new Error("nextHull() called on non-hull edge");
 308             Vertex v = rotate(v1, !clockwise) == null ? v2 : v1;
 309             Edge e = rotate(v, !clockwise);
 310             while(!e.hasTriangle(null) && e!=this) e = e.rotate(v, !clockwise);
 311             if (e==this) throw new Error("confused");
 312             return e;
 313         }
 314
 315         public boolean isNear(Point p) { return area(v1,v2,p) < epsilon2; }
 316         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; }
 317         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; }
 318         public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; }
 319         public int weight() { return weight; }
 320         public int weight(Vertex v) { return v==v1?weight:(-1*weight); }
 321         public boolean locked() { return locks > 0; }
 322         public boolean partitions(Point va, Point vb) { return side(va,vb)==-1; }
 323         public int     side(Point a, Point b) { return side(a) * side(b); }
 324         public int     side(Point a)          { return Mesh.side(v(1), v(2), a); }
 325         public boolean hasVertex(Vertex v) { return v1==v || v2==v; }
 326         public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; }
 327         public String toString() { return v(1) + "--" + v(2); }
 328         public void rmTriangle(Triangle t) {
 329             if (t1==t) t1 = null;
 330             else if (t2==t) t2 = null;
 331             else throw new Error();
 332             if (t1==null && t2==null) delete();
 333         }
 334         public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); }
 335
 336         public boolean colinear(Point v) { return area(v,v1,v2)<=epsilon; }
 337
 338         public boolean intersects(Point p) {
 339             return
 340                 side(p)==0 &&
 341                 p.x <= Math.max(v1.x,v2.x) &&
 342                 p.x >= Math.min(v1.x,v2.x) &&
 343                 p.y <= Math.max(v1.y,v2.y) &&
 344                 p.y >= Math.min(v1.y,v2.y);
 345         }
 346         public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); }
 347         public boolean intersects(Point va, Point vb) {
 348             return
 349                 !v1.equals(va) &&
 350                 !v1.equals(vb) &&
 351                 !v2.equals(va) &&
 352                 !v2.equals(vb) &&
 353                 partitions(va, vb) &&
 354                 Mesh.side(va, vb, v1) * Mesh.side(va, vb, v2) == -1;
 355         }
 356         public Triangle opposingTriangle(Triangle t) {
 357             if (t1 == t) return t2;
 358             if (t2 == t) return t1;
 359             throw new Error();
 360         }
 361         public void addTriangle(Triangle tnew) {
 362             if (t1==null) t1 = tnew;
 363             else if (t2==null) t2 = tnew;
 364             else throw new Error("attempted to addTriangle("+tnew+")\n  t1="+t1+"\n  t2="+t2);
 365             if (t1==t2) throw new Error("same triangle can't be both sides of an edge");
 366             if (v1.x==v2.x) {
 367                 boolean b  = side(t1.opposingVertex(this)) == side(point(Float.MAX_VALUE, v1.y));
 368                 Triangle right = b ? t1 : t2;       // right side
 369                 Triangle left  = b ? t2 : t1;       // left side
 370                 t1 = right;
 371                 t2 = left;
 372             } else {
 373                 boolean b       = side(t1.opposingVertex(this)) == side(point(0, Float.MAX_VALUE));
 374                 Triangle top    = b ? t1 : t2;
 375                 Triangle bottom = b ? t2 : t1;
 376                 if (v1.y==v2.y) {                         // horizontal
 377                     t1 = bottom;
 378                     t2 = top;
 379                 } else if (v1.x > v2.x) {                 // positive slope
 380                     t1 = top;
 381                     t2 = bottom;
 382                 } else {                                  // negative slope
 383                     t1 = bottom;
 384                     t2 = top;
 385                 }
 386             }
 387         }
 388         public void bisect(Vertex v) {
 389             Edge e = this;
 390             Triangle t1 = this.t1==null?this.t2:this.t1;
 391             Triangle t  = t1==this.t1?this.t2:this.t1;
 392             Vertex opposing = t1.opposingVertex(e);
 393             Triangle top = null, ton = null;
 394             Vertex left = e.v(1);
 395             Vertex right = e.v(2);
 396             Vertex tov = null;
 397             boolean in1 = t1.in;
 398             boolean in2 = false;
 399             Triangle opposingTriangleLeft = t1.opposingTriangle(left);
 400             Triangle opposingTriangleRight = t1.opposingTriangle(right);
 401             Edge right_v = newEdge(right, v);
 402             Edge left_v = newEdge(left, v);
 403             Edge opposing_v = newEdge(opposing, v);
 404             Edge tov_v = null;
 405             Edge right_tov = null;
 406             Edge left_tov = null;
 407             Edge right_opposing = t1.opposingEdge(left);
 408             Edge left_opposing = t1.opposingEdge(right);
 409             if (t != null) {
 410                 t.check();
 411                 right_tov = t.opposingEdge(left);
 412                 left_tov = t.opposingEdge(right);
 413                 top = t.opposingTriangle(left);
 414                 ton = t.opposingTriangle(right);
 415                 tov = t.opposingVertex(t1);
 416                 in2 = t.in;
 417                 tov_v = newEdge(tov, v);
 418                 if (top == t1) top = null;
 419                 if (ton == t1) ton = null;
 420                 if (opposingTriangleLeft == t) opposingTriangleLeft = null;
 421                 if (opposingTriangleRight == t) opposingTriangleRight = null;
 422                 t.delete();
 423             }
 424             t1.delete();
 425             Triangle ta, tb, tc, td;
 426             ta = triangle(right_opposing, opposing_v, right_v);
 427             tb = triangle(left_opposing, opposing_v, left_v);
 428             ta.in = in1;
 429             tb.in = in1;
 430             if (t != null) {
 431                 tc = triangle(left_tov, tov_v, left_v);
 432                 td = triangle(right_tov, tov_v, right_v);
 433                 tc.in = in2;
 434                 td.in = in2;
 435             }
 436             if (locked()) fracture(v);
 437             else ta.fixup();
 438         }
 439         public Edge flip() {
 440             if (locked()) throw new Error("attempted to remove a locked edge: " + this);
 441             boolean in = t1.in && t2.in;
 442
 443             Edge e3   = rotate(v1, true);
 444             Vertex vb = e3.unCommonVertex(this);
 445             Edge e6   = e3.rotate(vb, true);
 446
 447             Edge e4   = rotate(v2, true);
 448             Vertex va = e4.unCommonVertex(this);
 449             Edge e1   = e4.rotate(va, true);
 450
 451             Edge e    = newEdge(va, vb);
 452
 453             t1.delete();
 454             t2.delete();
 455             Triangle ta, tb;
 456             ta = triangle(e1, e, e3);
 457             tb = triangle(e4, e, e6);
 458             ta.in = in;
 459             tb.in = in;
 460             return ta.getSharedEdge(tb);
 461         }
 462         public void fracture(Vertex vx) {
 463             if (!locked()) throw new Error("attempt to fracture an edge which does not exist: " + v1 + " " + v2);
 464             // delete-me
 465             Edge v1vx = newEdge(v1, vx);
 466             Edge vxv2 = newEdge(vx, v2);
 467             v1vx.locks += locks;
 468             vxv2.locks += locks;
 469             locks = 0;
 470             v1vx.weight += v(1)==v1vx.v(1) ? weight : (-1 * weight);
 471             vxv2.weight += v(2)==vxv2.v(2) ? weight : (-1 * weight);
 472             weight = 0;
 473             v1vx.lock();
 474             vxv2.lock();
 475         }
 476         public void fracture(Edge e) {
 477             triangle0=e.t1==null?e.t2:e.t1;
 478             Vertex v0 = vertex(Mesh.this.intersect(v1,v2,e.v(1),e.v(2)));
 479             if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0);
 480             if (v0 != v1 && v0 != v2) fracture(v0);
 481         }
 482         public void lock(Vertex v1, int delta) {
 483             weight += this.v(1)==v1 ? delta : (-1 * delta);
 484             locks += 1;
 485             lock();
 486         }
 487         public void lock() {
 488             Triangle t = t1==null ? t2 : t1;
 489             if (t==null) t = triangle0.seek(v1);
 490             if (!t.hasVertex(v1)) throw new Error("this sucks balls");
 491             boolean skipfo = false;
 492             for(Triangle told = null; t != told; t = told==null ? t : t.followVector(v1,v2)) {
 493                 told = t;
 494                 if (!t.encounters(v1,v2)) break;
 495                 if (!t.encounters(v2,v1)) break;
 496                 Triangle tlast = t.followVector(v2,v1);
 497                 if (tlast == null) throw new Error("seek from: " + tlast + "\n  " + v1 + " -> " + v2);
 498                 if (tlast == t) { if (t.hasVertex(v1)) continue; throw new Error("no predecessor"); }
 499                 Edge e = t.getSharedEdge(tlast);
 500                 if (!e.convex()) continue;
 501                 if (e.v(1)==v1 || e.v(1)==v2 || e.v(2)==v1 || e.v(2)==v2) { continue; }
 502                 if (this.intersects(e.v(1))) { fracture(e.v(1)); return; }
 503                 if (this.intersects(e.v(2))) { fracture(e.v(2)); return; }
 504                 if (!this.intersects(e)) continue;
 505                 if (e.locked()) {
 506                     fracture(e);
 507                     return;
 508                 } else {
 509                     Edge eold = e = e.flip();
 510                     t = e.t1;
 511                     if (t==null || !t.intersects(this)) t = e.t2;
 512                     told = t;
 513                     if (eold.intersects(this)) {
 514                         t = t.followVector(v1,v2);
 515                         if (t != e.t1 && t != e.t2) t = told;
 516                         continue;
 517                     } else {
 518                         told = null;
 519                         while(t.intersects(this)) {
 520                             if (t==told) break;
 521                             told = t;
 522                             t = t.followVector(v2,v1);
 523                         }
 524                         t = told;
 525                         told = null;
 526                         continue;
 527                     }
 528                 }
 529             }
 530             if (t1!=null) t1.fixup();
 531             if (t2!=null) t2.fixup();
 532         }
 533
 534         public void stroke(PixelBuffer buf, Affine a, int color) {
 535             int c = debug
 536                 ? (weight() == 0 ? color : 0xffff0000)
 537                 : (weight() != 0 ? color : 0);
 538             if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c);
 539         }
 540         public Edge(Vertex v1, Vertex v2) {
 541             boolean b = v1.y < v2.y || (v1.y==v2.y && v1.x < v2.x);
 542             this.v1 = b ? v1 : v2;
 543             this.v2 = b ? v2 : v1;
 544             edges.put(v1, v2, this);
 545             edges.put(v2, v1, this);
 546         }
 547     }
 548
 549     // Triangle //////////////////////////////////////////////////////////////////////////////
 550
 551     public Triangle triangle(Edge e1, Edge e2, Edge e3) {
 552         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;
 553         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;
 554         Point p = point(x,y);
 555         Triangle t = triangle0==null ? null : triangle0.seek(p);
 556         if (t != null &&
 557             (t.contains(p) || t.intersects(p)) &&
 558             t.hasEdge(e1) &&
 559             t.hasEdge(e2) &&
 560             t.hasEdge(e3))
 561             return triangle0 = t;
 562         t = new Triangle(e1, e2, e3);
 563         if (debug) t.check();
 564         if (triangle0 == null) triangle0 = t;
 565         return t;
 566     }
 567
 568         public static boolean fixing = false;
 569     private final class Triangle implements org.ibex.arenaj.Gladiator {
 570
 571         final float r2;
 572         final Point cc;
 573
 574         private Edge e1, e2, e3;    // should be final =(
 575         public int tick;
 576
 577         boolean in = false;
 578         boolean inWasSet = false;
 579         boolean painted = false;
 580         boolean dirty = true;
 581
 582         public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; }
 583         public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); }
 584         public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; }
 585
 586         public boolean encounters(Point p1, Point p2) {
 587             for(int i=1; i<=3; i++) {
 588                 if (v(i).equals(p1)) return true;
 589                 if (v(i).equals(p2)) return true;
 590                 if (v(i).intersects(p1,p2)) return true;
 591                 if (e(i).intersects(p1,p2)) return true;
 592             }
 593             return contains(p1) || contains(p2);
 594         }
 595         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; }
 596         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; }
 597         public Point c()  { return point(cx(),cy()); }
 598         public float cx() { return (float)(((double)v(1).x+(double)v(2).x+(double)v(3).x)/3); }
 599         public float cy() { return (float)(((double)v(1).y+(double)v(2).y+(double)v(3).y)/3); }
 600         public boolean intersects(Vertex va, Vertex vb){return e(1).intersects(va,vb)||e(2).intersects(va,vb)||e(3).intersects(va,vb);}
 601         public boolean intersects(Edge e){ return intersects(e.v(1),e.v(2)); }
 602         public boolean intersects(Point p){ return e(1).intersects(p) || e(2).intersects(p) || e(3).intersects(p); }
 603         public boolean hasEdge(Edge e) { return e.t1==this || e.t2==this; }
 604         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)); }
 605         public boolean hasVertex(Vertex a) { return a==v(1) || a==v(2) || a==v(3); }
 606         public Vertex opposingVertex(Triangle t) { return t(3)==t ? v(3) : t(1)==t ? v(1) : t(2)==t ? v(2) : null; }
 607         public Vertex opposingVertex(Edge e) { return e==e(1) ? v(1) : e==e(2) ? v(2) : e==e(3) ? v(3) : null; }
 608         public Edge   opposingEdge(Vertex v) { return v==v(1) ? e(1) : v==v(2) ? e(2) : v==v(3) ? e(3) : null; }
 609         public Triangle opposingTriangle(Vertex v) { return v(1)==v ? t(1) : v(2)==v ? t(2) : v(3)==v ? t(3) : null; }
 610         public String toString() { return "<<"+v(1)+""+v(2)+""+v(3)+">>"; }
 611
 612         public void stroke(PixelBuffer buf, Affine a, int color) {
 613             for(int i=1; i<=3; i++) if (in || debug) e(i).stroke(buf, a, color);
 614         }
 615         public Triangle fixup() {
 616             if (!dirty) return this;
 617             dirty = false;
 618             for(int i=1; i<=3; i++) {
 619                 Triangle t = t(i);
 620                 if (t==null) continue;
 621                 if (t.r2 <= v(i).distance2(t.cc)) continue;
 622                 Edge e = e(i);
 623                 if (e.locked()) { t.fixup(); continue; }
 624                 return e.flip().t1.fixup();
 625             }
 626             return this;
 627         }
 628         public void addHull(Vertex vnew) {
 629             Edge e = e(1).hasTriangle(null) ? e(1) : e(2).hasTriangle(null) ? e(2) : e(3).hasTriangle(null) ? e(3) : null;
 630             Triangle t = e.opposingTriangle(null), newt = null;
 631             while (!e.partitions(vnew, t.opposingVertex(e))) {
 632                 e = e.rotateHull(true);
 633                 t = e.opposingTriangle(null);
 634             }
 635             Edge ea = newEdge(e.v(1), vnew);
 636             Edge eb = newEdge(e.v(2), vnew);
 637             newt = triangle(e, ea, eb);
 638             if (ea.rotateHull(true) != eb) { Edge temp = ea; ea = eb; eb = temp; }
 639             for(int i=1; i<=2; i++)
 640                 for(Edge ex = i==1?eb:ea; ;) {
 641                     e = ex.rotateHull(i==1);
 642                     t = e.opposingTriangle(null);
 643                     if (!e.partitions(vnew, t.opposingVertex(e))) break;
 644                     Edge ep = newEdge(vnew, e.unCommonVertex(ex));
 645                     newt = triangle(e, ex, ep);
 646                     ex = ep;
 647                 }
 648             if (newt==null) throw new Error("couldn't find a place to add a triangle for " + vnew);
 649             newt.fixup();
 650         }
 651         public Triangle seek(Point p) {
 652             Triangle t = this;
 653             try {
 654             while (true) {
 655                 if      (t.contains(p) || t.intersects(p))  return t;
 656                 else if (t.e(3).intersects(p))                return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t;
 657                 else if (t.e(1).intersects(p))                return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t;
 658                 else if (t.e(2).intersects(p))                return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t;
 659                 else {
 660                     Triangle t2 = t.followVector(t.c(), p);
 661                     if (t2==null || t2==t) return t;
 662                     t = t2;
 663                 }
 664             }
 665             } finally { if (t!=null) triangle0 = t; }
 666         }
 667
 668         // gives the triangle across the edge through which the ray v(1)-->v(2) exits this triangle
 669         public Triangle followVector(Point p1, Point p2) {
 670             Triangle ret = followVector2(p1, p2);
 671             if (ret==null) return ret;
 672             triangle0 = ret;
 673             if (!ret.encounters(p1,p2)) return this;
 674             return ret;
 675         }
 676         public Triangle followVector2(Point p1, Point p2) {
 677             if (contains(p2) || intersects(p2) || v(1).equals(p2) || v(2).equals(p2) || v(3).equals(p2)) return this;
 678             for(int i=1; i<=3; i++) if (!v(i).equals(p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2);
 679             Triangle t1 = t(1);
 680             Triangle t2 = t(2);
 681             Triangle t3 = t(3);
 682             for(int i=1; i<=3; i++) {
 683                 int k1 = i==1?3:i==2?1:i==3?2:0;
 684                 int k2 = i==1?2:i==2?3:i==3?1:0;
 685                 int k3 = i==1?1:i==2?2:i==3?3:0;
 686                 if (v(i).equals(p1)) {
 687                     if (e(k1).partitions(v(k1),p2)) return t(k1);
 688                     if (e(k2).partitions(v(k2),p2)) return t(k2);
 689                     if (e(k3).partitions(v(k3),p2)) return t(k3);
 690                     throw new Error("bad!");
 691                 }
 692             }
 693             if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2))
 694                 throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" +
 695                                 "  p1=" + p1 + "\n" +
 696                                 "  p2=" + p2 + "\n" +
 697                                 "  t =" + this + " (area "+area(v(1),v(2),v(3))+")\n");
 698             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);
 699             throw new Error("giving up: \n  "+p1+" -> "+p2+"\n  " + this);
 700         }
 701
 702         public void check() {
 703             if (debug) {
 704                 for(int i=1; i<=3; i++) {
 705                     if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent");
 706                     if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent");
 707                     if (e(i).t1 == e(i).t2) throw new Error("same triangle on both sides of edge");
 708                 }
 709                 if (e(1)==e(2) || e(2)==e(3) || e(3)==e(1)) throw new Error("identical edges");
 710                 for(int i=1; i<=3; i++) {
 711                     if (t(i) != null) if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)");
 712                     if (t(i) != null) {
 713                         if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark");
 714                         if (!e(i).hasTriangle(t(i))) throw new Error("blark2");
 715                         if (!e(i).hasTriangle(this)) throw new Error("blark3");
 716                     }
 717                 }
 718                 // check that edges all join up
 719             }
 720         }
 721
 722         public void trisect(Vertex v) {
 723             if (!contains(v)) throw new Error("trisect(v) but I don't contain v = " + v);
 724             if (hasVertex(v)) throw new Error("attempt to trisect a triangle at one of its own vertices");
 725             for(int i=3; i>0; i--) if (e(i).isNear(v)) { e(i).bisect(v); return; }
 726             Triangle a=null,b=null,c=null;
 727
 728             boolean oldIn = in;
 729             Edge v1v = newEdge(v(1), v);
 730             Edge v2v = newEdge(v(2), v);
 731             Edge v3v = newEdge(v(3), v);
 732             Edge e1 = this.e(1);
 733             Edge e2 = this.e(2);
 734             Edge e3 = this.e(3);
 735             delete();
 736
 737             a = triangle(e3, v1v, v2v);
 738             b = triangle(e2, v1v, v3v);
 739             c = triangle(e1, v3v, v2v);
 740             a.in = oldIn;
 741             b.in = oldIn;
 742             c.in = oldIn;
 743             a.fixup();
 744         }
 745
 746         public void setIn(boolean evenOdd, int weight) {
 747             if (inWasSet) return;
 748             inWasSet = true;
 749             in = (evenOdd && weight%2!=0) || (!evenOdd && weight!=0);
 750             for(int i=1; i<=3; i++) if (t(i) != null) t(i).setIn(evenOdd, weight + e(i).weight());
 751         }
 752
 753         public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
 754             if (painted) return;
 755             painted = true;
 756             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);
 757             for(int i=1; i<=3; i++)
 758                 if (t(i) != null) {
 759                     boolean prepaint = t(i).painted;
 760                     if (debug) e(i).stroke(buf, a, color);
 761                     t(i).fill(buf, a, clip, color, strokeOnly);
 762                 }
 763         }
 764
 765         public Triangle(Edge e1, Edge e2, Edge e3) {
 766             this.e1 = e1;
 767             this.e2 = e2;
 768             this.e3 = e3;
 769             Vertex v1 = e(2).unCommonVertex(e(1));
 770             Vertex v2 = e(3).unCommonVertex(e(2));
 771             Vertex v3 = e(1).unCommonVertex(e(3));
 772             if (e(1).intersects(v1)) throw new Error("triangle points are colinear");
 773             if (e(2).intersects(v2)) throw new Error("triangle points are colinear");
 774             if (e(3).intersects(v3)) throw new Error("triangle points are colinear");
 775             e(1).addTriangle(this);
 776             e(2).addTriangle(this);
 777             e(3).addTriangle(this);
 778
 779             float a = 0;
 780             Q: for(int q=0; q<2; q++) {
 781                 for(int i=0; i<3; i++) {
 782                     if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q;
 783                     Vertex t = v2; v2=v3; v3=v1; v1 = t;
 784                 }
 785                 Vertex t = v2; v2=v3; v3=t;
 786             }
 787             if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
 788             float a1=(v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
 789             float a2=(v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
 790             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);
 791             r2 = v1.distance2(cc);
 792             triangles.add(this);
 793         }
 794         public void clear() {
 795             if (!painted) return;
 796             painted = false;
 797             if (t(3) != null) t(3).clear();
 798             if (t(1) != null) t(1).clear();
 799             if (t(2) != null) t(2).clear();
 800         }
 801         public void delete() {
 802             if (triangle0 == this) {
 803                 if (t(1) != null) triangle0 = t(1);
 804                 else if (t(2) != null) triangle0 = t(2);
 805                 else if (t(3) != null) triangle0 = t(3);
 806                 else triangle0 = null;
 807             }
 808             triangles.remove(this);
 809             e(1).rmTriangle(this);
 810             e(2).rmTriangle(this);
 811             e(3).rmTriangle(this);
 812             e1 = null;
 813             e2 = null;
 814             e3 = null;
 815         }
 816     }
 817
 818     // Queries /////////////////////////////////////////////////////////////////////////////////
 819
 820     public boolean queryPoint(Point p) {
 821         if (triangle0==null) return false;
 822         Triangle ret = triangle0.seek(p);
 823         return (ret.contains(p) || ret.intersects(p)) && ret.in;
 824     }
 825
 826
 827     // Drawing //////////////////////////////////////////////////////////////////////////////
 828
 829     public void setIn(boolean evenOdd) {
 830         iterateTriangles(ITERATE_CLEAR_WASSET, null, null);
 831         triangle0.setIn(evenOdd, 1);
 832     }
 833
 834     public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
 835         if (triangle0==null) return;
 836         iterateTriangles(ITERATE_CLEAR, null, null);
 837         triangle0.fill(buf, a, clip, color, strokeOnly);
 838     }
 839
 840     public void stroke(PixelBuffer buf, Affine a, int color) {
 841         if (triangle0==null) return;
 842         iterateTriangles(ITERATE_STROKE, null, a, buf, color);
 843     }
 844
 845     public void newcontour() {
 846         if (start != null) add(start.x, start.y);
 847         start = null;
 848         last = null;
 849     }
 850
 851     public Mesh addRect(float x, float y, float w, float h) {
 852         if (w==0 || h==0) return this;
 853         Vertex v1 = vertex(point(x,y));
 854         Vertex v2 = vertex(point(x+w,y));
 855         Vertex v3 = vertex(point(x+w,y+h));
 856         Vertex v4 = vertex(point(x,y+h));
 857         newEdge(v1,v2).lock(v1,1);
 858         newEdge(v2,v3).lock(v2,1);
 859         newEdge(v3,v4).lock(v3,1);
 860         newEdge(v4,v1).lock(v4,1);
 861         setIn(true);
 862         return this;
 863     }
 864
 865     public void add(float x, float y) {
 866         Vertex vx = vertex(point(x,y));
 867         if (vx==last) return;
 868         if (start==null) start = vx;
 869         try {
 870             if (last==null) return;
 871             if (numvertices<3) return;
 872             if (numvertices==3) getEdge(start, last).lock(start,1);
 873             getEdge(last,vx).lock(last,1);
 874         } finally {
 875             last = vx;
 876         }
 877     }
 878
 879 }
 880
 881