X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2FGeom.java;h=a30b9a77c8cbc74469dfb82790d45404d556d5a0;hb=b987cd997410c14c4ce5076d3aa39c7903b62b2f;hp=c879bfed1acb27b5d8b5423d2253ef6fb8e93732;hpb=8a19e3f30ae67231e204c28d5ec93e5a6d812861;p=anneal.git

diff --git a/src/Geom.java b/src/Geom.java
index c879bfe..a30b9a7 100644
--- a/src/Geom.java
+++ b/src/Geom.java
@@ -5,23 +5,58 @@ import javax.swing.*;
 import javax.media.opengl.*;
 import javax.media.opengl.glu.*;
 
-public class Geom {
+public class Geom implements Iterable<Geom.T> {
+
+    public static float EPSILON = (float)0.000001;
 
     private HashMap<P,P> ps = new HashMap<P,P>();
+    private HashMap<E,E> es = new HashMap<E,E>();
+    private HashSet<T>   ts = new HashSet<T>();
+
+    public Iterator<T> iterator() { return ts.iterator(); }
 
     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);
+        ps.put(p,p);
         return p;
     }
+    
+    public E newE(P p1, P p2) {
+        E e = new E(p1, p2);
+        E e2 = es.get(e);
+        if (e2 != null) return e2;
+        es.put(e,e);
+        return e;
+    }
 
-    /** point in 3-space */
-    public class P {
+    public T newT(E e1, E e2, E e3, V norm) {
+        P p1 = e1.shared(e2);
+        P p2 = e2.shared(e3);
+        P p3 = e3.shared(e1);
+        V norm2 = p2.minus(p1).cross(p3.minus(p1));
+        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) { E t = e1; e1 = e3; e2 = e2; e3 = t; }
+        if (e1.t1 != null && e1.t1.hasE(e1) && e1.t1.hasE(e2) && e1.t1.hasE(e3)) return e1.t1;
+        if (e1.t2 != null && e1.t2.hasE(e1) && e1.t2.hasE(e2) && e1.t2.hasE(e3)) return e1.t2;
+        if (e2.t1 != null && e2.t1.hasE(e1) && e2.t1.hasE(e2) && e2.t1.hasE(e3)) return e2.t1;
+        if (e2.t2 != null && e2.t2.hasE(e1) && e2.t2.hasE(e2) && e2.t2.hasE(e3)) return e2.t2;
+        if (e3.t1 != null && e3.t1.hasE(e1) && e3.t1.hasE(e2) && e3.t1.hasE(e3)) return e3.t1;
+        if (e3.t2 != null && e3.t2.hasE(e1) && e3.t2.hasE(e2) && e3.t2.hasE(e3)) return e3.t2;
+        T ret = new T(e1, e2, e3);
+        ts.add(ret);
+        return ret;
+    }
+
+    /** [UNIQUE] point in 3-space */
+    public final class P {
         public final float x, y, z;
+        private T t = null;  // any of the triangles incident at this point
         public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
-        public V minus(P p) { return null; }
+        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 boolean equals(Object o) {
             if (o==null || !(o instanceof P)) return false;
             P p = (P)o;
@@ -33,22 +68,44 @@ public class Geom {
                 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() {
+            if (t==null) throw new Error("attempt to get vertex normal for point which does not belong to any triangles");
+            T ti = t;
+            V norm = new V(0, 0, 0);
+            do {
+                norm = norm.plus(ti.norm().times((float)ti.angle(this)));
+                ti = ti.next(this);
+            } while(ti != t);
+            return norm.norm();
+        }
     }
 
     /** vector in 3-space */
-    public class V {
+    public final class V {
         private final float x, y, 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() { float m = mag(); return new V(x/m, y/m, z/m); }
+        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 String toString() { return "<"+x+","+y+","+z+">"; }
     }
 
-    /** an edge */
-    public 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; }
+        T t1, t2;
+        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;
+        }
+        public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
+        public float length() { return p1.minus(p2).mag(); }
         public boolean equals(Object o) {
             if (o==null || !(o instanceof E)) return false;
             E e = (E)o;
@@ -56,26 +113,58 @@ public class Geom {
             if (this.p2 == e.p1 && this.p1 == e.p2) return true;
             return false;
         }
-        public P shared(E e) { return null; }
+        public P shared(E e) {
+            if (p1==e.p1) return p1;
+            if (p1==e.p2) return p1;
+            if (p2==e.p1) return p2;
+            if (p2==e.p2) return p2;
+            throw new Error("no shared vertex in shared()");
+        }
+        public P unshared(E e) {
+            if (p1==e.p1) return p2;
+            if (p1==e.p2) return p2;
+            if (p2==e.p1) return p1;
+            if (p2==e.p2) return p1;
+            throw new Error("no shared vertex in unshared()");
+        }
+        public T other(T t) {
+            if (t1==t) return t2;
+            if (t2==t) return t1;
+            throw new Error("edge " + this + " does not own triangle " + t);
+        }
+        public P other(P p) {
+            if (p==p1) return p2;
+            if (p==p2) return p1;
+            throw new Error("edge " + this + " does not own point " + p);
+        }
     }
 
-    /** a triangle (face) */
-    public class T {
+    /** [UNIQUE] a triangle (face) */
+    public final 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;
-            } else {
-                this.e1 = e3;
-                this.e2 = e2;
-                this.e3 = e1;
-            }
+        T(E e1, E e2, E e3) {
+            if (e1.p1.t==null) e1.p1.t = this;
+            if (e1.p2.t==null) e1.p2.t = this;
+            if (e2.p1.t==null) e2.p1.t = this;
+            if (e2.p2.t==null) e2.p2.t = this;
+            if (e3.p1.t==null) e3.p1.t = this;
+            if (e3.p2.t==null) e3.p2.t = this;
+            if (e1==e2) throw new Error("attempt to create triangle with duplicate edge: " + e1);
+            if (e2==e3) throw new Error("attempt to create triangle with duplicate edge: " + e2);
+            if (e3==e1) throw new Error("attempt to create triangle with duplicate edge: " + e3);
+            // check that each pair of edges shares a vertex
+            e1.shared(e2);
+            e2.shared(e3);
+            e3.shared(e1);
+            this.e1 = e1;
+            this.e2 = e2;
+            this.e3 = e3;
+            // FEATURE: colinearity/sliverness check?
+            if (e1.t1 == null) e1.t1 = this; else if (e1.t2 == null) e1.t2 = this; else throw new Error("non-manifold surface");
+            if (e2.t1 == null) e2.t1 = this; else if (e2.t2 == null) e2.t2 = this; else throw new Error("non-manifold surface");
+            if (e3.t1 == null) e3.t1 = this; else if (e3.t2 == null) e3.t2 = this; else throw new Error("non-manifold surface");
+            // FIXME: check that triangles we share an edge with agree on the direction of the normal vector
+            // FIXME: check for sealed/watertight surface once construction is complete (an infer normal(s)?)
         }
         public V norm() {
             P p1 = e1.shared(e2);
@@ -83,7 +172,48 @@ public class Geom {
             P p3 = e3.shared(e1);
             return p2.minus(p1).cross(p3.minus(p1)).norm();
         }
-        public T(E e1, E e2, E e3) { this.e1 = e1; this.e2 = e2; this.e3 = e3; }
+        public boolean hasE(E e) { return e1==e || e2==e || e3==e; }
+        public void glVertices(GL gl) {
+            p1().glVertex(gl);
+            p2().glVertex(gl);
+            p3().glVertex(gl);
+        }
+        public P p1() { return e1.shared(e2); }
+        public P p2() { return e1.shared(e3); }
+        public P p3() { return e3.shared(e2); }
+        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;
+        }
+
+        // FIXME: ambiguity firstEdge or secondEdge?
+        /** returns the next triangle walking "around" shared vertex p */
+        public T next(P p) { return secondEdge(p).other(this); }
+
+        public E firstEdge(P p) {
+            if      (p == e1.shared(e2)) return e1;
+            else if (p == e2.shared(e3)) return e2;
+            else if (p == e3.shared(e1)) return e3;
+            else throw new Error("triangle " + this + " does not own point " + p);
+        }
+
+        public E secondEdge(P p) {
+            if      (p == e1.shared(e2)) return e2;
+            else if (p == e2.shared(e3)) return e3;
+            else if (p == e3.shared(e1)) return e1;
+            else throw new Error("triangle " + this + " does not own point " + p);
+        }
+
+        /** returns the angle at point p */
+        public double angle(P p) {
+            V v1 = firstEdge(p).other(p).minus(p);
+            V v2 = secondEdge(p).other(p).minus(p);
+            return Math.acos(v1.norm().dot(v2.norm()));
+        }
+
     }
 
     /** matrix */