X-Git-Url: http://git.megacz.com/?p=anneal.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fqfat%2FMesh.java;h=219da71afdc52c46e0889412574c0832d15f8dd5;hp=157955153cdc1b2c28650008a7052f8bb348d28f;hb=3a566fdd09e751b7901edc4d22060032f96fe438;hpb=3b84875407de81c3ca4481b1a7f323df6204de5d diff --git a/src/edu/berkeley/qfat/Mesh.java b/src/edu/berkeley/qfat/Mesh.java index 1579551..219da71 100644 --- a/src/edu/berkeley/qfat/Mesh.java +++ b/src/edu/berkeley/qfat/Mesh.java @@ -15,7 +15,8 @@ public class Mesh implements Iterable { public static Random random = new Random(); private PointSet pointset = new PointSet(); - public Vert nearest(Point p) { return pointset.nearest(p); } + + public Iterable vertices() { return pointset; } public Iterable edges() { return @@ -42,8 +43,6 @@ public class Mesh implements Iterable { 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; } @@ -77,15 +76,6 @@ 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(); - pointset.clear(); - for(T t : this) - for(Vert p : new Vert[] { t.v1(), t.v2(), t.v3() }) - p.kdinsert(); - */ return (float)(dist/num); } @@ -96,9 +86,6 @@ public class Mesh implements Iterable { for(Vert v : set) v.transform(m); } - public Vec diagonal() { return pointset.diagonal(); } - public Point centroid() { return pointset.centroid(); } - public float volume() { double total = 0; for(T t : this) { @@ -131,7 +118,10 @@ public class Mesh implements Iterable { } } - public Vert register(Point p) { Vert v = pointset.get(p); return v==null ? new Vert(p) : v; } + public Vec diagonal() { return pointset.diagonal(); } + public Point centroid() { return pointset.centroid(); } + public Vert nearest(Point p) { return pointset.nearest(p); } + public final class Vert extends HasPoint { public Point p; public Point getPoint() { return p; } @@ -140,21 +130,6 @@ public class Mesh implements Iterable { if (pointset.get(p) != null) throw new Error(); pointset.add(this); } - public void reinsert() { - pointset.remove(this); - pointset.add(this); - } - public void kdremove() { - if (!inserted) return; - inserted = false; - pointset.remove(this); - } - public void kdinsert() { - if (inserted) return; - inserted = true; - pointset.add(this); - } - public float score() { return oldscore; } public void unscore() { if (watch == null) return; @@ -170,8 +145,8 @@ public class Mesh implements Iterable { watch = null; } public Vert partner() { return watch==null ? this : watch; } - public Vert watchback() { return watch_count==0 ? partner() : - register(new Point(watch_x/watch_count, watch_y/watch_count, watch_z/watch_count)); } + public Point watchback() { return watch_count==0 ? partner().p : + new Point(watch_x/watch_count, watch_y/watch_count, watch_z/watch_count); } public void rescore() { if (score_against == null) return; @@ -249,15 +224,6 @@ public class Mesh implements Iterable { return good; } - public E makeE(Vert 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; - return new E(getFreeIncident(), p2); - } - public E getFreeIncident() { E ret = getFreeIncident(e, e); if (ret != null) return ret; @@ -330,89 +296,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); } @@ -441,8 +333,8 @@ public class Mesh implements Iterable { pair.shatter(); destroy(); - newT(r, p1, mid, null); - newT(r, mid, p2, null); + newT(r.p, p1.p, mid.p, null); + newT(r.p, mid.p, p2.p, null); bg1.add(p1.getE(mid)); bg2.add(mid.getE(p2)); return mid; @@ -558,18 +450,105 @@ 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(Vert p1, Vert p2, Vert p3, Vec norm) { + private Vert register(Point p) { + Vert v = pointset.get(p); + return v==null ? new Vert(p) : v; + } + public E makeE(Point p1, Point p2) { + Vert v1 = pointset.get(p1); + Vert v2 = pointset.get(p2); + if (v1 != null && v2 != null) { + E e = v1.getE(v2); + if (e != null) return e; + e = v2.getE(v1); + if (e != null) return e; + } + if (v1 != null) return new E(v1.getFreeIncident(), register(p2)); + if (v2 != null) return new E(v2.getFreeIncident(), register(p1)).pair; + return new E(register(p1), register(p2)); + } + public T newT(Point p1, Point p2, Point p3, Vec norm) { if (norm != null) { - Vec norm2 = p3.p.minus(p1.p).cross(p2.p.minus(p1.p)); + Vec norm2 = p3.minus(p1).cross(p2.minus(p1)); float dot = norm.dot(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; } + if (dot < 0) { Point p = p1; p1=p2; p2 = p; } } - E e12 = p1.makeE(p2); - E e23 = p2.makeE(p3); - E e31 = p3.makeE(p1); + E e12 = makeE(p1, p2); + E e23 = makeE(p2, p3); + E e31 = makeE(p3, p1); while(e12.next != e23 || e23.next != e31 || e31.next != e12) { e12.makeAdjacent(e23); e23.makeAdjacent(e31); @@ -634,10 +613,6 @@ public class Mesh implements Iterable { break; } this.color = color; - - v1().kdinsert(); - v2().kdinsert(); - v3().kdinsert(); } public E e1() { return e1; } public E e2() { return e1.next; }