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 import edu.wlu.cs.levy.CG.KDTree;
   8
   9 public class Geom implements Iterable<Geom.T> {
  10
  11     private KDTree kd = new KDTree(3);
  12
  13     public static float EPSILON = (float)0.000001;
  14     public static Random random = new Random();
  15
  16     private HashMap<P,P> ps = new HashMap<P,P>();
  17     private HashMap<E,E> es = new HashMap<E,E>();
  18     private HashSet<T>   ts = new HashSet<T>();
  19
  20     public Iterator<T> iterator() { return ts.iterator(); }
  21
  22     public P newP(double x, double y, double z) { return newP((float)x, (float)y, (float)z); }
  23     public P newP(float x, float y, float z) {
  24         P p = new P(x, y, z);
  25         P p2 = ps.get(p);
  26         if (p2 != null) return p2;
  27         ps.put(p,p);
  28         p.name = allname++;
  29         try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); }
  30         return p;
  31     }
  32
  33     public T newT(P p12, P p23, P p31, V norm) {
  34         V norm2 = p31.minus(p12).cross(p23.minus(p12));
  35         float dot = norm.dot(norm2);
  36         if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
  37         if (dot < 0) { P p = p12; p12=p23; p23 = p; }
  38         return newT(p12, p23, p31);
  39     }
  40
  41     public T newT(P p1, P p2, P p3) {
  42         E e12 = p1.makeE(p2);
  43         E e23 = p2.makeE(p3);
  44         E e31 = p3.makeE(p1);
  45         while(e12.next != e23 || e23.next != e31 || e31.next != e12) {
  46             e12.makeAdjacent(e23);
  47             e23.makeAdjacent(e31);
  48             e31.makeAdjacent(e12);
  49         }
  50         return e12.newT();
  51     }
  52
  53     private char allname = 'A';
  54
  55     /** [UNIQUE] point in 3-space */
  56     public final class P {
  57         char name;
  58
  59         float x, y, z;
  60
  61         private E e;                // some edge *leaving* this point
  62         private M binding = new M();
  63         private P bound_to = this;
  64
  65         public E makeE(P p2) {
  66             E e = getE(p2);
  67             if (e != null) return e;
  68             if (this.e == null && p2.e == null) return this.e = new E(this, p2);
  69             if (this.e == null && p2.e != null) return p2.makeE(this).pair;
  70
  71             e = getFreeIncident();
  72             if (e==null) throw new Error("could not find free incident to " + this);
  73             return new E(e, p2);
  74         }
  75
  76         public E getFreeIncident() {
  77             E ret = getFreeIncident(e, e);
  78             if (ret != null) return ret;
  79             ret = getFreeIncident(e.pair.next, e.pair.next);
  80             return ret;
  81         }
  82         public E getFreeIncident(E start, E before) {
  83             E e = start;
  84             do {
  85                 if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null) return e.pair;
  86                 e = e.pair.next;
  87             } while(e != before);
  88             return null;
  89         }
  90
  91         public E listIncidents(E start, E before) {
  92             E e = start;
  93             do {
  94                 if (e.pair.p2 == this && e.pair.t == null) System.out.println(e.pair + " / " + e.pair.t);
  95                 e = e.pair.next;
  96             } while(e != before);
  97             return null;
  98         }
  99
 100         public E getE(P p2) {
 101             E e = this.e;
 102             do {
 103                 if (e==null) return null;
 104                 if (e.p1 == this && e.p2 == p2) return e;
 105                 e = e.pair.next;
 106             } while (e!=this.e);
 107             return null;
 108         }
 109
 110         public boolean isBoundTo(P p) {
 111             P px = p;
 112             do {
 113                 if (px==this) return true;
 114                 px = px.bound_to;
 115             } while(px != p);
 116             return false;
 117         }
 118
 119         public void unbind() { bound_to = null; binding = null; }
 120         public void bind(P p) { bind(p, new M()); }
 121         public void bind(P p, M binding) {
 122             if (isBoundTo(p)) return;
 123             P temp_bound_to = p.bound_to;
 124             M temp_binding = p.binding;
 125             p.bound_to = this.bound_to;
 126             p.binding = binding.times(this.binding); // FIXME: may have order wrong here
 127             this.bound_to = temp_bound_to;
 128             this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
 129         }
 130
 131         public void move(V v) {
 132             P p = this;
 133             do {
 134                 p.x = p.x+v.x;
 135                 p.y = p.y+v.y;
 136                 p.z = p.z+v.z;
 137                 v = v.times(binding);
 138                 p = p.bound_to;
 139             } while (p != this);
 140         }
 141
 142         /** the next edge going around this point [FIXME: direction] */
 143         /*
 144         public E nextE(E e) {
 145             //e.other(this);  // sanity check
 146             if (e.t      != null && e.t.nextE(e).has(this))      return e.t.nextE(e);
 147             if (e.pair.t != null && e.pair.t.nextE(e).has(this)) return e.pair.nextE(e.pair);
 148             throw new Error();
 149         }
 150         */
 151
 152         public P(float x, float y, float z) {
 153             this.x = x; this.y = y; this.z = z;
 154         }
 155
 156         public P nearest() {
 157             Object[] results;
 158             try { results = kd.nearest(new double[]{x,y,z},2); } catch (Exception e) { throw new Error(e); }
 159             if (results[0] != this) throw new Error();
 160             return (P)results[1];
 161         }
 162
 163         public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
 164         public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
 165         public P times(M m) { return m.apply(this); }
 166         public boolean equals(Object o) {
 167             if (o==null || !(o instanceof P)) return false;
 168             P p = (P)o;
 169             return p.x==x && p.y==y && p.z==z;
 170         }
 171         // FIXME: moving a point alters its hashCode
 172         public int hashCode() {
 173             return
 174                 Float.floatToIntBits(x) ^
 175                 Float.floatToIntBits(y) ^
 176                 Float.floatToIntBits(z);
 177         }
 178         public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
 179         public String toString() { return ""+name; }
 180         //{ return "("+x+","+y+","+z+")"; }
 181         public V norm() {
 182             /*
 183             if (t==null) throw new Error("attempt to get vertex normal for point which does not belong to any triangles");
 184             T ti = t;
 185             V norm = new V(0, 0, 0);
 186             do {
 187                 norm = norm.plus(ti.norm().times((float)ti.angle(this)));
 188                 ti = ti.nextT(this);
 189             } while(ti != t);
 190             return norm.norm();
 191             */
 192             throw new Error();
 193         }
 194     }
 195
 196     /** vector in 3-space */
 197     public final class V {
 198         public final float x, y, z;
 199         public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
 200         public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
 201         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); }
 202         public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
 203         public V norm() { return div(mag()); }
 204         public V times(M m) { return m.apply(this); }
 205         public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
 206         public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
 207         public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
 208         public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
 209         public String toString() { return "<"+x+","+y+","+z+">"; }
 210     }
 211
 212     /** [UNIQUE] an edge */
 213     public final class E {
 214         public final P p1, p2;
 215         T t;
 216         E prev;
 217         E next;
 218         E pair;
 219
 220         private void syncm() {
 221             this.prev.next = this;
 222             this.next.prev = this;
 223             this.pair.pair = this;
 224             if (this.next.p1 != p2) throw new Error();
 225             if (this.prev.p2 != p1) throw new Error();
 226         }
 227         private void sync() {
 228             syncm();
 229             this.p1.e = this;
 230             System.out.println("make " + this);
 231             /*
 232             if (next != this && next.next != this && next.next.next == this)
 233                 newT();
 234             */
 235         }
 236
 237         public T newT() {
 238             if (t==null) t = new T(this);
 239             return t;
 240         }
 241
 242         public void makeAdjacent(E e) {
 243             if (this.next == e) return;
 244             if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex");
 245             if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free");
 246
 247             System.out.println(this + ".makeAdjacent("+e+") -- from " + this.next);
 248             E freeIncident = p2.getFreeIncident();
 249             if (freeIncident==null) throw new Error("unable to find freeIncident");
 250
 251             e.prev.next = freeIncident.next;
 252             freeIncident.next.prev = e.prev;
 253
 254             freeIncident.next = this.next;
 255             this.next.prev = freeIncident;
 256
 257             this.next = e;
 258             e.prev = this;
 259
 260             syncm();
 261             freeIncident.syncm();
 262
 263             //throw new Error("makeAdjacent() failed");
 264         }
 265
 266         /** creates an isolated edge out in the middle of space */
 267         public E(P p1, P p2) {
 268             if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
 269             this.p1 = p1;
 270             this.p2 = p2;
 271             this.prev = this.next = this.pair = new E(this, this, this);
 272             sync();
 273         }
 274
 275         /** adds a new half-edge from prev.p2 to p2 */
 276         public E(E prev, P p2) {
 277             this.p1 = prev.p2;
 278             this.p2 = p2;
 279             this.prev = prev;
 280             if (p2.e==null) {
 281                 this.next = this.pair = new E(this, this, prev.next);
 282             } else {
 283                 E q = p2.getFreeIncident();
 284                 if (q==null) {
 285                     System.out.println("listing:");
 286                     p2.listIncidents(p2.e, p2.e);
 287                     p2.listIncidents(p2.e.pair.next, p2.e.pair.next);
 288                     throw new Error("could not find free incident to " + p2 + " from " + p2.e);
 289                 }
 290                 this.next = q.next;
 291                 this.next.prev = this;
 292                 this.pair = new E(q, this, prev.next);
 293             }
 294             sync();
 295         }
 296
 297         /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */
 298         public E(E prev, E pair, E next) {
 299             this.p1 = prev.p2;
 300             this.p2 = next.p1;
 301             this.prev = prev;
 302             this.next = next;
 303             this.pair = pair;
 304             sync();
 305         }
 306         public P midpoint() { return newP((p1.x+p2.x)/2, (p1.y+p2.y)/2, (p1.z+p2.z)/2); }
 307         public boolean has(P p) { return p==p1 || p==p2; }
 308         public float length() { return p1.minus(p2).mag(); }
 309         public String toString() { return p1+"->"+p2; }
 310         public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
 311         public boolean equals(Object o) { return o!=null && o instanceof E && this.p1 == ((E)o).p1 && this.p2 == ((E)o).p2; }
 312     }
 313
 314     /** [UNIQUE] a triangle (face) */
 315     public final class T {
 316         public final E e1;
 317         public final int color;
 318
 319         public void bind(T t2, int rot) {
 320             // FIXME
 321         }
 322
 323         T(E e1) {
 324             this.e1 = e1;
 325             E e2 = e1.next;
 326             E e3 = e2.next;
 327             if (e1==e2     || e1==e3) throw new Error();
 328             if (e3.next!=e1) throw new Error();
 329             if (e1.t!=null || e2.t!=null || e3.t!=null)  throw new Error("non-manifold surface");
 330             e1.t = this;
 331             e1.next.t = this;
 332             e1.next.next.t = this;
 333             /*
 334             if (e1.pair.t != null && e1.pair.t.nextP(e1) != prevP(e1)) throw new Error("normals disagree!");
 335             if (e2.pair.t != null && e2.pair.t.nextP(e2) != prevP(e2)) throw new Error("normals disagree!");
 336             if (e3.pair.t != null && e3.pair.t.nextP(e3) != prevP(e3)) throw new Error("normals disagree!");
 337             */
 338             // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
 339
 340             int color = Math.abs(random.nextInt());
 341
 342             while(true) {
 343                 color = color % 4;
 344                 if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; }
 345                 if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; }
 346                 if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
 347                 break;
 348             }
 349
 350             // FIXME unnecssary
 351             ts.add(this);
 352
 353             this.color = color;
 354         }
 355         /*
 356         public int hashCode() { return e1().hashCode() ^ e2().hashCode() ^ e3.hashCode(); }
 357         public boolean equals(Object o) {
 358             if (o==null || !(o instanceof T)) return false;
 359             T t = (T)o;
 360             return e1==t.e1() || e1==t.e2() || e1==t.e3();
 361         }
 362         */
 363         public P p1() { return e1.p1; }
 364         public P p2() { return e1.p2; }
 365         public P p3() { return e1.next.p2; }
 366         public E e1() { return e1; }
 367         public E e2() { return e1.next; }
 368         public E e3() { return e1.prev; }
 369         public V norm() { return p2().minus(p1()).cross(p3().minus(p1())).norm(); }
 370         public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
 371         public boolean has(P p) { return p1()==p || p2()==p || p3()==p; }
 372         public void glVertices(GL gl) {
 373             p1().glVertex(gl);
 374             p2().glVertex(gl);
 375             p3().glVertex(gl);
 376         }
 377
 378         public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
 379                                           (p1().y+p2().y+p3().y)/3,
 380                                           (p1().z+p2().z+p3().z)/3); }
 381         public float diameter() {
 382             // FIXME: what is this supposed to be?
 383             return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2;
 384         }
 385
 386         /** returns the next triangle walking clockwise around the vertex normal */
 387         /*
 388         public T nextT(P p) { return prevE(p).pair.t; }
 389         public T prevT(P p) { return nextE(p).pair.t; }
 390
 391         public E nextE(E e) {
 392             if (e==e2) return e1;
 393             if (e==e3) return e2;
 394             if (e==e1) return e3;
 395             throw new Error("triangle " + this + " does not own edge " + e);
 396         }
 397
 398         public E prevE(E e) {
 399             if (e==e2) return e3;
 400             if (e==e3) return e1;
 401             if (e==e1) return e2;
 402             throw new Error("triangle " + this + " does not own edge " + e);
 403         }
 404         // edge "after" this point, moving clockwise around the normal
 405         public E nextE(P p) {
 406             if      (p == e1.shared(e2)) return e1;
 407             else if (p == e2.shared(e3)) return e2;
 408             else if (p == e3.shared(e1)) return e3;
 409             else throw new Error("triangle " + this + " does not own point " + p);
 410         }
 411         // edge "before" this point, moving clockwise around the normal
 412         public E prevE(P p) {
 413             if      (p == e1.shared(e2)) return e2;
 414             else if (p == e2.shared(e3)) return e3;
 415             else if (p == e3.shared(e1)) return e1;
 416             else throw new Error("triangle " + this + " does not own point " + p);
 417         }
 418
 419         // returns the angle at point p
 420         public double angle(P p) {
 421             V v1 = nextE(p).other(p).minus(p);
 422             V v2 = prevE(p).other(p).minus(p);
 423             return Math.acos(v1.norm().dot(v2.norm()));
 424         }
 425         */
 426     }
 427
 428
 429     /** matrix */
 430     public class M {
 431         public M() { }
 432         public P apply(P p) { return p; }
 433         public V apply(V v) { return v; }
 434         public M invert() { return this; }
 435         public M times(M m) { return this; }
 436     }
 437
 438 }