* trigger a Surface.abort; if rendering were done in the same pass,
* rendering work done prior to the Surface.abort would be wasted.
*/
-public final class Box extends JS.Obj implements Callable {
+public final class Box extends JS.Obj implements Callable, Mesh.Chain {
+
+ public Mesh.Chain getMeshChainParent() { return parent; }
+ public Mesh getMesh() { return mesh; }
+ public Affine getAffine() { return transform; }
// Macros //////////////////////////////////////////////////////////////////////
private int strokecolor = 0xFF000000;
public float flex = 1;
private Path path = null;
+ private Path clippath = null;
private Affine transform = Affine.identity();
// FEATURE: polygon caching
- private Polygon polygon = null;
+ private Mesh polygon = null;
private Mesh mesh = null;
// specified directly by user
transform.f = 0;
a = a.copy().premultiply(transform);
- boolean relevant = packed() || ((fillcolor&0xff000000)!=0x0) || path!=null;
+ //boolean relevant = packed() || ((fillcolor&0xff000000)!=0x0) || path!=null;
+ boolean relevant = true;
int save_xmin = xmin, save_ymin = ymin, save_xmax = xmax, save_ymax = ymax;
if (!relevant) {
for(Box child = getChild(0); child != null; child = child.nextSibling()) {
private static final boolean OPTIMIZE = false;
/** Renders self and children within the specified region. All rendering operations are clipped to xIn,yIn,wIn,hIn */
- public void render(PixelBuffer buf, Affine a) {
+ public void render(PixelBuffer buf, Affine a, Mesh clipFrom) { render(buf, a, clipFrom, Affine.identity()); }
+ public void render(PixelBuffer buf, Affine a, Mesh clipFrom, Affine clipa) {
if (!test(VISIBLE)) return;
- a = a.copy().premultiply(transform);
-
- // FIXME: clipping
- if (path == null) {
- if (((fillcolor & 0xFF000000) != 0x00000000 || parent == null) && (text==null||"".equals(text))) {
- if (OPTIMIZE && a.doesNotRotate()) {
- int x = (int)a.multiply_px(0, 0);
- int y = (int)a.multiply_py(0, 0);
- int x2 = (int)a.multiply_px(contentwidth, contentheight);
- int y2 = (int)a.multiply_py(contentwidth, contentheight);
- buf.fillTrapezoid(x, x, y, x2, x2, y2, (fillcolor & 0xFF000000) == 0 ? 0xffffffff : fillcolor);
- } else {
- new Polygon().addrect(0, 0, contentwidth, contentheight, a).fill(buf, new Paint.SingleColorPaint(fillcolor));
- }
+ a = a.copy().multiply(transform);
+ clipa = clipa.copy().multiply(transform);
+
+ if (mesh == null)
+ if (path != null) mesh = new Mesh(path, true);
+ else {
+ if (((fillcolor & 0xFF000000) != 0x00000000 || parent == null) && (text==null||"".equals(text)))
+ mesh = new Mesh().addRect(0, 0, contentwidth, contentheight);
+ // long ret = font.rasterizeGlyphs(text, buf, a, null, 0x777777, 0);
+ // minwidth = maxwidth = font.textwidth(text);
+ // minheight = maxheight = font.textwidth(text);
+ // if (ret == 0) Platform.Scheduler.add(this);
+ // FIXME: texture
}
- if (text != null) {
- long ret = font.rasterizeGlyphs(text, buf, a, null, 0x777777, 0);
- minwidth = maxwidth = font.textwidth(text);
- minheight = maxheight = font.textwidth(text);
- if (ret == 0) Platform.Scheduler.add(this);
- }
- // FIXME: texture
- } else {
- if (mesh == null) {
- Log.warn(this, "generating mesh...");
- mesh = new Mesh(new Polygon(path, Affine.identity()));
- Log.warn(this, " done generating mesh.");
- }
- mesh.fill(buf, a, fillcolor, true, false);
- mesh.stroke(buf, a, strokecolor);
- //mesh.fill(buf, a, fillcolor, true, true);
+ if (mesh==null) {
+ for(Box b = getChild(0); b != null; b = b.nextSibling()) b.render(buf, a, clipFrom, clipa);
+ return;
}
- for(Box b = getChild(0); b != null; b = b.nextSibling()) b.render(buf, a);
+ if (clipFrom != null) clipFrom.subtract(mesh, clipa);
+ Mesh mesh = treeSize() > 0 ? this.mesh.copy() : this.mesh;
+ for(Box b = getChild(0); b != null; b = b.nextSibling()) b.render(buf, a, mesh, Affine.identity());
+ mesh.fill(buf, a, null, fillcolor, true);
}
-
// Methods to implement org.ibex.js.JS //////////////////////////////////////
public JS call(JS method, JS[] args) throws JSExn {
case "hshrink": CHECKSET_FLAG(HSHRINK); RECONSTRAIN();
case "vshrink": CHECKSET_FLAG(VSHRINK); RECONSTRAIN();
case "path": {
+ mesh = null;
path = new Path(JSU.toString(value));
float tx = -1 * Encode.longToFloat2(path.horizontalBounds(Affine.identity()));
float ty = -1 * Encode.longToFloat2(path.verticalBounds(Affine.identity()));
dirty();
polygon = null;
}
+ case "clippath": {
+ clippath = new Path(JSU.toString(value));
+ //float tx = -1 * Encode.longToFloat2(clippath.horizontalBounds(Affine.identity()));
+ //float ty = -1 * Encode.longToFloat2(clippath.verticalBounds(Affine.identity()));
+ //clippath.transform(Affine.translate(tx, ty), true);
+ REPLACE();
+ RECONSTRAIN();
+ dirty();
+ polygon = null;
+ }
case "transform": {
transform = Affine.parse(JSU.toString(value));
transform.e = 0;
transform.f = 0;
- if (getSurface() != null) getSurface().dirty(0, 0, 500, 500); // FIXME
+ if (getSurface() != null) // FIXME
+ getSurface().dirty(0, 0, getSurface().root.contentwidth, getSurface().root.contentheight);
REPLACE();
RECONSTRAIN(); dirty(); polygon = null;
}
import java.util.collections.*;
import org.ibex.util.*;
+// TODO:
+// - allow edge-constraint removal
+//
+// ~30% of our time spent finding vertices => use a balanced quadtree
+//
+// - 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()
+// - subtract()
+// - [??] preserve in/out-ness every time we delete() a triangle
+
/**
- * An incremental, adaptive, constrained Delaunay Triangulation.
- * @see Kallmann, Bieri, and Thalmann: Fully Dynamic Constrained Delaunay Triangulations
+ * An incremental, adaptive, addWeighted Delaunay Triangulation.
+ * @see Kallmann, Bieri, and Thalmann: Fully Dynamic AddWeighted Delaunay Triangulations
*/
public final class Mesh {
- //#define Vertex int
-
- private static final float epsilon = (float)0.001;
+ private static final float epsilon = (float)0.0001;
+ private static final float epsilon2 = (float)0.001;
private static final boolean debug = false;
- private Vector triangles = new Vector();
-
- public static float B = (float)5.0;
- public static float Q = (float)0.4;
+ private Vector triangles = new Vector();
+ private Hash edges = new Hash();
+ 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<edges.length; i++) {
+ Edge e = (Edge)edges[i];
+ Vertex mv1 = m.vertex(e.v(1));
+ Vertex mv2 = m.vertex(e.v(2));
+ Edge me = m.getEdge(mv1, mv2);
+ if (e.locked()) {
+ me.lock(mv1, 0);
+ me.weight = e.weight;
+ }
+ }
+ m.setIn(true);
+ return m;
+ }
- public static Hashtable nexter = new Hashtable();
- public static LinkedList next(Vertex v) {
- LinkedList hs = (LinkedList)nexter.get(new Integer(v));
- if (hs == null) nexter.put(new Integer(v), hs = new LinkedList());
- return hs;
+ public void reset() {
+ triangles.setSize(0);
+ start = null;
+ last = null;
}
- // Vertices //////////////////////////////////////////////////////////////////////////////
-
- public Vertex v(float x, float y) {
- if (numvertices >= this.x.length-1) {
- if (debug) Log.debug(Mesh.class, "expanding vertex arrays from " + this.x.length + " to " + this.x.length*2);
- float[] newx = new float[this.x.length * 2];
- float[] newy = new float[this.y.length * 2];
- System.arraycopy(this.x, 0, newx, 0, this.x.length);
- System.arraycopy(this.y, 0, newy, 0, this.y.length);
- this.x = newx;
- this.y = newy;
- }
- this.x[numvertices] = x;
- this.y[numvertices] = y;
- return numvertices++;
+ // Chain //////////////////////////////////////////////////////////////////////////////
+
+ public static interface Chain {
+ public Mesh.Chain getMeshChainParent();
+ public Affine getAffine();
+ public Mesh getMesh();
}
- public int numvertices = 0;
- public float x[] = new float[255];
- public float y[] = new float[255];
- public String s(Vertex v) { return "("+x(v)+","+y(v)+")"; }
- public float x(Vertex v) { return x[v]; }
- public float y(Vertex v) { return y[v]; }
-
- public static final Vertex NULLVERTEX = -1;
-
- public Vertex newVertex(float x, float y) {
- Vertex ret = NULLVERTEX;
- for(int k=0; k<numvertices; k++) {
- Vertex v = k;
- if (distance(v,x,y)<epsilon) if (ret==NULLVERTEX || distance(v,x,y) < distance(ret,x,y)) ret = v;
- }
- if (ret != NULLVERTEX) return ret;
- Vector vec = new Vector();
- boolean interior = false;
- int edges = 0;
- Vertex v = v(x,y);
- if (numvertices<=2) return v;
- if (numvertices==3) { newTriangle(0, 1, 2, "first three points"); return v; }
- for(int i=0; i<triangles.size(); i++) {
- Triangle t = (Triangle)triangles.elementAt(i);
- if (t.contains(v)) {
- Triangle t12 = t.t12;
- Triangle t23 = t.t23;
- Triangle t31 = t.t31;
- t.delete();
- vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
- vec.addElement(newTriangle(v, t.v3, t.v2, "vertexinsertion " + v));
- vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
- //#repeat t23/t31/t12 v1/v2/v3 v2/v3/v1 v3/v1/v2
- } else if (t.t23 != null && isect(t.v2, t.v3, v)) {
- Triangle tt = t.t23;
- Vertex va = tt.opposingVertex(t);
- tt.delete();
- t.delete();
- vec.addElement(newTriangle(v, t.v1, t.v3, "vertexinsertion " + v));
- vec.addElement(newTriangle(v, t.v1, t.v2, "vertexinsertion " + v));
- vec.addElement(newTriangle(v, t.v3, va , "vertexinsertion " + v));
- vec.addElement(newTriangle(v, t.v2, va , "vertexinsertion " + v));
- //#end
- } else {
- continue;
- }
- fixup(vec, v);
- return v;
- }
- boolean good = false;
- while(true) {
- for(int j=0; j<triangles.size(); j++) {
- Triangle t = (Triangle)triangles.elementAt(j);
- if (t.v1==v || t.v2==v || t.v3==v) continue;
- //#repeat t12/t23/t31 v3/v1/v2 v2/v3/v1 v1/v2/v3
- if (t.t12==null) {
- boolean bad = false;
- for(int k=0; k<triangles.size(); k++) {
- Triangle tt = (Triangle)triangles.elementAt(k);
- if (tt.intersectsSegment(v, t.v1)) { bad = true; break; }
- if (tt.intersectsSegment(v, t.v2)) { bad = true; break; }
+
+ // Constructor //////////////////////////////////////////////////////////////////////////////
+
+ public Mesh() { }
+ public Mesh(Path p, boolean evenOdd) { p.addTo(this, evenOdd); }
+
+ public void subtract(Mesh m, Affine a) { clipOp(m,a,true); }
+ public void intersect(Mesh m, Affine a) { clipOp(m,a,false); }
+ public void add(Mesh m, Affine a) { iterateTriangles(ITERATE_ADD, m, a); }
+ public static long seekTime = 0;
+
+ public static final int ITERATE_SUBTRACT = 1;
+ public static final int ITERATE_INTERSECT = 2;
+ public static final int ITERATE_ADD = 3;
+ int tick = 0;
+ Triangle[] iter = new Triangle[100];
+
+ private void iterateTriangles(int mode, Mesh m, Affine a) {
+ tick++;
+ int numiter = 0;
+ if (iter.length < triangles.size()) iter = new Triangle[triangles.size()];
+ iter[numiter++] = triangle0;
+ while(numiter > 0) {
+ Triangle t = iter[--numiter];
+ if (t.tick >= this.tick) continue;
+ switch(mode) {
+ case ITERATE_INTERSECT:
+ case ITERATE_SUBTRACT: {
+ if (!t.in) break;
+ boolean oin = m.queryPoint(t.c().multiply(a));
+ t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin);
+ break;
}
- if (!bad) {
- vec.addElement(newTriangle(v,t.v1,t.v2, "hull expansion"));
- good = true;
+ 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);
}
+ break;
}
- //#end
}
- 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;
+ }
}
- if (!good) throw new Error("couldn't figure out where to put " + s(v));
- fixup(vec, v);
- return v;
}
- public void fixup(Vector vec, Vertex v) {
- while(vec.size() > 0) {
- Triangle t = (Triangle)vec.lastElement();
- vec.setSize(vec.size() - 1);
- if (t.deleted) continue;
- //if (t.wind(t.nextVertex(v), t.prevVertex(v)) != 0) continue; // FIXME
- Triangle to = t.opposingTriangle(v);
- if (to==null) continue; //throw new Error("fixup invoked with a triangle which does not have me as a vertex");
- if (to.deleted) throw new Error("v should not happen");
- if (to.r < distance(v,to.ccx, to.ccy)) continue;
- Vertex v2 = to.opposingVertex(t);
- t.delete();
- to.delete();
- vec.addElement(newTriangle(v, t.nextVertex(v), v2, "fixup"));
- vec.addElement(newTriangle(v, t.prevVertex(v), v2, "fixup"));
- }
+ public void clipOp(Mesh m, Affine a, boolean subtract) {
+ seekTime = 0;
+ long start = System.currentTimeMillis();
+ m.add(this, a);
+ iterateTriangles(subtract ? ITERATE_SUBTRACT : ITERATE_INTERSECT, m, a.inverse());
+ float total = (float)((System.currentTimeMillis() - start));
+ float seek = (float)seekTime;
+ if (total > 80) System.out.println("clip in " + (100 * (seek/total)) + "%");
}
- // Static //////////////////////////////////////////////////////////////////////////////
-
- public Triangle newTriangle(Vertex v1, Vertex v2, Vertex v3, String source) {
- if (v1==v2 || v2==v3 || v3==v1) throw new Error("identical vertices");
- for(int i=0; i<triangles.size(); i++) {
- Triangle t = (Triangle)triangles.elementAt(i);
- if (t.v1==v1&&t.v2==v2&&t.v3==v3) return t;
- if (t.v1==v1&&t.v2==v3&&t.v3==v2) return t;
- if (t.v1==v2&&t.v2==v3&&t.v3==v1) return t;
- if (t.v1==v2&&t.v2==v1&&t.v3==v3) return t;
- if (t.v1==v3&&t.v2==v1&&t.v3==v2) return t;
- if (t.v1==v3&&t.v2==v2&&t.v3==v1) return t;
- }
- Triangle t = new Triangle(source, v1, v2, v3, false, false);
- if (debug) checktri();
- return t;
+ // Geometry //////////////////////////////////////////////////////////////////////////////
+
+ public 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 void checktri() {
- for(int i=0; i<triangles.size(); i++) {
- Triangle t = (Triangle)triangles.elementAt(i);
- if (t.t12 != null && (t.t12.t12 != t && t.t12.t23 != t && t.t12.t31 != t)) throw new Error("t12");
- if (t.t23 != null && (t.t23.t12 != t && t.t23.t23 != t && t.t23.t31 != t)) throw new Error("t23");
- if (t.t31 != null && (t.t31.t12 != t && t.t31.t23 != t && t.t31.t31 != t)) throw new Error("t31");
- for(int j=0; j<triangles.size(); j++) {
- Triangle t2 = (Triangle)triangles.elementAt(j);
- if (t2==t) continue;
- if (t.v1==t2.v1&&t.v2==t2.v2&&t.v3==t2.v3) throw new Error("poo");
- if (t.v1==t2.v1&&t.v2==t2.v3&&t.v3==t2.v2) throw new Error("poo");
- if (t.v1==t2.v2&&t.v2==t2.v3&&t.v3==t2.v1) throw new Error("poo");
- if (t.v1==t2.v2&&t.v2==t2.v1&&t.v3==t2.v3) throw new Error("poo");
- if (t.v1==t2.v3&&t.v2==t2.v1&&t.v3==t2.v2) throw new Error("poo");
- if (t.v1==t2.v3&&t.v2==t2.v2&&t.v3==t2.v1) throw new Error("poo");
- }
- }
+ public Point intersect(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 point((float)x,(float)y);
}
- // Vertex //////////////////////////////////////////////////////////////////////////////
+ public static int side(Point p1, Point p2, Point p3) {
+ 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) return b>=0 ? -1 : 1;
+ if (c < 0) return b>=0 ? 1 : -1;
+ return 0;
+ }
- public boolean triangulate(Vertex vv, HashSet orphans, Vertex v, boolean first) {
- if (first) {
- HashSet left = new HashSet();
- HashSet right = new HashSet();
- for(Iterator it=orphans.iterator(); it.hasNext();) {
- Vertex o = ((Integer)it.next()).intValue();
- if (o==v||o==vv) continue;
- if (side(vv, v, o) == -1) left.add(new Integer(o));
- else if (side(vv, v, o) == 1) right.add(new Integer(o));
- else throw new Error("impossible "+vv+" "+v + " " + o);
- }
- triangulate(vv, left, v, false);
- triangulate(v, right, vv, false);
- return false;
- }
- Vertex farthest = NULLVERTEX;
- float dist = 0;
- if (orphans.size()==0) return true;
- Vertex o = ((Integer)orphans.iterator().next()).intValue();
- if (orphans.size()==1) {
- Triangle t = newTriangle(vv, v, o, "triangulate2 " + v + " " + vv);
- if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
- if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
- if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
- return false;
- }
+ // Vertex //////////////////////////////////////////////////////////////////////////////
- Vertex best = NULLVERTEX;
- OUTER: for(Iterator it=orphans.iterator(); it.hasNext();) {
- o = ((Integer)it.next()).intValue();
- if (o==v) continue;
- Triangle t = new Triangle("temp", vv, v, o, true);
- for(Iterator it2=orphans.iterator(); it2.hasNext();) {
- Vertex z = ((Integer)it2.next()).intValue();
- if (z==o) continue;
- if (z==v) continue;
- if (z==vv) continue;
- if (distance(z,t.ccx,t.ccy) < t.r || t.contains(z)) continue OUTER;
- }
- if (best==NULLVERTEX || new Triangle("temp",vv,v,best,true).area() > new Triangle("temp",vv,v,o,true).area())
- best = o;
- }
- if (best==NULLVERTEX) throw new Error("notgood, #orphans = " + orphans.size());
- o = best;
- HashSet left = new HashSet();
- HashSet right = new HashSet();
- for(Iterator it2=orphans.iterator(); it2.hasNext();) {
- Vertex x = ((Integer)it2.next()).intValue();
- if (o==x||vv==x||v==x) continue;
- int side_of_x = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,x);
- int side_of_v = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,v);
- int side_of_vv = side(o,(x(vv)+x(v))/2,(y(vv)+y(v))/2,vv);
- if (side_of_x==side_of_vv && side_of_vv!=0) right.add(new Integer(x));
- else if (side_of_x==side_of_v && side_of_v!=0) left.add(new Integer(x));
- else throw new Error("impossible "+vv+" "+v + " " + o + " ==> " + x);
+ 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 vertex0.distance(p)<=epsilon ? vertex0 : (vertex1 = new Vertex(p));
+ case 2: {
+ if (vertex0.distance(p)<=epsilon) return vertex0;
+ if (vertex1.distance(p)<=epsilon) return vertex1;
+ Vertex v2 = new Vertex(p);
+ triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0));
+ return v2;
}
- boolean doit = true;
- doit &= triangulate(o, left, v, false);
- doit &= triangulate(o, right, vv, false);
- if (doit) {
- Triangle t = newTriangle(v, vv, o,"triangulate 0/0");
- if (((t.v1==vv && t.v2==v)||(t.v1==v && t.v2==vv)) && t.t12==null) return true;
- if (((t.v3==vv && t.v2==v)||(t.v3==v && t.v2==vv)) && t.t23==null) return true;
- if (((t.v1==vv && t.v3==v)||(t.v1==v && t.v3==vv)) && t.t31==null) return true;
- return false;
+ 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 && t.e(i).v(j).distance(p)<=epsilon) return t.e(i).v(j);
+ Vertex v = new Vertex(p);
+ if (t.e(3).intersects(p)) t.e(3).bisect(v);
+ else if (t.e(1).intersects(p)) t.e(1).bisect(v);
+ else if (t.e(2).intersects(p)) t.e(2).bisect(v);
+ else if (t.contains(v)) t.trisect(v);
+ else t.addHull(v);
+ return v;
}
- return true;
}
+ }
- public void force() {
- while(true) {
- boolean redo = false;
- for(int k=0; k<numvertices; k++) {
- Vertex v = k;
- redo |= force(v);
- }
- if (!redo) break;
+ private Point point(float x, float y) { return new Point(x,y); }
+ private Point point(Point p, Affine a) { return point(p.x(a), p.y(a)); }
+ private class Point {
+ public float x;
+ public float y;
+ public String toString() { return "("+x+","+y+")"; }
+ public Point multiply(Affine a) { return point(x(a),y(a)); }
+ public Point(float x, float y) { this.x = x; this.y = y; }
+ public Point(Point p) { this(p.x,p.y); }
+ public boolean equals(float x, float y) { return distance(x,y) <= epsilon; }
+ public boolean equals(Object o) { return (!(o instanceof Point)) ? false : ((Point)o).distance(this) <= epsilon; }
+ public float distance(Point v) { return distance(v.x,v.y); }
+ private float distance(float x, float y) { return (float)Math.sqrt(distance2(x, y)); }
+ public float distance2(Point v) { return distance2(v.x, v.y); }
+ private float distance2(float x, float y) { return (this.x-x)*(this.x-x)+(this.y-y)*(this.y-y); }
+ public float x(Affine a) { return a.multiply_px(x,y); }
+ public float y(Affine a) { return a.multiply_py(x,y); }
+ public int xi(Affine a) { return (int)x(a); }
+ public int yi(Affine a) { return (int)y(a); }
+ public boolean intersects(Point p1, Point p2) {
+ return
+ Mesh.side(p1,p2,this)==0 &&
+ x <= Math.max(p1.x,p2.x) &&
+ x >= Math.min(p1.x,p2.x) &&
+ y <= Math.max(p1.y,p2.y) &&
+ y >= Math.min(p1.y,p2.y);
}
}
- public boolean force(Vertex vv) {
- boolean ret = false;
- OUTER: for(Iterator it=next(vv).iterator(); it.hasNext();) {
- Vertex v = ((Integer)it.next()).intValue();
- for(int k=0; k<numvertices; k++) {
- Vertex v2 = k;
- if (v2==vv||v2==v) continue;
- //if (next(vv).contains(v2) || next(v2).contains(vv)) continue;
- if (isect(v,vv,v2)) {
- if (debug) Log.debug(Mesh.class,"breaking line " + vv+"-"+v + " at vertex " + v2);
- next(vv).remove(new Integer(v));
- next(vv).add(new Integer(v2));
- next(v2).add(new Integer(v));
- ret = true;
- break OUTER;
- }
- }
- boolean good = false;
- for (int i=0; i<triangles.size(); i++)
- if (((Triangle)triangles.elementAt(i)).hasEdge(vv,v)) { good = true; break; }
- if (good) continue;
- HashSet orphans = new HashSet();
- for (int i=0; i<triangles.size(); i++) {
- Triangle t = ((Triangle)triangles.elementAt(i));
- if (t.deleted) continue;
- if (t.intersectsSegment(vv, v)) {
- if (debug) Log.debug(Mesh.class,"removing triangle " + t + " because it intersects segment " + vv+"-"+v);
- Vector vec = new Vector();
- orphans.add(new Integer(t.v1));
- orphans.add(new Integer(t.v2));
- orphans.add(new Integer(t.v3));
- orphans.remove(new Integer(v));
- orphans.remove(new Integer(vv));
- t.delete();
- i--;
- ret = true;
- }
- }
- orphans.remove(new Integer(vv));
- orphans.remove(new Integer(v));
- triangulate(vv, orphans, v, true);
- break;
- }
+
+ private final class Vertex extends Point implements org.ibex.arenaj.Gladiator {
+ public Vertex(Point p) { super(p); numvertices++; }
+ }
+
+ // Edge //////////////////////////////////////////////////////////////////////////////
+
+ public Edge newEdge(Vertex v1, Vertex v2) {
+ if (v1==v2) throw new Error();
+ Edge ret = (Edge)edges.get(v1,v2);
+ 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) ret = new Edge(v1,v2);
return ret;
}
- public void makeNonDegenerate() {
- while(true) {
- boolean redo = false;
- for(int k=0; k<numvertices; k++) {
- Vector vec = new Vector();
- Vertex vx = k;
- redo |= makeNonDegenerate(vec, vx);
+ private final class Edge implements org.ibex.arenaj.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) { return i==1?v1:i==2?v2: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 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 Mesh.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(); }
+ public boolean convex() { return this.intersects(t1.opposingVertex(t2), t2.opposingVertex(t1)); }
+
+ public boolean colinear(Point v) { return area(v,v1,v2)<=epsilon; }
+
+ public boolean intersects(Point p) {
+ return
+ side(p)==0 &&
+ p.x <= Math.max(v1.x,v2.x) &&
+ p.x >= Math.min(v1.x,v2.x) &&
+ p.y <= Math.max(v1.y,v2.y) &&
+ p.y >= Math.min(v1.y,v2.y);
+ }
+ public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); }
+ public boolean intersects(Point va, Point vb) {
+ return
+ !v1.equals(va) &&
+ !v1.equals(vb) &&
+ !v2.equals(va) &&
+ !v2.equals(vb) &&
+ partitions(va, vb) &&
+ Mesh.side(va, vb, v1) * Mesh.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;
+ }
}
- if (!redo) break;
}
- }
- 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;
}
}
}
+ if (t1!=null) t1.fixup();
+ if (t2!=null) t2.fixup();
+ }
+
+ public void stroke(PixelBuffer buf, Affine a, int color) {
+ int c = 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);
}
- return false;
}
// Triangle //////////////////////////////////////////////////////////////////////////////
- private final class Triangle {
- Triangle t12=null, t23=null, t31=null;
- final Vertex v1, v2, v3;
+ public Triangle triangle(Edge e1, Edge e2, Edge e3) {
+ 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;
+ 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;
+ Point p = point(x,y);
+ Triangle t = triangle0==null ? null : triangle0.seek(p);
+ if (t != null &&
+ (t.contains(p) || t.intersects(p)) &&
+ t.hasEdge(e1) &&
+ t.hasEdge(e2) &&
+ t.hasEdge(e3))
+ return triangle0 = t;
+ t = new Triangle(e1, e2, e3);
+ if (debug) t.check();
+ if (triangle0 == null) triangle0 = t;
+ return t;
+ }
+
+ public static boolean fixing = false;
+ private final class Triangle implements org.ibex.arenaj.Gladiator {
+
+ final float r2;
+ final Point cc;
+
+ private Edge e1, e2, e3; // should be final =(
+ public int tick;
+
boolean in = false;
- boolean deleted = false;
+ boolean inWasSet = false;
boolean painted = false;
- boolean special = false;
- final String source;
- final float ccx, ccy, r;
-
- public boolean hasEdge(Vertex a, Vertex b) { return a!=b && (a==v1||a==v2||a==v3) && (b==v1||b==v2||b==v3); }
- public Vertex opposingVertex(Triangle t) { return t12==t ? v3 : t23==t ? v1 : t31==t ? v2 : NULLVERTEX; }
- public Triangle opposingTriangle(Vertex v) { return v1==v ? t23 : v2==v ? t31 : v3==v ? t12 : null; }
- public Vertex nextVertex(Vertex v) { return v1==v ? v2 : v2==v ? v3 : v3==v ? v1 : NULLVERTEX; }
- public Vertex prevVertex(Vertex v) { return v1==v ? v3 : v2==v ? v1 : v3==v ? v2 : NULLVERTEX; }
- public String toString() { return "<<"+v1+""+v2+""+v3+">>"; }
- public boolean intersectsSegment(Vertex a, Vertex b) { return isect(v1,v2,a,b) || isect(v3,v2,a,b) || isect(v1,v3,a,b); }
- public float area() {
- float a = distance(v1,v2);
- float b = distance(v2,v3);
- float c = distance(v3,v1);
- float s = (a+b+c)/2;
- return (float)Math.sqrt(s*(s-a)*(s-b)*(s-c));
- }
-
- public boolean checkSkinny() {
- if (!(r / Math.min(Math.min(distance(v1,v2), distance(v2,v3)), distance(v3,v1)) > B)) return false;
- if (debug) Log.debug(this,"skinny triangle " + this);
- for (Vertex v=0; v<numvertices; v++) {
- for (Iterator nit = next(v).iterator(); nit.hasNext();) {
- Vertex v2 = ((Integer)nit.next()).intValue();
- float midx = (x(v)+x(v2))/2;
- float midy = (y(v)+y(v2))/2;
- if (distance(midx,midy,ccx,ccy) <= distance(v,midx,midy)) {
- if (debug) Log.debug(this," but splitting it would encroach on a segment");
- return false;
- }
+ boolean dirty = true;
+
+ public Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; }
+ public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); }
+ public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; }
+
+ public boolean encounters(Point p1, Point p2) {
+ for(int i=1; i<=3; i++) {
+ if (v(i).equals(p1)) return true;
+ if (v(i).equals(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 Point c() { return point(cx(),cy()); }
+ public float cx() { return (float)(((double)v(1).x+(double)v(2).x+(double)v(3).x)/3); }
+ public float cy() { return (float)(((double)v(1).y+(double)v(2).y+(double)v(3).y)/3); }
+ 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.r2 <= v(i).distance2(t.cc)) 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) {
+ if (t.contains(p) || t.intersects(p)) return t;
+ else if (t.e(3).intersects(p)) return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t;
+ else if (t.e(1).intersects(p)) return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t;
+ else if (t.e(2).intersects(p)) return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t;
+ else {
+ Triangle t2 = t.followVector(t.c(), p);
+ if (t2==null || t2==t) return t;
+ t = t2;
}
}
- newVertex(ccx, ccy);
- return true;
+ } finally { if (t!=null) triangle0 = t; }
}
- public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, int count, boolean strokeOnly) {
- if (painted) return;
- if (deleted) throw new Error("gargh!");
- if (!strokeOnly) {
- if (special) {
- buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
- (int)a.multiply_py((float)x(v1), (float)y(v1)),
- (int)a.multiply_px((float)x(v2), (float)y(v2)),
- (int)a.multiply_py((float)x(v2), (float)y(v2)),
- (int)a.multiply_px((float)x(v3), (float)y(v3)),
- (int)a.multiply_py((float)x(v3), (float)y(v3)),
- 0xff0000ff);
- } else if ((evenOdd && count%2!=0) || (!evenOdd && count!=0)) {
- buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
- (int)a.multiply_py((float)x(v1), (float)y(v1)),
- (int)a.multiply_px((float)x(v2), (float)y(v2)),
- (int)a.multiply_py((float)x(v2), (float)y(v2)),
- (int)a.multiply_px((float)x(v3), (float)y(v3)),
- (int)a.multiply_py((float)x(v3), (float)y(v3)),
- color);
- } else {
- if (debug)
- buf.fillTriangle((int)a.multiply_px((float)x(v1), (float)y(v1)),
- (int)a.multiply_py((float)x(v1), (float)y(v1)),
- (int)a.multiply_px((float)x(v2), (float)y(v2)),
- (int)a.multiply_py((float)x(v2), (float)y(v2)),
- (int)a.multiply_px((float)x(v3), (float)y(v3)),
- (int)a.multiply_py((float)x(v3), (float)y(v3)),
- 0xff000000 | ((color & 0x00ffffff) >> 8));
+ // 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) || v(1).equals(p2) || v(2).equals(p2) || v(3).equals(p2)) return this;
+ for(int i=1; i<=3; i++) if (!v(i).equals(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 (v(i).equals(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!");
}
}
- painted = true;
- //#repeat t12/t23/t31 v1/v2/v3 v2/v3/v1
- if (t12 != null && !t12.painted) {
- t12.fill(buf, a, color, evenOdd, count + wind(v1, v2), strokeOnly);
- if (debug)
- drawLine(buf, (x(v1)*2+x(v2))/3, (y(v1)*2+y(v2))/3, (x(v1)+2*x(v2))/3, (y(v1)+2*y(v2))/3, a,
- wind(v2,v1)==0?0xff000000:0xff0000ff);
+ if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2))
+ 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),v(2),v(3))+")\n");
+ 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);
+ throw new Error("giving up: \n "+p1+" -> "+p2+"\n " + this);
+ }
+
+ public void check() {
+ if (debug) {
+ 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) if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)");
+ if (t(i) != null) {
+ 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");
+ }
+ }
+ // check that edges all join up
}
- //#end
}
- public int wind(Vertex a, Vertex b) {
- if (next(a).contains(new Integer(b)) && next(b).contains(new Integer(a))) return 0;
- if (y(a) < y(b) || (y(a)==y(b) && x(a)<x(b))) return wind(b, a);
- if (next(a).contains(new Integer(b))) return 1;
- if (next(b).contains(new Integer(a))) return -1;
- return 0;
+
+ 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).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();
}
- public void clear() {
- if (!painted) return;
- painted = false;
- if (t12 != null) t12.clear();
- if (t23 != null) t23.clear();
- if (t31 != null) t31.clear();
- }
- public Triangle(String source, Vertex v1, Vertex v2, Vertex v3) { this(source, v1, v2, v3, false, false); }
- public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake) { this(source, v1,v2,v3,fake,false); }
- public Triangle(String source, Vertex v1, Vertex v2, Vertex v3, boolean fake, boolean ignoreProblems) {
- this.source = source;
+
+ 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 v1 = e(2).unCommonVertex(e(1));
+ Vertex v2 = e(3).unCommonVertex(e(2));
+ Vertex 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);
+
float a = 0;
- for(int i=0; i<3; i++) {
- a=(y(v2)-y(v3))*(x(v2)-x(v1))-(y(v2)-y(v1))*(x(v2)-x(v3));
- if (a!=0) break;
- Vertex t = v2; v2=v3; v3=v1; v1 = t;
+ 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;
+ Vertex t = v2; v2=v3; v3=v1; v1 = t;
+ }
+ Vertex t = v2; v2=v3; v3=t;
}
if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3);
- this.v1 = v1; this.v2 = v2; this.v3 = v3;
- float a1=(x(v1)+x(v2))*(x(v2)-x(v1))+(y(v2)-y(v1))*(y(v1)+y(v2));
- float a2=(x(v2)+x(v3))*(x(v2)-x(v3))+(y(v2)-y(v3))*(y(v2)+y(v3));
- ccx=(a1*(y(v2)-y(v3))-a2*(y(v2)-y(v1)))/a/2;
- ccy=(a2*(x(v2)-x(v1))-a1*(x(v2)-x(v3)))/a/2;
- r = distance(v1,ccx, ccy);
- if (fake) return;
- for(int i=0; i<triangles.size(); i++) {
- Triangle t = (Triangle)triangles.elementAt(i);
- if ((t.v1==v1&&t.v2==v2)||(t.v1==v2&&t.v2==v1)) { if (t.t12!=null) throw new Error(); t.t12=this; t12=t; }
- if ((t.v1==v2&&t.v2==v3)||(t.v1==v3&&t.v2==v2)) { if (t.t12!=null) throw new Error(); t.t12=this; t23=t; }
- if ((t.v1==v3&&t.v2==v1)||(t.v1==v1&&t.v2==v3)) { if (t.t12!=null) throw new Error(); t.t12=this; t31=t; }
- if ((t.v2==v1&&t.v3==v2)||(t.v2==v2&&t.v3==v1)) { if (t.t23!=null) throw new Error(); t.t23=this; t12=t; }
- if ((t.v2==v2&&t.v3==v3)||(t.v2==v3&&t.v3==v2)) { if (t.t23!=null) throw new Error(); t.t23=this; t23=t; }
- if ((t.v2==v3&&t.v3==v1)||(t.v2==v1&&t.v3==v3)) { if (t.t23!=null) throw new Error(); t.t23=this; t31=t; }
- if ((t.v3==v1&&t.v1==v2)||(t.v3==v2&&t.v1==v1)) { if (t.t31!=null) throw new Error(); t.t31=this; t12=t; }
- if ((t.v3==v2&&t.v1==v3)||(t.v3==v3&&t.v1==v2)) { if (t.t31!=null) throw new Error(); t.t31=this; t23=t; }
- if ((t.v3==v3&&t.v1==v1)||(t.v3==v1&&t.v1==v3)) { if (t.t31!=null) throw new Error(); t.t31=this; t31=t; }
- }
+ float a1=(v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y);
+ float a2=(v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y);
+ 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);
+ r2 = v1.distance2(cc);
triangles.add(this);
}
+ 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 (deleted) return;
- deleted = true;
+ 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);
- if (t12 != null) { if (t12.t12==this) t12.t12=null; if (t12.t23==this) t12.t23=null; if (t12.t31==this) t12.t31=null; }
- if (t23 != null) { if (t23.t12==this) t23.t12=null; if (t23.t23==this) t23.t23=null; if (t23.t31==this) t23.t31=null; }
- if (t31 != null) { if (t31.t12==this) t31.t12=null; if (t31.t23==this) t31.t23=null; if (t31.t31==this) t31.t31=null; }
- }
- public boolean contains(Vertex v) {
- float x = x(v);
- float y = y(v);
- if (v==v1) return false;
- if (v==v2) return false;
- if (v==v3) return false;
- if (isect(v1,v2,v)) return false;
- if (isect(v2,v3,v)) return false;
- if (isect(v3,v1,v)) return false;
- return (side(v1,v2,x,y)==side(v1,v2,v3)) && (side(v3,v2,x,y)==side(v3,v2,v1)) && (side(v1,v3,x,y)==side(v1,v3,v2));
+ e(1).rmTriangle(this);
+ e(2).rmTriangle(this);
+ e(3).rmTriangle(this);
+ e1 = null;
+ e2 = null;
+ e3 = null;
}
}
- // Constructor //////////////////////////////////////////////////////////////////////////////
-
- public Mesh(Polygon p) {
- p.sort();
- triangles.setSize(0);
- for(int i=0; i<p.numcontours-1; i++) {
- Vertex last = NULLVERTEX, first = NULLVERTEX;
- boolean good = false;
- for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
- Vertex v = newVertex(p.x[j], p.y[j]);
- if (v==last) continue;
- if (v==first) continue;
- if (last == NULLVERTEX) { last = v; continue; }
- if (first == NULLVERTEX) { first = v; continue; }
- good = true;
- break;
- }
- if (debug) Log.debug(this,"contour " + i + " is " + (good?"good":"bad"));
- if (!good) continue;
- last = NULLVERTEX; first = NULLVERTEX;
- for(int j=p.contours[i]; j<p.contours[i+1]; j++) {
- Vertex v = newVertex(p.x[j], p.y[j]);
- if (v==last) continue;
- if (first==NULLVERTEX) first=v;
- if (last != NULLVERTEX) next(last).add(new Integer(v));
- last = v;
- makeNonDegenerate();
- force();
- }
- if (last!=first) next(last).add(new Integer(first));
- }
- makeNonDegenerate();
- force();
- /*
- redo = true;
- for(; redo;) {
- redo = false;
- for(int k=0; k<triangles.size(); k++) {
- Triangle t = (Triangle)triangles.elementAt(k);
- redo |= t.checkSkinny();
- }
- break;
- }
- System.out.println("I now have " + numvertices + " vertices");
- */
-
+ // 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 //////////////////////////////////////////////////////////////////////////////
- private void drawLine(PixelBuffer buf, float x1, float y1, float x2, float y2, Affine a, int color) {
- buf.drawLine((int)a.multiply_px(x1, y1), (int)a.multiply_py(x1, y1),
- (int)a.multiply_px(x2, y2), (int)a.multiply_py(x2, y2),
- color);
+ public void setIn(boolean evenOdd) {
+ for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).inWasSet = false;
+ triangle0.setIn(evenOdd, 1);
}
- public void fill(PixelBuffer buf, Affine a, int color, boolean evenOdd, boolean strokeOnly) {
+
+ public void fill(PixelBuffer buf, Affine a, Mesh.Chain clip, int color, boolean strokeOnly) {
+ if (triangle0==null) return;
+ System.out.println("I have " + triangles.size() + " triangles");
for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).clear();
- ((Triangle)triangles.elementAt(0)).fill(buf, a, color, evenOdd, 1, strokeOnly);
+ triangle0.fill(buf, a, clip, color, strokeOnly);
}
public void stroke(PixelBuffer buf, Affine a, int color) {
- if (debug)
- for (int i=0; i<numvertices; i++) {
- Vertex v = i;
- for(Iterator it = next(v).iterator(); it.hasNext();) {
- Vertex v2 = ((Integer)it.next()).intValue();
- drawLine(buf, x(v), y(v), x(v2), y(v2), a, 0xffff0000);
- }
- }
- for (int i=0; i<triangles.size(); i++) {
- Triangle t = ((Triangle)triangles.elementAt(i));
- Vertex v1 = t.v1;
- Vertex v2 = t.v2;
- Vertex v3 = t.v3;
- if (debug||t.wind(v1,v2)!=0) drawLine(buf,x(v1),y(v1),x(v2),y(v2),a,(debug && t.wind(v1,v2)!=0) ?0xffffffff:color);
- if (debug||t.wind(v3,v2)!=0) drawLine(buf,x(v3),y(v3),x(v2),y(v2),a,(debug && t.wind(v3,v2)!=0) ?0xffffffff:color);
- if (debug||t.wind(v1,v3)!=0) drawLine(buf,x(v1),y(v1),x(v3),y(v3),a,(debug && t.wind(v1,v3)!=0) ?0xffffffff:color);
- }
+ if (triangle0==null) return;
+ for (int i=0; i<triangles.size(); i++) ((Triangle)triangles.elementAt(i)).stroke(buf, a, color);
}
- // Geometric Utility Functions //////////////////////////////////////////////////////////////////////////////
-
- public float distance(Vertex v1, Vertex v2) { return distance(x(v1), y(v1), x(v2), y(v2)); }
- public float distance(Vertex v1, float x, float y) { return distance(x(v1),y(v1),x,y); }
- public float distance(float x1,float y1,float x2,float y2) {return (float)Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
- public int side(Vertex v1, Vertex v2, Vertex v3) { return side(v1, v2, x(v3), y(v3)); }
- public int side(Vertex v1, Vertex v2, float x, float y) { return side(v1, x(v2), y(v2), x, y); }
- public int side(Vertex v1, float x, float y, Vertex v3) { return side(v1, x, y, x(v3), y(v3)); }
- public int side(Vertex v1, float x, float y, float x2, float y2) {
- float a = y-y(v1), b = x(v1)-x, c = -1 * (a*x(v1)+b*y(v1));
- return (- (a*x2+c)/b > y2) ? -1 : (- (a*x2+c)/b < y2) ? 1 : 0;
+ public void newcontour() {
+ if (start != null) add(start.x, start.y);
+ start = null;
+ last = null;
}
- public boolean isect(Vertex v1, Vertex v2, Vertex v3, Vertex v4) {
- if (v1==v3 || v1==v4 || v2==v3 || v2==v4) return false;
- float a = side(v1,v2,v3);
- float b = side(v1,v2,v4);
- float c = side(v3,v4,v1);
- float d = side(v3,v4,v2);
- return a!=b && c!=d && a!=0 && b!=0 && c!=0 && d!=0;
+ 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 boolean isect(Vertex v1, Vertex v2, Vertex v) {
- return
- side(v1,v2,v)==0 &&
- x(v) - Math.max(x(v1),x(v2)) < 0 &&
- x(v) - Math.min(x(v1),x(v2)) > 0 &&
- y(v) - Math.max(y(v1),y(v2)) < 0 &&
- y(v) - Math.min(y(v1),y(v2)) > 0;
+ 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;
+ }
}
-
}
// Licensed under the GNU General Public License version 2 ("the License").
// You may not use this file except in compliance with the License.
-// FIXME
package org.ibex.graphics;
import java.util.*;
import org.ibex.util.*;
public static final float INCHES_PER_CM = (float)0.3937;
public static final float INCHES_PER_MM = INCHES_PER_CM / 10;
private static final int DEFAULT_PATHLEN = 1000;
+ private static final int NUMSTEPS = 10;
private static final float PI = (float)Math.PI;
- // the number of vertices on this path
- int numvertices = 0;
+ boolean closed = false;
+ Curve head = null;
+ Curve tail = null;
+ protected void add(Curve c) {
+ if (head==null) { tail=head=c; return; }
+ c.prev = tail;
+ tail.next = c;
+ tail = c;
+ }
- // the vertices of the path
- float[] x = new float[DEFAULT_PATHLEN];
- float[] y = new float[DEFAULT_PATHLEN];
+ public void addTo(Mesh m, boolean evenOdd) {
+ for(Curve c = head; c != null; c = c.next) c.addTo(m);
+ m.setIn(evenOdd);
+ }
- // the type of each edge; type[i] is the type of the edge from x[i],y[i] to x[i+1],y[i+1]
- byte[] type = new byte[DEFAULT_PATHLEN];
+ abstract class Curve {
+ Curve next, prev;
+ float x, y;
+ float c1x, c1y, c2x, c2y;
+ public Curve() { }
+ public abstract void addTo(Mesh ret);
+ }
- // bezier control points
- float[] c1x = new float[DEFAULT_PATHLEN]; // or rx (arcto)
- float[] c1y = new float[DEFAULT_PATHLEN]; // or ry (arcto)
- float[] c2x = new float[DEFAULT_PATHLEN]; // or x-axis-rotation (arcto)
- float[] c2y = new float[DEFAULT_PATHLEN]; // or large-arc << 1 | sweep (arcto)
+ class Line extends Curve {
+ public void addTo(Mesh ret) {
+ float rx = next.x;
+ float ry = next.y;
+ ret.add(rx,ry);
+ }
+ }
- boolean closed = false;
+ class Move extends Curve {
+ public void addTo(Mesh ret) {
+ ret.newcontour();
+ if (next==null) return;
+ float rx = next.x;
+ float ry = next.y;
+ ret.add(rx, ry);
+ }
+ }
- static final byte TYPE_MOVETO = 0;
- static final byte TYPE_LINETO = 1;
- static final byte TYPE_ARCTO = 2;
- static final byte TYPE_CUBIC = 3;
- static final byte TYPE_QUADRADIC = 4;
+ class Arc extends Curve {
+ public void addTo(Mesh ret) {
+ System.out.println("ARC!");
+ float rx = c1x;
+ float ry = c1y;
+ float phi = c2x;
+ float fa = ((int)c2y) >> 1;
+ float fs = ((int)c2y) & 1;
+ float x1 = x;
+ float y1 = y;
+ float x2 = next.x;
+ float y2 = next.y;
+
+ // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
+ float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
+ float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
+ float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
+ (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
+ float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
+ float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
+ float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
+ float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
+
+ // F.6.4 Conversion from center to endpoint parameterization
+ float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
+ float det = ux * vy - uy * vx;
+ float theta1 = (det < 0 ? -1 : 1) *
+ (float)Math.acos((ux * vx + uy * vy) /
+ ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
+ ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
+ vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
+ det = ux * vy - uy * vx;
+ float dtheta = (det < 0 ? -1 : 1) *
+ (float)Math.acos((ux * vx + uy * vy) /
+ ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
+ dtheta = dtheta % (float)(2 * Math.PI);
+
+ if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
+ if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
+
+ if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
+ else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
+
+ // FIXME: integrate F.6.6
+ // FIXME: isn't quite ending where it should...
+
+ // F.6.3: Parameterization alternatives
+ float theta = theta1;
+ for(int j=0; j<NUMSTEPS; j++) {
+ float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
+ ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
+ float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
+ ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
+ ret.add(rasterx, rastery);
+ theta += dtheta / NUMSTEPS;
+ }
+ }
+ }
- // FIXME: hack
- private String toString;
- public String toString() { return toString; }
+ class Bezier extends Curve {
+ float cx, cy;
+ public void addTo(Mesh ret) {
+ float ax = next.x - 3 * c2x + 3 * c1x - x;
+ float bx = 3 * c2x - 6 * c1x + 3 * x;
+ float cx = 3 * c1x - 3 * x;
+ float dx = x;
+ float ay = next.y - 3 * c2y + 3 * c1y - y;
+ float by = 3 * c2y - 6 * c1y + 3 * y;
+ float cy = 3 * c1y - 3 * y;
+ float dy = y;
+
+ float x0 = x;
+ float y0 = y;
+ float x1 = next.x;
+ float y1 = next.y;
+ float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
+
+ //for(float t=0; t<1; t += 0.5) {
+ for(float t=0; t<1; t += 1/(steps/20)) {
+ float rx = ax * t * t * t + bx * t * t + cx * t + dx;
+ float ry = ay * t * t * t + by * t * t + cy * t + dy;
+ ret.add(rx,ry);
+ }
+ }
+ }
+
+ class QuadBezier extends Curve {
+ float cx, cy, cx2, cy2;
+ public void addTo(Mesh ret) {
+ throw new Error("doesn't work yet");
+ /*
+ float bx = next.x - 2 * c1x + x;
+ float cx = 2 * c1x - 2 * x;
+ float dx = x;
+ float by = next.y - 2 * c1y + y;
+ float cy = 2 * c1y - 2 * y;
+ float dy = y;
+
+ float x0 = a.multiply_px(x, y);
+ float y0 = a.multiply_py(x, y);
+ float x1 = a.multiply_px(next.x, next.y);
+ float y1 = a.multiply_py(next.x, next.y);
+ float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
+
+ for(float t=0; t<1; t += 1 / (steps/20)) {
+ float rx = bx * t * t + cx * t + dx;
+ float ry = by * t * t + cy * t + dy;
+ ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
+ }
+ */
+ }
+ }
public Path(String s) {
- this.toString = s;
+ //this.toString = s;
Tokenizer t = new Tokenizer(s);
char last_command = 'M';
boolean first = true;
// FIXME wrong
float min = Float.MAX_VALUE;
float max = Float.MIN_VALUE;
- for(int i=0; i<numvertices; i++) {
- min = Math.min(min, a.multiply_px(x[i], y[i]));
- max = Math.max(max, a.multiply_px(x[i], y[i]));
+ for(Curve c = head; c != null; c = c.next) {
+ min = Math.min(min, a.multiply_px(c.x, c.y));
+ max = Math.max(max, a.multiply_px(c.x, c.y));
}
return Encode.twoFloatsToLong(max, min);
}
public long transform(Affine a, boolean forReal, boolean widthheight) {
float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
float maxx = Integer.MIN_VALUE; float maxy = Integer.MIN_VALUE;
- for(int i=0; i<numvertices; i++) {
- if (type[i] == TYPE_ARCTO) { /* FIXME!!! WRONG!!!! */ continue; }
- float x = a.multiply_px(this.x[i], this.y[i]); if (x>maxx) maxx = x; if (x<minx) minx = x;
- float y = a.multiply_py(this.x[i], this.y[i]); if (y>maxy) maxy = y; if (y<miny) miny = y;
- float c1x = a.multiply_px(this.c1x[i], this.c1y[i]); if (c1x>maxx) maxx = c1x; if (c1x<minx) minx = c1x;
- float c1y = a.multiply_py(this.c1x[i], this.c1y[i]); if (c1y>maxy) maxy = c1y; if (c1y<miny) miny = c1y;
- float c2x = a.multiply_px(this.c2x[i], this.c2y[i]); if (c2x>maxx) maxx = c2x; if (c2x<minx) minx = c2x;
- float c2y = a.multiply_py(this.c2x[i], this.c2y[i]); if (c2y>maxy) maxy = c2y; if (c2y<miny) miny = c2y;
+ for(Curve c = head; c != null; c = c.next) {
+ if (c instanceof Arc) { /* FIXME!!! WRONG!!!! */ continue; }
+ float x = a.multiply_px(c.x, c.y); if (x>maxx) maxx = x; if (x<minx) minx = x;
+ float y = a.multiply_py(c.x, c.y); if (y>maxy) maxy = y; if (y<miny) miny = y;
+ float c1x = a.multiply_px(c.c1x, c.c1y); if (c1x>maxx) maxx = c1x; if (c1x<minx) minx = c1x;
+ float c1y = a.multiply_py(c.c1x, c.c1y); if (c1y>maxy) maxy = c1y; if (c1y<miny) miny = c1y;
+ float c2x = a.multiply_px(c.c2x, c.c2y); if (c2x>maxx) maxx = c2x; if (c2x<minx) minx = c2x;
+ float c2y = a.multiply_py(c.c2x, c.c2y); if (c2y>maxy) maxy = c2y; if (c2y<miny) miny = c2y;
if (forReal) {
- this.x[i] = x; this.y[i] = y;
- this.c1x[i] = c1x; this.c1y[i] = c1y;
- this.c2x[i] = c2x; this.c2y[i] = c2y;
+ c.x = x; c.y = y;
+ c.c1x = c1x; c.c1y = c1y;
+ c.c2x = c2x; c.c2y = c2y;
}
}
if (widthheight) return ((((long)Float.floatToIntBits(maxx - minx)) << 32) | ((long)Float.floatToIntBits(maxy - miny)));
public void alignToOrigin() {
float minx = Integer.MAX_VALUE; float miny = Integer.MAX_VALUE;
- for(int i=0; i<numvertices; i++) { if (x[i] < minx) minx = x[i]; if (y[i] < miny) miny = y[i]; }
- for(int i=0; i<numvertices; i++) {
- x[i] -= minx; y[i] -= miny;
- if (type[i] == TYPE_ARCTO) continue;
- c1x[i] -= minx; c2x[i] -= minx; c1y[i] -= miny; c2y[i] -= miny;
+ for(Curve c = head; c != null; c = c.next) { if (c.x < minx) minx = c.x; if (c.y < miny) miny = c.y; }
+ for(Curve c = head; c != null; c = c.next) {
+ c.x -= minx; c.y -= miny;
+ if (c instanceof Arc) continue;
+ c.c1x -= minx; c.c2x -= minx; c.c1y -= miny; c.c2y -= miny;
}
}
-
public static class Tokenizer {
// FIXME: check array bounds exception for improperly terminated string
String s;
if (s == null) return null;
Tokenizer t = new Tokenizer(s);
Path ret = new Path(s);
+ return ret;/*
char last_command = 'M';
boolean first = true;
while(t.hasMoreTokens()) {
ret.parseSingleCommandAndArguments(t, command, relative);
last_command = command;
}
- return ret;
+ return ret;*/
}
-
private void consumeWhitespace() {
while(i < s.length() && (Character.isWhitespace(s.charAt(i)))) i++;
if (i < s.length() && s.charAt(i) == ',') i++;
}
}
- /** Creates a concrete vector path transformed through the given matrix. */
- public void addTo(Polygon ret, Affine a) {
- float NUMSTEPS = 5; // FIXME
- ret.x[0] = a.multiply_px(x[0], y[0]);
- ret.y[0] = a.multiply_py(x[0], y[0]);
-
- for(int i=0; i<numvertices; i++) {
- if (type[i] == TYPE_LINETO) {
- float rx = x[i+1];
- float ry = y[i+1];
- ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
-
- } else if (type[i] == TYPE_MOVETO) {
- float rx = x[i+1];
- float ry = y[i+1];
- ret.newcontour();
- ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
-
- } else if (type[i] == TYPE_ARCTO) {
- float rx = c1x[i];
- float ry = c1y[i];
- float phi = c2x[i];
- float fa = ((int)c2y[i]) >> 1;
- float fs = ((int)c2y[i]) & 1;
- float x1 = x[i];
- float y1 = y[i];
- float x2 = x[i+1];
- float y2 = y[i+1];
-
- // F.6.5: given x1,y1,x2,y2,fa,fs, compute cx,cy,theta1,dtheta
- float x1_ = (float)Math.cos(phi) * (x1 - x2) / 2 + (float)Math.sin(phi) * (y1 - y2) / 2;
- float y1_ = -1 * (float)Math.sin(phi) * (x1 - x2) / 2 + (float)Math.cos(phi) * (y1 - y2) / 2;
- float tmp = (float)Math.sqrt((rx * rx * ry * ry - rx * rx * y1_ * y1_ - ry * ry * x1_ * x1_) /
- (rx * rx * y1_ * y1_ + ry * ry * x1_ * x1_));
- float cx_ = (fa == fs ? -1 : 1) * tmp * (rx * y1_ / ry);
- float cy_ = (fa == fs ? -1 : 1) * -1 * tmp * (ry * x1_ / rx);
- float cx = (float)Math.cos(phi) * cx_ - (float)Math.sin(phi) * cy_ + (x1 + x2) / 2;
- float cy = (float)Math.sin(phi) * cx_ + (float)Math.cos(phi) * cy_ + (y1 + y2) / 2;
-
- // F.6.4 Conversion from center to endpoint parameterization
- float ux = 1, uy = 0, vx = (x1_ - cx_) / rx, vy = (y1_ - cy_) / ry;
- float det = ux * vy - uy * vx;
- float theta1 = (det < 0 ? -1 : 1) *
- (float)Math.acos((ux * vx + uy * vy) /
- ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
- ux = (x1_ - cx_) / rx; uy = (y1_ - cy_) / ry;
- vx = (-1 * x1_ - cx_) / rx; vy = (-1 * y1_ - cy_) / ry;
- det = ux * vy - uy * vx;
- float dtheta = (det < 0 ? -1 : 1) *
- (float)Math.acos((ux * vx + uy * vy) /
- ((float)Math.sqrt(ux * ux + uy * uy) * (float)Math.sqrt(vx * vx + vy * vy)));
- dtheta = dtheta % (float)(2 * Math.PI);
-
- if (fs == 0 && dtheta > 0) theta1 -= 2 * PI;
- if (fs == 1 && dtheta < 0) theta1 += 2 * PI;
-
- if (fa == 1 && dtheta < 0) dtheta = 2 * PI + dtheta;
- else if (fa == 1 && dtheta > 0) dtheta = -1 * (2 * PI - dtheta);
-
- // FIXME: integrate F.6.6
- // FIXME: isn't quite ending where it should...
-
- // F.6.3: Parameterization alternatives
- float theta = theta1;
- for(int j=0; j<NUMSTEPS; j++) {
- float rasterx = rx * (float)Math.cos(theta) * (float)Math.cos(phi) -
- ry * (float)Math.sin(theta) * (float)Math.sin(phi) + cx;
- float rastery = rx * (float)Math.cos(theta) * (float)Math.sin(phi) +
- ry * (float)Math.cos(phi) * (float)Math.sin(theta) + cy;
- ret.add(a.multiply_px(rasterx, rastery), a.multiply_py(rasterx, rastery));
- theta += dtheta / NUMSTEPS;
- }
-
- } else if (type[i] == TYPE_CUBIC) {
-
- float ax = x[i+1] - 3 * c2x[i] + 3 * c1x[i] - x[i];
- float bx = 3 * c2x[i] - 6 * c1x[i] + 3 * x[i];
- float cx = 3 * c1x[i] - 3 * x[i];
- float dx = x[i];
- float ay = y[i+1] - 3 * c2y[i] + 3 * c1y[i] - y[i];
- float by = 3 * c2y[i] - 6 * c1y[i] + 3 * y[i];
- float cy = 3 * c1y[i] - 3 * y[i];
- float dy = y[i];
-
- float x0 = a.multiply_px(x[i], y[i]);
- float y0 = a.multiply_py(x[i], y[i]);
- float x1 = a.multiply_px(x[i+1], y[i+1]);
- float y1 = a.multiply_py(x[i+1], y[i+1]);
- float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
-
- for(float t=0; t<1; t += 1 / (steps/20)) {
- float rx = ax * t * t * t + bx * t * t + cx * t + dx;
- float ry = ay * t * t * t + by * t * t + cy * t + dy;
- ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
- }
-
-
- } else if (type[i] == TYPE_QUADRADIC) {
-
- float bx = x[i+1] - 2 * c1x[i] + x[i];
- float cx = 2 * c1x[i] - 2 * x[i];
- float dx = x[i];
- float by = y[i+1] - 2 * c1y[i] + y[i];
- float cy = 2 * c1y[i] - 2 * y[i];
- float dy = y[i];
-
- float x0 = a.multiply_px(x[i], y[i]);
- float y0 = a.multiply_py(x[i], y[i]);
- float x1 = a.multiply_px(x[i+1], y[i+1]);
- float y1 = a.multiply_py(x[i+1], y[i+1]);
- float steps = (float)Math.sqrt( (x1-x0) * (x1-x0) + (y1-y0) * (y1-y0) );
-
- for(float t=0; t<1; t += 1 / (steps/20)) {
- float rx = bx * t * t + cx * t + dx;
- float ry = by * t * t + cy * t + dy;
- ret.add(a.multiply_px(rx, ry), a.multiply_py(rx, ry));
- }
-
- }
- }
- }
-
protected void parseSingleCommandAndArguments(Tokenizer t, char command, boolean relative) {
- if (numvertices == 0 && command != 'm')
- throw new RuntimeException("first command MUST be an 'm', not a " + command);
- if (numvertices > x.length - 2) {
- float[] new_x = new float[x.length * 2]; System.arraycopy(x, 0, new_x, 0, x.length); x = new_x;
- float[] new_y = new float[y.length * 2]; System.arraycopy(y, 0, new_y, 0, y.length); y = new_y;
- }
+ if (tail==null && command!='m') throw new RuntimeException("first command MUST be an 'm', not a " + command);
switch(command) {
case 'z': {
- int where;
- type[numvertices-1] = TYPE_LINETO;
- for(where = numvertices-2; where >= 0 && type[where] != TYPE_MOVETO; where--);
- x[numvertices] = x[where+1];
- y[numvertices] = y[where+1];
- numvertices++;
+ Curve c;
+ for(c = tail.prev; c != null && !(c instanceof Move); c = c.prev);
+ Line ret = new Line();
+ ret.x = c.x;
+ ret.y = c.y;
+ add(ret);
+ Move mov = new Move();
+ mov.x = ret.x;
+ mov.y = ret.y;
+ add(mov);
closed = true;
// FIXME: actually, we should search back to the last 'z' or 'm', not just 'm'
break;
}
case 'm': {
- if (numvertices > 0) type[numvertices-1] = TYPE_MOVETO;
- x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- if (numvertices > 2 && type[numvertices-2] == TYPE_MOVETO) {
- x[numvertices-1] = x[numvertices];
- y[numvertices-1] = y[numvertices];
- } else {
- numvertices++;
- }
+ // feature: collapse consecutive movetos
+ Move ret = new Move();
+ ret.x = t.parseFloat() + (relative ? tail.y : 0);
+ ret.y = t.parseFloat() + (relative ? tail.y : 0);
+ add(ret);
break;
}
case 'l': case 'h': case 'v': {
- type[numvertices-1] = TYPE_LINETO;
float first = t.parseFloat(), second;
- if (command == 'h') {
- second = relative ? 0 : y[numvertices - 1];
- } else if (command == 'v') {
- second = first; first = relative ? 0 : x[numvertices - 1];
- } else {
- second = t.parseFloat();
- }
- x[numvertices] = first + (relative ? x[numvertices - 1] : 0);
- y[numvertices] = second + (relative ? y[numvertices - 1] : 0);
- numvertices++;
+ if (command == 'h') second = relative ? 0 : tail.y;
+ else if (command == 'v') { second = first; first = relative ? 0 : tail.x; }
+ else second = t.parseFloat();
+ Line ret = new Line();
+ ret.x = first + (relative ? tail.x : 0);
+ ret.y = second + (relative ? tail.y : 0);
+ add(ret);
break;
}
case 'a': {
- type[numvertices-1] = TYPE_ARCTO;
- c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- c2x[numvertices-1] = (t.parseFloat() / 360) * 2 * PI;
- c2y[numvertices-1] = (((int)t.parseFloat()) << 1) | (int)t.parseFloat();
- x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- numvertices++;
+ Arc ret = new Arc();
+ ret.c1x = t.parseFloat() + (relative ? tail.x : 0);
+ ret.c1y = t.parseFloat() + (relative ? tail.y : 0);
+ ret.c2x = (t.parseFloat() / 360) * 2 * PI;
+ ret.c2y = t.parseFloat();
+ ret.x = t.parseFloat() + (relative ? tail.x : 0);
+ ret.y = t.parseFloat() + (relative ? tail.y : 0);
+ add(ret);
break;
}
case 's': case 'c': {
- type[numvertices-1] = TYPE_CUBIC;
+ Bezier ret = new Bezier();
if (command == 'c') {
- c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- } else if (numvertices > 1 && type[numvertices-2] == TYPE_CUBIC) {
- c1x[numvertices-1] = 2 * x[numvertices - 1] - c2x[numvertices-2];
- c1y[numvertices-1] = 2 * y[numvertices - 1] - c2y[numvertices-2];
+ tail.c1x = t.parseFloat() + (relative ? tail.x : 0);
+ tail.c1y = t.parseFloat() + (relative ? tail.y : 0);
+ } else if (head != null && tail instanceof Bezier) {
+ tail.c1x = 2 * tail.x-((Bezier)tail).c2x;
+ tail.c1y = 2 * tail.y-((Bezier)tail).c2x;
} else {
- c1x[numvertices-1] = x[numvertices-1];
- c1y[numvertices-1] = y[numvertices-1];
+ tail.c1x = tail.x;
+ tail.c1y = tail.y;
}
- c2x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- c2y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- numvertices++;
+ tail.c2x = t.parseFloat() + (relative ? tail.x : 0);
+ tail.c2y = t.parseFloat() + (relative ? tail.y : 0);
+ ret.x = t.parseFloat() + (relative ? tail.x : 0);
+ ret.y = t.parseFloat() + (relative ? tail.y : 0);
+ add(ret);
break;
}
case 't': case 'q': {
- type[numvertices-1] = TYPE_QUADRADIC;
+ QuadBezier ret = new QuadBezier();
if (command == 'q') {
- c1x[numvertices-1] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- c1y[numvertices-1] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- } else if (numvertices > 1 && type[numvertices-2] == TYPE_QUADRADIC) {
- c1x[numvertices-1] = 2 * x[numvertices - 1] - c1x[numvertices-2];
- c1y[numvertices-1] = 2 * y[numvertices - 1] - c1y[numvertices-2];
+ tail.c1x = t.parseFloat() + (relative ? tail.x : 0);
+ tail.c1y = t.parseFloat() + (relative ? tail.y : 0);
+ } else if (head != null && tail instanceof QuadBezier) {
+ tail.c1x = 2 * tail.x-((QuadBezier)tail).c1x;
+ tail.c1y = 2 * tail.y-((QuadBezier)tail).c1y;
} else {
- c1x[numvertices-1] = x[numvertices-1];
- c1y[numvertices-1] = y[numvertices-1];
+ tail.c1x = tail.x;
+ tail.c1y = tail.y;
}
- x[numvertices] = t.parseFloat() + (relative ? x[numvertices - 1] : 0);
- y[numvertices] = t.parseFloat() + (relative ? y[numvertices - 1] : 0);
- numvertices++;
+ ret.x = t.parseFloat() + (relative ? tail.x : 0);
+ ret.y = t.parseFloat() + (relative ? tail.y : 0);
+ add(ret);
break;
}
default:
- // FIXME
- }
-
- /*
- // invariant: after this loop, no two lines intersect other than at a vertex
- // FIXME: cleanup
- int index = numvertices - 2;
- for(int i=0; i<Math.min(numvertices - 3, index); i++) {
- for(int j = index; j < numvertices - 1; j++) {
-
- // I'm not sure how to deal with vertical lines...
- if (x[i+1] == x[i] || x[j+1] == x[j]) continue;
-
- float islope = (y[i+1] - y[i]) / (x[i+1] - x[i]);
- float jslope = (y[j+1] - y[j]) / (x[j+1] - x[j]);
- if (islope == jslope) continue; // parallel lines can't intersect
-
- float _x = (islope * x[i] - jslope * x[j] + y[j] - y[i]) / (islope - jslope);
- float _y = islope * (_x - x[i]) + y[i];
-
- if (_x > Math.min(x[i+1], x[i]) && _x < Math.max(x[i+1], x[i]) &&
- _x > Math.min(x[j+1], x[j]) && _x < Math.max(x[j+1], x[j])) {
- // FIXME: something's not right in here. See if we can do without fracturing line 'i'.
- for(int k = ++numvertices; k>i; k--) { x[k] = x[k - 1]; y[k] = y[k - 1]; }
- x[i+1] = _x;
- y[i+1] = _y;
- x[numvertices] = x[numvertices - 1]; x[numvertices - 1] = _x;
- y[numvertices] = y[numvertices - 1]; y[numvertices - 1] = _y;
- edges[numedges++] = numvertices - 1; numvertices++;
- index++;
- break; // actually 'continue' the outermost loop
- }
- }
}
- */
}
public abstract void fillTriangle(int x1, int y1, int x2, int y2, int x3, int y3, int color);
public abstract void drawPicture(Picture p, Affine a, Mesh h);
public abstract void drawGlyph(Font.Glyph source, Affine a, Mesh h, int rgb, int bg);
- public abstract void stroke(Polygon p, int color);
- public abstract void fill(Polygon p, Paint paint);
+ public abstract void stroke(Mesh p, int color);
+ public abstract void fill(Mesh p, Paint paint);
}
+++ /dev/null
-package org.ibex.graphics;\r
-import java.util.*;\r
-import org.ibex.util.*;\r
-\r
-//\r
-// This is a very heavily modified (nearly complete rewrite) version\r
-// of GPCJ, which is itself a Java port of the Generalized Polygon\r
-// Clipping Library\r
-// \r
-// http://www.cs.man.ac.uk/aig/staff/alan/software/gpc.html\r
-//\r
-// Modifications by Adam Megacz\r
-//\r
-\r
-// Possible remaining optimizations:\r
-// -- recycle EdgeNode instances\r
-// -- evolve PolygonNode into the Polygon class?\r
-\r
-//\r
-// !! WARNING !! !! WARNING !! !! WARNING !!\r
-//\r
-// Unlike GPCJ, this code is NOT reentrant or thread-safe; static\r
-// arrays are used to avoid allocation penalties. Also, the union(),\r
-// intersection(), and xor() methods destructively update the 'this'\r
-// object.\r
-//\r
-\r
-/*\r
- * The SEI Software Open Source License, Version 1.0\r
- *\r
- * Copyright (c) 2004, Solution Engineering, Inc.\r
- * All rights reserved.\r
- *\r
- * Redistribution and use in source and binary forms, with or without\r
- * modification, are permitted provided that the following conditions\r
- * are met:\r
- *\r
- * 1. Redistributions of source code must retain the above copyright\r
- * notice, this list of conditions and the following disclaimer. \r
- *\r
- * 2. The end-user documentation included with the redistribution,\r
- * if any, must include the following acknowledgment:\r
- * "This product includes software developed by the\r
- * Solution Engineering, Inc. (http://www.seisw.com/)."\r
- * Alternately, this acknowledgment may appear in the software itself,\r
- * if and wherever such third-party acknowledgments normally appear.\r
- *\r
- * 3. The name "Solution Engineering" must not be used to endorse or\r
- * promote products derived from this software without prior\r
- * written permission. For written permission, please contact\r
- * admin@seisw.com.\r
- *\r
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED\r
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE\r
- * DISCLAIMED. IN NO EVENT SHALL SOLUTION ENGINEERING, INC. OR\r
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\r
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\r
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF\r
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND\r
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,\r
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT\r
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF\r
- * SUCH DAMAGE.\r
- * ====================================================================\r
- */\r
-\r
-\r
-public final class Polygon {\r
-\r
- private static final int DEFAULT_PATHLEN = 10;\r
- private static final int DEFAULT_CONTOURS = 4;\r
-\r
- private static final int BIGNUM = 65535;\r
-\r
- public boolean[] hole = new boolean[DEFAULT_CONTOURS];\r
- public boolean[] contributing = new boolean[DEFAULT_CONTOURS];\r
- public float[] x = new float[DEFAULT_PATHLEN];\r
- public float[] y = new float[DEFAULT_PATHLEN];\r
- public int numvertices = 0;\r
- public int[] edges = null;\r
- public int numedges = 0;\r
- public int[] contours = new int[DEFAULT_CONTOURS];\r
- public int numcontours = 0;\r
- public float[] minx_ = new float[DEFAULT_CONTOURS];\r
- public float[] miny_ = new float[DEFAULT_CONTOURS];\r
- public float[] maxx_ = new float[DEFAULT_CONTOURS];\r
- public float[] maxy_ = new float[DEFAULT_CONTOURS];\r
- public float minx = Float.MAX_VALUE;\r
- public float miny = Float.MAX_VALUE;\r
- public float maxx = Float.MIN_VALUE;\r
- public float maxy = Float.MIN_VALUE;\r
- public boolean sealed = false;\r
-\r
- public Polygon() { }\r
- public Polygon(Path p, Affine a) { p.addTo(this, a); }\r
- public void intersection(Polygon p2) { clip(GPC_INT, this, p2); }\r
- public void intersect(Polygon p2) { clip(GPC_INT, this, p2); }\r
- public void union(Polygon p2) { clip(GPC_UNION, this, p2); }\r
- public void xor(Polygon p2) { clip(GPC_XOR, this, p2); }\r
- public void subtract(Polygon p2) { clip(GPC_DIFF, this, p2); }\r
- private static Polygon rectclipper = new Polygon();\r
- public Polygon addrect(float x1, float y1, float x2, float y2, Affine a) {\r
- add(a.multiply_px(x1, y1), a.multiply_py(x1, y1));\r
- add(a.multiply_px(x2, y1), a.multiply_py(x2, y1));\r
- add(a.multiply_px(x2, y2), a.multiply_py(x2, y2));\r
- add(a.multiply_px(x1, y2), a.multiply_py(x1, y2));\r
- closepath();\r
- return this;\r
- }\r
- public void clipto(float x1, float y1, float x2, float y2, Affine a) {\r
- rectclipper.clear();\r
- rectclipper.addrect(x1, y1, x2, y2, a);\r
- intersection(rectclipper);\r
- }\r
- public void closepath() {\r
- if (numcontours > 0 && numvertices == 0) return;\r
- if (numcontours > 0 && (x[contours[numcontours-1]] != x[numvertices-1] || y[contours[numcontours-1]] != y[numvertices-1]))\r
- add(x[contours[numcontours-1]], y[contours[numcontours-1]]);\r
- }\r
- public void newcontour() {\r
- if (numcontours > 0 && numvertices == contours[numcontours-1]) return;\r
- closepath();\r
- maxx_[numcontours] = maxy_[numcontours] = Float.MIN_VALUE;\r
- minx_[numcontours] = miny_[numcontours] = Float.MAX_VALUE;\r
- contours[numcontours++] = numvertices;\r
- if (numcontours >= contours.length - 2) {\r
- int[] z = new int[contours.length * 4]; System.arraycopy(contours, 0, z, 0, contours.length); contours = z;\r
- boolean[] s = new boolean[hole.length * 4]; System.arraycopy(hole, 0, s, 0, hole.length); hole = s;\r
- s = new boolean[contributing.length * 4];System.arraycopy(contributing,0,s,0,contributing.length);contributing = s;\r
- float[] f = new float[minx_.length * 4]; System.arraycopy(minx_, 0, f, 0, minx_.length); minx_ = f;\r
- f = new float[maxx_.length * 4]; System.arraycopy(maxx_, 0, f, 0, maxx_.length); maxx_ = f;\r
- f = new float[miny_.length * 4]; System.arraycopy(miny_, 0, f, 0, miny_.length); miny_ = f;\r
- f = new float[maxy_.length * 4]; System.arraycopy(maxy_, 0, f, 0, maxy_.length); maxy_ = f;\r
- Log.debug(this, "growing contour list to " + contours.length);\r
- } \r
- }\r
- public void add(float x, float y) {\r
- if (sealed) { Log.error(this, "tried to add a vertex to a sealed polygon!"); return; }\r
- if (numcontours == 0) newcontour();\r
- this.x[numvertices] = x;\r
- this.y[numvertices] = y;\r
- numvertices++;\r
- if (x > maxx_[numcontours-1]) maxx_[numcontours-1] = x;\r
- if (x < minx_[numcontours-1]) minx_[numcontours-1] = x;\r
- if (y > maxy_[numcontours-1]) maxy_[numcontours-1] = y;\r
- if (y < miny_[numcontours-1]) miny_[numcontours-1] = y;\r
- if (x > maxx) maxx = x;\r
- if (x < minx) minx = x;\r
- if (y > maxy) maxy = y;\r
- if (y < miny) miny = y;\r
- if (numvertices >= this.x.length) {\r
- float[] new_x = new float[this.x.length * 4]; System.arraycopy(this.x, 0, new_x, 0, this.x.length); this.x = new_x;\r
- float[] new_y = new float[this.y.length * 4]; System.arraycopy(this.y, 0, new_y, 0, this.y.length); this.y = new_y;\r
- Log.debug(this, "growing vertex list to " + this.x.length);\r
- } \r
- }\r
- public void clear() {\r
- numvertices = 0; numedges = 0; numcontours = 0; sealed = false;\r
- maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;\r
- }\r
- public boolean isEmpty() { return numvertices == 0; }\r
- public void add(Polygon p) { add(p, Affine.identity()); }\r
- public void add(Polygon p, Affine a) { for(int i=0; i<p.numcontours; i++) add(p, i, a); }\r
- public void add(Polygon p, int idx) { add(p, idx, Affine.identity()); }\r
- public void add(Polygon p, int idx, Affine a) {\r
- newcontour();\r
- for(int i=p.contours[idx]; i<p.contours[idx+1]; i++) {\r
- float x = p.x[p.contours[idx]+i];\r
- float y = p.y[p.contours[idx]+i];\r
- add(a.multiply_px(x, y), a.multiply_py(x, y));\r
- }\r
- }\r
- public Polygon transform(Affine a) {\r
- maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;\r
- int s = 0;\r
- for(int i=0; i<numvertices; i++) {\r
- while (i >= contours[s+1]) s++;\r
- float x = a.multiply_px(this.x[i], this.y[i]);\r
- float y = a.multiply_py(this.x[i], this.y[i]);\r
- this.x[i] = x; \r
- this.y[i] = y; \r
- if (x > maxx_[s]) maxx_[s] = x;\r
- if (x < minx_[s]) minx_[s] = x;\r
- if (y > maxy_[s]) maxy_[s] = y;\r
- if (y < miny_[s]) miny_[s] = y;\r
- if (x > maxx) maxx = x;\r
- if (x < minx) minx = x;\r
- if (y > maxy) maxy = y;\r
- if (y < miny) miny = y;\r
- }\r
- return this;\r
- }\r
-\r
- public void stroke(PixelBuffer buf, int color) {\r
- Polygon p = this;\r
- if (!p.sealed) p.sort();\r
- for(int i=0; i<p.numedges; i++) {\r
- float x1 = p.x[p.edges[i]];\r
- float y1 = p.y[p.edges[i]];\r
- float x2 = p.x[p.edges[i]+1];\r
- float y2 = p.y[p.edges[i]+1];\r
- buf.drawLine((int)Math.floor(x1), (int)Math.floor(y1), (int)Math.ceil(x2), (int)Math.ceil(y2), color);\r
- }\r
- }\r
-\r
- /** finds the x value at which the line intercepts the line y=_y */\r
- private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {\r
- Polygon p = this;\r
- if (includeTop ? (_y < Math.min(p.y[i], p.y[i+1])) : (_y <= Math.min(p.y[i], p.y[i+1])))\r
- return Integer.MIN_VALUE;\r
- if (includeBottom ? (_y > Math.max(p.y[i], p.y[i+1])) : (_y >= Math.max(p.y[i], p.y[i+1])))\r
- return Integer.MIN_VALUE;\r
- float f = (((float)(p.x[i + 1] - p.x[i])) / ((float)(p.y[i + 1] - p.y[i])) ) * ((float)(_y - p.y[i])) + p.x[i];\r
- return (int)Math.floor(f);\r
- }\r
-\r
- /** fill the interior of the path */\r
- public void fill(PixelBuffer buf, Paint paint) {\r
- Polygon p = this;\r
- if (!p.sealed) p.sort();\r
- if (p.numedges == 0) return;\r
- float y0 = p.y[p.edges[0]], y1 = y0;\r
- boolean useEvenOdd = false;\r
-\r
- // we iterate over all endpoints in increasing y-coordinate order\r
- OUTER: for(int index = 1; index<p.numedges; index++) {\r
- int count = 0;\r
-\r
- // we now examine the horizontal band between y=y0 and y=y1\r
- y0 = y1;\r
- y1 = p.y[p.edges[index]];\r
- if (y0 == y1) continue;\r
-\r
- // within this band, we iterate over all p.edges\r
- int x0 = Integer.MIN_VALUE;\r
- int leftSegment = -1;\r
- while(true) {\r
- int x1 = Integer.MAX_VALUE;\r
- int rightSegment = Integer.MAX_VALUE;\r
- for(int i=0; i<p.numedges; i++) {\r
- if (p.y[p.edges[i]] == p.y[p.edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.\r
- // we order the segments by the x-coordinate of their midpoint;\r
- // since segments cannot intersect, this is a well-ordering\r
- int i0 = intercept(p.edges[i], y0, true, false);\r
- int i1 = intercept(p.edges[i], y1, false, true);\r
- if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;\r
- int midpoint = i0 + i1;\r
- if (midpoint < x0) continue;\r
- if (midpoint == x0 && i <= leftSegment) continue;\r
- if (midpoint > x1) continue;\r
- if (midpoint == x1 && i >= rightSegment) continue;\r
- rightSegment = i;\r
- x1 = midpoint;\r
- }\r
- if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;\r
- if (leftSegment != -1)\r
- if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0)) {\r
- int tx1a = intercept(p.edges[leftSegment], y0, true, true);\r
- int tx1b = intercept(p.edges[rightSegment], y0, true, true);\r
- int tx2a = intercept(p.edges[leftSegment], y1, true, true);\r
- int tx2b = intercept(p.edges[rightSegment], y1, true, true);\r
- buf.fillTrapezoid(tx1a, tx1b, (int)y0, tx2a, tx2b, (int)y1, ((Paint.SingleColorPaint)paint).color);\r
- }\r
- if (useEvenOdd) count++;\r
- else count += (p.y[p.edges[rightSegment]] < p.y[p.edges[rightSegment]+1]) ? -1 : 1;\r
- leftSegment = rightSegment; x0 = x1;\r
- }\r
- }\r
- }\r
-\r
- //////////////////////////////////////////////////////////////////////////////\r
-\r
- public Polygon sort() {\r
- closepath();\r
- contours[numcontours] = numvertices;\r
- sealed = true;\r
- numedges = 0;\r
- edges = new int[numvertices];\r
- for(int i=0; i<numcontours; i++)\r
- for(int j=contours[i]; j<contours[i+1]-1; j++)\r
- edges[numedges++] = j;\r
- sort(0, numedges - 1, false);\r
- return this;\r
- }\r
-\r
- /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */\r
- int sort(int left, int right, boolean partition) {\r
- if (partition) {\r
- int i, j, middle;\r
- middle = (left + right) / 2;\r
- int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;\r
- for (i = left - 1, j = right; ; ) {\r
- while (y[edges[++i]] < y[edges[right]]);\r
- while (j > left && y[edges[--j]] > y[edges[right]]);\r
- if (i >= j) break;\r
- s = edges[i]; edges[i] = edges[j]; edges[j] = s;\r
- }\r
- s = edges[right]; edges[right] = edges[i]; edges[i] = s;\r
- return i;\r
- } else {\r
- if (left >= right) return 0;\r
- int p = sort(left, right, true);\r
- sort(left, p - 1, false);\r
- sort(p + 1, right, false);\r
- return 0;\r
- }\r
- }\r
-\r
- // Rendering //////////////////////////////////////////////////////////////////////////////\r
-\r
- \r
- private static int bound(int min, int mid, int max) { return mid < min ? min : mid > max ? max : mid; }\r
-\r
- public String toString(int i) {\r
- String ret = " ";\r
- for(int j=contours[i]; j<contours[i+1]; j++) ret += x[j]+","+y[j];\r
- return ret + "\n";\r
- }\r
- public String toString() {\r
- String ret = "Polygon\n";\r
- for(int i=0; i<numcontours; i++) ret += toString(i);\r
- return ret;\r
- }\r
-\r
-\r
- // GPC //////////////////////////////////////////////////////////////////////////////\r
-\r
- //private static final float GPC_EPSILON = 2.2204460492503131e-016 ;\r
- private static final float GPC_EPSILON = (float)1e-8;\r
- private static final String GPC_VERSION = "2.31" ;\r
- private static final int LEFT = 0 ;\r
- private static final int RIGHT = 1 ;\r
- private static final int ABOVE = 0 ;\r
- private static final int BELOW = 1 ;\r
- private static final int CLIP = 0 ;\r
- private static final int SUBJ = 1 ;\r
- \r
- // evilbadnonthreadsafestuff\r
- private static ScanBeamList sbte = new ScanBeamList();\r
- private static EdgeTable s_heap = new EdgeTable();\r
- private static EdgeTable c_heap = new EdgeTable();\r
- private static LmtTable lmt_table = new LmtTable();\r
- private static TopPolygonNode out_poly = new TopPolygonNode();\r
- private static AetTree aet = new AetTree();\r
- private static ItNodeTable it_table = new ItNodeTable();\r
-\r
- private static Polygon clip(byte op, Polygon subj, Polygon clip) {\r
- try {\r
- return clip_(op, subj, clip);\r
- } catch (Exception npe) {\r
- npe.printStackTrace();\r
- return null;\r
- }\r
- }\r
- private static Polygon clip_(byte op, Polygon subj, Polygon clip) {\r
- int parity_CLIP = LEFT;\r
- int parity_SUBJ = LEFT;\r
- float[] sbt = null;\r
- int local_min = 0;\r
- int scanbeam = 0;\r
-\r
- numFreeEdgeNodes = numEdgeNodes;\r
-\r
- subj.closepath(); subj.contours[subj.numcontours] = subj.numvertices;\r
- clip.closepath(); clip.contours[clip.numcontours] = clip.numvertices;\r
- PolygonNode.clear();\r
-\r
- // Test for trivial NULL result cases \r
- if ((subj.isEmpty() && clip.isEmpty()) || (subj.isEmpty() && ((op == GPC_INT) || (op == GPC_DIFF))) ||\r
- (clip.isEmpty() && (op == GPC_INT)))\r
- { subj.clear(); return subj; }\r
- \r
- // Identify potentialy contributing contours \r
- if (((op == GPC_INT) || (op == GPC_DIFF)) && !subj.isEmpty() && !clip.isEmpty())\r
- minimax_test(subj, clip, op);\r
- \r
- // Build LMT \r
- lmt_table.clear();\r
- sbte.clear();\r
- s_heap.clear();\r
- c_heap.clear();\r
- if (!subj.isEmpty()) build_lmt(s_heap, lmt_table, sbte, subj, SUBJ, op);\r
- if (!clip.isEmpty()) build_lmt(c_heap, lmt_table, sbte, clip, CLIP, op);\r
- if (lmt_table.isEmpty()) { subj.clear(); return subj; } // Return a NULL result if no contours contribute\r
-\r
- // Build scanbeam table from scanbeam tree \r
- sbt = sbte.sort();\r
- // Invert clip polygon for difference operation \r
- if (op == GPC_DIFF) parity_CLIP = RIGHT;\r
- out_poly.clear();\r
- aet.clear();\r
- \r
- // Process each scanbeam \r
- while(scanbeam < sbte.entries) {\r
- // Set yb and yt to the bottom and top of the scanbeam \r
- float yb = sbt[scanbeam++];\r
- float yt = (float)0.0;\r
- float dy = (float)0.0;\r
- if (scanbeam < sbte.entries) { yt = sbt[scanbeam]; dy = yt - yb; }\r
- \r
- // === SCANBEAM BOUNDARY PROCESSING ================================ \r
- // If LMT node corresponding to yb exists \r
- if (local_min < lmt_table.numentries && lmt_table.y[local_min] == yb) {\r
- // Add edges starting at this local minimum to the AET \r
- for(EdgeNode edge = lmt_table.first_bound[local_min]; (edge != null); edge= edge.next_bound)\r
- add_edge_to_aet(aet, edge);\r
- local_min++;\r
- }\r
- \r
- float px = -Float.MAX_VALUE; // Set dummy previous x value\r
- EdgeNode e0 = aet.top_node; // Create bundles within AET\r
- EdgeNode e1 = aet.top_node;\r
- \r
- // Set up bundle fields of first edge \r
- if (aet.top_node.type == CLIP) aet.top_node.bundle_ABOVE_CLIP = (aet.top_node.top_y != yb) ? 1 : 0;\r
- else aet.top_node.bundle_ABOVE_SUBJ = (aet.top_node.top_y != yb) ? 1 : 0;\r
-\r
- if (((aet.top_node.type==0) ? 1 : 0) == CLIP) aet.top_node.bundle_ABOVE_CLIP = 0;\r
- else aet.top_node.bundle_ABOVE_SUBJ = 0;\r
- aet.top_node.bstate_ABOVE = UNBUNDLED;\r
-\r
- for (EdgeNode next_edge = aet.top_node.next; next_edge != null; next_edge = next_edge.next) {\r
- int ne_type = next_edge.type;\r
- int ne_type_opp = ((next_edge.type==0) ? 1 : 0); // next edge type opposite\r
- \r
- // Set up bundle fields of next edge \r
- if (ne_type == CLIP) next_edge.bundle_ABOVE_CLIP = (next_edge.top_y != yb) ? 1 : 0;\r
- else next_edge.bundle_ABOVE_SUBJ = (next_edge.top_y != yb) ? 1 : 0; \r
- if (ne_type_opp == CLIP) next_edge.bundle_ABOVE_CLIP = 0;\r
- else next_edge.bundle_ABOVE_SUBJ = 0; \r
- next_edge.bstate_ABOVE = UNBUNDLED;\r
- \r
- // Bundle edges above the scanbeam boundary if they coincide \r
- if ((ne_type == CLIP ? next_edge.bundle_ABOVE_CLIP : next_edge.bundle_ABOVE_SUBJ) == 1) {\r
- if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top_y != yb)) {\r
- if (ne_type == CLIP)\r
- next_edge.bundle_ABOVE_CLIP ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
- else next_edge.bundle_ABOVE_SUBJ ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
- if (ne_type_opp == CLIP)\r
- next_edge.bundle_ABOVE_CLIP = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
- else next_edge.bundle_ABOVE_SUBJ = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;\r
- next_edge.bstate_ABOVE = BUNDLE_HEAD;\r
- e0.bundle_ABOVE_CLIP = 0;\r
- e0.bundle_ABOVE_SUBJ = 0;\r
- e0.bstate_ABOVE = BUNDLE_TAIL;\r
- }\r
- e0 = next_edge;\r
- }\r
- }\r
- \r
- int horiz_CLIP = HState.NH;\r
- int horiz_SUBJ = HState.NH;\r
- int exists_CLIP = 0;\r
- int exists_SUBJ = 0;\r
- PolygonNode cf = null;\r
- \r
- // Process each edge at this scanbeam boundary \r
- for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {\r
- exists_CLIP = edge.bundle_ABOVE_CLIP + (edge.bundle_BELOW_CLIP << 1);\r
- exists_SUBJ = edge.bundle_ABOVE_SUBJ + (edge.bundle_BELOW_SUBJ << 1);\r
- \r
- if ((exists_CLIP != 0) || (exists_SUBJ != 0)) { // Set bundle side \r
- edge.bside_CLIP = parity_CLIP;\r
- edge.bside_SUBJ = parity_SUBJ;\r
- boolean contributing = false;\r
- int br=0, bl=0, tr=0, tl=0;\r
- // Determine contributing status and quadrant occupancies \r
- switch(op) {\r
- case GPC_DIFF:\r
- case GPC_INT:\r
- contributing= ((exists_CLIP!=0) && ((parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||\r
- ((exists_SUBJ!=0) && ((parity_CLIP!=0) || (horiz_CLIP!=0))) ||\r
- ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));\r
- br = ((parity_CLIP!=0) && (parity_SUBJ!=0)) ? 1 : 0;\r
- bl = (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) &&\r
- ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
- tr = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) !=0) && \r
- ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0)) !=0)) ? 1 : 0;\r
- tl = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) &&\r
- ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0))?1:0;\r
- break;\r
-\r
- case GPC_XOR:\r
- contributing= (exists_CLIP!=0) || (exists_SUBJ!=0);\r
- br= (parity_CLIP) ^ (parity_SUBJ);\r
- bl= (parity_CLIP ^ edge.bundle_ABOVE_CLIP) ^ (parity_SUBJ ^ edge.bundle_ABOVE_SUBJ);\r
- tr= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0));\r
- tl= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)\r
- ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ);\r
- break;\r
-\r
- case GPC_UNION:\r
- contributing= ((exists_CLIP!=0) && (!(parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||\r
- ((exists_SUBJ!=0) && (!(parity_CLIP!=0) || (horiz_CLIP!=0))) ||\r
- ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));\r
- br= ((parity_CLIP!=0) || (parity_SUBJ!=0))?1:0;\r
- bl= (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) || ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0))?1:0;\r
- tr= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0))!=0) || \r
- ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0))!=0)) ?1:0;\r
- tl= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) ||\r
- ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0)) ? 1:0;\r
- break;\r
- default: throw new IllegalStateException("Unknown op");\r
- }\r
- \r
- // Update parity \r
- parity_CLIP ^= edge.bundle_ABOVE_CLIP;\r
- parity_SUBJ ^= edge.bundle_ABOVE_SUBJ;\r
- \r
- // Update horizontal state \r
- if (exists_CLIP!=0) horiz_CLIP = HState.next_h_state[horiz_CLIP][((exists_CLIP - 1) << 1) + parity_CLIP];\r
- if (exists_SUBJ!=0) horiz_SUBJ = HState.next_h_state[horiz_SUBJ][((exists_SUBJ - 1) << 1) + parity_SUBJ];\r
- \r
- if (contributing) {\r
- float xb = edge.xb;\r
- int vclass = VertexType.getType(tr, tl, br, bl);\r
- switch (vclass) {\r
- case VertexType.EMN:\r
- case VertexType.IMN:\r
- edge.outp_ABOVE = out_poly.add_local_min(xb, yb);\r
- px = xb;\r
- cf = edge.outp_ABOVE;\r
- break;\r
- case VertexType.ERI:\r
- if (xb != px) { cf.add_right(xb, yb); px= xb; }\r
- edge.outp_ABOVE= cf;\r
- cf= null;\r
- break;\r
- case VertexType.ELI:\r
- edge.outp_BELOW.add_left(xb, yb);\r
- px= xb;\r
- cf= edge.outp_BELOW;\r
- break;\r
- case VertexType.EMX:\r
- if (xb != px) { cf.add_left(xb, yb); px= xb; }\r
- out_poly.merge_right(cf, edge.outp_BELOW);\r
- cf= null;\r
- break;\r
- case VertexType.ILI:\r
- if (xb != px) { cf.add_left(xb, yb); px= xb; }\r
- edge.outp_ABOVE= cf;\r
- cf= null;\r
- break;\r
- case VertexType.IRI:\r
- edge.outp_BELOW.add_right(xb, yb);\r
- px= xb;\r
- cf= edge.outp_BELOW;\r
- edge.outp_BELOW= null;\r
- break;\r
- case VertexType.IMX:\r
- if (xb != px) { cf.add_right(xb, yb); px= xb; }\r
- out_poly.merge_left(cf, edge.outp_BELOW);\r
- cf= null;\r
- edge.outp_BELOW= null;\r
- break;\r
- case VertexType.IMM:\r
- if (xb != px) { cf.add_right(xb, yb); px= xb; }\r
- out_poly.merge_left(cf, edge.outp_BELOW);\r
- edge.outp_BELOW= null;\r
- edge.outp_ABOVE = out_poly.add_local_min(xb, yb);\r
- cf= edge.outp_ABOVE;\r
- break;\r
- case VertexType.EMM:\r
- if (xb != px) { cf.add_left(xb, yb); px= xb; }\r
- out_poly.merge_right(cf, edge.outp_BELOW);\r
- edge.outp_BELOW= null;\r
- edge.outp_ABOVE = out_poly.add_local_min(xb, yb);\r
- cf= edge.outp_ABOVE;\r
- break;\r
- case VertexType.LED:\r
- if (edge.bot_y == yb) edge.outp_BELOW.add_left(xb, yb);\r
- edge.outp_ABOVE= edge.outp_BELOW;\r
- px= xb;\r
- break;\r
- case VertexType.RED:\r
- if (edge.bot_y == yb) edge.outp_BELOW.add_right(xb, yb);\r
- edge.outp_ABOVE= edge.outp_BELOW;\r
- px= xb;\r
- break;\r
- default:\r
- break;\r
- } // End of switch \r
- } // End of contributing conditional \r
- } // End of edge exists conditional \r
- } // End of AET loop \r
- \r
- // Delete terminating edges from the AET, otherwise compute xt \r
- for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {\r
- if (edge.top_y == yb) {\r
- EdgeNode prev_edge = edge.prev;\r
- EdgeNode next_edge= edge.next;\r
- \r
- if (prev_edge != null) prev_edge.next = next_edge;\r
- else aet.top_node = next_edge;\r
- if (next_edge != null) next_edge.prev = prev_edge;\r
- \r
- // Copy bundle head state to the adjacent tail edge if required \r
- if ((edge.bstate_BELOW == BUNDLE_HEAD) && (prev_edge!=null)) {\r
- if (prev_edge.bstate_BELOW == BUNDLE_TAIL) {\r
- prev_edge.outp_BELOW= edge.outp_BELOW;\r
- prev_edge.bstate_BELOW= UNBUNDLED;\r
- if (prev_edge.prev != null) {\r
- if (prev_edge.prev.bstate_BELOW == BUNDLE_TAIL)\r
- prev_edge.bstate_BELOW = BUNDLE_HEAD;\r
- }\r
- }\r
- }\r
- } else {\r
- if (edge.top_y == yt) edge.xt = edge.top_x;\r
- else edge.xt= edge.bot_x + edge.dx * (yt - edge.bot_y);\r
- }\r
- }\r
- \r
- if (scanbeam < sbte.entries) {\r
- // === SCANBEAM INTERIOR PROCESSING ============================== \r
- // Build intersection table for the current scanbeam \r
- it_table.clear();\r
- it_table.build_intersection_table(aet, dy);\r
- \r
- // Process each node in the intersection table \r
- for (int intersect = 0; intersect < it_table.num; intersect++) {\r
- e0 = it_table.ie_0[intersect];\r
- e1 = it_table.ie_1[intersect];\r
- \r
- // Only generate output for contributing intersections \r
- if (((e0.bundle_ABOVE_CLIP!=0) || (e0.bundle_ABOVE_SUBJ!=0)) &&\r
- ((e1.bundle_ABOVE_CLIP!=0) || (e1.bundle_ABOVE_SUBJ!=0))) {\r
-\r
- PolygonNode p = e0.outp_ABOVE;\r
- PolygonNode q = e1.outp_ABOVE;\r
- float ix = it_table.x[intersect];\r
- float iy = it_table.y[intersect] + yb;\r
- \r
- int in_clip = (((e0.bundle_ABOVE_CLIP!=0) && !(e0.bside_CLIP!=0)) ||\r
- ((e1.bundle_ABOVE_CLIP!=0) && (e1.bside_CLIP!=0)) ||\r
- (!(e0.bundle_ABOVE_CLIP!=0) && !(e1.bundle_ABOVE_CLIP!=0) &&\r
- (e0.bside_CLIP!=0) && (e1.bside_CLIP!=0))) ? 1 : 0;\r
- \r
- int in_subj = (((e0.bundle_ABOVE_SUBJ!=0) && !(e0.bside_SUBJ!=0)) ||\r
- ((e1.bundle_ABOVE_SUBJ!=0) && (e1.bside_SUBJ!=0)) ||\r
- (!(e0.bundle_ABOVE_SUBJ!=0) && !(e1.bundle_ABOVE_SUBJ!=0) &&\r
- (e0.bside_SUBJ!=0) && (e1.bside_SUBJ!=0))) ? 1 : 0;\r
- \r
- int tr=0, tl=0, br=0, bl=0;\r
- // Determine quadrant occupancies \r
- switch(op) {\r
- case GPC_DIFF:\r
- case GPC_INT:\r
- tr= ((in_clip!=0) && (in_subj!=0)) ? 1 : 0;\r
- tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0))?1:0;\r
- br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0))?1:0;\r
- bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) &&\r
- ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1:0;\r
- break;\r
- case GPC_XOR:\r
- tr= (in_clip)^ (in_subj);\r
- tl= (in_clip ^ e1.bundle_ABOVE_CLIP) ^ (in_subj ^ e1.bundle_ABOVE_SUBJ);\r
- br= (in_clip ^ e0.bundle_ABOVE_CLIP) ^ (in_subj ^ e0.bundle_ABOVE_SUBJ);\r
- bl= (in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)\r
- ^ (in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ);\r
- break;\r
- case GPC_UNION:\r
- tr= ((in_clip!=0) || (in_subj!=0)) ? 1 : 0;\r
- tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
- br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
- bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) ||\r
- ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;\r
- break;\r
- default: throw new IllegalStateException("Unknown op type, "+op);\r
- }\r
- \r
- int vclass = VertexType.getType(tr, tl, br, bl);\r
- switch (vclass) {\r
- case VertexType.EMN:\r
- e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
- e1.outp_ABOVE = e0.outp_ABOVE;\r
- break;\r
- case VertexType.ERI:\r
- if (p != null) { p.add_right(ix, iy); e1.outp_ABOVE= p; e0.outp_ABOVE= null; }\r
- break;\r
- case VertexType.ELI:\r
- if (q != null) { q.add_left(ix, iy); e0.outp_ABOVE= q; e1.outp_ABOVE= null; }\r
- break;\r
- case VertexType.EMX:\r
- if ((p!=null) && (q!=null)) {\r
- p.add_left(ix, iy);\r
- out_poly.merge_right(p, q);\r
- e0.outp_ABOVE= null;\r
- e1.outp_ABOVE= null;\r
- }\r
- break;\r
- case VertexType.IMN:\r
- e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
- e1.outp_ABOVE = e0.outp_ABOVE;\r
- break;\r
- case VertexType.ILI:\r
- if (p != null) {\r
- p.add_left(ix, iy);\r
- e1.outp_ABOVE= p;\r
- e0.outp_ABOVE= null;\r
- }\r
- break;\r
- case VertexType.IRI:\r
- if (q!=null) {\r
- q.add_right(ix, iy);\r
- e0.outp_ABOVE= q;\r
- e1.outp_ABOVE= null;\r
- }\r
- break;\r
- case VertexType.IMX:\r
- if ((p!=null) && (q!=null)) {\r
- p.add_right(ix, iy);\r
- out_poly.merge_left(p, q);\r
- e0.outp_ABOVE= null;\r
- e1.outp_ABOVE= null;\r
- }\r
- break;\r
- case VertexType.IMM:\r
- if ((p!=null) && (q!=null)) {\r
- p.add_right(ix, iy);\r
- out_poly.merge_left(p, q);\r
- e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
- e1.outp_ABOVE= e0.outp_ABOVE;\r
- }\r
- break;\r
- case VertexType.EMM:\r
- if ((p!=null) && (q!=null)) {\r
- p.add_left(ix, iy);\r
- out_poly.merge_right(p, q);\r
- e0.outp_ABOVE = out_poly.add_local_min(ix, iy);\r
- e1.outp_ABOVE = e0.outp_ABOVE;\r
- }\r
- break;\r
- default: break;\r
- } // End of switch \r
- } // End of contributing intersection conditional \r
- \r
- // Swap bundle sides in response to edge crossing \r
- if (e0.bundle_ABOVE_CLIP!=0) e1.bside_CLIP = (e1.bside_CLIP==0)?1:0;\r
- if (e1.bundle_ABOVE_CLIP!=0) e0.bside_CLIP= (e0.bside_CLIP==0)?1:0;\r
- if (e0.bundle_ABOVE_SUBJ!=0) e1.bside_SUBJ= (e1.bside_SUBJ==0)?1:0;\r
- if (e1.bundle_ABOVE_SUBJ!=0) e0.bside_SUBJ= (e0.bside_SUBJ==0)?1:0;\r
-\r
- // Swap e0 and e1 bundles in the AET \r
- EdgeNode prev_edge = e0.prev;\r
- EdgeNode next_edge = e1.next;\r
- if (next_edge != null) next_edge.prev = e0;\r
- \r
- if (e0.bstate_ABOVE == BUNDLE_HEAD) {\r
- boolean search = true;\r
- while (search) {\r
- prev_edge= prev_edge.prev;\r
- if (prev_edge != null) {\r
- if (prev_edge.bstate_ABOVE != BUNDLE_TAIL)\r
- search= false;\r
- } else {\r
- search= false;\r
- }\r
- }\r
- }\r
- if (prev_edge == null) {\r
- aet.top_node.prev = e1;\r
- e1.next = aet.top_node;\r
- aet.top_node = e0.next;\r
- } else {\r
- prev_edge.next.prev = e1;\r
- e1.next = prev_edge.next;\r
- prev_edge.next = e0.next;\r
- }\r
- e0.next.prev = prev_edge;\r
- e1.next.prev = e1;\r
- e0.next = next_edge;\r
- } // End of IT loop\r
- \r
- // Prepare for next scanbeam \r
- for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {\r
- EdgeNode next_edge = edge.next;\r
- EdgeNode succ_edge = edge.succ;\r
- if ((edge.top_y == yt) && (succ_edge!=null)) {\r
- // Replace AET edge by its successor \r
- succ_edge.outp_BELOW= edge.outp_ABOVE;\r
- succ_edge.bstate_BELOW= edge.bstate_ABOVE;\r
- succ_edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;\r
- succ_edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;\r
- EdgeNode prev_edge = edge.prev;\r
- if (prev_edge != null) prev_edge.next = succ_edge;\r
- else aet.top_node = succ_edge;\r
- if (next_edge != null) next_edge.prev= succ_edge;\r
- succ_edge.prev = prev_edge;\r
- succ_edge.next = next_edge;\r
- } else {\r
- // Update this edge \r
- edge.outp_BELOW= edge.outp_ABOVE;\r
- edge.bstate_BELOW= edge.bstate_ABOVE;\r
- edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;\r
- edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;\r
- edge.xb= edge.xt;\r
- }\r
- edge.outp_ABOVE= null;\r
- }\r
- }\r
- } // === END OF SCANBEAM PROCESSING ================================== \r
-\r
- // Generate result polygon from out_poly \r
- subj.clear();\r
- return out_poly.getResult(subj);\r
- }\r
- \r
- private static boolean EQ(float a, float b) { return (Math.abs(a - b) <= GPC_EPSILON); }\r
- private static int PREV_INDEX(int i, int n) { return ((i - 1 + n) % n); }\r
- private static int NEXT_INDEX(int i, int n) { return ((i + 1 ) % n); }\r
- private static boolean OPTIMAL(Polygon p, int index, int i) {\r
- return (p.y[p.contours[index] + PREV_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]) ||\r
- (p.y[p.contours[index] + NEXT_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]);\r
- }\r
- \r
- private static void minimax_test(Polygon subj, Polygon clip, byte op) {\r
- // For each clip contour, search for any subject contour overlaps \r
- for(int c=0; c < clip.numcontours; c++) {\r
- boolean overlap = false;\r
- for(int s = 0; !overlap && (s < subj.numcontours); s++)\r
- overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&\r
- (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));\r
- clip.contributing[c] = overlap;\r
- } \r
- if (op != GPC_INT) return;\r
- // For each subject contour, search for any clip contour overlaps \r
- for (int s=0; s < subj.numcontours; s++) {\r
- boolean overlap = false;\r
- for (int c=0; !overlap && (c < clip.numcontours); c++)\r
- overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&\r
- (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));\r
- subj.contributing[s] = overlap;\r
- }\r
- }\r
-\r
- private static void insert_bound(LmtTable lmt_table, float y, EdgeNode e) {\r
- int index = lmt_table.add(y, null);\r
- // Link node e to the tail of the list \r
- if (lmt_table.first_bound[index] == null) { lmt_table.first_bound[index] = e; return; }\r
- EdgeNode prev_bound = null;\r
- EdgeNode current_bound = lmt_table.first_bound[index];\r
- while(true)\r
- // Do primary sort on the x field \r
- if (e.bot_x < current_bound.bot_x) {\r
- // Insert a new node mid-list \r
- if (prev_bound == null) lmt_table.first_bound[index] = e;\r
- else prev_bound.next_bound = e;\r
- e.next_bound = current_bound;\r
- break;\r
- } else if (e.bot_x == current_bound.bot_x) {\r
- // Do secondary sort on the dx field \r
- if (e.dx < current_bound.dx) {\r
- // Insert a new node mid-list \r
- if (prev_bound == null) lmt_table.first_bound[index] = e;\r
- else prev_bound.next_bound = e;\r
- e.next_bound = current_bound;\r
- break;\r
- }\r
- // Head further down the list \r
- if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }\r
- prev_bound = current_bound;\r
- current_bound = current_bound.next_bound;\r
- } else {\r
- // Head further down the list \r
- if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }\r
- prev_bound = current_bound;\r
- current_bound = current_bound.next_bound;\r
- }\r
- }\r
- \r
- private static void add_edge_to_aet(AetTree aet, EdgeNode edge) {\r
- if (aet.top_node == null) {\r
- // Append edge onto the tail end of the AET \r
- aet.top_node = edge;\r
- edge.prev = null;\r
- edge.next= null;\r
- return;\r
- }\r
- EdgeNode current_edge = aet.top_node;\r
- EdgeNode prev = null;\r
- while(true)\r
- // Do primary sort on the xb field \r
- if (edge.xb < current_edge.xb) {\r
- // Insert edge here (before the AET edge) \r
- edge.prev= prev;\r
- edge.next= current_edge;\r
- current_edge.prev = edge;\r
- if (prev == null) aet.top_node = edge;\r
- else prev.next = edge;\r
- break;\r
- } else if (edge.xb == current_edge.xb) {\r
- // Do secondary sort on the dx field \r
- if (edge.dx < current_edge.dx) {\r
- // Insert edge here (before the AET edge) \r
- edge.prev= prev;\r
- edge.next= current_edge;\r
- current_edge.prev = edge;\r
- if (prev == null) aet.top_node = edge;\r
- else prev.next = edge;\r
- break;\r
- }\r
- // Head further into the AET \r
- prev = current_edge;\r
- if (current_edge.next == null) {\r
- current_edge.next = edge;\r
- edge.prev = current_edge;\r
- edge.next = null;\r
- break;\r
- }\r
- current_edge = current_edge.next;\r
- } else {\r
- // Head further into the AET \r
- prev = current_edge;\r
- if (current_edge.next == null) {\r
- current_edge.next = edge;\r
- edge.prev = current_edge;\r
- edge.next = null;\r
- break;\r
- }\r
- current_edge = current_edge.next;\r
- }\r
- }\r
-\r
- private static void build_lmt(EdgeTable edge_table, LmtTable lmt_table, ScanBeamList sbte, Polygon p, int type, byte op) {\r
- for (int c=0; c < p.numcontours; c++) {\r
- if (!p.contributing[c]) { p.contributing[c] = true; continue; }\r
- // Perform contour optimisation \r
- int num_vertices= 0;\r
- int e_index = 0;\r
- edge_table.clear();\r
- for (int i= 0; i < p.contours[c+1] - p.contours[c]; i++)\r
- if (OPTIMAL(p, c, i)) {\r
- edge_table.addNode(p.x[p.contours[c]+i], p.y[p.contours[c]+i]);\r
- sbte.add(p.y[p.contours[c]+i]); // Record vertex in the scanbeam table \r
- num_vertices++;\r
- }\r
- \r
- // Do the contour forward pass \r
- for (int min= 0; min < num_vertices; min++) {\r
- // If a forward local minimum... \r
- if (edge_table.FWD_MIN(min)) {\r
- // Search for the next local maximum... \r
- int num_edges = 1;\r
- int max = NEXT_INDEX(min, num_vertices);\r
- while(edge_table.NOT_FMAX(max)) { num_edges++; max = NEXT_INDEX(max, num_vertices); }\r
-\r
- // Build the next edge list \r
- int v = min;\r
- EdgeNode e = edge_table.getNode(e_index);\r
- e.bstate_BELOW = UNBUNDLED;\r
- e.bundle_BELOW_CLIP = 0;\r
- e.bundle_BELOW_SUBJ = 0;\r
- \r
- for (int i= 0; i < num_edges; i++) {\r
- EdgeNode ei = edge_table.getNode(e_index+i);\r
- EdgeNode ev = edge_table.getNode(v);\r
- ei.xb = ev.vertex_x;\r
- ei.bot_x = ev.vertex_x;\r
- ei.bot_y = ev.vertex_y;\r
- v = NEXT_INDEX(v, num_vertices);\r
- ev = edge_table.getNode(v);\r
- ei.top_x= ev.vertex_x;\r
- ei.top_y= ev.vertex_y;\r
- ei.dx= (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);\r
- ei.type = type;\r
- ei.outp_ABOVE = null;\r
- ei.outp_BELOW = null;\r
- ei.next = null;\r
- ei.prev = null;\r
- ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;\r
- ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;\r
- ei.next_bound = null;\r
- ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;\r
- ei.bside_SUBJ = LEFT;\r
- }\r
- insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);\r
- e_index += num_edges;\r
- }\r
- }\r
-\r
- // Do the contour reverse pass \r
- for (int min= 0; min < num_vertices; min++) {\r
- // If a reverse local minimum... \r
- if (edge_table.REV_MIN(min)) {\r
- // Search for the previous local maximum... \r
- int num_edges= 1;\r
- int max = PREV_INDEX(min, num_vertices);\r
- while(edge_table.NOT_RMAX(max)) { num_edges++; max = PREV_INDEX(max, num_vertices); }\r
- // Build the previous edge list \r
- int v = min;\r
- EdgeNode e = edge_table.getNode(e_index);\r
- e.bstate_BELOW = UNBUNDLED;\r
- e.bundle_BELOW_CLIP = 0;\r
- e.bundle_BELOW_SUBJ = 0;\r
- for (int i= 0; i < num_edges; i++) {\r
- EdgeNode ei = edge_table.getNode(e_index+i);\r
- EdgeNode ev = edge_table.getNode(v);\r
- ei.xb = ev.vertex_x;\r
- ei.bot_x = ev.vertex_x;\r
- ei.bot_y = ev.vertex_y;\r
- v= PREV_INDEX(v, num_vertices);\r
- ev = edge_table.getNode(v);\r
- ei.top_x = ev.vertex_x;\r
- ei.top_y = ev.vertex_y;\r
- ei.dx = (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);\r
- ei.type = type;\r
- ei.outp_ABOVE = null;\r
- ei.outp_BELOW = null;\r
- ei.next = null;\r
- ei.prev = null;\r
- ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;\r
- ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;\r
- ei.next_bound = null;\r
- ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;\r
- ei.bside_SUBJ = LEFT;\r
- }\r
- insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);\r
- e_index+= num_edges;\r
- }\r
- }\r
- }\r
- }\r
-\r
- public static final byte GPC_DIFF = 0;\r
- public static final byte GPC_INT = 1;\r
- public static final byte GPC_XOR = 2;\r
- public static final byte GPC_UNION = 3;\r
-\r
- // Edge intersection classes\r
- private static class VertexType {\r
- public static final int NUL = 0; // Empty non-intersection \r
- public static final int EMX = 1; // External maximum \r
- public static final int ELI = 2; // External left intermediate \r
- public static final int TED = 3; // Top edge \r
- public static final int ERI = 4; // External right intermediate \r
- public static final int RED = 5; // Right edge \r
- public static final int IMM = 6; // Internal maximum and minimum \r
- public static final int IMN = 7; // Internal minimum \r
- public static final int EMN = 8; // External minimum \r
- public static final int EMM = 9; // External maximum and minimum \r
- public static final int LED = 10; // Left edge \r
- public static final int ILI = 11; // Internal left intermediate \r
- public static final int BED = 12; // Bottom edge \r
- public static final int IRI = 13; // Internal right intermediate \r
- public static final int IMX = 14; // Internal maximum \r
- public static final int FUL = 15; // Full non-intersection \r
- public static int getType(int tr, int tl, int br, int bl) { return tr + (tl << 1) + (br << 2) + (bl << 3); }\r
- }\r
- \r
- private static class HState {\r
- public static final int NH = 0; // No horizontal edge \r
- public static final int BH = 1; // Bottom horizontal edge \r
- public static final int TH = 2; // Top horizontal edge \r
- // Horizontal edge state transitions within scanbeam boundary \r
- public static final int[][] next_h_state =\r
- {\r
- // ABOVE BELOW CROSS \r
- // L R L R L R \r
- /* NH */ {BH, TH, TH, BH, NH, NH},\r
- /* BH */ {NH, NH, NH, NH, TH, TH},\r
- /* TH */ {NH, NH, NH, NH, BH, BH}\r
- };\r
- }\r
- \r
- public static final byte UNBUNDLED = 0; // Isolated edge not within a bundle\r
- public static final byte BUNDLE_HEAD = 1; // Bundle head node\r
- public static final byte BUNDLE_TAIL = 2; // Passive bundle tail node\r
-\r
- private static class PolygonNode {\r
- public static void clear() { numvertices = 1; }\r
- private static final float[] x = new float[BIGNUM];\r
- private static final float[] y = new float[BIGNUM];\r
- private static final int[] nxt = new int[BIGNUM];\r
- private static int numvertices = 1;\r
-\r
- int active = 1; // Active flag / vertex count \r
- boolean hole; // Hole / external contour flag \r
- int v_LEFT; // Left and right vertex list ptrs \r
- int v_RIGHT; // Left and right vertex list ptrs \r
- PolygonNode next; // Pointer to next polygon contour \r
- PolygonNode proxy; // Pointer to actual structure used \r
- \r
- public PolygonNode(PolygonNode next, float x0, float y0) {\r
- // Make v_LEFT and v_RIGHT point to new vertex \r
- x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;\r
- this.v_LEFT = numvertices;\r
- this.v_RIGHT = numvertices;\r
- numvertices++;\r
- this.proxy = this; // Initialise proxy to point to p itself \r
- this.next = next;\r
- }\r
- public void merge(PolygonNode q) { nxt[proxy.v_RIGHT] = q.proxy.v_LEFT; q.proxy.v_LEFT = proxy.v_LEFT; }\r
- public void mergeRight(PolygonNode p) { nxt[proxy.v_RIGHT] = p.proxy.v_LEFT; proxy.v_RIGHT = p.proxy.v_RIGHT; }\r
- public void addSelfTo(Polygon poly) {\r
- for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) poly.add(x[vtx], y[vtx]);\r
- poly.newcontour();\r
- }\r
- public int count() { int ret = 0; for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) ret++; return ret; }\r
- public void add_right(float x0, float y0) {\r
- x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;\r
- nxt[proxy.v_RIGHT] = numvertices;\r
- proxy.v_RIGHT = numvertices;\r
- numvertices++;\r
- }\r
- public void add_left(float x0, float y0) {\r
- x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;\r
- nxt[numvertices] = proxy.v_LEFT;\r
- proxy.v_LEFT = numvertices;\r
- numvertices++;\r
- }\r
- }\r
-\r
- private static class TopPolygonNode {\r
- PolygonNode top_node = null;\r
- public void clear() { top_node = null; }\r
- public PolygonNode add_local_min(float x, float y) {\r
- PolygonNode existing_min = top_node;\r
- top_node = new PolygonNode(existing_min, x, y);\r
- return top_node;\r
- }\r
- public void merge_left(PolygonNode p, PolygonNode q) {\r
- // Label contour as a hole \r
- q.proxy.hole = true;\r
- if (p.proxy == q.proxy) return;\r
- // Assign p's vertex list to the left end of q's list \r
- p.merge(q);\r
- // Redirect any p.proxy references to q.proxy \r
- PolygonNode target = p.proxy;\r
- for(PolygonNode node = top_node; (node != null); node = node.next)\r
- if (node.proxy == target) { node.active= 0; node.proxy= q.proxy; }\r
- }\r
-\r
- public void merge_right(PolygonNode p, PolygonNode q) {\r
- // Label contour as external \r
- q.proxy.hole = false;\r
- if (p.proxy == q.proxy) return;\r
- // Assign p's vertex list to the right end of q's list \r
- q.mergeRight(p);\r
- // Redirect any p->proxy references to q->proxy \r
- PolygonNode target = p.proxy;\r
- for (PolygonNode node = top_node; (node != null); node = node.next)\r
- if (node.proxy == target) { node.active = 0; node.proxy= q.proxy; }\r
- }\r
- \r
- public int count_contours() {\r
- int nc = 0;\r
- for (PolygonNode polygon = top_node; (polygon != null); polygon = polygon.next)\r
- if (polygon.active != 0) {\r
- // Count the vertices in the current contour \r
- int nv= polygon.proxy.count();\r
- // Record valid vertex counts in the active field \r
- if (nv > 2) { polygon.active = nv; nc++; }\r
- else polygon.active= 0;\r
- }\r
- return nc;\r
- }\r
- \r
- public Polygon getResult(Polygon result) {\r
- int num_contours = count_contours();\r
- if (num_contours <= 0) return result;\r
- int c= 0;\r
- PolygonNode npoly_node = null;\r
- for (PolygonNode poly_node = top_node; (poly_node != null); poly_node = npoly_node) {\r
- npoly_node = poly_node.next;\r
- if (poly_node.active == 0) continue;\r
- int prepoly = result.numcontours;\r
- // This algorithm puts the verticies into the poly in reverse order\r
- poly_node.proxy.addSelfTo(result);\r
- if (poly_node.proxy.hole) {\r
- for(int i=prepoly; i<result.numcontours; i++)\r
- result.hole[i] = poly_node.proxy.hole;\r
- }\r
- c++;\r
- }\r
- return result;\r
- }\r
- }\r
- \r
- private static EdgeNode[] allEdgeNodes = new EdgeNode[BIGNUM];\r
- private static int numEdgeNodes = 0;\r
- private static int numFreeEdgeNodes = 0;\r
- private static EdgeNode newEdgeNode(float x, float y) {\r
- if (numFreeEdgeNodes == 0) {\r
- return allEdgeNodes[numEdgeNodes++] = new EdgeNode(x, y);\r
- } else {\r
- EdgeNode ret = allEdgeNodes[--numFreeEdgeNodes];\r
- ret.vertex_x = x;\r
- ret.vertex_y = y;\r
- return ret;\r
- }\r
- }\r
- private static class EdgeNode {\r
- float vertex_x;\r
- float vertex_y;\r
- float top_x;\r
- float top_y;\r
- float bot_x;\r
- float bot_y;\r
- float xb; // Scanbeam bottom x coordinate \r
- float xt; // Scanbeam top x coordinate \r
- float dx; // Change in x for a unit y increase \r
- int type; // Clip / subject edge flag \r
- int bundle_ABOVE_CLIP;\r
- int bundle_ABOVE_SUBJ;\r
- int bundle_BELOW_CLIP;\r
- int bundle_BELOW_SUBJ;\r
- int bside_CLIP;\r
- int bside_SUBJ;\r
- byte bstate_ABOVE;\r
- byte bstate_BELOW;\r
- PolygonNode outp_ABOVE; // Output polygon / tristrip pointer \r
- PolygonNode outp_BELOW; // Output polygon / tristrip pointer \r
- EdgeNode prev; // Previous edge in the AET \r
- EdgeNode next; // Next edge in the AET \r
- EdgeNode pred; // Edge connected at the lower end \r
- EdgeNode succ; // Edge connected at the upper end \r
- EdgeNode next_bound; // Pointer to next bound in LMT \r
- public EdgeNode(float x, float y) { vertex_x = x; vertex_y = y; }\r
- }\r
- private static class AetTree { EdgeNode top_node; public void clear() { top_node = null; } }\r
-\r
- private static class EdgeTable {\r
- public EdgeNode[] edges = new EdgeNode[BIGNUM];\r
- public int entries;\r
- public void clear() { for(; entries >= 0; entries--) edges[entries] = null; entries = 0; }\r
- public void addNode(float x, float y) { edges[entries++] = newEdgeNode(x, y); }\r
- public EdgeNode getNode(int index) { return edges[index]; }\r
- public boolean NOT_RMAX(int i) { return (edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }\r
- public boolean NOT_FMAX(int i) { return(edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }\r
- public boolean FWD_MIN(int i) {\r
- return ((edges[PREV_INDEX(i, entries)].vertex_y >= edges[i].vertex_y) &&\r
- (edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y));\r
- }\r
- public boolean REV_MIN(int i) {\r
- return ((edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y) &&\r
- (edges[NEXT_INDEX(i, entries)].vertex_y >= edges[i].vertex_y));\r
- }\r
- }\r
-\r
- private static class LmtTable {\r
- float[] y = new float[BIGNUM];\r
- EdgeNode[] first_bound = new EdgeNode[BIGNUM];\r
- int numentries = 0;\r
- public void clear() { for(; numentries >= 0; numentries--) first_bound[numentries] = null; numentries = 0; }\r
- public int count() { return numentries; }\r
- public boolean isEmpty() { return numentries == 0; }\r
- public int add(float y0, EdgeNode e) {\r
- for(int i=0; i<numentries; i++)\r
- if (y[i] == y0) return i;\r
- else if (y[i] > y0) {\r
- System.arraycopy(y, i, y, i+1, numentries-i);\r
- System.arraycopy(first_bound, i, first_bound, i+1, numentries-i);\r
- y[i] = y0;\r
- first_bound[i] = e;\r
- numentries++;\r
- return i;\r
- }\r
- y[numentries] = y0;\r
- first_bound[numentries] = e;\r
- return numentries++;\r
- }\r
- }\r
-\r
- private static class ScanBeamList {\r
- public int entries = 0;\r
- public float[] floats = new float[BIGNUM];\r
- public void clear() { entries = 0; }\r
- public void add(float f) { floats[entries++] = f; }\r
- public float[] sort() {\r
- org.ibex.util.Vec.sortFloats(floats, 0, entries-1);\r
- int j = 0;\r
- for(int i=1; i<entries; i++) if (floats[j] != floats[i]) floats[++j] = floats[i];\r
- entries = j+1;\r
- return floats;\r
- }\r
- }\r
- \r
- private static class ItNodeTable {\r
- EdgeNode ie_0[] = new EdgeNode[BIGNUM];\r
- EdgeNode ie_1[] = new EdgeNode[BIGNUM];\r
- float x[] = new float[BIGNUM];\r
- float y[] = new float[BIGNUM];\r
- int num = 0;\r
- public void clear() { for(; num>=0; num--) { ie_0[num] = null; ie_1[num] = null; } num = 0; }\r
- public void build_intersection_table(AetTree aet, float dy) {\r
- int st = -1;\r
- // Process each AET edge \r
- for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next)\r
- if ((edge.bstate_ABOVE == BUNDLE_HEAD) ||\r
- (edge.bundle_ABOVE_CLIP != 0) || (edge.bundle_ABOVE_SUBJ != 0))\r
- st = add_st_edge(st, edge, dy);\r
- sort(0, num-1);\r
- for(;numst>=0; numst--) edge[numst] = null; numst = 0;\r
- }\r
- \r
- int numst = 0;\r
- EdgeNode edge[] = new EdgeNode[BIGNUM]; // Pointer to AET edge \r
- float xb[] = new float[BIGNUM]; // Scanbeam bottom x coordinate \r
- float xt[] = new float[BIGNUM]; // Scanbeam top x coordinate \r
- float dx[] = new float[BIGNUM]; // Change in x for a unit y increase \r
- int prev[] = new int[BIGNUM]; // Previous edge in sorted list \r
-\r
- private int add_st_edge(int st, EdgeNode e, float dy) {\r
- if (st == -1) { st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; prev[st] = -1; return st; }\r
- float den = (xt[st] - xb[st]) - (e.xt - e.xb);\r
-\r
- // If new edge and ST edge don't cross, No intersection - insert edge here (before the ST edge) \r
- if ((e.xt >= xt[st]) || (e.dx == dx[st]) || (Math.abs(den) <= GPC_EPSILON))\r
- { prev[numst] = st; st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; return st; }\r
-\r
- // Compute intersection between new edge and ST edge \r
- float r = (e.xb - xb[st]) / den;\r
- float x = xb[st] + r * (xt[st] - xb[st]);\r
- float y = r * dy;\r
- // Insert the edge pointers and the intersection point in the IT \r
- add_intersection(edge[st], e, x, y);\r
- prev[st] = add_st_edge(prev[st], e, dy);\r
- return st;\r
- }\r
- private void add_intersection(EdgeNode edge0, EdgeNode edge1, float x0, float y0) {\r
- ie_0[num] = edge0; ie_1[num] = edge1; x[num] = x0; y[num] = y0; num++; }\r
-\r
- public final void sort(int start, int end) {\r
- if(start >= end) return;\r
- if(end-start <= 6) {\r
- for(int i=start+1;i<=end;i++) {\r
- float tmpa = y[i];\r
- float tmpx = x[i];\r
- EdgeNode tmpe0 = ie_0[i];\r
- EdgeNode tmpe1 = ie_1[i];\r
- int j;\r
- for(j=i-1;j>=start;j--) {\r
- if(y[j] <= tmpa) break;\r
- y[j+1] = y[j];\r
- x[j+1] = x[j];\r
- ie_0[j+1] = ie_0[j];\r
- ie_1[j+1] = ie_1[j];\r
- }\r
- y[j+1] = tmpa;\r
- x[j+1] = tmpx;\r
- ie_0[j+1] = tmpe0;\r
- ie_1[j+1] = tmpe1;\r
- }\r
- return;\r
- }\r
- float pivot = y[end];\r
- int lo = start - 1;\r
- int hi = end;\r
- do {\r
- while(y[++lo] < pivot) { }\r
- while((hi > lo) && y[--hi] > pivot) { }\r
- swap(lo, hi);\r
- } while(lo < hi);\r
- swap(lo, end);\r
- sort(start, lo-1);\r
- sort(lo+1, end);\r
- }\r
- private final void swap(int a, int b) {\r
- if(a != b) {\r
- float tmp = x[a]; x[a] = x[b]; x[b] = tmp;\r
- tmp = y[a]; y[a] = y[b]; y[b] = tmp;\r
- EdgeNode tmpe = ie_0[a]; ie_0[a] = ie_0[b]; ie_0[b] = tmpe;\r
- tmpe = ie_1[a]; ie_1[a] = ie_1[b]; ie_1[b] = tmpe;\r
- }\r
- }\r
- }\r
-\r
-}\r
public void drawGlyph(Font.Glyph source, int dx, int dy, int cx1, int cy1, int cx2, int cy2, int argb, int bc) {
}
*/
- public void stroke(Polygon p, int color) {
+ public void stroke(Mesh p, int color) {
// FIXME
}
- public void fill(Polygon p, Paint paint) {
+ public void fill(Mesh p, Paint paint) {
// FIXME
}
g.drawLine(x1, y1, x2, y2);
}
- public void stroke(org.ibex.graphics.Polygon p, int color) { p.stroke(this, color); }
- public void fill(org.ibex.graphics.Polygon p, org.ibex.graphics.Paint paint) { p.fill(this, paint); }
+ public void stroke(org.ibex.graphics.Mesh p, int color) { /*p.stroke(this, color);*/ }
+ public void fill(org.ibex.graphics.Mesh p, org.ibex.graphics.Paint paint) { /*p.fill(this, paint);*/ }
private static int[] xa = new int[4];
private static int[] ya = new int[4];
}
- protected static class AWTSurface extends Surface.DoubleBufferedSurface
+ protected static class AWTSurface extends Surface
implements MouseListener, MouseMotionListener, KeyListener, ComponentListener, WindowListener {
protected AWTPixelBuffer pb = null;
Frame frame = null;
Window window = null;
+ public PixelBuffer getPixelBuffer() { return pb==null?(pb=new AWTPixelBuffer(this)):pb; }
+
public void blit(PixelBuffer source, int sx, int sy, int dx, int dy, int dx2, int dy2) {
getGraphics().drawImage(((AWTPixelBuffer)source).i, sx, sy, sx+(dx2-dx), sy+(dy2-dy), dx, dy, dx2, dy2, null);
}
private int oldfill = 0x0;
public void render() {
// useful optimizatin;
+ /*
if (oldfill != root.fillcolor) {
oldfill = root.fillcolor;
window.setBackground((root.fillcolor & 0xFF000000) == 0 ?
(root.fillcolor >> 8) & 0xff,
(root.fillcolor) & 0xff));
}
+ */
super.render();
}
g2.drawImage(i2, 0, 0, null);
}
- public void fill(org.ibex.graphics.Polygon p, org.ibex.graphics.Paint paint) { fillStroke(p, paint, true, false); }
- public void stroke(org.ibex.graphics.Polygon p, org.ibex.graphics.Paint paint) { fillStroke(p, paint, false, true); }
- public void fillStroke(org.ibex.graphics.Polygon p, org.ibex.graphics.Paint paint, boolean fill, boolean stroke) {
+ public void fill(Mesh p, org.ibex.graphics.Paint paint) { fillStroke(p, paint, true, false); }
+ public void stroke(Mesh p, org.ibex.graphics.Paint paint) { fillStroke(p, paint, false, true); }
+ public void fillStroke(Mesh p, org.ibex.graphics.Paint paint, boolean fill, boolean stroke) {/*
if (g == null) g = getGraphics();
((Graphics2D)g).setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_OFF);
int argb = ((org.ibex.graphics.Paint.SingleColorPaint)paint).color;
}
if (fill) ((Graphics2D)g).fill(gp);
if (stroke) ((Graphics2D)g).draw(gp);
- }
+ */}
public Java2PixelBuffer(int w, int h) {
super(w,h);
fillTrapezoid(x1, x1, y1, x2, x2, y2, color);
}
- public void stroke(Polygon p, int color) { p.stroke(this, color); }
- public native void natFill(Polygon p, int color);
- public void fill(Polygon p, Paint paint) { natFill(p, ((Paint.SingleColorPaint)paint).color); }
+ public void stroke(Mesh p, int color) { /*p.stroke(this, color);*/ }
+ public native void natFill(Mesh p, int color);
+ public void fill(Mesh p, Paint paint) { natFill(p, ((Paint.SingleColorPaint)paint).color); }
public void drawGlyph(org.ibex.graphics.Font.Glyph source, int dx, int dy,
int cx1, int cy1, int cx2, int cy2, int rgb, int pc) {
public void drawLine(int x1, int y1, int x2, int y2, int color) { }
public void drawGlyph(Font.Glyph source, int dx1, int dy1, int cx1, int cy1, int cx2, int cy2, int rgb, int pc){}
- public void stroke(Polygon p, int color){}
- public void fill(Polygon p, Paint paint){}
+ public void stroke(Mesh p, int color){}
+ public void fill(Mesh p, Paint paint){}
int w = 0;
int h = 0;
public void drawLine(int x1, int y1, int x2, int y2, int color) { }
public void drawGlyph(Font.Glyph source, int dx1, int dy1, int cx1, int cy1, int cx2, int cy2, int rgb, int pc){}
- public void stroke(Polygon p, int color){}
- public void fill(Polygon p, Paint paint){}
+ public void stroke(Mesh p, int color){}
+ public void fill(Mesh p, Paint paint){}
int clipx, clipy, clipw, cliph;
int width;
projects / org.ibex.core.git / commitdiff