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.*;
13 // FIXME: Not all triangles who get their dirty bit set wind up having fixup() called on them -- bad!!
15 // FEATURE: Delauanay refinement
17 // - allow edge-constraint removal
18 // - store "which curve is inside me" pointer in Triangle
19 // - split if two curves enter
20 // - go to treating Vertex as a value class (epsilon==0)
22 // - [??] preserve in/out-ness every time we delete() a triangle
25 * An incremental, adaptive, addWeighted Delaunay Triangulation.
26 * @see Kallmann, Bieri, and Thalmann: Fully Dynamic AddWeighted Delaunay Triangulations
28 public final class Mesh {
30 private static final float epsilon = (float)0.0;
31 private static final float epsilon2 = (float)0.0;
32 private static final boolean debug = false;
33 //private static final boolean check = true;
34 private static final boolean check = false;
36 private Vector triangles = new Vector(); /* we no longer need this */
37 private Hash edges = new Hash(); /* we no longer need this either */
38 private int numvertices = 0;
39 private Triangle triangle0 = null;
40 private Vertex vertex0 = null;
41 private Vertex vertex1 = null;
42 private Vertex start = null;
43 private Vertex last = null;
47 m.vertex(triangle0.v(1));
48 m.vertex(triangle0.v(2));
49 m.vertex(triangle0.v(3));
50 Object[] edges = this.edges.vals();
51 for(int i=0; i<edges.length; i++) {
52 Edge e = (Edge)edges[i];
53 Vertex mv1 = m.vertex(e.v(1));
54 Vertex mv2 = m.vertex(e.v(2));
55 Edge me = m.getEdge(mv1, mv2);
71 // Chain //////////////////////////////////////////////////////////////////////////////
73 public static interface Chain {
74 public Mesh.Chain getMeshChainParent();
75 public Affine getAffine();
76 public Mesh getMesh();
79 // Constructor //////////////////////////////////////////////////////////////////////////////
82 public Mesh(Path p, boolean evenOdd) { p.addTo(this, evenOdd); }
84 public void subtract(Mesh m, Affine a) { clipOp(m,a,true); }
85 public void intersect(Mesh m, Affine a) { clipOp(m,a,false); }
86 public void add(Mesh m, Affine a) { iterateTriangles(ITERATE_ADD, m, a); }
87 public static long seekTime = 0;
89 public static final int ITERATE_SUBTRACT = 1;
90 public static final int ITERATE_INTERSECT = 2;
91 public static final int ITERATE_ADD = 3;
92 public static final int ITERATE_CLEAR_WASSET = 4;
93 public static final int ITERATE_CLEAR = 5;
94 public static final int ITERATE_STROKE = 6;
96 Triangle[] iter = new Triangle[100];
98 private void iterateTriangles(int mode, Mesh m, Affine a) { iterateTriangles(mode, m, a, null, 0); }
99 private void iterateTriangles(int mode, Mesh m, Affine a, PixelBuffer buf, int color) {
102 if (iter.length < triangles.size()) iter = new Triangle[triangles.size()];
103 iter[numiter++] = triangle0;
105 Triangle t = iter[--numiter];
106 if (t==null) return; // FIXME: is this right?!?
107 if (t.tick >= this.tick) continue;
109 case ITERATE_STROKE: t.stroke(buf, a, color); break;
110 case ITERATE_CLEAR: t.clear(); break;
111 case ITERATE_CLEAR_WASSET: t.inWasSet = false; break;
112 case ITERATE_INTERSECT:
113 case ITERATE_SUBTRACT: {
115 Point p = Imprecise.center(Mesh.this, t.v(1), t.v(2), t.v(3));
116 boolean oin = m.queryPoint(p.multiply(a));
117 t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin);
121 for(int i=1; i<=3; i++) {
123 if (e.t1 != null && e.t1.tick >= this.tick) continue;
124 if (e.t2 != null && e.t2.tick >= this.tick) continue;
125 if (!e.locked()) continue;
126 if ((e.t1==null || !e.t1.in) && (e.t2==null || !e.t2.in)) continue;
127 Point p1 = e.v(1).multiply(a);
128 Point p2 = e.v(2).multiply(a);
129 Vertex v1=null, v2=null;
132 if (v1==v2) continue;
133 m.getEdge(v1, v2).lock(v1, 0);
135 if (check) checkAllDelaunay();
140 for(int i=1; i<=3; i++) {
141 Triangle ti = t.t(i);
142 if (ti == null) continue;
143 if (ti.tick >= this.tick) continue;
144 iter[numiter++] = ti;
148 public void checkAllDelaunay() {
149 for(int i=0; i<triangles.size(); i++)
150 ((Triangle)triangles.get(i)).checkDelaunay();
153 public void clipOp(Mesh m, Affine a, boolean subtract) {
155 long start = System.currentTimeMillis();
157 iterateTriangles(subtract ? ITERATE_SUBTRACT : ITERATE_INTERSECT, m, a.inverse());
158 float total = (float)((System.currentTimeMillis() - start));
159 float seek = (float)seekTime;
160 if (total > 80) System.out.println("clip in " + (100 * (seek/total)) + "%");
163 // Imprecise Geometry //////////////////////////////////////////////////////////////////////////////
164 // (all of these can be off by a good margin and degrade only performance, not correctness) ////////
165 ////////////////////////////////////////////////////////////////////////////////////////////////////
167 private static class Imprecise {
168 public static Point center(Mesh m, Point v1, Point v2, Point v3) {
169 return m.point((float)((double)v1.x+(double)v2.x+(double)v3.x)/3,
170 (float)(((double)v1.y+(double)v2.y+(double)v3.y)/3));
172 public static boolean near(Point a, Point b) {
173 return ddistance(a.x, a.y, b.x, b.y) <= epsilon;
175 public static boolean incircle(Point v1, Point v2, Point v3, Point p) {
178 Q: for(int q=0; q<2; q++) {
179 for(int i=0; i<3; i++) {
180 if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q;
181 Point t = v2; v2=v3; v3=v1; v1 = t;
183 Point t = v2; v2=v3; v3=t;
185 if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
186 double a1 = (v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
187 double a2 = (v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
188 double ccx = (a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2;
189 double ccy = (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2;
190 double r2 = (v1.x-ccx)*(v1.x-ccx)+(v1.y-ccy)*(v1.y-ccy);
191 double pd = (p.x-ccx)*(p.x-ccx)+(p.y-ccy)*(p.y-ccy);
194 return Predicates.incircle(v1.x, v1.y, v2.x, v2.y, v3.x, v3.y, p.x, p.y)>0;
196 public static Point midpoint(Mesh m, Point a, Point b) { return m.point((a.x+b.x)/2,(a.y+b.y)/2); }
197 private static double ddistance(double x1, double y1, double x2, double y2) {
198 return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
199 public static float area(Point p1, Point p2, Point p3) {
206 double a = ddistance(x1,y1,x2,y2);
207 double b = ddistance(x2,y2,x3,y3);
208 double c = ddistance(x3,y3,x1,y1);
209 double s = (a+b+c)/2;
210 double t = s*(s-a)*(s-b)*(s-c);
212 return (float)Math.sqrt(t);
215 public static Point intersect(Mesh m, Point v1, Point v2, Point v3, Point v4) {
216 double a1 = v2.y-v1.y;
217 double a2 = v4.y-v3.y;
218 double b1 = v1.x-v2.x;
219 double b2 = v3.x-v4.x;
220 double c1 = -1 * (a1*v1.x+b1*v1.y);
221 double c2 = -1 * (a2*v3.x+b2*v3.y);
222 double x = (b2*c1-c2*b1)/(b1*a2-b2*a1);
223 double y = (a2*c1-c2*a1)/(a1*b2-a2*b1);
224 if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n ");
225 return m.point((float)x,(float)y);
227 public static int side(Point p1, Point p2, Point p3) {
237 // this MUST be done to double precision
238 double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2);
239 if (c > 0) ret = b>=0 ? -1 : 1;
240 else if (c < 0) ret = b>=0 ? 1 : -1;
244 return Predicates.side(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
249 // Precise Geometry /////////////////////////////////////////////////////////////////////////////
252 Runtime.getRuntime().load(new java.io.File("Predicates.jnilib").getAbsolutePath());
256 // Vertex //////////////////////////////////////////////////////////////////////////////
258 public static int state = 0;
259 public Vertex vertex(Point p, Affine a) { return vertex(p.multiply(a)); }
260 public Vertex vertex(Point p) {
262 switch(numvertices) {
263 case 0: return (vertex0 = new Vertex(p));
264 case 1: return Imprecise.near(vertex0,p) ? vertex0 : (vertex1 = new Vertex(p));
266 if (Imprecise.near(vertex0,p)) return vertex0;
267 if (Imprecise.near(vertex1,p)) return vertex1;
268 Vertex v2 = new Vertex(p);
269 triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0));
274 t = triangle0.seek(p);
275 for(int i=1; i<=3; i++)
276 for(int j=1; j<=2; j++)
277 if (t != null && Imprecise.near(t.e(i).v(j),p))
279 // this will probably always need to be here since a vertex for which side()==0 could still
280 // be slightly off to one side (and hence part of a neighboring "sliver" triangle.
281 for(int k=1; k<=3; k++)
282 for(int i=1; i<=3; i++)
283 for(int j=1; j<=2; j++)
284 if (t != null && t.t(k)!=null && Imprecise.near(t.t(k).e(i).v(j),p))
285 return t.t(k).e(i).v(j);
286 for(int i=0; i<vertices.size(); i++)
287 if (Imprecise.near(((Vertex)vertices.get(i)),p))
288 throw new Error("bah! " + p + " " + vertices.get(i) + " state: " + state +
294 Vertex v = new Vertex(p);
295 if (t.e(3).intersects(p)) t.e(3).bisect(v);
296 else if (t.e(1).intersects(p)) t.e(1).bisect(v);
297 else if (t.e(2).intersects(p)) t.e(2).bisect(v);
298 else if (t.contains(v)) t.trisect(v);
305 Vector vertices = new Vector();
307 private Point point(float x, float y) { return new Point(x,y); }
308 //private Point point(Point p, Affine a) { return point(p.x(a), p.y(a)); }
309 private class Point {
312 public String toString() { return "("+x+","+y+")"; }
313 public Point multiply(Affine a) { return point(x(a),y(a)); }
314 public Point(float x, float y) { this.x = x; this.y = y; }
315 public Point(Point p) { this(p.x,p.y); }
316 public float x(Affine a) { return a.multiply_px(x,y); }
317 public float y(Affine a) { return a.multiply_py(x,y); }
318 public int xi(Affine a) { return (int)x(a); }
319 public int yi(Affine a) { return (int)y(a); }
320 public boolean intersects(Point p1, Point p2) {
322 Imprecise.side(p1,p2,this)==0 &&
323 x <= Math.max(p1.x,p2.x) &&
324 x >= Math.min(p1.x,p2.x) &&
325 y <= Math.max(p1.y,p2.y) &&
326 y >= Math.min(p1.y,p2.y);
330 private final class Vertex extends Point implements org.ibex.classgen.opt.Arena.Gladiator {
331 public Vertex(Point p) {
338 // Edge //////////////////////////////////////////////////////////////////////////////
340 public Edge newEdge(Vertex v1, Vertex v2) {
341 return getEdge(v1,v2);
343 if (v1==v2) throw new Error();
344 Edge ret = (Edge)edges.get(v1,v2);
345 //if (ret != null) throw new Error("tried to get an edge that already exists!");
346 if (ret == null) ret = new Edge(v1,v2);
351 public Edge getEdge(Vertex v1, Vertex v2) {
352 if (v1==v2) throw new Error();
353 Edge ret = (Edge)edges.get(v1,v2);
354 if (ret != null) return ret;
357 if (triangle0 != null) {
358 t = triangle0.seek(Imprecise.midpoint(this, v1,v2));
360 for(int i=1; i<=3; i++)
361 if (t.e(i).hasVertex(v1) && t.e(i).hasVertex(v2)) ret = t.e(i);
364 ret = (Edge)edges.get(v1,v2);
365 if (ret != null && (ret.t1 != null || ret.t2 != null)) throw new Error("bah! " + ret);
367 if (ret == null) ret = new Edge(v1,v2);
371 private final class Edge implements org.ibex.classgen.opt.Arena.Gladiator {
372 private final Vertex v1;
373 private final Vertex v2;
377 private int locks = 0;
378 private int weight = 0;
380 public void delete() {
381 if (t1!=null || t2!=null) throw new Error("tried to remove an edge before its triangles");
382 edges.put(v1,v2,null);
383 edges.put(v2,v1,null);
386 public Vertex v(int i) {
390 default: return null;
394 public Edge rotate(Vertex v, boolean clockwise) {
395 Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null;
396 if (t==null) return null;
397 for(int i=1; i<=3; i++) if (t.e(i)!=this && t.e(i).hasVertex(v)) return t.e(i);
400 public Edge rotateHull(boolean clockwise) {
401 if (t1!=null && t2!=null) throw new Error("nextHull() called on non-hull edge");
402 Vertex v = rotate(v1, !clockwise) == null ? v2 : v1;
403 Edge e = rotate(v, !clockwise);
404 while(!e.hasTriangle(null) && e!=this) e = e.rotate(v, !clockwise);
405 if (e==this) throw new Error("confused");
409 public boolean isNear(Point p) { return Imprecise.area(v1,v2,p) <= epsilon2; }
410 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; }
411 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; }
412 public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; }
413 public int weight() { return weight; }
414 public int weight(Vertex v) { return v==v1?weight:(-1*weight); }
415 public boolean locked() { return locks > 0; }
416 public boolean partitions(Point va, Point vb) { return side(va,vb)==-1; }
417 public int side(Point a, Point b) { return side(a) * side(b); }
418 public int side(Point a) { return Imprecise.side(v(1), v(2), a); }
419 public boolean hasVertex(Vertex v) { return v1==v || v2==v; }
420 public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; }
421 public String toString() { return v(1) + "--" + v(2); }
422 public void rmTriangle(Triangle t) {
423 if (t1==t) t1 = null;
424 else if (t2==t) t2 = null;
425 else throw new Error();
426 if (t1==null && t2==null) delete();
428 public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); }
430 public boolean intersects(Point p) { return p.intersects(v1, v2); }
431 public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); }
432 public boolean intersects(Point va, Point vb) {
434 !Imprecise.near(v1,va) &&
435 !Imprecise.near(v1,vb) &&
436 !Imprecise.near(v2,va) &&
437 !Imprecise.near(v2,vb) &&
438 partitions(va, vb) &&
439 Imprecise.side(va, vb, v1) * Imprecise.side(va, vb, v2) == -1;
442 public Triangle opposingTriangle(Triangle t) {
443 if (t1 == t) return t2;
444 if (t2 == t) return t1;
447 public void addTriangle(Triangle tnew) {
448 if (t1==null) t1 = tnew;
449 else if (t2==null) t2 = tnew;
450 else throw new Error("attempted to addTriangle("+tnew+")\n t1="+t1+"\n t2="+t2);
451 if (t1==t2) throw new Error("same triangle can't be both sides of an edge");
453 boolean b = side(t1.opposingVertex(this)) == side(point(Float.MAX_VALUE, v1.y));
454 Triangle right = b ? t1 : t2; // right side
455 Triangle left = b ? t2 : t1; // left side
459 boolean b = side(t1.opposingVertex(this)) == side(point(0, Float.MAX_VALUE));
460 Triangle top = b ? t1 : t2;
461 Triangle bottom = b ? t2 : t1;
462 if (v1.y==v2.y) { // horizontal
465 } else if (v1.x > v2.x) { // positive slope
468 } else { // negative slope
474 public void bisect(Vertex v) {
475 if (v==this.v(1)) throw new Error("this should never happen");
476 if (v==this.v(2)) throw new Error("this should never happen");
478 Triangle t1 = this.t1==null?this.t2:this.t1;
479 Triangle t = t1==this.t1?this.t2:this.t1;
480 Vertex opposing = t1.opposingVertex(e);
481 Triangle top = null, ton = null;
482 Vertex left = e.v(1);
483 Vertex right = e.v(2);
487 Triangle opposingTriangleLeft = t1.opposingTriangle(left);
488 Triangle opposingTriangleRight = t1.opposingTriangle(right);
489 Edge right_v = newEdge(right, v);
490 Edge left_v = newEdge(left, v);
491 Edge opposing_v = newEdge(opposing, v);
493 Edge right_tov = null;
494 Edge left_tov = null;
495 Edge right_opposing = t1.opposingEdge(left);
496 Edge left_opposing = t1.opposingEdge(right);
499 right_tov = t.opposingEdge(left);
500 left_tov = t.opposingEdge(right);
501 top = t.opposingTriangle(left);
502 ton = t.opposingTriangle(right);
503 tov = t.opposingVertex(t1);
505 tov_v = newEdge(tov, v);
506 if (top == t1) top = null; // is this possible?
507 if (ton == t1) ton = null; // is this possible?
508 if (opposingTriangleLeft == t) opposingTriangleLeft = null; // is this possible?
509 if (opposingTriangleRight == t) opposingTriangleRight = null; // is this possible?
513 Triangle ta, tb, tc=null, td=null;
514 ta = triangle(right_opposing, opposing_v, right_v);
515 tb = triangle(left_opposing, opposing_v, left_v);
519 if (tov_v==left_v) throw new Error("barf");
520 if (tov_v==right_v) throw new Error("barf");
521 if (tov_v==left_tov) throw new Error("barf");
522 if (tov_v==right_tov) throw new Error("barf");
523 if (right_v==right_tov) throw new Error("barf");
524 if (left_v==left_tov) throw new Error("barf " + tov + " " + left);
525 tc = triangle(left_tov, tov_v, left_v);
526 td = triangle(right_tov, tov_v, right_v);
530 if (locked()) fracture(v);
532 if (ta!=null) ta.check();
533 if (tb!=null) tb.check();
534 if (tc!=null) tc.check();
535 if (td!=null) td.check();
538 if (locked()) throw new Error("attempted to remove a locked edge: " + this);
539 boolean in = t1.in && t2.in;
541 Edge e3 = rotate(v1, true);
542 Vertex vb = e3.unCommonVertex(this);
543 Edge e6 = e3.rotate(vb, true);
545 Edge e4 = rotate(v2, true);
546 Vertex va = e4.unCommonVertex(this);
547 Edge e1 = e4.rotate(va, true);
549 Edge e = newEdge(va, vb);
554 ta = triangle(e1, e, e3);
555 tb = triangle(e4, e, e6);
558 return ta.getSharedEdge(tb);
560 public void fracture(Vertex vx) {
561 if (!locked()) throw new Error("attempt to fracture an edge which does not exist: " + v1 + " " + v2);
563 Edge v1vx = newEdge(v1, vx);
564 Edge vxv2 = newEdge(vx, v2);
568 v1vx.weight += v(1)==v1vx.v(1) ? weight : (-1 * weight);
569 vxv2.weight += v(2)==vxv2.v(2) ? weight : (-1 * weight);
574 public void fracture(Edge e) {
575 triangle0=e.t1==null?e.t2:e.t1;
576 Vertex v0 = vertex(Imprecise.intersect(Mesh.this, v1,v2,e.v(1),e.v(2)));
577 if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0);
578 if (v0 != v1 && v0 != v2) fracture(v0);
580 public void lock(Vertex v1, int delta) {
581 weight += this.v(1)==v1 ? delta : (-1 * delta);
586 Triangle t = t1==null ? t2 : t1;
587 if (t==null) t = triangle0.seek(v1);
588 if (!t.hasVertex(v1)) throw new Error("this sucks balls");
589 boolean skipfo = false;
590 for(Triangle told = null; t != told; t = told==null ? t : t.followVector(v1,v2)) {
592 if (!t.encounters(v1,v2)) break;
593 if (!t.encounters(v2,v1)) break;
594 Triangle tlast = t.followVector(v2,v1);
595 if (tlast == null) throw new Error("seek from: " + tlast + "\n " + v1 + " -> " + v2);
596 if (tlast == t) { if (t.hasVertex(v1)) continue; throw new Error("no predecessor"); }
597 Edge e = t.getSharedEdge(tlast);
598 if (!e.convex()) continue;
599 if (e.v(1)==v1 || e.v(1)==v2 || e.v(2)==v1 || e.v(2)==v2) { continue; }
600 if (this.intersects(e.v(1))) { fracture(e.v(1)); return; }
601 if (this.intersects(e.v(2))) { fracture(e.v(2)); return; }
602 if (!this.intersects(e)) continue;
607 Edge eold = e = e.flip();
609 if (t==null || !t.intersects(this)) t = e.t2;
611 if (eold.intersects(this)) {
612 t = t.followVector(v1,v2);
613 if (t != e.t1 && t != e.t2) t = told;
617 while(t.intersects(this)) {
621 System.out.println("I think that " + this + " intersects:\n "+t);
622 for(int i=1; i<=3; i++)
623 System.out.println(" " + t.e(i) + ": " + t.e(i).intersects(this));
625 t = t.followVector(v2,v1);
633 if (t1!=null) t1.fixup();
634 if (t2!=null) t2.fixup();
637 public boolean violated = false;
638 public void stroke(PixelBuffer buf, Affine a, int color) {
643 ? (weight() == 0 ? color : 0xffff0000)
644 : (weight() != 0 ? color : 0);
645 if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c);
647 public Edge(Vertex v1, Vertex v2) {
648 boolean b = v1.y < v2.y || (v1.y==v2.y && v1.x < v2.x);
649 this.v1 = b ? v1 : v2;
650 this.v2 = b ? v2 : v1;
651 edges.put(v1, v2, this);
652 edges.put(v2, v1, this);
656 // Triangle //////////////////////////////////////////////////////////////////////////////
658 public Triangle triangle(Edge e1, Edge e2, Edge e3) {
659 if (e3.t1!=null && e3.t1.hasEdge(e2) && e3.t1.hasEdge(e1)) return e3.t1;
660 if (e3.t2!=null && e3.t2.hasEdge(e2) && e3.t2.hasEdge(e1)) return e3.t2;
661 if (e2.t1!=null && e2.t1.hasEdge(e2) && e2.t1.hasEdge(e1)) return e2.t1;
662 if (e2.t2!=null && e2.t2.hasEdge(e2) && e2.t2.hasEdge(e1)) return e2.t2;
663 if (e1.t1!=null && e1.t1.hasEdge(e2) && e1.t1.hasEdge(e1)) return e1.t1;
664 if (e1.t2!=null && e1.t2.hasEdge(e2) && e1.t2.hasEdge(e1)) return e1.t2;
665 Triangle t = new Triangle(e1, e2, e3);
666 if (debug) t.check();
667 if (triangle0 == null) triangle0 = t;
671 public static boolean fixing = false;
672 public static int count = 0;
673 private final class Triangle implements org.ibex.classgen.opt.Arena.Gladiator {
678 private Edge e1, e2, e3; // should be final =(
679 private Vertex v1, v2, v3;
683 boolean inWasSet = false;
684 boolean painted = false;
685 boolean dirty = true;
687 //public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; }
688 public Edge e(int i) {
693 default: return null;
696 //public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); }
697 public Vertex v(int i) {
702 default: return null;
704 public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; }
705 public Vertex closestVertex(Point p) {
706 double d1 = Math.sqrt((v(1).x-p.x)*(v(1).x-p.x)+(v(1).y-p.y)*(v(1).y-p.y));
707 double d2 = Math.sqrt((v(2).x-p.x)*(v(2).x-p.x)+(v(2).y-p.y)*(v(2).y-p.y));
708 double d3 = Math.sqrt((v(3).x-p.x)*(v(3).x-p.x)+(v(3).y-p.y)*(v(3).y-p.y));
709 return (d1 < d2 && d1 < d3) ? v(1) : (d2 < d3) ? v(2) : v(3);
712 public boolean encounters(Point p1, Point p2) {
713 for(int i=1; i<=3; i++) {
714 if (Imprecise.near(v(i),p1)) return true;
715 if (Imprecise.near(v(i),p2)) return true;
716 if (v(i).intersects(p1,p2)) return true;
717 if (e(i).intersects(p1,p2)) return true;
719 return contains(p1) || contains(p2);
721 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; }
722 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; }
724 public boolean intersects(Vertex va, Vertex vb){return e(1).intersects(va,vb)||e(2).intersects(va,vb)||e(3).intersects(va,vb);}
725 public boolean intersects(Edge e){ return intersects(e.v(1),e.v(2)); }
726 public boolean intersects(Point p){ return e(1).intersects(p) || e(2).intersects(p) || e(3).intersects(p); }
727 public boolean hasEdge(Edge e) { return e.t1==this || e.t2==this; }
728 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)); }
729 public boolean hasVertex(Vertex a) { return a==v(1) || a==v(2) || a==v(3); }
730 public Vertex opposingVertex(Triangle t) { return t(3)==t ? v(3) : t(1)==t ? v(1) : t(2)==t ? v(2) : null; }
731 public Vertex opposingVertex(Edge e) { return e==e(1) ? v(1) : e==e(2) ? v(2) : e==e(3) ? v(3) : null; }
732 public Edge opposingEdge(Vertex v) { return v==v(1) ? e(1) : v==v(2) ? e(2) : v==v(3) ? e(3) : null; }
733 public Triangle opposingTriangle(Vertex v) { return v(1)==v ? t(1) : v(2)==v ? t(2) : v(3)==v ? t(3) : null; }
734 public String toString() { return "<<"+v(1)+""+v(2)+""+v(3)+">>"; }
736 public void stroke(PixelBuffer buf, Affine a, int color) {
737 for(int i=1; i<=3; i++) if (in || debug) e(i).stroke(buf, a, color);
739 public Triangle fixup() {
740 if (!dirty) return this;
742 for(int i=1; i<=3; i++) {
744 if (t==null) continue;
745 if (!t.cc(v(i))) continue;
747 if (e.locked()) { t.fixup(); continue; }
748 return e.flip().t1.fixup();
752 public void addHull(Vertex vnew) {
753 Edge e = e(1).hasTriangle(null) ? e(1) : e(2).hasTriangle(null) ? e(2) : e(3).hasTriangle(null) ? e(3) : null;
754 Triangle t = e.opposingTriangle(null), newt = null;
755 while (!e.partitions(vnew, t.opposingVertex(e))) {
756 e = e.rotateHull(true);
757 t = e.opposingTriangle(null);
759 Edge ea = newEdge(e.v(1), vnew);
760 Edge eb = newEdge(e.v(2), vnew);
761 newt = triangle(e, ea, eb);
762 if (ea.rotateHull(true) != eb) { Edge temp = ea; ea = eb; eb = temp; }
763 for(int i=1; i<=2; i++)
764 for(Edge ex = i==1?eb:ea; ;) {
765 e = ex.rotateHull(i==1);
766 t = e.opposingTriangle(null);
767 if (!e.partitions(vnew, t.opposingVertex(e))) break;
768 Edge ep = newEdge(vnew, e.unCommonVertex(ex));
769 newt = triangle(e, ex, ep);
772 if (newt==null) throw new Error("couldn't find a place to add a triangle for " + vnew);
775 public Triangle seek(Point p) {
780 //System.out.println("seek " + t + " -> " + p + " / " + count);
781 if (t.contains(p)) { state = -1; return t; }
782 else if (t.intersects(p)) { state = 1; return t; }
783 else if (t.e(3).intersects(p)) { state = 2; return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t; }
784 else if (t.e(1).intersects(p)) { state = 3; return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t; }
785 else if (t.e(2).intersects(p)) {state = 4; return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t; }
787 // we "slingshot" back from the centroid in case we're inside of a "sliver" triangle
789 //Triangle t2 = t.followVector(p0, p);
790 Triangle t2 = t.followVector(t.closestVertex(p), p);
791 if (t2==null || t2==t) {
792 if (t.e(1).partitions(p, t.v(1)) && t.t(1)!=null) t = t.t(1);
793 else if (t.e(2).partitions(p, t.v(2)) && t.t(2)!=null) t = t.t(2);
794 else if (t.e(3).partitions(p, t.v(3)) && t.t(3)!=null) t = t.t(3);
804 } finally { if (t!=null) triangle0 = t; }
807 // gives the triangle across the edge through which the ray v(1)-->v(2) exits this triangle
808 public Triangle followVector(Point p1, Point p2) {
809 Triangle ret = followVector2(p1, p2);
810 if (ret==null) return ret;
812 if (!ret.encounters(p1,p2)) return this;
815 public Triangle followVector2(Point p1, Point p2) {
816 if (contains(p2) || intersects(p2) || Imprecise.near(v(1),p2) || Imprecise.near(v(2),p2) || Imprecise.near(v(3),p2))
818 for(int i=1; i<=3; i++) if (!Imprecise.near(v(i),p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2);
822 for(int i=1; i<=3; i++) {
823 int k1 = i==1?3:i==2?1:i==3?2:0;
824 int k2 = i==1?2:i==2?3:i==3?1:0;
825 int k3 = i==1?1:i==2?2:i==3?3:0;
826 if (Imprecise.near(v(i),p1)) {
827 if (e(k1).partitions(v(k1),p2)) return t(k1);
828 if (e(k2).partitions(v(k2),p2)) return t(k2);
829 if (e(k3).partitions(v(k3),p2)) return t(k3);
830 throw new Error("bad!");
833 //if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2))
834 for(int i=1; i<=3; i++)
835 if (e(i).intersects(p1,p2))
836 if (e(i).side(v(i)) * e(i).side(p2) == -1)
838 for(int i=1; i<=3; i++)
839 if (e(i).partitions(p1,p2))
841 for(int i=1; i<=3; i++)
842 if (e(i).partitions(v(i),p2))
844 for(int i=1; i<=3; i++)
845 if (v(i).intersects(p1,p2))
846 throw new Error("bad news: \n "+p1+" -> "+p2+"\n " + this);
848 System.out.println("slingshot from: " + p1 + " to " + p2 + " on " + this + "\n" +
849 (e(1).side(v(1)) * e(1).side(p2))+" "+
850 (e(2).side(v(2)) * e(2).side(p2))+" "+
851 (e(3).side(v(3)) * e(3).side(p2))
854 return followVector(new Point(2*p1.x-p2.x, 2*p1.y-p2.y), p2);
856 //throw new Error("giving up: \n "+p1+" -> "+p2+"\n " + this);
858 final Point pp1 = p1;
859 final Point pp2 = p2;
861 public void paint(Graphics g) {
862 g.setColor(java.awt.Color.white);
863 g.fillRect(0, 0, getWidth(), getHeight());
864 g.setColor(java.awt.Color.black);
865 g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(2).x+100, (int)v(2).y+100);
866 g.drawLine((int)v(3).x+100, (int)v(3).y+100, (int)v(2).x+100, (int)v(2).y+100);
867 g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(3).x+100, (int)v(3).y+100);
869 g.setColor(java.awt.Color.red);
870 g.drawLine((int)pp1.x+100, (int)pp1.y+100, (int)pp2.x+100, (int)pp2.y+100);
873 try { Thread.sleep(100000); } catch (Exception e) { }
877 throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" +
880 " t =" + this + " (area "+area(v(1)+100,v(2),v(3))+")\n");
884 public void check() {
885 if (e1==null && e2==null && e3==null) return;
887 for(int i=1; i<=3; i++) {
888 if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent");
889 if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent");
890 if (e(i).t1 == e(i).t2) throw new Error("same triangle on both sides of edge");
892 if (e(1)==e(2) || e(2)==e(3) || e(3)==e(1)) throw new Error("identical edges");
893 for(int i=1; i<=3; i++) {
894 if (t(i) == null) continue;
895 if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)");
896 if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark");
897 if (!e(i).hasTriangle(t(i))) throw new Error("blark2");
898 if (!e(i).hasTriangle(this)) throw new Error("blark3");
900 for(int i=1; i<=3; i++)
901 if (e(i).commonVertex(e(i==3?1:(i+1)))==null)
902 throw new Error("edges have no common vertex");
903 // check that delauanay property is preserved
907 public void checkDelaunay() {
908 for(int i=1; i<=3; i++) {
909 if (t(i) == null) continue;
910 Vertex v = t(i).opposingVertex(e(i));
911 if (!e(i).locked() && /*Imprecise.incircle(v(1), v(2), v(3), v)*/cc(v) /*&& !dirty && !t(i).dirty*/) {
912 //throw new Error("Delaunay violation: vertex " + v + "\n triangle: " + this);
913 //System.out.println("violation: " + e(i));
914 e(i).violated = true;
916 e(i).violated = false;
921 public void trisect(Vertex v) {
922 if (!contains(v)) throw new Error("trisect(v) but I don't contain v = " + v);
923 if (hasVertex(v)) throw new Error("attempt to trisect a triangle at one of its own vertices");
924 for(int i=3; i>0; i--) if (e(i).intersects(v)/* || e(i).isNear(v)*/) {
928 Triangle a=null,b=null,c=null;
931 Edge v1v = newEdge(v(1), v);
932 Edge v2v = newEdge(v(2), v);
933 Edge v3v = newEdge(v(3), v);
939 a = triangle(e3, v1v, v2v);
940 b = triangle(e2, v1v, v3v);
941 c = triangle(e1, v3v, v2v);
951 public void setIn(boolean evenOdd, int weight) {
952 if (inWasSet) return;
954 in = (evenOdd && weight%2!=0) || (!evenOdd && weight!=0);
955 for(int i=1; i<=3; i++) if (t(i) != null) t(i).setIn(evenOdd, weight + e(i).weight());
958 public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
961 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);
962 for(int i=1; i<=3; i++)
964 boolean prepaint = t(i).painted;
965 //if (debug) e(i).stroke(buf, a, color);
966 t(i).fill(buf, a, clip, color, strokeOnly);
970 public Triangle(Edge e1, Edge e2, Edge e3) {
974 /*Vertex*/ this.v1 = e(2).unCommonVertex(e(1));
975 /*Vertex*/ this.v2 = e(3).unCommonVertex(e(2));
976 /*Vertex*/ this.v3 = e(1).unCommonVertex(e(3));
977 if (e(1).intersects(v1)) throw new Error("triangle points are colinear");
978 if (e(2).intersects(v2)) throw new Error("triangle points are colinear");
979 if (e(3).intersects(v3)) throw new Error("triangle points are colinear");
980 e(1).addTriangle(this);
981 e(2).addTriangle(this);
982 e(3).addTriangle(this);
985 public boolean cc(Point p) {
987 Vertex v1 = e(2).unCommonVertex(e(1));
988 Vertex v2 = e(3).unCommonVertex(e(2));
989 Vertex v3 = e(1).unCommonVertex(e(3));
991 return Imprecise.incircle(v1, v2, v3, p);
993 public void clear() {
994 if (!painted) return;
996 if (t(3) != null) t(3).clear();
997 if (t(1) != null) t(1).clear();
998 if (t(2) != null) t(2).clear();
1000 public void delete() {
1001 if (triangle0 == this) {
1002 if (t(1) != null) triangle0 = t(1);
1003 else if (t(2) != null) triangle0 = t(2);
1004 else if (t(3) != null) triangle0 = t(3);
1005 else triangle0 = null;
1007 triangles.remove(this);
1008 e(1).rmTriangle(this);
1009 e(2).rmTriangle(this);
1010 e(3).rmTriangle(this);
1017 // Queries /////////////////////////////////////////////////////////////////////////////////
1019 public boolean queryPoint(Point p) {
1020 if (triangle0==null) return false;
1021 Triangle ret = triangle0.seek(p);
1022 return (ret.contains(p) || ret.intersects(p)) && ret.in;
1026 // Drawing //////////////////////////////////////////////////////////////////////////////
1028 public void setIn(boolean evenOdd) {
1029 iterateTriangles(ITERATE_CLEAR_WASSET, null, null);
1030 triangle0.setIn(evenOdd, 1);
1033 public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
1034 if (triangle0==null) return;
1035 iterateTriangles(ITERATE_CLEAR, null, null);
1036 triangle0.fill(buf, a, clip, color, strokeOnly);
1039 public void stroke(PixelBuffer buf, Affine a, int color) {
1040 if (triangle0==null) return;
1041 iterateTriangles(ITERATE_STROKE, null, a, buf, color);
1044 public void newcontour() {
1045 if (start != null) add(start.x, start.y);
1050 public Mesh addRect(float x, float y, float w, float h) {
1051 if (w==0 || h==0) return this;
1052 Vertex v1 = vertex(point(x,y));
1053 Vertex v2 = vertex(point(x+w,y));
1054 Vertex v3 = vertex(point(x+w,y+h));
1055 Vertex v4 = vertex(point(x,y+h));
1056 newEdge(v1,v2).lock(v1,1);
1057 newEdge(v2,v3).lock(v2,1);
1058 newEdge(v3,v4).lock(v3,1);
1059 newEdge(v4,v1).lock(v4,1);
1064 public void add(float x, float y) {
1065 Vertex vx = vertex(point(x,y));
1066 if (vx==last) return;
1067 if (start==null) start = vx;
1069 if (last==null) return;
1070 if (numvertices<3) return;
1071 if (numvertices==3) getEdge(start, last).lock(start,1);
1072 getEdge(last,vx).lock(last,1);
1076 if (check) checkAllDelaunay();