From: adam Date: Sun, 2 Dec 2007 00:44:40 +0000 (-0800) Subject: switched to true half-edge X-Git-Url: http://git.megacz.com/?p=anneal.git;a=commitdiff_plain;h=207c278791e5d7b53cdb099cb67bb5df713e59d9 switched to true half-edge darcs-hash:20071202004440-5007d-e41543f8fb19a225ae1dd76a4309240920415efe.gz --- diff --git a/Makefile b/Makefile index 0d6f0c7..7dd5bb1 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,4 @@ all: mkdir -p build - javac -d build `find src -name \*.java` - java -cp build Main + javac -cp lib/kd.jar -d build `find src -name \*.java` + java -cp lib/kd.jar:build Main diff --git a/src/Geom.java b/src/Geom.java index 08b7cc1..558332d 100644 --- a/src/Geom.java +++ b/src/Geom.java @@ -4,12 +4,14 @@ import java.awt.event.*; import javax.swing.*; import javax.media.opengl.*; import javax.media.opengl.glu.*; - -// FEATURE: octree for nearest-point queries? Could make moving points around problematic. +import edu.wlu.cs.levy.CG.KDTree; public class Geom implements Iterable { + private KDTree kd = new KDTree(3); + public static float EPSILON = (float)0.000001; + public static Random random = new Random(); private HashMap ps = new HashMap(); private HashMap es = new HashMap(); @@ -23,61 +25,101 @@ public class Geom implements Iterable { P p2 = ps.get(p); if (p2 != null) return p2; ps.put(p,p); + p.name = allname++; + try { kd.insert(new double[]{p.x,p.y,p.z},p); } catch (Exception e) { throw new Error(e); } return p; } - public E newE(P p1, P p2) { - E e = new E(p1, p2); - E e2 = es.get(e); - if (e2 != null) return e2; - es.put(e,e); - return e; + public T newT(P p12, P p23, P p31, V norm) { + 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) { P p = p12; p12=p23; p23 = p; } + return newT(p12, p23, p31); } 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))); + E e12 = p1.makeE(p2); + E e23 = p2.makeE(p3); + E e31 = p3.makeE(p1); + while(e12.next != e23 || e23.next != e31 || e31.next != e12) { + e12.makeAdjacent(e23); + e23.makeAdjacent(e31); + e31.makeAdjacent(e12); + } + return e12.newT(); } - /** 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; - T ret = new T(e1, e2, e3); - ts.add(ret); - return ret; - } + private char allname = 'A'; /** [UNIQUE] point in 3-space */ public final class P { - - float x, y, z; + char name; - private T t = null; // any of the triangles incident at this point + float x, y, z; + private E e; // some edge *leaving* 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) { + public E makeE(P p2) { + E e = getE(p2); + if (e != null) return e; + 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); + } + + public E getFreeIncident() { + E ret = getFreeIncident(e, e); + if (ret != null) return ret; + ret = getFreeIncident(e.pair.next, e.pair.next); + return ret; + } + public E getFreeIncident(E start, E before) { + E e = start; + do { + if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null) return e.pair; + e = e.pair.next; + } while(e != before); + 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 { + if (e==null) return null; + if (e.p1 == this && e.p2 == p2) return e; + e = e.pair.next; + } while (e!=this.e); + return null; + } + + public boolean isBoundTo(P p) { P px = p; do { - if (px==this) return; // already bound + if (px==this) return true; px = px.bound_to; } while(px != p); + return false; + } + public void unbind() { bound_to = null; binding = null; } + public void bind(P p) { bind(p, new M()); } + public void bind(P p, M binding) { + if (isBoundTo(p)) return; P temp_bound_to = p.bound_to; M temp_binding = p.binding; p.bound_to = this.bound_to; @@ -97,7 +139,27 @@ public class Geom implements Iterable { } while (p != this); } - public P(float x, float y, float z) { this.x = x; this.y = y; this.z = z; } + /** 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; + } + + public P nearest() { + Object[] results; + try { results = kd.nearest(new double[]{x,y,z},2); } catch (Exception e) { throw new Error(e); } + if (results[0] != this) throw new Error(); + return (P)results[1]; + } + 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); } @@ -106,6 +168,7 @@ public class Geom implements Iterable { P p = (P)o; return p.x==x && p.y==y && p.z==z; } + // FIXME: moving a point alters its hashCode public int hashCode() { return Float.floatToIntBits(x) ^ @@ -113,8 +176,10 @@ 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 String toString() { return ""+name; } + //{ 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); @@ -123,6 +188,8 @@ public class Geom implements Iterable { ti = ti.nextT(this); } while(ti != t); return norm.norm(); + */ + throw new Error(); } } @@ -145,110 +212,203 @@ public class Geom implements Iterable { /** [UNIQUE] an edge */ public final class E { public final P p1, p2; - T t1, t2; + T t; + E prev; + E next; + E pair; + + private void syncm() { + 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(); + */ + } + + public T newT() { + if (t==null) t = new T(this); + return t; + } + + public void makeAdjacent(E e) { + if (this.next == e) return; + 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.prev.next = freeIncident.next; + freeIncident.next.prev = e.prev; + + freeIncident.next = this.next; + this.next.prev = freeIncident; + + this.next = e; + e.prev = this; + + syncm(); + freeIncident.syncm(); + + //throw new Error("makeAdjacent() failed"); + } + + /** creates an isolated edge out in the middle of space */ 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; + this.prev = this.next = this.pair = new E(this, this, this); + sync(); } - 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; - if (this.p1 == e.p1 && this.p2 == e.p2) return true; - if (this.p2 == e.p1 && this.p1 == e.p2) return true; - return false; + + /** adds a new half-edge from prev.p2 to p2 */ + public E(E prev, P p2) { + this.p1 = prev.p2; + this.p2 = p2; + this.prev = prev; + 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); + } + sync(); } - public P shared(E e) { - if (p1==e.p1) return p1; - if (p1==e.p2) return p1; - if (p2==e.p1) return p2; - if (p2==e.p2) return p2; - throw new Error("no shared vertex in shared()"); - } - public P unshared(E e) { - if (p1==e.p1) return p2; - if (p1==e.p2) return p2; - if (p2==e.p1) return p1; - 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); + + /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */ + public E(E prev, E pair, E next) { + this.p1 = prev.p2; + this.p2 = next.p1; + this.prev = prev; + this.next = next; + this.pair = pair; + sync(); } + public P midpoint() { return newP((p1.x+p2.x)/2, (p1.y+p2.y)/2, (p1.z+p2.z)/2); } + 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 class T { - public final E e1, e2, e3; - 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); + public final E e1; + public final int color; + + public void bind(T t2, int rot) { + // FIXME + } + + T(E 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"); - // FIXME: check that triangles we share an edge with agree on the direction of the normal vector + 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"); + 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; } + if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; } + if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; } + break; + } + + // FIXME unnecssary + ts.add(this); + + this.color = color; } - public V norm() { - P p1 = e1.shared(e2); - P p2 = e2.shared(e3); - P p3 = e3.shared(e1); - return p2.minus(p1).cross(p3.minus(p1)).norm(); + /* + 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 boolean hasE(E e) { return e1==e || e2==e || e3==e; } + */ + public P p1() { return e1.p1; } + public P p2() { return e1.p2; } + public P p3() { return e1.next.p2; } + public E e1() { return e1; } + public E e2() { return e1.next; } + public E e3() { return e1.prev; } + public V norm() { return p2().minus(p1()).cross(p3().minus(p1())).norm(); } + public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; } + public boolean has(P p) { return p1()==p || p2()==p || p3()==p; } 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; + 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).other(this); } - public T prevT(P p) { return nextE(p).other(this); } + /* + public T nextT(P p) { return prevE(p).pair.t; } + public T prevT(P p) { return nextE(p).pair.t; } - /** edge "after" this point, moving clockwise around the normal */ + 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 */ + // 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; @@ -256,13 +416,13 @@ public class Geom implements Iterable { else throw new Error("triangle " + this + " does not own point " + p); } - /** returns the angle at 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())); } - + */ } diff --git a/src/Main.java b/src/Main.java index da616df..e97f975 100644 --- a/src/Main.java +++ b/src/Main.java @@ -4,6 +4,8 @@ import javax.swing.*; import javax.media.opengl.*; import javax.media.opengl.glu.*; +// FEATURE: check google's 3D warehouse for sample shapes + public class Main implements GLEventListener { private Geom geom = new Geom(); @@ -16,6 +18,7 @@ public class Main implements GLEventListener { public Main(StlFile stlf) { + Geom.P ltf = geom.newP(-0.2, 0.1, 0.1); Geom.P mtf = geom.newP( 0.0, 0.1, 0.1); Geom.P rtf = geom.newP( 0.2, 0.1, 0.1); @@ -55,17 +58,6 @@ public class Main implements GLEventListener { geom.new V( 0, 0, -0.2), }; - for(Geom.V v : translations) { - for(Geom.P p1 : points) { - for(Geom.P p2 : points) { - if (p1.plus(v).minus(p2).mag() < Geom.EPSILON) { - System.out.println("bind " + p1 + " to " + p2); - p1.bind(p2); - } - } - } - } - // top geom.newT(ltf, mtf, mtn); geom.newT(mtn, ltn, ltf); @@ -98,8 +90,39 @@ public class Main implements GLEventListener { geom.newT(rtf, mtf, rbf); geom.newT(rbf, mtf, mbf); + for(Geom.V v : translations) { + for(Geom.T t1 : geom) { + for(Geom.T t2 : geom) { + if (t1==t2) continue; + + if ((t1.p1().plus(v).minus(t2.p1()).mag() < Geom.EPSILON) && + (t1.p2().plus(v).minus(t2.p3()).mag() < Geom.EPSILON) && + (t1.p3().plus(v).minus(t2.p2()).mag() < Geom.EPSILON)) + t1.bind(t2, 0); + if ((t1.p2().plus(v).minus(t2.p1()).mag() < Geom.EPSILON) && + (t1.p3().plus(v).minus(t2.p3()).mag() < Geom.EPSILON) && + (t1.p1().plus(v).minus(t2.p2()).mag() < Geom.EPSILON)) + t1.bind(t2, 1); + if ((t1.p3().plus(v).minus(t2.p1()).mag() < Geom.EPSILON) && + (t1.p1().plus(v).minus(t2.p3()).mag() < Geom.EPSILON) && + (t1.p2().plus(v).minus(t2.p2()).mag() < Geom.EPSILON)) + t1.bind(t2, 2); + } + } + } + + //Geom.P mid = geom.newE(ltf, lbn).shatter(); + + //tx.e2.shatter(); + //tx.e3.shatter(); + + //mid.move(geom.new V((float)-0.05,0,0)); + + //mtf.move(geom.new V(0, (float)-0.05, (float)0.05)); + mtf.move(geom.new V(0, (float)-0.05, (float)0.00)); /* + for(int i=0; i