X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2FGeom.java;h=316e33468c56d865ed0bd5a6378d13fe14abdf14;hb=a3aad0bab8b523ead43362277b5d04a14e178cfb;hp=fec07b576244af63cc7daec946b0b22fc77aba1f;hpb=77132d13c4434fa3e320d4516e98c1d8a7df21cc;p=anneal.git

diff --git a/src/Geom.java b/src/Geom.java
index fec07b5..316e334 100644
--- a/src/Geom.java
+++ b/src/Geom.java
@@ -1,164 +1,383 @@
 import java.awt.*;
+import java.util.*;
 import java.awt.event.*;
 import javax.swing.*;
 import javax.media.opengl.*;
 import javax.media.opengl.glu.*;
+import edu.wlu.cs.levy.CG.KDTree;
 
-public class Geom implements GLEventListener {
-
-    public static StlFile stlf = null;
-
-    /**
-     * Take care of initialization here.
-     */
-    public void init(GLAutoDrawable gld) {
-        GL gl = gld.getGL();
-        GLU glu = new GLU();
-        gl.glClearColor(0.0f, 0.0f, 0.0f, 1.0f);
-        gl.glViewport(0, 0, 500, 300);
-        gl.glMatrixMode(GL.GL_PROJECTION);
-        gl.glLoadIdentity();
-        //glu.gluOrtho2D(0.0, 500.0, 0.0, 300.0);
-        display(gld);
-    }
+public class Geom implements Iterable<Geom.T> {
+
+    private KDTree kd = new KDTree(3);
+
+    public static float EPSILON = (float)0.000001;
+    public static Random random = new Random();
+
+    private HashMap<P,P> ps = new HashMap<P,P>();
+    private HashSet<T>   ts = new HashSet<T>();
+
+    public Iterator<T> iterator() { return ts.iterator(); }
 
+    public P newP(double x, double y, double z) { return newP((float)x, (float)y, (float)z); }
+    public P newP(float x, float y, float z) {
+        P p = new P(x, y, z);
+        P p2 = ps.get(p);
+        if (p2 != null) return p2;
+        ps.put(p,p);
+        p.name = allname++;
+        try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); }
+        return p;
+    }
+    
+    public T newT(P p12, P p23, P p31, V norm) {
+        V norm2 = p31.minus(p12).cross(p23.minus(p12));
+        float dot = norm.dot(norm2);
+        if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
+        if (dot < 0) { P p = p12; p12=p23; p23 = p; }
+        return newT(p12, p23, p31);
+    }
 
-    /**
-     * Take care of drawing here.
-     */
-    public void display(GLAutoDrawable drawable) {
-        float red = 0.0f;
-        float green = 0.0f;
-        float blue = 0.0f;
-        GL gl = drawable.getGL();
-        gl.glClear(GL.GL_COLOR_BUFFER_BIT);
-        gl.glPointSize(5.0f);
-
-        for(int i=0; i<stlf.coordArray.length; i+=3) {
-            red -= .09f;
-            green -= .12f;
-            blue -= .15f;
-            if (red < 0.15) red = 1.0f;
-            if (green < 0.15) green = 1.0f;
-            if (blue < 0.15) blue = 1.0f;
-            gl.glColor3f(red, green, blue);
-
-            gl.glBegin(GL.GL_TRIANGLES);
-            for(int j=0; j<3; j++)
-                gl.glVertex3f(stlf.coordArray[i+j].x,
-                              stlf.coordArray[i+j].y,
-                              stlf.coordArray[i+j].z);
-            gl.glEnd();
+    public T newT(P p1, P p2, P p3) {
+        E e12 = p1.makeE(p2);
+        E e23 = p2.makeE(p3);
+        E e31 = p3.makeE(p1);
+        while(e12.next != e23 || e23.next != e31 || e31.next != e12) {
+            e12.makeAdjacent(e23);
+            e23.makeAdjacent(e31);
+            e31.makeAdjacent(e12);
         }
+        T ret = e12.makeT();
+        if (e12.t == null) throw new Error();
+        if (e23.t == null) throw new Error();
+        if (e31.t == null) throw new Error();
+        return ret;
     }
 
+    private char allname = 'A';
 
-    public void reshape(
-                        GLAutoDrawable drawable,
-                        int x,
-                        int y,
-                        int width,
-                     int height
-                        ) {}
-    public void displayChanged(
-                               GLAutoDrawable drawable,
-                               boolean modeChanged,
-                            boolean deviceChanged
-                               ) {}
-
-    /** point in 3-space */
-    public static class P {
-        public final float x, y, z;
-        public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
-        public V minus(P p) { return null; }
+    /** [UNIQUE] point in 3-space */
+    public final class P {
+        char name;
+
+        float x, y, z;
+
+        private E e;                // some edge *leaving* this point
+        private M binding = new M();
+        private P bound_to = this;
+
+        public E makeE(P p2) {
+            E e = getE(p2);
+            if (e != null) return e;
+            e = p2.getE(this);
+            if (this.e == null && p2.e == null) return this.e = new E(this, p2);
+            if (this.e == null && p2.e != null) return p2.makeE(this).pair;
+            return new E(getFreeIncident(), p2);
+        }
+
+        public E getFreeIncident() {
+            E ret = getFreeIncident(e, e);
+            if (ret != null) return ret;
+            ret = getFreeIncident(e.pair.next, e.pair.next);
+            if (ret == null) throw new Error("unable to find free incident to " + this);
+            return ret;
+        }
+
+        public E getFreeIncident(E start, E before) {
+            E e = start;
+            do {
+                if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null) return e.pair;
+                e = e.pair.next;
+            } while(e != before);
+            return null;
+        }
+
+        public E getE(P p2) {
+            E e = this.e;
+            do {
+                if (e==null) return null;
+                if (e.p1 == this && e.p2 == p2) return e;
+                e = e.pair.next;
+            } while (e!=this.e);
+            return null;
+        }
+
+        public boolean isBoundTo(P p) {
+            P px = p;
+            do {
+                if (px==this) return true;
+                px = px.bound_to;
+            } while(px != p);
+            return false;
+        }
+
+        public void unbind() { bound_to = null; binding = null; }
+        public void bind(P p) { bind(p, new M()); }
+        public void bind(P p, M binding) {
+            if (isBoundTo(p)) return;
+            P temp_bound_to = p.bound_to;
+            M temp_binding = p.binding;
+            p.bound_to = this.bound_to;
+            p.binding = binding.times(this.binding); // FIXME: may have order wrong here
+            this.bound_to = temp_bound_to;
+            this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
+        }
+
+        public void move(V v) {
+            P p = this;
+            do {
+                p.x = p.x+v.x;
+                p.y = p.y+v.y;
+                p.z = p.z+v.z;
+                v = v.times(binding);
+                p = p.bound_to;
+            } while (p != this);
+        }
+
+        public P(float x, float y, float z) {
+            this.x = x; this.y = y; this.z = z;
+        }
+
+        public P nearest() {
+            Object[] results;
+            try { results = kd.nearest(new double[]{x,y,z},2); } catch (Exception e) { throw new Error(e); }
+            if (results[0] != this) throw new Error();
+            return (P)results[1];
+        }
+
+        public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
+        public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
+        public P times(M m) { return m.apply(this); }
+        public boolean equals(Object o) {
+            if (o==null || !(o instanceof P)) return false;
+            P p = (P)o;
+            return p.x==x && p.y==y && p.z==z;
+        }
+        // FIXME: moving a point alters its hashCode
+        public int hashCode() {
+            return
+                Float.floatToIntBits(x) ^
+                Float.floatToIntBits(y) ^
+                Float.floatToIntBits(z);
+        }
+        public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
+        public String toString() { return "("+x+","+y+","+z+")"; }
+        public V norm() {
+            V norm = new V(0, 0, 0);
+            E e = this.e;
+            do {
+                if (e.t != null) norm = norm.plus(e.t.norm().times((float)e.prev.angle()));
+                e = e.pair.next;
+            } while(e != this.e);
+            return norm.norm();
+        }
     }
 
     /** vector in 3-space */
-    public static class V {
-        private final float x, y, z;
+    public final class V {
+        public final float x, y, z;
+        public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
         public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
-        public V norm() { return null; /* FIXME */ }
-        public boolean sameDirection(V v) { throw new Error(); }
-        public V cross(V v) { return null; }
+        public V cross(V v) { return new V(y*v.z-z*v.y, z*v.x-x*v.z, x*v.y-y*v.x); }
+        public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
+        public V norm() { return div(mag()); }
+        public V times(M m) { return m.apply(this); }
+        public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
+        public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
+        public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
+        public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
+        public String toString() { return "<"+x+","+y+","+z+">"; }
     }
 
-    /** an edge */
-    public static class E {
+    /** [UNIQUE] an edge */
+    public final class E {
         public final P p1, p2;
-        private T t1, t2;
-        public E(P p1, P p2) { this.p1 = p1; this.p2 = p2; }
-        public boolean equals(Object o) {
-            if (o==null || !(o instanceof E)) return false;
-            E e = (E)o;
-            if (this.p1 == e.p1 && this.p2 == e.p2) return true;
-            if (this.p2 == e.p1 && this.p1 == e.p2) return true;
-            return false;
+        T t;     // triangle to our "left"
+        E prev;  // previous half-edge
+        E next;  // next half-edge
+        E pair;  // partner half-edge
+
+
+        public E bound_to = this;
+
+        public void bind(E e) { bind(e, new M()); }
+        public void bind(E e, M m) {
+            E old = this.bound_to;
+            this.bound_to = e.bound_to;
+            e.bound_to = old;
+        }
+
+        public void dobind() {
+            for(E ex = bound_to; ex != this; ex = ex.bound_to) {
+                p1.bind(ex.p1);
+                p2.bind(ex.p2);
+            }
+        }
+
+        public boolean destroyed = false;
+        public void shatter() {
+            if (destroyed) return;
+            /*
+            HashSet<E> eh = new HashSet<E>();
+            eh.add(this);
+            for(E ex = bound_to; ex != this; ex = ex.bound_to) eh.add(ex);
+            E[] es = (E[])eh.toArray(new E[0]);
+            */
+            destroy();
+            pair.shatter();
+            for(E ex = bound_to; ex != this; ex = ex.bound_to) ex.shatter();
+        }
+        public void destroy() {
+            this.destroyed = true;
+        }
+
+        private void sync() {
+            this.prev.next = this;
+            this.next.prev = this;
+            this.pair.pair = 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;
+        }
+
+        public T makeT() { return t==null ? (t = new T(this)) : t; }
+
+        /** angle between this half-edge and the next */
+        public double angle() {
+            V v1 = next.p2.minus(p2);
+            V v2 = this.p1.minus(p2);
+            return Math.acos(v1.norm().dot(v2.norm()));
+        }
+
+        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");
+
+            E freeIncident = p2.getFreeIncident(e, this);
+
+            e.prev.next = freeIncident.next;
+            freeIncident.next.prev = e.prev;
+
+            freeIncident.next = this.next;
+            this.next.prev = freeIncident;
+            
+            this.next = e;
+            e.prev = this;
+
+            sync();
+            freeIncident.sync();
         }
-        public P shared(E e) { return null; }
-    }
 
-    /** a triangle (face) */
-    public static class T {
-        public final E e1, e2, e3;
-        public T(E e1, E e2, E e3, V normal) {
-            P p1 = e1.shared(e2);
-            P p2 = e2.shared(e3);
-            P p3 = e3.shared(e1);
-            V norm = p2.minus(p1).cross(p3.minus(p1));
-            if (norm.sameDirection(normal)) {
-                this.e1 = e1;
-                this.e2 = e2;
-                this.e3 = e3;
+        /** creates an isolated edge out in the middle of space */
+        public E(P p1, P p2) {
+            if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
+            this.p1 = p1;
+            this.p2 = p2;
+            this.prev = this.next = this.pair = new E(this, this, this);
+            sync();
+        }
+
+        /** adds a new half-edge from prev.p2 to p2 */
+        public E(E prev, P p2) {
+            this.p1 = prev.p2;
+            this.p2 = p2;
+            this.prev = prev;
+            if (p2.getE(p1) != null) throw new Error();
+            if (p2.e==null) {
+                this.next = this.pair = new E(this, this, prev.next);
             } else {
-                this.e1 = e3;
-                this.e2 = e2;
-                this.e3 = e1;
+                E q = p2.getFreeIncident();
+                this.next = q.next;
+                this.next.prev = this;
+                E z = prev.next;
+                this.prev.next = this;
+                this.pair = new E(q, this, z);
             }
+            sync();
         }
-        public V norm() {
-            P p1 = e1.shared(e2);
-            P p2 = e2.shared(e3);
-            P p3 = e3.shared(e1);
-            return p2.minus(p1).cross(p3.minus(p1)).norm();
+
+        /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */
+        public E(E prev, E pair, E next) {
+            this.p1 = prev.p2;
+            this.p2 = next.p1;
+            this.prev = prev;
+            this.next = next;
+            this.pair = pair;
+            sync();
         }
-        public T(E e1, E e2, E e3) { this.e1 = e1; this.e2 = e2; this.e3 = e3; }
+        public P midpoint() { return newP((p1.x+p2.x)/2, (p1.y+p2.y)/2, (p1.z+p2.z)/2); }
+        public boolean has(P p) { return p==p1 || p==p2; }
+        public float length() { return p1.minus(p2).mag(); }
+        public String toString() { return p1+"->"+p2; }
     }
 
-    /** matrix */
-    public static class M {
+    /** [UNIQUE] a triangle (face) */
+    public final class T {
+        public final E e1;
+        public final int color;
+
+        T(E e1) {
+            this.e1 = e1;
+            E e2 = e1.next;
+            E e3 = e2.next;
+            if (e1==e2     || e1==e3) throw new Error();
+            if (e3.next!=e1) throw new Error();
+            if (e1.t!=null || e2.t!=null || e3.t!=null)
+                throw new Error("non-manifold surface or disagreeing normals");
+            e1.t = this;
+            e1.next.t = this;
+            e1.next.next.t = this;
+
+            // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
+
+            int color = Math.abs(random.nextInt());
+            while(true) {
+                color = color % 4;
+                if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; }
+                if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; }
+                if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
+                break;
+            }
+
+            // FIXME unnecssary
+            ts.add(this);
+
+            this.color = color;
+        }
+        public P p1() { return e1.p1; }
+        public P p2() { return e1.p2; }
+        public P p3() { return e1.next.p2; }
+        public E e1() { return e1; }
+        public E e2() { return e1.next; }
+        public E e3() { return e1.prev; }
+        public V norm() { return p2().minus(p1()).cross(p3().minus(p1())).norm(); }
+        public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
+        public boolean has(P p) { return p1()==p || p2()==p || p3()==p; }
+        public void glVertices(GL gl) {
+            p1().glVertex(gl);
+            p2().glVertex(gl);
+            p3().glVertex(gl);
+        }
+
+        public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
+                                          (p1().y+p2().y+p3().y)/3, 
+                                          (p1().z+p2().z+p3().z)/3); }
+        public float diameter() {
+            // FIXME: what is this supposed to be?
+            return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2;
+        }
+
+
     }
 
-    public static void main(String[] s) throws Exception {
-        stlf = new StlFile();
-        stlf.load("teapot.stl");
-        /*
-        for(int i=0; i<stlf.coordArray.length; i+=3) {
-            System.out.println("triangle: (" +
-                               stlf.coordArray[i+0] + ", " +
-                               stlf.coordArray[i+1] + ", " +
-                               stlf.coordArray[i+2] + ")");
-        }
-
-    gi.setCoordinates();
-    gi.setNormals(normArray);
-    gi.setStripCounts(stripCounts);
-
-        GeometryInfo gi = ;
-        ga.convertToIndexedTriangles();
-        GeometryArray ga = ;
-        ga.convertToIndexedTriangles();
-        */
-
-        Geom geom = new Geom();
-        
-
-        Frame f = new Frame();
-        GLCapabilities glcaps = new GLCapabilities();
-        GLCanvas glcanvas = new GLCanvas();
-        glcanvas.addGLEventListener(geom);
-        f.add(glcanvas, BorderLayout.CENTER);
-        f.show();
-        f.setSize(500, 300);
+
+    /** matrix */
+    public class M {
+        public M() { }
+        public P apply(P p) { return p; }
+        public V apply(V v) { return v; }
+        public M invert() { return this; }
+        public M times(M m) { return this; }
     }
 
 }