checkpoint autogen tile

darcs-hash:20071220072222-5007d-7101a13f632ca9acf5848cf965633aff3d0b3301.gz

diff --git a/src/edu/berkeley/qfat/Main.java b/src/edu/berkeley/qfat/Main.java
index 14e6bcd..5d86d71 100644 (file)
--- a/src/edu/berkeley/qfat/Main.java
+++ b/src/edu/berkeley/qfat/Main.java
@@ -7,6 +7,7 @@ import javax.media.opengl.glu.*;
 import java.util.*;
 import edu.berkeley.qfat.geom.*;
 import edu.berkeley.qfat.geom.Point;
+import edu.berkeley.qfat.geom.Polygon;
 
 // TO DO:
 // - real anneal
@@ -40,6 +41,11 @@ import edu.berkeley.qfat.geom.Point;
 
 */
 
+/*
+
+
+ */
+
 
 // FIXME: re-orient goal (how?)
 
@@ -51,7 +57,43 @@ public class Main extends MeshViewer {
     
     /** magnification factor */
     private static final float MAG = 1;
-    public static final float MATCHING_EPSILON = 0.01f;
+    public static final float MATCHING_EPSILON = 0.0001f;
+
+    public void generateTile(Matrix[] matrices, Mesh mesh) {
+        HashSet<HalfSpace> halfSpaces = new HashSet<HalfSpace>();
+        HashSet<Polygon> polygons = new HashSet<Polygon>();
+        for(Matrix m : matrices) {
+            Vec v = m.getTranslationalComponent();
+            if (v.mag() < 0.0001) continue;
+            v = v.times(0.5f);
+            Point p = Point.ORIGIN.plus(v);
+            HalfSpace hs = new HalfSpace(p, Point.ORIGIN.minus(p).norm());
+            halfSpaces.add(hs);
+            polygons.add(new Polygon(hs));
+        }
+        for(Polygon p : polygons) {
+            System.out.println(p.plane.norm + " " + p.plane.dvalue);
+            for(HalfSpace hs : halfSpaces) {
+                if (p.plane==hs) continue;
+                p = p.intersect(hs);
+            }
+            p.tesselate(mesh);
+        }
+    }
+
+    private void quad(Mesh mesh, Matrix m, Point p1_, Point p2_, Point p3_, Point p4_) {
+        Point p1 = m.times(p1_);
+        Point p2 = m.times(p2_);
+        Point p3 = m.times(p3_);
+        Point p4 = m.times(p4_);
+        Point c  = new Point((p1.x+p2.x+p3.x+p4.x)/4,
+                             (p1.y+p2.y+p3.y+p4.y)/4,
+                             (p1.z+p2.z+p3.z+p4.z)/4);
+        mesh.newT(p1, p2, c, null, 0);
+        mesh.newT(p2, p3, c, null, 0);
+        mesh.newT(p3, p4, c, null, 0);
+        mesh.newT(p4, p1, c, null, 0);
+    }
 
     public Main(StlFile stlf, Frame f) {
         super(f);
@@ -65,7 +107,8 @@ public class Main extends MeshViewer {
         }
 
         // rotate to align major axis -- this probably needs to be done by a human.
-        goal.transform(Matrix.rotate(new Vec(0, 0, 1), (float)(Math.PI/2)));
+        //goal.transform(Matrix.rotate(new Vec(0, 0, 1), (float)(Math.PI/2)));
+        goal.transform(Matrix.rotate(new Vec(0, 1, 0), (float)(Math.PI/2)));
 
         float goal_width  = goal.diagonal().dot(new Vec(1, 0, 0));
         float goal_height = goal.diagonal().dot(new Vec(0, 1, 0));
@@ -76,6 +119,7 @@ public class Main extends MeshViewer {
           float height = (float)0.08;
           float depth  = (float)0.3;
         */
+        
         float width  = (float)0.7;
         float depth  = (float)0.08;
         float height = (float)0.4;
@@ -87,24 +131,56 @@ public class Main extends MeshViewer {
         float halfup = 0;
 
         translations = new Matrix[] {
-            /*
-            Matrix.translate(new Vec(lshift,  depth,    halfup)),
-            Matrix.translate(new Vec(rshift,  depth,    halfup)),
-            Matrix.translate(new Vec(lshift, -depth,    halfup)),
-            Matrix.translate(new Vec(rshift, -depth,    halfup)),
-            */
+
+            //Matrix.translate(new Vec(lshift,  depth,    0)),
+            //Matrix.translate(new Vec(rshift,  depth,    0)),
+            //Matrix.translate(new Vec(lshift, -depth,    0)),
+            //Matrix.translate(new Vec(rshift, -depth,    0)),
 
             //Matrix.translate(new Vec(0,  depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
             //Matrix.translate(new Vec(0, -depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
+            //Matrix.translate(new Vec(0,   0,    height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
+            //Matrix.translate(new Vec(0,   0,   -height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
 
-            Matrix.translate(new Vec(0,   0,    height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
-            Matrix.translate(new Vec(0,   0,   -height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
-            /*
             Matrix.translate(new Vec(0,  depth, 0)),
             Matrix.translate(new Vec(0, -depth, 0)),
             Matrix.translate(new Vec(0,      0,  height)),
             Matrix.translate(new Vec(0,      0, -height)),
-            */
+
+            //Matrix.translate(new Vec(lshift,        depth,  height/2)),
+            //Matrix.translate(new Vec(lshift,        depth, -height/2)),
+            //Matrix.translate(new Vec(rshift,       -depth,  height/2)),
+            //Matrix.translate(new Vec(rshift,       -depth, -height/2)),
+            //Matrix.translate(new Vec(rshift,       0,  height)),
+            //Matrix.translate(new Vec(rshift,       0, -height)),
+
+            Matrix.translate(new Vec( width,           0,    0)),
+            Matrix.translate(new Vec(-width,           0,    0)),
+
+        };
+
+        generateTile(translations, tile);
+
+        /*
+        translations = new Matrix[] {
+
+            //Matrix.translate(new Vec(lshift,  depth,    halfup)),
+            //Matrix.translate(new Vec(rshift,  depth,    halfup)),
+            //Matrix.translate(new Vec(lshift, -depth,    halfup)),
+            //Matrix.translate(new Vec(rshift, -depth,    halfup)),
+
+
+            //Matrix.translate(new Vec(0,  depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
+            //Matrix.translate(new Vec(0, -depth,    0)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
+
+            Matrix.translate(new Vec(0,   0,    height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
+            Matrix.translate(new Vec(0,   0,   -height)).times(Matrix.rotate(new Vec(0, 0, 1), (float)Math.PI)),
+
+            //Matrix.translate(new Vec(0,  depth, 0)),
+            //Matrix.translate(new Vec(0, -depth, 0)),
+            //Matrix.translate(new Vec(0,      0,  height)),
+            //Matrix.translate(new Vec(0,      0, -height)),
+
             //Matrix.translate(new Vec(lshift,        depth,  height/2)),
             //Matrix.translate(new Vec(lshift,        depth, -height/2)),
             //Matrix.translate(new Vec(rshift,       -depth,  height/2)),
@@ -227,12 +303,132 @@ public class Main extends MeshViewer {
             if (e.p1.p.x == e.p2.p.x && e.p1.p.z == e.p2.p.z) continue;
             e.shatter();
         }
+        */
+
+        /*
+         height = 4;
+         width  = 4;
+         depth  = 1;
+
+        Matrix mm = Matrix.scale(0.1f);
+        // top
+        quad(tile, mm, 
+             new Point( 2,  2,  0),
+             new Point( 1,  1, -1),
+             new Point(-1,  1, -1),
+             new Point(-2,  2,  0));
+        quad(tile, mm, 
+             new Point(-2,  2,  0),
+             new Point(-1,  1,  1),
+             new Point( 1,  1,  1),
+             new Point( 2,  2,  0));
+        quad(tile, mm, 
+             new Point( 1,  1, -1),
+             new Point( 1,  1,  1),
+             new Point(-1,  1,  1),
+             new Point(-1,  1, -1));
+
+        // bottom
+        quad(tile, mm, 
+             new Point(-2, -2,  0),
+             new Point(-1, -1, -1),
+             new Point( 1, -1, -1),
+             new Point( 2, -2,  0));
+        quad(tile, mm, 
+             new Point( 2, -2,  0),
+             new Point( 1, -1,  1),
+             new Point(-1, -1,  1),
+             new Point(-2, -2,  0));
+        quad(tile, mm, 
+             new Point(-1, -1, -1),
+             new Point(-1, -1,  1),
+             new Point( 1, -1,  1),
+             new Point( 1, -1, -1));
+
+        // left
+        quad(tile, mm, 
+             new Point( 2, -2,  0),
+             new Point( 1, -1, -1),
+             new Point( 1,  1, -1),
+             new Point( 2,  2,  0));
+        quad(tile, mm, 
+             new Point( 2,  2,  0),
+             new Point( 1,  1,  1),
+             new Point( 1, -1,  1),
+             new Point( 2, -2,  0));
+        quad(tile, mm, 
+             new Point( 1, -1, -1),
+             new Point( 1, -1,  1),
+             new Point( 1,  1,  1),
+             new Point( 1,  1, -1));
+
+        // bottom
+        quad(tile, mm, 
+             new Point(-2,  2,  0),
+             new Point(-1,  1, -1),
+             new Point(-1, -1, -1),
+             new Point(-2, -2,  0));
+        quad(tile, mm, 
+             new Point(-2, -2,  0),
+             new Point(-1, -1,  1),
+             new Point(-1,  1,  1),
+             new Point(-2,  2,  0));
+        quad(tile, mm, 
+             new Point(-1,  1, -1),
+             new Point(-1,  1,  1),
+             new Point(-1, -1,  1),
+             new Point(-1, -1, -1));
+
+        float factor = (float)Math.pow(tile.volume() / goal.volume(), 1.0/3.0);
+        goal.transform(Matrix.scale(factor/2.4f));
 
-        for(Matrix m : translations) {
+        /*        
+        translations = new Matrix[] {
+
+            Matrix.translate(new Vec(0, 0.2f,0))
+            .times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
+
+            Matrix.translate(new Vec(0,-0.2f,0))
+            .times(Matrix.rotate(new Vec(0,1,0), (float)(-1*Math.PI/2))),
+
+            //Matrix.translate(new Vec( 0.2f,0,0))
+            //.times(Matrix.rotate(new Vec(1,0,0), (float)( 1*Math.PI/2))),
+            //Matrix.translate(new Vec(-0.2f,0,0))
+            //.times(Matrix.rotate(new Vec(1,0,0), (float)(-1*Math.PI/2))),
+
+            //Matrix.translate(new Vec( 0.2f, 0,0))
+            //.times(Matrix.rotate(new Vec(0,0,1), (float)( 1*Math.PI/2)))
+            //.times(Matrix.rotate(new Vec(0,1,0), (float)( 3*Math.PI/2))),
+
+            //Matrix.translate(new Vec(-0.2f, 0,0))
+            //.times(Matrix.rotate(new Vec(0,0,1), (float)( 3*Math.PI/2)))
+            //.times(Matrix.rotate(new Vec(0,1,0), (float)( 3*Math.PI/2))),
+            
+            //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
+            //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
+            //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
+            //Matrix.rotate(new Vec(0,0,1), (float)( 1*Math.PI/2))
+            //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
+            //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
+
+            //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
+            //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
+            //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
+            //Matrix.rotate(new Vec(0,0,1), (float)( 0*Math.PI/2))
+            //.times(Matrix.translate(new Vec(0, -0.2f, 0)))
+            //.times(Matrix.rotate(new Vec(0,1,0), (float)( 1*Math.PI/2))),
+
+            Matrix.ONE,
+        };
+        */
+            
+        for(Matrix m1 : translations) {
+        for(Matrix m2 : translations) {
             for(Mesh.T t1 : tile) {
                 for(Mesh.T t2 : tile) {
                     if (t1==t2) continue;
 
+                    Matrix m = m1.inverse().times(m2);
                     if ((t1.v1().p.times(m).minus(t2.v1().p).mag() < MATCHING_EPSILON) &&
                         (t1.v2().p.times(m).minus(t2.v3().p).mag() < MATCHING_EPSILON) &&
                         (t1.v3().p.times(m).minus(t2.v2().p).mag() < MATCHING_EPSILON)) {
@@ -258,12 +454,13 @@ public class Main extends MeshViewer {
                 }
             }
         }
+        }
 
         //xMesh.Vertex mid = lbf.getE(mbn).shatter();
 
         // rescale to match volume
-        float factor = (float)Math.pow(tile.volume() / goal.volume(), 1.0/3.0);
-        goal.transform(Matrix.scale(factor));
+
+
 
         // translate to match centroid
         goal.transform(Matrix.translate(tile.centroid().minus(goal.centroid())));
@@ -299,12 +496,11 @@ public class Main extends MeshViewer {
             Thread.yield();
             repaint();
         }
-        for(int i=0; i<Math.min(oldverts,200); i++) {
+        for(int i=0; i<Math.min(oldverts,50); i++) {
             Mesh.E e = es.poll();
             verts++;
             //System.out.println("shatter " + e);
             //e.shatter(e.midpoint(), null, null, true, true);
-            
             e.shatter();
             Thread.yield();
             repaint();
@@ -312,30 +508,37 @@ public class Main extends MeshViewer {
         tile.rebindPoints();
     }
 
-    public synchronized void rand(float temp, Mesh.Vertex p) {
+    public synchronized void rand(double temp, Mesh.Vertex p) {
 
         p.reComputeErrorAround();
         double tile_error = tile.error();
         double goal_error = goal.error();
 
-        float max = p.averageEdgeLength()/10;
+        //float max = p.averageEdgeLength()/10;
+        float max = 0.01f;
+
         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);
 
+        //System.out.println(v.mag() + " " + max);
         boolean good = p.move(m, false);
-        if (!good) { /*misses++;*/ return; }
+        //if (!good) { /*misses++;*/ return; }
 
         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) / (((double)temp)/1000000));
+        double swapProbability = Math.exp((-1 * delta) / temp);
+        //System.out.println(swapProbability);
         boolean doSwap = good && (Math.random() < swapProbability);
         //boolean doSwap = good && (tile_delta <= 0 && goal_delta <= 0);
         //boolean doSwap = good && (tile_delta + goal_delta <= 0);
+
+        //if (temp < 0.000001) doSwap = good && (tile_delta <= 0 && goal_delta <= 0);
+
         if (doSwap) {
             tile_error = new_tile_error;
             goal_error = new_goal_error;
@@ -351,9 +554,9 @@ public class Main extends MeshViewer {
     float hits = 0;
     float misses = 0;
     public void anneal() throws Exception {
-        float hightemp = 1;
-        float temp = hightemp;
-        float last = 10;
+        double hightemp = 1;
+        double temp = hightemp;
+        double last = 10;
         boolean seek_upward = false;
         double acceptance = 1;
         while(true) {
@@ -361,7 +564,7 @@ public class Main extends MeshViewer {
                 double ratio = (hits+misses==0) ? 1 : (hits / (hits+misses));
                 hits = 0;
                 misses = 0;
-                float gamma = 1;
+                double gamma = 1;
                 acceptance = (ratio+acceptance)/2;
                 accepts = (int)(Math.ceil(ratio*100));
                 temps = (int)(Math.ceil(temp*1000));
@@ -372,22 +575,25 @@ public class Main extends MeshViewer {
                         breakit();
                     }
                     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.8f;
+                } else if (acceptance > 0.96) gamma = 0.1f;
+                else if (acceptance > 0.9)    gamma = 0.2f;
+                else if (acceptance > 0.8)    gamma = 0.3f;
+                else if (acceptance > 0.6)    gamma = 0.4f;
+                else if (acceptance > 0.3)    gamma = 0.6f;
                 else if (acceptance > 0.15)   gamma = 0.9f;
-                else if (acceptance > 0.05)   gamma = 0.95f;
+                else if (acceptance > 0.05)   gamma = 0.94f;
                 else if (acceptance > 0.01)   gamma = 0.98f;
                 else { /*breaks++;*/ }
 
+                /*
                 if (seek_upward) {
                     if (acceptance > 0.2) seek_upward = false;
                     else gamma = 2-gamma;
                 }
+                */
 
-                temp = temp * gamma;
+                if (anneal)
+                    temp = temp * gamma;
 
 
                 HashSet<Mesh.Vertex> hs = new HashSet<Mesh.Vertex>();
@@ -396,7 +602,7 @@ public class Main extends MeshViewer {
 
                 int count = 0;
                 long then = System.currentTimeMillis();
-                for(int i=0; i<40; i++) {
+                for(int i=0; i<400; i++) {
                     if (anneal) {
                         count++;
                         Mesh.Vertex v = pts[Math.abs(random.nextInt()) % pts.length];
@@ -407,6 +613,8 @@ public class Main extends MeshViewer {
                     Thread.yield();
                     repaint();
                 }
+
+                /*
                 PriorityQueue<Mesh.E> es = new PriorityQueue<Mesh.E>();
                 for(Mesh.T t : tile) {
                     float max = 5;
@@ -416,25 +624,26 @@ public class Main extends MeshViewer {
                         if (t.aspect() < 0.1 && e.length()>e.next.length() && e.length()>e.prev.length()) es.add(e);
                     }
                 }
-                /*
                 for(int i=0; i<5; i++) {
                     Mesh.E e = es.poll();
                     if (e==null) break;
                     e.shatter();
                 }
-                */
+
+
                 tile.rebindPoints();
+                */
+
 
                 System.out.println("temp="+temp + " ratio="+(Math.ceil(acceptance*100)) + " " +
                                    "points_per_second=" +
                                    (count*1000)/((double)(System.currentTimeMillis()-then)));
-
                 for(Mesh.Vertex p : goal.vertices()) p.recomputeFundamentalQuadricIfNeighborChanged();
 
                 synchronized(safeTriangles) {
                     safeTriangles.clear();
                     for(Mesh.T t : tile) 
-                        if (t.shouldBeDrawn())
+                        //if (t.shouldBeDrawn())
                             safeTriangles.add(t);
                 }
             }
@@ -444,7 +653,8 @@ public class Main extends MeshViewer {
 
     public static void main(String[] s) throws Exception {
         StlFile stlf = new StlFile();
-        stlf.load("fish.stl");
+        stlf.load("torus.stl");
+        //stlf.load("fish.stl");
         //stlf.load("monkey.stl");
         Frame f = new Frame();
         Main main = new Main(stlf, f);

diff --git a/src/edu/berkeley/qfat/Mesh.java b/src/edu/berkeley/qfat/Mesh.java
index 62498f8..774c7f9 100644 (file)
--- a/src/edu/berkeley/qfat/Mesh.java
+++ b/src/edu/berkeley/qfat/Mesh.java
@@ -51,7 +51,7 @@ public class Mesh implements Iterable<Mesh.T> {
     public void transform(Matrix m) {
         ArrayList<Vertex> set = new ArrayList<Vertex>();
         for(Vertex v : vertices) set.add(v);
-        for(Vertex v : set) v.transform(m.times(v.p), true);
+        for(Vertex v : set) v.transform(m.times(v.p), true, null);
     }
 
     public void rebuild() { /*vertices.rebuild();*/ }
@@ -77,7 +77,8 @@ public class Mesh implements Iterable<Mesh.T> {
 
     /** a vertex in the mesh */
     public final class Vertex extends HasQuadric implements Visitor {
-        public Point p, oldp, goodp;
+        public Point p, goodp;
+        public Point oldp;
         E e;                // some edge *leaving* this point
 
         private boolean illegal = false;
@@ -144,16 +145,17 @@ public class Mesh implements Iterable<Mesh.T> {
             if (quadric_count != 0)
                 nerror = (nerror + quadric.preAndPostMultiply(p))/(quadric_count+1);
 
+            if (!immutableVertices && quadric_count == 0)
+                nerror *= 2;
+                
             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
                 double ang = Math.abs(e.dihedralAngle());
                 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()) * 10;
                 }
-                */
             }
 
             setError(nerror);
@@ -167,43 +169,62 @@ public class Mesh implements Iterable<Mesh.T> {
             //     t2' = t2.getMatrix(t1) * M * t1
             //     t1 =     t1.getMatrix(t2) * t2
             // M * t1 = M * t1.getMatrix(t2) * t2
-            for(Vertex v : (Iterable<Vertex>)getBoundPeers())
-                good &= v.transform(v.getBindingMatrix(this).times(m).times(this.p),
-                                    ignoreProblems);
+            Point op = this.p;
+            Point pt = m.times(this.p);
+            for(Vertex v : (Iterable<Vertex>)getBoundPeers()) {
+                Point pt2 = v.getBindingMatrix(this).times(pt);
+                /*
+                if (Math.abs( v.p.minus(pt2).mag() / pt.minus(op).mag() ) > 5)
+                    throw new Error(v.p+" "+pt2+"\n"+op+" "+pt+"\n"+v.getBindingMatrix(this));
+                if (Math.abs( v.p.minus(pt2).mag() / pt.minus(op).mag() ) < 1/5) throw new Error();
+                */
+                good &= v.transform(pt2,
+                                    ignoreProblems, v.getBindingMatrix(this));
+            }
 
             for(Vertex v : (Iterable<Vertex>)getBoundPeers())
-                if (good || ignoreProblems)  v.reComputeErrorAround();
-                else                         v.transform(v.oldp, true);
-
+                v.recomputeFundamentalQuadricIfNeighborChanged();
             return good;
         }
 
         /** does NOT update bound pairs! */
-        private boolean transform(Point newp, boolean ignoreProblems) {
+        private boolean transform(Point newp, boolean ignoreProblems, Matrix yes) {
             this.oldp = this.p;
             if (immutableVertices) throw new Error();
 
             unApplyQuadricToNeighbor();
+
+
+            illegal = false;
+            if (this.p.minus(newp).mag() > 0.1 && !ignoreProblems) {
+            /*
+                try {
+                    throw new Exception(""+this.p.minus(newp).mag()+" "+ignoreProblems+" "+yes);
+                } catch(Exception e) {
+                    e.printStackTrace();
+                }
+            */
+                illegal = true;
+            }
+
             this.p = newp;
             reinsert();
             applyQuadricToNeighbor();
 
             if (!ignoreProblems) {
-                illegal = false;
                 checkLegality();
             }
-            for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) e.p2.quadricStale = true;
+            for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next)
+                e.p2.quadricStale = true;
             return !illegal;
         } 
 
         public void checkLegality() {
-            /*
             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
                 if (Math.abs(e.dihedralAngle()) > (Math.PI * 0.9) ||
                     Math.abs(e.next.dihedralAngle()) > (Math.PI * 0.9)) illegal = true;
-                if (e.t.aspect() < 0.1) illegal = true;
+                if (e.t.aspect() < 0.2) illegal = true;
             }
-            */
             if (!illegal) triangles.range(oldp, this.p, (Visitor<T>)this);
         }
 
@@ -272,40 +293,6 @@ public class Mesh implements Iterable<Mesh.T> {
         public void bindTo(Vertex p) { bindTo(Matrix.ONE, p); }
     }
 
-    public class BindingGroup {
-        private HashSet<E> set = new HashSet<E>();
-        public BindingGroup bind_others;
-        public BindingGroup other() { return bind_others; }
-        public BindingGroup(BindingGroup bind_others) { this.bind_others = bind_others; }
-        public BindingGroup() { this.bind_others = new BindingGroup(this); }
-        public BindingGroup(E e) { this(); set.add(e); }
-        public void add(E e) {
-            if (set.contains(e)) return;
-            set.add(e);
-            BindingGroup e_bind_peers = e.bind_peers;
-            BindingGroup e_bind_to    = e.bind_to;
-            e.bind_peers = this;
-            e.bind_to    = bind_others;
-            for (E epeer  : e_bind_peers.set) add(epeer);
-            for (E eother : e_bind_to.set)    bind_others.add(eother);
-            /*
-            for(E eother : bind_others.set) {
-                if (e.next.bind_to.set.contains(eother.prev)) {
-                    e.next.next.bindEdge(eother.prev.prev);
-                }
-                if (e.prev.bind_to.set.contains(eother.next)) {
-                    e.prev.prev.bindEdge(eother.next.next);
-                }
-            }
-            */
-        }
-        public void dobind(E e) {
-            for(E ebound : set) {
-                e.p1.bindTo(Matrix.ONE, ebound.p2);
-                e.p2.bindTo(Matrix.ONE, ebound.p1);
-            }
-        }
-    }
 
     /** [UNIQUE] an edge */
     public final class E extends HasBindingGroup implements Comparable<E> {
@@ -315,8 +302,6 @@ public class Mesh implements Iterable<Mesh.T> {
         E prev;  // previous half-edge
         E next;  // next half-edge
         E pair;  // partner half-edge
-        public BindingGroup bind_peers  = new BindingGroup(this);
-        public BindingGroup bind_to     = bind_peers.other();
         boolean shattered = false;
 
         public boolean intersects(T t) { return t.intersects(p1.p, p2.p); }
@@ -358,8 +343,6 @@ public class Mesh implements Iterable<Mesh.T> {
             pair._bindEdge(e.pair, m);
         }
         public void _bindEdge(E e, Matrix m) {
-            //bind_to.add(e);
-
             e = e.pair;
             /*
             //assumes edges are identical length at binding time
@@ -385,7 +368,6 @@ public class Mesh implements Iterable<Mesh.T> {
         }
         
         public void dobind() {
-            //bind_to.dobind(this);
             for(E e : (Iterable<E>)getBoundPeers()) {
                 if (e==this) continue;
                 p1.bindTo(getBindingMatrix(e), e.p1);
@@ -414,8 +396,6 @@ public class Mesh implements Iterable<Mesh.T> {
                 newT(r.p, mid,    e.p2.p, null, 0);
                 newT(l.p, mid,    e.p1.p, null, 0);
                 newT(l.p, e.p2.p, mid,    null, 0);
-                /*
-                */
             }
             for(E e : (Iterable<E>)getBoundPeers()) {
                 Point mid = e.midpoint();
@@ -430,7 +410,6 @@ public class Mesh implements Iterable<Mesh.T> {
                 e.p1.getE(mid).pair.     bindTo(e.getBindingMatrix(firste), first.pair);
                 e.p2.getE(mid).pair.     bindTo(e.getBindingMatrix(firste), firstq);
                 e.p2.getE(mid).pair.pair.bindTo(e.getBindingMatrix(firste), firstq.pair);
-                //e.p1.getE(mid).pair.prev.bindTo(e.pair.getBindingMatrix(firstx), first.pair.prev);
             }
             return null;
         }
@@ -457,10 +436,6 @@ public class Mesh implements Iterable<Mesh.T> {
             pair.next.t = null;
             pair.prev.t = null;
 
-            this.bind_to = null;
-            pair.bind_to = null;
-            this.bind_peers = null;
-            pair.bind_peers = null;
             pair.prev.next = next;
             next.prev = pair.prev;
             prev.next = pair.next;
@@ -473,7 +448,6 @@ public class Mesh implements Iterable<Mesh.T> {
             this.prev.next = this;
             this.next.prev = this;
             this.pair.pair = this;
-            bind_peers.add(this);
             if (this.next.p1 != p2) throw new Error();
             if (this.prev.p2 != p1) throw new Error();
             if (this.p1.e == null) this.p1.e = this;
@@ -499,7 +473,7 @@ public class Mesh implements Iterable<Mesh.T> {
         public void makeAdjacent(E e) {
             if (this.next == e) return;
             if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex");
-            if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free");
+            if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free ");
 
             E freeIncident = p2.getFreeIncident(e, this);
 

diff --git a/src/edu/berkeley/qfat/MeshViewer.java b/src/edu/berkeley/qfat/MeshViewer.java
index c7f9d76..e8f4586 100644 (file)
--- a/src/edu/berkeley/qfat/MeshViewer.java
+++ b/src/edu/berkeley/qfat/MeshViewer.java
@@ -151,6 +151,7 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi
     public void reshape(GLAutoDrawable drawable, int x, int y, int width, int height) { }
     public void displayChanged(GLAutoDrawable drawable, boolean modeChanged, boolean deviceChanged) { }
     public void display(GLAutoDrawable drawable) {
+
         if (translations==null) return;
 
         glcanvas.setSize(f.getWidth(), f.getHeight() - 100);
@@ -198,6 +199,7 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi
         gl.glColor4f(1,1,1,1);
         for(Matrix m : translations) {
             //if (v1.z==0 && v1.y==0) continue;
+            //if (i>0) continue;
             i++;
             /*
             Point p = new Point(0, 0, 0).times(m);
@@ -239,7 +241,12 @@ public class MeshViewer implements GLEventListener, MouseListener, MouseMotionLi
                 case 5: gl.glColor4f((float)0.25, (float)0.75, (float)0.75, (float)0.3); break;
                 case 6: gl.glColor4f((float)0.75, (float)0.25, (float)0.75, (float)0.3); break;
             }
-            //gl.glColor4f((float)0.75, (float)0.25, (float)0.25, (float)0.3);
+            /*
+            if (t.e1().pair.t==null) gl.glColor4f((float)0.25, (float)0.25, (float)0.75, (float)0.3);
+            else if (t.e2().pair.t==null) gl.glColor4f((float)0.25, (float)0.25, (float)0.75, (float)0.3);
+            else if (t.e3().pair.t==null) gl.glColor4f((float)0.25, (float)0.25, (float)0.75, (float)0.3);
+            else  gl.glColor4f((float)0.75, (float)0.25, (float)0.25, (float)0.3);
+            */
             //gl.glBegin(GL.GL_LINES);
 
             if (triangles) {

diff --git a/src/edu/berkeley/qfat/geom/BindingGroup.java b/src/edu/berkeley/qfat/geom/BindingGroup.java
index 5f6bf2b..fbd1879 100644 (file)
--- a/src/edu/berkeley/qfat/geom/BindingGroup.java
+++ b/src/edu/berkeley/qfat/geom/BindingGroup.java
@@ -20,10 +20,13 @@ public class BindingGroup<T extends HasBindingGroup> implements Iterable<T> {
             matrices.put((T)hbg, bg.matrices.get(hbg).times(m));
             hbg.bindingGroup = this;
         }
+        HashSet<HasBindingGroup> stuff = new HashSet<HasBindingGroup>();
         for(HasBindingGroup hbg : bg.matrices.keySet())
-            hbg.bindingGroupChanged(this);
+            stuff.add(hbg);
         bg.matrices.clear();
         bg.master = null;
+        for(HasBindingGroup hbg : stuff)
+            hbg.bindingGroupChanged(this);
     }
 
     public T getMaster() { return master; }

diff --git a/src/edu/berkeley/qfat/geom/HalfSpace.java b/src/edu/berkeley/qfat/geom/HalfSpace.java
new file mode 100644 (file)
index 0000000..ebbd796
--- /dev/null
+++ b/src/edu/berkeley/qfat/geom/HalfSpace.java
@@ -0,0 +1,36 @@
+package edu.berkeley.qfat.geom;
+import javax.media.opengl.*;
+
+public final class HalfSpace extends Plane {
+
+    public HalfSpace(Point p, Vec norm) { super(p, norm); }
+
+    /*
+    public Segment clip(Segment s) {
+        // FIXME: return null if segment is entirely excluded
+        throw new Error();
+    }
+
+
+    public Point intersect(Segment s) {
+    }
+
+    public HalfPlane intersect(Plane p) {
+        if (norm.minus(hs.norm).mag() < 0.001)
+            throw new Error("half-spaces are nearly parallel");
+        
+    }
+    */
+
+    public boolean contains(Point p) {
+        float checker = p.x*norm.x+p.y*norm.y+p.z*norm.z + dvalue;
+        //System.out.println(norm+" "+dvalue+" contains " + p + " => " + checker);
+        return checker <= 0.00001;
+    }
+
+    public boolean contains(HalfSpace hs) {
+        // FIXME
+        return false;
+    }
+    
+}

diff --git a/src/edu/berkeley/qfat/geom/HasBindingGroup.java b/src/edu/berkeley/qfat/geom/HasBindingGroup.java
index 064b657..ad9ee31 100644 (file)
--- a/src/edu/berkeley/qfat/geom/HasBindingGroup.java
+++ b/src/edu/berkeley/qfat/geom/HasBindingGroup.java
@@ -18,10 +18,17 @@ public abstract class HasBindingGroup {
         if (other.bindingGroup == this.bindingGroup) {
             if (getBindingMatrix(other).equals(bindingMatrix))
                 return;
+            /*
             throw new Error("rebind attempt: "+this+" and "+other+" with "
                             + bindingMatrix
                             + "; expected "
                             + getBindingMatrix(other));
+            */
+            System.err.println("WARNING: discarding rebind attempt: "+this+" and "+other+" with "
+                               + bindingMatrix
+                               + "; expected "
+                               + getBindingMatrix(other));
+            return;
         }
 
         bindingMatrix =

diff --git a/src/edu/berkeley/qfat/geom/Matrix.java b/src/edu/berkeley/qfat/geom/Matrix.java
index dbe4076..eeeb68f 100644 (file)
--- a/src/edu/berkeley/qfat/geom/Matrix.java
+++ b/src/edu/berkeley/qfat/geom/Matrix.java
@@ -71,6 +71,22 @@ public class Matrix {
                           0, 0, 0, 1);
     }
 
+    public static Matrix reflect(Vec v) {
+        Vec reflectionPlaneNormal = v.norm();
+        float a = reflectionPlaneNormal.x;
+        float b = reflectionPlaneNormal.y;
+        float c = reflectionPlaneNormal.z;
+        return
+                new Matrix( 1-2*a*a,  -2*a*b,  -2*a*c, 0,
+                            -2*a*b,  1-2*b*b,  -2*b*c, 0,
+                            -2*a*c,   -2*b*c, 1-2*c*c, 0,
+                            0,       0,       0,       1);
+    }
+
+    public Vec getTranslationalComponent() {
+        return new Vec(d, h, l);
+    }
+
     public Matrix plus(Matrix x) {
         return new Matrix(a+x.a, b+x.b, c+x.c, d+x.d, e+x.e, f+x.f, g+x.g, h+x.h, i+x.i, j+x.j, k+x.k, l+x.l, m+x.m, n+x.n, o+x.o, p+x.p);
     }

diff --git a/src/edu/berkeley/qfat/geom/Plane.java b/src/edu/berkeley/qfat/geom/Plane.java
new file mode 100644 (file)
index 0000000..1f79b06
--- /dev/null
+++ b/src/edu/berkeley/qfat/geom/Plane.java
@@ -0,0 +1,24 @@
+package edu.berkeley.qfat.geom;
+import javax.media.opengl.*;
+
+public class Plane {
+
+    public final Vec norm;
+    public final float dvalue;
+
+    public Plane(Point p, Vec norm) {
+        this.norm = norm.norm();
+        this.dvalue = p.x*this.norm.x+p.y*this.norm.y+p.z*this.norm.z;
+    }
+
+    public Point intersect(Plane p1, Plane p2) {
+        Plane p3 = this;
+        float z = p1.norm.dot(p2.norm.cross(p3.norm));
+        if (Math.abs(z) == 0) return null;  // planes do not intersect at a point
+        Vec v1 = p2.norm.cross(p3.norm).times(-1 * p1.dvalue);
+        Vec v2 = p3.norm.cross(p1.norm).times(-1 * p2.dvalue);
+        Vec v3 = p1.norm.cross(p2.norm).times(-1 * p3.dvalue);
+        return Point.ORIGIN.plus(v1.plus(v2).plus(v3).times(1/z));
+    }
+
+}

diff --git a/src/edu/berkeley/qfat/geom/Polygon.java b/src/edu/berkeley/qfat/geom/Polygon.java
new file mode 100644 (file)
index 0000000..e2d3bc5
--- /dev/null
+++ b/src/edu/berkeley/qfat/geom/Polygon.java
@@ -0,0 +1,66 @@
+package edu.berkeley.qfat.geom;
+import javax.media.opengl.*;
+import java.util.*;
+import edu.berkeley.qfat.Mesh;
+
+// FIXME: numerical stability issues galore
+/** a planar, convex, possibly infinite/open polygon */
+public final class Polygon {
+
+    public final Plane plane;
+    
+    private final HalfSpace[] halfSpaces;
+
+    public Polygon(Plane plane) { this(plane, new HalfSpace[0]); }
+
+    public Polygon(Plane plane, HalfSpace[] halfSpaces) {
+        this.plane = plane;
+        this.halfSpaces = halfSpaces;
+    }
+
+    public Polygon intersect(HalfSpace hs) {
+        HalfSpace[] newHalfSpaces = new HalfSpace[halfSpaces.length+1];
+        System.arraycopy(halfSpaces, 0, newHalfSpaces, 0, halfSpaces.length);
+        newHalfSpaces[newHalfSpaces.length-1] = hs;
+        return new Polygon(plane, newHalfSpaces);
+    }
+
+    public Triangle[] tesselate(Mesh mesh) {
+        // FIXME: check for closedness
+        // find a starting point
+        HashSet<Segment> segments = new HashSet<Segment>();
+        int i;
+        for(i=0; i<halfSpaces.length; i++) {
+            Point p1=null, p2=null;
+            for(int j=0; j<halfSpaces.length; j++) {
+                if (i==j) continue;
+                Point p = plane.intersect(halfSpaces[i], halfSpaces[j]);
+                if (p==null) continue;
+                for(int k=0; k<halfSpaces.length; k++) {
+                    if (i==k || j==k) continue;
+                    //if (!halfSpaces[k].contains(p)) { p = null; break; }
+                }
+                if (p!=null) {
+                    if (p1==null) p1 = p;
+                    else if (p2==null) { if (!p.equals(p1)) p2 = p; }
+                    else throw new Error();
+                }
+            }
+            if (p1!=null && p2!=null) {
+                System.out.println("new segment: " + p1 + " " + p2);
+                segments.add(new Segment(p1, p2));
+            }
+        }
+        Vec cen = new Vec(0,0,0);
+        for(Segment s : segments)
+            cen = cen.plus(s.p1.minus(Point.ORIGIN)).plus(s.p2.minus(Point.ORIGIN));
+        Point centroid = Point.ORIGIN.plus(cen.times(1f/(2*segments.size())));
+        for(Segment s : segments) {
+            System.out.println("newt! " + s.p1 + " " + centroid + " " + s.p2 + " " + plane.norm.times(-1));
+            mesh.newT(s.p1, centroid, s.p2, plane.norm.times(-1), 0);
+        }
+        System.out.println("done");
+        return null;
+    }
+
+}

diff --git a/src/edu/berkeley/qfat/geom/Segment.java b/src/edu/berkeley/qfat/geom/Segment.java
index 8a1febd..576bb75 100644 (file)
--- a/src/edu/berkeley/qfat/geom/Segment.java
+++ b/src/edu/berkeley/qfat/geom/Segment.java
@@ -9,6 +9,15 @@ public class Segment implements HasBoundingBox {
 
     public Segment(Point p1, Point p2) { this.p1 = p1; this.p2 = p2; }
 
+    public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
+    public boolean equals(Object o) {
+        if (o==null || !(o instanceof Segment)) return false;
+        Segment seg = (Segment)o;
+        if (seg.p1.equals(p1) && seg.p2.equals(p2)) return true;
+        if (seg.p2.equals(p1) && seg.p1.equals(p2)) return true;
+        return false;
+    }
+
     public float getMaxX() { return Math.max(p1.x, p2.x); }
     public float getMinX() { return Math.min(p1.x, p2.x); }
     public float getMaxY() { return Math.max(p1.y, p2.y); }