public class Mesh implements Iterable<Mesh.T> {
- private KDTree kd = new KDTree(3);
public static float EPSILON = (float)0.0001;
public static Random random = new Random();
- private HashMap<Point,Vert> ps = new HashMap<Point,Vert>();
- public HashSet<E> es = new HashSet<E>();
- public ArrayList<T> ts = new ArrayList<T>();
+ private PointSet<Vert> pointset = new PointSet<Vert>();
+ public Vert nearest(Point p) { return pointset.nearest(p); }
+ private HashMap<Point,Vert> verts = new HashMap<Point,Vert>();
+
+ public Iterable<E> edges() {
+ return
+ new Iterable<E>() {
+ public Iterator<E> iterator() {
+ // HACK
+ HashSet<E> hse = new HashSet<E>();
+ 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<T> iterator() { return ts.iterator(); }
+ public Iterator<T> iterator() {
+ for(Vert v : verts.values())
+ 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 void unbind() {
for(Mesh.T t : this) {
- t.p1().unbind();
- t.p2().unbind();
- t.p3().unbind();
+ t.v1().unbind();
+ t.v2().unbind();
+ t.v3().unbind();
}
}
int num = 0;
double dist = 0;
HashSet<Vert> done = new HashSet<Vert>();
- for(T t : ts)
- for(Vert p : new Vert[] { t.p1(), t.p2(), t.p3() }) {
+ 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(Vert p : new Vert[] { t.p1(), t.p2(), t.p3() })
+ 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)
- for(Vert p : new Vert[] { t.p1(), t.p2(), t.p3() })
+ 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<Vert> set = new ArrayList<Vert>();
- set.addAll(ps.values());
+ set.addAll(verts.values());
for(Vert v : set) v.transform(m);
}
float max_x = Float.MIN_VALUE;
float max_y = Float.MIN_VALUE;
float max_z = Float.MIN_VALUE;
- for(Point p : ps.keySet()) {
+ for(Point p : verts.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;
float max_x = Float.MIN_VALUE;
float max_y = Float.MIN_VALUE;
float max_z = Float.MIN_VALUE;
- for(Point p : ps.keySet()) {
+ for(Point p : verts.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;
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;
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 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 (dot < 0) { Vert p = p1; p1=p2; p2 = p; }
- }
- 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);
- }
- 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;
- }
public class BindingGroup {
public HashSet<E> es = new HashSet<E>();
}
}
- 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);
}
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; }
// 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);
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);
+ 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;
public final class E implements Comparable<E> {
public boolean intersects(T t) {
- double A0=t.p1().p.x, A1=t.p1().p.y, A2=t.p1().p.z;
- double B0=t.p2().p.x, B1=t.p2().p.y, B2=t.p2().p.z;
- double C0=t.p3().p.x, C1=t.p3().p.y, C2=t.p3().p.z;
+ 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;
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;
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--;
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++;
public String toString() { return p1+"->"+p2; }
}
+ 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 evertsilon of each other: "+norm+" "+norm2);
+ if (dot < 0) { Vert p = p1; p1=p2; p2 = p; }
+ }
+ 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);
+ }
+ 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;
+ }
+
+
+ public class FaceIterator implements Iterator<T> {
+ private HashSet<T> visited = new HashSet<T>();
+ private LinkedList<T> next = new LinkedList<T>();
+ 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 {
+ 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 = p1().p.distance(p);
- float d2 = p2().p.distance(p);
- float d3 = p3().p.distance(p);
- if (d1 < d2 && d1 < d3) return p1();
- if (d2 < d3) return p2();
- return p3();
}
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;
if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
break;
}
-
- // FIXME unnecssary
- ts.add(this);
- p1().kdinsert();
- p2().kdinsert();
- p3().kdinsert();
-
this.color = color;
+
+ v1().kdinsert();
+ v2().kdinsert();
+ v3().kdinsert();
}
- public Vert p1() { return e1.p1; }
- public Vert p2() { return e1.p2; }
- public Vert p3() { return e1.next.p2; }
public E e1() { return e1; }
public E e2() { return e1.next; }
public E e3() { return e1.prev; }
- public Vec norm() { return p2().p.minus(p1().p).cross(p3().p.minus(p1().p)).norm(); }
+ 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 boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
- public boolean has(Vert v) { return p1()==v || p2()==v || p3()==v; }
-
- public float area() {
- return (float)Math.abs(0.5 * e1().length() * new Vec(p1().p, p2().p).norm().dot(new Vec(p2().p, p3().p)));
- }
-
- public void glVertices(GL gl) {
- p1().p.glVertex(gl);
- p2().p.glVertex(gl);
- p3().p.glVertex(gl);
- }
-
- public Point centroid() { return new Point((p1().p.x+p2().p.x+p3().p.x)/3,
- (p1().p.y+p2().p.y+p3().p.y)/3,
- (p1().p.z+p2().p.z+p3().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;
- }
-
-
+ public boolean has(Vert v) { return v1()==v || v2()==v || v3()==v; }
}
-
}