// Copyright 2000-2005 the Contributors, as shown in the revision logs. // Licensed under the GNU General Public License version 2 ("the License"). // You may not use this file except in compliance with the License. package org.ibex.graphics; import java.util.*; import java.util.collections.*; import org.ibex.util.*; import java.awt.*; // TODO: // FIXME: Not all triangles who get their dirty bit set wind up having fixup() called on them -- bad!! // FEATURE: Delauanay refinement // - allow edge-constraint removal // - store "which curve is inside me" pointer in Triangle // - split if two curves enter // - go to treating Vertex as a value class (epsilon==0) // - union() // - [??] preserve in/out-ness every time we delete() a triangle /** * An incremental, adaptive, addWeighted Delaunay Triangulation. * @see Kallmann, Bieri, and Thalmann: Fully Dynamic AddWeighted Delaunay Triangulations */ public final class Mesh { private static final float epsilon = (float)0.0; private static final float epsilon2 = (float)0.0; private static final boolean debug = false; //private static final boolean check = true; private static final boolean check = false; private Vector triangles = new Vector(); /* we no longer need this */ private Hash edges = new Hash(); /* we no longer need this either */ private int numvertices = 0; private Triangle triangle0 = null; private Vertex vertex0 = null; private Vertex vertex1 = null; private Vertex start = null; private Vertex last = null; public Mesh copy() { Mesh m = new Mesh(); m.vertex(triangle0.v(1)); m.vertex(triangle0.v(2)); m.vertex(triangle0.v(3)); Object[] edges = this.edges.vals(); for(int i=0; i 0) { Triangle t = iter[--numiter]; if (t==null) return; // FIXME: is this right?!? if (t.tick >= this.tick) continue; switch(mode) { case ITERATE_STROKE: t.stroke(buf, a, color); break; case ITERATE_CLEAR: t.clear(); break; case ITERATE_CLEAR_WASSET: t.inWasSet = false; break; case ITERATE_INTERSECT: case ITERATE_SUBTRACT: { if (!t.in) break; Point p = Imprecise.center(Mesh.this, t.v(1), t.v(2), t.v(3)); boolean oin = m.queryPoint(p.multiply(a)); t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin); break; } case ITERATE_ADD: { for(int i=1; i<=3; i++) { Edge e = t.e(i); if (e.t1 != null && e.t1.tick >= this.tick) continue; if (e.t2 != null && e.t2.tick >= this.tick) continue; if (!e.locked()) continue; if ((e.t1==null || !e.t1.in) && (e.t2==null || !e.t2.in)) continue; Point p1 = e.v(1).multiply(a); Point p2 = e.v(2).multiply(a); Vertex v1=null, v2=null; v1 = m.vertex(p1); v2 = m.vertex(p2); if (v1==v2) continue; m.getEdge(v1, v2).lock(v1, 0); } if (check) checkAllDelaunay(); break; } } t.tick = this.tick; for(int i=1; i<=3; i++) { Triangle ti = t.t(i); if (ti == null) continue; if (ti.tick >= this.tick) continue; iter[numiter++] = ti; } } } public void checkAllDelaunay() { for(int i=0; i 80) System.out.println("clip in " + (100 * (seek/total)) + "%"); } // Imprecise Geometry ////////////////////////////////////////////////////////////////////////////// // (all of these can be off by a good margin and degrade only performance, not correctness) //////// //////////////////////////////////////////////////////////////////////////////////////////////////// private static class Imprecise { public static Point center(Mesh m, Point v1, Point v2, Point v3) { return m.point((float)((double)v1.x+(double)v2.x+(double)v3.x)/3, (float)(((double)v1.y+(double)v2.y+(double)v3.y)/3)); } public static boolean near(Point a, Point b) { return ddistance(a.x, a.y, b.x, b.y) <= epsilon; } public static boolean incircle(Point v1, Point v2, Point v3, Point p) { /* float a = 0; Q: for(int q=0; q<2; q++) { for(int i=0; i<3; i++) { if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q; Point t = v2; v2=v3; v3=v1; v1 = t; } Point t = v2; v2=v3; v3=t; } if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3); double a1 = (v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y); double a2 = (v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y); double ccx = (a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2; double ccy = (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2; double r2 = (v1.x-ccx)*(v1.x-ccx)+(v1.y-ccy)*(v1.y-ccy); double pd = (p.x-ccx)*(p.x-ccx)+(p.y-ccy)*(p.y-ccy); return r2 > pd; */ return Predicates.incircle(v1.x, v1.y, v2.x, v2.y, v3.x, v3.y, p.x, p.y)>0; } public static Point midpoint(Mesh m, Point a, Point b) { return m.point((a.x+b.x)/2,(a.y+b.y)/2); } private static double ddistance(double x1, double y1, double x2, double y2) { return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} public static float area(Point p1, Point p2, Point p3) { float x1 = p1.x; float x2 = p2.x; float x3 = p3.x; float y1 = p1.y; float y2 = p2.y; float y3 = p3.y; double a = ddistance(x1,y1,x2,y2); double b = ddistance(x2,y2,x3,y3); double c = ddistance(x3,y3,x1,y1); double s = (a+b+c)/2; double t = s*(s-a)*(s-b)*(s-c); if (t < 0) return 0; return (float)Math.sqrt(t); } public static Point intersect(Mesh m, Point v1, Point v2, Point v3, Point v4) { double a1 = v2.y-v1.y; double a2 = v4.y-v3.y; double b1 = v1.x-v2.x; double b2 = v3.x-v4.x; double c1 = -1 * (a1*v1.x+b1*v1.y); double c2 = -1 * (a2*v3.x+b2*v3.y); double x = (b2*c1-c2*b1)/(b1*a2-b2*a1); double y = (a2*c1-c2*a1)/(a1*b2-a2*b1); if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n "); return m.point((float)x,(float)y); } public static int side(Point p1, Point p2, Point p3) { /* int ret = 0; float x0 = p1.x; float x = p2.x; float x2 = p3.x; float y0 = p1.y; float y = p2.y; float y2 = p3.y; // this MUST be done to double precision double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2); if (c > 0) ret = b>=0 ? -1 : 1; else if (c < 0) ret = b>=0 ? 1 : -1; else ret = 0; return ret; */ return Predicates.side(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } } // Precise Geometry ///////////////////////////////////////////////////////////////////////////// static { Runtime.getRuntime().load(new java.io.File("Predicates.jnilib").getAbsolutePath()); } // Vertex ////////////////////////////////////////////////////////////////////////////// public static int state = 0; public Vertex vertex(Point p, Affine a) { return vertex(p.multiply(a)); } public Vertex vertex(Point p) { Vertex ret = null; switch(numvertices) { case 0: return (vertex0 = new Vertex(p)); case 1: return Imprecise.near(vertex0,p) ? vertex0 : (vertex1 = new Vertex(p)); case 2: { if (Imprecise.near(vertex0,p)) return vertex0; if (Imprecise.near(vertex1,p)) return vertex1; Vertex v2 = new Vertex(p); triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0)); return v2; } default: { Triangle t = null; t = triangle0.seek(p); for(int i=1; i<=3; i++) for(int j=1; j<=2; j++) if (t != null && Imprecise.near(t.e(i).v(j),p)) return t.e(i).v(j); // this will probably always need to be here since a vertex for which side()==0 could still // be slightly off to one side (and hence part of a neighboring "sliver" triangle. for(int k=1; k<=3; k++) for(int i=1; i<=3; i++) for(int j=1; j<=2; j++) if (t != null && t.t(k)!=null && Imprecise.near(t.t(k).e(i).v(j),p)) return t.t(k).e(i).v(j); for(int i=0; i= Math.min(p1.x,p2.x) && y <= Math.max(p1.y,p2.y) && y >= Math.min(p1.y,p2.y); } } private final class Vertex extends Point implements org.ibex.classgen.opt.Arena.Gladiator { public Vertex(Point p) { super(p); numvertices++; vertices.add(this); } } // Edge ////////////////////////////////////////////////////////////////////////////// public Edge newEdge(Vertex v1, Vertex v2) { return getEdge(v1,v2); /* if (v1==v2) throw new Error(); Edge ret = (Edge)edges.get(v1,v2); //if (ret != null) throw new Error("tried to get an edge that already exists!"); if (ret == null) ret = new Edge(v1,v2); return ret; */ } public Edge getEdge(Vertex v1, Vertex v2) { if (v1==v2) throw new Error(); Edge ret = (Edge)edges.get(v1,v2); if (ret != null) return ret; //Edge ret = null; Triangle t = null; if (triangle0 != null) { t = triangle0.seek(Imprecise.midpoint(this, v1,v2)); if (t != null) for(int i=1; i<=3; i++) if (t.e(i).hasVertex(v1) && t.e(i).hasVertex(v2)) ret = t.e(i); } if (ret == null) { ret = (Edge)edges.get(v1,v2); if (ret != null && (ret.t1 != null || ret.t2 != null)) throw new Error("bah! " + ret); } if (ret == null) ret = new Edge(v1,v2); return ret; } private final class Edge implements org.ibex.classgen.opt.Arena.Gladiator { private final Vertex v1; private final Vertex v2; Triangle t1 = null; Triangle t2 = null; private int locks = 0; private int weight = 0; public void delete() { if (t1!=null || t2!=null) throw new Error("tried to remove an edge before its triangles"); edges.put(v1,v2,null); edges.put(v2,v1,null); } public Vertex v(int i) { switch(i) { case 1: return v1; case 2: return v2; default: return null; } } public Edge rotate(Vertex v, boolean clockwise) { Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null; if (t==null) return null; for(int i=1; i<=3; i++) if (t.e(i)!=this && t.e(i).hasVertex(v)) return t.e(i); return null; } public Edge rotateHull(boolean clockwise) { if (t1!=null && t2!=null) throw new Error("nextHull() called on non-hull edge"); Vertex v = rotate(v1, !clockwise) == null ? v2 : v1; Edge e = rotate(v, !clockwise); while(!e.hasTriangle(null) && e!=this) e = e.rotate(v, !clockwise); if (e==this) throw new Error("confused"); return e; } public boolean isNear(Point p) { return Imprecise.area(v1,v2,p) <= epsilon2; } 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; } 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; } public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; } public int weight() { return weight; } public int weight(Vertex v) { return v==v1?weight:(-1*weight); } public boolean locked() { return locks > 0; } public boolean partitions(Point va, Point vb) { return side(va,vb)==-1; } public int side(Point a, Point b) { return side(a) * side(b); } public int side(Point a) { return Imprecise.side(v(1), v(2), a); } public boolean hasVertex(Vertex v) { return v1==v || v2==v; } public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; } public String toString() { return v(1) + "--" + v(2); } public void rmTriangle(Triangle t) { if (t1==t) t1 = null; else if (t2==t) t2 = null; else throw new Error(); if (t1==null && t2==null) delete(); } public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); } public boolean intersects(Point p) { return p.intersects(v1, v2); } public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); } public boolean intersects(Point va, Point vb) { return !Imprecise.near(v1,va) && !Imprecise.near(v1,vb) && !Imprecise.near(v2,va) && !Imprecise.near(v2,vb) && partitions(va, vb) && Imprecise.side(va, vb, v1) * Imprecise.side(va, vb, v2) == -1; } public Triangle opposingTriangle(Triangle t) { if (t1 == t) return t2; if (t2 == t) return t1; throw new Error(); } public void addTriangle(Triangle tnew) { if (t1==null) t1 = tnew; else if (t2==null) t2 = tnew; else throw new Error("attempted to addTriangle("+tnew+")\n t1="+t1+"\n t2="+t2); if (t1==t2) throw new Error("same triangle can't be both sides of an edge"); if (v1.x==v2.x) { boolean b = side(t1.opposingVertex(this)) == side(point(Float.MAX_VALUE, v1.y)); Triangle right = b ? t1 : t2; // right side Triangle left = b ? t2 : t1; // left side t1 = right; t2 = left; } else { boolean b = side(t1.opposingVertex(this)) == side(point(0, Float.MAX_VALUE)); Triangle top = b ? t1 : t2; Triangle bottom = b ? t2 : t1; if (v1.y==v2.y) { // horizontal t1 = bottom; t2 = top; } else if (v1.x > v2.x) { // positive slope t1 = top; t2 = bottom; } else { // negative slope t1 = bottom; t2 = top; } } } public void bisect(Vertex v) { if (v==this.v(1)) throw new Error("this should never happen"); if (v==this.v(2)) throw new Error("this should never happen"); 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; // is this possible? if (ton == t1) ton = null; // is this possible? if (opposingTriangleLeft == t) opposingTriangleLeft = null; // is this possible? if (opposingTriangleRight == t) opposingTriangleRight = null; // is this possible? t.delete(); } t1.delete(); Triangle ta, tb, tc=null, td=null; 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) { if (tov_v==left_v) throw new Error("barf"); if (tov_v==right_v) throw new Error("barf"); if (tov_v==left_tov) throw new Error("barf"); if (tov_v==right_tov) throw new Error("barf"); if (right_v==right_tov) throw new Error("barf"); if (left_v==left_tov) throw new Error("barf " + tov + " " + left); 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(); if (ta!=null) ta.check(); if (tb!=null) tb.check(); if (tc!=null) tc.check(); if (td!=null) td.check(); } 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(Imprecise.intersect(Mesh.this, 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; /* System.out.println("I think that " + this + " intersects:\n "+t); for(int i=1; i<=3; i++) System.out.println(" " + t.e(i) + ": " + t.e(i).intersects(this)); */ t = t.followVector(v2,v1); } t = told; told = null; continue; } } } if (t1!=null) t1.fixup(); if (t2!=null) t2.fixup(); } public boolean violated = false; public void stroke(PixelBuffer buf, Affine a, int color) { int c = violated ? 0xffff0000 : debug ? (weight() == 0 ? color : 0xffff0000) : (weight() != 0 ? color : 0); if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c); } public Edge(Vertex v1, Vertex v2) { boolean b = v1.y < v2.y || (v1.y==v2.y && v1.x < v2.x); this.v1 = b ? v1 : v2; this.v2 = b ? v2 : v1; edges.put(v1, v2, this); edges.put(v2, v1, this); } } // Triangle ////////////////////////////////////////////////////////////////////////////// public Triangle triangle(Edge e1, Edge e2, Edge e3) { if (e3.t1!=null && e3.t1.hasEdge(e2) && e3.t1.hasEdge(e1)) return e3.t1; if (e3.t2!=null && e3.t2.hasEdge(e2) && e3.t2.hasEdge(e1)) return e3.t2; if (e2.t1!=null && e2.t1.hasEdge(e2) && e2.t1.hasEdge(e1)) return e2.t1; if (e2.t2!=null && e2.t2.hasEdge(e2) && e2.t2.hasEdge(e1)) return e2.t2; if (e1.t1!=null && e1.t1.hasEdge(e2) && e1.t1.hasEdge(e1)) return e1.t1; if (e1.t2!=null && e1.t2.hasEdge(e2) && e1.t2.hasEdge(e1)) return e1.t2; Triangle t = new Triangle(e1, e2, e3); if (debug) t.check(); if (triangle0 == null) triangle0 = t; return t; } public static boolean fixing = false; public static int count = 0; private final class Triangle implements org.ibex.classgen.opt.Arena.Gladiator { //final double r2; //final Point cc; private Edge e1, e2, e3; // should be final =( private Vertex v1, v2, v3; public int tick; boolean in = false; boolean inWasSet = false; boolean painted = false; boolean dirty = true; //public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; } public Edge e(int i) { switch(i) { case 1: return e1; case 2: return e2; case 3: return e3; default: return null; } } //public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); } public Vertex v(int i) { switch(i) { case 1: return v1; case 2: return v2; case 3: return v3; default: return null; } } public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; } public Vertex closestVertex(Point p) { double d1 = Math.sqrt((v(1).x-p.x)*(v(1).x-p.x)+(v(1).y-p.y)*(v(1).y-p.y)); double d2 = Math.sqrt((v(2).x-p.x)*(v(2).x-p.x)+(v(2).y-p.y)*(v(2).y-p.y)); double d3 = Math.sqrt((v(3).x-p.x)*(v(3).x-p.x)+(v(3).y-p.y)*(v(3).y-p.y)); return (d1 < d2 && d1 < d3) ? v(1) : (d2 < d3) ? v(2) : v(3); } public boolean encounters(Point p1, Point p2) { for(int i=1; i<=3; i++) { if (Imprecise.near(v(i),p1)) return true; if (Imprecise.near(v(i),p2)) return true; if (v(i).intersects(p1,p2)) return true; if (e(i).intersects(p1,p2)) return true; } return contains(p1) || contains(p2); } 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; } 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; } public boolean intersects(Vertex va, Vertex vb){return e(1).intersects(va,vb)||e(2).intersects(va,vb)||e(3).intersects(va,vb);} public boolean intersects(Edge e){ return intersects(e.v(1),e.v(2)); } public boolean intersects(Point p){ return e(1).intersects(p) || e(2).intersects(p) || e(3).intersects(p); } public boolean hasEdge(Edge e) { return e.t1==this || e.t2==this; } 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)); } public boolean hasVertex(Vertex a) { return a==v(1) || a==v(2) || a==v(3); } public Vertex opposingVertex(Triangle t) { return t(3)==t ? v(3) : t(1)==t ? v(1) : t(2)==t ? v(2) : null; } public Vertex opposingVertex(Edge e) { return e==e(1) ? v(1) : e==e(2) ? v(2) : e==e(3) ? v(3) : null; } public Edge opposingEdge(Vertex v) { return v==v(1) ? e(1) : v==v(2) ? e(2) : v==v(3) ? e(3) : null; } public Triangle opposingTriangle(Vertex v) { return v(1)==v ? t(1) : v(2)==v ? t(2) : v(3)==v ? t(3) : null; } public String toString() { return "<<"+v(1)+""+v(2)+""+v(3)+">>"; } public void stroke(PixelBuffer buf, Affine a, int color) { for(int i=1; i<=3; i++) if (in || debug) e(i).stroke(buf, a, color); } public Triangle fixup() { if (!dirty) return this; dirty = false; for(int i=1; i<=3; i++) { Triangle t = t(i); if (t==null) continue; if (!t.cc(v(i))) continue; Edge e = e(i); if (e.locked()) { t.fixup(); continue; } return e.flip().t1.fixup(); } return this; } public void addHull(Vertex vnew) { Edge e = e(1).hasTriangle(null) ? e(1) : e(2).hasTriangle(null) ? e(2) : e(3).hasTriangle(null) ? e(3) : null; Triangle t = e.opposingTriangle(null), newt = null; while (!e.partitions(vnew, t.opposingVertex(e))) { e = e.rotateHull(true); t = e.opposingTriangle(null); } Edge ea = newEdge(e.v(1), vnew); Edge eb = newEdge(e.v(2), vnew); newt = triangle(e, ea, eb); if (ea.rotateHull(true) != eb) { Edge temp = ea; ea = eb; eb = temp; } for(int i=1; i<=2; i++) for(Edge ex = i==1?eb:ea; ;) { e = ex.rotateHull(i==1); t = e.opposingTriangle(null); if (!e.partitions(vnew, t.opposingVertex(e))) break; Edge ep = newEdge(vnew, e.unCommonVertex(ex)); newt = triangle(e, ex, ep); ex = ep; } if (newt==null) throw new Error("couldn't find a place to add a triangle for " + vnew); newt.fixup(); } public Triangle seek(Point p) { Triangle t = this; try { while (true) { count++; //System.out.println("seek " + t + " -> " + p + " / " + count); if (t.contains(p)) { state = -1; return t; } else if (t.intersects(p)) { state = 1; return t; } else if (t.e(3).intersects(p)) { state = 2; return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t; } else if (t.e(1).intersects(p)) { state = 3; return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t; } else if (t.e(2).intersects(p)) {state = 4; return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t; } else { // we "slingshot" back from the centroid in case we're inside of a "sliver" triangle //Point p0 = t.c(); //Triangle t2 = t.followVector(p0, p); Triangle t2 = t.followVector(t.closestVertex(p), p); if (t2==null || t2==t) { if (t.e(1).partitions(p, t.v(1)) && t.t(1)!=null) t = t.t(1); else if (t.e(2).partitions(p, t.v(2)) && t.t(2)!=null) t = t.t(2); else if (t.e(3).partitions(p, t.v(3)) && t.t(3)!=null) t = t.t(3); else { state = 5; return t; } } else { t = t2; } } } } finally { if (t!=null) triangle0 = t; } } // gives the triangle across the edge through which the ray v(1)-->v(2) exits this triangle public Triangle followVector(Point p1, Point p2) { Triangle ret = followVector2(p1, p2); if (ret==null) return ret; triangle0 = ret; if (!ret.encounters(p1,p2)) return this; return ret; } public Triangle followVector2(Point p1, Point p2) { if (contains(p2) || intersects(p2) || Imprecise.near(v(1),p2) || Imprecise.near(v(2),p2) || Imprecise.near(v(3),p2)) return this; for(int i=1; i<=3; i++) if (!Imprecise.near(v(i),p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2); Triangle t1 = t(1); Triangle t2 = t(2); Triangle t3 = t(3); for(int i=1; i<=3; i++) { int k1 = i==1?3:i==2?1:i==3?2:0; int k2 = i==1?2:i==2?3:i==3?1:0; int k3 = i==1?1:i==2?2:i==3?3:0; if (Imprecise.near(v(i),p1)) { if (e(k1).partitions(v(k1),p2)) return t(k1); if (e(k2).partitions(v(k2),p2)) return t(k2); if (e(k3).partitions(v(k3),p2)) return t(k3); throw new Error("bad!"); } } //if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2)) for(int i=1; i<=3; i++) if (e(i).intersects(p1,p2)) if (e(i).side(v(i)) * e(i).side(p2) == -1) return t(i); for(int i=1; i<=3; i++) if (e(i).partitions(p1,p2)) return t(i); for(int i=1; i<=3; i++) if (e(i).partitions(v(i),p2)) return t(i); for(int i=1; i<=3; i++) if (v(i).intersects(p1,p2)) throw new Error("bad news: \n "+p1+" -> "+p2+"\n " + this); System.out.println("slingshot from: " + p1 + " to " + p2 + " on " + this + "\n" + (e(1).side(v(1)) * e(1).side(p2))+" "+ (e(2).side(v(2)) * e(2).side(p2))+" "+ (e(3).side(v(3)) * e(3).side(p2)) ); /* return followVector(new Point(2*p1.x-p2.x, 2*p1.y-p2.y), p2); */ //throw new Error("giving up: \n "+p1+" -> "+p2+"\n " + this); final Point pp1 = p1; final Point pp2 = p2; new Frame() { public void paint(Graphics g) { g.setColor(java.awt.Color.white); g.fillRect(0, 0, getWidth(), getHeight()); g.setColor(java.awt.Color.black); g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(2).x+100, (int)v(2).y+100); g.drawLine((int)v(3).x+100, (int)v(3).y+100, (int)v(2).x+100, (int)v(2).y+100); g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(3).x+100, (int)v(3).y+100); g.setColor(java.awt.Color.red); g.drawLine((int)pp1.x+100, (int)pp1.y+100, (int)pp2.x+100, (int)pp2.y+100); } }.show(); try { Thread.sleep(100000); } catch (Exception e) { } return null; /* throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" + " p1=" + p1 + "\n" + " p2=" + p2 + "\n" + " t =" + this + " (area "+area(v(1)+100,v(2),v(3))+")\n"); */ } public void check() { if (e1==null && e2==null && e3==null) return; if (check) { for(int i=1; i<=3; i++) { if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent"); if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent"); if (e(i).t1 == e(i).t2) throw new Error("same triangle on both sides of edge"); } if (e(1)==e(2) || e(2)==e(3) || e(3)==e(1)) throw new Error("identical edges"); for(int i=1; i<=3; i++) { if (t(i) == null) continue; if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)"); if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark"); if (!e(i).hasTriangle(t(i))) throw new Error("blark2"); if (!e(i).hasTriangle(this)) throw new Error("blark3"); } for(int i=1; i<=3; i++) if (e(i).commonVertex(e(i==3?1:(i+1)))==null) throw new Error("edges have no common vertex"); // check that delauanay property is preserved } } public void checkDelaunay() { for(int i=1; i<=3; i++) { if (t(i) == null) continue; Vertex v = t(i).opposingVertex(e(i)); if (!e(i).locked() && /*Imprecise.incircle(v(1), v(2), v(3), v)*/cc(v) /*&& !dirty && !t(i).dirty*/) { //throw new Error("Delaunay violation: vertex " + v + "\n triangle: " + this); //System.out.println("violation: " + e(i)); e(i).violated = true; } else { e(i).violated = false; } } } public void trisect(Vertex v) { if (!contains(v)) throw new Error("trisect(v) but I don't contain v = " + v); if (hasVertex(v)) throw new Error("attempt to trisect a triangle at one of its own vertices"); for(int i=3; i>0; i--) if (e(i).intersects(v)/* || e(i).isNear(v)*/) { e(i).bisect(v); return; } Triangle a=null,b=null,c=null; boolean oldIn = in; Edge v1v = newEdge(v(1), v); Edge v2v = newEdge(v(2), v); Edge v3v = newEdge(v(3), v); Edge e1 = this.e(1); Edge e2 = this.e(2); Edge e3 = this.e(3); delete(); a = triangle(e3, v1v, v2v); b = triangle(e2, v1v, v3v); c = triangle(e1, v3v, v2v); a.in = oldIn; b.in = oldIn; c.in = oldIn; a.fixup(); a.check(); b.check(); c.check(); } public void setIn(boolean evenOdd, int weight) { if (inWasSet) return; inWasSet = true; in = (evenOdd && weight%2!=0) || (!evenOdd && weight!=0); for(int i=1; i<=3; i++) if (t(i) != null) t(i).setIn(evenOdd, weight + e(i).weight()); } public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) { if (painted) return; painted = true; 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); for(int i=1; i<=3; i++) if (t(i) != null) { boolean prepaint = t(i).painted; //if (debug) e(i).stroke(buf, a, color); t(i).fill(buf, a, clip, color, strokeOnly); } } public Triangle(Edge e1, Edge e2, Edge e3) { this.e1 = e1; this.e2 = e2; this.e3 = e3; /*Vertex*/ this.v1 = e(2).unCommonVertex(e(1)); /*Vertex*/ this.v2 = e(3).unCommonVertex(e(2)); /*Vertex*/ this.v3 = e(1).unCommonVertex(e(3)); if (e(1).intersects(v1)) throw new Error("triangle points are colinear"); if (e(2).intersects(v2)) throw new Error("triangle points are colinear"); if (e(3).intersects(v3)) throw new Error("triangle points are colinear"); e(1).addTriangle(this); e(2).addTriangle(this); e(3).addTriangle(this); triangles.add(this); } public boolean cc(Point p) { /* Vertex v1 = e(2).unCommonVertex(e(1)); Vertex v2 = e(3).unCommonVertex(e(2)); Vertex v3 = e(1).unCommonVertex(e(3)); */ return Imprecise.incircle(v1, v2, v3, p); } public void clear() { if (!painted) return; painted = false; if (t(3) != null) t(3).clear(); if (t(1) != null) t(1).clear(); if (t(2) != null) t(2).clear(); } public void delete() { if (triangle0 == this) { if (t(1) != null) triangle0 = t(1); else if (t(2) != null) triangle0 = t(2); else if (t(3) != null) triangle0 = t(3); else triangle0 = null; } triangles.remove(this); e(1).rmTriangle(this); e(2).rmTriangle(this); e(3).rmTriangle(this); e1 = null; e2 = null; e3 = null; } } // Queries ///////////////////////////////////////////////////////////////////////////////// public boolean queryPoint(Point p) { if (triangle0==null) return false; Triangle ret = triangle0.seek(p); return (ret.contains(p) || ret.intersects(p)) && ret.in; } // Drawing ////////////////////////////////////////////////////////////////////////////// public void setIn(boolean evenOdd) { iterateTriangles(ITERATE_CLEAR_WASSET, null, null); triangle0.setIn(evenOdd, 1); } public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) { if (triangle0==null) return; iterateTriangles(ITERATE_CLEAR, null, null); triangle0.fill(buf, a, clip, color, strokeOnly); } public void stroke(PixelBuffer buf, Affine a, int color) { if (triangle0==null) return; iterateTriangles(ITERATE_STROKE, null, a, buf, color); } public void newcontour() { if (start != null) add(start.x, start.y); start = null; last = null; } public Mesh addRect(float x, float y, float w, float h) { if (w==0 || h==0) return this; Vertex v1 = vertex(point(x,y)); Vertex v2 = vertex(point(x+w,y)); Vertex v3 = vertex(point(x+w,y+h)); Vertex v4 = vertex(point(x,y+h)); newEdge(v1,v2).lock(v1,1); newEdge(v2,v3).lock(v2,1); newEdge(v3,v4).lock(v3,1); newEdge(v4,v1).lock(v4,1); setIn(true); return this; } public void add(float x, float y) { Vertex vx = vertex(point(x,y)); if (vx==last) return; if (start==null) start = vx; try { if (last==null) return; if (numvertices<3) return; if (numvertices==3) getEdge(start, last).lock(start,1); getEdge(last,vx).lock(last,1); } finally { last = vx; } if (check) checkAllDelaunay(); } }