3 import java.awt.event.*;
5 import javax.media.opengl.*;
6 import javax.media.opengl.glu.*;
8 // FEATURE: octree for nearest-point queries? Could make moving points around problematic.
10 public class Geom implements Iterable<Geom.T> {
12 public static float EPSILON = (float)0.000001;
14 private HashMap<P,P> ps = new HashMap<P,P>();
15 private HashMap<E,E> es = new HashMap<E,E>();
16 private HashSet<T> ts = new HashSet<T>();
18 public Iterator<T> iterator() { return ts.iterator(); }
20 public P newP(double x, double y, double z) { return newP((float)x, (float)y, (float)z); }
21 public P newP(float x, float y, float z) {
24 if (p2 != null) return p2;
29 public E newE(P p1, P p2) {
32 if (e2 != null) return e2;
37 public T newT(P p1, P p2, P p3) {
38 return newT(newE(p1, p2), newE(p2, p3), newE(p3, p1), p3.minus(p1).cross(p2.minus(p1)));
41 /** ensures that e1.cross(e2).norm()==e2.cross(e3).norm()==e3.cross(e1).norm()==t.norm() */
42 public T newT(E e1, E e2, E e3, V norm) {
43 P p12 = e1.shared(e2);
44 P p23 = e2.shared(e3);
45 P p31 = e3.shared(e1);
46 V norm2 = p31.minus(p12).cross(p23.minus(p12));
47 float dot = norm.dot(norm2);
48 if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
49 if (dot < 0) { E t = e1; e1 = e3; e2 = e2; e3 = t; }
50 if (e1.t1 != null && e1.t1.hasE(e1) && e1.t1.hasE(e2) && e1.t1.hasE(e3)) return e1.t1;
51 if (e1.t2 != null && e1.t2.hasE(e1) && e1.t2.hasE(e2) && e1.t2.hasE(e3)) return e1.t2;
52 if (e2.t1 != null && e2.t1.hasE(e1) && e2.t1.hasE(e2) && e2.t1.hasE(e3)) return e2.t1;
53 if (e2.t2 != null && e2.t2.hasE(e1) && e2.t2.hasE(e2) && e2.t2.hasE(e3)) return e2.t2;
54 if (e3.t1 != null && e3.t1.hasE(e1) && e3.t1.hasE(e2) && e3.t1.hasE(e3)) return e3.t1;
55 if (e3.t2 != null && e3.t2.hasE(e1) && e3.t2.hasE(e2) && e3.t2.hasE(e3)) return e3.t2;
56 T ret = new T(e1, e2, e3);
61 /** [UNIQUE] point in 3-space */
62 public final class P {
66 private T t = null; // any of the triangles incident at this point
68 private M binding = new M();
69 private P bound_to = this;
71 public void unbind() { bound_to = null; binding = null; }
72 public void bind(P p) { bind(p, new M()); }
73 public void bind(P p, M binding) {
77 if (px==this) return; // already bound
81 P temp_bound_to = p.bound_to;
82 M temp_binding = p.binding;
83 p.bound_to = this.bound_to;
84 p.binding = binding.times(this.binding); // FIXME: may have order wrong here
85 this.bound_to = temp_bound_to;
86 this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
89 public void move(V v) {
100 public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
101 public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
102 public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
103 public P times(M m) { return m.apply(this); }
104 public boolean equals(Object o) {
105 if (o==null || !(o instanceof P)) return false;
107 return p.x==x && p.y==y && p.z==z;
109 public int hashCode() {
111 Float.floatToIntBits(x) ^
112 Float.floatToIntBits(y) ^
113 Float.floatToIntBits(z);
115 public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
116 public String toString() { return "("+x+","+y+","+z+")"; }
118 if (t==null) throw new Error("attempt to get vertex normal for point which does not belong to any triangles");
120 V norm = new V(0, 0, 0);
122 norm = norm.plus(ti.norm().times((float)ti.angle(this)));
129 /** vector in 3-space */
130 public final class V {
131 public final float x, y, z;
132 public V(double x, double y, double z) { this((float)x, (float)y, (float)z); }
133 public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
134 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); }
135 public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
136 public V norm() { return div(mag()); }
137 public V times(M m) { return m.apply(this); }
138 public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
139 public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
140 public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
141 public V div(float mag) { return new V(x/mag, y/mag, z/mag); }
142 public String toString() { return "<"+x+","+y+","+z+">"; }
145 /** [UNIQUE] an edge */
146 public final class E {
147 public final P p1, p2;
149 public E(P p1, P p2) {
150 if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1);
154 public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
155 public float length() { return p1.minus(p2).mag(); }
156 public boolean equals(Object o) {
157 if (o==null || !(o instanceof E)) return false;
159 if (this.p1 == e.p1 && this.p2 == e.p2) return true;
160 if (this.p2 == e.p1 && this.p1 == e.p2) return true;
163 public P shared(E e) {
164 if (p1==e.p1) return p1;
165 if (p1==e.p2) return p1;
166 if (p2==e.p1) return p2;
167 if (p2==e.p2) return p2;
168 throw new Error("no shared vertex in shared()");
170 public P unshared(E e) {
171 if (p1==e.p1) return p2;
172 if (p1==e.p2) return p2;
173 if (p2==e.p1) return p1;
174 if (p2==e.p2) return p1;
175 throw new Error("no shared vertex in unshared()");
177 public T other(T t) {
178 if (t1==t) return t2;
179 if (t2==t) return t1;
180 throw new Error("edge " + this + " does not own triangle " + t);
182 public P other(P p) {
183 if (p==p1) return p2;
184 if (p==p2) return p1;
185 throw new Error("edge " + this + " does not own point " + p);
189 /** [UNIQUE] a triangle (face) */
190 public final class T {
191 public final E e1, e2, e3;
192 T(E e1, E e2, E e3) {
193 if (e1.p1.t==null) e1.p1.t = this;
194 if (e1.p2.t==null) e1.p2.t = this;
195 if (e2.p1.t==null) e2.p1.t = this;
196 if (e2.p2.t==null) e2.p2.t = this;
197 if (e3.p1.t==null) e3.p1.t = this;
198 if (e3.p2.t==null) e3.p2.t = this;
199 if (e1==e2) throw new Error("attempt to create triangle with duplicate edge: " + e1);
200 if (e2==e3) throw new Error("attempt to create triangle with duplicate edge: " + e2);
201 if (e3==e1) throw new Error("attempt to create triangle with duplicate edge: " + e3);
202 // check that each pair of edges shares a vertex
209 // FEATURE: colinearity/sliverness check?
210 if (e1.t1 == null) e1.t1 = this; else if (e1.t2 == null) e1.t2 = this; else throw new Error("non-manifold surface");
211 if (e2.t1 == null) e2.t1 = this; else if (e2.t2 == null) e2.t2 = this; else throw new Error("non-manifold surface");
212 if (e3.t1 == null) e3.t1 = this; else if (e3.t2 == null) e3.t2 = this; else throw new Error("non-manifold surface");
213 // FIXME: check that triangles we share an edge with agree on the direction of the normal vector
214 // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
217 P p1 = e1.shared(e2);
218 P p2 = e2.shared(e3);
219 P p3 = e3.shared(e1);
220 return p2.minus(p1).cross(p3.minus(p1)).norm();
222 public boolean hasE(E e) { return e1==e || e2==e || e3==e; }
223 public void glVertices(GL gl) {
228 public P p1() { return e1.shared(e2); }
229 public P p2() { return e1.shared(e3); }
230 public P p3() { return e3.shared(e2); }
231 public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
232 (p1().y+p2().y+p3().y)/3,
233 (p1().z+p2().z+p3().z)/3); }
234 public float diameter() {
235 // FIXME: what is this supposed to be?
236 return Math.max(Math.max(e1.length(), e2.length()), e3.length()) / 2;
239 /** returns the next triangle walking clockwise around the vertex normal */
240 public T nextT(P p) { return prevE(p).other(this); }
241 public T prevT(P p) { return nextE(p).other(this); }
243 /** edge "after" this point, moving clockwise around the normal */
244 public E nextE(P p) {
245 if (p == e1.shared(e2)) return e1;
246 else if (p == e2.shared(e3)) return e2;
247 else if (p == e3.shared(e1)) return e3;
248 else throw new Error("triangle " + this + " does not own point " + p);
251 /** edge "before" this point, moving clockwise around the normal */
252 public E prevE(P p) {
253 if (p == e1.shared(e2)) return e2;
254 else if (p == e2.shared(e3)) return e3;
255 else if (p == e3.shared(e1)) return e1;
256 else throw new Error("triangle " + this + " does not own point " + p);
259 /** returns the angle at point p */
260 public double angle(P p) {
261 V v1 = nextE(p).other(p).minus(p);
262 V v2 = prevE(p).other(p).minus(p);
263 return Math.acos(v1.norm().dot(v2.norm()));
272 public P apply(P p) { return p; }
273 public V apply(V v) { return v; }
274 public M invert() { return this; }
275 public M times(M m) { return this; }