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.001f;
  61
  62     private static boolean small(float f) { return Math.abs(f) < 0.001; }
  63     public void generateTile(Matrix[] matrices, Mesh mesh) {
  64         mesh.coalesce = true;
  65         HashSet<HalfSpace> halfSpaces = new HashSet<HalfSpace>();
  66         HashSet<Polygon> polygons = new HashSet<Polygon>();
  67         for(Matrix m : matrices) {
  68             Vec v = m.getTranslationalComponent();
  69             if (v.mag() < 0.0001) continue;
  70             v = v.times(0.5f);
  71             Point p = Point.ORIGIN.plus(v);
  72             Vec v0 = v;
  73             /*
  74             if      (small(v.x) && small(v.y)) v = new Vec(0,0,1);
  75             else if (small(v.y) && small(v.z)) v = new Vec(1,0,0);
  76             else if (small(v.z) && small(v.x)) v = new Vec(0,1,0);
  77             else if (small(v.x))               v = new Vec(0,v.y,0).minus(new Vec(0,0,v.z)).cross(new Vec(1,0,0));
  78             else if (small(v.y))               v = new Vec(0,0,v.z).minus(new Vec(v.x,0,0)).cross(new Vec(0,1,0));
  79             else if (small(v.z))               v = new Vec(v.x,0,0).minus(new Vec(0,v.y,0)).cross(new Vec(0,0,1));
  80             else {
  81                 Point v1 = new Point(v.x, 0,   0);
  82                 Point v2 = new Point(0,   v.y, 0);
  83                 Point v3 = new Point(0,   0,   v.z);
  84                 v = v3.minus(v2).cross(v1.minus(v2));
  85             }
  86             */
  87             if (v.dot(Point.ORIGIN.minus(p)) < 0) v = v.times(-1);
  88
  89             System.out.println(v);
  90             HalfSpace hs = new HalfSpace(p, v.norm());
  91             halfSpaces.add(hs);
  92             polygons.add(new Polygon(hs));
  93         }
  94         for(Polygon p : polygons) {
  95             System.out.println(p.plane.norm + " " + p.plane.dvalue);
  96             for(HalfSpace hs : halfSpaces) {
  97                 if (p.plane==hs) continue;
  98                 p = p.intersect(hs);
  99             }
 100             p.tesselate(mesh);
 101         }
 102     }
 103
 104     private void quad(Mesh mesh, Matrix m, Point p1_, Point p2_, Point p3_, Point p4_) {
 105         Point p1 = m.times(p1_);
 106         Point p2 = m.times(p2_);
 107         Point p3 = m.times(p3_);
 108         Point p4 = m.times(p4_);
 109         Point c  = new Point((p1.x+p2.x+p3.x+p4.x)/4,
 110                              (p1.y+p2.y+p3.y+p4.y)/4,
 111                              (p1.z+p2.z+p3.z+p4.z)/4);
 112         mesh.newT(p1, p2, c, null, 0);
 113         mesh.newT(p2, p3, c, null, 0);
 114         mesh.newT(p3, p4, c, null, 0);
 115         mesh.newT(p4, p1, c, null, 0);
 116     }
 117
 118     public Main(StlFile stlf, Frame f) {
 119         super(f);
 120
 121         for(int i=0; i<stlf.coordArray.length; i+=3) {
 122             Point p0 = new Point(stlf.coordArray[i+0].x * MAG, stlf.coordArray[i+0].y * MAG, stlf.coordArray[i+0].z * MAG);
 123             Point p1 = new Point(stlf.coordArray[i+1].x * MAG, stlf.coordArray[i+1].y * MAG, stlf.coordArray[i+1].z * MAG);
 124             Point p2 = new Point(stlf.coordArray[i+2].x * MAG, stlf.coordArray[i+2].y * MAG, stlf.coordArray[i+2].z * MAG);
 125             Vec n  = new Vec(stlf.normArray[i/3].x * MAG, stlf.normArray[i/3].y  * MAG, stlf.normArray[i/3].z * MAG);
 126             Mesh.T t  = goal.newT(p0, p1, p2, n, 0);
 127         }
 128
 129         // rotate to align major axis -- this probably needs to be done by a human.
 130         //goal.transform(Matrix.rotate(new Vec(0, 0, 1), (float)(Math.PI/2)));
 131
 132
 133         float goal_width  = goal.diagonal().dot(new Vec(1, 0, 0));
 134         float goal_height = goal.diagonal().dot(new Vec(0, 1, 0));
 135         float goal_depth  = goal.diagonal().dot(new Vec(0, 0, 1));
 136
 137         /*
 138           float width  = (float)0.6;
 139           float height = (float)0.08;
 140           float depth  = (float)0.3;
 141         */
 142
 143         float width  = (float)0.8;
 144         float depth  = (float)0.08;
 145         float height = (float)0.4;
 146
 147         float rshift =   width/2;
 148         float lshift = -(width/2);
 149         float halfup = 0;
 150         //float shift = height/2;
 151         //width = (width*2)/3;
 152         float shift = 0;
 153         translations = new Matrix[] {
 154
 155             Matrix.translate(new Vec(lshift/2,  depth,    -shift)),
 156             Matrix.translate(new Vec(rshift/2,  depth,    -shift)),
 157             Matrix.translate(new Vec(lshift/2, -depth,    -shift)),
 158             Matrix.translate(new Vec(rshift/2, -depth,    -shift)),
 159
 160             Matrix.translate(new Vec(lshift,  depth/2,    -shift)),
 161             Matrix.translate(new Vec(rshift,  depth/2,    -shift)),
 162             Matrix.translate(new Vec(lshift, -depth/2,    -shift)),
 163             Matrix.translate(new Vec(rshift, -depth/2,    -shift)),
 164
 165
 166             /*
 167             Matrix.translate(new Vec(lshift,  depth,    -shift)),
 168             Matrix.translate(new Vec(rshift,  depth,    -shift)),
 169             Matrix.translate(new Vec(lshift, -depth,    -shift)),
 170             Matrix.translate(new Vec(rshift, -depth,    -shift)),
 171             */
 172             /*
 173             Matrix.translate(new Vec(lshift,  depth,    shift)),
 174             Matrix.translate(new Vec(rshift,  depth,    shift)),
 175             Matrix.translate(new Vec(lshift, -depth,    shift)),
 176             Matrix.translate(new Vec(rshift, -depth,    shift)),
 177             */
 178             //Matrix.translate(new Vec(0,  depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 179             //Matrix.translate(new Vec(0, -depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 180             //Matrix.translate(new Vec(0,   0,    height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 181             //Matrix.translate(new Vec(0,   0,   -height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 182
 183             //Matrix.translate(new Vec(0,  depth, 0)),
 184             //Matrix.translate(new Vec(0, -depth, 0)),
 185             Matrix.translate(new Vec(0,      0,  height)),
 186             Matrix.translate(new Vec(0,      0, -height)),
 187
 188             //Matrix.translate(new Vec(lshift,        depth,  height/2)),
 189             //Matrix.translate(new Vec(lshift,        depth, -height/2)),
 190             //Matrix.translate(new Vec(rshift,       -depth,  height/2)),
 191             //Matrix.translate(new Vec(rshift,       -depth, -height/2)),
 192             //Matrix.translate(new Vec(rshift,       0,  height)),
 193             //Matrix.translate(new Vec(rshift,       0, -height)),
 194
 195             Matrix.translate(new Vec( width,           0,    0)),
 196             Matrix.translate(new Vec(-width,           0,    0)),
 197
 198             Matrix.ONE
 199         };
 200
 201         float unit = 0.1f;
 202         float r = unit/2;
 203         float sin = (float)(unit * Math.sin(Math.PI/3));
 204         float cos = (float)(unit * Math.cos(Math.PI/3));
 205         float x = (float)(r*Math.tan(Math.PI/6));
 206         float z = (float)(r/Math.cos(Math.PI/6));
 207         height = 2*r*(float)Math.sqrt(2f/3f);
 208
 209
 210         r *= 0.3f;
 211         cos *= 0.3f;
 212         unit *= 0.3f;
 213
 214
 215         /*
 216         sin *= 0.3f;
 217         x *= 0.3f;
 218         z *= 0.3f;
 219         */
 220         translations = new Matrix[] {
 221             Matrix.translate(new Vec(-unit, 0, 0)),
 222             Matrix.translate(new Vec( unit, 0, 0)),
 223             Matrix.translate(new Vec(-cos,  0,  sin)),
 224             Matrix.translate(new Vec( cos,  0,  sin)),
 225             Matrix.translate(new Vec(-cos,  0, -sin)),
 226             Matrix.translate(new Vec( cos,  0, -sin)),
 227             Matrix.translate(new Vec( 0,  height, z)),
 228             Matrix.translate(new Vec(-r,  height, -x)),
 229             Matrix.translate(new Vec( r,  height, -x)),
 230             Matrix.translate(new Vec( 0, -height, -z)),
 231             Matrix.translate(new Vec(-r, -height, x)),
 232             Matrix.translate(new Vec( r, -height, x)),
 233         };
 234
 235
 236         /*
 237         translations = new Matrix[] {
 238
 239             //Matrix.translate(new Vec(lshift,  depth,    halfup)),
 240             //Matrix.translate(new Vec(rshift,  depth,    halfup)),
 241             //Matrix.translate(new Vec(lshift, -depth,    halfup)),
 242             //Matrix.translate(new Vec(rshift, -depth,    halfup)),
 243
 244
 245             //Matrix.translate(new Vec(0,  depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 246             //Matrix.translate(new Vec(0, -depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 247
 248             Matrix.translate(new Vec(0,   0,    height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 249             Matrix.translate(new Vec(0,   0,   -height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 250
 251             //Matrix.translate(new Vec(0,  depth, 0)),
 252             //Matrix.translate(new Vec(0, -depth, 0)),
 253             //Matrix.translate(new Vec(0,      0,  height)),
 254             //Matrix.translate(new Vec(0,      0, -height)),
 255
 256             //Matrix.translate(new Vec(lshift,        depth,  height/2)),
 257             //Matrix.translate(new Vec(lshift,        depth, -height/2)),
 258             //Matrix.translate(new Vec(rshift,       -depth,  height/2)),
 259             //Matrix.translate(new Vec(rshift,       -depth, -height/2)),
 260             //Matrix.translate(new Vec(rshift,       0,  height)),
 261             //Matrix.translate(new Vec(rshift,       0, -height)),
 262
 263             Matrix.translate(new Vec( width,           0,    0)),
 264             Matrix.translate(new Vec(-width,           0,    0)),
 265
 266         };
 267         */
 268         //
 269
 270
 271         //generateTile(translations, tile);
 272
 273         Point ltf = new Point(lshift,  (depth/2),  (height/2));
 274         Point mtf = new Point( 0.0,    (depth/2),  (height/2));
 275         Point rtf = new Point(rshift,  (depth/2),  (height/2));
 276         Point lbf = new Point(lshift, -(depth/2),  (height/2));
 277         Point mbf = new Point( 0.0,   -(depth/2),  (height/2));
 278         Point rbf = new Point(rshift, -(depth/2),  (height/2));
 279
 280         Point ltc = new Point(lshift,  (depth/2), 0);
 281         Point mtc = new Point( 0.0,    (depth/2), 0);
 282         Point rtc = new Point(rshift,  (depth/2), 0);
 283         Point lbc = new Point(lshift, -(depth/2), 0);
 284         Point mbc = new Point( 0.0,   -(depth/2), 0);
 285         Point rbc = new Point(rshift, -(depth/2), 0);
 286
 287         Point ltn = new Point(lshift,  (depth/2), -(height/2));
 288         Point mtn = new Point( 0.0,    (depth/2), -(height/2));
 289         Point rtn = new Point(rshift,  (depth/2), -(height/2));
 290         Point lbn = new Point(lshift, -(depth/2), -(height/2));
 291         Point mbn = new Point( 0.0,   -(depth/2), -(height/2));
 292         Point rbn = new Point(rshift, -(depth/2), -(height/2));
 293
 294
 295         Point[] points = new Point[] {
 296             ltf,
 297             mtf,
 298             rtf,
 299             lbf,
 300             mbf,
 301             rbf,
 302
 303             ltc,
 304             mtc,
 305             rtc,
 306             lbc,
 307             mbc,
 308             rbc,
 309
 310             ltn,
 311             mtn,
 312             rtn,
 313             lbn,
 314             mbn,
 315             rbn
 316         };
 317         /*
 318
 319         // top
 320         tile.newT(ltf, mtf, mtc, null, 1);
 321         tile.newT(mtc, ltc, ltf, null, 1);
 322         tile.newT(mtf, rtf, rtc, null, 1);
 323         tile.newT(rtc, mtc, mtf, null, 1);
 324
 325         tile.newT(ltc, mtc, mtn, null, 1);
 326         tile.newT(mtn, ltn, ltc, null, 1);
 327         tile.newT(mtc, rtc, rtn, null, 1);
 328         tile.newT(rtn, mtn, mtc, null, 1);
 329
 330         // bottom (swap normals)
 331         tile.newT(mbf, lbf, mbc, null, 2);
 332         tile.newT(lbc, mbc, lbf, null, 2);
 333         tile.newT(rbf, mbf, rbc, null, 2);
 334         tile.newT(mbc, rbc, mbf, null, 2);
 335
 336         tile.newT(mbc, lbc, mbn, null, 2);
 337         tile.newT(lbn, mbn, lbc, null, 2);
 338
 339         tile.newT(rbc, mbc, rbn, null, 2);
 340         tile.newT(mbn, rbn, mbc, null, 2);
 341
 342
 343         // left
 344         tile.newT(ltf, ltc, lbc, null, 3);
 345         tile.newT(lbc, lbf, ltf, null, 3);
 346         tile.newT(ltc, ltn, lbn, null, 3);
 347         tile.newT(lbn, lbc, ltc, null, 3);
 348
 349         // right (swap normals)
 350         tile.newT(rtc, rtf, rbc, null, 4);
 351         tile.newT(rbf, rbc, rtf, null, 4);
 352         tile.newT(rtn, rtc, rbn, null, 4);
 353         tile.newT(rbc, rbn, rtc, null, 4);
 354
 355         // front
 356         tile.newT(ltn, mtn, mbn, null, 5);
 357         tile.newT(ltn, mbn, lbn, null, 5);
 358         tile.newT(mtn, rtn, rbn, null, 5);
 359         tile.newT(mtn, rbn, mbn, null, 5);
 360
 361         // back
 362         tile.newT(mtf, ltf, mbf, null, 6);
 363         tile.newT(mbf, ltf, lbf, null, 6);
 364         tile.newT(rtf, mtf, rbf, null, 6);
 365         tile.newT(rbf, mtf, mbf, null, 6);
 366 */
 367         /*
 368         HashSet<Mesh.E> es = new HashSet<Mesh.E>();
 369         for(Mesh.T t : tile) {
 370             es.add(t.e1());
 371             es.add(t.e2());
 372             es.add(t.e3());
 373         }
 374         for(Mesh.E e : es) {
 375             if (e.p1.p.x == e.p2.p.x && e.p1.p.y == e.p2.p.y) continue;
 376             if (e.p1.p.z == e.p2.p.z && e.p1.p.y == e.p2.p.y) continue;
 377             if (e.p1.p.x == e.p2.p.x && e.p1.p.z == e.p2.p.z) continue;
 378             e.shatter();
 379         }
 380         */
 381
 382
 383          height = 4;
 384          width  = 4;
 385          depth  = 1;
 386
 387         Matrix mm = Matrix.scale(0.1f);
 388         // top
 389         quad(tile, mm,
 390              new Point( 2,  2,  0),
 391              new Point( 1,  1, -1),
 392              new Point(-1,  1, -1),
 393              new Point(-2,  2,  0));
 394         quad(tile, mm,
 395              new Point(-2,  2,  0),
 396              new Point(-1,  1,  1),
 397              new Point( 1,  1,  1),
 398              new Point( 2,  2,  0));
 399         quad(tile, mm,
 400              new Point( 1,  1, -1),
 401              new Point( 1,  1,  1),
 402              new Point(-1,  1,  1),
 403              new Point(-1,  1, -1));
 404
 405         // bottom
 406         quad(tile, mm,
 407              new Point(-2, -2,  0),
 408              new Point(-1, -1, -1),
 409              new Point( 1, -1, -1),
 410              new Point( 2, -2,  0));
 411         quad(tile, mm,
 412              new Point( 2, -2,  0),
 413              new Point( 1, -1,  1),
 414              new Point(-1, -1,  1),
 415              new Point(-2, -2,  0));
 416         quad(tile, mm,
 417              new Point(-1, -1, -1),
 418              new Point(-1, -1,  1),
 419              new Point( 1, -1,  1),
 420              new Point( 1, -1, -1));
 421
 422         // left
 423         quad(tile, mm,
 424              new Point( 2, -2,  0),
 425              new Point( 1, -1, -1),
 426              new Point( 1,  1, -1),
 427              new Point( 2,  2,  0));
 428         quad(tile, mm,
 429              new Point( 2,  2,  0),
 430              new Point( 1,  1,  1),
 431              new Point( 1, -1,  1),
 432              new Point( 2, -2,  0));
 433         quad(tile, mm,
 434              new Point( 1, -1, -1),
 435              new Point( 1, -1,  1),
 436              new Point( 1,  1,  1),
 437              new Point( 1,  1, -1));
 438
 439         // bottom
 440         quad(tile, mm,
 441              new Point(-2,  2,  0),
 442              new Point(-1,  1, -1),
 443              new Point(-1, -1, -1),
 444              new Point(-2, -2,  0));
 445         quad(tile, mm,
 446              new Point(-2, -2,  0),
 447              new Point(-1, -1,  1),
 448              new Point(-1,  1,  1),
 449              new Point(-2,  2,  0));
 450         quad(tile, mm,
 451              new Point(-1,  1, -1),
 452              new Point(-1,  1,  1),
 453              new Point(-1, -1,  1),
 454              new Point(-1, -1, -1));
 455
 456
 457
 458         translations = new Matrix[] {
 459
 460             Matrix.translate(new Vec(0, 0.2f,0))
 461             .times(Matrix.rotate(new Vec(0,1,0), (float)(1*Math.PI/2))),
 462
 463             Matrix.translate(new Vec(0,-0.2f,0))
 464             .times(Matrix.rotate(new Vec(0,1,0), (float)(1*Math.PI/2))),
 465
 466             Matrix.translate(new Vec( 0.2f,0,0))
 467             .times(Matrix.rotate(new Vec(1,0,0), (float)(-1*Math.PI/2))),
 468
 469             Matrix.translate(new Vec(-0.2f,0,0))
 470             .times(Matrix.rotate(new Vec(1,0,0), (float)(-1*Math.PI/2))),
 471
 472
 473             /*
 474             Matrix.rotate(new Vec(0,0,1), (float)(1*Math.PI/2)),
 475             Matrix.rotate(new Vec(0,0,1), (float)(2*Math.PI/2)),
 476             Matrix.rotate(new Vec(0,0,1), (float)(3*Math.PI/2)),
 477
 478             Matrix.rotate(new Vec(1,0,0), (float)(2*Math.PI/2)),
 479             */
 480             //Matrix.rotate(new Vec(0,0,1), (float)(2*Math.PI/2)),
 481             //Matrix.scale(1,-1,1),
 482
 483             //Matrix.translate(new Vec( 0.2f, 0,0))
 484             //.times(Matrix.rotate(new Vec(0,0,1), (float)( 1*Math.PI/2)))
 485             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 3*Math.PI/2))),
 486
 487             //Matrix.translate(new Vec(-0.2f, 0,0))
 488             //.times(Matrix.rotate(new Vec(0,0,1), (float)( 3*Math.PI/2)))
 489             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 3*Math.PI/2))),
 490
 491             //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
 492             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 493             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 494             //Matrix.rotate(new Vec(0,0,1), (float)( 1*Math.PI/2))
 495             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 496             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 497
 498             //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
 499             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 500             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 501             //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
 502             //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
 503             //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
 504
 505             Matrix.ONE,
 506         };
 507
 508
 509
 510         for(Matrix m1 : translations) {
 511         for(Matrix m2 : translations) {
 512             for(Mesh.T t1 : tile) {
 513                 for(Mesh.T t2 : tile) {
 514
 515                     Matrix m = m1.inverse().times(m2);
 516                     if ((t1.v1().p.times(m).distance(t2.v1().p) < MATCHING_EPSILON) &&
 517                         (t1.v2().p.times(m).distance(t2.v3().p) < MATCHING_EPSILON) &&
 518                         (t1.v3().p.times(m).distance(t2.v2().p) < MATCHING_EPSILON)) {
 519                         t2.e3().bindEdge(t1.e1(), m);
 520                         t2.e2().bindEdge(t1.e2(), m);
 521                         t2.e1().bindEdge(t1.e3(), m);
 522                     }
 523                     if ((t1.v2().p.times(m).distance(t2.v1().p) < MATCHING_EPSILON) &&
 524                         (t1.v3().p.times(m).distance(t2.v3().p) < MATCHING_EPSILON) &&
 525                         (t1.v1().p.times(m).distance(t2.v2().p) < MATCHING_EPSILON)) {
 526                         t2.e3().bindEdge(t1.e2(), m);
 527                         t2.e2().bindEdge(t1.e3(), m);
 528                         t2.e1().bindEdge(t1.e1(), m);
 529                     }
 530                     if ((t1.v3().p.times(m).distance(t2.v1().p) < MATCHING_EPSILON) &&
 531                         (t1.v1().p.times(m).distance(t2.v3().p) < MATCHING_EPSILON) &&
 532                         (t1.v2().p.times(m).distance(t2.v2().p) < MATCHING_EPSILON)) {
 533                         t2.e3().bindEdge(t1.e3(), m);
 534                         t2.e2().bindEdge(t1.e1(), m);
 535                         t2.e1().bindEdge(t1.e2(), m);
 536                     }
 537
 538                     if ((t1.v1().p.times(m).distance(t2.v1().p) < MATCHING_EPSILON) &&
 539                         (t1.v2().p.times(m).distance(t2.v2().p) < MATCHING_EPSILON) &&
 540                         (t1.v3().p.times(m).distance(t2.v3().p) < MATCHING_EPSILON)) {
 541                         t2.e1().bindEdge(t1.e1().pair, m);
 542                         t2.e2().bindEdge(t1.e2().pair, m);
 543                         t2.e3().bindEdge(t1.e3().pair, m);
 544                     }
 545                     if ((t1.v2().p.times(m).distance(t2.v1().p) < MATCHING_EPSILON) &&
 546                         (t1.v3().p.times(m).distance(t2.v2().p) < MATCHING_EPSILON) &&
 547                         (t1.v1().p.times(m).distance(t2.v3().p) < MATCHING_EPSILON)) {
 548                         t2.e2().bindEdge(t1.e1().pair, m);
 549                         t2.e3().bindEdge(t1.e2().pair, m);
 550                         t2.e1().bindEdge(t1.e3().pair, m);
 551                     }
 552                     if ((t1.v3().p.times(m).distance(t2.v1().p) < MATCHING_EPSILON) &&
 553                         (t1.v1().p.times(m).distance(t2.v2().p) < MATCHING_EPSILON) &&
 554                         (t1.v2().p.times(m).distance(t2.v3().p) < MATCHING_EPSILON)) {
 555                         t2.e3().bindEdge(t1.e1().pair, m);
 556                         t2.e1().bindEdge(t1.e2().pair, m);
 557                         t2.e2().bindEdge(t1.e3().pair, m);
 558                     }
 559
 560                 }
 561             }
 562         }
 563         }
 564
 565         //xMesh.Vertex mid = lbf.getE(mbn).shatter();
 566
 567         // rescale to match volume
 568
 569
 570         float factor = (float)Math.pow(tile.volume() / goal.volume(), 1.0/3.0);
 571         goal.transform(Matrix.scale(factor/2.1f));
 572         goal.transform(Matrix.rotate(new Vec(0, 1, 0), (float)(Math.PI/2)));
 573
 574         // translate to match centroid
 575         goal.transform(Matrix.translate(tile.centroid().minus(goal.centroid())));
 576         goal.makeVerticesImmutable();
 577
 578         //tx.e2.shatter();
 579         //tx.e3.shatter();
 580
 581
 582         tile.rebindPoints();
 583
 584         //mid.move(new Vec((float)0,0,(float)-0.05));
 585         //ltn.move(new Vec((float)0,0,(float)-0.05));
 586
 587         //mtf.move(new Vec(0, (float)-0.05, (float)0.05));
 588
 589
 590         System.out.println("tile volume: " + tile.volume());
 591         System.out.println("goal volume: " + goal.volume());
 592
 593         tile.error_against = goal;
 594         goal.error_against = tile;
 595     }
 596
 597     public void breakit() {
 598         int oldverts = verts;
 599         System.out.println("doubling vertices.");
 600         PriorityQueue<Mesh.E> es = new PriorityQueue<Mesh.E>();
 601         for(Mesh.T t : tile) {
 602             es.add(t.e1());
 603             es.add(t.e2());
 604             es.add(t.e3());
 605             Thread.yield();
 606             repaint();
 607         }
 608         for(int i=0; i<Math.min(oldverts,50); i++) {
 609             Mesh.E e = es.poll();
 610             verts++;
 611             //System.out.println("shatter " + e);
 612             //e.shatter(e.midpoint(), null, null, true, true);
 613             e.shatter();
 614             Thread.yield();
 615             repaint();
 616         }
 617         tile.rebindPoints();
 618     }
 619
 620     public synchronized void rand(double temp, Mesh.Vertex p) {
 621
 622         p.reComputeErrorAround();
 623         double tile_error = tile.error();
 624         double goal_error = goal.error();
 625
 626         //float max = p.averageEdgeLength()/10;
 627         float max = 0.01f;
 628
 629         Vec v = new Vec(random.nextFloat(), random.nextFloat(), random.nextFloat());
 630         v = v.norm().times((random.nextFloat() - 0.5f) * max);
 631         //System.out.println(max + " " + p.averageEdgeLength() + " " + v.mag());
 632         Matrix m = Matrix.translate(v);
 633
 634         //System.out.println(v.mag() + " " + max);
 635         boolean good = p.move(m, false);
 636         if (!good) { /*misses++;*/ return; }
 637
 638         double new_tile_error = tile.error();
 639         double new_goal_error = goal.error();
 640         double tile_delta = (new_tile_error - tile_error) / tile_error;
 641         double goal_delta = (new_goal_error - goal_error) / goal_error;
 642         double delta = tile_delta + goal_delta;
 643         double swapProbability = Math.exp((-1 * delta) / temp);
 644         //System.out.println(swapProbability);
 645         boolean doSwap = good && (Math.random() < swapProbability);
 646         //boolean doSwap = good && (tile_delta <= 0 && goal_delta <= 0);
 647         //boolean doSwap = good && (tile_delta + goal_delta <= 0);
 648
 649         //if (temp < 0.000001) doSwap = good && (tile_delta <= 0 && goal_delta <= 0);
 650
 651         if (doSwap) {
 652             tile_error = new_tile_error;
 653             goal_error = new_goal_error;
 654             //System.out.println("error: " + tile_error + " / " + goal_error);
 655             hits++;
 656             p.goodp = p.p;
 657         } else {
 658             p.move(Matrix.translate(v.times(-1)), true);
 659             misses++;
 660         }
 661         p.reComputeErrorAround();
 662     }
 663
 664     float hits = 0;
 665     float misses = 0;
 666     public void anneal() throws Exception {
 667         double hightemp = 1;
 668         double temp = hightemp;
 669         double last = 10;
 670         boolean seek_upward = false;
 671         double acceptance = 1;
 672         while(true) {
 673             synchronized(this) {
 674                 double ratio = (hits+misses==0) ? 1 : (hits / (hits+misses));
 675                 hits = 0;
 676                 misses = 0;
 677                 double gamma = 1;
 678                 acceptance = (ratio+acceptance)/2;
 679                 accepts = (int)(Math.ceil(ratio*100));
 680                 temps = (int)(Math.ceil(temp*1000));
 681                 vertss = tile.size();
 682                 if (breaks > 0) {
 683                     while (breaks>0) {
 684                         breaks--;
 685                         breakit();
 686                     }
 687                     seek_upward = true;
 688                 } else if (acceptance > 0.96) gamma = 0.1f;
 689                 else if (acceptance > 0.9)    gamma = 0.2f;
 690                 else if (acceptance > 0.8)    gamma = 0.3f;
 691                 else if (acceptance > 0.6)    gamma = 0.4f;
 692                 else if (acceptance > 0.3)    gamma = 0.6f;
 693                 else if (acceptance > 0.15)   gamma = 0.9f;
 694                 else if (acceptance > 0.05)   gamma = 0.94f;
 695                 else if (acceptance > 0.01)   gamma = 0.98f;
 696                 else { /*breaks++;*/ }
 697
 698                 /*
 699                 if (seek_upward) {
 700                     if (acceptance > 0.2) seek_upward = false;
 701                     else gamma = 2-gamma;
 702                 }
 703                 */
 704
 705                 if (anneal)
 706                     temp = temp * gamma;
 707
 708
 709                 HashSet<Mesh.Vertex> hs = new HashSet<Mesh.Vertex>();
 710                 for(Mesh.Vertex p : tile.vertices()) hs.add(p);
 711                 Mesh.Vertex[] pts = (Mesh.Vertex[])hs.toArray(new Mesh.Vertex[0]);
 712
 713                 int count = 0;
 714                 long then = System.currentTimeMillis();
 715                 for(int i=0; i<400; i++) {
 716                     if (anneal) {
 717                         count++;
 718                         Mesh.Vertex v = pts[Math.abs(random.nextInt()) % pts.length];
 719                         rand(temp,v);
 720                         v.recomputeFundamentalQuadricIfStale();
 721                         v.recomputeFundamentalQuadricIfNeighborChanged();
 722                     }
 723                     Thread.yield();
 724                     repaint();
 725                 }
 726
 727                 /*
 728                 PriorityQueue<Mesh.E> es = new PriorityQueue<Mesh.E>();
 729                 for(Mesh.T t : tile) {
 730                     float max = 5;
 731                     for(Mesh.E e : new Mesh.E[] { t.e1(), t.e2(), t.e3() }) {
 732                         if (e==null) continue;
 733                         if (e.stretchRatio() > max) es.add(e);
 734                         if (t.aspect() < 0.1 && e.length()>e.next.length() && e.length()>e.prev.length()) es.add(e);
 735                     }
 736                 }
 737                 for(int i=0; i<5; i++) {
 738                     Mesh.E e = es.poll();
 739                     if (e==null) break;
 740                     e.shatter();
 741                 }
 742
 743
 744                 tile.rebindPoints();
 745                 */
 746
 747
 748                 System.out.println("temp="+temp + " ratio="+(Math.ceil(acceptance*100)) + " " +
 749                                    "points_per_second=" +
 750                                    (count*1000)/((double)(System.currentTimeMillis()-then)));
 751                 for(Mesh.Vertex p : goal.vertices()) {
 752                     p.quadricStale = true;
 753                     p.recomputeFundamentalQuadricIfNeighborChanged();
 754                 }
 755
 756                 synchronized(safeTriangles) {
 757                     safeTriangles.clear();
 758                     for(Mesh.T t : tile)
 759                         //if (t.shouldBeDrawn())
 760                             safeTriangles.add(t);
 761                 }
 762             }
 763         }
 764     }
 765
 766
 767     public static void main(String[] s) throws Exception {
 768         StlFile stlf = new StlFile();
 769         stlf.load("torus.stl");
 770         //stlf.load("fish.stl");
 771         //stlf.load("monkey.stl");
 772         Frame f = new Frame();
 773         Main main = new Main(stlf, f);
 774         f.pack();
 775         f.show();
 776         f.setSize(900, 900);
 777         f.doLayout();
 778         main.anneal();
 779     }
 780
 781 }