src/edu/berkeley/qfat/Mesh.java

   1 package edu.berkeley.qfat;
   2 import java.awt.*;
   3 import java.util.*;
   4 import java.awt.event.*;
   5 import javax.swing.*;
   6 import javax.media.opengl.*;
   7 import javax.media.opengl.glu.*;
   8 import edu.berkeley.qfat.geom.*;
   9 import edu.wlu.cs.levy.CG.KDTree;
  10 import edu.berkeley.qfat.geom.Point;
  11 import com.infomatiq.jsi.IntProcedure;
  12
  13 public class Mesh implements Iterable<Mesh.T> {
  14
  15     public static final float EPSILON = (float)0.0001;
  16     public static final Random random = new Random();
  17
  18     private RTree<T>         triangles = new RTree<T>();
  19     private PointSet<Vertex> vertices  = new PointSet<Vertex>();
  20
  21     public boolean immutableVertices;
  22     public boolean ignorecollision    = false;
  23     public Mesh    score_against      = null;
  24     public double  score              = 0;
  25
  26     public Mesh(boolean immutableVertices) { this.immutableVertices = immutableVertices; }
  27
  28     public void makeVerticesImmutable() { this.immutableVertices = true; }
  29     public float score() { return (float)score; }
  30
  31     public int size() { return vertices.size(); }
  32     public Iterable<Vertex> vertices() { return vertices; }
  33     public Iterator<T> iterator() { return triangles.iterator(); }
  34
  35     public void rebindPoints() {
  36         // unbind all points
  37         for(Mesh.T t : this) {
  38             t.v1().unbind();
  39             t.v2().unbind();
  40             t.v3().unbind();
  41         }
  42         // ask edges to re-implement their bindings
  43         for(Mesh.T t : this) {
  44             t.e1().dobind();
  45             t.e2().dobind();
  46             t.e3().dobind();
  47         }
  48     }
  49
  50     public void transform(Matrix m) {
  51         ArrayList<Vertex> set = new ArrayList<Vertex>();
  52         for(Vertex v : vertices) set.add(v);
  53         for(Vertex v : set) v.transform(m);
  54     }
  55
  56     public void rebuild() { /*vertices.rebuild();*/ }
  57     public Vec diagonal() { return vertices.diagonal(); }
  58     public Point centroid() { return vertices.centroid(); }
  59     public Vertex nearest(Point p) { return vertices.nearest(p); }
  60
  61     /** compute the volume of the mesh */
  62     public float volume() {
  63         double total = 0;
  64         for(T t : this) {
  65             double area = t.area();
  66             Vec origin_to_centroid = new Vec(new Point(0, 0, 0), t.centroid());
  67             boolean facingAway = t.norm().dot(origin_to_centroid) > 0;
  68             double height = Math.abs(t.norm().dot(origin_to_centroid));
  69             total += ((facingAway ? 1 : -1) * area * height) / 3.0;
  70         }
  71         return (float)total;
  72     }
  73
  74
  75     // Vertexices //////////////////////////////////////////////////////////////////////////////
  76
  77     /** a vertex in the mesh */
  78     public final class Vertex extends HasQuadric implements Visitor {
  79         public String toString() { return p.toString(); }
  80         public Point p;
  81         E e;                // some edge *leaving* this point
  82
  83         Matrix binding = Matrix.ONE;
  84         Vertex bound_to = this;
  85
  86         public Point getPoint() { return p; }
  87         public float score() { return oldscore; }
  88
  89         private Vertex(Point p) {
  90             this.p = p;
  91             if (vertices.get(p) != null) throw new Error();
  92             vertices.add(this);
  93         }
  94
  95         private void glNormal(GL gl) {
  96             Vec norm = norm();
  97             gl.glNormal3f(norm.x, norm.y, norm.z);
  98         }
  99
 100         public void _recomputeFundamentalQuadric() {
 101             Matrix m = Matrix.ZERO;
 102             int count = 0;
 103             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
 104                 T t = e.t;
 105                 m = m.plus(t.norm().fundamentalQuadric(t.centroid()));
 106                 count++;
 107             }
 108             quadricStale = false;
 109             fundamentalQuadric = m.times(1/(float)count);
 110         }
 111
 112         public void reComputeErrorAround() {
 113             reComputeError();
 114             if (nearest_in_other_mesh != null) nearest_in_other_mesh.reComputeError();
 115             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next)
 116                 e.p2.reComputeError();
 117         }
 118         public void reComputeError() {
 119             unComputeError();
 120             computeError();
 121         }
 122         public void unComputeError() {
 123             score -= oldscore;
 124             oldscore = 0;
 125         }
 126         public HasQuadric nearest() {
 127             if (score_against==null) return null;
 128             return score_against.vertices.nearest(p, this);
 129         }
 130         public void computeError() {
 131             oldscore =
 132                 quadric_count != 0
 133                 ? (quadric.preAndPostMultiply(p) * 100) / quadric_count
 134                 : immutableVertices
 135                 ? oldscore
 136                 : nearest_in_other_mesh != null
 137                 ? nearest_in_other_mesh.fundamentalQuadric().preAndPostMultiply(p) * 100 * 10
 138                 : score_against != null
 139                 ? nearest().fundamentalQuadric().preAndPostMultiply(p) * 100 * 10
 140                 : 0;
 141             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
 142                 double ang = Math.abs(e.crossAngle());
 143                 if (ang > Math.PI) throw new Error();
 144                 float minangle = (float)(Math.PI * 0.8);
 145                 if (ang > minangle)
 146                     oldscore += (ang - minangle);
 147             }
 148             score += oldscore;
 149         }
 150
 151         private void removeTrianglesFromRTree() {
 152             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next)
 153                 if (e.t != null) e.t.removeFromRTree();
 154         }
 155         private void addTrianglesToRTree() {
 156             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next)
 157                 if (e.t != null) e.t.addToRTree();
 158         }
 159
 160         /** does NOT update bound pairs! */
 161         public boolean transform(Matrix m) {
 162             if (immutableVertices) throw new Error();
 163
 164             unApplyQuadricToNeighbor();
 165             Point oldp = this.p;
 166
 167             if (vertices.get(this.p)==null) throw new Error();
 168             vertices.remove(this);
 169             removeTrianglesFromRTree();
 170             float newx = m.a*p.x + m.b*p.y + m.c*p.z + m.d;
 171             float newy = m.e*p.x + m.f*p.y + m.g*p.z + m.h;
 172             float newz = m.i*p.x + m.j*p.y + m.k*p.z + m.l;
 173             this.p = new Point(newx, newy, newz);
 174             addTrianglesToRTree();
 175             vertices.add(this);
 176
 177             applyQuadricToNeighbor();
 178
 179             good = true;
 180
 181             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next) {
 182                 if (Math.abs(e.crossAngle()) > (Math.PI * 0.9) || Math.abs(e.next.crossAngle()) > (Math.PI * 0.9)) good = false;
 183                 if (e.t.aspect() < 0.1) good = false;
 184                 e.p2.quadricStale = true;
 185             }
 186
 187             if (!ignorecollision && good) triangles.range(oldp, this.p, (Visitor<T>)this);
 188
 189             reComputeErrorAround();
 190             return good;
 191         }
 192
 193         public boolean visit(Object o) {
 194             if (o instanceof T) {
 195                 T t = (T)o;
 196                 if (!good) return false;
 197                 for(E e = Vertex.this.e; e!=null; e=e.pair.next==Vertex.this.e?null:e.pair.next) {
 198                     if (!t.has(e.p1) && !t.has(e.p2) && e.intersects(t)) { good = false; }
 199                     if (e.t != null) {
 200                         if (!e.t.has(t.e1().p1) && !e.t.has(t.e1().p2) && t.e1().intersects(e.t)) { good = false; }
 201                         if (!e.t.has(t.e2().p1) && !e.t.has(t.e2().p2) && t.e2().intersects(e.t)) { good = false; }
 202                         if (!e.t.has(t.e3().p1) && !e.t.has(t.e3().p2) && t.e3().intersects(e.t)) { good = false; }
 203                     }
 204                 }
 205                 return good;
 206             } else {
 207                 Vertex v = (Vertex)o;
 208                 if (v.e==null || v.norm().dot(Vertex.this.norm()) < 0)
 209                     return false;
 210                 return true;
 211             }
 212         }
 213         private boolean good;
 214
 215         public boolean move(Vec v) {
 216             Matrix m = Matrix.translate(v);
 217             Vertex p = this;
 218             boolean good = true;
 219             do {
 220                 good &= p.transform(m);
 221                 p = p.bound_to;
 222             } while (p != this);
 223             return good;
 224         }
 225
 226         public E getFreeIncident() {
 227             E ret = getFreeIncident(e, e);
 228             if (ret != null) return ret;
 229             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next)
 230                 System.out.println(e + " " + e.t);
 231             throw new Error("unable to find free incident to " + this);
 232         }
 233
 234         public E getFreeIncident(E start, E before) {
 235             for(E e = start; e!=null; e=e.pair.next==before?null:e.pair.next)
 236                 if (e.pair.p2 == this && e.pair.t == null && e.pair.next.t == null)
 237                     return e.pair;
 238             return null;
 239         }
 240
 241         public E getE(Point p2) {
 242             Vertex v = vertices.get(p2);
 243             if (v==null) return null;
 244             return getE(v);
 245         }
 246         public E getE(Vertex p2) {
 247             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next)
 248                 if (e.p1 == this && e.p2 == p2) return e;
 249             return null;
 250         }
 251
 252         public Vec norm() {
 253             Vec norm = new Vec(0, 0, 0);
 254             for(E e = this.e; e!=null; e=e.pair.next==this.e?null:e.pair.next)
 255                 if (e.t != null)
 256                     norm = norm.plus(e.t.norm().times((float)e.prev.angle()));
 257             return norm.norm();
 258         }
 259
 260         public boolean isBoundTo(Vertex p) {
 261             for(Vertex px = p; px!=null; px=(px.bound_to==p?null:px.bound_to))
 262                 if (px==this)
 263                     return true;
 264             return false;
 265         }
 266
 267         public void unbind() { bound_to = this; binding = Matrix.ONE; }
 268         public void bind(Vertex p) { bind(p, Matrix.ONE); }
 269         public void bind(Vertex p, Matrix binding) {
 270             if (isBoundTo(p)) return;
 271             Vertex temp_bound_to = p.bound_to;
 272             Matrix temp_binding = p.binding;
 273             p.bound_to = this.bound_to;
 274             p.binding = binding.times(this.binding); // FIXME: may have order wrong here
 275             this.bound_to = temp_bound_to;
 276             this.binding = temp_binding.times(temp_binding); // FIXME: may have order wrong here
 277         }
 278     }
 279
 280     public class BindingGroup {
 281         private HashSet<E> set = new HashSet<E>();
 282         public BindingGroup bind_others;
 283         public BindingGroup other() { return bind_others; }
 284         public BindingGroup(BindingGroup bind_others) { this.bind_others = bind_others; }
 285         public BindingGroup() { this.bind_others = new BindingGroup(this); }
 286         public BindingGroup(E e) { this(); set.add(e); }
 287         public void add(E e) {
 288             if (set.contains(e)) return;
 289             set.add(e);
 290             BindingGroup e_bind_peers = e.bind_peers;
 291             BindingGroup e_bind_to    = e.bind_to;
 292             e.bind_peers = this;
 293             e.bind_to    = bind_others;
 294             for (E epeer  : e_bind_peers.set) add(epeer);
 295             for (E eother : e_bind_to.set)    bind_others.add(eother);
 296
 297             for(E eother : bind_others.set) {
 298                 if (e.next.bind_to.set.contains(eother.prev)) {
 299                     e.next.next.bindEdge(eother.prev.prev);
 300                 }
 301                 if (e.prev.bind_to.set.contains(eother.next)) {
 302                     e.prev.prev.bindEdge(eother.next.next);
 303                 }
 304             }
 305
 306         }
 307         public void dobind(E e) {
 308             for(E ebound : set) {
 309                 e.p1.bind(ebound.p2);
 310                 e.p2.bind(ebound.p1);
 311             }
 312         }
 313         public void shatter(BindingGroup bg1, BindingGroup bg2) {
 314             for(E e : set) {
 315                 e.shatter(e.midpoint(), bg1, bg2);
 316             }
 317         }
 318     }
 319
 320     /** [UNIQUE] an edge */
 321     public final class E implements Comparable<E> {
 322
 323         public final Vertex p1, p2;
 324         T t;     // triangle to our "left"
 325         E prev;  // previous half-edge
 326         E next;  // next half-edge
 327         E pair;  // partner half-edge
 328         public BindingGroup bind_peers  = new BindingGroup(this);
 329         public BindingGroup bind_to     = bind_peers.other();
 330         boolean shattered = false;
 331
 332         public boolean intersects(T t) { return t.intersects(p1.p, p2.p); }
 333         public float comparator() {
 334             Vertex nearest = score_against.nearest(midpoint());
 335             return (float)Math.max(length(), midpoint().distance(nearest.p));
 336         }
 337         public int compareTo(E e) {
 338             return e.comparator() > comparator() ? 1 : -1;
 339         }
 340         public void bindEdge(E e) { bind_to.add(e); }
 341         public void dobind() { bind_to.dobind(this); }
 342
 343         public Point shatter() { return shatter(midpoint(), null, null); }
 344         public Point shatter(Point mid, BindingGroup bg1, BindingGroup bg2) {
 345             if (shattered || destroyed) return mid;
 346             shattered = true;
 347
 348             Vertex r = next.p2;
 349             E next = this.next;
 350             E prev = this.prev;
 351
 352             int old_colorclass = t==null ? 0 : t.colorclass;
 353             if (bg1==null) bg1 = new BindingGroup();
 354             if (bg2==null) bg2 = new BindingGroup();
 355             BindingGroup old_bind_to = bind_to;
 356             bind_peers.shatter(bg1, bg2);
 357             old_bind_to.shatter(bg2.other(), bg1.other());
 358             pair.shatter();
 359             destroy();
 360
 361             newT(r.p, p1.p, mid, null, old_colorclass);
 362             newT(r.p, mid, p2.p, null, old_colorclass);
 363             bg1.add(p1.getE(mid));
 364             bg2.add(p2.getE(mid).pair);
 365             return mid;
 366         }
 367
 368         public boolean destroyed = false;
 369         public void destroy() {
 370             if (destroyed) return;
 371             destroyed = true;
 372             pair.destroyed = true;
 373
 374             if (t != null) t.destroy();
 375             t = null;
 376
 377             if (pair.t != null) pair.t.destroy();
 378             pair.t = null;
 379
 380             if (next.t != null) next.t.destroy();
 381             if (prev.t != null) prev.t.destroy();
 382             next.t = null;
 383             prev.t = null;
 384
 385             if (pair.next.t != null) pair.next.t.destroy();
 386             if (pair.prev.t != null) pair.next.t.destroy();
 387             pair.next.t = null;
 388             pair.prev.t = null;
 389
 390             this.bind_to = null;
 391             pair.bind_to = null;
 392             this.bind_peers = null;
 393             pair.bind_peers = null;
 394             pair.prev.next = next;
 395             next.prev = pair.prev;
 396             prev.next = pair.next;
 397             pair.next = prev;
 398             if (p1.e == this) p1.e = prev.next;
 399             if (pair.p1.e == pair) pair.p1.e = pair.prev.next;
 400         }
 401
 402         private void sync() {
 403             this.prev.next = this;
 404             this.next.prev = this;
 405             this.pair.pair = this;
 406             bind_peers.add(this);
 407             if (this.next.p1 != p2) throw new Error();
 408             if (this.prev.p2 != p1) throw new Error();
 409             if (this.p1.e == null) this.p1.e = this;
 410             if (!added) added = true;
 411         }
 412         private boolean added = false;
 413
 414         public T makeT(int colorclass) { return t==null ? (t = new T(this, colorclass)) : t; }
 415
 416         public double crossAngle() {
 417             Vec v1 = t.norm().times(-1);
 418             Vec v2 = pair.t.norm().times(-1);
 419             return Math.acos(v1.norm().dot(v2.norm()));
 420         }
 421
 422         /** angle between this half-edge and the next */
 423         public double angle() {
 424             Vec v1 = next.p2.p.minus(p2.p);
 425             Vec v2 = this.p1.p.minus(p2.p);
 426             return Math.acos(v1.norm().dot(v2.norm()));
 427         }
 428
 429         public void makeAdjacent(E e) {
 430             if (this.next == e) return;
 431             if (p2 != e.p1) throw new Error("cannot make adjacent -- no shared vertex");
 432             if (t != null || e.t != null) throw new Error("cannot make adjacent -- edges not both free");
 433
 434             E freeIncident = p2.getFreeIncident(e, this);
 435
 436             e.prev.next = freeIncident.next;
 437             freeIncident.next.prev = e.prev;
 438
 439             freeIncident.next = this.next;
 440             this.next.prev = freeIncident;
 441
 442             this.next = e;
 443             e.prev = this;
 444
 445             sync();
 446             freeIncident.sync();
 447         }
 448
 449         /** creates an isolated edge out in the middle of space */
 450         public E(Point p1, Point p2) {
 451             if (vertices.get(p1) != null) throw new Error();
 452             if (vertices.get(p2) != null) throw new Error();
 453             this.p1 = new Vertex(p1);
 454             this.p2 = new Vertex(p2);
 455             this.prev = this.next = this.pair = new E(this, this, this);
 456             this.p1.e = this;
 457             this.p2.e = this.pair;
 458             sync();
 459         }
 460
 461         /** adds a new half-edge from prev.p2 to p2 */
 462         public E(E prev, Point p) {
 463             Vertex p2;
 464             p2 = vertices.get(p);
 465             if (p2 == null) p2 = new Vertex(p);
 466             this.p1 = prev.p2;
 467             this.p2 = p2;
 468             this.prev = prev;
 469             if (p2.getE(p1) != null) throw new Error();
 470             if (p2.e==null) {
 471                 this.next = this.pair = new E(this, this, prev.next);
 472             } else {
 473                 E q = p2.getFreeIncident();
 474                 this.next = q.next;
 475                 this.next.prev = this;
 476                 E z = prev.next;
 477                 this.prev.next = this;
 478                 this.pair = new E(q, this, z);
 479             }
 480             if (p2.e==null) p2.e = this.pair;
 481             sync();
 482         }
 483
 484         /** adds a new half-edge to the mesh with a given predecessor, successor, and pair */
 485         public E(E prev, E pair, E next) {
 486             this.p1 = prev.p2;
 487             this.p2 = next.p1;
 488             this.prev = prev;
 489             this.next = next;
 490             this.pair = pair;
 491             sync();
 492         }
 493         public Point midpoint() { return new Point((p1.p.x+p2.p.x)/2, (p1.p.y+p2.p.y)/2, (p1.p.z+p2.p.z)/2); }
 494         public boolean has(Vertex v) { return v==p1 || v==p2; }
 495         public float length() { return p1.p.minus(p2.p).mag(); }
 496         public String toString() { return p1+"->"+p2; }
 497
 498     }
 499
 500     public E makeE(Point p1, Point p2) {
 501         Vertex v1 = vertices.get(p1);
 502         Vertex v2 = vertices.get(p2);
 503         if (v1 != null && v2 != null) {
 504             E e = v1.getE(v2);
 505             if (e != null) return e;
 506             e = v2.getE(v1);
 507             if (e != null) return e;
 508         }
 509         if (v1 != null) return new E(v1.getFreeIncident(), p2);
 510         if (v2 != null) return new E(v2.getFreeIncident(), p1).pair;
 511         return new E(p1, p2);
 512     }
 513     public T newT(Point p1, Point p2, Point p3, Vec norm, int colorclass) {
 514         if (norm != null) {
 515             Vec norm2 = p3.minus(p1).cross(p2.minus(p1));
 516             float dot = norm.dot(norm2);
 517             //if (Math.abs(dot) < EPointSILON) throw new Error("dot products within evertsilon of each other: "+norm+" "+norm2);
 518             if (dot < 0) { Point p = p1; p1=p2; p2 = p; }
 519         }
 520         E e12 = makeE(p1, p2);
 521         E e23 = makeE(p2, p3);
 522         E e31 = makeE(p3, p1);
 523         while(e12.next != e23 || e23.next != e31 || e31.next != e12) {
 524             e12.makeAdjacent(e23);
 525             e23.makeAdjacent(e31);
 526             e31.makeAdjacent(e12);
 527         }
 528         T ret = e12.makeT(colorclass);
 529         if (e12.t == null) throw new Error();
 530         if (e23.t == null) throw new Error();
 531         if (e31.t == null) throw new Error();
 532         return ret;
 533     }
 534
 535
 536     /** [UNIQUE] a triangle (face) */
 537     public final class T extends Triangle {
 538         public final E e1;
 539         public final int color;
 540         public final int colorclass;
 541
 542         public void removeFromRTree() { triangles.remove(this); }
 543         public void addToRTree() { triangles.insert(this); }
 544
 545         public void destroy() { triangles.remove(this); }
 546
 547         T(E e1, int colorclass) {
 548             this.e1 = e1;
 549             E e2 = e1.next;
 550             E e3 = e2.next;
 551             if (e1==e2 || e1==e3) throw new Error();
 552             if (e3.next!=e1) throw new Error();
 553             if (e1.t!=null || e2.t!=null || e3.t!=null) throw new Error("non-manifold surface or disagreeing normals");
 554             e1.t = this;
 555             e1.next.t = this;
 556             e1.next.next.t = this;
 557
 558             // FIXME: check for sealed/watertight surface once construction is complete (and infer normal(s)?)
 559
 560             int color = Math.abs(random.nextInt());
 561             while(true) {
 562                 color = color % 4;
 563                 if (e1().pair.t != null && color == e1().pair.t.color) { color++; continue; }
 564                 if (e2().pair.t != null && color == e2().pair.t.color) { color++; continue; }
 565                 if (e3().pair.t != null && color == e3().pair.t.color) { color++; continue; }
 566                 break;
 567             }
 568             this.color = color;
 569             this.colorclass = colorclass;
 570             triangles.add(this);
 571         }
 572         public E e1() { return e1; }
 573         public E e2() { return e1.next; }
 574         public E e3() { return e1.prev; }
 575         public Vertex v1() { return e1.p1; }
 576         public Vertex v2() { return e1.p2; }
 577         public Vertex v3() { return e1.next.p2; }
 578         public Point p1() { return e1.p1.p; }
 579         public Point p2() { return e1.p2.p; }
 580         public Point p3() { return e1.next.p2.p; }
 581         public boolean hasE(E e) { return e1==e || e1.next==e || e1.prev==e; }
 582         public boolean has(Vertex v) { return v1()==v || v2()==v || v3()==v; }
 583
 584         public boolean shouldBeDrawn() {
 585             if (e1().bind_to.set.size() == 0) return false;
 586             if (e2().bind_to.set.size() == 0) return false;
 587             if (e3().bind_to.set.size() == 0) return false;
 588             return true;
 589         }
 590
 591     }
 592 }