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 HashSet<T> ts = new HashSet<T>();
19 public Iterator<T> iterator() { return ts.iterator(); }
21 public P newP(double x, double y, double z) { return newP((float)x, (float)y, (float)z); }
22 public P newP(float x, float y, float z) {
25 if (p2 != null) return p2;
28 try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); }
32 public T newT(P p12, P p23, P p31, V norm) {
33 V norm2 = p31.minus(p12).cross(p23.minus(p12));
34 float dot = norm.dot(norm2);
35 if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
36 if (dot < 0) { P p = p12; p12=p23; p23 = p; }
37 return newT(p12, p23, p31);
40 public T newT(P p1, P p2, P p3) {
44 while(e12.next != e23 || e23.next != e31 || e31.next != e12) {
45 e12.makeAdjacent(e23);
46 e23.makeAdjacent(e31);
47 e31.makeAdjacent(e12);
50 if (e12.t == null) throw new Error();
51 if (e23.t == null) throw new Error();
52 if (e31.t == null) throw new Error();
56 private char allname = 'A';
58 /** [UNIQUE] point in 3-space */
59 public final class P {
64 private E e; // some edge *leaving* this point
65 private M binding = new M();
66 private P bound_to = this;
68 public E makeE(P p2) {
70 if (e != null) return e;
72 if (this.e == null && p2.e == null) return this.e = new E(this, p2);
73 if (this.e == null && p2.e != null) return p2.makeE(this).pair;
74 return new E(getFreeIncident(), p2);
77 public E getFreeIncident() {
78 E ret = getFreeIncident(e, e);
79 if (ret != null) return ret;
80 ret = getFreeIncident(e.pair.next, e.pair.next);
81 if (ret == null) throw new Error("unable to find free incident to " + this);
85 public E getFreeIncident(E start, E before) {
88 if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null) return e.pair;
97 if (e==null) return null;
98 if (e.p1 == this && e.p2 == p2) return e;
104 public boolean isBoundTo(P p) {
107 if (px==this) return true;
113 public void unbind() { bound_to = null; binding = null; }
114 public void bind(P p) { bind(p, new M()); }
115 public void bind(P p, M binding) {
116 if (isBoundTo(p)) return;
117 P temp_bound_to = p.bound_to;
118 M temp_binding = p.binding;
119 p.bound_to = this.bound_to;
120 p.binding = binding.times(this.binding); // FIXME: may have order wrong here
121 this.bound_to = temp_bound_to;
122 this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
125 public void move(V v) {
131 v = v.times(binding);
136 public P(float x, float y, float z) {
137 this.x = x; this.y = y; this.z = z;
142 try { results = kd.nearest(new double[]{x,y,z},2); } catch (Exception e) { throw new Error(e); }
143 if (results[0] != this) throw new Error();
144 return (P)results[1];
147 public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
148 public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
149 public P times(M m) { return m.apply(this); }
150 public boolean equals(Object o) {
151 if (o==null || !(o instanceof P)) return false;
153 return p.x==x && p.y==y && p.z==z;
155 // FIXME: moving a point alters its hashCode
156 public int hashCode() {
158 Float.floatToIntBits(x) ^
159 Float.floatToIntBits(y) ^
160 Float.floatToIntBits(z);
162 public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
163 public String toString() { return "("+x+","+y+","+z+")"; }
165 V norm = new V(0, 0, 0);
168 if (e.t != null) norm = norm.plus(e.t.norm().times((float)e.prev.angle()));
170 } while(e != this.e);
175 /** vector in 3-space */
176 public final class V {
177 public final float x, y, z;
178 public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
179 public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
180 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); }
181 public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
182 public V norm() { return div(mag()); }
183 public V times(M m) { return m.apply(this); }
184 public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
185 public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
186 public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
187 public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
188 public String toString() { return "<"+x+","+y+","+z+">"; }
191 /** [UNIQUE] an edge */
192 public final class E {
193 public final P p1, p2;
194 T t; // triangle to our "left"
195 E prev; // previous half-edge
196 E next; // next half-edge
197 E pair; // partner half-edge
200 public E bound_to = this;
202 public void bind(E e) { bind(e, new M()); }
203 public void bind(E e, M m) {
204 E old = this.bound_to;
205 this.bound_to = e.bound_to;
209 public void dobind() {
210 for(E ex = bound_to; ex != this; ex = ex.bound_to) {
216 public boolean destroyed = false;
217 public void shatter() {
218 if (destroyed) return;
220 HashSet<E> eh = new HashSet<E>();
222 for(E ex = bound_to; ex != this; ex = ex.bound_to) eh.add(ex);
223 E[] es = (E[])eh.toArray(new E[0]);
227 for(E ex = bound_to; ex != this; ex = ex.bound_to) ex.shatter();
229 public void destroy() {
230 this.destroyed = true;
233 private void sync() {
234 this.prev.next = this;
235 this.next.prev = this;
236 this.pair.pair = this;
237 if (this.next.p1 != p2) throw new Error();
238 if (this.prev.p2 != p1) throw new Error();
239 if (this.p1.e == null) this.p1.e = this;
242 public T makeT() { return t==null ? (t = new T(this)) : t; }
244 /** angle between this half-edge and the next */
245 public double angle() {
246 V v1 = next.p2.minus(p2);
247 V v2 = this.p1.minus(p2);
248 return Math.acos(v1.norm().dot(v2.norm()));
251 public void makeAdjacent(E e) {
252 if (this.next == e) return;
253 if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex");
254 if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free");
256 E freeIncident = p2.getFreeIncident(e, this);
258 e.prev.next = freeIncident.next;
259 freeIncident.next.prev = e.prev;
261 freeIncident.next = this.next;
262 this.next.prev = freeIncident;
271 /** creates an isolated edge out in the middle of space */
272 public E(P p1, P p2) {
273 if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
276 this.prev = this.next = this.pair = new E(this, this, this);
280 /** adds a new half-edge from prev.p2 to p2 */
281 public E(E prev, P p2) {
285 if (p2.getE(p1) != null) throw new Error();
287 this.next = this.pair = new E(this, this, prev.next);
289 E q = p2.getFreeIncident();
291 this.next.prev = this;
293 this.prev.next = this;
294 this.pair = new E(q, this, z);
299 /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */
300 public E(E prev, E pair, E next) {
308 public P midpoint() { return newP((p1.x+p2.x)/2, (p1.y+p2.y)/2, (p1.z+p2.z)/2); }
309 public boolean has(P p) { return p==p1 || p==p2; }
310 public float length() { return p1.minus(p2).mag(); }
311 public String toString() { return p1+"->"+p2; }
314 /** [UNIQUE] a triangle (face) */
315 public final class T {
317 public final int color;
323 if (e1==e2 || e1==e3) throw new Error();
324 if (e3.next!=e1) throw new Error();
325 if (e1.t!=null || e2.t!=null || e3.t!=null)
326 throw new Error("non-manifold surface or disagreeing normals");
329 e1.next.next.t = this;
331 // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
333 int color = Math.abs(random.nextInt());
336 if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; }
337 if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; }
338 if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
347 public P p1() { return e1.p1; }
348 public P p2() { return e1.p2; }
349 public P p3() { return e1.next.p2; }
350 public E e1() { return e1; }
351 public E e2() { return e1.next; }
352 public E e3() { return e1.prev; }
353 public V norm() { return p2().minus(p1()).cross(p3().minus(p1())).norm(); }
354 public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
355 public boolean has(P p) { return p1()==p || p2()==p || p3()==p; }
356 public void glVertices(GL gl) {
362 public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
363 (p1().y+p2().y+p3().y)/3,
364 (p1().z+p2().z+p3().z)/3); }
365 public float diameter() {
366 // FIXME: what is this supposed to be?
367 return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2;
377 public P apply(P p) { return p; }
378 public V apply(V v) { return v; }
379 public M invert() { return this; }
380 public M times(M m) { return this; }