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 /**
  11  *  An incremental, adaptive, constrained Delaunay Triangulation.
  12  *  @see Kallmann, Bieri, and Thalmann: Fully Dynamic Constrained Delaunay Triangulations
  13  */
  14 public final class Mesh {
  15
  16     //#define Vertex int
  17
  18     private static final float epsilon = (float)0.001;
  19     private static final boolean debug = false;
  20
  21     private              Vector triangles = new Vector();
  22
  23     public static float B = (float)5.0;
  24     public static float Q = (float)0.4;
  25
  26     public static Hashtable nexter = new Hashtable();
  27     public static LinkedList next(Vertex v) {
  28         LinkedList hs = (LinkedList)nexter.get(new Integer(v));
  29         if (hs == null) nexter.put(new Integer(v), hs = new LinkedList());
  30         return hs;
  31     }
  32
  33     // Vertices //////////////////////////////////////////////////////////////////////////////
  34
  35     public Vertex v(float x, float y) {
  36         if (numvertices >= this.x.length-1) {
  37             if (debug) Log.debug(Mesh.class, "expanding vertex arrays from " + this.x.length + " to " + this.x.length*2);
  38             float[] newx = new float[this.x.length * 2];
  39             float[] newy = new float[this.y.length * 2];
  40             System.arraycopy(this.x, 0, newx, 0, this.x.length);
  41             System.arraycopy(this.y, 0, newy, 0, this.y.length);
  42             this.x = newx;
  43             this.y = newy;
  44         }
  45         this.x[numvertices] = x;
  46         this.y[numvertices] = y;
  47         return numvertices++;
  48     }
  49     public int numvertices = 0;
  50     public float x[] = new float[255];
  51     public float y[] = new float[255];
  52     public String s(Vertex v) { return "("+x(v)+","+y(v)+")"; }
  53     public float  x(Vertex v) { return x[v]; }
  54     public float  y(Vertex v) { return y[v]; }
  55
  56     public static final Vertex NULLVERTEX = -1;
  57
  58     public Vertex newVertex(float x, float y) {
  59         Vertex ret = NULLVERTEX;
  60         for(int k=0; k<numvertices; k++) {
  61             Vertex v = k;
  62             if (distance(v,x,y)<epsilon) if (ret==NULLVERTEX || distance(v,x,y) < distance(ret,x,y)) ret = v;
  63         }
  64         if (ret != NULLVERTEX) return ret;
  65         Vector vec = new Vector();
  66         boolean interior = false;
  67         int edges = 0;
  68         Vertex v = v(x,y);
  69         if (numvertices<=2) return v;
  70         if (numvertices==3) { newTriangle(0, 1, 2, "first three points"); return v; }
  71         for(int i=0; i<triangles.size(); i++) {
  72             Triangle t = (Triangle)triangles.elementAt(i);
  73             if (t.contains(v)) {
  74                 Triangle t12 = t.t12;
  75                 Triangle t23 = t.t23;
  76                 Triangle t31 = t.t31;
  77                 t.delete();
  78                 vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
  79                 vec.addElement(newTriangle(v, t.v3, t.v2, "vertexinsertion " + v));
  80                 vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
  81                 //#repeat t23/t31/t12 v1/v2/v3 v2/v3/v1 v3/v1/v2
  82             } else if (t.t23 != null && isect(t.v2, t.v3, v)) {
  83                 Triangle tt = t.t23;
  84                 Vertex va = tt.opposingVertex(t);
  85                 tt.delete();
  86                 t.delete();
  87                 vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
  88                 vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
  89                 vec.addElement(newTriangle(v, t.v3, va  , "vertexinsertion " + v));
  90                 vec.addElement(newTriangle(v, t.v2, va  , "vertexinsertion " + v));
  91                 //#end
  92             } else {
  93                 continue;
  94             }
  95             fixup(vec, v);
  96             return v;
  97         }
  98         boolean good = false;
  99         while(true) {
 100             for(int j=0; j<triangles.size(); j++) {
 101                 Triangle t = (Triangle)triangles.elementAt(j);
 102                 if (t.v1==v || t.v2==v || t.v3==v) continue;
 103                 //#repeat t12/t23/t31 v3/v1/v2 v2/v3/v1 v1/v2/v3
 104                 if (t.t12==null) {
 105                     boolean bad = false;
 106                     for(int k=0; k<triangles.size(); k++) {
 107                         Triangle tt = (Triangle)triangles.elementAt(k);
 108                         if (tt.intersectsSegment(v, t.v1)) { bad = true; break; }
 109                         if (tt.intersectsSegment(v, t.v2)) { bad = true; break; }
 110                     }
 111                     if (!bad) {
 112                         vec.addElement(newTriangle(v,t.v1,t.v2, "hull expansion"));
 113                         good = true;
 114                     }
 115                 }
 116                 //#end
 117             }
 118             break;
 119         }
 120         if (!good) throw new Error("couldn't figure out where to put " + s(v));
 121         fixup(vec, v);
 122         return v;
 123     }
 124
 125     public void fixup(Vector vec, Vertex v) {
 126         while(vec.size() > 0) {
 127             Triangle t = (Triangle)vec.lastElement();
 128             vec.setSize(vec.size() - 1);
 129             if (t.deleted) continue;
 130             //if (t.wind(t.nextVertex(v), t.prevVertex(v)) != 0) continue;    // FIXME
 131             Triangle to = t.opposingTriangle(v);
 132             if (to==null)  continue; //throw new Error("fixup invoked with a triangle which does not have me as a vertex");
 133             if (to.deleted) throw new Error("v should not happen");
 134             if (to.r < distance(v,to.ccx, to.ccy)) continue;
 135             Vertex v2 = to.opposingVertex(t);
 136             t.delete();
 137             to.delete();
 138             vec.addElement(newTriangle(v, t.nextVertex(v), v2, "fixup"));
 139             vec.addElement(newTriangle(v, t.prevVertex(v), v2, "fixup"));
 140         }
 141     }
 142
 143     // Static //////////////////////////////////////////////////////////////////////////////
 144
 145     public Triangle newTriangle(Vertex v1, Vertex v2, Vertex v3, String source) {
 146         if (v1==v2 || v2==v3 || v3==v1) throw new Error("identical vertices");
 147         for(int i=0; i<triangles.size(); i++) {
 148             Triangle t = (Triangle)triangles.elementAt(i);
 149             if (t.v1==v1&&t.v2==v2&&t.v3==v3) return t;
 150             if (t.v1==v1&&t.v2==v3&&t.v3==v2) return t;
 151             if (t.v1==v2&&t.v2==v3&&t.v3==v1) return t;
 152             if (t.v1==v2&&t.v2==v1&&t.v3==v3) return t;
 153             if (t.v1==v3&&t.v2==v1&&t.v3==v2) return t;
 154             if (t.v1==v3&&t.v2==v2&&t.v3==v1) return t;
 155         }
 156         Triangle t = new Triangle(source, v1, v2, v3, false, false);
 157         if (debug) checktri();
 158         return t;
 159     }
 160
 161     public void checktri() {
 162         for(int i=0; i<triangles.size(); i++) {
 163             Triangle t = (Triangle)triangles.elementAt(i);
 164             if (t.t12 != null && (t.t12.t12 != t && t.t12.t23 != t && t.t12.t31 != t)) throw new Error("t12");
 165             if (t.t23 != null && (t.t23.t12 != t && t.t23.t23 != t && t.t23.t31 != t)) throw new Error("t23");
 166             if (t.t31 != null && (t.t31.t12 != t && t.t31.t23 != t && t.t31.t31 != t)) throw new Error("t31");
 167             for(int j=0; j<triangles.size(); j++) {
 168                 Triangle t2 = (Triangle)triangles.elementAt(j);
 169                 if (t2==t) continue;
 170                 if (t.v1==t2.v1&&t.v2==t2.v2&&t.v3==t2.v3) throw new Error("poo");
 171                 if (t.v1==t2.v1&&t.v2==t2.v3&&t.v3==t2.v2) throw new Error("poo");
 172                 if (t.v1==t2.v2&&t.v2==t2.v3&&t.v3==t2.v1) throw new Error("poo");
 173                 if (t.v1==t2.v2&&t.v2==t2.v1&&t.v3==t2.v3) throw new Error("poo");
 174                 if (t.v1==t2.v3&&t.v2==t2.v1&&t.v3==t2.v2) throw new Error("poo");
 175                 if (t.v1==t2.v3&&t.v2==t2.v2&&t.v3==t2.v1) throw new Error("poo");
 176             }
 177         }
 178     }
 179
 180     // Vertex //////////////////////////////////////////////////////////////////////////////
 181
 182         public boolean triangulate(Vertex vv, HashSet orphans, Vertex v, boolean first) {
 183             if (first) {
 184                 HashSet left = new HashSet();
 185                 HashSet right = new HashSet();
 186                 for(Iterator it=orphans.iterator(); it.hasNext();) {
 187                     Vertex o = ((Integer)it.next()).intValue();
 188                     if (o==v||o==vv) continue;
 189                     if (side(vv, v, o) == -1) left.add(new Integer(o));
 190                     else if (side(vv, v, o) == 1) right.add(new Integer(o));
 191                     else throw new Error("impossible "+vv+" "+v + " " + o);
 192                 }
 193                 triangulate(vv, left, v, false);
 194                 triangulate(v, right, vv, false);
 195                 return false;
 196             }
 197             Vertex farthest = NULLVERTEX;
 198             float dist = 0;
 199             if (orphans.size()==0) return true;
 200             Vertex o = ((Integer)orphans.iterator().next()).intValue();
 201             if (orphans.size()==1) {
 202                 Triangle t = newTriangle(vv, v, o, "triangulate2 " + v + " " + vv);
 203                 if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
 204                 if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
 205                 if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
 206                 return false;
 207             }
 208
 209             Vertex best = NULLVERTEX;
 210             OUTER: for(Iterator it=orphans.iterator(); it.hasNext();) {
 211                 o = ((Integer)it.next()).intValue();
 212                 if (o==v) continue;
 213                 Triangle t = new Triangle("temp", vv, v, o, true);
 214                 for(Iterator it2=orphans.iterator(); it2.hasNext();) {
 215                     Vertex z = ((Integer)it2.next()).intValue();
 216                     if (z==o) continue;
 217                     if (z==v) continue;
 218                     if (z==vv) continue;
 219                     if (distance(z,t.ccx,t.ccy) < t.r || t.contains(z)) continue OUTER;
 220                 }
 221                 if (best==NULLVERTEX || new Triangle("temp",vv,v,best,true).area() > new Triangle("temp",vv,v,o,true).area())
 222                     best = o;
 223             }
 224             if (best==NULLVERTEX) throw new Error("notgood, #orphans = " + orphans.size());
 225             o = best;
 226             HashSet left = new HashSet();
 227             HashSet right = new HashSet();
 228             for(Iterator it2=orphans.iterator(); it2.hasNext();) {
 229                 Vertex x = ((Integer)it2.next()).intValue();
 230                 if (o==x||vv==x||v==x) continue;
 231                 int side_of_x    = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,x);
 232                 int side_of_v    = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,v);
 233                 int side_of_vv = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,vv);
 234                 if (side_of_x==side_of_vv && side_of_vv!=0) right.add(new Integer(x));
 235                 else if (side_of_x==side_of_v && side_of_v!=0) left.add(new Integer(x));
 236                 else throw new Error("impossible "+vv+" "+v + " " + o + " ==> " + x);
 237             }
 238             boolean doit = true;
 239             doit &= triangulate(o, left, v, false);
 240             doit &= triangulate(o, right, vv, false);
 241             if (doit) {
 242                 Triangle t = newTriangle(v, vv, o,"triangulate 0/0");
 243                 if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
 244                 if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
 245                 if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
 246                 return false;
 247             }
 248             return true;
 249         }
 250
 251     public void force() {
 252         while(true) {
 253             boolean redo = false;
 254             for(int k=0; k<numvertices; k++) {
 255                 Vertex v = k;
 256                 redo |= force(v);
 257             }
 258             if (!redo) break;
 259         }
 260     }
 261     public boolean force(Vertex vv) {
 262         boolean ret = false;
 263         OUTER: for(Iterator it=next(vv).iterator(); it.hasNext();) {
 264             Vertex v = ((Integer)it.next()).intValue();
 265             for(int k=0; k<numvertices; k++) {
 266                 Vertex v2 = k;
 267                 if (v2==vv||v2==v) continue;
 268                 //if (next(vv).contains(v2) || next(v2).contains(vv)) continue;
 269                 if (isect(v,vv,v2)) {
 270                     if (debug) Log.debug(Mesh.class,"breaking line " + vv+"-"+v + " at vertex " + v2);
 271                     next(vv).remove(new Integer(v));
 272                     next(vv).add(new Integer(v2));
 273                     next(v2).add(new Integer(v));
 274                     ret = true;
 275                     break OUTER;
 276                 }
 277             }
 278             boolean good = false;
 279             for (int i=0; i<triangles.size(); i++)
 280                 if (((Triangle)triangles.elementAt(i)).hasEdge(vv,v)) { good = true; break; }
 281             if (good) continue;
 282             HashSet orphans = new HashSet();
 283             for (int i=0; i<triangles.size(); i++) {
 284                 Triangle t = ((Triangle)triangles.elementAt(i));
 285                 if (t.deleted) continue;
 286                 if (t.intersectsSegment(vv, v)) {
 287                     if (debug) Log.debug(Mesh.class,"removing triangle " + t + " because it intersects segment " + vv+"-"+v);
 288                     Vector vec = new Vector();
 289                     orphans.add(new Integer(t.v1));
 290                     orphans.add(new Integer(t.v2));
 291                     orphans.add(new Integer(t.v3));
 292                     orphans.remove(new Integer(v));
 293                     orphans.remove(new Integer(vv));
 294                     t.delete();
 295                     i--;
 296                     ret = true;
 297                 }
 298             }
 299             orphans.remove(new Integer(vv));
 300             orphans.remove(new Integer(v));
 301             triangulate(vv, orphans, v, true);
 302             break;
 303         }
 304         return ret;
 305     }
 306
 307     public void makeNonDegenerate() {
 308         while(true) {
 309             boolean redo = false;
 310             for(int k=0; k<numvertices; k++) {
 311                 Vector vec = new Vector();
 312                 Vertex vx = k;
 313                 redo |= makeNonDegenerate(vec, vx);
 314             }
 315             if (!redo) break;
 316         }
 317     }
 318     public boolean makeNonDegenerate(Vector vec, Vertex v1) {
 319         for(int i2 = 0; i2<next(v1).size(); i2++) {
 320             Vertex v2 = ((Integer)next(v1).get(i2)).intValue();
 321             for(int i3 = 0; i3<numvertices; i3++) {
 322                 Vertex v3 = i3;
 323                 for(int i4=0; i4<next(v3).size(); i4++) {
 324                     Vertex v4 = ((Integer)next(v3).get(i4)).intValue();
 325                     if (v1==v3||v1==v4||v2==v3||v2==v4) continue;
 326                     if (isect(v1,v2,v3,v4)) {
 327                         float a1 = y(v2)-y(v1);
 328                         float a2 = y(v4)-y(v3);
 329                         float b1 = x(v1)-x(v2);
 330                         float b2 = x(v3)-x(v4);
 331                         float c1 = -1 * (a1*x(v1)+b1*y(v1));
 332                         float c2 = -1 * (a2*x(v3)+b2*y(v3));
 333                         // a1x+b1y+c1=0
 334                         // y=-(a1x+c1)/b1
 335                         // a2x-(a1x+c1)(b2/b1)+c2=0
 336                         // a2b1x-b2(a1x+c1)+b1c2=0
 337                         // a2b1x-a1b2x-b2c1+b1c2=0
 338                         // x(a2b1-a1b2)-b2c1+b1c2=0
 339                         // x(a2b1-a1b2)=b2c1-b1c2
 340                         // x=(b2c1-b1c2)/(a2b1-a1b2)
 341                         float xq = (b2*c1-c2*b1)/(b1*a2-b2*a1);
 342                         Vertex v0 = newVertex(xq, -1 * (a1*xq+c1) / b1);
 343                         //if (v0==v1||v0==v2||v0==v3||v0==v4) continue;
 344                         if (debug) Log.debug(this,"inserting new vertex " + v0+" between " + v1+"-"+v2 +" and "+ v3+"-"+v4);
 345                         next(v1).remove(new Integer(v2));
 346                         next(v1).add(new Integer(v0));
 347                         next(v0).add(new Integer(v2));
 348                         next(v3).remove(new Integer(v4));
 349                         next(v3).add(new Integer(v0));
 350                         next(v0).add(new Integer(v4));
 351                         return true;
 352                     }
 353                 }
 354             }
 355         }
 356         return false;
 357     }
 358
 359     // Triangle //////////////////////////////////////////////////////////////////////////////
 360
 361     private final class Triangle {
 362         Triangle t12=null, t23=null, t31=null;
 363         final Vertex v1, v2, v3;
 364         boolean in = false;
 365         boolean deleted = false;
 366         boolean painted = false;
 367         boolean special = false;
 368         final String source;
 369         final float ccx, ccy, r;
 370
 371         public boolean hasEdge(Vertex a, Vertex b) { return a!=b && (a==v1||a==v2||a==v3) && (b==v1||b==v2||b==v3); }
 372         public Vertex opposingVertex(Triangle t) { return t12==t ? v3 : t23==t ? v1 : t31==t ? v2 : NULLVERTEX; }
 373         public Triangle opposingTriangle(Vertex v) { return v1==v ? t23 : v2==v ? t31 : v3==v ? t12 : null; }
 374         public Vertex nextVertex(Vertex v) { return v1==v ? v2 : v2==v ? v3 : v3==v ? v1 : NULLVERTEX; }
 375         public Vertex prevVertex(Vertex v) { return v1==v ? v3 : v2==v ? v1 : v3==v ? v2 : NULLVERTEX; }
 376         public String toString() { return "<<"+v1+""+v2+""+v3+">>"; }
 377         public boolean intersectsSegment(Vertex a, Vertex b) { return isect(v1,v2,a,b) || isect(v3,v2,a,b) || isect(v1,v3,a,b); }
 378         public float area() {
 379             float a = distance(v1,v2);
 380             float b = distance(v2,v3);
 381             float c = distance(v3,v1);
 382             float s = (a+b+c)/2;
 383             return (float)Math.sqrt(s*(s-a)*(s-b)*(s-c));
 384         }
 385
 386         public boolean checkSkinny() {
 387             if (!(r / Math.min(Math.min(distance(v1,v2), distance(v2,v3)), distance(v3,v1)) > B)) return false;
 388             if (debug) Log.debug(this,"skinny triangle " + this);
 389             for (Vertex v=0; v<numvertices; v++) {
 390                 for (Iterator nit = next(v).iterator(); nit.hasNext();) {
 391                     Vertex v2 = ((Integer)nit.next()).intValue();
 392                     float midx = (x(v)+x(v2))/2;
 393                     float midy = (y(v)+y(v2))/2;
 394                     if (distance(midx,midy,ccx,ccy) <= distance(v,midx,midy)) {
 395                         if (debug) Log.debug(this,"  but splitting it would encroach on a segment");
 396                         return false;
 397                     }
 398                 }
 399             }
 400             newVertex(ccx, ccy);
 401             return true;
 402         }
 403
 404         public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, int count, boolean strokeOnly) {
 405             if (painted) return;
 406             if (deleted) throw new Error("gargh!");
 407             if (!strokeOnly) {
 408                 if (special) {
 409                     buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
 410                                      (int)a.multiply_py((float)x(v1), (float)y(v1)),
 411                                      (int)a.multiply_px((float)x(v2), (float)y(v2)),
 412                                      (int)a.multiply_py((float)x(v2), (float)y(v2)),
 413                                      (int)a.multiply_px((float)x(v3), (float)y(v3)),
 414                                      (int)a.multiply_py((float)x(v3), (float)y(v3)),
 415                                      0xff0000ff);
 416                 } else if ((evenOdd && count%2!=0) || (!evenOdd && count!=0)) {
 417                     buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
 418                                      (int)a.multiply_py((float)x(v1), (float)y(v1)),
 419                                      (int)a.multiply_px((float)x(v2), (float)y(v2)),
 420                                      (int)a.multiply_py((float)x(v2), (float)y(v2)),
 421                                      (int)a.multiply_px((float)x(v3), (float)y(v3)),
 422                                      (int)a.multiply_py((float)x(v3), (float)y(v3)),
 423                                      color);
 424                 } else {
 425                     if (debug)
 426                         buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
 427                                          (int)a.multiply_py((float)x(v1), (float)y(v1)),
 428                                          (int)a.multiply_px((float)x(v2), (float)y(v2)),
 429                                          (int)a.multiply_py((float)x(v2), (float)y(v2)),
 430                                          (int)a.multiply_px((float)x(v3), (float)y(v3)),
 431                                          (int)a.multiply_py((float)x(v3), (float)y(v3)),
 432                                          0xff000000 | ((color & 0x00ffffff) >> 8));
 433                 }
 434             }
 435             painted = true;
 436             //#repeat t12/t23/t31 v1/v2/v3 v2/v3/v1
 437             if (t12 != null && !t12.painted) {
 438                 t12.fill(buf, a, color, evenOdd, count + wind(v1, v2), strokeOnly);
 439                 if (debug)
 440                     drawLine(buf, (x(v1)*2+x(v2))/3, (y(v1)*2+y(v2))/3, (x(v1)+2*x(v2))/3, (y(v1)+2*y(v2))/3, a,
 441                              wind(v2,v1)==0?0xff000000:0xff0000ff);
 442             }
 443             //#end
 444         }
 445         public int wind(Vertex a, Vertex b) {
 446             if (next(a).contains(new Integer(b)) && next(b).contains(new Integer(a))) return 0;
 447             if (y(a) < y(b) || (y(a)==y(b) && x(a)<x(b))) return wind(b, a);
 448             if (next(a).contains(new Integer(b))) return 1;
 449             if (next(b).contains(new Integer(a))) return -1;
 450             return 0;
 451         }
 452         public void clear() {
 453             if (!painted) return;
 454             painted = false;
 455             if (t12 != null) t12.clear();
 456             if (t23 != null) t23.clear();
 457             if (t31 != null) t31.clear();
 458         }
 459         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3) { this(source, v1, v2, v3, false, false); }
 460         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake) { this(source, v1,v2,v3,fake,false); }
 461         public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake, boolean ignoreProblems) {
 462             this.source = source;
 463             float a = 0;
 464             for(int i=0; i<3; i++) {
 465                 a=(y(v2)-y(v3))*(x(v2)-x(v1))-(y(v2)-y(v1))*(x(v2)-x(v3));
 466                 if (a!=0) break;
 467                 Vertex t = v2; v2=v3; v3=v1; v1 = t;
 468             }
 469             if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
 470             this.v1 = v1; this.v2 = v2; this.v3 = v3;
 471             float a1=(x(v1)+x(v2))*(x(v2)-x(v1))+(y(v2)-y(v1))*(y(v1)+y(v2));
 472             float a2=(x(v2)+x(v3))*(x(v2)-x(v3))+(y(v2)-y(v3))*(y(v2)+y(v3));
 473             ccx=(a1*(y(v2)-y(v3))-a2*(y(v2)-y(v1)))/a/2;
 474             ccy=(a2*(x(v2)-x(v1))-a1*(x(v2)-x(v3)))/a/2;
 475             r = distance(v1,ccx, ccy);
 476             if (fake) return;
 477             for(int i=0; i<triangles.size(); i++) {
 478                 Triangle t = (Triangle)triangles.elementAt(i);
 479                 if ((t.v1==v1&&t.v2==v2)||(t.v1==v2&&t.v2==v1)) { if (t.t12!=null) throw new Error(); t.t12=this; t12=t; }
 480                 if ((t.v1==v2&&t.v2==v3)||(t.v1==v3&&t.v2==v2)) { if (t.t12!=null) throw new Error(); t.t12=this; t23=t; }
 481                 if ((t.v1==v3&&t.v2==v1)||(t.v1==v1&&t.v2==v3)) { if (t.t12!=null) throw new Error(); t.t12=this; t31=t; }
 482                 if ((t.v2==v1&&t.v3==v2)||(t.v2==v2&&t.v3==v1)) { if (t.t23!=null) throw new Error(); t.t23=this; t12=t; }
 483                 if ((t.v2==v2&&t.v3==v3)||(t.v2==v3&&t.v3==v2)) { if (t.t23!=null) throw new Error(); t.t23=this; t23=t; }
 484                 if ((t.v2==v3&&t.v3==v1)||(t.v2==v1&&t.v3==v3)) { if (t.t23!=null) throw new Error(); t.t23=this; t31=t; }
 485                 if ((t.v3==v1&&t.v1==v2)||(t.v3==v2&&t.v1==v1)) { if (t.t31!=null) throw new Error(); t.t31=this; t12=t; }
 486                 if ((t.v3==v2&&t.v1==v3)||(t.v3==v3&&t.v1==v2)) { if (t.t31!=null) throw new Error(); t.t31=this; t23=t; }
 487                 if ((t.v3==v3&&t.v1==v1)||(t.v3==v1&&t.v1==v3)) { if (t.t31!=null) throw new Error(); t.t31=this; t31=t; }
 488             }
 489             triangles.add(this);
 490         }
 491         public void delete() {
 492             if (deleted) return;
 493             deleted = true;
 494             triangles.remove(this);
 495             if (t12 != null) { if (t12.t12==this) t12.t12=null; if (t12.t23==this) t12.t23=null; if (t12.t31==this) t12.t31=null; }
 496             if (t23 != null) { if (t23.t12==this) t23.t12=null; if (t23.t23==this) t23.t23=null; if (t23.t31==this) t23.t31=null; }
 497             if (t31 != null) { if (t31.t12==this) t31.t12=null; if (t31.t23==this) t31.t23=null; if (t31.t31==this) t31.t31=null; }
 498         }
 499         public boolean contains(Vertex v) {
 500             float x = x(v);
 501             float y = y(v);
 502             if (v==v1) return false;
 503             if (v==v2) return false;
 504             if (v==v3) return false;
 505             if (isect(v1,v2,v)) return false;
 506             if (isect(v2,v3,v)) return false;
 507             if (isect(v3,v1,v)) return false;
 508             return (side(v1,v2,x,y)==side(v1,v2,v3)) && (side(v3,v2,x,y)==side(v3,v2,v1)) && (side(v1,v3,x,y)==side(v1,v3,v2));
 509         }
 510     }
 511
 512     // Constructor //////////////////////////////////////////////////////////////////////////////
 513
 514     public Mesh(Polygon p) {
 515         p.sort();
 516         triangles.setSize(0);
 517         for(int i=0; i<p.numcontours-1; i++) {
 518             Vertex last = NULLVERTEX, first = NULLVERTEX;
 519             boolean good = false;
 520             for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
 521                 Vertex v = newVertex(p.x[j], p.y[j]);
 522                 if (v==last) continue;
 523                 if (v==first) continue;
 524                 if (last == NULLVERTEX) { last = v; continue; }
 525                 if (first == NULLVERTEX) { first = v; continue; }
 526                 good = true;
 527                 break;
 528             }
 529             if (debug) Log.debug(this,"contour " + i + " is " + (good?"good":"bad"));
 530             if (!good) continue;
 531             last = NULLVERTEX; first = NULLVERTEX;
 532             for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
 533                 Vertex v = newVertex(p.x[j], p.y[j]);
 534                 if (v==last) continue;
 535                 if (first==NULLVERTEX) first=v;
 536                 if (last != NULLVERTEX) next(last).add(new Integer(v));
 537                 last = v;
 538                 makeNonDegenerate();
 539                 force();
 540             }
 541             if (last!=first) next(last).add(new Integer(first));
 542         }
 543         makeNonDegenerate();
 544         force();
 545         /*
 546         redo = true;
 547         for(; redo;) {
 548             redo = false;
 549             for(int k=0; k<triangles.size(); k++) {
 550                 Triangle t = (Triangle)triangles.elementAt(k);
 551                 redo |= t.checkSkinny();
 552             }
 553             break;
 554         }
 555         System.out.println("I now have " + numvertices + " vertices");
 556         */
 557
 558     }
 559
 560     // Drawing //////////////////////////////////////////////////////////////////////////////
 561
 562     private void drawLine(PixelBuffer buf, float x1, float y1, float x2, float y2, Affine a, int color) {
 563         buf.drawLine((int)a.multiply_px(x1, y1), (int)a.multiply_py(x1, y1),
 564                      (int)a.multiply_px(x2, y2), (int)a.multiply_py(x2, y2),
 565                      color);
 566     }
 567     public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, boolean strokeOnly) {
 568         for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).clear();
 569         ((Triangle)triangles.elementAt(0)).fill(buf, a, color, evenOdd, 1, strokeOnly);
 570     }
 571
 572     public void stroke(PixelBuffer buf, Affine a, int color) {
 573         if (debug)
 574             for (int i=0; i<numvertices; i++) {
 575                 Vertex v = i;
 576                 for(Iterator it = next(v).iterator(); it.hasNext();) {
 577                     Vertex v2 = ((Integer)it.next()).intValue();
 578                     drawLine(buf, x(v), y(v), x(v2), y(v2), a, 0xffff0000);
 579                 }
 580             }
 581         for (int i=0; i<triangles.size(); i++) {
 582             Triangle t = ((Triangle)triangles.elementAt(i));
 583             Vertex v1 = t.v1;
 584             Vertex v2 = t.v2;
 585             Vertex v3 = t.v3;
 586             if (debug||t.wind(v1,v2)!=0) drawLine(buf,x(v1),y(v1),x(v2),y(v2),a,(debug && t.wind(v1,v2)!=0) ?0xffffffff:color);
 587             if (debug||t.wind(v3,v2)!=0) drawLine(buf,x(v3),y(v3),x(v2),y(v2),a,(debug && t.wind(v3,v2)!=0) ?0xffffffff:color);
 588             if (debug||t.wind(v1,v3)!=0) drawLine(buf,x(v1),y(v1),x(v3),y(v3),a,(debug && t.wind(v1,v3)!=0) ?0xffffffff:color);
 589         }
 590     }
 591
 592     // Geometric Utility Functions //////////////////////////////////////////////////////////////////////////////
 593
 594     public float distance(Vertex v1, Vertex v2) { return distance(x(v1), y(v1), x(v2), y(v2)); }
 595     public float distance(Vertex v1, float x, float y) { return distance(x(v1),y(v1),x,y); }
 596     public float distance(float x1,float y1,float x2,float y2) {return (float)Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
 597     public int side(Vertex v1, Vertex v2, Vertex v3) { return side(v1, v2, x(v3), y(v3)); }
 598     public int side(Vertex v1, Vertex v2, float x, float y) { return side(v1, x(v2), y(v2), x, y); }
 599     public int side(Vertex v1, float x, float y, Vertex v3) { return side(v1, x, y, x(v3), y(v3)); }
 600     public int side(Vertex v1, float x, float y, float x2, float y2) {
 601         float a = y-y(v1), b = x(v1)-x, c = -1 * (a*x(v1)+b*y(v1));
 602         return (- (a*x2+c)/b > y2) ? -1 : (- (a*x2+c)/b < y2) ? 1 : 0;
 603     }
 604
 605     public boolean isect(Vertex v1, Vertex v2, Vertex v3, Vertex v4) {
 606         if (v1==v3 || v1==v4 || v2==v3 || v2==v4) return false;
 607         float a = side(v1,v2,v3);
 608         float b = side(v1,v2,v4);
 609         float c = side(v3,v4,v1);
 610         float d = side(v3,v4,v2);
 611         return a!=b && c!=d && a!=0 && b!=0 && c!=0 && d!=0;
 612     }
 613
 614     public boolean isect(Vertex v1, Vertex v2, Vertex v) {
 615         return
 616             side(v1,v2,v)==0 &&
 617             x(v) - Math.max(x(v1),x(v2)) < 0 &&
 618             x(v) - Math.min(x(v1),x(v2)) > 0 &&
 619             y(v) - Math.max(y(v1),y(v2)) < 0 &&
 620             y(v) - Math.min(y(v1),y(v2)) > 0;
 621     }
 622
 623
 624 }
 625
 626