X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2FGeom.java;h=445c896f391e1229d3d16e23d1bf004e0057cf9a;hb=04b2e2c139e2087242fa911a6d3a8991d285bbb3;hp=558332de03ffdd4cb68c74da8e061fc418ef16d0;hpb=207c278791e5d7b53cdb099cb67bb5df713e59d9;p=anneal.git diff --git a/src/Geom.java b/src/Geom.java index 558332d..445c896 100644 --- a/src/Geom.java +++ b/src/Geom.java @@ -14,7 +14,6 @@ public class Geom implements Iterable { public static Random random = new Random(); private HashMap ps = new HashMap(); - private HashMap es = new HashMap(); private HashSet ts = new HashSet(); public Iterator iterator() { return ts.iterator(); } @@ -47,7 +46,11 @@ public class Geom implements Iterable { e23.makeAdjacent(e31); e31.makeAdjacent(e12); } - return e12.newT(); + T ret = e12.makeT(); + if (e12.t == null) throw new Error(); + if (e23.t == null) throw new Error(); + if (e31.t == null) throw new Error(); + return ret; } private char allname = 'A'; @@ -65,20 +68,20 @@ public class Geom implements Iterable { public E makeE(P p2) { E e = getE(p2); if (e != null) return e; + e = p2.getE(this); if (this.e == null && p2.e == null) return this.e = new E(this, p2); if (this.e == null && p2.e != null) return p2.makeE(this).pair; - - e = getFreeIncident(); - if (e==null) throw new Error("could not find free incident to " + this); - return new E(e, p2); + return new E(getFreeIncident(), p2); } public E getFreeIncident() { E ret = getFreeIncident(e, e); if (ret != null) return ret; ret = getFreeIncident(e.pair.next, e.pair.next); + if (ret == null) throw new Error("unable to find free incident to " + this); return ret; } + public E getFreeIncident(E start, E before) { E e = start; do { @@ -88,15 +91,6 @@ public class Geom implements Iterable { return null; } - public E listIncidents(E start, E before) { - E e = start; - do { - if (e.pair.p2 == this && e.pair.t == null) System.out.println(e.pair + " / " + e.pair.t); - e = e.pair.next; - } while(e != before); - return null; - } - public E getE(P p2) { E e = this.e; do { @@ -139,16 +133,6 @@ public class Geom implements Iterable { } while (p != this); } - /** the next edge going around this point [FIXME: direction] */ - /* - public E nextE(E e) { - //e.other(this); // sanity check - if (e.t != null && e.t.nextE(e).has(this)) return e.t.nextE(e); - if (e.pair.t != null && e.pair.t.nextE(e).has(this)) return e.pair.nextE(e.pair); - throw new Error(); - } - */ - public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; } @@ -176,20 +160,15 @@ public class Geom implements Iterable { Float.floatToIntBits(z); } public void glVertex(GL gl) { gl.glVertex3f(x, y, z); } - public String toString() { return ""+name; } - //{ return "("+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); + E e = this.e; do { - norm = norm.plus(ti.norm().times((float)ti.angle(this))); - ti = ti.nextT(this); - } while(ti != t); + if (e.t != null) norm = norm.plus(e.t.norm().times((float)e.prev.angle())); + e = e.pair.next; + } while(e != this.e); return norm.norm(); - */ - throw new Error(); } } @@ -209,34 +188,85 @@ public class Geom implements Iterable { public String toString() { return "<"+x+","+y+","+z+">"; } } + public class BindingGroup { + public HashSet es = new HashSet(); + public BindingGroup() { } + public merge(E e) { + if (e.bg != null) merge(e.bg); + else { es.add(e); e.bg = this; } + } + public merge(BindingGroup bg) { + for(E e : bg.es) { + e.bg = this; + this.bg.add(e); + } + } + } + /** [UNIQUE] an edge */ public final class E { public final P p1, p2; - T t; - E prev; - E next; - E pair; + T t; // triangle to our "left" + E prev; // previous half-edge + E next; // next half-edge + E pair; // partner half-edge + + + public BindingGroup bg = null; + + public void bind(E e) { bind(e, new M()); } + public void bind(E e, M m) { + if (e.bg != null) e.bg.merge(this); + else if (bg != null) bg.merge(e); + else { + bg = new BindingGroup(); + bg.merge(this); + bg.merge(e); + } + } - private void syncm() { + public void dobind() { + if (bg==null) return; + for(E ex : bg.es) { + if (ex==this) continue; + p1.bind(ex.p1); + p2.bind(ex.p2); + } + } + + public boolean destroyed = false; + public void shatter() { + if (destroyed) return; + /* + HashSet eh = new HashSet(); + eh.add(this); + for(E ex = bound_to; ex != this; ex = ex.bound_to) eh.add(ex); + E[] es = (E[])eh.toArray(new E[0]); + */ + destroy(); + pair.shatter(); + for(E ex = bound_to; ex != this; ex = ex.bound_to) ex.shatter(); + } + public void destroy() { + this.destroyed = true; + } + + private void sync() { this.prev.next = this; this.next.prev = this; this.pair.pair = this; if (this.next.p1 != p2) throw new Error(); if (this.prev.p2 != p1) throw new Error(); - } - private void sync() { - syncm(); - this.p1.e = this; - System.out.println("make " + this); - /* - if (next != this && next.next != this && next.next.next == this) - newT(); - */ + if (this.p1.e == null) this.p1.e = this; } - public T newT() { - if (t==null) t = new T(this); - return t; + public T makeT() { return t==null ? (t = new T(this)) : t; } + + /** angle between this half-edge and the next */ + public double angle() { + V v1 = next.p2.minus(p2); + V v2 = this.p1.minus(p2); + return Math.acos(v1.norm().dot(v2.norm())); } public void makeAdjacent(E e) { @@ -244,9 +274,7 @@ public class Geom implements Iterable { if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex"); if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free"); - System.out.println(this + ".makeAdjacent("+e+") -- from " + this.next); - E freeIncident = p2.getFreeIncident(); - if (freeIncident==null) throw new Error("unable to find freeIncident"); + E freeIncident = p2.getFreeIncident(e, this); e.prev.next = freeIncident.next; freeIncident.next.prev = e.prev; @@ -257,10 +285,8 @@ public class Geom implements Iterable { this.next = e; e.prev = this; - syncm(); - freeIncident.syncm(); - - //throw new Error("makeAdjacent() failed"); + sync(); + freeIncident.sync(); } /** creates an isolated edge out in the middle of space */ @@ -277,19 +303,16 @@ public class Geom implements Iterable { this.p1 = prev.p2; this.p2 = p2; this.prev = prev; + if (p2.getE(p1) != null) throw new Error(); if (p2.e==null) { this.next = this.pair = new E(this, this, prev.next); } else { E q = p2.getFreeIncident(); - if (q==null) { - System.out.println("listing:"); - p2.listIncidents(p2.e, p2.e); - p2.listIncidents(p2.e.pair.next, p2.e.pair.next); - throw new Error("could not find free incident to " + p2 + " from " + p2.e); - } this.next = q.next; this.next.prev = this; - this.pair = new E(q, this, prev.next); + E z = prev.next; + this.prev.next = this; + this.pair = new E(q, this, z); } sync(); } @@ -307,8 +330,6 @@ public class Geom implements Iterable { public boolean has(P p) { return p==p1 || p==p2; } public float length() { return p1.minus(p2).mag(); } public String toString() { return p1+"->"+p2; } - public int hashCode() { return p1.hashCode() ^ p2.hashCode(); } - public boolean equals(Object o) { return o!=null && o instanceof E && this.p1 == ((E)o).p1 && this.p2 == ((E)o).p2; } } /** [UNIQUE] a triangle (face) */ @@ -316,29 +337,21 @@ public class Geom implements Iterable { public final E e1; public final int color; - public void bind(T t2, int rot) { - // FIXME - } - T(E e1) { this.e1 = e1; E e2 = e1.next; E e3 = e2.next; if (e1==e2 || e1==e3) throw new Error(); if (e3.next!=e1) throw new Error(); - if (e1.t!=null || e2.t!=null || e3.t!=null) throw new Error("non-manifold surface"); + if (e1.t!=null || e2.t!=null || e3.t!=null) + throw new Error("non-manifold surface or disagreeing normals"); e1.t = this; e1.next.t = this; e1.next.next.t = this; - /* - if (e1.pair.t != null && e1.pair.t.nextP(e1) != prevP(e1)) throw new Error("normals disagree!"); - if (e2.pair.t != null && e2.pair.t.nextP(e2) != prevP(e2)) throw new Error("normals disagree!"); - if (e3.pair.t != null && e3.pair.t.nextP(e3) != prevP(e3)) throw new Error("normals disagree!"); - */ + // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?) int color = Math.abs(random.nextInt()); - while(true) { color = color % 4; if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; } @@ -352,14 +365,6 @@ public class Geom implements Iterable { this.color = color; } - /* - 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; - return e1==t.e1() || e1==t.e2() || e1==t.e3(); - } - */ public P p1() { return e1.p1; } public P p2() { return e1.p2; } public P p3() { return e1.next.p2; } @@ -383,46 +388,7 @@ public class Geom implements Iterable { return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2; } - /** returns the next triangle walking clockwise around the vertex normal */ - /* - public T nextT(P p) { return prevE(p).pair.t; } - public T prevT(P p) { return nextE(p).pair.t; } - - public E nextE(E e) { - if (e==e2) return e1; - if (e==e3) return e2; - if (e==e1) return e3; - throw new Error("triangle " + this + " does not own edge " + e); - } - public E prevE(E e) { - if (e==e2) return e3; - if (e==e3) return e1; - if (e==e1) return e2; - throw new Error("triangle " + this + " does not own edge " + e); - } - // 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); - } - // 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())); - } - */ }