X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fqfat%2FMesh.java;h=13c00da4f86c943ed3cf14f0ef23fd4883114a52;hb=facb9d3f3606b4d410b758cd031d6235237b389a;hp=5b98a319f5e965a3a32a8bfb04c3eaa69ab07b8f;hpb=eb77bcb358e7aed2d35c70a682fe4b64be94abc1;p=anneal.git diff --git a/src/edu/berkeley/qfat/Mesh.java b/src/edu/berkeley/qfat/Mesh.java index 5b98a31..13c00da 100644 --- a/src/edu/berkeley/qfat/Mesh.java +++ b/src/edu/berkeley/qfat/Mesh.java @@ -11,22 +11,38 @@ 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 Iterable vertices() { return pointset; } + + 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() { - if (es.size() == 0) return new FaceIterator(); - return new FaceIterator(es.iterator().next().p1); + 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); } - public Mesh score_against = null; public double score = 0; public float score() { return (float)score; } @@ -60,60 +76,16 @@ public class Mesh implements Iterable { done.add(p); p.rescore(); } - for(T t : this) - for(Vert p : new Vert[] { t.v1(), t.v2(), t.v3() }) - p.kdremove(); - kd = new KDTree(3); - 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 float volume() { double total = 0; for(T t : this) { @@ -126,11 +98,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(); @@ -151,25 +118,19 @@ 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 Vec diagonal() { return pointset.diagonal(); } + public Point centroid() { return pointset.centroid(); } + public Vert nearest(Point p) { return pointset.nearest(p); } + + public Vert register(Point p) { Vert v = pointset.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); - } - public void kdremove() { - if (!inserted) return; - inserted = false; - try { kd.delete(new double[]{p.x,p.y,p.z}); } catch (Exception e) { } - } - 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); } + if (pointset.get(p) != null) throw new Error(); + pointset.add(this); } - public float score() { return oldscore; } public void unscore() { if (watch == null) return; @@ -199,7 +160,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; @@ -223,21 +184,21 @@ 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 (pointset.get(this.p)==null) throw new Error(); + 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); } 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; @@ -345,89 +306,15 @@ public class Mesh implements Iterable { /** [UNIQUE] an edge */ public final class E implements Comparable { - public boolean intersects(T t) { - double A0=t.v1().p.x, A1=t.v1().p.y, A2=t.v1().p.z; - double B0=t.v2().p.x, B1=t.v2().p.y, B2=t.v2().p.z; - double C0=t.v3().p.x, C1=t.v3().p.y, C2=t.v3().p.z; - double j0=p1.p.x, j1=p1.p.y, j2=p1.p.z; - double k0=p2.p.x, k1=p2.p.y, k2=p2.p.z; - double J0, J1, J2; - double K0, K1, K2; - double i0, i1, i2; - double a0, a1, a2; - double b0, b1, b2; - double c0, c1, c2; - double in_det; - double R00, R01, R02, R03, - R10, R11, R12, R13, - R20, R21, R22, R23, - R30, R31, R32, R33; - - - /* a = B - A */ - a0 = B0 - A0; - a1 = B1 - A1; - a2 = B2 - A2; - /* b = C - B */ - b0 = C0 - A0; - b1 = C1 - A1; - b2 = C2 - A2; - /* c = a × b */ - c0 = a1 * b2 - a2 * b1; - c1 = a2 * b0 - a0 * b2; - c2 = a0 * b1 - a1 * b0; - - /* M^(-1) = (1/det(M)) * adj(M) */ - in_det = 1 / (c0 * c0 + c1 * c1 + c2 * c2); - R00 = (b1 * c2 - b2 * c1) * in_det; - R01 = (b2 * c0 - b0 * c2) * in_det; - R02 = (b0 * c1 - b1 * c0) * in_det; - R10 = (c1 * a2 - c2 * a1) * in_det; - R11 = (c2 * a0 - c0 * a2) * in_det; - R12 = (c0 * a1 - c1 * a0) * in_det; - R20 = (c0) * in_det; - R21 = (c1) * in_det; - R22 = (c2) * in_det; - - /* O = M^(-1) * A */ - R03 = -(R00 * A0 + R01 * A1 + R02 * A2); - R13 = -(R10 * A0 + R11 * A1 + R12 * A2); - R23 = -(R20 * A0 + R21 * A1 + R22 * A2); - - /* fill in last row of 4x4 matrix */ - R30 = R31 = R32 = 0; - R33 = 1; - - J2 = R20 * j0 + R21 * j1 + R22 * j2 + R23; - K2 = R20 * k0 + R21 * k1 + R22 * k2 + R23; - if (J2 * K2 >= 0) return false; - - J0 = R00 * j0 + R01 * j1 + R02 * j2 + R03; - K0 = R00 * k0 + R01 * k1 + R02 * k2 + R03; - i0 = J0 + J2 * ((K0 - J0) / (J2 - K2)); - if (i0 < 0 || i0 > 1) return false; - - J1 = R10 * j0 + R11 * j1 + R12 * j2 + R13; - K1 = R10 * k0 + R11 * k1 + R12 * k2 + R13; - i1 = J1 + J2 * ((K1 - J1) / (J2 - K2)); - if (i1 < 0 || i1 > 1 || i0 + i1 > 1) return false; - - return true; - } - - public int compareTo(E e) { - return e.length() > length() ? 1 : -1; - } - public final Vert p1, p2; T t; // triangle to our "left" E prev; // previous half-edge E next; // next half-edge E pair; // partner half-edge - - public BindingGroup bg = new BindingGroup(this); + public int compareTo(E e) { return e.length() > length() ? 1 : -1; } + public void bind(E e) { bind(e, new Matrix()); } public void bind(E e, Matrix m) { e.bg.add(this); } @@ -470,8 +357,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; @@ -484,8 +369,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--; @@ -499,7 +382,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++; @@ -578,13 +460,84 @@ public class Mesh implements Iterable { public boolean has(Vert v) { return v==p1 || v==p2; } public float length() { return p1.p.minus(p2.p).mag(); } public String toString() { return p1+"->"+p2; } + + public boolean intersects(T t) { + double A0=t.v1().p.x, A1=t.v1().p.y, A2=t.v1().p.z; + double B0=t.v2().p.x, B1=t.v2().p.y, B2=t.v2().p.z; + double C0=t.v3().p.x, C1=t.v3().p.y, C2=t.v3().p.z; + double j0=p1.p.x, j1=p1.p.y, j2=p1.p.z; + double k0=p2.p.x, k1=p2.p.y, k2=p2.p.z; + double J0, J1, J2; + double K0, K1, K2; + double i0, i1, i2; + double a0, a1, a2; + double b0, b1, b2; + double c0, c1, c2; + double in_det; + double R00, R01, R02, R03, + R10, R11, R12, R13, + R20, R21, R22, R23, + R30, R31, R32, R33; + + + /* a = B - A */ + a0 = B0 - A0; + a1 = B1 - A1; + a2 = B2 - A2; + /* b = C - B */ + b0 = C0 - A0; + b1 = C1 - A1; + b2 = C2 - A2; + /* c = a × b */ + c0 = a1 * b2 - a2 * b1; + c1 = a2 * b0 - a0 * b2; + c2 = a0 * b1 - a1 * b0; + + /* M^(-1) = (1/det(M)) * adj(M) */ + in_det = 1 / (c0 * c0 + c1 * c1 + c2 * c2); + R00 = (b1 * c2 - b2 * c1) * in_det; + R01 = (b2 * c0 - b0 * c2) * in_det; + R02 = (b0 * c1 - b1 * c0) * in_det; + R10 = (c1 * a2 - c2 * a1) * in_det; + R11 = (c2 * a0 - c0 * a2) * in_det; + R12 = (c0 * a1 - c1 * a0) * in_det; + R20 = (c0) * in_det; + R21 = (c1) * in_det; + R22 = (c2) * in_det; + + /* O = M^(-1) * A */ + R03 = -(R00 * A0 + R01 * A1 + R02 * A2); + R13 = -(R10 * A0 + R11 * A1 + R12 * A2); + R23 = -(R20 * A0 + R21 * A1 + R22 * A2); + + /* fill in last row of 4x4 matrix */ + R30 = R31 = R32 = 0; + R33 = 1; + + J2 = R20 * j0 + R21 * j1 + R22 * j2 + R23; + K2 = R20 * k0 + R21 * k1 + R22 * k2 + R23; + if (J2 * K2 >= 0) return false; + + J0 = R00 * j0 + R01 * j1 + R02 * j2 + R03; + K0 = R00 * k0 + R01 * k1 + R02 * k2 + R03; + i0 = J0 + J2 * ((K0 - J0) / (J2 - K2)); + if (i0 < 0 || i0 > 1) return false; + + J1 = R10 * j0 + R11 * j1 + R12 * j2 + R13; + K1 = R10 * k0 + R11 * k1 + R12 * k2 + R13; + i1 = J1 + J2 * ((K1 - J1) / (J2 - K2)); + if (i1 < 0 || i1 > 1 || i0 + i1 > 1) return false; + + return true; + } } + public T newT(Point p1, Point p2, Point p3, Vec norm) { return newT(register(p1), register(p2), register(p3), norm); } public T newT(Vert p1, Vert p2, Vert p3, Vec norm) { 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); @@ -630,7 +583,6 @@ public class Mesh implements Iterable { public final int color; public void destroy() { - ts.remove(this); } T(E e1) { @@ -655,12 +607,6 @@ public class Mesh implements Iterable { break; } this.color = color; - - // FIXME unnecssary? - ts.add(this); - v1().kdinsert(); - v2().kdinsert(); - v3().kdinsert(); } public E e1() { return e1; } public E e2() { return e1.next; }