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