From 0525dcc815af1e875699147e9f203969eeae723d Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Sat, 15 Dec 2007 22:57:19 -0800
Subject: [PATCH] checkpoint

darcs-hash:20071216065719-5007d-0a6eb1b32b322c1c1e3fbd871542f433d3e9824f.gz
---
 src/edu/berkeley/qfat/Main.java |   93 +++++++++++++++------------------------
 src/edu/berkeley/qfat/Mesh.java |   52 ++++++++++++++++++----
 2 files changed, 78 insertions(+), 67 deletions(-)

diff --git a/src/edu/berkeley/qfat/Main.java b/src/edu/berkeley/qfat/Main.java
index f51c772..03ca6dc 100644
--- a/src/edu/berkeley/qfat/Main.java
+++ b/src/edu/berkeley/qfat/Main.java
@@ -266,7 +266,7 @@ public class Main extends MeshViewer {
         goal.error_against = tile;
     }
 
-    public synchronized void breakit() {
+    public void breakit() {
         int oldverts = verts;
         System.out.println("doubling vertices.");
         PriorityQueue<Mesh.E> es = new PriorityQueue<Mesh.E>();
@@ -274,50 +274,43 @@ public class Main extends MeshViewer {
             es.add(t.e1());
             es.add(t.e2());
             es.add(t.e3());
+            Thread.yield();
+            repaint();
         }
-        for(int i=0; i<oldverts; i++) {
+        for(int i=0; i<Math.min(oldverts,200); i++) {
             Mesh.E e = es.poll();
             verts++;
             //System.out.println("shatter " + e);
             e.shatter();
+            Thread.yield();
+            repaint();
         }
         tile.rebindPoints();
     }
 
     public synchronized void rand(float temp, Mesh.Vertex p) {
 
-        //p.reComputeError();
         p.reComputeErrorAround();
         double tile_error = tile.error();
         double goal_error = goal.error();
 
-        Vec v;
-        /*
-          Matrix inv = p.errorQuadric();
-          v = new Vec(inv.d, inv.h, inv.l).norm().times(1/(float)300);
-          if (p.quadric_count == 0) {
-          v = goal.nearest(p.p).p.minus(p.p).norm().times(1/(float)300);
-          }
-        */
-        Vec v2 = new Vec((random.nextFloat() - (float)0.5) / 500,
-                         (random.nextFloat() - (float)0.5)  / 500,
-                         (random.nextFloat() - (float)0.5)  / 500);
-        //v = v.plus(v2.norm().times(1/(float)300));
-        v = v2.norm().times(1/(float)300);
-
+        float max = p.averageEdgeLength()/30;
+        Vec v = new Vec(random.nextFloat(), random.nextFloat(), random.nextFloat());
+        v = v.norm().times((random.nextFloat() - 0.5f) * max);
+        //System.out.println(max + " " + p.averageEdgeLength() + " " + v.mag());
         Matrix m = Matrix.translate(v);
 
         boolean good = p.move(m, false);
         if (!good) { misses++; return; }
 
-        //p.reComputeErrorAround();
+        p.reComputeErrorAround();
 
         double new_tile_error = tile.error();
         double new_goal_error = goal.error();
         double tile_delta = (new_tile_error - tile_error) / tile_error;
         double goal_delta = (new_goal_error - goal_error) / goal_error;
         double delta = tile_delta + goal_delta;
-        double swapProbability = Math.exp((-1 * delta) / temp);
+        double swapProbability = Math.exp((-1 * delta) / (((double)temp)/10000));
         boolean doSwap = good && (Math.random() < swapProbability);
         //boolean doSwap = good && (tile_delta <= 0 && goal_delta <= 0);
         //boolean doSwap = good && (tile_delta + goal_delta <= 0);
@@ -335,57 +328,41 @@ public class Main extends MeshViewer {
     float hits = 0;
     float misses = 0;
     public void anneal() throws Exception {
-        float hightemp = 10;
+        float hightemp = 1;
         float temp = hightemp;
         float last = 10;
-        float lastbreak = 10;
+        boolean seek_upward = false;
+        double acceptance = 1;
         while(true) {
             synchronized(this) {
                 double ratio = (hits+misses==0) ? 1 : (hits / (hits+misses));
                 hits = 0;
                 misses = 0;
-                float gamma = 0;
-                double acceptance = ratio;
+                float gamma = 1;
+                acceptance = (ratio+acceptance)/2;
                 accepts = (int)(Math.ceil(ratio*100));
                 temps = (int)(Math.ceil(temp*1000));
                 vertss = tile.size();
-                if (breaks > 0) { while (breaks>0) {
+                if (breaks > 0) {
+                    while (breaks>0) {
                         breaks--;
                         breakit();
-                        //gamma = 1;
-                        float t = temp;
-                        temp = lastbreak;
-                        gamma = 1;
-                        lastbreak = t;
-                        //temp = last * 0.8f;
-                        //last = temp;
-                        //temp = hightemp;
-                    } } else
-                    if (acceptance > 0.96) gamma = 0.4f;
-                    else if (acceptance > 0.9) gamma = 0.5f;
-                    else if (acceptance > 0.8) gamma = 0.65f;
-                    else if (acceptance > 0.6) gamma = 0.7f;
-                    else {
-                        if (acceptance > 0.3) {
-                            gamma = 0.9f;
-                        } else if (acceptance > 0.15) {
-                            gamma = 0.95f;
-                        } else if (acceptance > 0.10) {
-                            gamma = 0.98f;
-                        } else {
-                            breakit();
-                        float t = temp;
-                        temp = lastbreak;
-                        gamma = 1;
-                        lastbreak = t;
-                            //gamma = 1;
-                        //gamma = 0.99f;
-                            //gamma = 1;
-                            //temp = last * 0.8f;
-                            //last = temp;
-                            //temp = hightemp;
-                        }
                     }
+                    seek_upward = true;
+                } else if (acceptance > 0.96) gamma = 0.4f;
+                else if (acceptance > 0.9)    gamma = 0.5f;
+                else if (acceptance > 0.8)    gamma = 0.65f;
+                else if (acceptance > 0.6)    gamma = 0.7f;
+                else if (acceptance > 0.3)    gamma = 0.9f;
+                else if (acceptance > 0.15)   gamma = 0.95f;
+                else if (acceptance > 0.10)   gamma = 0.98f;
+                else breaks++;
+
+                if (seek_upward) {
+                    if (acceptance > 0.3) seek_upward = false;
+                    else gamma = 2-gamma;
+                }
+
                 temp = temp * gamma;
 
 
@@ -406,7 +383,7 @@ public class Main extends MeshViewer {
                     Thread.yield();
                     repaint();
                 }
-                System.out.println("temp="+temp + " ratio="+(Math.ceil(ratio*100)) + " " +
+                System.out.println("temp="+temp + " ratio="+(Math.ceil(acceptance*100)) + " " +
                                    "points_per_second=" +
                                    (count*1000)/((double)(System.currentTimeMillis()-then)));
 
diff --git a/src/edu/berkeley/qfat/Mesh.java b/src/edu/berkeley/qfat/Mesh.java
index 1484b66..babad37 100644
--- a/src/edu/berkeley/qfat/Mesh.java
+++ b/src/edu/berkeley/qfat/Mesh.java
@@ -104,6 +104,25 @@ public class Mesh implements Iterable<Mesh.T> {
             error += olderror;
         }
 
+        public float averageTriangleArea() {
+            int count = 0;
+            float ret = 0;
+            for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
+                ret += e.t.area();
+                count++;
+            }
+            return ret/count;
+        }
+        public float averageEdgeLength() {
+            int count = 0;
+            float ret = 0;
+            for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
+                ret += e.length();
+                count++;
+            }
+            return ret/count;
+        }
+
         public Matrix _recomputeFundamentalQuadric() {
             Matrix m = Matrix.ZERO;
             int count = 0;
@@ -116,19 +135,23 @@ public class Mesh implements Iterable<Mesh.T> {
 
         public HasQuadric nearest() { return error_against==null ? null : error_against.vertices.nearest(p, this); }
         public void computeError() {
+            if (error_against==null) return;
             float nerror =
                 quadric_count != 0
-                ? (quadric.preAndPostMultiply(p) * 100) / quadric_count
+                ? (quadric.preAndPostMultiply(p) * 100)/quadric_count
                 : nearest_in_other_mesh != null
-                ? nearest_in_other_mesh.fundamentalQuadric().preAndPostMultiply(p) * 100 * 10
-                : error_against != null
-                ? nearest().fundamentalQuadric().preAndPostMultiply(p) * 100 * 10
-                : 0;
+                ? nearest_in_other_mesh.fundamentalQuadric().preAndPostMultiply(p) * 100
+                : nearest().fundamentalQuadric().preAndPostMultiply(p) * 100;
             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
                 double ang = Math.abs(e.crossAngle());
                 if (ang > Math.PI) throw new Error();
                 float minangle = (float)(Math.PI * 0.8);
                 if (ang > minangle) nerror += (ang - minangle);
+                /*
+                if (e.t.aspect() < 0.2) {
+                    nerror += (0.2-e.t.aspect()) * 300;
+                }
+                */
             }
             setError(nerror);
         }
@@ -153,10 +176,11 @@ public class Mesh implements Iterable<Mesh.T> {
 
         public void checkLegality() {
             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
-                if (Math.abs(e.crossAngle()) > (Math.PI * 0.9) || Math.abs(e.next.crossAngle()) > (Math.PI * 0.9)) illegal = true;
-                if (e.t.aspect() < 0.1) illegal = true;
+                if (Math.abs(e.crossAngle()) > (Math.PI * 0.9) ||
+                    Math.abs(e.next.crossAngle()) > (Math.PI * 0.9)) illegal = true;
+                //if (e.t.aspect() < 0.1) illegal = true;
             }
-            if (illegal) triangles.range(oldp, this.p, (Visitor<T>)this);
+            if (!illegal) triangles.range(oldp, this.p, (Visitor<T>)this);
         }
 
         public void reComputeErrorAround() {
@@ -305,8 +329,18 @@ public class Mesh implements Iterable<Mesh.T> {
 
         public boolean intersects(T t) { return t.intersects(p1.p, p2.p); }
         public float comparator() {
+            /*
             Vertex nearest = error_against.nearest(midpoint());
-            return (float)Math.max(length(), midpoint().distance(nearest.p));
+            //return (float)Math.max(length(), midpoint().distance(nearest.p));
+            //return length();
+            float nearest_distance = midpoint().distance(nearest.p);
+            float other_distance =
+                (p1.p.distance(error_against.nearest(p1.p).p)+
+                 p2.p.distance(error_against.nearest(p2.p).p))/2;
+            return nearest_distance/other_distance;
+            */
+            //return length();
+            return t==null?0:(1/t.aspect());
         }
         public int compareTo(E e) {
             return e.comparator() > comparator() ? 1 : -1;
-- 
1.7.10.4