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 // FEATURE: octree for nearest-point queries?  Could make moving points around problematic.
   9
  10 public class Geom implements Iterable<Geom.T> {
  11
  12     public static float EPSILON = (float)0.000001;
  13
  14     private HashMap<P,P> ps = new HashMap<P,P>();
  15     private HashMap<E,E> es = new HashMap<E,E>();
  16     private HashSet<T>   ts = new HashSet<T>();
  17
  18     public Iterator<T> iterator() { return ts.iterator(); }
  19
  20     public P newP(double x, double y, double z) { return newP((float)x, (float)y, (float)z); }
  21     public P newP(float x, float y, float z) {
  22         P p = new P(x, y, z);
  23         P p2 = ps.get(p);
  24         if (p2 != null) return p2;
  25         ps.put(p,p);
  26         return p;
  27     }
  28
  29     public E newE(P p1, P p2) {
  30         E e = new E(p1, p2);
  31         E e2 = es.get(e);
  32         if (e2 != null) return e2;
  33         es.put(e,e);
  34         return e;
  35     }
  36
  37     public T newT(P p1, P p2, P p3) {
  38         return newT(newE(p1, p2), newE(p2, p3), newE(p3, p1), p3.minus(p1).cross(p2.minus(p1)));
  39     }
  40
  41     /** ensures that e1.cross(e2).norm()==e2.cross(e3).norm()==e3.cross(e1).norm()==t.norm() */
  42     public T newT(E e1, E e2, E e3, V norm) {
  43         P p12 = e1.shared(e2);
  44         P p23 = e2.shared(e3);
  45         P p31 = e3.shared(e1);
  46         V norm2 = p31.minus(p12).cross(p23.minus(p12));
  47         float dot = norm.dot(norm2);
  48         if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
  49         if (dot < 0) { E t = e1; e1 = e3; e2 = e2; e3 = t; }
  50         if (e1.t1 != null && e1.t1.hasE(e1) && e1.t1.hasE(e2) && e1.t1.hasE(e3)) return e1.t1;
  51         if (e1.t2 != null && e1.t2.hasE(e1) && e1.t2.hasE(e2) && e1.t2.hasE(e3)) return e1.t2;
  52         if (e2.t1 != null && e2.t1.hasE(e1) && e2.t1.hasE(e2) && e2.t1.hasE(e3)) return e2.t1;
  53         if (e2.t2 != null && e2.t2.hasE(e1) && e2.t2.hasE(e2) && e2.t2.hasE(e3)) return e2.t2;
  54         if (e3.t1 != null && e3.t1.hasE(e1) && e3.t1.hasE(e2) && e3.t1.hasE(e3)) return e3.t1;
  55         if (e3.t2 != null && e3.t2.hasE(e1) && e3.t2.hasE(e2) && e3.t2.hasE(e3)) return e3.t2;
  56         T ret = new T(e1, e2, e3);
  57         ts.add(ret);
  58         return ret;
  59     }
  60
  61     /** [UNIQUE] point in 3-space */
  62     public final class P {
  63
  64         float x, y, z;
  65
  66         private T t = null;  // any of the triangles incident at this point
  67
  68         private M binding = new M();
  69         private P bound_to = this;
  70
  71         public void unbind() { bound_to = null; binding = null; }
  72         public void bind(P p) { bind(p, new M()); }
  73         public void bind(P p, M binding) {
  74
  75             P px = p;
  76             do {
  77                 if (px==this) return; // already bound
  78                 px = px.bound_to;
  79             } while(px != p);
  80
  81             P temp_bound_to = p.bound_to;
  82             M temp_binding = p.binding;
  83             p.bound_to = this.bound_to;
  84             p.binding = binding.times(this.binding); // FIXME: may have order wrong here
  85             this.bound_to = temp_bound_to;
  86             this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
  87         }
  88
  89         public void move(V v) {
  90             P p = this;
  91             do {
  92                 p.x = p.x+v.x;
  93                 p.y = p.y+v.y;
  94                 p.z = p.z+v.z;
  95                 v = v.times(binding);
  96                 p = p.bound_to;
  97             } while (p != this);
  98         }
  99
 100         public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
 101         public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
 102         public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
 103         public P times(M m) { return m.apply(this); }
 104         public boolean equals(Object o) {
 105             if (o==null || !(o instanceof P)) return false;
 106             P p = (P)o;
 107             return p.x==x && p.y==y && p.z==z;
 108         }
 109         public int hashCode() {
 110             return
 111                 Float.floatToIntBits(x) ^
 112                 Float.floatToIntBits(y) ^
 113                 Float.floatToIntBits(z);
 114         }
 115         public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
 116         public String toString() { return "("+x+","+y+","+z+")"; }
 117         public V norm() {
 118             if (t==null) throw new Error("attempt to get vertex normal for point which does not belong to any triangles");
 119             T ti = t;
 120             V norm = new V(0, 0, 0);
 121             do {
 122                 norm = norm.plus(ti.norm().times((float)ti.angle(this)));
 123                 ti = ti.nextT(this);
 124             } while(ti != t);
 125             return norm.norm();
 126         }
 127     }
 128
 129     /** vector in 3-space */
 130     public final class V {
 131         public final float x, y, z;
 132         public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
 133         public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
 134         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); }
 135         public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
 136         public V norm() { return div(mag()); }
 137         public V times(M m) { return m.apply(this); }
 138         public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
 139         public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
 140         public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
 141         public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
 142         public String toString() { return "<"+x+","+y+","+z+">"; }
 143     }
 144
 145     /** [UNIQUE] an edge */
 146     public final class E {
 147         public final P p1, p2;
 148         T t1, t2;
 149         public E(P p1, P p2) {
 150             if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
 151             this.p1 = p1;
 152             this.p2 = p2;
 153         }
 154         public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
 155         public float length() { return p1.minus(p2).mag(); }
 156         public boolean equals(Object o) {
 157             if (o==null || !(o instanceof E)) return false;
 158             E e = (E)o;
 159             if (this.p1 == e.p1 && this.p2 == e.p2) return true;
 160             if (this.p2 == e.p1 && this.p1 == e.p2) return true;
 161             return false;
 162         }
 163         public P shared(E e) {
 164             if (p1==e.p1) return p1;
 165             if (p1==e.p2) return p1;
 166             if (p2==e.p1) return p2;
 167             if (p2==e.p2) return p2;
 168             throw new Error("no shared vertex in shared()");
 169         }
 170         public P unshared(E e) {
 171             if (p1==e.p1) return p2;
 172             if (p1==e.p2) return p2;
 173             if (p2==e.p1) return p1;
 174             if (p2==e.p2) return p1;
 175             throw new Error("no shared vertex in unshared()");
 176         }
 177         public T other(T t) {
 178             if (t1==t) return t2;
 179             if (t2==t) return t1;
 180             throw new Error("edge " + this + " does not own triangle " + t);
 181         }
 182         public P other(P p) {
 183             if (p==p1) return p2;
 184             if (p==p2) return p1;
 185             throw new Error("edge " + this + " does not own point " + p);
 186         }
 187     }
 188
 189     /** [UNIQUE] a triangle (face) */
 190     public final class T {
 191         public final E e1, e2, e3;
 192         T(E e1, E e2, E e3) {
 193             if (e1.p1.t==null) e1.p1.t = this;
 194             if (e1.p2.t==null) e1.p2.t = this;
 195             if (e2.p1.t==null) e2.p1.t = this;
 196             if (e2.p2.t==null) e2.p2.t = this;
 197             if (e3.p1.t==null) e3.p1.t = this;
 198             if (e3.p2.t==null) e3.p2.t = this;
 199             if (e1==e2) throw new Error("attempt to create triangle with duplicate edge: " + e1);
 200             if (e2==e3) throw new Error("attempt to create triangle with duplicate edge: " + e2);
 201             if (e3==e1) throw new Error("attempt to create triangle with duplicate edge: " + e3);
 202             // check that each pair of edges shares a vertex
 203             e1.shared(e2);
 204             e2.shared(e3);
 205             e3.shared(e1);
 206             this.e1 = e1;
 207             this.e2 = e2;
 208             this.e3 = e3;
 209             // FEATURE: colinearity/sliverness check?
 210             if (e1.t1 == null) e1.t1 = this; else if (e1.t2 == null) e1.t2 = this; else throw new Error("non-manifold surface");
 211             if (e2.t1 == null) e2.t1 = this; else if (e2.t2 == null) e2.t2 = this; else throw new Error("non-manifold surface");
 212             if (e3.t1 == null) e3.t1 = this; else if (e3.t2 == null) e3.t2 = this; else throw new Error("non-manifold surface");
 213             // FIXME: check that triangles we share an edge with agree on the direction of the normal vector
 214             // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
 215         }
 216         public V norm() {
 217             P p1 = e1.shared(e2);
 218             P p2 = e2.shared(e3);
 219             P p3 = e3.shared(e1);
 220             return p2.minus(p1).cross(p3.minus(p1)).norm();
 221         }
 222         public boolean hasE(E e) { return e1==e || e2==e || e3==e; }
 223         public void glVertices(GL gl) {
 224             p1().glVertex(gl);
 225             p2().glVertex(gl);
 226             p3().glVertex(gl);
 227         }
 228         public P p1() { return e1.shared(e2); }
 229         public P p2() { return e1.shared(e3); }
 230         public P p3() { return e3.shared(e2); }
 231         public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
 232                                           (p1().y+p2().y+p3().y)/3,
 233                                           (p1().z+p2().z+p3().z)/3); }
 234         public float diameter() {
 235             // FIXME: what is this supposed to be?
 236             return Math.max(Math.max(e1.length(), e2.length()), e3.length()) / 2;
 237         }
 238
 239         /** returns the next triangle walking clockwise around the vertex normal */
 240         public T nextT(P p) { return prevE(p).other(this); }
 241         public T prevT(P p) { return nextE(p).other(this); }
 242
 243         /** edge "after" this point, moving clockwise around the normal */
 244         public E nextE(P p) {
 245             if      (p == e1.shared(e2)) return e1;
 246             else if (p == e2.shared(e3)) return e2;
 247             else if (p == e3.shared(e1)) return e3;
 248             else throw new Error("triangle " + this + " does not own point " + p);
 249         }
 250
 251         /** edge "before" this point, moving clockwise around the normal */
 252         public E prevE(P p) {
 253             if      (p == e1.shared(e2)) return e2;
 254             else if (p == e2.shared(e3)) return e3;
 255             else if (p == e3.shared(e1)) return e1;
 256             else throw new Error("triangle " + this + " does not own point " + p);
 257         }
 258
 259         /** returns the angle at point p */
 260         public double angle(P p) {
 261             V v1 = nextE(p).other(p).minus(p);
 262             V v2 = prevE(p).other(p).minus(p);
 263             return Math.acos(v1.norm().dot(v2.norm()));
 264         }
 265
 266     }
 267
 268
 269     /** matrix */
 270     public class M {
 271         public M() { }
 272         public P apply(P p) { return p; }
 273         public V apply(V v) { return v; }
 274         public M invert() { return this; }
 275         public M times(M m) { return this; }
 276     }
 277
 278 }