It's still a work in progress, but I've cleaned up a lot of logic and
made it faster in a number of ways. Note that I've abstracted out the
cache stuff and created an "AlphaConsumer" interface which may evolve
over time.
In FX we actually consume alphas in larger chunks than the code in JDK
which was driven by Ductus's 32x32 mandate, so I would have had to make
completely incompatible changes to emitRow - so I moved it behind an
interface. For the JDK code, if you want to integrate this version, I
would have the cache implement the new interface and move your version
of emitRow into the Cache object. I'd send you the new code for my
AlphaConsumer, but it is incompatible with what you need to cache so it
won't help you.
You'll also need a bit of un-translation cleanup as we have mirrors of
all of java.awt.geom with special new APIs that FX needs.
...jim
On 11/8/2010 6:40 AM, Denis Lila wrote:
Hi Jim.
Also, I've gotten another 20% improvement out of the design with a few
more tweaks. (Though I measured the 20% in the stripped down version
that I'm prototyping with FX so I'm not sure how much of that 20%
would show up through the layers of the 2D code. Overall, I've about
doubled the frame rates of the prototype since your first drop that you
checked in to the OpenJDK repository.)
Can I see your new version?
Attached.
How about looking more at the stroking end of the process and I'll dig
a little more into optimal rasterization code. I have a lot of
experience with optimizing rasterizer code (and JNI if it comes to that), but
very little with the curve manipulations involved in stroking (math is so
*hard* at my age ;-)...
Sounds good. Have you implemented your idea of processing one pixel row at a
time, as opposed to processing subpixel rows? If not, I could do that.
Not yet. Right now I've gotten a lot of mileage out of a few tweaks of
the bookkeeping of the sample-row-at-a-time version. I'm still mulling
over exactly how to make that go faster.
...jim
package com.sun.openpisces;
/**
* @author Flar
*/
public interface AlphaConsumer {
public int getOriginX();
public int getOriginY();
public int getWidth();
public int getHeight();
public void setMaxAlpha(int maxalpha);
public void setAndClearRelativeAlphas(int alphaDeltas[], int y,
int firstdelta, int lastdelta);
}
package com.sun.openpisces;
import com.sun.javafx.geom.PathConsumer;
import com.sun.javafx.geom.PathIterator;
import com.sun.javafx.geom.Rectangle;
import java.util.Iterator;
/**
* @author Flar
*/
public final class OpenPiscesRenderer implements PathConsumer {
public static void feedConsumer(PathIterator pi, PathConsumer pc) {
float[] coords = new float[6];
while (!pi.isDone()) {
int type = pi.currentSegment(coords);
switch (type) {
case PathIterator.SEG_MOVETO:
pc.moveTo(coords[0], coords[1]);
break;
case PathIterator.SEG_LINETO:
pc.lineTo(coords[0], coords[1]);
break;
case PathIterator.SEG_QUADTO:
pc.quadTo(coords[0], coords[1],
coords[2], coords[3]);
break;
case PathIterator.SEG_CUBICTO:
pc.curveTo(coords[0], coords[1],
coords[2], coords[3],
coords[4], coords[5]);
break;
case PathIterator.SEG_CLOSE:
pc.closePath();
break;
}
pi.next();
}
pc.pathDone();
}
private final class ScanlineIterator {
private int[] crossings;
private int[] edgePtrs;
private int edgeCount;
// crossing bounds. The bounds are not necessarily tight (the scan line
// at minY, for example, might have no crossings). The x bounds will
// be accumulated as crossings are computed.
private final int maxY;
private int nextY;
private static final int INIT_CROSSINGS_SIZE = 10;
private ScanlineIterator() {
crossings = new int[INIT_CROSSINGS_SIZE];
edgePtrs = new int[INIT_CROSSINGS_SIZE];
// We don't care if we clip some of the line off with ceil, since
// no scan line crossings will be eliminated (in fact, the ceil is
// the y of the first scan line crossing).
nextY = getFirstScanLineCrossing();
maxY = getScanLineCrossingEnd()-1;
}
private int next() {
// TODO: make function that convert from y value to bucket idx?
int cury = nextY++;
int bucket = cury - boundsMinY;
int count = this.edgeCount;
int ptrs[] = this.edgePtrs;
float edges[] = OpenPiscesRenderer.this.edges;
int bucketcount = edgeBucketCounts[bucket];
if ((bucketcount & 0x1) != 0) {
int newCount = 0;
for (int i = 0; i < count; i++) {
int ecur = ptrs[i];
if (edges[ecur+YMAX] > cury) {
ptrs[newCount++] = ecur;
}
}
count = newCount;
}
ptrs = Helpers.widenArray(ptrs, count, bucketcount >> 1);
for (int ecur = edgeBuckets[bucket]; ecur != NULL; ecur = (int)edges[ecur+NEXT]) {
ptrs[count++] = ecur;
// REMIND: Adjust start Y if necessary
}
this.edgePtrs = ptrs;
this.edgeCount = count;
if ((count & 0x1) != 0) {
System.out.println("ODD NUMBER OF EDGES!!!!");
}
int xings[] = this.crossings;
if (xings.length < count) {
this.crossings = xings = new int[ptrs.length];
}
for (int i = 0; i < count; i++) {
int ecur = ptrs[i];
float curx = edges[ecur+CURX];
int cross = ((int) curx) << 1;
edges[ecur+CURX] = curx + edges[ecur+SLOPE];
if (edges[ecur+OR] > 0) {
cross |= 1;
}
int j = i;
while (--j >= 0) {
int jcross = xings[j];
if (jcross <= cross) {
break;
}
xings[j+1] = jcross;
ptrs[j+1] = ptrs[j];
}
xings[j+1] = cross;
ptrs[j+1] = ecur;
}
return count;
}
private boolean hasNext() {
return nextY < maxY;
}
private int curY() {
return nextY - 1;
}
}
//////////////////////////////////////////////////////////////////////////////
// EDGE LIST
//////////////////////////////////////////////////////////////////////////////
// TODO(maybe): very tempting to use fixed point here. A lot of opportunities
// for shifts and just removing certain operations altogether.
// common to all types of input path segments.
private static final int YMAX = 0;
private static final int CURX = 1;
// this and OR are meant to be indeces into "int" fields, but arrays must
// be homogenous, so every field is a float. However floats can represent
// exactly up to 26 bit ints, so we're ok.
private static final int OR = 2;
private static final int SLOPE = 3;
private static final int NEXT = 4;
private float edgeMinY = Float.POSITIVE_INFINITY;
private float edgeMaxY = Float.NEGATIVE_INFINITY;
private float edgeMinX = Float.POSITIVE_INFINITY;
private float edgeMaxX = Float.NEGATIVE_INFINITY;
private static final int SIZEOF_EDGE = 5;
private static final int NULL = -1;
private float[] edges = null;
private int[] edgeBuckets = null;
private int[] edgeBucketCounts = null; // 2*newedges + (1 if pruning needed)
private int numEdges;
private static final float DEC_BND = 20f;
private static final float INC_BND = 8f;
// each bucket is a linked list. this method adds eptr to the
// start "bucket"th linked list.
private void addEdgeToBucket(final int eptr, final int bucket) {
// we could implement this in terms of insertEdge, but this is a special
// case, so we optimize a bit.
edges[eptr+NEXT] = edgeBuckets[bucket];
edgeBuckets[bucket] = eptr;
edgeBucketCounts[bucket] += 2;
}
// Flattens using adaptive forward differencing. This only carries out
// one iteration of the AFD loop. All it does is update AFD variables (i.e.
// X0, Y0, D*[X|Y], COUNT; not variables used for computing scanline crossings).
private void quadBreakIntoLinesAndAdd(float[] pts, final int or) {
final int countlg = 3;
int count = 1 << countlg;
// the dx and dy refer to forward differencing variables, not the last
// coefficients of the "points" polynomial
float ddx, ddy, dx, dy;
c.set(pts, 6);
ddx = c.dbx / (1 << (2 * countlg));
ddy = c.dby / (1 << (2 * countlg));
dx = c.bx / (1 << (2 * countlg)) + c.cx / (1 << countlg);
dy = c.by / (1 << (2 * countlg)) + c.cy / (1 << countlg);
float x0, y0, x1, y1;
x0 = x1 = pts[0];
y0 = y1 = pts[1];
while (count > 0) {
while (Math.abs(ddx) > DEC_BND || Math.abs(ddy) > DEC_BND) {
ddx = ddx / 4;
ddy = ddy / 4;
dx = (dx - ddx) / 2;
dy = (dy - ddy) / 2;
count <<= 1;
}
// can only do this on even "count" values, because we must divide count by 2
while (count % 2 == 0 && Math.abs(dx) <= INC_BND && Math.abs(dy) <= INC_BND) {
dx = 2 * dx + ddx;
dy = 2 * dy + ddy;
ddx = 4 * ddx;
ddy = 4 * ddy;
count >>= 1;
}
count--;
if (count > 0) {
x1 += dx;
dx += ddx;
y1 += dy;
dy += ddy;
} else {
x1 = pts[4];
y1 = pts[5];
}
addLine(x0, y0, x1, y1, or);
x0 = x1;
y0 = y1;
}
}
private void curveBreakIntoLinesAndAdd(float[] pts, final int or) {
final int countlg = 3;
int count = 1 << countlg;
// the dx and dy refer to forward differencing variables, not the last
// coefficients of the "points" polynomial
float dddx, dddy, ddx, ddy, dx, dy;
c.set(pts, 8);
dddx = 2f * c.dax / (1 << (3 * countlg));
dddy = 2f * c.day / (1 << (3 * countlg));
ddx = dddx + c.dbx / (1 << (2 * countlg));
ddy = dddy + c.dby / (1 << (2 * countlg));
dx = c.ax / (1 << (3 * countlg)) + c.bx / (1 << (2 * countlg)) + c.cx / (1 << countlg);
dy = c.ay / (1 << (3 * countlg)) + c.by / (1 << (2 * countlg)) + c.cy / (1 << countlg);
float x0, y0, x1, y1;
x0 = x1 = pts[0];
y0 = y1 = pts[1];
while (count > 0) {
while (Math.abs(ddx) > DEC_BND || Math.abs(ddy) > DEC_BND) {
dddx /= 8;
dddy /= 8;
ddx = ddx/4 - dddx;
ddy = ddy/4 - dddy;
dx = (dx - ddx) / 2;
dy = (dy - ddy) / 2;
count <<= 1;
}
// can only do this on even "count" values, because we must divide count by 2
while (count % 2 == 0 && Math.abs(dx) <= INC_BND && Math.abs(dy) <= INC_BND) {
dx = 2 * dx + ddx;
dy = 2 * dy + ddy;
ddx = 4 * (ddx + dddx);
ddy = 4 * (ddy + dddy);
dddx = 8 * dddx;
dddy = 8 * dddy;
count >>= 1;
}
count--;
if (count > 0) {
x1 += dx;
dx += ddx;
ddx += dddx;
y1 += dy;
dy += ddy;
ddy += dddy;
} else {
x1 = pts[6];
y1 = pts[7];
}
addLine(x0, y0, x1, y1, or);
x0 = x1;
y0 = y1;
}
}
// Preconditions: y2 > y1 and the curve must cross some scanline
// i.e.: y1 <= y < y2 for some y such that boundsMinY <= y < boundsMaxY
private void addLine(float x1, float y1, float x2, float y2, int or) {
if (y1 > y2) {
System.out.println("backwards line");
}
final int firstCrossing = Math.max((int) Math.ceil(y1), boundsMinY);
final int lastCrossing = Math.min((int)Math.ceil(y2), boundsMaxY);
if (firstCrossing >= lastCrossing) {
return;
}
final int ptr = numEdges * SIZEOF_EDGE;
final float slope = (x2 - x1) / (y2 - y1);
edges = Helpers.widenArray(edges, ptr, SIZEOF_EDGE);
numEdges++;
edges[ptr+OR] = or;
edges[ptr+CURX] = x1 + (firstCrossing - y1) * slope;
edges[ptr+SLOPE] = slope;
edges[ptr+YMAX] = y2;
final int bucketIdx = firstCrossing - boundsMinY;
addEdgeToBucket(ptr, bucketIdx);
if (lastCrossing < boundsMaxY) {
edgeBucketCounts[lastCrossing - boundsMinY] |= 1;
}
}
// preconditions: should not be called before the last line has been added
// to the edge list (even though it will return a correct answer at that
// point in time, it's not meant to be used that way).
private int getFirstScanLineCrossing() {
return Math.max(boundsMinY, (int)Math.ceil(edgeMinY));
}
private int getScanLineCrossingEnd() {
return Math.min(boundsMaxY, (int)Math.ceil(edgeMaxY));
}
// precondition: the curve in pts must be monotonic and increasing in y.
private void somethingTo(float[] pts, final int type, final int or) {
final float xs = pts[0], ys = pts[1], xf = pts[type-2], yf = pts[type-1];
double firstScanline = Math.ceil(ys);
if (firstScanline >= Math.ceil(yf) ||
firstScanline >= boundsMaxY || yf <= boundsMinY)
{
return;
}
if (ys < edgeMinY) { edgeMinY = ys; }
if (yf > edgeMaxY) { edgeMaxY = yf; }
int minXidx = (pts[0] < pts[type-2] ? 0 : type - 2);
float minX = pts[minXidx];
float maxX = pts[type - 2 - minXidx];
if (minX < edgeMinX) { edgeMinX = minX; }
if (maxX > edgeMaxX) { edgeMaxX = maxX; }
switch (type) {
case 4:
addLine(xs, ys, xf, yf, or);
break;
case 6:
quadBreakIntoLinesAndAdd(pts, or);
break;
case 8:
curveBreakIntoLinesAndAdd(pts, or);
break;
default:
throw new InternalError();
}
}
// END EDGE LIST
//////////////////////////////////////////////////////////////////////////////
public static final int WIND_EVEN_ODD = 0;
public static final int WIND_NON_ZERO = 1;
// Antialiasing
final private int SUBPIXEL_LG_POSITIONS_X;
final private int SUBPIXEL_LG_POSITIONS_Y;
final private int SUBPIXEL_POSITIONS_X;
final private int SUBPIXEL_POSITIONS_Y;
final private int SUBPIXEL_MASK_X;
final private int SUBPIXEL_MASK_Y;
final int MAX_AA_ALPHA;
// Bounds of the drawing region, at subpixel precision.
private final int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY;
// Current winding rule
private final int windingRule;
// Current drawing position, i.e., final point of last segment
private float x0, y0;
// Position of most recent 'moveTo' command
private float pix_sx0, pix_sy0;
public OpenPiscesRenderer(int subpixelLgPositionsX, int subpixelLgPositionsY,
int pix_boundsX, int pix_boundsY,
int pix_boundsWidth, int pix_boundsHeight,
int windingRule)
{
this.SUBPIXEL_LG_POSITIONS_X = subpixelLgPositionsX;
this.SUBPIXEL_LG_POSITIONS_Y = subpixelLgPositionsY;
this.SUBPIXEL_POSITIONS_X = 1 << (SUBPIXEL_LG_POSITIONS_X);
this.SUBPIXEL_POSITIONS_Y = 1 << (SUBPIXEL_LG_POSITIONS_Y);
this.SUBPIXEL_MASK_X = SUBPIXEL_POSITIONS_X - 1;
this.SUBPIXEL_MASK_Y = SUBPIXEL_POSITIONS_Y - 1;
this.MAX_AA_ALPHA = (SUBPIXEL_POSITIONS_X * SUBPIXEL_POSITIONS_Y);
this.windingRule = windingRule;
this.boundsMinX = pix_boundsX * SUBPIXEL_POSITIONS_X;
this.boundsMinY = pix_boundsY * SUBPIXEL_POSITIONS_Y;
this.boundsMaxX = (pix_boundsX + pix_boundsWidth) * SUBPIXEL_POSITIONS_X;
this.boundsMaxY = (pix_boundsY + pix_boundsHeight) * SUBPIXEL_POSITIONS_Y;
edgeBuckets = new int[boundsMaxY - boundsMinY];
edgeBucketCounts = new int[edgeBuckets.length];
java.util.Arrays.fill(edgeBuckets, NULL);
}
private float tosubpixx(float pix_x) {
return pix_x * SUBPIXEL_POSITIONS_X;
}
private float tosubpixy(float pix_y) {
return pix_y * SUBPIXEL_POSITIONS_Y;
}
public void moveTo(float pix_x0, float pix_y0) {
closePath();
this.pix_sx0 = pix_x0;
this.pix_sy0 = pix_y0;
this.y0 = tosubpixy(pix_y0);
this.x0 = tosubpixx(pix_x0);
}
private final float[][] pts = new float[2][8];
private final float[] ts = new float[4];
private static void invertPolyPoints(float[] pts, int off, int type) {
for (int i = off, j = off + type - 2; i < j; i += 2, j -= 2) {
float tmp = pts[i];
pts[i] = pts[j];
pts[j] = tmp;
tmp = pts[i+1];
pts[i+1] = pts[j+1];
pts[j+1] = tmp;
}
}
// return orientation before making the curve upright.
private static int makeMonotonicCurveUpright(float[] pts, int off, int type) {
float y0 = pts[off + 1];
float y1 = pts[off + type - 1];
if (y0 > y1) {
invertPolyPoints(pts, off, type);
return -1;
} else if (y0 < y1) {
return 1;
}
return 0;
}
public void lineTo(float pix_x1, float pix_y1) {
pts[0][0] = x0; pts[0][1] = y0;
x0 = tosubpixx(pix_x1);
y0 = tosubpixy(pix_y1);
pts[0][2] = x0; pts[0][3] = y0;
int or = makeMonotonicCurveUpright(pts[0], 0, 4);
somethingTo(pts[0], 4, or);
}
Curve c = new Curve();
private void curveOrQuadTo(int type) {
c.set(pts[0], type);
int numTs = c.dxRoots(ts, 0);
numTs += c.dyRoots(ts, numTs);
numTs = Helpers.filterOutNotInAB(ts, 0, numTs, 0, 1);
Helpers.isort(ts, 0, numTs);
Iterator<float[]> it = Curve.breakPtsAtTs(pts, type, ts, numTs);
while(it.hasNext()) {
float[] curCurve = it.next();
int or = makeMonotonicCurveUpright(curCurve, 0, type);
somethingTo(curCurve, type, or);
}
}
public void curveTo(float x1, float y1,
float x2, float y2,
float x3, float y3)
{
pts[0][0] = x0; pts[0][1] = y0;
pts[0][2] = tosubpixx(x1); pts[0][3] = tosubpixy(y1);
pts[0][4] = tosubpixx(x2); pts[0][5] = tosubpixy(y2);
x0 = tosubpixx(x3);
y0 = tosubpixy(y3);
pts[0][6] = x0; pts[0][7] = y0;
curveOrQuadTo(8);
}
public void quadTo(float x1, float y1, float x2, float y2) {
pts[0][0] = x0; pts[0][1] = y0;
pts[0][2] = tosubpixx(x1); pts[0][3] = tosubpixy(y1);
x0 = tosubpixx(x2);
y0 = tosubpixy(y2);
pts[0][4] = x0; pts[0][5] = y0;
curveOrQuadTo(6);
}
public void closePath() {
// lineTo expects its input in pixel coordinates.
lineTo(pix_sx0, pix_sy0);
}
public void pathDone() {
closePath();
}
public void produceAlphas(AlphaConsumer ac) {
ac.setMaxAlpha(MAX_AA_ALPHA);
// Mask to determine the relevant bit of the crossing sum
// 0x1 if EVEN_ODD, all bits if NON_ZERO
int mask = (windingRule == WIND_EVEN_ODD) ? 0x1 : ~0x0;
// add 2 to better deal with the last pixel in a pixel row.
int width = ac.getWidth();
int[] alpha = new int[width+2];
int bboxx0 = ac.getOriginX() << SUBPIXEL_LG_POSITIONS_X;
int bboxx1 = bboxx0 + (width << SUBPIXEL_LG_POSITIONS_X);
// Now we iterate through the scanlines. We must tell emitRow the coord
// of the first non-transparent pixel, so we must keep accumulators for
// the first and last pixels of the section of the current pixel row
// that we will emit.
// We also need to accumulate pix_bbox*, but the iterator does it
// for us. We will just get the values from it once this loop is done
int pix_maxX = bboxx1 >> SUBPIXEL_LG_POSITIONS_X;
int pix_minX = bboxx0 >> SUBPIXEL_LG_POSITIONS_Y;
int y = boundsMinY; // needs to be declared here so we emit the last row properly.
ScanlineIterator it = this.new ScanlineIterator();
for ( ; it.hasNext(); ) {
int numCrossings = it.next();
int[] crossings = it.crossings;
y = it.curY();
if (numCrossings > 0) {
int lowx = crossings[0] >> 1;
int highx = crossings[numCrossings - 1] >> 1;
int x0 = Math.max(lowx, bboxx0);
int x1 = Math.min(highx, bboxx1);
pix_minX = Math.min(pix_minX, x0 >> SUBPIXEL_LG_POSITIONS_X);
pix_maxX = Math.max(pix_maxX, x1 >> SUBPIXEL_LG_POSITIONS_X);
}
int sum = 0;
int prev = bboxx0;
for (int i = 0; i < numCrossings; i++) {
int curxo = crossings[i];
int curx = curxo >> 1;
int crorientation = ((curxo & 0x1) << 1) - 1;
if ((sum & mask) != 0) {
int x0 = Math.max(prev, bboxx0);
int x1 = Math.min(curx, bboxx1);
if (x0 < x1) {
x0 -= bboxx0; // turn x0, x1 from coords to indices
x1 -= bboxx0; // in the alpha array.
int pix_x = x0 >> SUBPIXEL_LG_POSITIONS_X;
int pix_xmaxm1 = (x1 - 1) >> SUBPIXEL_LG_POSITIONS_X;
if (pix_x == pix_xmaxm1) {
// Start and end in same pixel
alpha[pix_x] += (x1 - x0);
alpha[pix_x+1] -= (x1 - x0);
} else {
int pix_xmax = x1 >> SUBPIXEL_LG_POSITIONS_X;
alpha[pix_x] += SUBPIXEL_POSITIONS_X - (x0 & SUBPIXEL_MASK_X);
alpha[pix_x+1] += (x0 & SUBPIXEL_MASK_X);
alpha[pix_xmax] -= SUBPIXEL_POSITIONS_X - (x1 & SUBPIXEL_MASK_X);
alpha[pix_xmax+1] -= (x1 & SUBPIXEL_MASK_X);
}
}
}
sum += crorientation;
prev = curx;
}
// even if this last row had no crossings, alpha will be zeroed
// from the last emitRow call. But this doesn't matter because
// maxX < minX, so no row will be emitted to the cache.
if ((y & SUBPIXEL_MASK_Y) == SUBPIXEL_MASK_Y) {
ac.setAndClearRelativeAlphas(alpha, y >> SUBPIXEL_LG_POSITIONS_Y,
pix_minX, pix_maxX);
pix_maxX = bboxx1 >> SUBPIXEL_LG_POSITIONS_X;
pix_minX = bboxx0 >> SUBPIXEL_LG_POSITIONS_Y;
}
}
// Emit final row.
// Note, if y is on a MASK row then it was already sent above...
if ((y & SUBPIXEL_MASK_Y) < SUBPIXEL_MASK_Y) {
ac.setAndClearRelativeAlphas(alpha, y >> SUBPIXEL_LG_POSITIONS_Y,
pix_minX, pix_maxX);
}
}
public void endRendering(Rectangle outputBounds) {
int spminX = Math.max((int)Math.ceil(edgeMinX), boundsMinX);
int spmaxX = Math.min((int)Math.ceil(edgeMaxX), boundsMaxX);
int spminY = Math.max((int)Math.ceil(edgeMinY), boundsMinY);
int spmaxY = Math.min((int)Math.ceil(edgeMaxY), boundsMaxY);
int pminX = spminX >> SUBPIXEL_LG_POSITIONS_X;
int pmaxX = (spmaxX + SUBPIXEL_MASK_X) >> SUBPIXEL_LG_POSITIONS_X;
int pminY = spminY >> SUBPIXEL_LG_POSITIONS_Y;
int pmaxY = (spmaxY + SUBPIXEL_MASK_Y) >> SUBPIXEL_LG_POSITIONS_Y;
outputBounds.setBounds(pminX, pminY, pmaxX - pminX, pmaxY - pminY);
}
}
