public static Random random = new Random();
private HashMap<P,P> ps = new HashMap<P,P>();
- private HashMap<E,E> es = new HashMap<E,E>();
private HashSet<T> ts = new HashSet<T>();
public Iterator<T> iterator() { return ts.iterator(); }
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';
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 {
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 {
} 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;
}
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();
}
}
public String toString() { return "<"+x+","+y+","+z+">"; }
}
+ public class BindingGroup {
+ public HashSet<E> es = new HashSet<E>();
+ 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<E> eh = new HashSet<E>();
+ 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) {
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;
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 */
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();
}
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) */
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; }
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; }
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()));
- }
- */
}