src/Geom.java

   1 import java.awt.*;
   2 import java.util.*;
   3 import java.awt.event.*;
   4 import javax.swing.*;
   5 import javax.media.opengl.*;
   6 import javax.media.opengl.glu.*;
   7
   8 public class Geom implements Iterable<Geom.T> {
   9
  10     public static float EPSILON = (float)0.000001;
  11
  12     private HashMap<P,P> ps = new HashMap<P,P>();
  13     private HashMap<E,E> es = new HashMap<E,E>();
  14     private HashSet<T>   ts = new HashSet<T>();
  15
  16     public Iterator<T> iterator() { return ts.iterator(); }
  17
  18     public P newP(float x, float y, float z) {
  19         P p = new P(x, y, z);
  20         P p2 = ps.get(p);
  21         if (p2 != null) return p2;
  22         ps.put(p,p);
  23         return p;
  24     }
  25
  26     public E newE(P p1, P p2) {
  27         E e = new E(p1, p2);
  28         E e2 = es.get(e);
  29         if (e2 != null) return e2;
  30         es.put(e,e);
  31         return e;
  32     }
  33
  34     public T newT(E e1, E e2, E e3, V norm) {
  35         P p1 = e1.shared(e2);
  36         P p2 = e2.shared(e3);
  37         P p3 = e3.shared(e1);
  38         V norm2 = p2.minus(p1).cross(p3.minus(p1));
  39         float dot = norm.dot(norm2);
  40         if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
  41         if (dot < 0) { E t = e1; e1 = e3; e2 = e2; e3 = t; }
  42         if (e1.t1 != null && e1.t1.hasE(e1) && e1.t1.hasE(e2) && e1.t1.hasE(e3)) return e1.t1;
  43         if (e1.t2 != null && e1.t2.hasE(e1) && e1.t2.hasE(e2) && e1.t2.hasE(e3)) return e1.t2;
  44         if (e2.t1 != null && e2.t1.hasE(e1) && e2.t1.hasE(e2) && e2.t1.hasE(e3)) return e2.t1;
  45         if (e2.t2 != null && e2.t2.hasE(e1) && e2.t2.hasE(e2) && e2.t2.hasE(e3)) return e2.t2;
  46         if (e3.t1 != null && e3.t1.hasE(e1) && e3.t1.hasE(e2) && e3.t1.hasE(e3)) return e3.t1;
  47         if (e3.t2 != null && e3.t2.hasE(e1) && e3.t2.hasE(e2) && e3.t2.hasE(e3)) return e3.t2;
  48         T ret = new T(e1, e2, e3);
  49         ts.add(ret);
  50         return ret;
  51     }
  52
  53     /** [UNIQUE] point in 3-space */
  54     public final class P {
  55         public final float x, y, z;
  56         private T t = null;  // any of the triangles incident at this point
  57         public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
  58         public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
  59         public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
  60         public boolean equals(Object o) {
  61             if (o==null || !(o instanceof P)) return false;
  62             P p = (P)o;
  63             return p.x==x && p.y==y && p.z==z;
  64         }
  65         public int hashCode() {
  66             return
  67                 Float.floatToIntBits(x) ^
  68                 Float.floatToIntBits(y) ^
  69                 Float.floatToIntBits(z);
  70         }
  71         public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
  72         public String toString() { return "("+x+","+y+","+z+")"; }
  73         public V norm() {
  74             if (t==null) throw new Error("attempt to get vertex normal for point which does not belong to any triangles");
  75             T ti = t;
  76             V norm = new V(0, 0, 0);
  77             do {
  78                 norm = norm.plus(ti.norm().times((float)ti.angle(this)));
  79                 ti = ti.next(this);
  80             } while(ti != t);
  81             return norm.norm();
  82         }
  83     }
  84
  85     /** vector in 3-space */
  86     public final class V {
  87         private final float x, y, z;
  88         public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
  89         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); }
  90         public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
  91         public V norm() { float m = mag(); return new V(x/m, y/m, z/m); }
  92         public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
  93         public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
  94         public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
  95         public String toString() { return "<"+x+","+y+","+z+">"; }
  96     }
  97
  98     /** [UNIQUE] an edge */
  99     public final class E {
 100         public final P p1, p2;
 101         T t1, t2;
 102         public E(P p1, P p2) {
 103             if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
 104             this.p1 = p1;
 105             this.p2 = p2;
 106         }
 107         public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
 108         public float length() { return p1.minus(p2).mag(); }
 109         public boolean equals(Object o) {
 110             if (o==null || !(o instanceof E)) return false;
 111             E e = (E)o;
 112             if (this.p1 == e.p1 && this.p2 == e.p2) return true;
 113             if (this.p2 == e.p1 && this.p1 == e.p2) return true;
 114             return false;
 115         }
 116         public P shared(E e) {
 117             if (p1==e.p1) return p1;
 118             if (p1==e.p2) return p1;
 119             if (p2==e.p1) return p2;
 120             if (p2==e.p2) return p2;
 121             throw new Error("no shared vertex in shared()");
 122         }
 123         public P unshared(E e) {
 124             if (p1==e.p1) return p2;
 125             if (p1==e.p2) return p2;
 126             if (p2==e.p1) return p1;
 127             if (p2==e.p2) return p1;
 128             throw new Error("no shared vertex in unshared()");
 129         }
 130         public T other(T t) {
 131             if (t1==t) return t2;
 132             if (t2==t) return t1;
 133             throw new Error("edge " + this + " does not own triangle " + t);
 134         }
 135         public P other(P p) {
 136             if (p==p1) return p2;
 137             if (p==p2) return p1;
 138             throw new Error("edge " + this + " does not own point " + p);
 139         }
 140     }
 141
 142     /** [UNIQUE] a triangle (face) */
 143     public final class T {
 144         public final E e1, e2, e3;
 145         T(E e1, E e2, E e3) {
 146             if (e1.p1.t==null) e1.p1.t = this;
 147             if (e1.p2.t==null) e1.p2.t = this;
 148             if (e2.p1.t==null) e2.p1.t = this;
 149             if (e2.p2.t==null) e2.p2.t = this;
 150             if (e3.p1.t==null) e3.p1.t = this;
 151             if (e3.p2.t==null) e3.p2.t = this;
 152             if (e1==e2) throw new Error("attempt to create triangle with duplicate edge: " + e1);
 153             if (e2==e3) throw new Error("attempt to create triangle with duplicate edge: " + e2);
 154             if (e3==e1) throw new Error("attempt to create triangle with duplicate edge: " + e3);
 155             // check that each pair of edges shares a vertex
 156             e1.shared(e2);
 157             e2.shared(e3);
 158             e3.shared(e1);
 159             this.e1 = e1;
 160             this.e2 = e2;
 161             this.e3 = e3;
 162             // FEATURE: colinearity/sliverness check?
 163             if (e1.t1 == null) e1.t1 = this; else if (e1.t2 == null) e1.t2 = this; else throw new Error("non-manifold surface");
 164             if (e2.t1 == null) e2.t1 = this; else if (e2.t2 == null) e2.t2 = this; else throw new Error("non-manifold surface");
 165             if (e3.t1 == null) e3.t1 = this; else if (e3.t2 == null) e3.t2 = this; else throw new Error("non-manifold surface");
 166             // FIXME: check that triangles we share an edge with agree on the direction of the normal vector
 167             // FIXME: check for sealed/watertight surface once construction is complete (an infer normal(s)?)
 168         }
 169         public V norm() {
 170             P p1 = e1.shared(e2);
 171             P p2 = e2.shared(e3);
 172             P p3 = e3.shared(e1);
 173             return p2.minus(p1).cross(p3.minus(p1)).norm();
 174         }
 175         public boolean hasE(E e) { return e1==e || e2==e || e3==e; }
 176         public void glVertices(GL gl) {
 177             p1().glVertex(gl);
 178             p2().glVertex(gl);
 179             p3().glVertex(gl);
 180         }
 181         public P p1() { return e1.shared(e2); }
 182         public P p2() { return e1.shared(e3); }
 183         public P p3() { return e3.shared(e2); }
 184         public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
 185                                           (p1().y+p2().y+p3().y)/3,
 186                                           (p1().z+p2().z+p3().z)/3); }
 187         public float diameter() {
 188             // FIXME: what is this supposed to be?
 189             return Math.max(Math.max(e1.length(), e2.length()), e3.length()) / 2;
 190         }
 191
 192         // FIXME: ambiguity firstEdge or secondEdge?
 193         /** returns the next triangle walking "around" shared vertex p */
 194         public T next(P p) { return secondEdge(p).other(this); }
 195
 196         public E firstEdge(P p) {
 197             if      (p == e1.shared(e2)) return e1;
 198             else if (p == e2.shared(e3)) return e2;
 199             else if (p == e3.shared(e1)) return e3;
 200             else throw new Error("triangle " + this + " does not own point " + p);
 201         }
 202
 203         public E secondEdge(P p) {
 204             if      (p == e1.shared(e2)) return e2;
 205             else if (p == e2.shared(e3)) return e3;
 206             else if (p == e3.shared(e1)) return e1;
 207             else throw new Error("triangle " + this + " does not own point " + p);
 208         }
 209
 210         /** returns the angle at point p */
 211         public double angle(P p) {
 212             V v1 = firstEdge(p).other(p).minus(p);
 213             V v2 = secondEdge(p).other(p).minus(p);
 214             return Math.acos(v1.norm().dot(v2.norm()));
 215         }
 216
 217     }
 218
 219     /** matrix */
 220     public class M {
 221     }
 222
 223 }