1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
2 // Licensed under the GNU General Public License version 2 ("the License").
3 // You may not use this file except in compliance with the License.
5 package org.ibex.graphics;
7 import java.util.collections.*;
8 import org.ibex.util.*;
11 // - allow edge-constraint removal
13 // ~30% of our time spent finding vertices => use a balanced quadtree
15 // - store "which curve is inside me" pointer in Triangle
16 // - split if two curves enter
17 // - go to treating Vertex as a value class (epsilon==0)
20 // - [??] preserve in/out-ness every time we delete() a triangle
23 * An incremental, adaptive, addWeighted Delaunay Triangulation.
24 * @see Kallmann, Bieri, and Thalmann: Fully Dynamic AddWeighted Delaunay Triangulations
26 public final class Mesh {
28 private static final float epsilon = (float)0.0001;
29 private static final float epsilon2 = (float)0.001;
30 private static final boolean debug = false;
32 private Vector triangles = new Vector(); /* we no longer need this */
33 private Hash edges = new Hash(); /* we no longer need this either */
34 private int numvertices = 0;
35 private Triangle triangle0 = null;
36 private Vertex vertex0 = null;
37 private Vertex vertex1 = null;
38 private Vertex start = null;
39 private Vertex last = null;
43 m.vertex(triangle0.v(1));
44 m.vertex(triangle0.v(2));
45 m.vertex(triangle0.v(3));
46 Object[] edges = this.edges.vals();
47 for(int i=0; i<edges.length; i++) {
48 Edge e = (Edge)edges[i];
49 Vertex mv1 = m.vertex(e.v(1));
50 Vertex mv2 = m.vertex(e.v(2));
51 Edge me = m.getEdge(mv1, mv2);
67 // Chain //////////////////////////////////////////////////////////////////////////////
69 public static interface Chain {
70 public Mesh.Chain getMeshChainParent();
71 public Affine getAffine();
72 public Mesh getMesh();
75 // Constructor //////////////////////////////////////////////////////////////////////////////
78 public Mesh(Path p, boolean evenOdd) { p.addTo(this, evenOdd); }
80 public void subtract(Mesh m, Affine a) { clipOp(m,a,true); }
81 public void intersect(Mesh m, Affine a) { clipOp(m,a,false); }
82 public void add(Mesh m, Affine a) { iterateTriangles(ITERATE_ADD, m, a); }
83 public static long seekTime = 0;
85 public static final int ITERATE_SUBTRACT = 1;
86 public static final int ITERATE_INTERSECT = 2;
87 public static final int ITERATE_ADD = 3;
88 public static final int ITERATE_CLEAR_WASSET = 4;
89 public static final int ITERATE_CLEAR = 5;
90 public static final int ITERATE_STROKE = 6;
92 Triangle[] iter = new Triangle[100];
94 private void iterateTriangles(int mode, Mesh m, Affine a) { iterateTriangles(mode, m, a, null, 0); }
95 private void iterateTriangles(int mode, Mesh m, Affine a, PixelBuffer buf, int color) {
98 if (iter.length < triangles.size()) iter = new Triangle[triangles.size()];
99 iter[numiter++] = triangle0;
101 Triangle t = iter[--numiter];
102 if (t.tick >= this.tick) continue;
104 case ITERATE_STROKE: t.stroke(buf, a, color); break;
105 case ITERATE_CLEAR: t.clear(); break;
106 case ITERATE_CLEAR_WASSET: t.inWasSet = false; break;
107 case ITERATE_INTERSECT:
108 case ITERATE_SUBTRACT: {
110 boolean oin = m.queryPoint(t.c().multiply(a));
111 t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin);
115 for(int i=1; i<=3; i++) {
117 if (e.t1 != null && e.t1.tick >= this.tick) continue;
118 if (e.t2 != null && e.t2.tick >= this.tick) continue;
119 if (!e.locked()) continue;
120 if ((e.t1==null || !e.t1.in) && (e.t2==null || !e.t2.in)) continue;
121 Point p1 = e.v(1).multiply(a);
122 Point p2 = e.v(2).multiply(a);
123 Vertex v1=null, v2=null;
126 if (v1==v2) continue;
127 m.getEdge(v1, v2).lock(v1, 0);
133 for(int i=1; i<=3; i++) {
134 Triangle ti = t.t(i);
135 if (ti == null) continue;
136 if (ti.tick >= this.tick) continue;
137 iter[numiter++] = ti;
142 public void clipOp(Mesh m, Affine a, boolean subtract) {
144 long start = System.currentTimeMillis();
146 iterateTriangles(subtract ? ITERATE_SUBTRACT : ITERATE_INTERSECT, m, a.inverse());
147 float total = (float)((System.currentTimeMillis() - start));
148 float seek = (float)seekTime;
149 if (total > 80) System.out.println("clip in " + (100 * (seek/total)) + "%");
152 // Geometry //////////////////////////////////////////////////////////////////////////////
154 public static double ddistance(double x1, double y1, double x2, double y2) {
155 return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
156 public static float area(Point p1, Point p2, Point p3) {
163 double a = ddistance(x1,y1,x2,y2);
164 double b = ddistance(x2,y2,x3,y3);
165 double c = ddistance(x3,y3,x1,y1);
166 double s = (a+b+c)/2;
167 double t = s*(s-a)*(s-b)*(s-c);
169 return (float)Math.sqrt(t);
172 public Point intersect(Point v1, Point v2, Point v3, Point v4) {
173 double a1 = v2.y-v1.y;
174 double a2 = v4.y-v3.y;
175 double b1 = v1.x-v2.x;
176 double b2 = v3.x-v4.x;
177 double c1 = -1 * (a1*v1.x+b1*v1.y);
178 double c2 = -1 * (a2*v3.x+b2*v3.y);
179 double x = (b2*c1-c2*b1)/(b1*a2-b2*a1);
180 double y = (a2*c1-c2*a1)/(a1*b2-a2*b1);
181 if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n ");
182 return point((float)x,(float)y);
185 public static int side(Point p1, Point p2, Point p3) {
192 // this MUST be done to double precision
193 double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2);
194 if (c > 0) return b>=0 ? -1 : 1;
195 if (c < 0) return b>=0 ? 1 : -1;
199 // Vertex //////////////////////////////////////////////////////////////////////////////
201 public Vertex vertex(Point p, Affine a) { return vertex(p.multiply(a)); }
202 public Vertex vertex(Point p) {
204 switch(numvertices) {
205 case 0: return (vertex0 = new Vertex(p));
206 case 1: return vertex0.distance(p)<=epsilon ? vertex0 : (vertex1 = new Vertex(p));
208 if (vertex0.distance(p)<=epsilon) return vertex0;
209 if (vertex1.distance(p)<=epsilon) return vertex1;
210 Vertex v2 = new Vertex(p);
211 triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0));
216 t = triangle0.seek(p);
217 for(int i=1; i<=3; i++)
218 for(int j=1; j<=2; j++)
219 if (t != null && t.e(i).v(j).distance(p)<=epsilon) return t.e(i).v(j);
220 Vertex v = new Vertex(p);
221 if (t.e(3).intersects(p)) t.e(3).bisect(v);
222 else if (t.e(1).intersects(p)) t.e(1).bisect(v);
223 else if (t.e(2).intersects(p)) t.e(2).bisect(v);
224 else if (t.contains(v)) t.trisect(v);
231 private Point point(float x, float y) { return new Point(x,y); }
232 private Point point(Point a, Point b) { return new Point((a.x+b.x)/2,(a.y+b.y)/2); }
233 private Point point(Point p, Affine a) { return point(p.x(a), p.y(a)); }
234 private class Point {
237 public String toString() { return "("+x+","+y+")"; }
238 public Point multiply(Affine a) { return point(x(a),y(a)); }
239 public Point(float x, float y) { this.x = x; this.y = y; }
240 public Point(Point p) { this(p.x,p.y); }
241 public boolean equals(float x, float y) { return distance(x,y) <= epsilon; }
242 public boolean equals(Object o) { return (!(o instanceof Point)) ? false : ((Point)o).distance(this) <= epsilon; }
243 public float distance(Point v) { return distance(v.x,v.y); }
244 private float distance(float x, float y) { return (float)Math.sqrt(distance2(x, y)); }
245 public float distance2(Point v) { return distance2(v.x, v.y); }
246 private float distance2(float x, float y) { return (this.x-x)*(this.x-x)+(this.y-y)*(this.y-y); }
247 public float x(Affine a) { return a.multiply_px(x,y); }
248 public float y(Affine a) { return a.multiply_py(x,y); }
249 public int xi(Affine a) { return (int)x(a); }
250 public int yi(Affine a) { return (int)y(a); }
251 public boolean intersects(Point p1, Point p2) {
253 Mesh.side(p1,p2,this)==0 &&
254 x <= Math.max(p1.x,p2.x) &&
255 x >= Math.min(p1.x,p2.x) &&
256 y <= Math.max(p1.y,p2.y) &&
257 y >= Math.min(p1.y,p2.y);
261 private final class Vertex extends Point implements org.ibex.arenaj.Gladiator {
262 public Vertex(Point p) { super(p); numvertices++; }
265 // Edge //////////////////////////////////////////////////////////////////////////////
267 public Edge newEdge(Vertex v1, Vertex v2) {
268 return getEdge(v1,v2);
270 if (v1==v2) throw new Error();
271 Edge ret = (Edge)edges.get(v1,v2);
272 //if (ret != null) throw new Error("tried to get an edge that already exists!");
273 if (ret == null) ret = new Edge(v1,v2);
278 public Edge getEdge(Vertex v1, Vertex v2) {
279 if (v1==v2) throw new Error();
280 //Edge ret = (Edge)edges.get(v1,v2);
283 if (triangle0 != null) {
284 t = triangle0.seek(point(v1,v2));
286 for(int i=1; i<=3; i++)
287 if (t.e(i).hasVertex(v1) && t.e(i).hasVertex(v2)) ret = t.e(i);
290 ret = (Edge)edges.get(v1,v2);
291 if (ret != null && (ret.t1 != null || ret.t2 != null)) throw new Error("bah! " + ret);
293 if (ret == null) ret = new Edge(v1,v2);
297 private final class Edge implements org.ibex.arenaj.Gladiator {
298 private final Vertex v1;
299 private final Vertex v2;
303 private int locks = 0;
304 private int weight = 0;
306 public void delete() {
307 if (t1!=null || t2!=null) throw new Error("tried to remove an edge before its triangles");
308 edges.put(v1,v2,null);
309 edges.put(v2,v1,null);
312 public Vertex v(int i) { return i==1?v1:i==2?v2:null; }
314 public Edge rotate(Vertex v, boolean clockwise) {
315 Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null;
316 if (t==null) return null;
317 for(int i=1; i<=3; i++) if (t.e(i)!=this && t.e(i).hasVertex(v)) return t.e(i);
320 public Edge rotateHull(boolean clockwise) {
321 if (t1!=null && t2!=null) throw new Error("nextHull() called on non-hull edge");
322 Vertex v = rotate(v1, !clockwise) == null ? v2 : v1;
323 Edge e = rotate(v, !clockwise);
324 while(!e.hasTriangle(null) && e!=this) e = e.rotate(v, !clockwise);
325 if (e==this) throw new Error("confused");
329 public boolean isNear(Point p) { return area(v1,v2,p) < epsilon2; }
330 public Vertex commonVertex(Edge e) { return v1==e.v(1) || v1==e.v(2) ? v1 : v2==e.v(1) || v2==e.v(2) ? v2 : null; }
331 public Vertex unCommonVertex(Edge e) { return v1!=e.v(1) && v1!=e.v(2) ? v1 : v2!=e.v(1) && v2!=e.v(2) ? v2 : null; }
332 public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; }
333 public int weight() { return weight; }
334 public int weight(Vertex v) { return v==v1?weight:(-1*weight); }
335 public boolean locked() { return locks > 0; }
336 public boolean partitions(Point va, Point vb) { return side(va,vb)==-1; }
337 public int side(Point a, Point b) { return side(a) * side(b); }
338 public int side(Point a) { return Mesh.side(v(1), v(2), a); }
339 public boolean hasVertex(Vertex v) { return v1==v || v2==v; }
340 public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; }
341 public String toString() { return v(1) + "--" + v(2); }
342 public void rmTriangle(Triangle t) {
343 if (t1==t) t1 = null;
344 else if (t2==t) t2 = null;
345 else throw new Error();
346 if (t1==null && t2==null) delete();
348 public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); }
350 public boolean colinear(Point v) { return area(v,v1,v2)<=epsilon; }
352 public boolean intersects(Point p) {
355 p.x <= Math.max(v1.x,v2.x) &&
356 p.x >= Math.min(v1.x,v2.x) &&
357 p.y <= Math.max(v1.y,v2.y) &&
358 p.y >= Math.min(v1.y,v2.y);
360 public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); }
361 public boolean intersects(Point va, Point vb) {
367 partitions(va, vb) &&
368 Mesh.side(va, vb, v1) * Mesh.side(va, vb, v2) == -1;
370 public Triangle opposingTriangle(Triangle t) {
371 if (t1 == t) return t2;
372 if (t2 == t) return t1;
375 public void addTriangle(Triangle tnew) {
376 if (t1==null) t1 = tnew;
377 else if (t2==null) t2 = tnew;
378 else throw new Error("attempted to addTriangle("+tnew+")\n t1="+t1+"\n t2="+t2);
379 if (t1==t2) throw new Error("same triangle can't be both sides of an edge");
381 boolean b = side(t1.opposingVertex(this)) == side(point(Float.MAX_VALUE, v1.y));
382 Triangle right = b ? t1 : t2; // right side
383 Triangle left = b ? t2 : t1; // left side
387 boolean b = side(t1.opposingVertex(this)) == side(point(0, Float.MAX_VALUE));
388 Triangle top = b ? t1 : t2;
389 Triangle bottom = b ? t2 : t1;
390 if (v1.y==v2.y) { // horizontal
393 } else if (v1.x > v2.x) { // positive slope
396 } else { // negative slope
402 public void bisect(Vertex v) {
404 Triangle t1 = this.t1==null?this.t2:this.t1;
405 Triangle t = t1==this.t1?this.t2:this.t1;
406 Vertex opposing = t1.opposingVertex(e);
407 Triangle top = null, ton = null;
408 Vertex left = e.v(1);
409 Vertex right = e.v(2);
413 Triangle opposingTriangleLeft = t1.opposingTriangle(left);
414 Triangle opposingTriangleRight = t1.opposingTriangle(right);
415 Edge right_v = newEdge(right, v);
416 Edge left_v = newEdge(left, v);
417 Edge opposing_v = newEdge(opposing, v);
419 Edge right_tov = null;
420 Edge left_tov = null;
421 Edge right_opposing = t1.opposingEdge(left);
422 Edge left_opposing = t1.opposingEdge(right);
425 right_tov = t.opposingEdge(left);
426 left_tov = t.opposingEdge(right);
427 top = t.opposingTriangle(left);
428 ton = t.opposingTriangle(right);
429 tov = t.opposingVertex(t1);
431 tov_v = newEdge(tov, v);
432 if (top == t1) top = null;
433 if (ton == t1) ton = null;
434 if (opposingTriangleLeft == t) opposingTriangleLeft = null;
435 if (opposingTriangleRight == t) opposingTriangleRight = null;
439 Triangle ta, tb, tc, td;
440 ta = triangle(right_opposing, opposing_v, right_v);
441 tb = triangle(left_opposing, opposing_v, left_v);
445 tc = triangle(left_tov, tov_v, left_v);
446 td = triangle(right_tov, tov_v, right_v);
450 if (locked()) fracture(v);
454 if (locked()) throw new Error("attempted to remove a locked edge: " + this);
455 boolean in = t1.in && t2.in;
457 Edge e3 = rotate(v1, true);
458 Vertex vb = e3.unCommonVertex(this);
459 Edge e6 = e3.rotate(vb, true);
461 Edge e4 = rotate(v2, true);
462 Vertex va = e4.unCommonVertex(this);
463 Edge e1 = e4.rotate(va, true);
465 Edge e = newEdge(va, vb);
470 ta = triangle(e1, e, e3);
471 tb = triangle(e4, e, e6);
474 return ta.getSharedEdge(tb);
476 public void fracture(Vertex vx) {
477 if (!locked()) throw new Error("attempt to fracture an edge which does not exist: " + v1 + " " + v2);
479 Edge v1vx = newEdge(v1, vx);
480 Edge vxv2 = newEdge(vx, v2);
484 v1vx.weight += v(1)==v1vx.v(1) ? weight : (-1 * weight);
485 vxv2.weight += v(2)==vxv2.v(2) ? weight : (-1 * weight);
490 public void fracture(Edge e) {
491 triangle0=e.t1==null?e.t2:e.t1;
492 Vertex v0 = vertex(Mesh.this.intersect(v1,v2,e.v(1),e.v(2)));
493 if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0);
494 if (v0 != v1 && v0 != v2) fracture(v0);
496 public void lock(Vertex v1, int delta) {
497 weight += this.v(1)==v1 ? delta : (-1 * delta);
502 Triangle t = t1==null ? t2 : t1;
503 if (t==null) t = triangle0.seek(v1);
504 if (!t.hasVertex(v1)) throw new Error("this sucks balls");
505 boolean skipfo = false;
506 for(Triangle told = null; t != told; t = told==null ? t : t.followVector(v1,v2)) {
508 if (!t.encounters(v1,v2)) break;
509 if (!t.encounters(v2,v1)) break;
510 Triangle tlast = t.followVector(v2,v1);
511 if (tlast == null) throw new Error("seek from: " + tlast + "\n " + v1 + " -> " + v2);
512 if (tlast == t) { if (t.hasVertex(v1)) continue; throw new Error("no predecessor"); }
513 Edge e = t.getSharedEdge(tlast);
514 if (!e.convex()) continue;
515 if (e.v(1)==v1 || e.v(1)==v2 || e.v(2)==v1 || e.v(2)==v2) { continue; }
516 if (this.intersects(e.v(1))) { fracture(e.v(1)); return; }
517 if (this.intersects(e.v(2))) { fracture(e.v(2)); return; }
518 if (!this.intersects(e)) continue;
523 Edge eold = e = e.flip();
525 if (t==null || !t.intersects(this)) t = e.t2;
527 if (eold.intersects(this)) {
528 t = t.followVector(v1,v2);
529 if (t != e.t1 && t != e.t2) t = told;
533 while(t.intersects(this)) {
536 t = t.followVector(v2,v1);
544 if (t1!=null) t1.fixup();
545 if (t2!=null) t2.fixup();
548 public void stroke(PixelBuffer buf, Affine a, int color) {
550 ? (weight() == 0 ? color : 0xffff0000)
551 : (weight() != 0 ? color : 0);
552 if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c);
554 public Edge(Vertex v1, Vertex v2) {
555 boolean b = v1.y < v2.y || (v1.y==v2.y && v1.x < v2.x);
556 this.v1 = b ? v1 : v2;
557 this.v2 = b ? v2 : v1;
558 edges.put(v1, v2, this);
559 edges.put(v2, v1, this);
563 // Triangle //////////////////////////////////////////////////////////////////////////////
565 public Triangle triangle(Edge e1, Edge e2, Edge e3) {
566 float x = (e1.v(1).x+e1.v(2).x+e2.v(1).x+e2.v(2).x+e3.v(1).x+e3.v(2).x)/6;
567 float y = (e1.v(1).y+e1.v(2).y+e2.v(1).y+e2.v(2).y+e3.v(1).y+e3.v(2).y)/6;
568 Point p = point(x,y);
569 Triangle t = triangle0==null ? null : triangle0.seek(p);
571 (t.contains(p) || t.intersects(p)) &&
575 return triangle0 = t;
576 t = new Triangle(e1, e2, e3);
577 if (debug) t.check();
578 if (triangle0 == null) triangle0 = t;
582 public static boolean fixing = false;
583 private final class Triangle implements org.ibex.arenaj.Gladiator {
588 private Edge e1, e2, e3; // should be final =(
592 boolean inWasSet = false;
593 boolean painted = false;
594 boolean dirty = true;
596 public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; }
597 public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); }
598 public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; }
600 public boolean encounters(Point p1, Point p2) {
601 for(int i=1; i<=3; i++) {
602 if (v(i).equals(p1)) return true;
603 if (v(i).equals(p2)) return true;
604 if (v(i).intersects(p1,p2)) return true;
605 if (e(i).intersects(p1,p2)) return true;
607 return contains(p1) || contains(p2);
609 public Edge getSharedEdge(Triangle t) { return e(1).t1==t||e(1).t2==t?e(1):e(2).t1==t||e(2).t2==t?e(2):e(3).t1==t||e(3).t2==t?e(3):null; }
610 public boolean contains(Point p) { return e(1).side(v(1),p)==1 && e(2).side(v(2),p)==1 && e(3).side(v(3),p)==1; }
611 public Point c() { return point(cx(),cy()); }
612 public float cx() { return (float)(((double)v(1).x+(double)v(2).x+(double)v(3).x)/3); }
613 public float cy() { return (float)(((double)v(1).y+(double)v(2).y+(double)v(3).y)/3); }
614 public boolean intersects(Vertex va, Vertex vb){return e(1).intersects(va,vb)||e(2).intersects(va,vb)||e(3).intersects(va,vb);}
615 public boolean intersects(Edge e){ return intersects(e.v(1),e.v(2)); }
616 public boolean intersects(Point p){ return e(1).intersects(p) || e(2).intersects(p) || e(3).intersects(p); }
617 public boolean hasEdge(Edge e) { return e.t1==this || e.t2==this; }
618 public boolean hasEdge(Vertex a, Vertex b) { return a!=b && (a==v(1)||a==v(2)||a==v(3)) && (b==v(1)||b==v(2)||b==v(3)); }
619 public boolean hasVertex(Vertex a) { return a==v(1) || a==v(2) || a==v(3); }
620 public Vertex opposingVertex(Triangle t) { return t(3)==t ? v(3) : t(1)==t ? v(1) : t(2)==t ? v(2) : null; }
621 public Vertex opposingVertex(Edge e) { return e==e(1) ? v(1) : e==e(2) ? v(2) : e==e(3) ? v(3) : null; }
622 public Edge opposingEdge(Vertex v) { return v==v(1) ? e(1) : v==v(2) ? e(2) : v==v(3) ? e(3) : null; }
623 public Triangle opposingTriangle(Vertex v) { return v(1)==v ? t(1) : v(2)==v ? t(2) : v(3)==v ? t(3) : null; }
624 public String toString() { return "<<"+v(1)+""+v(2)+""+v(3)+">>"; }
626 public void stroke(PixelBuffer buf, Affine a, int color) {
627 for(int i=1; i<=3; i++) if (in || debug) e(i).stroke(buf, a, color);
629 public Triangle fixup() {
630 if (!dirty) return this;
632 for(int i=1; i<=3; i++) {
634 if (t==null) continue;
635 if (t.r2 <= v(i).distance2(t.cc)) continue;
637 if (e.locked()) { t.fixup(); continue; }
638 return e.flip().t1.fixup();
642 public void addHull(Vertex vnew) {
643 Edge e = e(1).hasTriangle(null) ? e(1) : e(2).hasTriangle(null) ? e(2) : e(3).hasTriangle(null) ? e(3) : null;
644 Triangle t = e.opposingTriangle(null), newt = null;
645 while (!e.partitions(vnew, t.opposingVertex(e))) {
646 e = e.rotateHull(true);
647 t = e.opposingTriangle(null);
649 Edge ea = newEdge(e.v(1), vnew);
650 Edge eb = newEdge(e.v(2), vnew);
651 newt = triangle(e, ea, eb);
652 if (ea.rotateHull(true) != eb) { Edge temp = ea; ea = eb; eb = temp; }
653 for(int i=1; i<=2; i++)
654 for(Edge ex = i==1?eb:ea; ;) {
655 e = ex.rotateHull(i==1);
656 t = e.opposingTriangle(null);
657 if (!e.partitions(vnew, t.opposingVertex(e))) break;
658 Edge ep = newEdge(vnew, e.unCommonVertex(ex));
659 newt = triangle(e, ex, ep);
662 if (newt==null) throw new Error("couldn't find a place to add a triangle for " + vnew);
665 public Triangle seek(Point p) {
669 if (t.contains(p) || t.intersects(p)) return t;
670 else if (t.e(3).intersects(p)) return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t;
671 else if (t.e(1).intersects(p)) return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t;
672 else if (t.e(2).intersects(p)) return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t;
674 Triangle t2 = t.followVector(t.c(), p);
675 if (t2==null || t2==t) return t;
679 } finally { if (t!=null) triangle0 = t; }
682 // gives the triangle across the edge through which the ray v(1)-->v(2) exits this triangle
683 public Triangle followVector(Point p1, Point p2) {
684 Triangle ret = followVector2(p1, p2);
685 if (ret==null) return ret;
687 if (!ret.encounters(p1,p2)) return this;
690 public Triangle followVector2(Point p1, Point p2) {
691 if (contains(p2) || intersects(p2) || v(1).equals(p2) || v(2).equals(p2) || v(3).equals(p2)) return this;
692 for(int i=1; i<=3; i++) if (!v(i).equals(p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2);
696 for(int i=1; i<=3; i++) {
697 int k1 = i==1?3:i==2?1:i==3?2:0;
698 int k2 = i==1?2:i==2?3:i==3?1:0;
699 int k3 = i==1?1:i==2?2:i==3?3:0;
700 if (v(i).equals(p1)) {
701 if (e(k1).partitions(v(k1),p2)) return t(k1);
702 if (e(k2).partitions(v(k2),p2)) return t(k2);
703 if (e(k3).partitions(v(k3),p2)) return t(k3);
704 throw new Error("bad!");
707 if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2))
708 throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" +
711 " t =" + this + " (area "+area(v(1),v(2),v(3))+")\n");
712 for(int i=1; i<=3; i++) if (e(i).intersects(p1,p2) && e(i).side(v(i)) * e(i).side(p2) == -1) return t(i);
713 throw new Error("giving up: \n "+p1+" -> "+p2+"\n " + this);
716 public void check() {
718 for(int i=1; i<=3; i++) {
719 if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent");
720 if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent");
721 if (e(i).t1 == e(i).t2) throw new Error("same triangle on both sides of edge");
723 if (e(1)==e(2) || e(2)==e(3) || e(3)==e(1)) throw new Error("identical edges");
724 for(int i=1; i<=3; i++) {
725 if (t(i) != null) if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)");
727 if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark");
728 if (!e(i).hasTriangle(t(i))) throw new Error("blark2");
729 if (!e(i).hasTriangle(this)) throw new Error("blark3");
732 // check that edges all join up
736 public void trisect(Vertex v) {
737 if (!contains(v)) throw new Error("trisect(v) but I don't contain v = " + v);
738 if (hasVertex(v)) throw new Error("attempt to trisect a triangle at one of its own vertices");
739 for(int i=3; i>0; i--) if (e(i).isNear(v)) { e(i).bisect(v); return; }
740 Triangle a=null,b=null,c=null;
743 Edge v1v = newEdge(v(1), v);
744 Edge v2v = newEdge(v(2), v);
745 Edge v3v = newEdge(v(3), v);
751 a = triangle(e3, v1v, v2v);
752 b = triangle(e2, v1v, v3v);
753 c = triangle(e1, v3v, v2v);
760 public void setIn(boolean evenOdd, int weight) {
761 if (inWasSet) return;
763 in = (evenOdd && weight%2!=0) || (!evenOdd && weight!=0);
764 for(int i=1; i<=3; i++) if (t(i) != null) t(i).setIn(evenOdd, weight + e(i).weight());
767 public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
770 if (in) buf.fillTriangle(v(1).xi(a), v(1).yi(a), v(2).xi(a), v(2).yi(a), v(3).xi(a), v(3).yi(a), color);
771 for(int i=1; i<=3; i++)
773 boolean prepaint = t(i).painted;
774 if (debug) e(i).stroke(buf, a, color);
775 t(i).fill(buf, a, clip, color, strokeOnly);
779 public Triangle(Edge e1, Edge e2, Edge e3) {
783 Vertex v1 = e(2).unCommonVertex(e(1));
784 Vertex v2 = e(3).unCommonVertex(e(2));
785 Vertex v3 = e(1).unCommonVertex(e(3));
786 if (e(1).intersects(v1)) throw new Error("triangle points are colinear");
787 if (e(2).intersects(v2)) throw new Error("triangle points are colinear");
788 if (e(3).intersects(v3)) throw new Error("triangle points are colinear");
789 e(1).addTriangle(this);
790 e(2).addTriangle(this);
791 e(3).addTriangle(this);
794 Q: for(int q=0; q<2; q++) {
795 for(int i=0; i<3; i++) {
796 if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q;
797 Vertex t = v2; v2=v3; v3=v1; v1 = t;
799 Vertex t = v2; v2=v3; v3=t;
801 if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
802 float a1=(v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
803 float a2=(v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
804 cc=point((a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2, (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2);
805 r2 = v1.distance2(cc);
808 public void clear() {
809 if (!painted) return;
811 if (t(3) != null) t(3).clear();
812 if (t(1) != null) t(1).clear();
813 if (t(2) != null) t(2).clear();
815 public void delete() {
816 if (triangle0 == this) {
817 if (t(1) != null) triangle0 = t(1);
818 else if (t(2) != null) triangle0 = t(2);
819 else if (t(3) != null) triangle0 = t(3);
820 else triangle0 = null;
822 triangles.remove(this);
823 e(1).rmTriangle(this);
824 e(2).rmTriangle(this);
825 e(3).rmTriangle(this);
832 // Queries /////////////////////////////////////////////////////////////////////////////////
834 public boolean queryPoint(Point p) {
835 if (triangle0==null) return false;
836 Triangle ret = triangle0.seek(p);
837 return (ret.contains(p) || ret.intersects(p)) && ret.in;
841 // Drawing //////////////////////////////////////////////////////////////////////////////
843 public void setIn(boolean evenOdd) {
844 iterateTriangles(ITERATE_CLEAR_WASSET, null, null);
845 triangle0.setIn(evenOdd, 1);
848 public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
849 if (triangle0==null) return;
850 iterateTriangles(ITERATE_CLEAR, null, null);
851 triangle0.fill(buf, a, clip, color, strokeOnly);
854 public void stroke(PixelBuffer buf, Affine a, int color) {
855 if (triangle0==null) return;
856 iterateTriangles(ITERATE_STROKE, null, a, buf, color);
859 public void newcontour() {
860 if (start != null) add(start.x, start.y);
865 public Mesh addRect(float x, float y, float w, float h) {
866 if (w==0 || h==0) return this;
867 Vertex v1 = vertex(point(x,y));
868 Vertex v2 = vertex(point(x+w,y));
869 Vertex v3 = vertex(point(x+w,y+h));
870 Vertex v4 = vertex(point(x,y+h));
871 newEdge(v1,v2).lock(v1,1);
872 newEdge(v2,v3).lock(v2,1);
873 newEdge(v3,v4).lock(v3,1);
874 newEdge(v4,v1).lock(v4,1);
879 public void add(float x, float y) {
880 Vertex vx = vertex(point(x,y));
881 if (vx==last) return;
882 if (start==null) start = vx;
884 if (last==null) return;
885 if (numvertices<3) return;
886 if (numvertices==3) getEdge(start, last).lock(start,1);
887 getEdge(last,vx).lock(last,1);