3 import java.awt.event.*;
5 import javax.media.opengl.*;
6 import javax.media.opengl.glu.*;
7 import edu.wlu.cs.levy.CG.KDTree;
9 public class Geom implements Iterable<Geom.T> {
11 private KDTree kd = new KDTree(3);
13 public static float EPSILON = (float)0.000001;
14 public static Random random = new Random();
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>();
20 public Iterator<T> iterator() { return ts.iterator(); }
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) {
26 if (p2 != null) return p2;
29 try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); }
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);
41 public T newT(P p1, P p2, P p3) {
45 while(e12.next != e23 || e23.next != e31 || e31.next != e12) {
46 e12.makeAdjacent(e23);
47 e23.makeAdjacent(e31);
48 e31.makeAdjacent(e12);
53 private char allname = 'A';
55 /** [UNIQUE] point in 3-space */
56 public final class P {
61 private E e; // some edge *leaving* this point
62 private M binding = new M();
63 private P bound_to = this;
65 public E makeE(P 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;
71 e = getFreeIncident();
72 if (e==null) throw new Error("could not find free incident to " + this);
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);
82 public E getFreeIncident(E start, E before) {
85 if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null) return e.pair;
91 public E listIncidents(E start, E before) {
94 if (e.pair.p2 == this && e.pair.t == null) System.out.println(e.pair + " / " + e.pair.t);
100 public E getE(P p2) {
103 if (e==null) return null;
104 if (e.p1 == this && e.p2 == p2) return e;
110 public boolean isBoundTo(P p) {
113 if (px==this) return true;
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
131 public void move(V v) {
137 v = v.times(binding);
142 /** the next edge going around this point [FIXME: direction] */
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);
152 public P(float x, float y, float z) {
153 this.x = x; this.y = y; this.z = z;
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];
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;
169 return p.x==x && p.y==y && p.z==z;
171 // FIXME: moving a point alters its hashCode
172 public int hashCode() {
174 Float.floatToIntBits(x) ^
175 Float.floatToIntBits(y) ^
176 Float.floatToIntBits(z);
178 public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
179 public String toString() { return ""+name; }
180 //{ return "("+x+","+y+","+z+")"; }
182 V norm = new V(0, 0, 0);
185 norm = norm.plus(e.t.norm().times((float)e.prev.angle()));
187 } while(e != this.e);
192 /** vector in 3-space */
193 public final class V {
194 public final float x, y, z;
195 public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
196 public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
197 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); }
198 public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
199 public V norm() { return div(mag()); }
200 public V times(M m) { return m.apply(this); }
201 public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
202 public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
203 public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
204 public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
205 public String toString() { return "<"+x+","+y+","+z+">"; }
208 /** [UNIQUE] an edge */
209 public final class E {
210 public final P p1, p2;
216 private void syncm() {
217 this.prev.next = this;
218 this.next.prev = this;
219 this.pair.pair = this;
220 if (this.next.p1 != p2) throw new Error();
221 if (this.prev.p2 != p1) throw new Error();
223 private void sync() {
226 System.out.println("make " + this);
228 if (next != this && next.next != this && next.next.next == this)
234 if (t==null) t = new T(this);
238 /** angle between this half-edge and the next */
239 public double angle() {
240 V v1 = next.p2.minus(p2);
241 V v2 = this.p1.minus(p2);
242 return Math.acos(v1.norm().dot(v2.norm()));
245 public void makeAdjacent(E e) {
246 if (this.next == e) return;
247 if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex");
248 if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free");
250 System.out.println(this + ".makeAdjacent("+e+") -- from " + this.next);
251 E freeIncident = p2.getFreeIncident();
252 if (freeIncident==null) throw new Error("unable to find freeIncident");
254 e.prev.next = freeIncident.next;
255 freeIncident.next.prev = e.prev;
257 freeIncident.next = this.next;
258 this.next.prev = freeIncident;
264 freeIncident.syncm();
266 //throw new Error("makeAdjacent() failed");
269 /** creates an isolated edge out in the middle of space */
270 public E(P p1, P p2) {
271 if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
274 this.prev = this.next = this.pair = new E(this, this, this);
278 /** adds a new half-edge from prev.p2 to p2 */
279 public E(E prev, P p2) {
284 this.next = this.pair = new E(this, this, prev.next);
286 E q = p2.getFreeIncident();
288 System.out.println("listing:");
289 p2.listIncidents(p2.e, p2.e);
290 p2.listIncidents(p2.e.pair.next, p2.e.pair.next);
291 throw new Error("could not find free incident to " + p2 + " from " + p2.e);
294 this.next.prev = this;
295 this.pair = new E(q, this, prev.next);
300 /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */
301 public E(E prev, E pair, E next) {
309 public P midpoint() { return newP((p1.x+p2.x)/2, (p1.y+p2.y)/2, (p1.z+p2.z)/2); }
310 public boolean has(P p) { return p==p1 || p==p2; }
311 public float length() { return p1.minus(p2).mag(); }
312 public String toString() { return p1+"->"+p2; }
313 public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
314 public boolean equals(Object o) { return o!=null && o instanceof E && this.p1 == ((E)o).p1 && this.p2 == ((E)o).p2; }
317 /** [UNIQUE] a triangle (face) */
318 public final class T {
320 public final int color;
322 public void bind(T t2, int rot) {
330 if (e1==e2 || e1==e3) throw new Error();
331 if (e3.next!=e1) throw new Error();
332 if (e1.t!=null || e2.t!=null || e3.t!=null) throw new Error("non-manifold surface");
335 e1.next.next.t = this;
337 if (e1.pair.t != null && e1.pair.t.nextP(e1) != prevP(e1)) throw new Error("normals disagree!");
338 if (e2.pair.t != null && e2.pair.t.nextP(e2) != prevP(e2)) throw new Error("normals disagree!");
339 if (e3.pair.t != null && e3.pair.t.nextP(e3) != prevP(e3)) throw new Error("normals disagree!");
341 // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
343 int color = Math.abs(random.nextInt());
347 if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; }
348 if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; }
349 if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
359 public int hashCode() { return e1().hashCode() ^ e2().hashCode() ^ e3.hashCode(); }
360 public boolean equals(Object o) {
361 if (o==null || !(o instanceof T)) return false;
363 return e1==t.e1() || e1==t.e2() || e1==t.e3();
366 public P p1() { return e1.p1; }
367 public P p2() { return e1.p2; }
368 public P p3() { return e1.next.p2; }
369 public E e1() { return e1; }
370 public E e2() { return e1.next; }
371 public E e3() { return e1.prev; }
372 public V norm() { return p2().minus(p1()).cross(p3().minus(p1())).norm(); }
373 public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
374 public boolean has(P p) { return p1()==p || p2()==p || p3()==p; }
375 public void glVertices(GL gl) {
381 public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
382 (p1().y+p2().y+p3().y)/3,
383 (p1().z+p2().z+p3().z)/3); }
384 public float diameter() {
385 // FIXME: what is this supposed to be?
386 return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2;
389 /** returns the next triangle walking clockwise around the vertex normal */
391 public T nextT(P p) { return prevE(p).pair.t; }
392 public T prevT(P p) { return nextE(p).pair.t; }
394 public E nextE(E e) {
395 if (e==e2) return e1;
396 if (e==e3) return e2;
397 if (e==e1) return e3;
398 throw new Error("triangle " + this + " does not own edge " + e);
401 public E prevE(E e) {
402 if (e==e2) return e3;
403 if (e==e3) return e1;
404 if (e==e1) return e2;
405 throw new Error("triangle " + this + " does not own edge " + e);
407 // edge "after" this point, moving clockwise around the normal
408 public E nextE(P p) {
409 if (p == e1.shared(e2)) return e1;
410 else if (p == e2.shared(e3)) return e2;
411 else if (p == e3.shared(e1)) return e3;
412 else throw new Error("triangle " + this + " does not own point " + p);
414 // edge "before" this point, moving clockwise around the normal
415 public E prevE(P p) {
416 if (p == e1.shared(e2)) return e2;
417 else if (p == e2.shared(e3)) return e3;
418 else if (p == e3.shared(e1)) return e1;
419 else throw new Error("triangle " + this + " does not own point " + p);
429 public P apply(P p) { return p; }
430 public V apply(V v) { return v; }
431 public M invert() { return this; }
432 public M times(M m) { return this; }