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 public PriorityQueue<E> es = new PriorityQueue<E>();
18 //private HashSet<T> ts = new HashSet<T>();
19 public ArrayList<T> ts = new ArrayList<T>();
21 public Iterator<T> iterator() { return ts.iterator(); }
23 public P newP(double x, double y, double z) { return newP((float)x, (float)y, (float)z); }
24 public P newP(float x, float y, float z) {
27 if (p2 != null) return p2;
30 //try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); }
34 public T newT(P p12, P p23, P p31, V norm) {
35 V norm2 = p31.minus(p12).cross(p23.minus(p12));
36 float dot = norm.dot(norm2);
37 if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
38 if (dot < 0) { P p = p12; p12=p23; p23 = p; }
39 return newT(p12, p23, p31);
42 public T newT(P p1, P p2, P p3) {
46 while(e12.next != e23 || e23.next != e31 || e31.next != e12) {
47 e12.makeAdjacent(e23);
48 e23.makeAdjacent(e31);
49 e31.makeAdjacent(e12);
52 if (e12.t == null) throw new Error();
53 if (e23.t == null) throw new Error();
54 if (e31.t == null) throw new Error();
58 private char allname = 'A';
60 /** [UNIQUE] point in 3-space */
61 public final class P {
66 private E e; // some edge *leaving* this point
67 private M binding = new M();
68 private P bound_to = this;
70 public E makeE(P p2) {
72 if (e != null) return e;
74 if (this.e == null && p2.e == null) return this.e = new E(this, p2);
75 if (this.e == null && p2.e != null) return p2.makeE(this).pair;
76 return new E(getFreeIncident(), p2);
79 public E getFreeIncident() {
80 E ret = getFreeIncident(e, e);
81 if (ret != null) return ret;
82 ret = getFreeIncident(e.pair.next, e.pair.next);
83 if (ret == null) throw new Error("unable to find free incident to " + this);
87 public E getFreeIncident(E start, E before) {
90 if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null) return e.pair;
99 if (e==null) return null;
100 if (e.p1 == this && e.p2 == p2) return e;
106 public boolean isBoundTo(P p) {
109 if (px==this) return true;
115 public void unbind() { bound_to = null; binding = null; }
116 public void bind(P p) { bind(p, new M()); }
117 public void bind(P p, M binding) {
118 if (isBoundTo(p)) return;
119 P temp_bound_to = p.bound_to;
120 M temp_binding = p.binding;
121 p.bound_to = this.bound_to;
122 p.binding = binding.times(this.binding); // FIXME: may have order wrong here
123 this.bound_to = temp_bound_to;
124 this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
127 public void move(V v) {
133 v = v.times(binding);
138 public P(float x, float y, float z) {
139 this.x = x; this.y = y; this.z = z;
144 try { results = kd.nearest(new double[]{x,y,z},2); } catch (Exception e) { throw new Error(e); }
145 if (results[0] != this) throw new Error();
146 return (P)results[1];
149 public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
150 public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
151 public P times(M m) { return m.apply(this); }
152 public boolean equals(Object o) {
153 if (o==null || !(o instanceof P)) return false;
155 return p.x==x && p.y==y && p.z==z;
157 // FIXME: moving a point alters its hashCode
158 public int hashCode() {
160 Float.floatToIntBits(x) ^
161 Float.floatToIntBits(y) ^
162 Float.floatToIntBits(z);
164 public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
165 public String toString() { return "("+x+","+y+","+z+")"; }
167 V norm = new V(0, 0, 0);
170 if (e.t != null) norm = norm.plus(e.t.norm().times((float)e.prev.angle()));
172 } while(e != this.e);
177 /** vector in 3-space */
178 public final class V {
179 public final float x, y, z;
180 public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
181 public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
182 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); }
183 public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
184 public V norm() { return div(mag()); }
185 public V times(M m) { return m.apply(this); }
186 public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
187 public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
188 public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
189 public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
190 public String toString() { return "<"+x+","+y+","+z+">"; }
193 public class BindingGroup {
194 public HashSet<E> es = new HashSet<E>();
195 public BindingGroup() { }
196 public BindingGroup(E e) { es.add(e); }
197 public void add(E e) {
198 if (e.bg != null) { merge(e.bg); return; }
202 public void merge(BindingGroup bg) {
210 /** [UNIQUE] an edge */
211 public final class E implements Comparable<E> {
213 public int compareTo(E e) {
214 return e.length() > length() ? 1 : -1;
217 public final P p1, p2;
218 T t; // triangle to our "left"
219 E prev; // previous half-edge
220 E next; // next half-edge
221 E pair; // partner half-edge
224 public BindingGroup bg = new BindingGroup(this);
226 public void bind(E e) { bind(e, new M()); }
227 public void bind(E e, M m) { e.bg.add(this); }
229 public void dobind() {
230 if (bg==null) return;
232 if (ex==this) continue;
238 boolean shattered = false;
239 public P shatter() { return shatter(midpoint(), null, null); }
240 public P shatter(P mid, BindingGroup bg1, BindingGroup bg2) {
241 if (shattered) return mid;
248 if (bg1==null) bg1 = new BindingGroup();
249 if (bg2==null) bg2 = new BindingGroup();
250 for(E e : bg.es) e.shatter(e.midpoint(), bg1, bg2);
256 bg1.add(p1.getE(mid));
257 bg2.add(mid.getE(p2));
261 public boolean destroyed = false;
262 public void destroy() {
263 if (destroyed) return;
265 pair.destroyed = true;
266 if (next.t != null) ts.remove(next.t);
267 if (prev.t != null) ts.remove(prev.t);
268 if (pair.next.t != null) ts.remove(pair.next.t);
269 if (pair.prev.t != null) ts.remove(pair.prev.t);
276 pair.prev.next = next;
277 next.prev = pair.prev;
278 prev.next = pair.next;
280 if (p1.e == this) p1.e = prev.next;
281 if (pair.p1.e == pair) pair.p1.e = pair.prev.next;
286 private void sync() {
287 this.prev.next = this;
288 this.next.prev = this;
289 this.pair.pair = this;
290 if (this.next.p1 != p2) throw new Error();
291 if (this.prev.p2 != p1) throw new Error();
292 if (this.p1.e == null) this.p1.e = this;
296 public T makeT() { return t==null ? (t = new T(this)) : t; }
298 /** angle between this half-edge and the next */
299 public double angle() {
300 V v1 = next.p2.minus(p2);
301 V v2 = this.p1.minus(p2);
302 return Math.acos(v1.norm().dot(v2.norm()));
305 public void makeAdjacent(E e) {
306 if (this.next == e) return;
307 if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex");
308 if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free");
310 E freeIncident = p2.getFreeIncident(e, this);
312 e.prev.next = freeIncident.next;
313 freeIncident.next.prev = e.prev;
315 freeIncident.next = this.next;
316 this.next.prev = freeIncident;
325 /** creates an isolated edge out in the middle of space */
326 public E(P p1, P p2) {
327 if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
330 this.prev = this.next = this.pair = new E(this, this, this);
334 /** adds a new half-edge from prev.p2 to p2 */
335 public E(E prev, P p2) {
339 if (p2.getE(p1) != null) throw new Error();
341 this.next = this.pair = new E(this, this, prev.next);
343 E q = p2.getFreeIncident();
345 this.next.prev = this;
347 this.prev.next = this;
348 this.pair = new E(q, this, z);
353 /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */
354 public E(E prev, E pair, E next) {
362 public P midpoint() { return newP((p1.x+p2.x)/2, (p1.y+p2.y)/2, (p1.z+p2.z)/2); }
363 public boolean has(P p) { return p==p1 || p==p2; }
364 public float length() { return p1.minus(p2).mag(); }
365 public String toString() { return p1+"->"+p2; }
368 /** [UNIQUE] a triangle (face) */
369 public final class T {
371 public final int color;
377 if (e1==e2 || e1==e3) throw new Error();
378 if (e3.next!=e1) throw new Error();
379 if (e1.t!=null || e2.t!=null || e3.t!=null)
380 throw new Error("non-manifold surface or disagreeing normals");
383 e1.next.next.t = this;
385 // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
387 int color = Math.abs(random.nextInt());
390 if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; }
391 if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; }
392 if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
401 public P p1() { return e1.p1; }
402 public P p2() { return e1.p2; }
403 public P p3() { return e1.next.p2; }
404 public E e1() { return e1; }
405 public E e2() { return e1.next; }
406 public E e3() { return e1.prev; }
407 public V norm() { return p2().minus(p1()).cross(p3().minus(p1())).norm(); }
408 public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
409 public boolean has(P p) { return p1()==p || p2()==p || p3()==p; }
410 public void glVertices(GL gl) {
416 public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
417 (p1().y+p2().y+p3().y)/3,
418 (p1().z+p2().z+p3().z)/3); }
419 public float diameter() {
420 // FIXME: what is this supposed to be?
421 return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2;
431 public P apply(P p) { return p; }
432 public V apply(V v) { return v; }
433 public M invert() { return this; }
434 public M times(M m) { return this; }
437 public void unbind() {
439 for(Geom.T t : this) {
447 for(Geom.T t : this) {