X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2FGeom.java;h=08b7cc1dc399ff1d3f9404a28d845633bafcab2d;hb=c257689076da7472ec2aff9d5d940647715ecf08;hp=944ee61508d30c6e40ec023aea9bf9fce7caf231;hpb=bb4936991545937dbde5d59a3fd230aeca7fb481;p=anneal.git diff --git a/src/Geom.java b/src/Geom.java index 944ee61..08b7cc1 100644 --- a/src/Geom.java +++ b/src/Geom.java @@ -5,14 +5,19 @@ import javax.swing.*; import javax.media.opengl.*; import javax.media.opengl.glu.*; +// FEATURE: octree for nearest-point queries? Could make moving points around problematic. + public class Geom implements Iterable { + public static float EPSILON = (float)0.000001; + private HashMap ps = new HashMap(); private HashMap es = new HashMap(); - private HashSet ts = new HashSet(); + private HashSet ts = new HashSet(); public Iterator iterator() { return ts.iterator(); } + public P newP(double x, double y, double z) { return newP((float)x, (float)y, (float)z); } public P newP(float x, float y, float z) { P p = new P(x, y, z); P p2 = ps.get(p); @@ -29,21 +34,73 @@ public class Geom implements Iterable { return e; } - public T newT(E e1, E e2, E e3) { + public T newT(P p1, P p2, P p3) { + return newT(newE(p1, p2), newE(p2, p3), newE(p3, p1), p3.minus(p1).cross(p2.minus(p1))); + } + + /** ensures that e1.cross(e2).norm()==e2.cross(e3).norm()==e3.cross(e1).norm()==t.norm() */ + public T newT(E e1, E e2, E e3, V norm) { + P p12 = e1.shared(e2); + P p23 = e2.shared(e3); + P p31 = e3.shared(e1); + V norm2 = p31.minus(p12).cross(p23.minus(p12)); + float dot = norm.dot(norm2); + if (Math.abs(dot) < EPSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2); + if (dot < 0) { E t = e1; e1 = e3; e2 = e2; e3 = t; } if (e1.t1 != null && e1.t1.hasE(e1) && e1.t1.hasE(e2) && e1.t1.hasE(e3)) return e1.t1; if (e1.t2 != null && e1.t2.hasE(e1) && e1.t2.hasE(e2) && e1.t2.hasE(e3)) return e1.t2; if (e2.t1 != null && e2.t1.hasE(e1) && e2.t1.hasE(e2) && e2.t1.hasE(e3)) return e2.t1; if (e2.t2 != null && e2.t2.hasE(e1) && e2.t2.hasE(e2) && e2.t2.hasE(e3)) return e2.t2; if (e3.t1 != null && e3.t1.hasE(e1) && e3.t1.hasE(e2) && e3.t1.hasE(e3)) return e3.t1; if (e3.t2 != null && e3.t2.hasE(e1) && e3.t2.hasE(e2) && e3.t2.hasE(e3)) return e3.t2; - return new T(e1, e2, e3); + T ret = new T(e1, e2, e3); + ts.add(ret); + return ret; } - /** point in 3-space */ + /** [UNIQUE] point in 3-space */ public final class P { - public final float x, y, z; + + float x, y, z; + + private T t = null; // any of the triangles incident at this point + + private M binding = new M(); + private P bound_to = this; + + public void unbind() { bound_to = null; binding = null; } + public void bind(P p) { bind(p, new M()); } + public void bind(P p, M binding) { + + P px = p; + do { + if (px==this) return; // already bound + px = px.bound_to; + } while(px != p); + + P temp_bound_to = p.bound_to; + M temp_binding = p.binding; + p.bound_to = this.bound_to; + p.binding = binding.times(this.binding); // FIXME: may have order wrong here + this.bound_to = temp_bound_to; + this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here + } + + public void move(V v) { + P p = this; + do { + p.x = p.x+v.x; + p.y = p.y+v.y; + p.z = p.z+v.z; + v = v.times(binding); + p = p.bound_to; + } while (p != this); + } + public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; } - public V minus(P p) { return null; } + public V minus(P p) { return new V(x-p.x, y-p.y, z-p.z); } + public P plus(V v) { return newP(x+v.x, y+v.y, z+v.z); } + public P times(M m) { return m.apply(this); } public boolean equals(Object o) { if (o==null || !(o instanceof P)) return false; P p = (P)o; @@ -56,23 +113,46 @@ public class Geom implements Iterable { Float.floatToIntBits(z); } public void glVertex(GL gl) { gl.glVertex3f(x, y, z); } + public String toString() { return "("+x+","+y+","+z+")"; } + public V norm() { + if (t==null) throw new Error("attempt to get vertex normal for point which does not belong to any triangles"); + T ti = t; + V norm = new V(0, 0, 0); + do { + norm = norm.plus(ti.norm().times((float)ti.angle(this))); + ti = ti.nextT(this); + } while(ti != t); + return norm.norm(); + } } /** vector in 3-space */ public final class V { - private final float x, y, z; + public final float x, y, z; + public V(double x, double y, double z) { this((float)x, (float)y, (float)z); } public V(float x, float y, float z) { this.x = x; this.y = y; this.z = z; } - public V norm() { return null; /* FIXME */ } - public boolean sameDirection(V v) { throw new Error(); } - public V cross(V v) { return null; } + 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); } + public V plus(V v) { return new V(x+v.x, y+v.y, z+v.z); } + public V norm() { return div(mag()); } + public V times(M m) { return m.apply(this); } + public float mag() { return (float)Math.sqrt(x*x+y*y+z*z); } + public float dot(V v) { return x*v.x + y*v.y + z*v.z; } + public V times(float mag) { return new V(x*mag, y*mag, z*mag); } + public V div(float mag) { return new V(x/mag, y/mag, z/mag); } + public String toString() { return "<"+x+","+y+","+z+">"; } } - /** an edge */ + /** [UNIQUE] an edge */ public final class E { public final P p1, p2; T t1, t2; - public E(P p1, P p2) { this.p1 = p1; this.p2 = p2; } + public E(P p1, P p2) { + if (p1==p2) throw new Error("attempt to create edge with single vertex: " + p1); + this.p1 = p1; + this.p2 = p2; + } public int hashCode() { return p1.hashCode() ^ p2.hashCode(); } + public float length() { return p1.minus(p2).mag(); } public boolean equals(Object o) { if (o==null || !(o instanceof E)) return false; E e = (E)o; @@ -94,29 +174,44 @@ public class Geom implements Iterable { if (p2==e.p2) return p1; throw new Error("no shared vertex in unshared()"); } + public T other(T t) { + if (t1==t) return t2; + if (t2==t) return t1; + throw new Error("edge " + this + " does not own triangle " + t); + } + public P other(P p) { + if (p==p1) return p2; + if (p==p2) return p1; + throw new Error("edge " + this + " does not own point " + p); + } } - /** a triangle (face) */ + /** [UNIQUE] a triangle (face) */ public final class T { public final E e1, e2, e3; - public T(E e1, E e2, E e3, V normal) { - P p1 = e1.shared(e2); - P p2 = e2.shared(e3); - P p3 = e3.shared(e1); - V norm = p2.minus(p1).cross(p3.minus(p1)); - if (norm.sameDirection(normal)) { - this.e1 = e1; - this.e2 = e2; - this.e3 = e3; - } else { - this.e1 = e3; - this.e2 = e2; - this.e3 = e1; - } + T(E e1, E e2, E e3) { + if (e1.p1.t==null) e1.p1.t = this; + if (e1.p2.t==null) e1.p2.t = this; + if (e2.p1.t==null) e2.p1.t = this; + if (e2.p2.t==null) e2.p2.t = this; + if (e3.p1.t==null) e3.p1.t = this; + if (e3.p2.t==null) e3.p2.t = this; + if (e1==e2) throw new Error("attempt to create triangle with duplicate edge: " + e1); + if (e2==e3) throw new Error("attempt to create triangle with duplicate edge: " + e2); + if (e3==e1) throw new Error("attempt to create triangle with duplicate edge: " + e3); + // check that each pair of edges shares a vertex + e1.shared(e2); + e2.shared(e3); + e3.shared(e1); + this.e1 = e1; + this.e2 = e2; + this.e3 = e3; + // FEATURE: colinearity/sliverness check? if (e1.t1 == null) e1.t1 = this; else if (e1.t2 == null) e1.t2 = this; else throw new Error("non-manifold surface"); if (e2.t1 == null) e2.t1 = this; else if (e2.t2 == null) e2.t2 = this; else throw new Error("non-manifold surface"); if (e3.t1 == null) e3.t1 = this; else if (e3.t2 == null) e3.t2 = this; else throw new Error("non-manifold surface"); - ts.add(this); + // FIXME: check that triangles we share an edge with agree on the direction of the normal vector + // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?) } public V norm() { P p1 = e1.shared(e2); @@ -124,38 +219,60 @@ public class Geom implements Iterable { P p3 = e3.shared(e1); return p2.minus(p1).cross(p3.minus(p1)).norm(); } - public T(E e1, E e2, E e3) { - this.e1 = e1; - this.e2 = e2; - this.e3 = e3; - if (e1.t1 == null) e1.t1 = this; else if (e1.t2 == null) e1.t2 = this; else throw new Error("non-manifold surface"); - if (e2.t1 == null) e2.t1 = this; else if (e2.t2 == null) e2.t2 = this; else throw new Error("non-manifold surface"); - if (e3.t1 == null) e3.t1 = this; else if (e3.t2 == null) e3.t2 = this; else throw new Error("non-manifold surface"); - ts.add(this); - } public boolean hasE(E e) { return e1==e || e2==e || e3==e; } + public void glVertices(GL gl) { + p1().glVertex(gl); + p2().glVertex(gl); + p3().glVertex(gl); + } + public P p1() { return e1.shared(e2); } + public P p2() { return e1.shared(e3); } + public P p3() { return e3.shared(e2); } + public P centroid() { return newP((p1().x+p2().x+p3().x)/3, + (p1().y+p2().y+p3().y)/3, + (p1().z+p2().z+p3().z)/3); } + public float diameter() { + // FIXME: what is this supposed to be? + return Math.max(Math.max(e1.length(), e2.length()), e3.length()) / 2; + } - // technically not required - /* - public int hashCode() { return e1.hashCode() ^ e2.hashCode() ^ e3.hashCode(); } - public boolean equals(Object o) { - if (o==null || !(o instanceof T)) return false; - T t = (T)o; - if (this.e1 == t.e1 && this.e2 == t.e2 && this.e3 == t.e3) return true; - if (this.e1 == t.e2 && this.e2 == t.e3 && this.e3 == t.e1) return true; - if (this.e1 == t.e3 && this.e2 == t.e1 && this.e3 == t.e2) return true; - return false; + /** returns the next triangle walking clockwise around the vertex normal */ + public T nextT(P p) { return prevE(p).other(this); } + public T prevT(P p) { return nextE(p).other(this); } + + /** edge "after" this point, moving clockwise around the normal */ + public E nextE(P p) { + if (p == e1.shared(e2)) return e1; + else if (p == e2.shared(e3)) return e2; + else if (p == e3.shared(e1)) return e3; + else throw new Error("triangle " + this + " does not own point " + p); } - */ - public void glVertices(GL gl) { - e1.unshared(e2).glVertex(gl); - e1.shared(e2).glVertex(gl); - e2.shared(e3).glVertex(gl); + + /** edge "before" this point, moving clockwise around the normal */ + public E prevE(P p) { + if (p == e1.shared(e2)) return e2; + else if (p == e2.shared(e3)) return e3; + else if (p == e3.shared(e1)) return e1; + else throw new Error("triangle " + this + " does not own point " + p); + } + + /** returns the angle at point p */ + public double angle(P p) { + V v1 = nextE(p).other(p).minus(p); + V v2 = prevE(p).other(p).minus(p); + return Math.acos(v1.norm().dot(v2.norm())); } + } + /** matrix */ public class M { + public M() { } + public P apply(P p) { return p; } + public V apply(V v) { return v; } + public M invert() { return this; } + public M times(M m) { return this; } } }