src/edu/berkeley/qfat/Main.java

   1 package edu.berkeley.qfat;
   2 import java.awt.*;
   3 import java.awt.event.*;
   4 import javax.swing.*;
   5 import javax.media.opengl.*;
   6 import javax.media.opengl.glu.*;
   7 import java.util.*;
   8 import edu.berkeley.qfat.geom.*;
   9 import edu.berkeley.qfat.geom.Point;
  10 import edu.berkeley.qfat.geom.Polygon;
  11
  12 // TO DO:
  13 // - real anneal
  14 // - solve self-intersection problem
  15 // - get a better test model?
  16 // - symmetry constraints withing the tile
  17 // - rotation matrices
  18 // - overbinding results in forced equational constraints on the leader
  19 // - shatter in invertd-triforce pattern brian mentioned
  20 // - aspect ratio?  non-uniform deformation?
  21 // - rotational alignment
  22
  23 // - movie-style user interface like
  24 //      http://www.coleran.com/markcoleranreell.html ?
  25
  26 // - consider recasting the Shewchuk predicates in Java?
  27 //    http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c
  28
  29 /*
  30   blender keys
  31   - middle mouse = option+click
  32   - right mouse = command+click
  33
  34   3,7,1 = view along axes (control for opp direction)
  35   4, 8, 7, 2 = rotate in discrete increments (+control to translate)
  36   middle trag: rotate space
  37   shift+middle drag: translate space
  38   wheel: zoom
  39   home: home view: take current angle, zoom to whole scnee
  40   5 = ortho vs non-ortho
  41
  42 */
  43
  44 /*
  45
  46
  47  */
  48
  49
  50 // FIXME: re-orient goal (how?)
  51
  52 public class Main extends MeshViewer {
  53
  54     public static int verts = 1;
  55
  56     public static final Random random = new Random();
  57
  58     /** magnification factor */
  59     private static final float MAG = 1;
  60     public static final float MATCHING_EPSILON = 0.0001f;
  61
  62     public void generateTile(Matrix[] matrices, Mesh mesh) {
  63         HashSet<HalfSpace> halfSpaces = new HashSet<HalfSpace>();
  64         HashSet<Polygon> polygons = new HashSet<Polygon>();
  65         for(Matrix m : matrices) {
  66             Vec v = m.getTranslationalComponent();
  67             if (v.mag() < 0.0001) continue;
  68             v = v.times(0.5f);
  69             Point p = Point.ORIGIN.plus(v);
  70             HalfSpace hs = new HalfSpace(p, Point.ORIGIN.minus(p).norm());
  71             halfSpaces.add(hs);
  72             polygons.add(new Polygon(hs));
  73         }
  74         for(Polygon p : polygons) {
  75             System.out.println(p.plane.norm + " " + p.plane.dvalue);
  76             for(HalfSpace hs : halfSpaces) {
  77                 if (p.plane==hs) continue;
  78                 p = p.intersect(hs);
  79             }
  80             p.tesselate(mesh);
  81         }
  82     }
  83
  84     private void quad(Mesh mesh, Matrix m, Point p1_, Point p2_, Point p3_, Point p4_) {
  85         Point p1 = m.times(p1_);
  86         Point p2 = m.times(p2_);
  87         Point p3 = m.times(p3_);
  88         Point p4 = m.times(p4_);
  89         Point c  = new Point((p1.x+p2.x+p3.x+p4.x)/4,
  90                              (p1.y+p2.y+p3.y+p4.y)/4,
  91                              (p1.z+p2.z+p3.z+p4.z)/4);
  92         mesh.newT(p1, p2, c, null, 0);
  93         mesh.newT(p2, p3, c, null, 0);
  94         mesh.newT(p3, p4, c, null, 0);
  95         mesh.newT(p4, p1, c, null, 0);
  96     }
  97
  98     public Main(StlFile stlf, Frame f) {
  99         super(f);
 100
 101         for(int i=0; i<stlf.coordArray.length; i+=3) {
 102             Point p0 = new Point(stlf.coordArray[i+0].x * MAG, stlf.coordArray[i+0].y * MAG, stlf.coordArray[i+0].z * MAG);
 103             Point p1 = new Point(stlf.coordArray[i+1].x * MAG, stlf.coordArray[i+1].y * MAG, stlf.coordArray[i+1].z * MAG);
 104             Point p2 = new Point(stlf.coordArray[i+2].x * MAG, stlf.coordArray[i+2].y * MAG, stlf.coordArray[i+2].z * MAG);
 105             Vec n  = new Vec(stlf.normArray[i/3].x * MAG, stlf.normArray[i/3].y  * MAG, stlf.normArray[i/3].z * MAG);
 106             Mesh.T t  = goal.newT(p0, p1, p2, n, 0);
 107         }
 108
 109         // rotate to align major axis -- this probably needs to be done by a human.
 110         //goal.transform(Matrix.rotate(new Vec(0, 0, 1), (float)(Math.PI/2)));
 111         goal.transform(Matrix.rotate(new Vec(0, 1, 0), (float)(Math.PI/2)));
 112
 113         float goal_width  = goal.diagonal().dot(new Vec(1, 0, 0));
 114         float goal_height = goal.diagonal().dot(new Vec(0, 1, 0));
 115         float goal_depth  = goal.diagonal().dot(new Vec(0, 0, 1));
 116
 117         /*
 118           float width  = (float)0.6;
 119           float height = (float)0.08;
 120           float depth  = (float)0.3;
 121         */
 122
 123         float width  = (float)0.7;
 124         float depth  = (float)0.08;
 125         float height = (float)0.4;
 126
 127         float rshift =   width/2;
 128         float lshift = -(width/2);
 129
 130         //float halfup = height/2;
 131         float halfup = 0;
 132
 133         translations = new Matrix[] {
 134
 135             //Matrix.translate(new Vec(lshift,  depth,    0)),
 136             //Matrix.translate(new Vec(rshift,  depth,    0)),
 137             //Matrix.translate(new Vec(lshift, -depth,    0)),
 138             //Matrix.translate(new Vec(rshift, -depth,    0)),
 139
 140             //Matrix.translate(new Vec(0,  depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 141             //Matrix.translate(new Vec(0, -depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 142             //Matrix.translate(new Vec(0,   0,    height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 143             //Matrix.translate(new Vec(0,   0,   -height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 144
 145             Matrix.translate(new Vec(0,  depth, 0)),
 146             Matrix.translate(new Vec(0, -depth, 0)),
 147             Matrix.translate(new Vec(0,      0,  height)),
 148             Matrix.translate(new Vec(0,      0, -height)),
 149
 150             //Matrix.translate(new Vec(lshift,        depth,  height/2)),
 151             //Matrix.translate(new Vec(lshift,        depth, -height/2)),
 152             //Matrix.translate(new Vec(rshift,       -depth,  height/2)),
 153             //Matrix.translate(new Vec(rshift,       -depth, -height/2)),
 154             //Matrix.translate(new Vec(rshift,       0,  height)),
 155             //Matrix.translate(new Vec(rshift,       0, -height)),
 156
 157             Matrix.translate(new Vec( width,           0,    0)),
 158             Matrix.translate(new Vec(-width,           0,    0)),
 159
 160         };
 161
 162         generateTile(translations, tile);
 163
 164         /*
 165         translations = new Matrix[] {
 166
 167             //Matrix.translate(new Vec(lshift,  depth,    halfup)),
 168             //Matrix.translate(new Vec(rshift,  depth,    halfup)),
 169             //Matrix.translate(new Vec(lshift, -depth,    halfup)),
 170             //Matrix.translate(new Vec(rshift, -depth,    halfup)),
 171
 172
 173             //Matrix.translate(new Vec(0,  depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 174             //Matrix.translate(new Vec(0, -depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 175
 176             Matrix.translate(new Vec(0,   0,    height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 177             Matrix.translate(new Vec(0,   0,   -height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 178
 179             //Matrix.translate(new Vec(0,  depth, 0)),
 180             //Matrix.translate(new Vec(0, -depth, 0)),
 181             //Matrix.translate(new Vec(0,      0,  height)),
 182             //Matrix.translate(new Vec(0,      0, -height)),
 183
 184             //Matrix.translate(new Vec(lshift,        depth,  height/2)),
 185             //Matrix.translate(new Vec(lshift,        depth, -height/2)),
 186             //Matrix.translate(new Vec(rshift,       -depth,  height/2)),
 187             //Matrix.translate(new Vec(rshift,       -depth, -height/2)),
 188             //Matrix.translate(new Vec(rshift,       0,  height)),
 189             //Matrix.translate(new Vec(rshift,       0, -height)),
 190
 191             Matrix.translate(new Vec( width,           0,    0)),
 192             Matrix.translate(new Vec(-width,           0,    0)),
 193
 194         };
 195
 196         //
 197
 198
 199
 200         Point ltf = new Point(lshift,  (depth/2),  (height/2));
 201         Point mtf = new Point( 0.0,    (depth/2),  (height/2));
 202         Point rtf = new Point(rshift,  (depth/2),  (height/2));
 203         Point lbf = new Point(lshift, -(depth/2),  (height/2));
 204         Point mbf = new Point( 0.0,   -(depth/2),  (height/2));
 205         Point rbf = new Point(rshift, -(depth/2),  (height/2));
 206
 207         Point ltc = new Point(lshift,  (depth/2), 0);
 208         Point mtc = new Point( 0.0,    (depth/2), 0);
 209         Point rtc = new Point(rshift,  (depth/2), 0);
 210         Point lbc = new Point(lshift, -(depth/2), 0);
 211         Point mbc = new Point( 0.0,   -(depth/2), 0);
 212         Point rbc = new Point(rshift, -(depth/2), 0);
 213
 214         Point ltn = new Point(lshift,  (depth/2), -(height/2));
 215         Point mtn = new Point( 0.0,    (depth/2), -(height/2));
 216         Point rtn = new Point(rshift,  (depth/2), -(height/2));
 217         Point lbn = new Point(lshift, -(depth/2), -(height/2));
 218         Point mbn = new Point( 0.0,   -(depth/2), -(height/2));
 219         Point rbn = new Point(rshift, -(depth/2), -(height/2));
 220
 221
 222         Point[] points = new Point[] {
 223             ltf,
 224             mtf,
 225             rtf,
 226             lbf,
 227             mbf,
 228             rbf,
 229
 230             ltc,
 231             mtc,
 232             rtc,
 233             lbc,
 234             mbc,
 235             rbc,
 236
 237             ltn,
 238             mtn,
 239             rtn,
 240             lbn,
 241             mbn,
 242             rbn
 243         };
 244
 245
 246         // top
 247         tile.newT(ltf, mtf, mtc, null, 1);
 248         tile.newT(mtc, ltc, ltf, null, 1);
 249         tile.newT(mtf, rtf, rtc, null, 1);
 250         tile.newT(rtc, mtc, mtf, null, 1);
 251
 252         tile.newT(ltc, mtc, mtn, null, 1);
 253         tile.newT(mtn, ltn, ltc, null, 1);
 254         tile.newT(mtc, rtc, rtn, null, 1);
 255         tile.newT(rtn, mtn, mtc, null, 1);
 256
 257         // bottom (swap normals)
 258         tile.newT(mbf, lbf, mbc, null, 2);
 259         tile.newT(lbc, mbc, lbf, null, 2);
 260         tile.newT(rbf, mbf, rbc, null, 2);
 261         tile.newT(mbc, rbc, mbf, null, 2);
 262
 263         tile.newT(mbc, lbc, mbn, null, 2);
 264         tile.newT(lbn, mbn, lbc, null, 2);
 265
 266         tile.newT(rbc, mbc, rbn, null, 2);
 267         tile.newT(mbn, rbn, mbc, null, 2);
 268
 269
 270         // left
 271         tile.newT(ltf, ltc, lbc, null, 3);
 272         tile.newT(lbc, lbf, ltf, null, 3);
 273         tile.newT(ltc, ltn, lbn, null, 3);
 274         tile.newT(lbn, lbc, ltc, null, 3);
 275
 276         // right (swap normals)
 277         tile.newT(rtc, rtf, rbc, null, 4);
 278         tile.newT(rbf, rbc, rtf, null, 4);
 279         tile.newT(rtn, rtc, rbn, null, 4);
 280         tile.newT(rbc, rbn, rtc, null, 4);
 281
 282         // front
 283         tile.newT(ltn, mtn, mbn, null, 5);
 284         tile.newT(ltn, mbn, lbn, null, 5);
 285         tile.newT(mtn, rtn, rbn, null, 5);
 286         tile.newT(mtn, rbn, mbn, null, 5);
 287
 288         // back
 289         tile.newT(mtf, ltf, mbf, null, 6);
 290         tile.newT(mbf, ltf, lbf, null, 6);
 291         tile.newT(rtf, mtf, rbf, null, 6);
 292         tile.newT(rbf, mtf, mbf, null, 6);
 293
 294         HashSet<Mesh.E> es = new HashSet<Mesh.E>();
 295         for(Mesh.T t : tile) {
 296             es.add(t.e1());
 297             es.add(t.e2());
 298             es.add(t.e3());
 299         }
 300         for(Mesh.E e : es) {
 301             if (e.p1.p.x == e.p2.p.x && e.p1.p.y == e.p2.p.y) continue;
 302             if (e.p1.p.z == e.p2.p.z && e.p1.p.y == e.p2.p.y) continue;
 303             if (e.p1.p.x == e.p2.p.x && e.p1.p.z == e.p2.p.z) continue;
 304             e.shatter();
 305         }
 306         */
 307
 308         /*
 309          height = 4;
 310          width  = 4;
 311          depth  = 1;
 312
 313         Matrix mm = Matrix.scale(0.1f);
 314         // top
 315         quad(tile, mm,
 316              new Point( 2,  2,  0),
 317              new Point( 1,  1, -1),
 318              new Point(-1,  1, -1),
 319              new Point(-2,  2,  0));
 320         quad(tile, mm,
 321              new Point(-2,  2,  0),
 322              new Point(-1,  1,  1),
 323              new Point( 1,  1,  1),
 324              new Point( 2,  2,  0));
 325         quad(tile, mm,
 326              new Point( 1,  1, -1),
 327              new Point( 1,  1,  1),
 328              new Point(-1,  1,  1),
 329              new Point(-1,  1, -1));
 330
 331         // bottom
 332         quad(tile, mm,
 333              new Point(-2, -2,  0),
 334              new Point(-1, -1, -1),
 335              new Point( 1, -1, -1),
 336              new Point( 2, -2,  0));
 337         quad(tile, mm,
 338              new Point( 2, -2,  0),
 339              new Point( 1, -1,  1),
 340              new Point(-1, -1,  1),
 341              new Point(-2, -2,  0));
 342         quad(tile, mm,
 343              new Point(-1, -1, -1),
 344              new Point(-1, -1,  1),
 345              new Point( 1, -1,  1),
 346              new Point( 1, -1, -1));
 347
 348         // left
 349         quad(tile, mm,
 350              new Point( 2, -2,  0),
 351              new Point( 1, -1, -1),
 352              new Point( 1,  1, -1),
 353              new Point( 2,  2,  0));
 354         quad(tile, mm,
 355              new Point( 2,  2,  0),
 356              new Point( 1,  1,  1),
 357              new Point( 1, -1,  1),
 358              new Point( 2, -2,  0));
 359         quad(tile, mm,
 360              new Point( 1, -1, -1),
 361              new Point( 1, -1,  1),
 362              new Point( 1,  1,  1),
 363              new Point( 1,  1, -1));
 364
 365         // bottom
 366         quad(tile, mm,
 367              new Point(-2,  2,  0),
 368              new Point(-1,  1, -1),
 369              new Point(-1, -1, -1),
 370              new Point(-2, -2,  0));
 371         quad(tile, mm,
 372              new Point(-2, -2,  0),
 373              new Point(-1, -1,  1),
 374              new Point(-1,  1,  1),
 375              new Point(-2,  2,  0));
 376         quad(tile, mm,
 377              new Point(-1,  1, -1),
 378              new Point(-1,  1,  1),
 379              new Point(-1, -1,  1),
 380              new Point(-1, -1, -1));
 381
 382         float factor = (float)Math.pow(tile.volume() / goal.volume(), 1.0/3.0);
 383         goal.transform(Matrix.scale(factor/2.4f));
 384
 385         /*
 386         translations = new Matrix[] {
 387
 388             Matrix.translate(new Vec(0, 0.2f,0))
 389             .times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 390
 391             Matrix.translate(new Vec(0,-0.2f,0))
 392             .times(Matrix.rotate(new Vec(0,1,0), (float)(-1*Math.PI/2))),
 393
 394             //Matrix.translate(new Vec( 0.2f,0,0))
 395             //.times(Matrix.rotate(new Vec(1,0,0), (float)( 1*Math.PI/2))),
 396             //Matrix.translate(new Vec(-0.2f,0,0))
 397             //.times(Matrix.rotate(new Vec(1,0,0), (float)(-1*Math.PI/2))),
 398
 399             //Matrix.translate(new Vec( 0.2f, 0,0))
 400             //.times(Matrix.rotate(new Vec(0,0,1), (float)( 1*Math.PI/2)))
 401             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 3*Math.PI/2))),
 402
 403             //Matrix.translate(new Vec(-0.2f, 0,0))
 404             //.times(Matrix.rotate(new Vec(0,0,1), (float)( 3*Math.PI/2)))
 405             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 3*Math.PI/2))),
 406
 407             //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
 408             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 409             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 410             //Matrix.rotate(new Vec(0,0,1), (float)( 1*Math.PI/2))
 411             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 412             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 413
 414             //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
 415             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 416             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 417             //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
 418             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 419             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 420
 421             Matrix.ONE,
 422         };
 423         */
 424
 425         for(Matrix m1 : translations) {
 426         for(Matrix m2 : translations) {
 427             for(Mesh.T t1 : tile) {
 428                 for(Mesh.T t2 : tile) {
 429                     if (t1==t2) continue;
 430
 431                     Matrix m = m1.inverse().times(m2);
 432                     if ((t1.v1().p.times(m).minus(t2.v1().p).mag() < MATCHING_EPSILON) &&
 433                         (t1.v2().p.times(m).minus(t2.v3().p).mag() < MATCHING_EPSILON) &&
 434                         (t1.v3().p.times(m).minus(t2.v2().p).mag() < MATCHING_EPSILON)) {
 435                         t2.e3().bindEdge(t1.e1(), m);
 436                         t2.e2().bindEdge(t1.e2(), m);
 437                         t2.e1().bindEdge(t1.e3(), m);
 438                     }
 439                     if ((t1.v2().p.times(m).minus(t2.v1().p).mag() < MATCHING_EPSILON) &&
 440                         (t1.v3().p.times(m).minus(t2.v3().p).mag() < MATCHING_EPSILON) &&
 441                         (t1.v1().p.times(m).minus(t2.v2().p).mag() < MATCHING_EPSILON)) {
 442                         t2.e3().bindEdge(t1.e2(), m);
 443                         t2.e2().bindEdge(t1.e3(), m);
 444                         t2.e1().bindEdge(t1.e1(), m);
 445                     }
 446                     if ((t1.v3().p.times(m).minus(t2.v1().p).mag() < MATCHING_EPSILON) &&
 447                         (t1.v1().p.times(m).minus(t2.v3().p).mag() < MATCHING_EPSILON) &&
 448                         (t1.v2().p.times(m).minus(t2.v2().p).mag() < MATCHING_EPSILON)) {
 449                         t2.e3().bindEdge(t1.e3(), m);
 450                         t2.e2().bindEdge(t1.e1(), m);
 451                         t2.e1().bindEdge(t1.e2(), m);
 452                     }
 453
 454                 }
 455             }
 456         }
 457         }
 458
 459         //xMesh.Vertex mid = lbf.getE(mbn).shatter();
 460
 461         // rescale to match volume
 462
 463
 464
 465         // translate to match centroid
 466         goal.transform(Matrix.translate(tile.centroid().minus(goal.centroid())));
 467         goal.makeVerticesImmutable();
 468
 469         //tx.e2.shatter();
 470         //tx.e3.shatter();
 471
 472
 473         tile.rebindPoints();
 474
 475         //mid.move(new Vec((float)0,0,(float)-0.05));
 476         //ltn.move(new Vec((float)0,0,(float)-0.05));
 477
 478         //mtf.move(new Vec(0, (float)-0.05, (float)0.05));
 479
 480
 481         System.out.println("tile volume: " + tile.volume());
 482         System.out.println("goal volume: " + goal.volume());
 483
 484         tile.error_against = goal;
 485         goal.error_against = tile;
 486     }
 487
 488     public void breakit() {
 489         int oldverts = verts;
 490         System.out.println("doubling vertices.");
 491         PriorityQueue<Mesh.E> es = new PriorityQueue<Mesh.E>();
 492         for(Mesh.T t : tile) {
 493             es.add(t.e1());
 494             es.add(t.e2());
 495             es.add(t.e3());
 496             Thread.yield();
 497             repaint();
 498         }
 499         for(int i=0; i<Math.min(oldverts,50); i++) {
 500             Mesh.E e = es.poll();
 501             verts++;
 502             //System.out.println("shatter " + e);
 503             //e.shatter(e.midpoint(), null, null, true, true);
 504             e.shatter();
 505             Thread.yield();
 506             repaint();
 507         }
 508         tile.rebindPoints();
 509     }
 510
 511     public synchronized void rand(double temp, Mesh.Vertex p) {
 512
 513         p.reComputeErrorAround();
 514         double tile_error = tile.error();
 515         double goal_error = goal.error();
 516
 517         //float max = p.averageEdgeLength()/10;
 518         float max = 0.01f;
 519
 520         Vec v = new Vec(random.nextFloat(), random.nextFloat(), random.nextFloat());
 521         v = v.norm().times((random.nextFloat() - 0.5f) * max);
 522         //System.out.println(max + " " + p.averageEdgeLength() + " " + v.mag());
 523         Matrix m = Matrix.translate(v);
 524
 525         //System.out.println(v.mag() + " " + max);
 526         boolean good = p.move(m, false);
 527         //if (!good) { /*misses++;*/ return; }
 528
 529         double new_tile_error = tile.error();
 530         double new_goal_error = goal.error();
 531         double tile_delta = (new_tile_error - tile_error) / tile_error;
 532         double goal_delta = (new_goal_error - goal_error) / goal_error;
 533         double delta = tile_delta + goal_delta;
 534         double swapProbability = Math.exp((-1 * delta) / temp);
 535         //System.out.println(swapProbability);
 536         boolean doSwap = good && (Math.random() < swapProbability);
 537         //boolean doSwap = good && (tile_delta <= 0 && goal_delta <= 0);
 538         //boolean doSwap = good && (tile_delta + goal_delta <= 0);
 539
 540         //if (temp < 0.000001) doSwap = good && (tile_delta <= 0 && goal_delta <= 0);
 541
 542         if (doSwap) {
 543             tile_error = new_tile_error;
 544             goal_error = new_goal_error;
 545             //System.out.println("error: " + tile_error + " / " + goal_error);
 546             hits++;
 547             p.goodp = p.p;
 548         } else {
 549             p.move(Matrix.translate(v.times(-1)), true);
 550             misses++;
 551         }
 552     }
 553
 554     float hits = 0;
 555     float misses = 0;
 556     public void anneal() throws Exception {
 557         double hightemp = 1;
 558         double temp = hightemp;
 559         double last = 10;
 560         boolean seek_upward = false;
 561         double acceptance = 1;
 562         while(true) {
 563             synchronized(this) {
 564                 double ratio = (hits+misses==0) ? 1 : (hits / (hits+misses));
 565                 hits = 0;
 566                 misses = 0;
 567                 double gamma = 1;
 568                 acceptance = (ratio+acceptance)/2;
 569                 accepts = (int)(Math.ceil(ratio*100));
 570                 temps = (int)(Math.ceil(temp*1000));
 571                 vertss = tile.size();
 572                 if (breaks > 0) {
 573                     while (breaks>0) {
 574                         breaks--;
 575                         breakit();
 576                     }
 577                     seek_upward = true;
 578                 } else if (acceptance > 0.96) gamma = 0.1f;
 579                 else if (acceptance > 0.9)    gamma = 0.2f;
 580                 else if (acceptance > 0.8)    gamma = 0.3f;
 581                 else if (acceptance > 0.6)    gamma = 0.4f;
 582                 else if (acceptance > 0.3)    gamma = 0.6f;
 583                 else if (acceptance > 0.15)   gamma = 0.9f;
 584                 else if (acceptance > 0.05)   gamma = 0.94f;
 585                 else if (acceptance > 0.01)   gamma = 0.98f;
 586                 else { /*breaks++;*/ }
 587
 588                 /*
 589                 if (seek_upward) {
 590                     if (acceptance > 0.2) seek_upward = false;
 591                     else gamma = 2-gamma;
 592                 }
 593                 */
 594
 595                 if (anneal)
 596                     temp = temp * gamma;
 597
 598
 599                 HashSet<Mesh.Vertex> hs = new HashSet<Mesh.Vertex>();
 600                 for(Mesh.Vertex p : tile.vertices()) hs.add(p);
 601                 Mesh.Vertex[] pts = (Mesh.Vertex[])hs.toArray(new Mesh.Vertex[0]);
 602
 603                 int count = 0;
 604                 long then = System.currentTimeMillis();
 605                 for(int i=0; i<400; i++) {
 606                     if (anneal) {
 607                         count++;
 608                         Mesh.Vertex v = pts[Math.abs(random.nextInt()) % pts.length];
 609                         rand(temp,v);
 610                         v.recomputeFundamentalQuadricIfStale();
 611                         v.recomputeFundamentalQuadricIfNeighborChanged();
 612                     }
 613                     Thread.yield();
 614                     repaint();
 615                 }
 616
 617                 /*
 618                 PriorityQueue<Mesh.E> es = new PriorityQueue<Mesh.E>();
 619                 for(Mesh.T t : tile) {
 620                     float max = 5;
 621                     for(Mesh.E e : new Mesh.E[] { t.e1(), t.e2(), t.e3() }) {
 622                         if (e==null) continue;
 623                         if (e.stretchRatio() > max) es.add(e);
 624                         if (t.aspect() < 0.1 && e.length()>e.next.length() && e.length()>e.prev.length()) es.add(e);
 625                     }
 626                 }
 627                 for(int i=0; i<5; i++) {
 628                     Mesh.E e = es.poll();
 629                     if (e==null) break;
 630                     e.shatter();
 631                 }
 632
 633
 634                 tile.rebindPoints();
 635                 */
 636
 637
 638                 System.out.println("temp="+temp + " ratio="+(Math.ceil(acceptance*100)) + " " +
 639                                    "points_per_second=" +
 640                                    (count*1000)/((double)(System.currentTimeMillis()-then)));
 641                 for(Mesh.Vertex p : goal.vertices()) p.recomputeFundamentalQuadricIfNeighborChanged();
 642
 643                 synchronized(safeTriangles) {
 644                     safeTriangles.clear();
 645                     for(Mesh.T t : tile)
 646                         //if (t.shouldBeDrawn())
 647                             safeTriangles.add(t);
 648                 }
 649             }
 650         }
 651     }
 652
 653
 654     public static void main(String[] s) throws Exception {
 655         StlFile stlf = new StlFile();
 656         stlf.load("torus.stl");
 657         //stlf.load("fish.stl");
 658         //stlf.load("monkey.stl");
 659         Frame f = new Frame();
 660         Main main = new Main(stlf, f);
 661         f.pack();
 662         f.show();
 663         f.setSize(900, 900);
 664         f.doLayout();
 665         main.anneal();
 666     }
 667
 668 }