X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fqfat%2FMesh.java;h=8592d8aafc0aa7a274145c5b43846bb94f062686;hb=a3a659d0128908676e5793c7e59884b565c367cf;hp=c830acf1f1020afb1e90629b2f077b8dd0a6b51e;hpb=400c3ff5e9f165c896811fc84d126552b2323849;p=anneal.git diff --git a/src/edu/berkeley/qfat/Mesh.java b/src/edu/berkeley/qfat/Mesh.java index c830acf..8592d8a 100644 --- a/src/edu/berkeley/qfat/Mesh.java +++ b/src/edu/berkeley/qfat/Mesh.java @@ -11,16 +11,37 @@ import edu.berkeley.qfat.geom.Point; public class Mesh implements Iterable { - private KDTree kd = new KDTree(3); - public static float EPSILON = (float)0.0001; public static Random random = new Random(); - private HashMap ps = new HashMap(); - public HashSet es = new HashSet(); - public ArrayList ts = new ArrayList(); + private PointSet pointset = new PointSet(); + public Vert nearest(Point p) { return pointset.nearest(p); } + private HashMap verts = new HashMap(); + + public Iterable edges() { + return + new Iterable() { + public Iterator iterator() { + // HACK + HashSet hse = new HashSet(); + for(T t : Mesh.this) { + hse.add(t.e1()); + hse.add(t.e2()); + hse.add(t.e3()); + hse.add(t.e1().pair); + hse.add(t.e2().pair); + hse.add(t.e3().pair); + } + return hse.iterator(); + } }; + } - public Iterator iterator() { return ts.iterator(); } + public Iterator iterator() { + for(Vert v : pointset) + if (v.e != null && v.e.t != null) + return new FaceIterator(v); + return new FaceIterator(); + } public Point origin() { return new Point(0, 0, 0); } @@ -51,69 +72,37 @@ public class Mesh implements Iterable { int num = 0; double dist = 0; HashSet done = new HashSet(); - for(T t : ts) + for(T t : this) for(Vert p : new Vert[] { t.v1(), t.v2(), t.v3() }) { if (done.contains(p)) continue; done.add(p); p.rescore(); } - for(T t : ts) + /* + for(T t : this) for(Vert p : new Vert[] { t.v1(), t.v2(), t.v3() }) p.kdremove(); - kd = new KDTree(3); - for(T t : ts) + pointset.clear(); + for(T t : this) for(Vert p : new Vert[] { t.v1(), t.v2(), t.v3() }) p.kdinsert(); + */ return (float)(dist/num); } public void transform(Matrix m) { ArrayList set = new ArrayList(); - set.addAll(ps.values()); + for (Vert v : pointset) + set.add(v); for(Vert v : set) v.transform(m); } - public Vec diagonal() { - float min_x = Float.MAX_VALUE; - float min_y = Float.MAX_VALUE; - float min_z = Float.MAX_VALUE; - float max_x = Float.MIN_VALUE; - float max_y = Float.MIN_VALUE; - float max_z = Float.MIN_VALUE; - for(Point p : ps.keySet()) { - if (p.x < min_x) min_x = p.x; - if (p.y < min_y) min_y = p.y; - if (p.z < min_z) min_z = p.z; - if (p.x > max_x) max_x = p.x; - if (p.y > max_y) max_y = p.y; - if (p.z > max_z) max_z = p.z; - } - return new Vec(max_x - min_x, max_y - min_y, max_z - min_z); - } - - public Point centroid() { - float min_x = Float.MAX_VALUE; - float min_y = Float.MAX_VALUE; - float min_z = Float.MAX_VALUE; - float max_x = Float.MIN_VALUE; - float max_y = Float.MIN_VALUE; - float max_z = Float.MIN_VALUE; - for(Point p : ps.keySet()) { - if (p.x < min_x) min_x = p.x; - if (p.y < min_y) min_y = p.y; - if (p.z < min_z) min_z = p.z; - if (p.x > max_x) max_x = p.x; - if (p.y > max_y) max_y = p.y; - if (p.z > max_z) max_z = p.z; - } - return new Point((float)(max_x + min_x)/2, - (float)(max_y + min_y)/2, - (float)(max_z + min_z)/2); - } + public Vec diagonal() { return pointset.diagonal(); } + public Point centroid() { return pointset.centroid(); } public float volume() { double total = 0; - for(T t : ts) { + for(T t : this) { double area = t.area(); Vec origin_to_centroid = new Vec(new Point(0, 0, 0), t.centroid()); boolean facingAway = t.norm().dot(origin_to_centroid) > 0; @@ -123,11 +112,6 @@ public class Mesh implements Iterable { return (float)total; } - public Vert nearest(Point p) { - Object[] results; - try { results = kd.nearest(new double[]{p.x,p.y,p.z},1); } catch (Exception e) { throw new Error(e); } - return (Vert)results[0]; - } public class BindingGroup { public HashSet es = new HashSet(); @@ -148,23 +132,29 @@ public class Mesh implements Iterable { } } - public Vert register(Point p) { Vert v = ps.get(p); return v==null ? new Vert(p) : v; } - public final class Vert { + public Vert register(Point p) { Vert v = verts.get(p); return v==null ? new Vert(p) : v; } + public final class Vert extends HasPoint { public Point p; + public Point getPoint() { return p; } private Vert(Point p) { this.p = p; - if (ps.get(p) != null) throw new Error(); - ps.put(this.p, this); + if (verts.get(p) != null) throw new Error(); + verts.put(this.p, this); + pointset.add(this); + } + public void reinsert() { + pointset.remove(this); + pointset.add(this); } public void kdremove() { if (!inserted) return; inserted = false; - try { kd.delete(new double[]{p.x,p.y,p.z}); } catch (Exception e) { } + pointset.remove(this); } public void kdinsert() { if (inserted) return; inserted = true; - try { kd.insert(new double[]{p.x,p.y,p.z},this); } catch (Exception e) { throw new Error(e); } + pointset.add(this); } public float score() { return oldscore; } @@ -196,7 +186,7 @@ public class Mesh implements Iterable { watch = score_against.nearest(po.p); // don't attract to vertices that face the other way - if (watch.norm().dot(norm()) < 0) { + if (watch.e == null || watch.norm().dot(norm()) < 0) { watch = null; } else { watch.watch_x += po.p.x; @@ -220,21 +210,23 @@ public class Mesh implements Iterable { // FIXME: screws up hashmap unscore(); try { - if (ps.get(this.p)==null) throw new Error(); - ps.remove(this.p); + if (verts.get(this.p)==null) throw new Error(); + verts.remove(this.p); + pointset.remove(this); float newx = m.a*p.x + m.b*p.y + m.c*p.z + m.d; float newy = m.e*p.x + m.f*p.y + m.g*p.z + m.h; float newz = m.i*p.x + m.j*p.y + m.k*p.z + m.l; this.p = new Point(newx, newy, newz); // FIXME: what if we move onto exactly where another point is? - ps.put(this.p,(Vert)this); + pointset.add(this); + verts.put(this.p,(Vert)this); } catch (Exception e) { throw new RuntimeException(e); } rescore(); boolean good = true; /* - for(T t : ts) { + for(T t : this) { for(E e = this.e; ;) { if (e.intersects(t)) { good = false; break; } e = e.pair.next; @@ -467,8 +459,6 @@ public class Mesh implements Iterable { pair.destroyed = true; if (next.t != null) next.t.destroy(); if (prev.t != null) prev.t.destroy(); - if (pair.next.t != null) ts.remove(pair.next.t); - if (pair.prev.t != null) ts.remove(pair.prev.t); next.t = null; prev.t = null; pair.next.t = null; @@ -481,8 +471,6 @@ public class Mesh implements Iterable { pair.next = prev; if (p1.e == this) p1.e = prev.next; if (pair.p1.e == pair) pair.p1.e = pair.prev.next; - es.remove(this); - es.remove(pair); avgedge -= this.length(); avgedge -= pair.length(); numedges--; @@ -496,7 +484,6 @@ public class Mesh implements Iterable { if (this.next.p1 != p2) throw new Error(); if (this.prev.p2 != p1) throw new Error(); if (this.p1.e == null) this.p1.e = this; - es.add(this); if (!added) { added = true; numedges++; @@ -581,7 +568,7 @@ public class Mesh implements Iterable { if (norm != null) { Vec norm2 = p3.p.minus(p1.p).cross(p2.p.minus(p1.p)); float dot = norm.dot(norm2); - //if (Math.abs(dot) < EPointSILON) throw new Error("dot products within epsilon of each other: "+norm+" "+norm2); + //if (Math.abs(dot) < EPointSILON) throw new Error("dot products within evertsilon of each other: "+norm+" "+norm2); if (dot < 0) { Vert p = p1; p1=p2; p2 = p; } } E e12 = p1.makeE(p2); @@ -599,32 +586,43 @@ public class Mesh implements Iterable { return ret; } + + public class FaceIterator implements Iterator { + private HashSet visited = new HashSet(); + private LinkedList next = new LinkedList(); + public FaceIterator() { } + public FaceIterator(Vert v) { next.addFirst(v.e.t); } + public boolean hasNext() { return next.peek()!=null; } + public void remove() { throw new Error(); } + public T next() { + T ret = next.removeFirst(); + if (ret == null) return null; + visited.add(ret); + T t1 = ret.e1().pair.t; + T t2 = ret.e2().pair.t; + T t3 = ret.e3().pair.t; + if (t1 != null && !visited.contains(t1)) next.addFirst(t1); + if (t2 != null && !visited.contains(t2)) next.addFirst(t2); + if (t3 != null && !visited.contains(t3)) next.addFirst(t3); + return ret; + } + } + /** [UNIQUE] a triangle (face) */ public final class T extends Triangle { public final E e1; public final int color; public void destroy() { - ts.remove(this); - } - - public Vert nearest(Point p) { - float d1 = v1().p.distance(p); - float d2 = v2().p.distance(p); - float d3 = v3().p.distance(p); - if (d1 < d2 && d1 < d3) return v1(); - if (d2 < d3) return v2(); - return v3(); } T(E e1) { this.e1 = e1; E e2 = e1.next; E e3 = e2.next; - if (e1==e2 || e1==e3) throw new Error(); + 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 or disagreeing normals"); + 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; @@ -639,45 +637,23 @@ public class Mesh implements Iterable { if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; } break; } + this.color = color; - // FIXME unnecssary - ts.add(this); v1().kdinsert(); v2().kdinsert(); v3().kdinsert(); - - this.color = color; } + public E e1() { return e1; } + public E e2() { return e1.next; } + public E e3() { return e1.prev; } public Vert v1() { return e1.p1; } public Vert v2() { return e1.p2; } public Vert v3() { return e1.next.p2; } public Point p1() { return e1.p1.p; } public Point p2() { return e1.p2.p; } public Point p3() { return e1.next.p2.p; } - public E e1() { return e1; } - public E e2() { return e1.next; } - public E e3() { return e1.prev; } - public Vec norm() { return v2().p.minus(v1().p).cross(v3().p.minus(v1().p)).norm(); } public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; } public boolean has(Vert v) { return v1()==v || v2()==v || v3()==v; } - public float area() { return (float)Math.abs(0.5*e1().length()*new Vec(v1().p, v2().p).norm().dot(new Vec(v2().p, v3().p))); } - public void glVertices(GL gl) { - v1().p.glVertex(gl); - v2().p.glVertex(gl); - v3().p.glVertex(gl); - } - - public Point centroid() { - return new Point((v1().p.x+v2().p.x+v3().p.x)/3, - (v1().p.y+v2().p.y+v3().p.y)/3, - (v1().p.z+v2().p.z+v3().p.z)/3); } - public float diameter() { - // FIXME: what is this supposed to be? - return Math.max(Math.max(e1().length(), e2().length()), e3().length()) / 2; - } - - } - }