From 531e31402f74fa636b2d9a2a367305bfd0777cdc Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 2 Jul 2005 09:55:35 +0000 Subject: [PATCH] Mesh replaces Polygon darcs-hash:20050702095535-5007d-363054fa8b0b0007550763492a503588dea8e8c3.gz --- src/org/ibex/core/Box.java | 81 +- src/org/ibex/graphics/Mesh.java | 1305 +++++++++++++++++------------- src/org/ibex/graphics/Path.java | 490 ++++++------ src/org/ibex/graphics/PixelBuffer.java | 4 +- src/org/ibex/graphics/Polygon.java | 1370 -------------------------------- src/org/ibex/graphics/Surface.java | 4 +- src/org/ibex/plat/AWT.java | 10 +- src/org/ibex/plat/Java2.java | 8 +- src/org/ibex/plat/OpenGL.java | 6 +- src/org/ibex/plat/Win32.java | 4 +- src/org/ibex/plat/X11.java | 4 +- 11 files changed, 1064 insertions(+), 2222 deletions(-) delete mode 100644 src/org/ibex/graphics/Polygon.java diff --git a/src/org/ibex/core/Box.java b/src/org/ibex/core/Box.java index 8c312de..ffec434 100644 --- a/src/org/ibex/core/Box.java +++ b/src/org/ibex/core/Box.java @@ -39,7 +39,11 @@ import org.ibex.graphics.*; * 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 ////////////////////////////////////////////////////////////////////// @@ -65,10 +69,11 @@ public final class Box extends JS.Obj implements Callable { 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 @@ -172,7 +177,8 @@ public final class Box extends JS.Obj implements Callable { 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()) { @@ -219,45 +225,34 @@ public final class Box extends JS.Obj implements Callable { 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 { @@ -383,6 +378,7 @@ public final class Box extends JS.Obj implements Callable { 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())); @@ -392,11 +388,22 @@ public final class Box extends JS.Obj implements Callable { 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; } diff --git a/src/org/ibex/graphics/Mesh.java b/src/org/ibex/graphics/Mesh.java index 12f71d7..4693b64 100644 --- a/src/org/ibex/graphics/Mesh.java +++ b/src/org/ibex/graphics/Mesh.java @@ -7,620 +7,861 @@ import java.util.*; 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= 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 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 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= 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 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 " + 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>"; } + + 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)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 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; + } } - } diff --git a/src/org/ibex/graphics/Path.java b/src/org/ibex/graphics/Path.java index 690924d..2b5be3c 100644 --- a/src/org/ibex/graphics/Path.java +++ b/src/org/ibex/graphics/Path.java @@ -2,7 +2,6 @@ // 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.*; @@ -14,38 +13,165 @@ public class Path { 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; jmaxx) maxx = x; if (xmaxy) maxy = y; if (ymaxx) maxx = c1x; if (c1xmaxy) maxy = c1y; if (c1ymaxx) maxx = c2x; if (c2xmaxy) maxy = c2y; if (c2ymaxx) maxx = x; if (xmaxy) maxy = y; if (ymaxx) maxx = c1x; if (c1xmaxy) maxy = c1y; if (c1ymaxx) maxx = c2x; if (c2xmaxy) maxy = c2y; if (c2y> 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 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(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 - } - } } - */ } diff --git a/src/org/ibex/graphics/PixelBuffer.java b/src/org/ibex/graphics/PixelBuffer.java index fb61837..1f49b94 100644 --- a/src/org/ibex/graphics/PixelBuffer.java +++ b/src/org/ibex/graphics/PixelBuffer.java @@ -23,8 +23,8 @@ public interface PixelBuffer { 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); } diff --git a/src/org/ibex/graphics/Polygon.java b/src/org/ibex/graphics/Polygon.java deleted file mode 100644 index 8dc4bfd..0000000 --- a/src/org/ibex/graphics/Polygon.java +++ /dev/null @@ -1,1370 +0,0 @@ -package org.ibex.graphics; -import java.util.*; -import org.ibex.util.*; - -// -// This is a very heavily modified (nearly complete rewrite) version -// of GPCJ, which is itself a Java port of the Generalized Polygon -// Clipping Library -// -// http://www.cs.man.ac.uk/aig/staff/alan/software/gpc.html -// -// Modifications by Adam Megacz -// - -// Possible remaining optimizations: -// -- recycle EdgeNode instances -// -- evolve PolygonNode into the Polygon class? - -// -// !! WARNING !! !! WARNING !! !! WARNING !! -// -// Unlike GPCJ, this code is NOT reentrant or thread-safe; static -// arrays are used to avoid allocation penalties. Also, the union(), -// intersection(), and xor() methods destructively update the 'this' -// object. -// - -/* - * The SEI Software Open Source License, Version 1.0 - * - * Copyright (c) 2004, Solution Engineering, Inc. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. The end-user documentation included with the redistribution, - * if any, must include the following acknowledgment: - * "This product includes software developed by the - * Solution Engineering, Inc. (http://www.seisw.com/)." - * Alternately, this acknowledgment may appear in the software itself, - * if and wherever such third-party acknowledgments normally appear. - * - * 3. The name "Solution Engineering" must not be used to endorse or - * promote products derived from this software without prior - * written permission. For written permission, please contact - * admin@seisw.com. - * - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED - * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - * DISCLAIMED. IN NO EVENT SHALL SOLUTION ENGINEERING, INC. OR - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF - * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND - * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, - * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT - * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * ==================================================================== - */ - - -public final class Polygon { - - private static final int DEFAULT_PATHLEN = 10; - private static final int DEFAULT_CONTOURS = 4; - - private static final int BIGNUM = 65535; - - public boolean[] hole = new boolean[DEFAULT_CONTOURS]; - public boolean[] contributing = new boolean[DEFAULT_CONTOURS]; - public float[] x = new float[DEFAULT_PATHLEN]; - public float[] y = new float[DEFAULT_PATHLEN]; - public int numvertices = 0; - public int[] edges = null; - public int numedges = 0; - public int[] contours = new int[DEFAULT_CONTOURS]; - public int numcontours = 0; - public float[] minx_ = new float[DEFAULT_CONTOURS]; - public float[] miny_ = new float[DEFAULT_CONTOURS]; - public float[] maxx_ = new float[DEFAULT_CONTOURS]; - public float[] maxy_ = new float[DEFAULT_CONTOURS]; - public float minx = Float.MAX_VALUE; - public float miny = Float.MAX_VALUE; - public float maxx = Float.MIN_VALUE; - public float maxy = Float.MIN_VALUE; - public boolean sealed = false; - - public Polygon() { } - public Polygon(Path p, Affine a) { p.addTo(this, a); } - public void intersection(Polygon p2) { clip(GPC_INT, this, p2); } - public void intersect(Polygon p2) { clip(GPC_INT, this, p2); } - public void union(Polygon p2) { clip(GPC_UNION, this, p2); } - public void xor(Polygon p2) { clip(GPC_XOR, this, p2); } - public void subtract(Polygon p2) { clip(GPC_DIFF, this, p2); } - private static Polygon rectclipper = new Polygon(); - public Polygon addrect(float x1, float y1, float x2, float y2, Affine a) { - add(a.multiply_px(x1, y1), a.multiply_py(x1, y1)); - add(a.multiply_px(x2, y1), a.multiply_py(x2, y1)); - add(a.multiply_px(x2, y2), a.multiply_py(x2, y2)); - add(a.multiply_px(x1, y2), a.multiply_py(x1, y2)); - closepath(); - return this; - } - public void clipto(float x1, float y1, float x2, float y2, Affine a) { - rectclipper.clear(); - rectclipper.addrect(x1, y1, x2, y2, a); - intersection(rectclipper); - } - public void closepath() { - if (numcontours > 0 && numvertices == 0) return; - if (numcontours > 0 && (x[contours[numcontours-1]] != x[numvertices-1] || y[contours[numcontours-1]] != y[numvertices-1])) - add(x[contours[numcontours-1]], y[contours[numcontours-1]]); - } - public void newcontour() { - if (numcontours > 0 && numvertices == contours[numcontours-1]) return; - closepath(); - maxx_[numcontours] = maxy_[numcontours] = Float.MIN_VALUE; - minx_[numcontours] = miny_[numcontours] = Float.MAX_VALUE; - contours[numcontours++] = numvertices; - if (numcontours >= contours.length - 2) { - int[] z = new int[contours.length * 4]; System.arraycopy(contours, 0, z, 0, contours.length); contours = z; - boolean[] s = new boolean[hole.length * 4]; System.arraycopy(hole, 0, s, 0, hole.length); hole = s; - s = new boolean[contributing.length * 4];System.arraycopy(contributing,0,s,0,contributing.length);contributing = s; - float[] f = new float[minx_.length * 4]; System.arraycopy(minx_, 0, f, 0, minx_.length); minx_ = f; - f = new float[maxx_.length * 4]; System.arraycopy(maxx_, 0, f, 0, maxx_.length); maxx_ = f; - f = new float[miny_.length * 4]; System.arraycopy(miny_, 0, f, 0, miny_.length); miny_ = f; - f = new float[maxy_.length * 4]; System.arraycopy(maxy_, 0, f, 0, maxy_.length); maxy_ = f; - Log.debug(this, "growing contour list to " + contours.length); - } - } - public void add(float x, float y) { - if (sealed) { Log.error(this, "tried to add a vertex to a sealed polygon!"); return; } - if (numcontours == 0) newcontour(); - this.x[numvertices] = x; - this.y[numvertices] = y; - numvertices++; - if (x > maxx_[numcontours-1]) maxx_[numcontours-1] = x; - if (x < minx_[numcontours-1]) minx_[numcontours-1] = x; - if (y > maxy_[numcontours-1]) maxy_[numcontours-1] = y; - if (y < miny_[numcontours-1]) miny_[numcontours-1] = y; - if (x > maxx) maxx = x; - if (x < minx) minx = x; - if (y > maxy) maxy = y; - if (y < miny) miny = y; - if (numvertices >= this.x.length) { - float[] new_x = new float[this.x.length * 4]; System.arraycopy(this.x, 0, new_x, 0, this.x.length); this.x = new_x; - float[] new_y = new float[this.y.length * 4]; System.arraycopy(this.y, 0, new_y, 0, this.y.length); this.y = new_y; - Log.debug(this, "growing vertex list to " + this.x.length); - } - } - public void clear() { - numvertices = 0; numedges = 0; numcontours = 0; sealed = false; - maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE; - } - public boolean isEmpty() { return numvertices == 0; } - public void add(Polygon p) { add(p, Affine.identity()); } - public void add(Polygon p, Affine a) { for(int i=0; i= contours[s+1]) s++; - float x = a.multiply_px(this.x[i], this.y[i]); - float y = a.multiply_py(this.x[i], this.y[i]); - this.x[i] = x; - this.y[i] = y; - if (x > maxx_[s]) maxx_[s] = x; - if (x < minx_[s]) minx_[s] = x; - if (y > maxy_[s]) maxy_[s] = y; - if (y < miny_[s]) miny_[s] = y; - if (x > maxx) maxx = x; - if (x < minx) minx = x; - if (y > maxy) maxy = y; - if (y < miny) miny = y; - } - return this; - } - - public void stroke(PixelBuffer buf, int color) { - Polygon p = this; - if (!p.sealed) p.sort(); - for(int i=0; i Math.max(p.y[i], p.y[i+1])) : (_y >= Math.max(p.y[i], p.y[i+1]))) - return Integer.MIN_VALUE; - 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]; - return (int)Math.floor(f); - } - - /** fill the interior of the path */ - public void fill(PixelBuffer buf, Paint paint) { - Polygon p = this; - if (!p.sealed) p.sort(); - if (p.numedges == 0) return; - float y0 = p.y[p.edges[0]], y1 = y0; - boolean useEvenOdd = false; - - // we iterate over all endpoints in increasing y-coordinate order - OUTER: for(int index = 1; index x1) continue; - if (midpoint == x1 && i >= rightSegment) continue; - rightSegment = i; - x1 = midpoint; - } - if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break; - if (leftSegment != -1) - if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0)) { - int tx1a = intercept(p.edges[leftSegment], y0, true, true); - int tx1b = intercept(p.edges[rightSegment], y0, true, true); - int tx2a = intercept(p.edges[leftSegment], y1, true, true); - int tx2b = intercept(p.edges[rightSegment], y1, true, true); - buf.fillTrapezoid(tx1a, tx1b, (int)y0, tx2a, tx2b, (int)y1, ((Paint.SingleColorPaint)paint).color); - } - if (useEvenOdd) count++; - else count += (p.y[p.edges[rightSegment]] < p.y[p.edges[rightSegment]+1]) ? -1 : 1; - leftSegment = rightSegment; x0 = x1; - } - } - } - - ////////////////////////////////////////////////////////////////////////////// - - public Polygon sort() { - closepath(); - contours[numcontours] = numvertices; - sealed = true; - numedges = 0; - edges = new int[numvertices]; - for(int i=0; i left && y[edges[--j]] > y[edges[right]]); - if (i >= j) break; - s = edges[i]; edges[i] = edges[j]; edges[j] = s; - } - s = edges[right]; edges[right] = edges[i]; edges[i] = s; - return i; - } else { - if (left >= right) return 0; - int p = sort(left, right, true); - sort(left, p - 1, false); - sort(p + 1, right, false); - return 0; - } - } - - // Rendering ////////////////////////////////////////////////////////////////////////////// - - - private static int bound(int min, int mid, int max) { return mid < min ? min : mid > max ? max : mid; } - - public String toString(int i) { - String ret = " "; - for(int j=contours[i]; j clip.maxx_[c]))) && - (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c]))); - clip.contributing[c] = overlap; - } - if (op != GPC_INT) return; - // For each subject contour, search for any clip contour overlaps - for (int s=0; s < subj.numcontours; s++) { - boolean overlap = false; - for (int c=0; !overlap && (c < clip.numcontours); c++) - overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) && - (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c]))); - subj.contributing[s] = overlap; - } - } - - private static void insert_bound(LmtTable lmt_table, float y, EdgeNode e) { - int index = lmt_table.add(y, null); - // Link node e to the tail of the list - if (lmt_table.first_bound[index] == null) { lmt_table.first_bound[index] = e; return; } - EdgeNode prev_bound = null; - EdgeNode current_bound = lmt_table.first_bound[index]; - while(true) - // Do primary sort on the x field - if (e.bot_x < current_bound.bot_x) { - // Insert a new node mid-list - if (prev_bound == null) lmt_table.first_bound[index] = e; - else prev_bound.next_bound = e; - e.next_bound = current_bound; - break; - } else if (e.bot_x == current_bound.bot_x) { - // Do secondary sort on the dx field - if (e.dx < current_bound.dx) { - // Insert a new node mid-list - if (prev_bound == null) lmt_table.first_bound[index] = e; - else prev_bound.next_bound = e; - e.next_bound = current_bound; - break; - } - // Head further down the list - if (current_bound.next_bound == null) { current_bound.next_bound = e; break; } - prev_bound = current_bound; - current_bound = current_bound.next_bound; - } else { - // Head further down the list - if (current_bound.next_bound == null) { current_bound.next_bound = e; break; } - prev_bound = current_bound; - current_bound = current_bound.next_bound; - } - } - - private static void add_edge_to_aet(AetTree aet, EdgeNode edge) { - if (aet.top_node == null) { - // Append edge onto the tail end of the AET - aet.top_node = edge; - edge.prev = null; - edge.next= null; - return; - } - EdgeNode current_edge = aet.top_node; - EdgeNode prev = null; - while(true) - // Do primary sort on the xb field - if (edge.xb < current_edge.xb) { - // Insert edge here (before the AET edge) - edge.prev= prev; - edge.next= current_edge; - current_edge.prev = edge; - if (prev == null) aet.top_node = edge; - else prev.next = edge; - break; - } else if (edge.xb == current_edge.xb) { - // Do secondary sort on the dx field - if (edge.dx < current_edge.dx) { - // Insert edge here (before the AET edge) - edge.prev= prev; - edge.next= current_edge; - current_edge.prev = edge; - if (prev == null) aet.top_node = edge; - else prev.next = edge; - break; - } - // Head further into the AET - prev = current_edge; - if (current_edge.next == null) { - current_edge.next = edge; - edge.prev = current_edge; - edge.next = null; - break; - } - current_edge = current_edge.next; - } else { - // Head further into the AET - prev = current_edge; - if (current_edge.next == null) { - current_edge.next = edge; - edge.prev = current_edge; - edge.next = null; - break; - } - current_edge = current_edge.next; - } - } - - private static void build_lmt(EdgeTable edge_table, LmtTable lmt_table, ScanBeamList sbte, Polygon p, int type, byte op) { - for (int c=0; c < p.numcontours; c++) { - if (!p.contributing[c]) { p.contributing[c] = true; continue; } - // Perform contour optimisation - int num_vertices= 0; - int e_index = 0; - edge_table.clear(); - for (int i= 0; i < p.contours[c+1] - p.contours[c]; i++) - if (OPTIMAL(p, c, i)) { - edge_table.addNode(p.x[p.contours[c]+i], p.y[p.contours[c]+i]); - sbte.add(p.y[p.contours[c]+i]); // Record vertex in the scanbeam table - num_vertices++; - } - - // Do the contour forward pass - for (int min= 0; min < num_vertices; min++) { - // If a forward local minimum... - if (edge_table.FWD_MIN(min)) { - // Search for the next local maximum... - int num_edges = 1; - int max = NEXT_INDEX(min, num_vertices); - while(edge_table.NOT_FMAX(max)) { num_edges++; max = NEXT_INDEX(max, num_vertices); } - - // Build the next edge list - int v = min; - EdgeNode e = edge_table.getNode(e_index); - e.bstate_BELOW = UNBUNDLED; - e.bundle_BELOW_CLIP = 0; - e.bundle_BELOW_SUBJ = 0; - - for (int i= 0; i < num_edges; i++) { - EdgeNode ei = edge_table.getNode(e_index+i); - EdgeNode ev = edge_table.getNode(v); - ei.xb = ev.vertex_x; - ei.bot_x = ev.vertex_x; - ei.bot_y = ev.vertex_y; - v = NEXT_INDEX(v, num_vertices); - ev = edge_table.getNode(v); - ei.top_x= ev.vertex_x; - ei.top_y= ev.vertex_y; - ei.dx= (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y); - ei.type = type; - ei.outp_ABOVE = null; - ei.outp_BELOW = null; - ei.next = null; - ei.prev = null; - ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null; - ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null; - ei.next_bound = null; - ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT; - ei.bside_SUBJ = LEFT; - } - insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e); - e_index += num_edges; - } - } - - // Do the contour reverse pass - for (int min= 0; min < num_vertices; min++) { - // If a reverse local minimum... - if (edge_table.REV_MIN(min)) { - // Search for the previous local maximum... - int num_edges= 1; - int max = PREV_INDEX(min, num_vertices); - while(edge_table.NOT_RMAX(max)) { num_edges++; max = PREV_INDEX(max, num_vertices); } - // Build the previous edge list - int v = min; - EdgeNode e = edge_table.getNode(e_index); - e.bstate_BELOW = UNBUNDLED; - e.bundle_BELOW_CLIP = 0; - e.bundle_BELOW_SUBJ = 0; - for (int i= 0; i < num_edges; i++) { - EdgeNode ei = edge_table.getNode(e_index+i); - EdgeNode ev = edge_table.getNode(v); - ei.xb = ev.vertex_x; - ei.bot_x = ev.vertex_x; - ei.bot_y = ev.vertex_y; - v= PREV_INDEX(v, num_vertices); - ev = edge_table.getNode(v); - ei.top_x = ev.vertex_x; - ei.top_y = ev.vertex_y; - ei.dx = (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y); - ei.type = type; - ei.outp_ABOVE = null; - ei.outp_BELOW = null; - ei.next = null; - ei.prev = null; - ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null; - ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null; - ei.next_bound = null; - ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT; - ei.bside_SUBJ = LEFT; - } - insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e); - e_index+= num_edges; - } - } - } - } - - public static final byte GPC_DIFF = 0; - public static final byte GPC_INT = 1; - public static final byte GPC_XOR = 2; - public static final byte GPC_UNION = 3; - - // Edge intersection classes - private static class VertexType { - public static final int NUL = 0; // Empty non-intersection - public static final int EMX = 1; // External maximum - public static final int ELI = 2; // External left intermediate - public static final int TED = 3; // Top edge - public static final int ERI = 4; // External right intermediate - public static final int RED = 5; // Right edge - public static final int IMM = 6; // Internal maximum and minimum - public static final int IMN = 7; // Internal minimum - public static final int EMN = 8; // External minimum - public static final int EMM = 9; // External maximum and minimum - public static final int LED = 10; // Left edge - public static final int ILI = 11; // Internal left intermediate - public static final int BED = 12; // Bottom edge - public static final int IRI = 13; // Internal right intermediate - public static final int IMX = 14; // Internal maximum - public static final int FUL = 15; // Full non-intersection - public static int getType(int tr, int tl, int br, int bl) { return tr + (tl << 1) + (br << 2) + (bl << 3); } - } - - private static class HState { - public static final int NH = 0; // No horizontal edge - public static final int BH = 1; // Bottom horizontal edge - public static final int TH = 2; // Top horizontal edge - // Horizontal edge state transitions within scanbeam boundary - public static final int[][] next_h_state = - { - // ABOVE BELOW CROSS - // L R L R L R - /* NH */ {BH, TH, TH, BH, NH, NH}, - /* BH */ {NH, NH, NH, NH, TH, TH}, - /* TH */ {NH, NH, NH, NH, BH, BH} - }; - } - - public static final byte UNBUNDLED = 0; // Isolated edge not within a bundle - public static final byte BUNDLE_HEAD = 1; // Bundle head node - public static final byte BUNDLE_TAIL = 2; // Passive bundle tail node - - private static class PolygonNode { - public static void clear() { numvertices = 1; } - private static final float[] x = new float[BIGNUM]; - private static final float[] y = new float[BIGNUM]; - private static final int[] nxt = new int[BIGNUM]; - private static int numvertices = 1; - - int active = 1; // Active flag / vertex count - boolean hole; // Hole / external contour flag - int v_LEFT; // Left and right vertex list ptrs - int v_RIGHT; // Left and right vertex list ptrs - PolygonNode next; // Pointer to next polygon contour - PolygonNode proxy; // Pointer to actual structure used - - public PolygonNode(PolygonNode next, float x0, float y0) { - // Make v_LEFT and v_RIGHT point to new vertex - x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0; - this.v_LEFT = numvertices; - this.v_RIGHT = numvertices; - numvertices++; - this.proxy = this; // Initialise proxy to point to p itself - this.next = next; - } - public void merge(PolygonNode q) { nxt[proxy.v_RIGHT] = q.proxy.v_LEFT; q.proxy.v_LEFT = proxy.v_LEFT; } - public void mergeRight(PolygonNode p) { nxt[proxy.v_RIGHT] = p.proxy.v_LEFT; proxy.v_RIGHT = p.proxy.v_RIGHT; } - public void addSelfTo(Polygon poly) { - for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) poly.add(x[vtx], y[vtx]); - poly.newcontour(); - } - public int count() { int ret = 0; for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) ret++; return ret; } - public void add_right(float x0, float y0) { - x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0; - nxt[proxy.v_RIGHT] = numvertices; - proxy.v_RIGHT = numvertices; - numvertices++; - } - public void add_left(float x0, float y0) { - x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0; - nxt[numvertices] = proxy.v_LEFT; - proxy.v_LEFT = numvertices; - numvertices++; - } - } - - private static class TopPolygonNode { - PolygonNode top_node = null; - public void clear() { top_node = null; } - public PolygonNode add_local_min(float x, float y) { - PolygonNode existing_min = top_node; - top_node = new PolygonNode(existing_min, x, y); - return top_node; - } - public void merge_left(PolygonNode p, PolygonNode q) { - // Label contour as a hole - q.proxy.hole = true; - if (p.proxy == q.proxy) return; - // Assign p's vertex list to the left end of q's list - p.merge(q); - // Redirect any p.proxy references to q.proxy - PolygonNode target = p.proxy; - for(PolygonNode node = top_node; (node != null); node = node.next) - if (node.proxy == target) { node.active= 0; node.proxy= q.proxy; } - } - - public void merge_right(PolygonNode p, PolygonNode q) { - // Label contour as external - q.proxy.hole = false; - if (p.proxy == q.proxy) return; - // Assign p's vertex list to the right end of q's list - q.mergeRight(p); - // Redirect any p->proxy references to q->proxy - PolygonNode target = p.proxy; - for (PolygonNode node = top_node; (node != null); node = node.next) - if (node.proxy == target) { node.active = 0; node.proxy= q.proxy; } - } - - public int count_contours() { - int nc = 0; - for (PolygonNode polygon = top_node; (polygon != null); polygon = polygon.next) - if (polygon.active != 0) { - // Count the vertices in the current contour - int nv= polygon.proxy.count(); - // Record valid vertex counts in the active field - if (nv > 2) { polygon.active = nv; nc++; } - else polygon.active= 0; - } - return nc; - } - - public Polygon getResult(Polygon result) { - int num_contours = count_contours(); - if (num_contours <= 0) return result; - int c= 0; - PolygonNode npoly_node = null; - for (PolygonNode poly_node = top_node; (poly_node != null); poly_node = npoly_node) { - npoly_node = poly_node.next; - if (poly_node.active == 0) continue; - int prepoly = result.numcontours; - // This algorithm puts the verticies into the poly in reverse order - poly_node.proxy.addSelfTo(result); - if (poly_node.proxy.hole) { - for(int i=prepoly; i= 0; entries--) edges[entries] = null; entries = 0; } - public void addNode(float x, float y) { edges[entries++] = newEdgeNode(x, y); } - public EdgeNode getNode(int index) { return edges[index]; } - public boolean NOT_RMAX(int i) { return (edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y); } - public boolean NOT_FMAX(int i) { return(edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y); } - public boolean FWD_MIN(int i) { - return ((edges[PREV_INDEX(i, entries)].vertex_y >= edges[i].vertex_y) && - (edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y)); - } - public boolean REV_MIN(int i) { - return ((edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y) && - (edges[NEXT_INDEX(i, entries)].vertex_y >= edges[i].vertex_y)); - } - } - - private static class LmtTable { - float[] y = new float[BIGNUM]; - EdgeNode[] first_bound = new EdgeNode[BIGNUM]; - int numentries = 0; - public void clear() { for(; numentries >= 0; numentries--) first_bound[numentries] = null; numentries = 0; } - public int count() { return numentries; } - public boolean isEmpty() { return numentries == 0; } - public int add(float y0, EdgeNode e) { - for(int i=0; i y0) { - System.arraycopy(y, i, y, i+1, numentries-i); - System.arraycopy(first_bound, i, first_bound, i+1, numentries-i); - y[i] = y0; - first_bound[i] = e; - numentries++; - return i; - } - y[numentries] = y0; - first_bound[numentries] = e; - return numentries++; - } - } - - private static class ScanBeamList { - public int entries = 0; - public float[] floats = new float[BIGNUM]; - public void clear() { entries = 0; } - public void add(float f) { floats[entries++] = f; } - public float[] sort() { - org.ibex.util.Vec.sortFloats(floats, 0, entries-1); - int j = 0; - for(int i=1; i=0; num--) { ie_0[num] = null; ie_1[num] = null; } num = 0; } - public void build_intersection_table(AetTree aet, float dy) { - int st = -1; - // Process each AET edge - for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) - if ((edge.bstate_ABOVE == BUNDLE_HEAD) || - (edge.bundle_ABOVE_CLIP != 0) || (edge.bundle_ABOVE_SUBJ != 0)) - st = add_st_edge(st, edge, dy); - sort(0, num-1); - for(;numst>=0; numst--) edge[numst] = null; numst = 0; - } - - int numst = 0; - EdgeNode edge[] = new EdgeNode[BIGNUM]; // Pointer to AET edge - float xb[] = new float[BIGNUM]; // Scanbeam bottom x coordinate - float xt[] = new float[BIGNUM]; // Scanbeam top x coordinate - float dx[] = new float[BIGNUM]; // Change in x for a unit y increase - int prev[] = new int[BIGNUM]; // Previous edge in sorted list - - private int add_st_edge(int st, EdgeNode e, float dy) { - 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; } - float den = (xt[st] - xb[st]) - (e.xt - e.xb); - - // If new edge and ST edge don't cross, No intersection - insert edge here (before the ST edge) - if ((e.xt >= xt[st]) || (e.dx == dx[st]) || (Math.abs(den) <= GPC_EPSILON)) - { prev[numst] = st; st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; return st; } - - // Compute intersection between new edge and ST edge - float r = (e.xb - xb[st]) / den; - float x = xb[st] + r * (xt[st] - xb[st]); - float y = r * dy; - // Insert the edge pointers and the intersection point in the IT - add_intersection(edge[st], e, x, y); - prev[st] = add_st_edge(prev[st], e, dy); - return st; - } - private void add_intersection(EdgeNode edge0, EdgeNode edge1, float x0, float y0) { - ie_0[num] = edge0; ie_1[num] = edge1; x[num] = x0; y[num] = y0; num++; } - - public final void sort(int start, int end) { - if(start >= end) return; - if(end-start <= 6) { - for(int i=start+1;i<=end;i++) { - float tmpa = y[i]; - float tmpx = x[i]; - EdgeNode tmpe0 = ie_0[i]; - EdgeNode tmpe1 = ie_1[i]; - int j; - for(j=i-1;j>=start;j--) { - if(y[j] <= tmpa) break; - y[j+1] = y[j]; - x[j+1] = x[j]; - ie_0[j+1] = ie_0[j]; - ie_1[j+1] = ie_1[j]; - } - y[j+1] = tmpa; - x[j+1] = tmpx; - ie_0[j+1] = tmpe0; - ie_1[j+1] = tmpe1; - } - return; - } - float pivot = y[end]; - int lo = start - 1; - int hi = end; - do { - while(y[++lo] < pivot) { } - while((hi > lo) && y[--hi] > pivot) { } - swap(lo, hi); - } while(lo < hi); - swap(lo, end); - sort(start, lo-1); - sort(lo+1, end); - } - private final void swap(int a, int b) { - if(a != b) { - float tmp = x[a]; x[a] = x[b]; x[b] = tmp; - tmp = y[a]; y[a] = y[b]; y[b] = tmp; - EdgeNode tmpe = ie_0[a]; ie_0[a] = ie_0[b]; ie_0[b] = tmpe; - tmpe = ie_1[a]; ie_1[a] = ie_1[b]; ie_1[b] = tmpe; - } - } - } - -} diff --git a/src/org/ibex/graphics/Surface.java b/src/org/ibex/graphics/Surface.java index f891b29..5be6c43 100644 --- a/src/org/ibex/graphics/Surface.java +++ b/src/org/ibex/graphics/Surface.java @@ -380,11 +380,11 @@ public abstract class Surface implements Callable { 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 } diff --git a/src/org/ibex/plat/AWT.java b/src/org/ibex/plat/AWT.java index 113ca78..e84f497 100644 --- a/src/org/ibex/plat/AWT.java +++ b/src/org/ibex/plat/AWT.java @@ -247,8 +247,8 @@ public class AWT extends JVM { 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]; @@ -293,7 +293,7 @@ public class AWT extends JVM { } - protected static class AWTSurface extends Surface.DoubleBufferedSurface + protected static class AWTSurface extends Surface implements MouseListener, MouseMotionListener, KeyListener, ComponentListener, WindowListener { protected AWTPixelBuffer pb = null; @@ -301,6 +301,8 @@ public class AWT extends JVM { 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); } @@ -378,6 +380,7 @@ public class AWT extends JVM { private int oldfill = 0x0; public void render() { // useful optimizatin; + /* if (oldfill != root.fillcolor) { oldfill = root.fillcolor; window.setBackground((root.fillcolor & 0xFF000000) == 0 ? @@ -386,6 +389,7 @@ public class AWT extends JVM { (root.fillcolor >> 8) & 0xff, (root.fillcolor) & 0xff)); } + */ super.render(); } diff --git a/src/org/ibex/plat/Java2.java b/src/org/ibex/plat/Java2.java index d1b646c..0fed4e9 100644 --- a/src/org/ibex/plat/Java2.java +++ b/src/org/ibex/plat/Java2.java @@ -134,9 +134,9 @@ public class Java2 extends AWT { 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; @@ -151,7 +151,7 @@ public class Java2 extends AWT { } if (fill) ((Graphics2D)g).fill(gp); if (stroke) ((Graphics2D)g).draw(gp); - } + */} public Java2PixelBuffer(int w, int h) { super(w,h); diff --git a/src/org/ibex/plat/OpenGL.java b/src/org/ibex/plat/OpenGL.java index a7aa726..674a80a 100644 --- a/src/org/ibex/plat/OpenGL.java +++ b/src/org/ibex/plat/OpenGL.java @@ -89,9 +89,9 @@ abstract class OpenGL { 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) { diff --git a/src/org/ibex/plat/Win32.java b/src/org/ibex/plat/Win32.java index 9700d1e..bdcaad6 100644 --- a/src/org/ibex/plat/Win32.java +++ b/src/org/ibex/plat/Win32.java @@ -243,8 +243,8 @@ public class Win32 extends GCJ { 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; diff --git a/src/org/ibex/plat/X11.java b/src/org/ibex/plat/X11.java index ffb11fb..72120f7 100644 --- a/src/org/ibex/plat/X11.java +++ b/src/org/ibex/plat/X11.java @@ -149,8 +149,8 @@ public class X11 extends POSIX { 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; -- 1.7.10.4