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);
51 if (e12.t == null) throw new Error();
52 if (e23.t == null) throw new Error();
53 if (e31.t == null) throw new Error();
57 private char allname = 'A';
59 /** [UNIQUE] point in 3-space */
60 public final class P {
65 private E e; // some edge *leaving* this point
66 private M binding = new M();
67 private P bound_to = this;
69 public E makeE(P p2) {
71 if (e != null) return e;
73 if (this.e == null && p2.e == null) return this.e = new E(this, p2);
74 if (this.e == null && p2.e != null) return p2.makeE(this).pair;
75 return new E(getFreeIncident(), p2);
78 public E getFreeIncident() {
79 E ret = getFreeIncident(e, e);
80 if (ret != null) return ret;
81 ret = getFreeIncident(e.pair.next, e.pair.next);
82 if (ret == null) throw new Error("unable to find free incident to " + this);
86 public E getFreeIncident(E start, E before) {
89 if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null) return e.pair;
98 if (e==null) return null;
99 if (e.p1 == this && e.p2 == p2) return e;
105 public boolean isBoundTo(P p) {
108 if (px==this) return true;
114 public void unbind() { bound_to = null; binding = null; }
115 public void bind(P p) { bind(p, new M()); }
116 public void bind(P p, M binding) {
117 if (isBoundTo(p)) return;
118 P temp_bound_to = p.bound_to;
119 M temp_binding = p.binding;
120 p.bound_to = this.bound_to;
121 p.binding = binding.times(this.binding); // FIXME: may have order wrong here
122 this.bound_to = temp_bound_to;
123 this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
126 public void move(V v) {
132 v = v.times(binding);
137 /** the next edge going around this point [FIXME: direction] */
139 public E nextE(E e) {
140 //e.other(this); // sanity check
141 if (e.t != null && e.t.nextE(e).has(this)) return e.t.nextE(e);
142 if (e.pair.t != null && e.pair.t.nextE(e).has(this)) return e.pair.nextE(e.pair);
147 public P(float x, float y, float z) {
148 this.x = x; this.y = y; this.z = z;
153 try { results = kd.nearest(new double[]{x,y,z},2); } catch (Exception e) { throw new Error(e); }
154 if (results[0] != this) throw new Error();
155 return (P)results[1];
158 public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
159 public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
160 public P times(M m) { return m.apply(this); }
161 public boolean equals(Object o) {
162 if (o==null || !(o instanceof P)) return false;
164 return p.x==x && p.y==y && p.z==z;
166 // FIXME: moving a point alters its hashCode
167 public int hashCode() {
169 Float.floatToIntBits(x) ^
170 Float.floatToIntBits(y) ^
171 Float.floatToIntBits(z);
173 public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
174 //public String toString() { return ""+name; }
175 public String toString() { return "("+x+","+y+","+z+")"; }
177 V norm = new V(0, 0, 0);
180 if (e.t != null) norm = norm.plus(e.t.norm().times((float)e.prev.angle()));
182 } while(e != this.e);
187 /** vector in 3-space */
188 public final class V {
189 public final float x, y, z;
190 public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
191 public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
192 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); }
193 public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
194 public V norm() { return div(mag()); }
195 public V times(M m) { return m.apply(this); }
196 public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
197 public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
198 public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
199 public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
200 public String toString() { return "<"+x+","+y+","+z+">"; }
203 /** [UNIQUE] an edge */
204 public final class E {
205 public final P p1, p2;
211 private void sync() {
212 this.prev.next = this;
213 this.next.prev = this;
214 this.pair.pair = this;
215 if (this.next.p1 != p2) throw new Error();
216 if (this.prev.p2 != p1) throw new Error();
217 if (this.p1.e == null) this.p1.e = this;
221 if (t==null) t = new T(this);
225 /** angle between this half-edge and the next */
226 public double angle() {
227 V v1 = next.p2.minus(p2);
228 V v2 = this.p1.minus(p2);
229 return Math.acos(v1.norm().dot(v2.norm()));
232 public void makeAdjacent(E e) {
233 if (this.next == e) return;
234 if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex");
235 if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free");
237 E freeIncident = p2.getFreeIncident(e, this);
239 e.prev.next = freeIncident.next;
240 freeIncident.next.prev = e.prev;
242 freeIncident.next = this.next;
243 this.next.prev = freeIncident;
252 /** creates an isolated edge out in the middle of space */
253 public E(P p1, P p2) {
254 if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
257 this.prev = this.next = this.pair = new E(this, this, this);
261 /** adds a new half-edge from prev.p2 to p2 */
262 public E(E prev, P p2) {
266 if (p2.getE(p1) != null) throw new Error();
268 this.next = this.pair = new E(this, this, prev.next);
270 E q = p2.getFreeIncident();
272 this.next.prev = this;
274 this.prev.next = this;
275 this.pair = new E(q, this, z);
280 /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */
281 public E(E prev, E pair, E next) {
289 public P midpoint() { return newP((p1.x+p2.x)/2, (p1.y+p2.y)/2, (p1.z+p2.z)/2); }
290 public boolean has(P p) { return p==p1 || p==p2; }
291 public float length() { return p1.minus(p2).mag(); }
292 public String toString() { return p1+"->"+p2; }
293 public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
294 public boolean equals(Object o) { return o!=null && o instanceof E && this.p1 == ((E)o).p1 && this.p2 == ((E)o).p2; }
297 /** [UNIQUE] a triangle (face) */
298 public final class T {
300 public final int color;
302 public void bind(T t2, int rot) {
310 if (e1==e2 || e1==e3) throw new Error();
311 if (e3.next!=e1) throw new Error();
312 if (e1.t!=null || e2.t!=null || e3.t!=null) throw new Error("non-manifold surface");
315 e1.next.next.t = this;
317 if (e1.pair.t != null && e1.pair.t.nextP(e1) != prevP(e1)) throw new Error("normals disagree!");
318 if (e2.pair.t != null && e2.pair.t.nextP(e2) != prevP(e2)) throw new Error("normals disagree!");
319 if (e3.pair.t != null && e3.pair.t.nextP(e3) != prevP(e3)) throw new Error("normals disagree!");
321 // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
323 int color = Math.abs(random.nextInt());
327 if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; }
328 if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; }
329 if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
339 public int hashCode() { return e1().hashCode() ^ e2().hashCode() ^ e3.hashCode(); }
340 public boolean equals(Object o) {
341 if (o==null || !(o instanceof T)) return false;
343 return e1==t.e1() || e1==t.e2() || e1==t.e3();
346 public P p1() { return e1.p1; }
347 public P p2() { return e1.p2; }
348 public P p3() { return e1.next.p2; }
349 public E e1() { return e1; }
350 public E e2() { return e1.next; }
351 public E e3() { return e1.prev; }
352 public V norm() { return p2().minus(p1()).cross(p3().minus(p1())).norm(); }
353 public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
354 public boolean has(P p) { return p1()==p || p2()==p || p3()==p; }
355 public void glVertices(GL gl) {
361 public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
362 (p1().y+p2().y+p3().y)/3,
363 (p1().z+p2().z+p3().z)/3); }
364 public float diameter() {
365 // FIXME: what is this supposed to be?
366 return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2;
369 /** returns the next triangle walking clockwise around the vertex normal */
371 public T nextT(P p) { return prevE(p).pair.t; }
372 public T prevT(P p) { return nextE(p).pair.t; }
374 public E nextE(E e) {
375 if (e==e2) return e1;
376 if (e==e3) return e2;
377 if (e==e1) return e3;
378 throw new Error("triangle " + this + " does not own edge " + e);
381 public E prevE(E e) {
382 if (e==e2) return e3;
383 if (e==e3) return e1;
384 if (e==e1) return e2;
385 throw new Error("triangle " + this + " does not own edge " + e);
387 // edge "after" this point, moving clockwise around the normal
388 public E nextE(P p) {
389 if (p == e1.shared(e2)) return e1;
390 else if (p == e2.shared(e3)) return e2;
391 else if (p == e3.shared(e1)) return e3;
392 else throw new Error("triangle " + this + " does not own point " + p);
394 // edge "before" this point, moving clockwise around the normal
395 public E prevE(P p) {
396 if (p == e1.shared(e2)) return e2;
397 else if (p == e2.shared(e3)) return e3;
398 else if (p == e3.shared(e1)) return e1;
399 else throw new Error("triangle " + this + " does not own point " + p);
409 public P apply(P p) { return p; }
410 public V apply(V v) { return v; }
411 public M invert() { return this; }
412 public M times(M m) { return this; }