From 0db1ff365b2acfa1be6420aca33a27dd01eb78f2 Mon Sep 17 00:00:00 2001 From: adam Date: Sun, 21 Jun 2009 23:43:47 +0000 Subject: [PATCH] questionable patch: merge of a lot of stuff from the svg branch darcs-hash:20090621234347-5007d-33c4857aac6bcc22b6677b410d83f712f3f53210.gz --- src/org/ibex/core/Box.java | 280 +++++++++++------- src/org/ibex/graphics/Font.java | 20 +- src/org/ibex/graphics/Mesh.java | 508 ++++++++++++++++++++++---------- src/org/ibex/graphics/Paint.java | 12 +- src/org/ibex/graphics/Path.java | 7 + src/org/ibex/graphics/PixelBuffer.java | 7 +- src/org/ibex/graphics/Surface.java | 24 +- src/org/ibex/plat/AWT.java | 31 +- src/org/ibex/plat/Java2.java | 8 +- 9 files changed, 595 insertions(+), 302 deletions(-) diff --git a/src/org/ibex/core/Box.java b/src/org/ibex/core/Box.java index b9f71b6..dffc33c 100644 --- a/src/org/ibex/core/Box.java +++ b/src/org/ibex/core/Box.java @@ -13,6 +13,11 @@ package org.ibex.core; // - textures // - align/origin // - clipping (all forms) +// - mouse events +// - fonts/text +// - vertical layout + +// - stroke clipping import java.util.*; import org.ibex.js.*; @@ -47,7 +52,7 @@ public final class Box extends JS.Obj implements Callable, Mesh.Chain { // Macros ////////////////////////////////////////////////////////////////////// - final void REPLACE() { for(Box b2 = this; b2 != null && !b2.test(REPLACE); b2 = b2.parent) b2.set(REPLACE); } + final void REPLACE() { for(Box b2 = this; b2 != null && !b2.test(REPLACE); b2 = b2.parent) b2.set(REPLACE); } final void RECONSTRAIN() { for(Box b2 = this; b2 != null && !b2.test(RECONSTRAIN); b2 = b2.parent) b2.set(RECONSTRAIN); } //#define CHECKSET_SHORT(prop) short nu = (short)JSU.toInt(value); if (nu == prop) break; prop = nu; @@ -83,8 +88,17 @@ public final class Box extends JS.Obj implements Callable, Mesh.Chain { public int maxheight = Integer.MAX_VALUE; // computed during reflow - public int width = 0; - public int height = 0; + //public int width = 0; // AS MEASURED IN PARENT SPACE! + //public int height = 0; // AS MEASURED IN PARENT SPACE! + float _width; + float _height; + private int width; + private int height; + private int rootwidth; + private int rootheight; + public int getRootWidth() { return rootwidth; } + public int getRootHeight() { return rootheight; } + public int contentwidth = 0; // == max(minwidth, textwidth, sum(child.contentwidth)) public int contentheight = 0; @@ -122,115 +136,180 @@ public final class Box extends JS.Obj implements Callable, Mesh.Chain { /** should only be invoked on the root box */ public void reflow() { - constrain(this, Affine.identity()); - width = maxwidth; - height = maxheight; + constrain(this, Affine.identity(), new BoundingBox()); + width = rootwidth = maxwidth; + height = rootheight = maxheight; transform.e = 0; transform.f = 0; - place(); + place(0, 0, width, height, false); } - void place() { - if (!packed()) { - for(Box child = getChild(0); child != null; child = child.nextSibling()) { - child.width = max(child.minwidth, min(child.test(HSHRINK) ? child.contentwidth : width, child.maxwidth)); - child.height = max(child.minheight, min(child.test(VSHRINK) ? child.contentheight : height, child.maxheight)); - child.place(); + public float minWidth() { return Encode.longToFloat1(transform.rotateBox(minwidth, minheight)); } + public float minHeight() { return Encode.longToFloat2(transform.rotateBox(minwidth, minheight)); } + public float maxWidth() { return Encode.longToFloat1(transform.rotateBox(maxwidth, maxheight)); } + public float maxHeight() { return Encode.longToFloat2(transform.rotateBox(maxwidth, maxheight)); } + public float contentWidth() { return Encode.longToFloat1(transform.rotateBox(contentwidth, contentheight)); } + public float contentHeight() { return Encode.longToFloat2(transform.rotateBox(contentwidth, contentheight)); } + + /** used (single-threadedly) in constrain() */ + private static int xmin = 0, ymin = 0, xmax = 0, ymax = 0; + + private static class BoundingBox { + public int xmin, ymin, xmax, ymax; + public boolean unbounded() { + return xmin==Integer.MAX_VALUE||xmax==Integer.MIN_VALUE||ymin==Integer.MAX_VALUE||ymax==Integer.MIN_VALUE; } + public void reset() { + xmin = Integer.MAX_VALUE; ymin = Integer.MAX_VALUE; + xmax = Integer.MIN_VALUE; ymax = Integer.MIN_VALUE; + } + public void include(Affine a, float cw, float ch) { + //#repeat contentwidth/contentheight contentheight/contentwidth minwidth/minheight row/col col/row \ + // textwidth/textheight maxwidth/maxheight bounds/boundsy x1/y1 x2/y2 z1/q1 z2/q2 z3/q3 z4/q4 \ + // horizontalBounds/verticalBounds e/f multiply_px/multiply_py xmin/ymin xmax/ymax + float z1 = a.multiply_px(0, 0); + float z2 = a.multiply_px(cw, ch); + float z3 = a.multiply_px(cw, 0); + float z4 = a.multiply_px(0, ch); + xmin = min(xmin, (int)min(min(z1, z2), min(z3, z4))); + xmax = max(xmax, (int)max(max(z1, z2), max(z3, z4))); + //#end + } + public void include(Affine a, Path path) { + //#repeat contentwidth/contentheight contentheight/contentwidth minwidth/minheight row/col col/row \ + // textwidth/textheight maxwidth/maxheight bounds/boundsy x1/y1 x2/y2 z1/q1 z2/q2 z3/q3 z4/q4 \ + // horizontalBounds/verticalBounds e/f multiply_px/multiply_py xmin/ymin xmax/ymax + long bounds = path.horizontalBounds(a); + float z1 = Encode.longToFloat2(bounds); + float z2 = Encode.longToFloat1(bounds); + float z3 = Encode.longToFloat2(bounds); + float z4 = Encode.longToFloat1(bounds); + xmin = min(xmin, (int)min(min(z1, z2), min(z3, z4))); + xmax = max(xmax, (int)max(max(z1, z2), max(z3, z4))); + //#end + } + } + + /** expand the {x,y}{min,max} boundingbox in space a to include this box */ + public void constrain(Box b, Affine a, BoundingBox bbox) { + contentwidth = 0; + contentheight = 0; + a = a.copy().premultiply(transform); + + BoundingBox bbox2 = new BoundingBox(); + for(Box child = getChild(0); child != null; child = child.nextSibling()) { + child.constrain(this, Affine.identity(), bbox2); + if (bbox2.unbounded()) { /* FIXME: why? */ bbox2.reset(); continue; } + if (packed()) { + // packed boxes mush together their childrens' bounding boxes + if (test(XAXIS)) { + contentwidth = contentwidth + (bbox2.xmax-bbox2.xmin); + contentheight = max(bbox2.ymax-bbox2.ymin, contentheight); + } else { + contentwidth = max(bbox2.xmax-bbox2.xmin, contentwidth); + contentheight = contentheight + (bbox2.ymax-bbox2.ymin); + } + bbox2.reset(); } + } + if (!packed()) { + // unpacked boxes simply use the "cumulative" bounding box + contentwidth = bbox2.xmax-bbox2.xmin; + contentheight = bbox2.ymax-bbox2.ymin; + } + + contentwidth = bound(minwidth, contentwidth, maxwidth); + contentheight = bound(minheight, contentheight, maxheight); + bbox.include(a, contentwidth, contentheight); + if (path!=null) bbox.include(a, path); + } + + void place(float x, float y, float w, float h, boolean keep) { + int oldw = width; + int oldh = height; + width = bound(contentwidth, (int)Encode.longToFloat1(transform.inverse().rotateBox(w, h)), test(HSHRINK)?contentwidth:maxwidth); + height = bound(contentheight, (int)Encode.longToFloat2(transform.inverse().rotateBox(w, h)), test(VSHRINK)?contentheight:maxheight); + if (oldw!=width || oldh!=height) mesh = null; + if (!keep) { + Affine a = transform; + transform.e = 0; + transform.f = 0; + float e; + float f; + //#repeat e/f x/y multiply_px/multiply_py horizontalBounds/verticalBounds bounds/boundsy z1/z1y z2/z2y z3/z3y z4/z4y + long bounds = path==null ? 0 : path.horizontalBounds(transform); + float z1 = path==null ? a.multiply_px(0, 0) : Encode.longToFloat2(bounds); + float z2 = path==null ? a.multiply_px(width, height) : Encode.longToFloat1(bounds); + float z3 = path==null ? a.multiply_px(width, 0) : Encode.longToFloat2(bounds); + float z4 = path==null ? a.multiply_px(0, height) : Encode.longToFloat1(bounds); + e = (-1 * min(min(z1, z2), min(z3, z4))) + x; + //#end + transform.e = e; + transform.f = f; + } + + if (!packed()) { + for(Box child = getChild(0); child != null; child = child.nextSibling()) + child.place(0, 0, width, height, true); return; } - float slack = width, oldslack = 0, flex = 0, newflex = 0; + float slack = test(XAXIS)?width:height, oldslack = 0, flex = 0, newflex = 0; for(Box child = getChild(0); child != null; child = child.nextSibling()) { if (!child.test(VISIBLE)) continue; - slack -= (child.width = child.contentwidth); - if (child.width < (child.test(HSHRINK)?child.contentwidth:child.maxwidth)) flex += child.flex; - child.height = child.test(HSHRINK) ? child.contentheight : bound(child.contentheight, height, child.maxheight); + if (test(XAXIS)) { + child._width = child.contentWidth(); + child._height = height; + slack -= child._width; + } else { + child._height = child.contentHeight(); + child._width = width; + slack -= child._height; + } + flex += child.flex; } while(slack > 0 && flex > 0 && oldslack!=slack) { oldslack = slack; - slack = width; + slack = test(XAXIS) ? width : height; + newflex = 0; for(Box child = getChild(0); child != null; child = child.nextSibling()) { if (!child.test(VISIBLE)) continue; - if (child.width < child.maxwidth && !child.test(HSHRINK)) - child.width = bound(child.contentwidth, (int)(child.width + (slack/flex)), child.maxwidth); - newflex += child.width < child.maxwidth && !child.test(HSHRINK) ? child.flex : 0; - slack -= child.width; + if (test(XAXIS)) { + float oldwidth = child._width; + if (child.test(HSHRINK)) child._width = min(child.maxWidth(), child._width+(oldslack*child.flex)/flex); + slack -= child._width; + if (child._width > oldwidth) newflex += child.flex; + } else { + float oldheight = child._height; + if (child.test(VSHRINK)) child._height = min(child.maxHeight(), child._height+(oldslack*child.flex)/flex); + slack -= child._height; + if (child._height > oldheight) newflex += child.flex; + } } flex = newflex; } float pos = slack / 2; for(Box child = getChild(0); child != null; child = child.nextSibling()) { if (!child.test(VISIBLE)) continue; - child.transform.e += pos; - child.transform.f += (height-child.height)/2; - pos += child.width; - child.place(); - } - } - - /** used (single-threadedly) in constrain() */ - private static int xmin = 0, ymin = 0, xmax = 0, ymax = 0; - public void constrain(Box b, Affine a) { - contentwidth = 0; - contentheight = 0; - a = a.copy().premultiply(transform); - - //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()) { - child.constrain(b, a); - contentwidth = max(contentwidth, child.contentwidth); - contentheight = max(contentheight, child.contentheight); + if (test(XAXIS)) { + child.place(pos, 0, child._width, child._height, false); + pos += child._width; + } else { + child.place(0, pos, child._width, child._height, false); + pos += child._height; } - return; } - - for(Box child = getChild(0); child != null; child = child.nextSibling()) { - xmin = Integer.MAX_VALUE; ymin = Integer.MAX_VALUE; - xmax = Integer.MIN_VALUE; ymax = Integer.MIN_VALUE; - if (packed()) { - child.transform.e = 0; - child.transform.f = 0; - } - child.constrain(this, Affine.identity()); - if (xmin==Integer.MAX_VALUE||xmax==Integer.MIN_VALUE||ymin==Integer.MAX_VALUE||ymax== Integer.MIN_VALUE) continue; - if (packed()) { - child.transform.e = -1 * xmin; - child.transform.f = -1 * ymin; - } - contentwidth += (xmax-xmin); - contentheight = max(ymax-ymin, contentheight); - } - xmin = save_xmin; - ymin = save_ymin; - xmax = save_xmax; - ymax = save_ymax; - - int cw = contentwidth = bound(minwidth, contentwidth, maxwidth); - int ch = contentheight = bound(minheight, contentheight, maxheight); - //#repeat contentwidth/contentheight contentheight/contentwidth minwidth/minheight row/col col/row \ - // textwidth/textheight maxwidth/maxheight bounds/boundsy x1/y1 x2/y2 z1/q1 z2/q2 z3/q3 z4/q4 \ - // horizontalBounds/verticalBounds e/f multiply_px/multiply_py xmin/ymin xmax/ymax - long bounds = path==null ? 0 : path.horizontalBounds(a); - float z1 = path==null ? a.multiply_px(0, 0) : Encode.longToFloat2(bounds); - float z2 = path==null ? a.multiply_px(cw, ch) : Encode.longToFloat1(bounds); - float z3 = path==null ? a.multiply_px(cw, 0) : Encode.longToFloat2(bounds); - float z4 = path==null ? a.multiply_px(0, ch) : Encode.longToFloat1(bounds); - xmin = min(xmin, (int)min(min(z1, z2), min(z3, z4))); - xmax = max(xmax, (int)max(max(z1, z2), max(z3, z4))); - //#end } - + + + + // Rendering Pipeline ///////////////////////////////////////////////////////////////////// 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, Mesh clipFrom) { render(buf, a, clipFrom, Affine.identity()); } - public void render(PixelBuffer buf, Affine a, Mesh clipFrom, Affine clipa) { + public void render(PixelBuffer buf, Affine a, Mesh clipFrom) { render(buf, a, clipFrom, Affine.identity(), 0); } + public void render(PixelBuffer buf, Affine a, Mesh clipFrom, Affine clipa, int bg) { if (!test(VISIBLE)) return; a = a.copy().multiply(transform); clipa = clipa.copy().multiply(transform); @@ -238,26 +317,29 @@ public final class Box extends JS.Obj implements Callable, Mesh.Chain { 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 (((fillcolor & 0xFF000000) != 0x00000000 || parent == null) && (text==null||"".equals(text))) { + mesh = new Mesh().addRect(0, 0, width, height); + } // if (ret == 0) Platform.Scheduler.add(this); // FIXME: texture } if (mesh==null) { - for(Box b = getChild(0); b != null; b = b.nextSibling()) b.render(buf, a, clipFrom, clipa); + for(Box b = getChild(0); b != null; b = b.nextSibling()) b.render(buf, a, clipFrom, clipa, bg); + if (!(text==null||text.equals(""))) + font.rasterizeGlyphs(text, buf, a.copy(), clipFrom, clipa.copy(), strokecolor, 0); return; } - // FIXME: mesh clipping code has been getting stuck in loops; to see this, - // uncomment the next two lines and swap the order of the last two lines. + if (clipFrom != null) clipFrom.subtract(mesh, clipa); + Mesh mesh = treeSize() > 0 ? this.mesh.copy() : this.mesh; + + if ((fillcolor & 0xff000000)!=0) bg = fillcolor; + for(Box b = getChild(0); b != null; b = b.nextSibling()) b.render(buf, a, mesh, Affine.identity(), bg); - //if (clipFrom != null) clipFrom.subtract(mesh, clipa); - //Mesh mesh = treeSize() > 0 ? this.mesh.copy() : this.mesh; mesh.fill(buf, a, null, fillcolor, true); - for(Box b = getChild(0); b != null; b = b.nextSibling()) b.render(buf, a, mesh, Affine.identity()); + if ((strokecolor & 0xff000000) != 0) mesh.stroke(buf, a, strokecolor); + if (!(text==null||text.equals(""))) + font.rasterizeGlyphs(text, buf, a.copy(), clipFrom, clipa.copy(), strokecolor, bg); } // Methods to implement org.ibex.js.JS ////////////////////////////////////// @@ -373,9 +455,7 @@ public final class Box extends JS.Obj implements Callable, Mesh.Chain { String s = value==null ? "" : JSU.toString(value); text = s; minwidth = maxwidth = font.textwidth(text); - System.out.println("width=" + width); minheight = maxheight = font.textheight(text); - System.out.println("height=" + height); RECONSTRAIN(); dirty(); } @@ -409,12 +489,12 @@ public final class Box extends JS.Obj implements Callable, Mesh.Chain { case "y": transform.f = JSU.toInt(value); case "transform": { transform = Affine.parse(JSU.toString(value)); - //transform.e = 0; - //transform.f = 0; if (getSurface() != null) // FIXME getSurface().dirty(0, 0, getSurface().root.contentwidth, getSurface().root.contentheight); REPLACE(); - RECONSTRAIN(); dirty(); polygon = null; + RECONSTRAIN(); + dirty(); + polygon = null; } case "width": setWidth(JSU.toInt(value), JSU.toInt(value)); case "height": setHeight(JSU.toInt(value), JSU.toInt(value)); @@ -618,7 +698,7 @@ public final class Box extends JS.Obj implements Callable, Mesh.Chain { // Trivial Helper Methods (should be inlined) ///////////////////////////////////////// public final int fontSize() { return font == null ? DEFAULT_FONT.pointsize : font.pointsize; } - public Enumeration keys() { throw new Error("you cannot apply for..in to a " + this.getClass().getName()); } + public Enumeration jskeys() { throw new Error("you cannot apply for..in to a " + this.getClass().getName()); } public Box getRoot() { return parent == null ? this : parent.getRoot(); } public Surface getSurface() { return Surface.fromBox(getRoot()); } private final boolean packed() { return test(YAXIS) || test(XAXIS); } diff --git a/src/org/ibex/graphics/Font.java b/src/org/ibex/graphics/Font.java index b2c30ca..70451a3 100644 --- a/src/org/ibex/graphics/Font.java +++ b/src/org/ibex/graphics/Font.java @@ -74,7 +74,7 @@ public class Font { } return path.toString(); } - public long rasterizeGlyphs(String text, PixelBuffer pb, Affine a, Mesh h, int fg, int bg) { + public long rasterizeGlyphs(String text, PixelBuffer pb, Affine a, Mesh h, Affine ha, int fg, int bg) { int width = 0, height = 0; if (!latinCharsPreloaded) { // preload the Latin-1 charset with low priority (we'll probably want it) for(int i=48; i<57; i++) if(glyphs[i]==null) toBeRasterized.append(glyphs[i]=Platform.createGlyph(this, (char)i)); @@ -88,11 +88,17 @@ public class Font { Glyph g = glyphs[c]; if (g == null) glyphs[c] = g = Platform.createGlyph(this, c); g.render(); - if (a!=null) a.premultiply(Affine.translate(0, g.font.max_ascent - g.baseline)); - if (pb != null) pb.drawGlyph(g, a, h, fg, bg); - if (a!=null) a.premultiply(Affine.translate(0, -1 * (g.font.max_ascent - g.baseline))); + if (a!=null) a.multiply(Affine.translate(0, g.font.max_ascent - g.baseline)); + if (ha!=null) ha.multiply(Affine.translate(0, g.font.max_ascent - g.baseline)); + if (pb != null) { + pb.drawGlyph(g, a, h, fg, bg); + if (h!=null) h.subtract(new Mesh().addRect(0, 0, g.width, g.height), ha); + } + if (a!=null) a.multiply(Affine.translate(0, -1 * (g.font.max_ascent - g.baseline))); + if (ha!=null) ha.multiply(Affine.translate(0, -1 * (g.font.max_ascent - g.baseline))); width += g.advance; - if (a!=null) a.premultiply(Affine.translate(g.advance, 0)); + if (a!=null) a.multiply(Affine.translate(g.advance, 0)); + if (ha!=null) ha.multiply(Affine.translate(g.advance, 0)); height = java.lang.Math.max(height, max_ascent + max_descent); } return ((((long)width) << 32) | (long)(height & 0xffffffffL)); @@ -105,13 +111,13 @@ public class Font { public long textsize(String s) { Long l = (Long)sizeCache.get(s); if (l != null) return ((Long)l).longValue(); - long ret = rasterizeGlyphs(s, null, null, null, 0, 0); + long ret = rasterizeGlyphs(s, null, null, null, null, 0, 0); sizeCache.put(s, new Long(ret)); return ret; } public Glyph getGlyph(char c) { - rasterizeGlyphs(c+"", null, null, null, 0, 0); + rasterizeGlyphs(c+"", null, null, null, null, 0, 0); Glyph g = glyphs[c]; g.render(); return g; diff --git a/src/org/ibex/graphics/Mesh.java b/src/org/ibex/graphics/Mesh.java index 0680a4c..274f668 100644 --- a/src/org/ibex/graphics/Mesh.java +++ b/src/org/ibex/graphics/Mesh.java @@ -6,17 +6,19 @@ package org.ibex.graphics; import java.util.*; import java.util.collections.*; import org.ibex.util.*; +import java.awt.*; // TODO: + +// FIXME: Not all triangles who get their dirty bit set wind up having fixup() called on them -- bad!! + +// FEATURE: Delauanay refinement + // - allow edge-constraint removal -// -// ~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 /** @@ -25,9 +27,11 @@ import org.ibex.util.*; */ public final class Mesh { - private static final float epsilon = (float)0.0001; - private static final float epsilon2 = (float)0.001; + private static final float epsilon = (float)0.0; + private static final float epsilon2 = (float)0.0; private static final boolean debug = false; + //private static final boolean check = true; + private static final boolean check = false; private Vector triangles = new Vector(); /* we no longer need this */ private Hash edges = new Hash(); /* we no longer need this either */ @@ -99,6 +103,7 @@ public final class Mesh { iter[numiter++] = triangle0; while(numiter > 0) { Triangle t = iter[--numiter]; + if (t==null) return; // FIXME: is this right?!? if (t.tick >= this.tick) continue; switch(mode) { case ITERATE_STROKE: t.stroke(buf, a, color); break; @@ -107,7 +112,8 @@ public final class Mesh { case ITERATE_INTERSECT: case ITERATE_SUBTRACT: { if (!t.in) break; - boolean oin = m.queryPoint(t.c().multiply(a)); + Point p = Imprecise.center(Mesh.this, t.v(1), t.v(2), t.v(3)); + boolean oin = m.queryPoint(p.multiply(a)); t.in = (mode==ITERATE_SUBTRACT) ? (t.in && !oin) : (t.in && oin); break; } @@ -121,11 +127,12 @@ public final class Mesh { 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); + v1 = m.vertex(p1); + v2 = m.vertex(p2); if (v1==v2) continue; m.getEdge(v1, v2).lock(v1, 0); } + if (check) checkAllDelaunay(); break; } } @@ -138,6 +145,10 @@ public final class Mesh { } } } + public void checkAllDelaunay() { + for(int i=0; i 80) System.out.println("clip in " + (100 * (seek/total)) + "%"); } - // 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); - } + // Imprecise Geometry ////////////////////////////////////////////////////////////////////////////// + // (all of these can be off by a good margin and degrade only performance, not correctness) //////// + //////////////////////////////////////////////////////////////////////////////////////////////////// - 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); + private static class Imprecise { + public static Point center(Mesh m, Point v1, Point v2, Point v3) { + return m.point((float)((double)v1.x+(double)v2.x+(double)v3.x)/3, + (float)(((double)v1.y+(double)v2.y+(double)v3.y)/3)); + } + public static boolean near(Point a, Point b) { + return ddistance(a.x, a.y, b.x, b.y) <= epsilon; + } + public static boolean incircle(Point v1, Point v2, Point v3, Point p) { + /* + float a = 0; + Q: for(int q=0; q<2; q++) { + for(int i=0; i<3; i++) { + if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q; + Point t = v2; v2=v3; v3=v1; v1 = t; + } + Point t = v2; v2=v3; v3=t; + } + if (a==0) throw new Error("a==0 for " + v1 + " " + v2 + " " + v3); + double a1 = (v1.x+v2.x)*(v2.x-v1.x)+(v2.y-v1.y)*(v1.y+v2.y); + double a2 = (v2.x+v3.x)*(v2.x-v3.x)+(v2.y-v3.y)*(v2.y+v3.y); + double ccx = (a1*(v2.y-v3.y)-a2*(v2.y-v1.y))/a/2; + double ccy = (a2*(v2.x-v1.x)-a1*(v2.x-v3.x))/a/2; + double r2 = (v1.x-ccx)*(v1.x-ccx)+(v1.y-ccy)*(v1.y-ccy); + double pd = (p.x-ccx)*(p.x-ccx)+(p.y-ccy)*(p.y-ccy); + return r2 > pd; + */ + return Predicates.incircle(v1.x, v1.y, v2.x, v2.y, v3.x, v3.y, p.x, p.y)>0; + } + public static Point midpoint(Mesh m, Point a, Point b) { return m.point((a.x+b.x)/2,(a.y+b.y)/2); } + private static double ddistance(double x1, double y1, double x2, double y2) { + return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} + public static float area(Point p1, Point p2, Point p3) { + float x1 = p1.x; + float x2 = p2.x; + float x3 = p3.x; + float y1 = p1.y; + float y2 = p2.y; + float y3 = p3.y; + double a = ddistance(x1,y1,x2,y2); + double b = ddistance(x2,y2,x3,y3); + double c = ddistance(x3,y3,x1,y1); + double s = (a+b+c)/2; + double t = s*(s-a)*(s-b)*(s-c); + if (t < 0) return 0; + return (float)Math.sqrt(t); + } + + public static Point intersect(Mesh m, Point v1, Point v2, Point v3, Point v4) { + double a1 = v2.y-v1.y; + double a2 = v4.y-v3.y; + double b1 = v1.x-v2.x; + double b2 = v3.x-v4.x; + double c1 = -1 * (a1*v1.x+b1*v1.y); + double c2 = -1 * (a2*v3.x+b2*v3.y); + double x = (b2*c1-c2*b1)/(b1*a2-b2*a1); + double y = (a2*c1-c2*a1)/(a1*b2-a2*b1); + if (Double.isNaN(x) || Double.isNaN(y)) throw new Error("cannot intersect:\n "); + return m.point((float)x,(float)y); + } + public static int side(Point p1, Point p2, Point p3) { + /* + int ret = 0; + float x0 = p1.x; + float x = p2.x; + float x2 = p3.x; + float y0 = p1.y; + float y = p2.y; + float y2 = p3.y; + + // this MUST be done to double precision + double a = y-y0, b = x0-x, c = a*(x0 - x2) + b*(y0 - y2); + if (c > 0) ret = b>=0 ? -1 : 1; + else if (c < 0) ret = b>=0 ? 1 : -1; + else ret = 0; + return ret; + */ + return Predicates.side(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); + } + } - 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; + // Precise Geometry ///////////////////////////////////////////////////////////////////////////// + + static { + Runtime.getRuntime().load(new java.io.File("Predicates.jnilib").getAbsolutePath()); } + // Vertex ////////////////////////////////////////////////////////////////////////////// + public static int state = 0; public Vertex vertex(Point p, Affine a) { return vertex(p.multiply(a)); } public Vertex vertex(Point p) { Vertex ret = null; switch(numvertices) { case 0: return (vertex0 = new Vertex(p)); - case 1: return vertex0.distance(p)<=epsilon ? vertex0 : (vertex1 = new Vertex(p)); + case 1: return Imprecise.near(vertex0,p) ? vertex0 : (vertex1 = new Vertex(p)); case 2: { - if (vertex0.distance(p)<=epsilon) return vertex0; - if (vertex1.distance(p)<=epsilon) return vertex1; + if (Imprecise.near(vertex0,p)) return vertex0; + if (Imprecise.near(vertex1,p)) return vertex1; Vertex v2 = new Vertex(p); triangle(newEdge(vertex0,vertex1), newEdge(vertex1,v2), newEdge(v2,vertex0)); return v2; @@ -216,7 +274,23 @@ public final class Mesh { 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); + if (t != null && Imprecise.near(t.e(i).v(j),p)) + return t.e(i).v(j); + // this will probably always need to be here since a vertex for which side()==0 could still + // be slightly off to one side (and hence part of a neighboring "sliver" triangle. + for(int k=1; k<=3; k++) + for(int i=1; i<=3; i++) + for(int j=1; j<=2; j++) + if (t != null && t.t(k)!=null && Imprecise.near(t.t(k).e(i).v(j),p)) + return t.t(k).e(i).v(j); + for(int i=0; i= Math.min(p1.x,p2.x) && y <= Math.max(p1.y,p2.y) && @@ -259,7 +328,11 @@ public final class Mesh { } private final class Vertex extends Point implements org.ibex.classgen.opt.Arena.Gladiator { - public Vertex(Point p) { super(p); numvertices++; } + public Vertex(Point p) { + super(p); + numvertices++; + vertices.add(this); + } } // Edge ////////////////////////////////////////////////////////////////////////////// @@ -277,11 +350,12 @@ public final class Mesh { public Edge getEdge(Vertex v1, Vertex v2) { if (v1==v2) throw new Error(); - //Edge ret = (Edge)edges.get(v1,v2); - Edge ret = null; + Edge ret = (Edge)edges.get(v1,v2); + if (ret != null) return ret; + //Edge ret = null; Triangle t = null; if (triangle0 != null) { - t = triangle0.seek(point(v1,v2)); + t = triangle0.seek(Imprecise.midpoint(this, v1,v2)); if (t != null) for(int i=1; i<=3; i++) if (t.e(i).hasVertex(v1) && t.e(i).hasVertex(v2)) ret = t.e(i); @@ -309,7 +383,13 @@ public final class Mesh { edges.put(v2,v1,null); } - public Vertex v(int i) { return i==1?v1:i==2?v2:null; } + public Vertex v(int i) { + switch(i) { + case 1: return v1; + case 2: return v2; + default: return null; + } + } public Edge rotate(Vertex v, boolean clockwise) { Triangle t = v==v1 ? (clockwise?t1:t2) : v==v2 ? (clockwise?t2:t1) : null; @@ -326,7 +406,7 @@ public final class Mesh { return e; } - public boolean isNear(Point p) { return area(v1,v2,p) < epsilon2; } + public boolean isNear(Point p) { return Imprecise.area(v1,v2,p) <= epsilon2; } public Vertex commonVertex(Edge e) { return v1==e.v(1) || v1==e.v(2) ? v1 : v2==e.v(1) || v2==e.v(2) ? v2 : null; } public Vertex unCommonVertex(Edge e) { return v1!=e.v(1) && v1!=e.v(2) ? v1 : v2!=e.v(1) && v2!=e.v(2) ? v2 : null; } public Vertex opposingVertex(Vertex v) { return v1==v ? v2 : v1; } @@ -335,7 +415,7 @@ public final class Mesh { 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 int side(Point a) { return Imprecise.side(v(1), v(2), a); } public boolean hasVertex(Vertex v) { return v1==v || v2==v; } public boolean hasTriangle(Triangle t) { return t==t1 || t==t2; } public String toString() { return v(1) + "--" + v(2); } @@ -347,26 +427,18 @@ public final class Mesh { } 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(Point p) { return p.intersects(v1, v2); } public boolean intersects(Edge e) { return intersects(e.v(1), e.v(2)); } public boolean intersects(Point va, Point vb) { return - !v1.equals(va) && - !v1.equals(vb) && - !v2.equals(va) && - !v2.equals(vb) && + !Imprecise.near(v1,va) && + !Imprecise.near(v1,vb) && + !Imprecise.near(v2,va) && + !Imprecise.near(v2,vb) && partitions(va, vb) && - Mesh.side(va, vb, v1) * Mesh.side(va, vb, v2) == -1; + Imprecise.side(va, vb, v1) * Imprecise.side(va, vb, v2) == -1; } + public Triangle opposingTriangle(Triangle t) { if (t1 == t) return t2; if (t2 == t) return t1; @@ -400,6 +472,8 @@ public final class Mesh { } } public void bisect(Vertex v) { + if (v==this.v(1)) throw new Error("this should never happen"); + if (v==this.v(2)) throw new Error("this should never happen"); Edge e = this; Triangle t1 = this.t1==null?this.t2:this.t1; Triangle t = t1==this.t1?this.t2:this.t1; @@ -429,26 +503,36 @@ public final class Mesh { 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; + if (top == t1) top = null; // is this possible? + if (ton == t1) ton = null; // is this possible? + if (opposingTriangleLeft == t) opposingTriangleLeft = null; // is this possible? + if (opposingTriangleRight == t) opposingTriangleRight = null; // is this possible? t.delete(); } t1.delete(); - Triangle ta, tb, tc, td; + Triangle ta, tb, tc=null, td=null; ta = triangle(right_opposing, opposing_v, right_v); tb = triangle(left_opposing, opposing_v, left_v); ta.in = in1; tb.in = in1; if (t != null) { + if (tov_v==left_v) throw new Error("barf"); + if (tov_v==right_v) throw new Error("barf"); + if (tov_v==left_tov) throw new Error("barf"); + if (tov_v==right_tov) throw new Error("barf"); + if (right_v==right_tov) throw new Error("barf"); + if (left_v==left_tov) throw new Error("barf " + tov + " " + left); tc = triangle(left_tov, tov_v, left_v); td = triangle(right_tov, tov_v, right_v); tc.in = in2; td.in = in2; } if (locked()) fracture(v); - else ta.fixup(); + else ta.fixup(); + if (ta!=null) ta.check(); + if (tb!=null) tb.check(); + if (tc!=null) tc.check(); + if (td!=null) td.check(); } public Edge flip() { if (locked()) throw new Error("attempted to remove a locked edge: " + this); @@ -489,7 +573,7 @@ public final class Mesh { } 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))); + Vertex v0 = vertex(Imprecise.intersect(Mesh.this, v1,v2,e.v(1),e.v(2))); if (v0 != e.v(1) && v0 != e.v(2) && e.locked()) e.fracture(v0); if (v0 != v1 && v0 != v2) fracture(v0); } @@ -533,6 +617,11 @@ public final class Mesh { while(t.intersects(this)) { if (t==told) break; told = t; + /* + System.out.println("I think that " + this + " intersects:\n "+t); + for(int i=1; i<=3; i++) + System.out.println(" " + t.e(i) + ": " + t.e(i).intersects(this)); + */ t = t.followVector(v2,v1); } t = told; @@ -545,8 +634,12 @@ public final class Mesh { if (t2!=null) t2.fixup(); } + public boolean violated = false; public void stroke(PixelBuffer buf, Affine a, int color) { - int c = debug + int c = + violated + ? 0xffff0000 + : debug ? (weight() == 0 ? color : 0xffff0000) : (weight() != 0 ? color : 0); if (c != 0) buf.drawLine(v1.xi(a), v1.yi(a), v2.xi(a), v2.yi(a), c); @@ -563,29 +656,27 @@ public final class Mesh { // Triangle ////////////////////////////////////////////////////////////////////////////// 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 (e3.t1!=null && e3.t1.hasEdge(e2) && e3.t1.hasEdge(e1)) return e3.t1; + if (e3.t2!=null && e3.t2.hasEdge(e2) && e3.t2.hasEdge(e1)) return e3.t2; + if (e2.t1!=null && e2.t1.hasEdge(e2) && e2.t1.hasEdge(e1)) return e2.t1; + if (e2.t2!=null && e2.t2.hasEdge(e2) && e2.t2.hasEdge(e1)) return e2.t2; + if (e1.t1!=null && e1.t1.hasEdge(e2) && e1.t1.hasEdge(e1)) return e1.t1; + if (e1.t2!=null && e1.t2.hasEdge(e2) && e1.t2.hasEdge(e1)) return e1.t2; + Triangle t = new Triangle(e1, e2, e3); if (debug) t.check(); if (triangle0 == null) triangle0 = t; return t; } - public static boolean fixing = false; + public static boolean fixing = false; + public static int count = 0; private final class Triangle implements org.ibex.classgen.opt.Arena.Gladiator { - final float r2; - final Point cc; + //final double r2; + //final Point cc; private Edge e1, e2, e3; // should be final =( + private Vertex v1, v2, v3; public int tick; boolean in = false; @@ -593,14 +684,35 @@ public final class Mesh { boolean painted = 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 Edge e(int i) { return i==1?e1:i==2?e2:i==3?e3:null; } + public Edge e(int i) { + switch(i) { + case 1: return e1; + case 2: return e2; + case 3: return e3; + default: return null; + } } + + //public Vertex v(int i) { return e(i==1?2:i==2?3:i==3?1:0).unCommonVertex(e(i)); } + public Vertex v(int i) { + switch(i) { + case 1: return v1; + case 2: return v2; + case 3: return v3; + default: return null; + } } public Triangle t(int i) { return e(i).t1==this ? e(i).t2 : e(i).t1; } - + public Vertex closestVertex(Point p) { + double d1 = Math.sqrt((v(1).x-p.x)*(v(1).x-p.x)+(v(1).y-p.y)*(v(1).y-p.y)); + double d2 = Math.sqrt((v(2).x-p.x)*(v(2).x-p.x)+(v(2).y-p.y)*(v(2).y-p.y)); + double d3 = Math.sqrt((v(3).x-p.x)*(v(3).x-p.x)+(v(3).y-p.y)*(v(3).y-p.y)); + return (d1 < d2 && d1 < d3) ? v(1) : (d2 < d3) ? v(2) : v(3); + } + public boolean encounters(Point p1, Point p2) { for(int i=1; i<=3; i++) { - if (v(i).equals(p1)) return true; - if (v(i).equals(p2)) return true; + if (Imprecise.near(v(i),p1)) return true; + if (Imprecise.near(v(i),p2)) return true; if (v(i).intersects(p1,p2)) return true; if (e(i).intersects(p1,p2)) return true; } @@ -608,9 +720,7 @@ public final class Mesh { } 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); } @@ -632,7 +742,7 @@ public final class Mesh { for(int i=1; i<=3; i++) { Triangle t = t(i); if (t==null) continue; - if (t.r2 <= v(i).distance2(t.cc)) continue; + if (!t.cc(v(i))) continue; Edge e = e(i); if (e.locked()) { t.fixup(); continue; } return e.flip().t1.fixup(); @@ -666,14 +776,29 @@ public final class Mesh { 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; + count++; + //System.out.println("seek " + t + " -> " + p + " / " + count); + if (t.contains(p)) { state = -1; return t; } + else if (t.intersects(p)) { state = 1; return t; } + else if (t.e(3).intersects(p)) { state = 2; return (t.t(3)!=null && t.t(3).contains(p)) ? t.t(3) : t; } + else if (t.e(1).intersects(p)) { state = 3; return (t.t(1)!=null && t.t(1).contains(p)) ? t.t(1) : t; } + else if (t.e(2).intersects(p)) {state = 4; return (t.t(2)!=null && t.t(2).contains(p)) ? t.t(2) : t; } else { - Triangle t2 = t.followVector(t.c(), p); - if (t2==null || t2==t) return t; - t = t2; + // we "slingshot" back from the centroid in case we're inside of a "sliver" triangle + //Point p0 = t.c(); + //Triangle t2 = t.followVector(p0, p); + Triangle t2 = t.followVector(t.closestVertex(p), p); + if (t2==null || t2==t) { + if (t.e(1).partitions(p, t.v(1)) && t.t(1)!=null) t = t.t(1); + else if (t.e(2).partitions(p, t.v(2)) && t.t(2)!=null) t = t.t(2); + else if (t.e(3).partitions(p, t.v(3)) && t.t(3)!=null) t = t.t(3); + else { + state = 5; + return t; + } + } else { + t = t2; + } } } } finally { if (t!=null) triangle0 = t; } @@ -688,8 +813,9 @@ public final class Mesh { 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); + if (contains(p2) || intersects(p2) || Imprecise.near(v(1),p2) || Imprecise.near(v(2),p2) || Imprecise.near(v(3),p2)) + return this; + for(int i=1; i<=3; i++) if (!Imprecise.near(v(i),p1) && v(i).intersects(p1,p2)) return followVector(v(i),p2); Triangle t1 = t(1); Triangle t2 = t(2); Triangle t3 = t(3); @@ -697,24 +823,67 @@ public final class Mesh { 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 (Imprecise.near(v(i),p1)) { if (e(k1).partitions(v(k1),p2)) return t(k1); if (e(k2).partitions(v(k2),p2)) return t(k2); if (e(k3).partitions(v(k3),p2)) return t(k3); throw new Error("bad!"); } } - if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2)) - 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); + //if (!e(1).intersects(p1,p2) && !e(2).intersects(p1,p2) && !e(3).intersects(p1,p2)) + for(int i=1; i<=3; i++) + if (e(i).intersects(p1,p2)) + if (e(i).side(v(i)) * e(i).side(p2) == -1) + return t(i); + for(int i=1; i<=3; i++) + if (e(i).partitions(p1,p2)) + return t(i); + for(int i=1; i<=3; i++) + if (e(i).partitions(v(i),p2)) + return t(i); + for(int i=1; i<=3; i++) + if (v(i).intersects(p1,p2)) + throw new Error("bad news: \n "+p1+" -> "+p2+"\n " + this); + + System.out.println("slingshot from: " + p1 + " to " + p2 + " on " + this + "\n" + + (e(1).side(v(1)) * e(1).side(p2))+" "+ + (e(2).side(v(2)) * e(2).side(p2))+" "+ + (e(3).side(v(3)) * e(3).side(p2)) + ); + /* + return followVector(new Point(2*p1.x-p2.x, 2*p1.y-p2.y), p2); + */ + //throw new Error("giving up: \n "+p1+" -> "+p2+"\n " + this); + + final Point pp1 = p1; + final Point pp2 = p2; + new Frame() { + public void paint(Graphics g) { + g.setColor(java.awt.Color.white); + g.fillRect(0, 0, getWidth(), getHeight()); + g.setColor(java.awt.Color.black); + g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(2).x+100, (int)v(2).y+100); + g.drawLine((int)v(3).x+100, (int)v(3).y+100, (int)v(2).x+100, (int)v(2).y+100); + g.drawLine((int)v(1).x+100, (int)v(1).y+100, (int)v(3).x+100, (int)v(3).y+100); + + g.setColor(java.awt.Color.red); + g.drawLine((int)pp1.x+100, (int)pp1.y+100, (int)pp2.x+100, (int)pp2.y+100); + } + }.show(); + try { Thread.sleep(100000); } catch (Exception e) { } + return null; + + /* + throw new Error("invoked followVector() on a Triangle which it does not encounter:\n" + + " p1=" + p1 + "\n" + + " p2=" + p2 + "\n" + + " t =" + this + " (area "+area(v(1)+100,v(2),v(3))+")\n"); + */ } public void check() { - if (debug) { + if (e1==null && e2==null && e3==null) return; + if (check) { for(int i=1; i<=3; i++) { if (e(i).v(1) != v(1) && e(i).v(1) != v(2) && e(i).v(1) != v(3)) throw new Error("inconsistent"); if (e(i).t1 != this && e(i).t2 != this) throw new Error("inconsistent"); @@ -722,21 +891,40 @@ public final class Mesh { } 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"); - } + if (t(i) == null) continue; + if (!t(i).hasEdge(e(i))) throw new Error("t1 doesn't have e(1)"); + if (t(i).getSharedEdge(this) != e(i)) throw new Error("blark"); + if (!e(i).hasTriangle(t(i))) throw new Error("blark2"); + if (!e(i).hasTriangle(this)) throw new Error("blark3"); + } + for(int i=1; i<=3; i++) + if (e(i).commonVertex(e(i==3?1:(i+1)))==null) + throw new Error("edges have no common vertex"); + // check that delauanay property is preserved + } + } + + public void checkDelaunay() { + for(int i=1; i<=3; i++) { + if (t(i) == null) continue; + Vertex v = t(i).opposingVertex(e(i)); + if (!e(i).locked() && /*Imprecise.incircle(v(1), v(2), v(3), v)*/cc(v) /*&& !dirty && !t(i).dirty*/) { + //throw new Error("Delaunay violation: vertex " + v + "\n triangle: " + this); + //System.out.println("violation: " + e(i)); + e(i).violated = true; + } else { + e(i).violated = false; } - // check that edges all join up } } 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; } + for(int i=3; i>0; i--) if (e(i).intersects(v)/* || e(i).isNear(v)*/) { + e(i).bisect(v); + return; + } Triangle a=null,b=null,c=null; boolean oldIn = in; @@ -755,6 +943,9 @@ public final class Mesh { b.in = oldIn; c.in = oldIn; a.fixup(); + a.check(); + b.check(); + c.check(); } public void setIn(boolean evenOdd, int weight) { @@ -771,7 +962,7 @@ public final class Mesh { for(int i=1; i<=3; i++) if (t(i) != null) { boolean prepaint = t(i).painted; - if (debug) e(i).stroke(buf, a, color); + //if (debug) e(i).stroke(buf, a, color); t(i).fill(buf, a, clip, color, strokeOnly); } } @@ -780,31 +971,25 @@ public final class Mesh { 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)); + /*Vertex*/ this.v1 = e(2).unCommonVertex(e(1)); + /*Vertex*/ this.v2 = e(3).unCommonVertex(e(2)); + /*Vertex*/ this.v3 = e(1).unCommonVertex(e(3)); if (e(1).intersects(v1)) throw new Error("triangle points are colinear"); if (e(2).intersects(v2)) throw new Error("triangle points are colinear"); if (e(3).intersects(v3)) throw new Error("triangle points are colinear"); e(1).addTriangle(this); e(2).addTriangle(this); e(3).addTriangle(this); - - float a = 0; - Q: for(int q=0; q<2; q++) { - for(int i=0; i<3; i++) { - if ((a=(v2.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v2.x-v3.x))!=0) break Q; - 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); - 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 boolean cc(Point p) { + /* + Vertex v1 = e(2).unCommonVertex(e(1)); + Vertex v2 = e(3).unCommonVertex(e(2)); + Vertex v3 = e(1).unCommonVertex(e(3)); + */ + return Imprecise.incircle(v1, v2, v3, p); + } public void clear() { if (!painted) return; painted = false; @@ -888,6 +1073,7 @@ public final class Mesh { } finally { last = vx; } + if (check) checkAllDelaunay(); } } diff --git a/src/org/ibex/graphics/Paint.java b/src/org/ibex/graphics/Paint.java index 3ba71b0..d75ed49 100644 --- a/src/org/ibex/graphics/Paint.java +++ b/src/org/ibex/graphics/Paint.java @@ -7,22 +7,24 @@ package org.ibex.graphics; import java.util.*; public abstract class Paint { - public abstract void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf); + //public abstract void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf); public static class SingleColorPaint extends Paint { public int color; public SingleColorPaint(int color) { this.color = color; } + /* public void fillTrapezoid(float x1, float x2, float y1, float x3, float x4, float y2, PixelBuffer buf) { buf.fillTrapezoid((int)Math.round(x1), (int)Math.round(x2), (int)Math.round(y1), (int)Math.round(x3), (int)Math.round(x4), (int)Math.round(y2), color); } + */ } public static class TexturePaint extends Paint { Affine a, invert; Picture p; public TexturePaint(Picture p, Affine a) { this.p = p; this.a = a.copy(); this.invert = a.copy().invert(); } - public void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf) { + //public void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf) { /* float x1 = invert.multiply_px(tx1, ty1); float x2 = invert.multiply_px(tx2, ty1); @@ -32,7 +34,7 @@ public abstract class Paint { float y2 = invert.multiply_py(tx3, ty2); */ //buf.paintTrapezoid((int)tx1, (int)tx2, (int)ty1, (int)tx3, (int)tx4, (int)ty2, p, a); - } + //} } public static abstract class GradientPaint extends Paint { @@ -55,7 +57,7 @@ public abstract class Paint { float[] stop_offsets; float cx, cy, r, fx, fy; - public void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf) { + //public void fillTrapezoid(float tx1, float tx2, float ty1, float tx3, float tx4, float ty2, PixelBuffer buf) { /* Affine a = buf.a; Affine inverse = a.copy().invert(); @@ -97,7 +99,7 @@ public abstract class Paint { } } */ - } + //} } /* public static class LinearGradientPaint extends GradientPaint { diff --git a/src/org/ibex/graphics/Path.java b/src/org/ibex/graphics/Path.java index 2b5be3c..7dce44b 100644 --- a/src/org/ibex/graphics/Path.java +++ b/src/org/ibex/graphics/Path.java @@ -187,6 +187,13 @@ public class Path { } } + public long boundingBox(Affine a) { + long hb = horizontalBounds(a); + long vb = verticalBounds(a); + return Encode.twoFloatsToLong(Math.abs(Encode.longToFloat1(hb) - Encode.longToFloat2(hb)), + Math.abs(Encode.longToFloat1(vb) - Encode.longToFloat2(vb))); + } + //#repeat width/height multiply_px/multiply_py horizontalBounds/verticalBounds public long horizontalBounds(Affine a) { // FIXME wrong diff --git a/src/org/ibex/graphics/PixelBuffer.java b/src/org/ibex/graphics/PixelBuffer.java index 1f49b94..52cacdb 100644 --- a/src/org/ibex/graphics/PixelBuffer.java +++ b/src/org/ibex/graphics/PixelBuffer.java @@ -19,12 +19,13 @@ import org.ibex.util.*; */ public interface PixelBuffer { public abstract void drawLine(int x1, int y1, int x2, int y2, int color); - public abstract void fillTrapezoid(int x1, int x2, int y1, int x3, int x4, int y2, int color); 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(Mesh p, int color); - public abstract void fill(Mesh 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/Surface.java b/src/org/ibex/graphics/Surface.java index 0799267..6e2bcc9 100644 --- a/src/org/ibex/graphics/Surface.java +++ b/src/org/ibex/graphics/Surface.java @@ -266,9 +266,9 @@ public abstract class Surface implements Callable { } int rootwidth = root.test(root.HSHRINK) ? root.contentwidth : root.maxwidth; int rootheight = root.test(root.VSHRINK) ? root.contentheight : root.maxheight; - if (rootwidth != root.width || rootheight != root.height) { + if (rootwidth != root.getRootWidth() || rootheight != root.getRootHeight()) { // dirty the place where the scar used to be and where it is now - dirty(0, root.height - scarImage.height, scarImage.width, scarImage.height); + dirty(0, root.getRootHeight() - scarImage.height, scarImage.width, scarImage.height); dirty(0, rootheight - scarImage.height, scarImage.width, scarImage.height); } root.reflow(); @@ -286,15 +286,17 @@ public abstract class Surface implements Callable { int x = dirt[i][0], y = dirt[i][1], w = dirt[i][2], h = dirt[i][3]; if (x < 0) x = 0; if (y < 0) y = 0; - if (x+w > root.width) w = root.width - x; - if (y+h > root.height) h = root.height - y; + if (x+w > root.getRootWidth()) w = root.getRootWidth() - x; + if (y+h > root.getRootHeight()) h = root.getRootHeight() - y; if (w <= 0 || h <= 0) continue; */ // FIXME: set clip to -- x, y, x + w, y + h, root.render(this.getPixelBuffer(), identity, null); + + //try { Thread.sleep(500); } catch (Exception e) { } /* - //getPixelBuffer().drawPicture(scarImage, 0, root.height - scarImage.height, x, y, x+w, y+h); + //getPixelBuffer().drawPicture(scarImage, 0, root.getRootHeight() - scarImage.height, x, y, x+w, y+h); if (abort) { // x,y,w,h is only partially reconstructed, so we must be careful not to re-blit it @@ -395,7 +397,7 @@ public abstract class Surface implements Callable { screenDirtyRegions.dirty(x1, y1, x2, y2); backbuffer.drawLine(x1, y1, x2, y2, color); } - + /* public abstract void _fillTrapezoid(int x1, int x2, int y1, int x3, int x4, int y2, int color); public void fillTrapezoid(int x1, int x2, int y1, int x3, int x4, int y2, int color) { // we don't dirty trapezoid-fills since it's faster to just do them directly than to copy from the backbuffer @@ -403,10 +405,11 @@ public abstract class Surface implements Callable { backbuffer.fillTrapezoid(x1, x2, y1, x3, x4, y2, color); //_fillTrapezoid(x1, x2, y1, x3, x4, y2, color); } - + */ public void render() { super.render(); if (abort) return; + /* int[][] dirt = screenDirtyRegions.flush(); for(int i = 0; dirt != null && i < dirt.length; i++) { if (dirt[i] == null) continue; @@ -416,12 +419,15 @@ public abstract class Surface implements Callable { int h = dirt[i][3]; if (x < 0) x = 0; if (y < 0) y = 0; - if (x+w > root.width) w = root.width - x; - if (y+h > root.height) h = root.height - y; + if (x+w > root.getRootWidth()) w = root.getRootWidth() - x; + if (y+h > root.getRootHeight()) h = root.getRootHeight() - y; if (w <= 0 || h <= 0) continue; if (abort) return; blit(backbuffer, x, y, x, y, w + x, h + y); } + */ + System.out.println("blit"); + blit(backbuffer, 0, 0, 0, 0, root.getRootWidth(), root.getRootHeight()); } // This is how subclasses signal a 'shallow dirty', indicating that although the backbuffer is valid, the screen is not diff --git a/src/org/ibex/plat/AWT.java b/src/org/ibex/plat/AWT.java index e84f497..050f9e7 100644 --- a/src/org/ibex/plat/AWT.java +++ b/src/org/ibex/plat/AWT.java @@ -205,7 +205,10 @@ public class AWT extends JVM { g.fillPolygon(xpoints, ypoints, 3); } - public void drawPicture(Picture p, Affine a, Mesh h) { throw new Error("drawPicture() not implemented"); } + public void drawPicture(Picture p, Affine a, Mesh h) { + throw new Error("drawPicture() not implemented"); + } + protected Image i = null; protected Graphics g = null; protected AWTSurface surface = null; @@ -247,8 +250,8 @@ public class AWT extends JVM { g.drawLine(x1, y1, x2, y2); } - 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);*/ } + //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]; @@ -268,7 +271,7 @@ public class AWT extends JVM { } // this doens't seem to work on Windows - public void drawGlyph(org.ibex.graphics.Font.Glyph source,Affine a,Mesh h,int rgb,int bg) { + public void drawGlyph(org.ibex.graphics.Font.Glyph source, Affine a, Mesh h, int argb, int bg) { //throw new Error("drawGlyph() not implemented"); /* Image i = ((AWTGlyph)source).getImage(); @@ -293,7 +296,7 @@ public class AWT extends JVM { } - protected static class AWTSurface extends Surface + protected static class AWTSurface extends Surface // extends Surface.DoubleBufferedSurface implements MouseListener, MouseMotionListener, KeyListener, ComponentListener, WindowListener { protected AWTPixelBuffer pb = null; @@ -356,13 +359,13 @@ public class AWT extends JVM { Dirty(r.x - insets.left, r.y - insets.top, r.width, r.height); } else { Dirty(0, 0, - Math.max(getWidth() - insets.left - insets.right, root.width), - Math.min(getHeight() - insets.top - insets.bottom, root.height)); + Math.max(getWidth() - insets.left - insets.right, root.getRootWidth()), + Math.min(getHeight() - insets.top - insets.bottom, root.getRootHeight())); } // ugly hack for Java1.4 dynamicLayout on Win32 -- this catches expansions during smooth resize - int newwidth = Math.max(getWidth() - insets.left - insets.right, root.width); - int newheight = Math.max(getHeight() - insets.top - insets.bottom, root.height); - if (newwidth != root.width || newheight != root.height) componentResized(newwidth, newheight); + int newwidth = Math.max(getWidth() - insets.left - insets.right, root.getRootWidth()); + int newheight = Math.max(getHeight() - insets.top - insets.bottom, root.getRootHeight()); + if (newwidth != root.getRootWidth() || newheight != root.getRootHeight()) componentResized(newwidth, newheight); } } @@ -470,7 +473,7 @@ public class AWT extends JVM { public void windowClosed(WindowEvent e) { } public void windowClosing(WindowEvent e) { Close(); } public void windowIconified(WindowEvent e) { Minimized(true); } - public void windowDeiconified(WindowEvent e) { dirty(0, 0, root.width, root.height); Minimized(false); } + public void windowDeiconified(WindowEvent e) { dirty(0, 0, root.getRootWidth(), root.getRootHeight()); Minimized(false); } public void windowActivated(WindowEvent e) { Focused(true); } public void windowDeactivated(WindowEvent e) { Focused(false); } public void componentMoved(ComponentEvent e) { PosChange(window.getLocation().x + insets.left, window.getLocation().y + insets.top); } @@ -483,8 +486,8 @@ public class AWT extends JVM { public void componentResized(int newwidth, int newheight) { SizeChange(newwidth, newheight); - if (newwidth > root.width) Dirty(root.width, 0, newwidth-root.width, newheight); - if (newheight > root.height) Dirty(0, root.height, newwidth, newheight-root.height); + if (newwidth > root.getRootWidth()) Dirty(root.getRootWidth(), 0, newwidth-root.getRootWidth(), newheight); + if (newheight > root.getRootHeight()) Dirty(0, root.getRootHeight(), newwidth, newheight-root.getRootHeight()); Refresh(); } @@ -499,7 +502,7 @@ public class AWT extends JVM { // ugly hack for Java1.4 dynamicLayout on Win32 -- this catches contractions during smooth resize int newwidth = window.getWidth() - insets.left - insets.right; int newheight = window.getHeight() - insets.top - insets.bottom; - if (newwidth != root.width || newheight != root.height) componentResized(newwidth, newheight); + if (newwidth != root.getRootWidth() || newheight != root.getRootHeight()) componentResized(newwidth, newheight); Move(m.getX() - insets.left, m.getY() - insets.top); } diff --git a/src/org/ibex/plat/Java2.java b/src/org/ibex/plat/Java2.java index 0fed4e9..92c9aa3 100644 --- a/src/org/ibex/plat/Java2.java +++ b/src/org/ibex/plat/Java2.java @@ -90,6 +90,7 @@ public class Java2 extends AWT { public static class Java2Surface extends AWTSurface { public Java2Surface(Box root, boolean framed) { super(root, framed); } + public PixelBuffer getPixelBuffer() { return pb==null?(pb=new Java2PixelBuffer(this)):pb; } protected void _setMinimized(boolean b) { if (frame == null) Log.info(this, "JDK 1.2 can only minimize frames, not windows"); else if (b) frame.setState(java.awt.Frame.ICONIFIED); @@ -129,9 +130,9 @@ public class Java2 extends AWT { g.setComposite(AlphaComposite.SrcIn); g.setColor(new java.awt.Color((rgb & 0x00FF0000) >> 16, (rgb & 0x0000FF00) >> 8, (rgb & 0x000000FF))); g.fillRect(0, 0, i2.getWidth(null), i2.getHeight(null)); - Graphics2D g2 = (Graphics2D)this.i.getGraphics().create(); - g2.transform(new java.awt.geom.AffineTransform(a.a, a.b, a.c, a.d, a.e, a.f)); - g2.drawImage(i2, 0, 0, null); + Graphics2D g2 = (Graphics2D)getGraphics(); + if (a!=null) g2.drawImage(i2, new java.awt.geom.AffineTransform(a.a, a.b, a.c, a.d, a.e, a.f), null); + else g2.drawImage(i2, 0, 0, null); } public void fill(Mesh p, org.ibex.graphics.Paint paint) { fillStroke(p, paint, true, false); } @@ -153,6 +154,7 @@ public class Java2 extends AWT { if (stroke) ((Graphics2D)g).draw(gp); */} + public Java2PixelBuffer(Java2Surface s) { super(s); } public Java2PixelBuffer(int w, int h) { super(w,h); sm = cm.createCompatibleSampleModel(w, h); -- 1.7.10.4