- }
- public boolean makeNonDegenerate(Vector vec, Vertex v1) {
- for(int i2 = 0; i2<next(v1).size(); i2++) {
- Vertex v2 = ((Integer)next(v1).get(i2)).intValue();
- for(int i3 = 0; i3<numvertices; i3++) {
- Vertex v3 = i3;
- for(int i4=0; i4<next(v3).size(); i4++) {
- Vertex v4 = ((Integer)next(v3).get(i4)).intValue();
- if (v1==v3||v1==v4||v2==v3||v2==v4) continue;
- if (isect(v1,v2,v3,v4)) {
- float a1 = y(v2)-y(v1);
- float a2 = y(v4)-y(v3);
- float b1 = x(v1)-x(v2);
- float b2 = x(v3)-x(v4);
- float c1 = -1 * (a1*x(v1)+b1*y(v1));
- float c2 = -1 * (a2*x(v3)+b2*y(v3));
- // a1x+b1y+c1=0
- // y=-(a1x+c1)/b1
- // a2x-(a1x+c1)(b2/b1)+c2=0
- // a2b1x-b2(a1x+c1)+b1c2=0
- // a2b1x-a1b2x-b2c1+b1c2=0
- // x(a2b1-a1b2)-b2c1+b1c2=0
- // x(a2b1-a1b2)=b2c1-b1c2
- // x=(b2c1-b1c2)/(a2b1-a1b2)
- float xq = (b2*c1-c2*b1)/(b1*a2-b2*a1);
- Vertex v0 = newVertex(xq, -1 * (a1*xq+c1) / b1);
- //if (v0==v1||v0==v2||v0==v3||v0==v4) continue;
- if (debug) Log.debug(this,"inserting new vertex " + v0+" between " + v1+"-"+v2 +" and "+ v3+"-"+v4);
- next(v1).remove(new Integer(v2));
- next(v1).add(new Integer(v0));
- next(v0).add(new Integer(v2));
- next(v3).remove(new Integer(v4));
- next(v3).add(new Integer(v0));
- next(v0).add(new Integer(v4));
- return true;
+ public void bisect(Vertex v) {
+ Edge e = this;
+ Triangle t1 = this.t1==null?this.t2:this.t1;
+ Triangle t = t1==this.t1?this.t2:this.t1;
+ Vertex opposing = t1.opposingVertex(e);
+ Triangle top = null, ton = null;
+ Vertex left = e.v(1);
+ Vertex right = e.v(2);
+ Vertex tov = null;
+ boolean in1 = t1.in;
+ boolean in2 = false;
+ Triangle opposingTriangleLeft = t1.opposingTriangle(left);
+ Triangle opposingTriangleRight = t1.opposingTriangle(right);
+ Edge right_v = newEdge(right, v);
+ Edge left_v = newEdge(left, v);
+ Edge opposing_v = newEdge(opposing, v);
+ Edge tov_v = null;
+ Edge right_tov = null;
+ Edge left_tov = null;
+ Edge right_opposing = t1.opposingEdge(left);
+ Edge left_opposing = t1.opposingEdge(right);
+ if (t != null) {
+ t.check();
+ right_tov = t.opposingEdge(left);
+ left_tov = t.opposingEdge(right);
+ top = t.opposingTriangle(left);
+ ton = t.opposingTriangle(right);
+ tov = t.opposingVertex(t1);
+ in2 = t.in;
+ tov_v = newEdge(tov, v);
+ if (top == t1) top = null;
+ if (ton == t1) ton = null;
+ if (opposingTriangleLeft == t) opposingTriangleLeft = null;
+ if (opposingTriangleRight == t) opposingTriangleRight = null;
+ t.delete();
+ }
+ t1.delete();
+ Triangle ta, tb, tc, td;
+ ta = triangle(right_opposing, opposing_v, right_v);
+ tb = triangle(left_opposing, opposing_v, left_v);
+ ta.in = in1;
+ tb.in = in1;
+ if (t != null) {
+ tc = triangle(left_tov, tov_v, left_v);
+ td = triangle(right_tov, tov_v, right_v);
+ tc.in = in2;
+ td.in = in2;
+ }
+ if (locked()) fracture(v);
+ else ta.fixup();
+ }
+ public Edge flip() {
+ if (locked()) throw new Error("attempted to remove a locked edge: " + this);
+ boolean in = t1.in && t2.in;
+
+ Edge e3 = rotate(v1, true);
+ Vertex vb = e3.unCommonVertex(this);
+ Edge e6 = e3.rotate(vb, true);
+
+ Edge e4 = rotate(v2, true);
+ Vertex va = e4.unCommonVertex(this);
+ Edge e1 = e4.rotate(va, true);
+
+ Edge e = newEdge(va, vb);
+
+ t1.delete();
+ t2.delete();
+ Triangle ta, tb;
+ ta = triangle(e1, e, e3);
+ tb = triangle(e4, e, e6);
+ ta.in = in;
+ tb.in = in;
+ return ta.getSharedEdge(tb);
+ }
+ public void fracture(Vertex vx) {
+ if (!locked()) throw new Error("attempt to fracture an edge which does not exist: " + v1 + " " + v2);
+ // delete-me
+ Edge v1vx = newEdge(v1, vx);
+ Edge vxv2 = newEdge(vx, v2);
+ v1vx.locks += locks;
+ vxv2.locks += locks;
+ locks = 0;
+ v1vx.weight += v(1)==v1vx.v(1) ? weight : (-1 * weight);
+ vxv2.weight += v(2)==vxv2.v(2) ? weight : (-1 * weight);
+ weight = 0;
+ v1vx.lock();
+ vxv2.lock();
+ }
+ public void fracture(Edge e) {
+ triangle0=e.t1==null?e.t2:e.t1;
+ Vertex v0 = vertex(Mesh.this.intersect(v1,v2,e.v(1),e.v(2)));
+ if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0);
+ if (v0 != v1 && v0 != v2) fracture(v0);
+ }
+ public void lock(Vertex v1, int delta) {
+ weight += this.v(1)==v1 ? delta : (-1 * delta);
+ locks += 1;
+ lock();
+ }
+ public void lock() {
+ Triangle t = t1==null ? t2 : t1;
+ if (t==null) t = triangle0.seek(v1);
+ if (!t.hasVertex(v1)) throw new Error("this sucks balls");
+ boolean skipfo = false;
+ for(Triangle told = null; t != told; t = told==null ? t : t.followVector(v1,v2)) {
+ told = t;
+ if (!t.encounters(v1,v2)) break;
+ if (!t.encounters(v2,v1)) break;
+ Triangle tlast = t.followVector(v2,v1);
+ if (tlast == null) throw new Error("seek from: " + tlast + "\n " + v1 + " -> " + v2);
+ if (tlast == t) { if (t.hasVertex(v1)) continue; throw new Error("no predecessor"); }
+ Edge e = t.getSharedEdge(tlast);
+ if (!e.convex()) continue;
+ if (e.v(1)==v1 || e.v(1)==v2 || e.v(2)==v1 || e.v(2)==v2) { continue; }
+ if (this.intersects(e.v(1))) { fracture(e.v(1)); return; }
+ if (this.intersects(e.v(2))) { fracture(e.v(2)); return; }
+ if (!this.intersects(e)) continue;
+ if (e.locked()) {
+ fracture(e);
+ return;
+ } else {
+ Edge eold = e = e.flip();
+ t = e.t1;
+ if (t==null || !t.intersects(this)) t = e.t2;
+ told = t;
+ if (eold.intersects(this)) {
+ t = t.followVector(v1,v2);
+ if (t != e.t1 && t != e.t2) t = told;
+ continue;
+ } else {
+ told = null;
+ while(t.intersects(this)) {
+ if (t==told) break;
+ told = t;
+ t = t.followVector(v2,v1);
+ }
+ t = told;
+ told = null;
+ continue;