3 import java.awt.event.*;
5 import javax.media.opengl.*;
6 import javax.media.opengl.glu.*;
8 public class Geom implements Iterable<Geom.T> {
10 public static float EPSILON = (float)0.000001;
12 private HashMap<P,P> ps = new HashMap<P,P>();
13 private HashMap<E,E> es = new HashMap<E,E>();
14 private HashSet<T> ts = new HashSet<T>();
16 public Iterator<T> iterator() { return ts.iterator(); }
18 public P newP(float x, float y, float z) {
21 if (p2 != null) return p2;
26 public E newE(P p1, P p2) {
29 if (e2 != null) return e2;
34 public T newT(E e1, E e2, E e3, V norm) {
38 // FEATURE: colinearity check?
39 V norm2 = p2.minus(p1).cross(p3.minus(p1));
40 float dot = norm.dot(norm2);
41 if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2);
42 if (dot < 0) { E t = e1; e1 = e3; e2 = e2; e3 = t; }
43 if (e1.t1 != null && e1.t1.hasE(e1) && e1.t1.hasE(e2) && e1.t1.hasE(e3)) return e1.t1;
44 if (e1.t2 != null && e1.t2.hasE(e1) && e1.t2.hasE(e2) && e1.t2.hasE(e3)) return e1.t2;
45 if (e2.t1 != null && e2.t1.hasE(e1) && e2.t1.hasE(e2) && e2.t1.hasE(e3)) return e2.t1;
46 if (e2.t2 != null && e2.t2.hasE(e1) && e2.t2.hasE(e2) && e2.t2.hasE(e3)) return e2.t2;
47 if (e3.t1 != null && e3.t1.hasE(e1) && e3.t1.hasE(e2) && e3.t1.hasE(e3)) return e3.t1;
48 if (e3.t2 != null && e3.t2.hasE(e1) && e3.t2.hasE(e2) && e3.t2.hasE(e3)) return e3.t2;
49 T ret = new T(e1, e2, e3);
54 /** [UNIQUE] point in 3-space */
55 public final class P {
56 public final float x, y, z;
57 private T t = null; // any of the triangles incident at this point
58 public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
59 public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); }
60 public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); }
61 public boolean equals(Object o) {
62 if (o==null || !(o instanceof P)) return false;
64 return p.x==x && p.y==y && p.z==z;
66 public int hashCode() {
68 Float.floatToIntBits(x) ^
69 Float.floatToIntBits(y) ^
70 Float.floatToIntBits(z);
72 public void glVertex(GL gl) { gl.glVertex3f(x, y, z); }
73 public String toString() { return "("+x+","+y+","+z+")"; }
75 if (t==null) throw new Error("attempt to get vertex normal for point which does not belong to any triangles");
77 V norm = new V(0, 0, 0);
79 norm = norm.plus(ti.norm().times((float)ti.angle(this)));
86 /** vector in 3-space */
87 public final class V {
88 private final float x, y, z;
89 public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; }
90 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); }
91 public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); }
92 public V norm() { float m = mag(); return new V(x/m, y/m, z/m); }
93 public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); }
94 public float dot(V v) { return x*v.x + y*v.y + z*v.z; }
95 public V times(float mag) { return new V(x*mag, y*mag, z*mag); }
96 public String toString() { return "<"+x+","+y+","+z+">"; }
99 /** [UNIQUE] an edge */
100 public final class E {
101 public final P p1, p2;
103 public E(P p1, P p2) { this.p1 = p1; this.p2 = p2; }
104 public int hashCode() { return p1.hashCode() ^ p2.hashCode(); }
105 public float length() { return p1.minus(p2).mag(); }
106 public boolean equals(Object o) {
107 if (o==null || !(o instanceof E)) return false;
109 if (this.p1 == e.p1 && this.p2 == e.p2) return true;
110 if (this.p2 == e.p1 && this.p1 == e.p2) return true;
113 public P shared(E e) {
114 if (p1==e.p1) return p1;
115 if (p1==e.p2) return p1;
116 if (p2==e.p1) return p2;
117 if (p2==e.p2) return p2;
118 throw new Error("no shared vertex in shared()");
120 public P unshared(E e) {
121 if (p1==e.p1) return p2;
122 if (p1==e.p2) return p2;
123 if (p2==e.p1) return p1;
124 if (p2==e.p2) return p1;
125 throw new Error("no shared vertex in unshared()");
127 public T other(T t) {
128 if (t1==t) return t2;
129 if (t2==t) return t1;
130 throw new Error("edge " + this + " does not own triangle " + t);
132 public P other(P p) {
133 if (p==p1) return p2;
134 if (p==p2) return p1;
135 throw new Error("edge " + this + " does not own point " + p);
139 /** [UNIQUE] a triangle (face) */
140 public final class T {
141 public final E e1, e2, e3;
143 P p1 = e1.shared(e2);
144 P p2 = e2.shared(e3);
145 P p3 = e3.shared(e1);
146 return p2.minus(p1).cross(p3.minus(p1)).norm();
148 T(E e1, E e2, E e3) {
149 if (e1.p1.t==null) e1.p1.t = this;
150 if (e1.p2.t==null) e1.p2.t = this;
151 if (e2.p1.t==null) e2.p1.t = this;
152 if (e2.p2.t==null) e2.p2.t = this;
153 if (e3.p1.t==null) e3.p1.t = this;
154 if (e3.p2.t==null) e3.p2.t = this;
158 if (e1.t1 == null) e1.t1 = this; else if (e1.t2 == null) e1.t2 = this; else throw new Error("non-manifold surface");
159 if (e2.t1 == null) e2.t1 = this; else if (e2.t2 == null) e2.t2 = this; else throw new Error("non-manifold surface");
160 if (e3.t1 == null) e3.t1 = this; else if (e3.t2 == null) e3.t2 = this; else throw new Error("non-manifold surface");
162 public boolean hasE(E e) { return e1==e || e2==e || e3==e; }
163 public void glVertices(GL gl) {
168 public P p1() { return e1.shared(e2); }
169 public P p2() { return e1.shared(e3); }
170 public P p3() { return e3.shared(e2); }
171 public P centroid() { return newP((p1().x+p2().x+p3().x)/3,
172 (p1().y+p2().y+p3().y)/3,
173 (p1().z+p2().z+p3().z)/3); }
174 public float diameter() {
175 // FIXME: what is this supposed to be?
176 return Math.max(Math.max(e1.length(), e2.length()), e3.length()) / 2;
179 // FIXME: ambiguity firstEdge or secondEdge?
180 /** returns the next triangle walking "around" shared vertex p */
181 public T next(P p) { return secondEdge(p).other(this); }
183 public E firstEdge(P p) {
184 if (p == e1.shared(e2)) return e1;
185 else if (p == e2.shared(e3)) return e2;
186 else if (p == e3.shared(e1)) return e3;
187 else throw new Error("triangle " + this + " does not own point " + p);
190 public E secondEdge(P p) {
191 if (p == e1.shared(e2)) return e2;
192 else if (p == e2.shared(e3)) return e3;
193 else if (p == e3.shared(e1)) return e1;
194 else throw new Error("triangle " + this + " does not own point " + p);
197 /** returns the angle at point p */
198 public double angle(P p) {
199 V v1 = firstEdge(p).other(p).minus(p);
200 V v2 = secondEdge(p).other(p).minus(p);
201 return Math.acos(v1.norm().dot(v2.norm()));