From 9257c9caa1d47949459343139aace021691e7801 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 5 Dec 2007 16:12:13 -0800 Subject: [PATCH] checkpoint darcs-hash:20071206001213-5007d-a802d227af2ef608c566c45a29331a2923b510c1.gz --- Makefile | 2 +- src/edu/berkeley/qfat/Main.java | 177 ++++++++++++++++++++++-------- src/edu/berkeley/qfat/Mesh.java | 91 +++++++++++++-- src/edu/berkeley/qfat/MeshViewer.java | 19 ++-- src/edu/berkeley/qfat/geom/Triangle.java | 8 ++ 5 files changed, 235 insertions(+), 62 deletions(-) diff --git a/Makefile b/Makefile index 7436dce..dec73e8 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,4 @@ all: mkdir -p build javac -cp lib/kd.jar -d build `find src -name \*.java` - java -cp lib/kd.jar:build edu.berkeley.qfat.Main + java -server -cp lib/kd.jar:build edu.berkeley.qfat.Main diff --git a/src/edu/berkeley/qfat/Main.java b/src/edu/berkeley/qfat/Main.java index 96c5c06..7eb7b09 100644 --- a/src/edu/berkeley/qfat/Main.java +++ b/src/edu/berkeley/qfat/Main.java @@ -54,12 +54,22 @@ public class Main extends MeshViewer { float rshift = width/2; float lshift = -(width/2); + //float halfup = height/2; + float halfup = 0; + translations = new Matrix[] { - new Matrix(new Vec(lshift, depth, 0)), - new Matrix(new Vec(rshift, depth, 0)), - new Matrix(new Vec(lshift, -depth, 0)), - new Matrix(new Vec(rshift, -depth, 0)), + new Matrix(new Vec(lshift, depth, halfup)), + new Matrix(new Vec(rshift, depth, halfup)), + new Matrix(new Vec(lshift, -depth, halfup)), + new Matrix(new Vec(rshift, -depth, halfup)), + /* + new Matrix(new Vec(lshift, depth, -halfup)), + new Matrix(new Vec(rshift, depth, -halfup)), + new Matrix(new Vec(lshift, -depth, -halfup)), + new Matrix(new Vec(rshift, -depth, -halfup)), + */ + new Matrix(new Vec(lshift, 0, height)), new Matrix(new Vec(rshift, 0, height)), new Matrix(new Vec(lshift, 0, -height)), @@ -67,35 +77,49 @@ public class Main extends MeshViewer { new Matrix(new Vec( width, 0, 0)), new Matrix(new Vec(-width, 0, 0)), - - new Matrix(new Vec( 0, 0, height)), - new Matrix(new Vec( 0, 0, -height)), }; Point ltf = new Point(lshift, (depth/2), (height/2)); - Point mtf = new Point( 0.0, (depth/2), (height/2)); + Point mtf = new Point( 0.0, (depth/2), (height/2)); Point rtf = new Point(rshift, (depth/2), (height/2)); - Point ltn = new Point(lshift, (depth/2), -(height/2)); - Point mtn = new Point( 0.0, (depth/2), -(height/2)); - Point rtn = new Point(rshift, (depth/2), -(height/2)); Point lbf = new Point(lshift, -(depth/2), (height/2)); - Point mbf = new Point( 0.0, -(depth/2), (height/2)); + Point mbf = new Point( 0.0, -(depth/2), (height/2)); Point rbf = new Point(rshift, -(depth/2), (height/2)); + + Point ltc = new Point(lshift, (depth/2), 0); + Point mtc = new Point( 0.0, (depth/2), 0); + Point rtc = new Point(rshift, (depth/2), 0); + Point lbc = new Point(lshift, -(depth/2), 0); + Point mbc = new Point( 0.0, -(depth/2), 0); + Point rbc = new Point(rshift, -(depth/2), 0); + + Point ltn = new Point(lshift, (depth/2), -(height/2)); + Point mtn = new Point( 0.0, (depth/2), -(height/2)); + Point rtn = new Point(rshift, (depth/2), -(height/2)); Point lbn = new Point(lshift, -(depth/2), -(height/2)); - Point mbn = new Point( 0.0, -(depth/2), -(height/2)); + Point mbn = new Point( 0.0, -(depth/2), -(height/2)); Point rbn = new Point(rshift, -(depth/2), -(height/2)); + Point[] points = new Point[] { ltf, mtf, rtf, - ltn, - mtn, - rtn, lbf, mbf, rbf, + + ltc, + mtc, + rtc, + lbc, + mbc, + rbc, + + ltn, + mtn, + rtn, lbn, mbn, rbn @@ -103,24 +127,40 @@ public class Main extends MeshViewer { // top - tile.newT(ltf, mtf, mtn, null, 1); - tile.newT(mtn, ltn, ltf, null, 1); - tile.newT(mtf, rtf, rtn, null, 1); - tile.newT(rtn, mtn, mtf, null, 1); + tile.newT(ltf, mtf, mtc, null, 1); + tile.newT(mtc, ltc, ltf, null, 1); + tile.newT(mtf, rtf, rtc, null, 1); + tile.newT(rtc, mtc, mtf, null, 1); + + tile.newT(ltc, mtc, mtn, null, 1); + tile.newT(mtn, ltn, ltc, null, 1); + tile.newT(mtc, rtc, rtn, null, 1); + tile.newT(rtn, mtn, mtc, null, 1); // bottom (swap normals) - tile.newT(mbf, lbf, mbn, null, 2); - tile.newT(lbn, mbn, lbf, null, 2); - tile.newT(rbf, mbf, rbn, null, 2); - tile.newT(mbn, rbn, mbf, null, 2); - + tile.newT(mbf, lbf, mbc, null, 2); + tile.newT(lbc, mbc, lbf, null, 2); + tile.newT(rbf, mbf, rbc, null, 2); + tile.newT(mbc, rbc, mbf, null, 2); + + tile.newT(mbc, lbc, mbn, null, 2); + tile.newT(lbn, mbn, lbc, null, 2); + + tile.newT(rbc, mbc, rbn, null, 2); + tile.newT(mbn, rbn, mbc, null, 2); + + // left - tile.newT(ltf, ltn, lbn, null, 3); - tile.newT(lbn, lbf, ltf, null, 3); + tile.newT(ltf, ltc, lbc, null, 3); + tile.newT(lbc, lbf, ltf, null, 3); + tile.newT(ltc, ltn, lbn, null, 3); + tile.newT(lbn, lbc, ltc, null, 3); // right (swap normals) - tile.newT(rtn, rtf, rbn, null, 4); - tile.newT(rbf, rbn, rtf, null, 4); + tile.newT(rtc, rtf, rbc, null, 4); + tile.newT(rbf, rbc, rtf, null, 4); + tile.newT(rtn, rtc, rbn, null, 4); + tile.newT(rbc, rbn, rtc, null, 4); // front tile.newT(ltn, mtn, mbn, null, 5); @@ -160,6 +200,7 @@ public class Main extends MeshViewer { t1.e1().bindEdge(t2.e2()); t1.e2().bindEdge(t2.e1()); } + } } } @@ -197,59 +238,103 @@ public class Main extends MeshViewer { //while(verts < 800) { PriorityQueue es = new PriorityQueue(); for(Mesh.E e : tile.edges()) es.add(e); - for(int i=0; i<40; i++) { + for(int i=0; i<8; i++) { Mesh.E e = es.poll(); verts++; - //System.out.println("shatter " + e); + System.out.println("shatter " + e); e.shatter(); - tile.rebindPoints(); } + tile.rebindPoints(); //} } - public synchronized void rand(double temperature, Mesh.Vert p) { + public synchronized void rand(float temp, Mesh.Vert p) { double tile_score = tile.score(); double goal_score = goal.score(); - p.reComputeError(); + //p.reComputeError(); + p.reComputeErrorAround(); - Vec v = new Vec((random.nextFloat() - (float)0.5) / 1000, - (random.nextFloat() - (float)0.5) / 1000, - (random.nextFloat() - (float)0.5) / 1000); + Vec v = new Vec((random.nextFloat() - (float)0.5) / 400, + (random.nextFloat() - (float)0.5) / 400, + (random.nextFloat() - (float)0.5) / 400); /* Matrix inv = p.errorQuadric(); Vec v = new Vec(inv.d, inv.h, inv.l).norm().times(1/(float)1000); */ boolean good = p.move(v); + + p.reComputeErrorAround(); + double new_tile_score = tile.score(); double new_goal_score = goal.score(); - double tile_delta = new_tile_score - tile_score; - double goal_delta = 0;//new_goal_score - goal_score; + double tile_delta = (new_tile_score - tile_score) / tile_score; + double goal_delta = (new_goal_score - goal_score) / goal_score; double delta = tile_delta + goal_delta; - //double swapProbability = Math.exp((-1 * delta) / temperature); - //boolean doSwap = Math.random() < swapProbability; - boolean doSwap = good && (tile_delta <= 0 && goal_delta <= 0); + double swapProbability = Math.exp((-1 * delta) / temp); + boolean doSwap = good && (Math.random() < swapProbability); + //boolean doSwap = good && (tile_delta <= 0 && goal_delta <= 0); if (doSwap) { tile_score = new_tile_score; goal_score = new_goal_score; //System.out.println("score: " + tile_score + " / " + goal_score); + hits++; } else { p.move(v.times(-1)); + misses++; } } + float hits = 0; + float misses = 0; public void anneal() throws Exception { int verts = 0; + float hightemp = 10; + float temp = hightemp; + float last = 10; while(true) { + double ratio = (hits+misses==0) ? 1 : (hits / (hits+misses)); + System.out.println("temp="+temp + " ratio="+(Math.ceil(ratio*100))); + hits = 0; + misses = 0; + float gamma = 0; + double acceptance = ratio; + if (breaks) { + breaks = false; + breakit(); + gamma = 2; + //temp = last * 0.8f; + //last = temp; + //temp = hightemp; + } else + if (acceptance > 0.96) gamma = 0.6f; + else if (acceptance > 0.9) gamma = 0.7f; + else if (acceptance > 0.8) gamma = 0.75f; + else if (acceptance > 0.6) gamma = 0.8f; + else { + if (acceptance > 0.3) { + gamma = 0.9f; + } else if (acceptance > 0.15) { + gamma = 0.95f; + } else { + breakit(); + gamma = 2; + //temp = last * 0.8f; + //last = temp; + //temp = hightemp; + } + } + temp = temp * gamma; + HashSet hs = new HashSet(); for(Mesh.Vert p : tile.vertices()) hs.add(p); for(int i=0; i<10; i++) { repaint(); - for(Mesh.Vert v : hs) rand(10,v); + for(Mesh.Vert v : hs) rand(temp,v); } tile.rebuildPointSet(); repaint(); - breakit(); + //breakit(); repaint(); goal.unApplyQuadricToNeighborAll(); repaint(); @@ -264,6 +349,10 @@ public class Main extends MeshViewer { stlf.load("simplefish.stl"); Frame f = new Frame(); Main main = new Main(stlf, f); + f.pack(); + f.show(); + f.setSize(900, 900); + f.doLayout(); main.anneal(); } diff --git a/src/edu/berkeley/qfat/Mesh.java b/src/edu/berkeley/qfat/Mesh.java index da10ac9..46c2200 100644 --- a/src/edu/berkeley/qfat/Mesh.java +++ b/src/edu/berkeley/qfat/Mesh.java @@ -37,11 +37,15 @@ public class Mesh implements Iterable { } public Iterator iterator() { + /* for(Vert v : pointset) if (v.e != null && v.e.t != null) return new FaceIterator(v); return new FaceIterator(); + */ + return ts.iterator(); } + public HashSet ts = new HashSet(); public Mesh score_against = null; public double score = 0; @@ -164,12 +168,14 @@ public class Mesh implements Iterable { unApplyQuadricToNeighbor(); Matrix m = Matrix.ZERO; E e = this.e; + int count = 0; do { T t = e.t; m = m.plus(t.norm().fundamentalQuadric(t.centroid())); + count++; e = e.pair.next; } while(e != this.e); - fundamentalQuadric = m; + fundamentalQuadric = m.times(1/(float)count); applyQuadricToNeighbor(); } @@ -208,6 +214,15 @@ public class Mesh implements Iterable { reComputeError(); } + public void reComputeErrorAround() { + reComputeError(); + if (nearest_in_other_mesh != null) nearest_in_other_mesh.reComputeError(); + E e = this.e; + do { + e.p2.reComputeError(); + e = e.pair.next; + } while (e != this.e); + } public void reComputeError() { unComputeError(); computeError(); @@ -217,11 +232,43 @@ public class Mesh implements Iterable { oldscore = 0; } public void computeError() { - oldscore = quadric_count == 0 ? 0 : ((quadric.preAndPostMultiply(p) * 100) / quadric_count); - double ang = Math.abs(e.crossAngle()); - if (ang < Math.PI * 0.2) - oldscore += ((Math.PI*0.2) - ang) * 10; + if (quadric_count == 0) { + if (nearest_in_other_mesh == null) { + if (score_against != null) { + Vert ne = score_against.nearest(p); + oldscore = ne.fundamentalQuadric().preAndPostMultiply(p) * 100 * 3; + } else { + oldscore = 0; + } + } else { + oldscore = nearest_in_other_mesh.fundamentalQuadric().preAndPostMultiply(p) * 100 * 3; + } + } else { + oldscore = (quadric.preAndPostMultiply(p) * 100) / quadric_count; + } + + oldscore = oldscore*oldscore; + + int numaspects = 0; + float aspects = 0; + E e = this.e; + do { + double ang = Math.abs(e.crossAngle()); + if (ang > Math.PI) throw new Error(); + if (e.t != null) { + numaspects++; + aspects += e.t.aspect()*e.t.aspect(); + } + + if (ang > Math.PI * 0.8) + oldscore += (ang - (Math.PI*0.8)) * 10; + + e = e.pair.next; + } while (e != this.e); + if (numaspects > 0) oldscore += (aspects / numaspects); + //System.out.println(oldscore); + //oldscore = oldscore*oldscore; score += oldscore; } @@ -257,14 +304,15 @@ public class Mesh implements Iterable { do { if (!t.has(e.p1) && !t.has(e.p2) && e.intersects(t)) { good = false; break; } if (e.t != null) { - if (!e.t.has(t.e1().p1) && !e.t.has(t.e1().p2) && t.e1().intersects(e.t)) { good = false; break; } - if (!e.t.has(t.e2().p1) && !e.t.has(t.e2().p2) && t.e2().intersects(e.t)) { good = false; break; } - if (!e.t.has(t.e3().p1) && !e.t.has(t.e3().p2) && t.e3().intersects(e.t)) { good = false; break; } + //if (!e.t.has(t.e1().p1) && !e.t.has(t.e1().p2) && t.e1().intersects(e.t)) { good = false; break; } + //if (!e.t.has(t.e2().p1) && !e.t.has(t.e2().p2) && t.e2().intersects(e.t)) { good = false; break; } + //if (!e.t.has(t.e3().p1) && !e.t.has(t.e3().p2) && t.e3().intersects(e.t)) { good = false; break; } } e = e.pair.next; } while(e != this.e); } -*/ + */ + reComputeErrorAround(); return good; } @@ -394,7 +442,15 @@ public class Mesh implements Iterable { public BindingGroup bind_to = bind_peers.other(); boolean shattered = false; - public int compareTo(E e) { return e.length() > length() ? 1 : -1; } + public float comparator() { + if (t==null) return length(); + if ((length() * length()) / t.area() > 10) + return (float)(length()*Math.sqrt(t.area())); + return length()*t.area(); + } + public int compareTo(E e) { + return e.comparator() > comparator() ? 1 : -1; + } public void bindEdge(E e) { bind_to.add(e); } public void dobind() { bind_to.dobind(this); } @@ -428,12 +484,23 @@ public class Mesh implements Iterable { if (destroyed) return; destroyed = true; pair.destroyed = true; + + if (t != null) t.destroy(); + t = null; + + if (pair.t != null) pair.t.destroy(); + pair.t = null; + if (next.t != null) next.t.destroy(); if (prev.t != null) prev.t.destroy(); next.t = null; prev.t = null; + + if (pair.next.t != null) pair.next.t.destroy(); + if (pair.prev.t != null) pair.next.t.destroy(); pair.next.t = null; pair.prev.t = null; + this.bind_to = null; pair.bind_to = null; this.bind_peers = null; @@ -685,6 +752,7 @@ public class Mesh implements Iterable { public final int colorclass; public void destroy() { + ts.remove(this); } T(E e1, int colorclass) { @@ -710,6 +778,7 @@ public class Mesh implements Iterable { } this.color = color; this.colorclass = colorclass; + ts.add(this); } public E e1() { return e1; } public E e2() { return e1.next; } @@ -724,9 +793,11 @@ public class Mesh implements Iterable { public boolean has(Vert v) { return v1()==v || v2()==v || v3()==v; } public void glVertices(GL gl) { + if (e1().bind_to.set.size() == 0) return; if (e2().bind_to.set.size() == 0) return; if (e3().bind_to.set.size() == 0) return; + norm().glNormal(gl); p1().glVertex(gl); p2().glVertex(gl); diff --git a/src/edu/berkeley/qfat/MeshViewer.java b/src/edu/berkeley/qfat/MeshViewer.java index cb21cfb..96680be 100644 --- a/src/edu/berkeley/qfat/MeshViewer.java +++ b/src/edu/berkeley/qfat/MeshViewer.java @@ -16,6 +16,7 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi public Mesh.Vert[] points; + public boolean breaks = false; boolean alt = false; boolean shift = false; boolean control = false; @@ -30,6 +31,7 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi case KeyEvent.VK_CONTROL: control = true; break; case KeyEvent.VK_ALT: alt = true; break; case KeyEvent.VK_SHIFT: shift = true; break; + case KeyEvent.VK_SPACE: breaks = true; break; } } public void keyReleased(KeyEvent e) { @@ -182,6 +184,7 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi t.glVertices(gl); gl.glEnd(); } else { + /* gl.glDisable(GL.GL_LIGHTING); gl.glBegin(GL.GL_LINES); gl.glColor3f(1, 1, 1); @@ -193,6 +196,7 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi t.e3().p2.p.glVertex(gl); gl.glEnd(); gl.glEnable(GL.GL_LIGHTING); + */ } Point centroid = t.centroid(); @@ -205,10 +209,15 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi if (mesh==goal) for(Mesh.Vert p : new Mesh.Vert[] { t.v1(), t.v2(), t.v3() }) { - //p.p.glVertex(gl); - //p.plus(p.norm().times(p.score()*10)).glVertex(gl); - //p.partner().p.glVertex(gl); + gl.glDisable(GL.GL_LIGHTING); + gl.glBegin(GL.GL_LINES); + gl.glColor3f(1, 1, 1); + p.p.glVertex(gl); + //p.p.plus(p.norm().times(p.score())).glVertex(gl); + if (p.nearest_in_other_mesh != null) p.nearest_in_other_mesh.p.glVertex(gl); //tile.nearest(p).centroid().glVertex(gl); + gl.glEnd(); + gl.glEnable(GL.GL_LIGHTING); } gl.glEnd(); @@ -222,10 +231,6 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi glcanvas = new GLCanvas(); glcanvas.addGLEventListener(this); f.add(glcanvas, BorderLayout.CENTER); - f.pack(); - f.show(); - f.setSize(900, 900); - f.doLayout(); glcanvas.addMouseListener(this); glcanvas.addMouseMotionListener(this); glcanvas.addMouseWheelListener(this); diff --git a/src/edu/berkeley/qfat/geom/Triangle.java b/src/edu/berkeley/qfat/geom/Triangle.java index 0ed9d39..6024e8f 100644 --- a/src/edu/berkeley/qfat/geom/Triangle.java +++ b/src/edu/berkeley/qfat/geom/Triangle.java @@ -30,4 +30,12 @@ public abstract class Triangle { p2().distance(p3())), p3().distance(p1())) / 2; } + + public float aspect() { + float max = Math.max(Math.max(p1().distance(p2()), + p2().distance(p3())), + p3().distance(p1())) / 2; + return 1/(1+area()/(max*max)); + } + } \ No newline at end of file -- 1.7.10.4