21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.marlin;
27
28 import static com.sun.marlin.OffHeapArray.SIZE_INT;
29 import jdk.internal.misc.Unsafe;
30
31 public final class Renderer implements MarlinRenderer, MarlinConst {
32
33 static final boolean DISABLE_RENDER = false;
34
35 private static final int ALL_BUT_LSB = 0xFFFFFFFE;
36 private static final int ERR_STEP_MAX = 0x7FFFFFFF; // = 2^31 - 1
37
38 private static final double POWER_2_TO_32 = 0x1.0p32;
39
40 // use float to make tosubpix methods faster (no int to float conversion)
41 static final float F_SUBPIXEL_POSITIONS_X
42 = (float) SUBPIXEL_POSITIONS_X;
43 static final float F_SUBPIXEL_POSITIONS_Y
44 = (float) SUBPIXEL_POSITIONS_Y;
45 static final int SUBPIXEL_MASK_X = SUBPIXEL_POSITIONS_X - 1;
46 static final int SUBPIXEL_MASK_Y = SUBPIXEL_POSITIONS_Y - 1;
47
48 // 2048 (pixelSize) pixels (height) x 8 subpixels = 64K
49 static final int INITIAL_BUCKET_ARRAY
50 = INITIAL_PIXEL_DIM * SUBPIXEL_POSITIONS_Y;
51
52 // crossing capacity = edges count / 4 ~ 1024
53 static final int INITIAL_CROSSING_COUNT = INITIAL_EDGES_COUNT >> 2;
54
55 // common to all types of input path segments.
56 // OFFSET as bytes
57 // only integer values:
58 public static final long OFF_CURX_OR = 0;
59 public static final long OFF_ERROR = OFF_CURX_OR + SIZE_INT;
60 public static final long OFF_BUMP_X = OFF_ERROR + SIZE_INT;
61 public static final long OFF_BUMP_ERR = OFF_BUMP_X + SIZE_INT;
62 public static final long OFF_NEXT = OFF_BUMP_ERR + SIZE_INT;
63 public static final long OFF_YMAX = OFF_NEXT + SIZE_INT;
64
65 // size of one edge in bytes
66 public static final int SIZEOF_EDGE_BYTES = (int)(OFF_YMAX + SIZE_INT);
67
68 // curve break into lines
69 // cubic error in subpixels to decrement step
70 private static final float CUB_DEC_ERR_SUBPIX
71 = 1f * (NORM_SUBPIXELS / 8f); // 1 pixel
72 // cubic error in subpixels to increment step
73 private static final float CUB_INC_ERR_SUBPIX
74 = 0.4f * (NORM_SUBPIXELS / 8f); // 0.4 pixel
75
76 // bad paths (59294/100000 == 59,29%, 94335 bad pixels (avg = 1,59), 3966 warnings (avg = 0,07)
77
78 // cubic bind length to decrement step
79 public static final float CUB_DEC_BND
80 = 8f * CUB_DEC_ERR_SUBPIX;
81 // cubic bind length to increment step
82 public static final float CUB_INC_BND
83 = 8f * CUB_INC_ERR_SUBPIX;
84
85 // cubic countlg
86 public static final int CUB_COUNT_LG = 2;
87 // cubic count = 2^countlg
88 private static final int CUB_COUNT = 1 << CUB_COUNT_LG;
89 // cubic count^2 = 4^countlg
90 private static final int CUB_COUNT_2 = 1 << (2 * CUB_COUNT_LG);
91 // cubic count^3 = 8^countlg
92 private static final int CUB_COUNT_3 = 1 << (3 * CUB_COUNT_LG);
93 // cubic dt = 1 / count
94 private static final float CUB_INV_COUNT = 1f / CUB_COUNT;
95 // cubic dt^2 = 1 / count^2 = 1 / 4^countlg
96 private static final float CUB_INV_COUNT_2 = 1f / CUB_COUNT_2;
97 // cubic dt^3 = 1 / count^3 = 1 / 8^countlg
98 private static final float CUB_INV_COUNT_3 = 1f / CUB_COUNT_3;
99
100 // quad break into lines
101 // quadratic error in subpixels
102 private static final float QUAD_DEC_ERR_SUBPIX
103 = 0.5f * (NORM_SUBPIXELS / 8f); // 0.5 pixel
104
105 // bad paths (62916/100000 == 62,92%, 103818 bad pixels (avg = 1,65), 6514 warnings (avg = 0,10)
106
107 // quadratic bind length to decrement step
108 public static final float QUAD_DEC_BND
109 = 8f * QUAD_DEC_ERR_SUBPIX;
110
111 //////////////////////////////////////////////////////////////////////////////
112 // SCAN LINE
113 //////////////////////////////////////////////////////////////////////////////
114 // crossings ie subpixel edge x coordinates
115 private int[] crossings;
116 // auxiliary storage for crossings (merge sort)
117 private int[] aux_crossings;
118
119 // indices into the segment pointer lists. They indicate the "active"
120 // sublist in the segment lists (the portion of the list that contains
121 // all the segments that cross the next scan line).
122 private int edgeCount;
123 private int[] edgePtrs;
124 // auxiliary storage for edge pointers (merge sort)
125 private int[] aux_edgePtrs;
126
127 // max used for both edgePtrs and crossings (stats only)
128 private int activeEdgeMaxUsed;
129
160 private final IntArrayCache.Reference edgeBucketCounts_ref;
161
162 boolean useRLE = false;
163
164 // Flattens using adaptive forward differencing. This only carries out
165 // one iteration of the AFD loop. All it does is update AFD variables (i.e.
166 // X0, Y0, D*[X|Y], COUNT; not variables used for computing scanline crossings).
167 private void quadBreakIntoLinesAndAdd(float x0, float y0,
168 final Curve c,
169 final float x2, final float y2)
170 {
171 int count = 1; // dt = 1 / count
172
173 // maximum(ddX|Y) = norm(dbx, dby) * dt^2 (= 1)
174 float maxDD = Math.abs(c.dbx) + Math.abs(c.dby);
175
176 final float _DEC_BND = QUAD_DEC_BND;
177
178 while (maxDD >= _DEC_BND) {
179 // divide step by half:
180 maxDD /= 4f; // error divided by 2^2 = 4
181
182 count <<= 1;
183 if (DO_STATS) {
184 rdrCtx.stats.stat_rdr_quadBreak_dec.add(count);
185 }
186 }
187
188 int nL = 0; // line count
189 if (count > 1) {
190 final float icount = 1f / count; // dt
191 final float icount2 = icount * icount; // dt^2
192
193 final float ddx = c.dbx * icount2;
194 final float ddy = c.dby * icount2;
195 float dx = c.bx * icount2 + c.cx * icount;
196 float dy = c.by * icount2 + c.cy * icount;
197
198 float x1, y1;
199
200 while (--count > 0) {
201 x1 = x0 + dx;
202 dx += ddx;
203 y1 = y0 + dy;
204 dy += ddy;
205
206 addLine(x0, y0, x1, y1);
207
208 if (DO_STATS) { nL++; }
209 x0 = x1;
210 y0 = y1;
217 }
218 }
219
220 // x0, y0 and x3,y3 are the endpoints of the curve. We could compute these
221 // using c.xat(0),c.yat(0) and c.xat(1),c.yat(1), but this might introduce
222 // numerical errors, and our callers already have the exact values.
223 // Another alternative would be to pass all the control points, and call
224 // c.set here, but then too many numbers are passed around.
225 private void curveBreakIntoLinesAndAdd(float x0, float y0,
226 final Curve c,
227 final float x3, final float y3)
228 {
229 int count = CUB_COUNT;
230 final float icount = CUB_INV_COUNT; // dt
231 final float icount2 = CUB_INV_COUNT_2; // dt^2
232 final float icount3 = CUB_INV_COUNT_3; // dt^3
233
234 // the dx and dy refer to forward differencing variables, not the last
235 // coefficients of the "points" polynomial
236 float dddx, dddy, ddx, ddy, dx, dy;
237 dddx = 2f * c.dax * icount3;
238 dddy = 2f * c.day * icount3;
239 ddx = dddx + c.dbx * icount2;
240 ddy = dddy + c.dby * icount2;
241 dx = c.ax * icount3 + c.bx * icount2 + c.cx * icount;
242 dy = c.ay * icount3 + c.by * icount2 + c.cy * icount;
243
244 // we use x0, y0 to walk the line
245 float x1 = x0, y1 = y0;
246 int nL = 0; // line count
247
248 final float _DEC_BND = CUB_DEC_BND;
249 final float _INC_BND = CUB_INC_BND;
250
251 while (count > 0) {
252 // divide step by half:
253 while (Math.abs(ddx) + Math.abs(ddy) >= _DEC_BND) {
254 dddx /= 8f;
255 dddy /= 8f;
256 ddx = ddx/4f - dddx;
257 ddy = ddy/4f - dddy;
258 dx = (dx - ddx) / 2f;
259 dy = (dy - ddy) / 2f;
260
261 count <<= 1;
262 if (DO_STATS) {
263 rdrCtx.stats.stat_rdr_curveBreak_dec.add(count);
264 }
265 }
266
267 // double step:
268 // TODO: why use first derivative dX|Y instead of second ddX|Y ?
269 // both scale changes should use speed or acceleration to have the same metric.
270
271 // can only do this on even "count" values, because we must divide count by 2
272 while (count % 2 == 0
273 && Math.abs(dx) + Math.abs(dy) <= _INC_BND)
274 {
275 dx = 2f * dx + ddx;
276 dy = 2f * dy + ddy;
277 ddx = 4f * (ddx + dddx);
278 ddy = 4f * (ddy + dddy);
279 dddx *= 8f;
280 dddy *= 8f;
281
282 count >>= 1;
283 if (DO_STATS) {
284 rdrCtx.stats.stat_rdr_curveBreak_inc.add(count);
285 }
286 }
287 if (--count > 0) {
288 x1 += dx;
289 dx += ddx;
290 ddx += dddx;
291 y1 += dy;
292 dy += ddy;
293 ddy += dddy;
294 } else {
295 x1 = x3;
296 y1 = y3;
297 }
298
299 addLine(x0, y0, x1, y1);
300
332 // ceil(y1) or ceil(y2)
333 // upper integer (inclusive)
334 final int firstCrossing = FloatMath.max(FloatMath.ceil_int(y1), boundsMinY);
335
336 // note: use boundsMaxY (last Y exclusive) to compute correct coverage
337 // upper integer (exclusive)
338 final int lastCrossing = FloatMath.min(FloatMath.ceil_int(y2), boundsMaxY);
339
340 /* skip horizontal lines in pixel space and clip edges
341 out of y range [boundsMinY; boundsMaxY] */
342 if (firstCrossing >= lastCrossing) {
343 if (DO_MONITORS) {
344 rdrCtx.stats.mon_rdr_addLine.stop();
345 }
346 if (DO_STATS) {
347 rdrCtx.stats.stat_rdr_addLine_skip.add(1);
348 }
349 return;
350 }
351
352 // edge min/max X/Y are in subpixel space (inclusive) within bounds:
353 // note: Use integer crossings to ensure consistent range within
354 // edgeBuckets / edgeBucketCounts arrays in case of NaN values (int = 0)
355 if (firstCrossing < edgeMinY) {
356 edgeMinY = firstCrossing;
357 }
358 if (lastCrossing > edgeMaxY) {
359 edgeMaxY = lastCrossing;
360 }
361
362 // Use double-precision for improved accuracy:
363 final double x1d = x1;
364 final double y1d = y1;
365 final double slope = (x1d - x2) / (y1d - y2);
366
367 if (slope >= 0.0) { // <==> x1 < x2
368 if (x1 < edgeMinX) {
369 edgeMinX = x1;
370 }
371 if (x2 > edgeMaxX) {
372 edgeMaxX = x2;
373 }
374 } else {
375 if (x2 < edgeMinX) {
376 edgeMinX = x2;
377 }
378 if (x1 > edgeMaxX) {
379 edgeMaxX = x1;
380 }
381 }
382
383 // local variables for performance:
384 final int _SIZEOF_EDGE_BYTES = SIZEOF_EDGE_BYTES;
385
386 final OffHeapArray _edges = edges;
387
445 final long slope_fixed = (long) (POWER_2_TO_32 * slope);
446
447 // last bit set to 0 to keep orientation:
448 _unsafe.putInt(addr, (((int) (slope_fixed >> 31L)) & ALL_BUT_LSB));
449 addr += SIZE_INT;
450 _unsafe.putInt(addr, ((int) slope_fixed) >>> 1);
451 addr += SIZE_INT;
452
453 final int[] _edgeBuckets = edgeBuckets;
454 final int[] _edgeBucketCounts = edgeBucketCounts;
455
456 final int _boundsMinY = boundsMinY;
457
458 // each bucket is a linked list. this method adds ptr to the
459 // start of the "bucket"th linked list.
460 final int bucketIdx = firstCrossing - _boundsMinY;
461
462 // pointer from bucket
463 _unsafe.putInt(addr, _edgeBuckets[bucketIdx]);
464 addr += SIZE_INT;
465 // y max (inclusive)
466 _unsafe.putInt(addr, lastCrossing);
467
468 // Update buckets:
469 // directly the edge struct "pointer"
470 _edgeBuckets[bucketIdx] = edgePtr;
471 _edgeBucketCounts[bucketIdx] += 2; // 1 << 1
472 // last bit means edge end
473 _edgeBucketCounts[lastCrossing - _boundsMinY] |= 0x1;
474
475 // update free pointer (ie length in bytes)
476 _edges.used += _SIZEOF_EDGE_BYTES;
477
478 if (DO_MONITORS) {
479 rdrCtx.stats.mon_rdr_addLine.stop();
480 }
481 }
482
483 // END EDGE LIST
484 //////////////////////////////////////////////////////////////////////////////
485
637 // unused arrays
638 edgeBuckets = edgeBuckets_ref.putArray(edgeBuckets, 0, 0);
639 edgeBucketCounts = edgeBucketCounts_ref.putArray(edgeBucketCounts, 0, 0);
640 }
641
642 // At last: resize back off-heap edges to initial size
643 if (edges.length != INITIAL_EDGES_CAPACITY) {
644 // note: may throw OOME:
645 edges.resize(INITIAL_EDGES_CAPACITY);
646 }
647 if (DO_CLEAN_DIRTY) {
648 // Force zero-fill dirty arrays:
649 edges.fill(BYTE_0);
650 }
651 if (DO_MONITORS) {
652 rdrCtx.stats.mon_rdr_endRendering.stop();
653 }
654 }
655
656 private static float tosubpixx(final float pix_x) {
657 return F_SUBPIXEL_POSITIONS_X * pix_x;
658 }
659
660 private static float tosubpixy(final float pix_y) {
661 // shift y by -0.5 for fast ceil(y - 0.5):
662 return F_SUBPIXEL_POSITIONS_Y * pix_y - 0.5f;
663 }
664
665 @Override
666 public void moveTo(float pix_x0, float pix_y0) {
667 closePath();
668 final float sx = tosubpixx(pix_x0);
669 final float sy = tosubpixy(pix_y0);
670 this.sx0 = sx;
671 this.sy0 = sy;
672 this.x0 = sx;
673 this.y0 = sy;
674 }
675
676 @Override
677 public void lineTo(float pix_x1, float pix_y1) {
678 final float x1 = tosubpixx(pix_x1);
679 final float y1 = tosubpixy(pix_y1);
680 addLine(x0, y0, x1, y1);
681 x0 = x1;
682 y0 = y1;
1164 x1 = bboxx1;
1165 // skip right side (fast exit loop):
1166 i = numCrossings;
1167 }
1168
1169 if (x0 < x1) {
1170 x0 -= bboxx0; // turn x0, x1 from coords to indices
1171 x1 -= bboxx0; // in the alpha array.
1172
1173 pix_x = x0 >> _SUBPIXEL_LG_POSITIONS_X;
1174 pix_xmaxm1 = (x1 - 1) >> _SUBPIXEL_LG_POSITIONS_X;
1175
1176 if (pix_x == pix_xmaxm1) {
1177 // Start and end in same pixel
1178 tmp = (x1 - x0); // number of subpixels
1179 _alpha[pix_x ] += tmp;
1180 _alpha[pix_x + 1] -= tmp;
1181
1182 if (useBlkFlags) {
1183 // flag used blocks:
1184 _blkFlags[ pix_x >> _BLK_SIZE_LG] = 1;
1185 _blkFlags[(pix_x + 1) >> _BLK_SIZE_LG] = 1;
1186 }
1187 } else {
1188 tmp = (x0 & _SUBPIXEL_MASK_X);
1189 _alpha[pix_x ]
1190 += (_SUBPIXEL_POSITIONS_X - tmp);
1191 _alpha[pix_x + 1]
1192 += tmp;
1193
1194 pix_xmax = x1 >> _SUBPIXEL_LG_POSITIONS_X;
1195
1196 tmp = (x1 & _SUBPIXEL_MASK_X);
1197 _alpha[pix_xmax ]
1198 -= (_SUBPIXEL_POSITIONS_X - tmp);
1199 _alpha[pix_xmax + 1]
1200 -= tmp;
1201
1202 if (useBlkFlags) {
1203 // flag used blocks:
1204 _blkFlags[ pix_x >> _BLK_SIZE_LG] = 1;
1205 _blkFlags[(pix_x + 1) >> _BLK_SIZE_LG] = 1;
1206 _blkFlags[ pix_xmax >> _BLK_SIZE_LG] = 1;
1207 _blkFlags[(pix_xmax + 1) >> _BLK_SIZE_LG] = 1;
1208 }
1209 }
1210 }
1211 }
1212
1213 sum += crorientation;
1214 prev = curx;
1215 }
1216 } else {
1217 // Non-zero winding rule: optimize that case (default)
1218 // and avoid processing intermediate crossings
1219 for (i = 1, sum = 0;; i++) {
1220 sum += crorientation;
1221
1222 if (sum != 0) {
1223 // prev = min(curx)
1224 if (prev > curx) {
1225 prev = curx;
1226 }
1227 } else {
1235 x1 = bboxx1;
1236 // skip right side (fast exit loop):
1237 i = numCrossings;
1238 }
1239
1240 if (x0 < x1) {
1241 x0 -= bboxx0; // turn x0, x1 from coords to indices
1242 x1 -= bboxx0; // in the alpha array.
1243
1244 pix_x = x0 >> _SUBPIXEL_LG_POSITIONS_X;
1245 pix_xmaxm1 = (x1 - 1) >> _SUBPIXEL_LG_POSITIONS_X;
1246
1247 if (pix_x == pix_xmaxm1) {
1248 // Start and end in same pixel
1249 tmp = (x1 - x0); // number of subpixels
1250 _alpha[pix_x ] += tmp;
1251 _alpha[pix_x + 1] -= tmp;
1252
1253 if (useBlkFlags) {
1254 // flag used blocks:
1255 _blkFlags[ pix_x >> _BLK_SIZE_LG] = 1;
1256 _blkFlags[(pix_x + 1) >> _BLK_SIZE_LG] = 1;
1257 }
1258 } else {
1259 tmp = (x0 & _SUBPIXEL_MASK_X);
1260 _alpha[pix_x ]
1261 += (_SUBPIXEL_POSITIONS_X - tmp);
1262 _alpha[pix_x + 1]
1263 += tmp;
1264
1265 pix_xmax = x1 >> _SUBPIXEL_LG_POSITIONS_X;
1266
1267 tmp = (x1 & _SUBPIXEL_MASK_X);
1268 _alpha[pix_xmax ]
1269 -= (_SUBPIXEL_POSITIONS_X - tmp);
1270 _alpha[pix_xmax + 1]
1271 -= tmp;
1272
1273 if (useBlkFlags) {
1274 // flag used blocks:
1275 _blkFlags[ pix_x >> _BLK_SIZE_LG] = 1;
1276 _blkFlags[(pix_x + 1) >> _BLK_SIZE_LG] = 1;
1277 _blkFlags[ pix_xmax >> _BLK_SIZE_LG] = 1;
1278 _blkFlags[(pix_xmax + 1) >> _BLK_SIZE_LG] = 1;
1279 }
1280 }
1281 }
1282 prev = _MAX_VALUE;
1283 }
1284
1285 if (i == numCrossings) {
1286 break;
1287 }
1288
1289 curxo = _crossings[i];
1290 curx = curxo >> 1;
1291 // to turn {0, 1} into {-1, 1}, multiply by 2 and subtract 1.
1292 // last bit contains orientation (0 or 1)
1293 crorientation = ((curxo & 0x1) << 1) - 1;
1294 }
1295 }
1296 } // numCrossings > 0
1297
1298 // even if this last row had no crossings, alpha will be zeroed
|
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.marlin;
27
28 import static com.sun.marlin.OffHeapArray.SIZE_INT;
29 import jdk.internal.misc.Unsafe;
30
31 public final class Renderer implements MarlinRenderer, MarlinConst {
32
33 static final boolean DISABLE_RENDER = false;
34
35 private static final int ALL_BUT_LSB = 0xFFFFFFFE;
36 private static final int ERR_STEP_MAX = 0x7FFFFFFF; // = 2^31 - 1
37
38 private static final double POWER_2_TO_32 = 0x1.0p32;
39
40 // use float to make tosubpix methods faster (no int to float conversion)
41 static final float SUBPIXEL_SCALE_X = (float) SUBPIXEL_POSITIONS_X;
42 static final float SUBPIXEL_SCALE_Y = (float) SUBPIXEL_POSITIONS_Y;
43 static final int SUBPIXEL_MASK_X = SUBPIXEL_POSITIONS_X - 1;
44 static final int SUBPIXEL_MASK_Y = SUBPIXEL_POSITIONS_Y - 1;
45
46 // 2048 (pixelSize) pixels (height) x 8 subpixels = 64K
47 static final int INITIAL_BUCKET_ARRAY
48 = INITIAL_PIXEL_DIM * SUBPIXEL_POSITIONS_Y;
49
50 // crossing capacity = edges count / 4 ~ 1024
51 static final int INITIAL_CROSSING_COUNT = INITIAL_EDGES_COUNT >> 2;
52
53 // common to all types of input path segments.
54 // OFFSET as bytes
55 // only integer values:
56 public static final long OFF_CURX_OR = 0;
57 public static final long OFF_ERROR = OFF_CURX_OR + SIZE_INT;
58 public static final long OFF_BUMP_X = OFF_ERROR + SIZE_INT;
59 public static final long OFF_BUMP_ERR = OFF_BUMP_X + SIZE_INT;
60 public static final long OFF_NEXT = OFF_BUMP_ERR + SIZE_INT;
61 public static final long OFF_YMAX = OFF_NEXT + SIZE_INT;
62
63 // size of one edge in bytes
64 public static final int SIZEOF_EDGE_BYTES = (int)(OFF_YMAX + SIZE_INT);
65
66 // curve break into lines
67 // cubic error in subpixels to decrement step
68 private static final float CUB_DEC_ERR_SUBPIX
69 = 1.0f * (NORM_SUBPIXELS / 8.0f); // 1 pixel
70 // cubic error in subpixels to increment step
71 private static final float CUB_INC_ERR_SUBPIX
72 = 0.4f * (NORM_SUBPIXELS / 8.0f); // 0.4 pixel
73
74 // bad paths (59294/100000 == 59,29%, 94335 bad pixels (avg = 1,59), 3966 warnings (avg = 0,07)
75
76 // cubic bind length to decrement step
77 public static final float CUB_DEC_BND
78 = 8.0f * CUB_DEC_ERR_SUBPIX;
79 // cubic bind length to increment step
80 public static final float CUB_INC_BND
81 = 8.0f * CUB_INC_ERR_SUBPIX;
82
83 // cubic countlg
84 public static final int CUB_COUNT_LG = 2;
85 // cubic count = 2^countlg
86 private static final int CUB_COUNT = 1 << CUB_COUNT_LG;
87 // cubic count^2 = 4^countlg
88 private static final int CUB_COUNT_2 = 1 << (2 * CUB_COUNT_LG);
89 // cubic count^3 = 8^countlg
90 private static final int CUB_COUNT_3 = 1 << (3 * CUB_COUNT_LG);
91 // cubic dt = 1 / count
92 private static final float CUB_INV_COUNT = 1.0f / CUB_COUNT;
93 // cubic dt^2 = 1 / count^2 = 1 / 4^countlg
94 private static final float CUB_INV_COUNT_2 = 1.0f / CUB_COUNT_2;
95 // cubic dt^3 = 1 / count^3 = 1 / 8^countlg
96 private static final float CUB_INV_COUNT_3 = 1.0f / CUB_COUNT_3;
97
98 // quad break into lines
99 // quadratic error in subpixels
100 private static final float QUAD_DEC_ERR_SUBPIX
101 = 0.5f * (NORM_SUBPIXELS / 8.0f); // 0.5 pixel
102
103 // bad paths (62916/100000 == 62,92%, 103818 bad pixels (avg = 1,65), 6514 warnings (avg = 0,10)
104
105 // quadratic bind length to decrement step
106 public static final float QUAD_DEC_BND
107 = 8.0f * QUAD_DEC_ERR_SUBPIX;
108
109 //////////////////////////////////////////////////////////////////////////////
110 // SCAN LINE
111 //////////////////////////////////////////////////////////////////////////////
112 // crossings ie subpixel edge x coordinates
113 private int[] crossings;
114 // auxiliary storage for crossings (merge sort)
115 private int[] aux_crossings;
116
117 // indices into the segment pointer lists. They indicate the "active"
118 // sublist in the segment lists (the portion of the list that contains
119 // all the segments that cross the next scan line).
120 private int edgeCount;
121 private int[] edgePtrs;
122 // auxiliary storage for edge pointers (merge sort)
123 private int[] aux_edgePtrs;
124
125 // max used for both edgePtrs and crossings (stats only)
126 private int activeEdgeMaxUsed;
127
158 private final IntArrayCache.Reference edgeBucketCounts_ref;
159
160 boolean useRLE = false;
161
162 // Flattens using adaptive forward differencing. This only carries out
163 // one iteration of the AFD loop. All it does is update AFD variables (i.e.
164 // X0, Y0, D*[X|Y], COUNT; not variables used for computing scanline crossings).
165 private void quadBreakIntoLinesAndAdd(float x0, float y0,
166 final Curve c,
167 final float x2, final float y2)
168 {
169 int count = 1; // dt = 1 / count
170
171 // maximum(ddX|Y) = norm(dbx, dby) * dt^2 (= 1)
172 float maxDD = Math.abs(c.dbx) + Math.abs(c.dby);
173
174 final float _DEC_BND = QUAD_DEC_BND;
175
176 while (maxDD >= _DEC_BND) {
177 // divide step by half:
178 maxDD /= 4.0f; // error divided by 2^2 = 4
179
180 count <<= 1;
181 if (DO_STATS) {
182 rdrCtx.stats.stat_rdr_quadBreak_dec.add(count);
183 }
184 }
185
186 int nL = 0; // line count
187 if (count > 1) {
188 final float icount = 1.0f / count; // dt
189 final float icount2 = icount * icount; // dt^2
190
191 final float ddx = c.dbx * icount2;
192 final float ddy = c.dby * icount2;
193 float dx = c.bx * icount2 + c.cx * icount;
194 float dy = c.by * icount2 + c.cy * icount;
195
196 float x1, y1;
197
198 while (--count > 0) {
199 x1 = x0 + dx;
200 dx += ddx;
201 y1 = y0 + dy;
202 dy += ddy;
203
204 addLine(x0, y0, x1, y1);
205
206 if (DO_STATS) { nL++; }
207 x0 = x1;
208 y0 = y1;
215 }
216 }
217
218 // x0, y0 and x3,y3 are the endpoints of the curve. We could compute these
219 // using c.xat(0),c.yat(0) and c.xat(1),c.yat(1), but this might introduce
220 // numerical errors, and our callers already have the exact values.
221 // Another alternative would be to pass all the control points, and call
222 // c.set here, but then too many numbers are passed around.
223 private void curveBreakIntoLinesAndAdd(float x0, float y0,
224 final Curve c,
225 final float x3, final float y3)
226 {
227 int count = CUB_COUNT;
228 final float icount = CUB_INV_COUNT; // dt
229 final float icount2 = CUB_INV_COUNT_2; // dt^2
230 final float icount3 = CUB_INV_COUNT_3; // dt^3
231
232 // the dx and dy refer to forward differencing variables, not the last
233 // coefficients of the "points" polynomial
234 float dddx, dddy, ddx, ddy, dx, dy;
235 dddx = 2.0f * c.dax * icount3;
236 dddy = 2.0f * c.day * icount3;
237 ddx = dddx + c.dbx * icount2;
238 ddy = dddy + c.dby * icount2;
239 dx = c.ax * icount3 + c.bx * icount2 + c.cx * icount;
240 dy = c.ay * icount3 + c.by * icount2 + c.cy * icount;
241
242 // we use x0, y0 to walk the line
243 float x1 = x0, y1 = y0;
244 int nL = 0; // line count
245
246 final float _DEC_BND = CUB_DEC_BND;
247 final float _INC_BND = CUB_INC_BND;
248
249 while (count > 0) {
250 // divide step by half:
251 while (Math.abs(ddx) + Math.abs(ddy) >= _DEC_BND) {
252 dddx /= 8.0f;
253 dddy /= 8.0f;
254 ddx = ddx / 4.0f - dddx;
255 ddy = ddy / 4.0f - dddy;
256 dx = (dx - ddx) / 2.0f;
257 dy = (dy - ddy) / 2.0f;
258
259 count <<= 1;
260 if (DO_STATS) {
261 rdrCtx.stats.stat_rdr_curveBreak_dec.add(count);
262 }
263 }
264
265 // double step:
266 // can only do this on even "count" values, because we must divide count by 2
267 while (count % 2 == 0
268 && Math.abs(dx) + Math.abs(dy) <= _INC_BND)
269 {
270 dx = 2.0f * dx + ddx;
271 dy = 2.0f * dy + ddy;
272 ddx = 4.0f * (ddx + dddx);
273 ddy = 4.0f * (ddy + dddy);
274 dddx *= 8.0f;
275 dddy *= 8.0f;
276
277 count >>= 1;
278 if (DO_STATS) {
279 rdrCtx.stats.stat_rdr_curveBreak_inc.add(count);
280 }
281 }
282 if (--count > 0) {
283 x1 += dx;
284 dx += ddx;
285 ddx += dddx;
286 y1 += dy;
287 dy += ddy;
288 ddy += dddy;
289 } else {
290 x1 = x3;
291 y1 = y3;
292 }
293
294 addLine(x0, y0, x1, y1);
295
327 // ceil(y1) or ceil(y2)
328 // upper integer (inclusive)
329 final int firstCrossing = FloatMath.max(FloatMath.ceil_int(y1), boundsMinY);
330
331 // note: use boundsMaxY (last Y exclusive) to compute correct coverage
332 // upper integer (exclusive)
333 final int lastCrossing = FloatMath.min(FloatMath.ceil_int(y2), boundsMaxY);
334
335 /* skip horizontal lines in pixel space and clip edges
336 out of y range [boundsMinY; boundsMaxY] */
337 if (firstCrossing >= lastCrossing) {
338 if (DO_MONITORS) {
339 rdrCtx.stats.mon_rdr_addLine.stop();
340 }
341 if (DO_STATS) {
342 rdrCtx.stats.stat_rdr_addLine_skip.add(1);
343 }
344 return;
345 }
346
347 // edge min/max X/Y are in subpixel space (half-open interval):
348 // note: Use integer crossings to ensure consistent range within
349 // edgeBuckets / edgeBucketCounts arrays in case of NaN values (int = 0)
350 if (firstCrossing < edgeMinY) {
351 edgeMinY = firstCrossing;
352 }
353 if (lastCrossing > edgeMaxY) {
354 edgeMaxY = lastCrossing;
355 }
356
357 // Use double-precision for improved accuracy:
358 final double x1d = x1;
359 final double y1d = y1;
360 final double slope = (x1d - x2) / (y1d - y2);
361
362 if (slope >= 0.0d) { // <==> x1 < x2
363 if (x1 < edgeMinX) {
364 edgeMinX = x1;
365 }
366 if (x2 > edgeMaxX) {
367 edgeMaxX = x2;
368 }
369 } else {
370 if (x2 < edgeMinX) {
371 edgeMinX = x2;
372 }
373 if (x1 > edgeMaxX) {
374 edgeMaxX = x1;
375 }
376 }
377
378 // local variables for performance:
379 final int _SIZEOF_EDGE_BYTES = SIZEOF_EDGE_BYTES;
380
381 final OffHeapArray _edges = edges;
382
440 final long slope_fixed = (long) (POWER_2_TO_32 * slope);
441
442 // last bit set to 0 to keep orientation:
443 _unsafe.putInt(addr, (((int) (slope_fixed >> 31L)) & ALL_BUT_LSB));
444 addr += SIZE_INT;
445 _unsafe.putInt(addr, ((int) slope_fixed) >>> 1);
446 addr += SIZE_INT;
447
448 final int[] _edgeBuckets = edgeBuckets;
449 final int[] _edgeBucketCounts = edgeBucketCounts;
450
451 final int _boundsMinY = boundsMinY;
452
453 // each bucket is a linked list. this method adds ptr to the
454 // start of the "bucket"th linked list.
455 final int bucketIdx = firstCrossing - _boundsMinY;
456
457 // pointer from bucket
458 _unsafe.putInt(addr, _edgeBuckets[bucketIdx]);
459 addr += SIZE_INT;
460 // y max (exclusive)
461 _unsafe.putInt(addr, lastCrossing);
462
463 // Update buckets:
464 // directly the edge struct "pointer"
465 _edgeBuckets[bucketIdx] = edgePtr;
466 _edgeBucketCounts[bucketIdx] += 2; // 1 << 1
467 // last bit means edge end
468 _edgeBucketCounts[lastCrossing - _boundsMinY] |= 0x1;
469
470 // update free pointer (ie length in bytes)
471 _edges.used += _SIZEOF_EDGE_BYTES;
472
473 if (DO_MONITORS) {
474 rdrCtx.stats.mon_rdr_addLine.stop();
475 }
476 }
477
478 // END EDGE LIST
479 //////////////////////////////////////////////////////////////////////////////
480
632 // unused arrays
633 edgeBuckets = edgeBuckets_ref.putArray(edgeBuckets, 0, 0);
634 edgeBucketCounts = edgeBucketCounts_ref.putArray(edgeBucketCounts, 0, 0);
635 }
636
637 // At last: resize back off-heap edges to initial size
638 if (edges.length != INITIAL_EDGES_CAPACITY) {
639 // note: may throw OOME:
640 edges.resize(INITIAL_EDGES_CAPACITY);
641 }
642 if (DO_CLEAN_DIRTY) {
643 // Force zero-fill dirty arrays:
644 edges.fill(BYTE_0);
645 }
646 if (DO_MONITORS) {
647 rdrCtx.stats.mon_rdr_endRendering.stop();
648 }
649 }
650
651 private static float tosubpixx(final float pix_x) {
652 return SUBPIXEL_SCALE_X * pix_x;
653 }
654
655 private static float tosubpixy(final float pix_y) {
656 // shift y by -0.5 for fast ceil(y - 0.5):
657 return SUBPIXEL_SCALE_Y * pix_y - 0.5f;
658 }
659
660 @Override
661 public void moveTo(float pix_x0, float pix_y0) {
662 closePath();
663 final float sx = tosubpixx(pix_x0);
664 final float sy = tosubpixy(pix_y0);
665 this.sx0 = sx;
666 this.sy0 = sy;
667 this.x0 = sx;
668 this.y0 = sy;
669 }
670
671 @Override
672 public void lineTo(float pix_x1, float pix_y1) {
673 final float x1 = tosubpixx(pix_x1);
674 final float y1 = tosubpixy(pix_y1);
675 addLine(x0, y0, x1, y1);
676 x0 = x1;
677 y0 = y1;
1159 x1 = bboxx1;
1160 // skip right side (fast exit loop):
1161 i = numCrossings;
1162 }
1163
1164 if (x0 < x1) {
1165 x0 -= bboxx0; // turn x0, x1 from coords to indices
1166 x1 -= bboxx0; // in the alpha array.
1167
1168 pix_x = x0 >> _SUBPIXEL_LG_POSITIONS_X;
1169 pix_xmaxm1 = (x1 - 1) >> _SUBPIXEL_LG_POSITIONS_X;
1170
1171 if (pix_x == pix_xmaxm1) {
1172 // Start and end in same pixel
1173 tmp = (x1 - x0); // number of subpixels
1174 _alpha[pix_x ] += tmp;
1175 _alpha[pix_x + 1] -= tmp;
1176
1177 if (useBlkFlags) {
1178 // flag used blocks:
1179 // note: block processing handles extra pixel:
1180 _blkFlags[pix_x >> _BLK_SIZE_LG] = 1;
1181 }
1182 } else {
1183 tmp = (x0 & _SUBPIXEL_MASK_X);
1184 _alpha[pix_x ]
1185 += (_SUBPIXEL_POSITIONS_X - tmp);
1186 _alpha[pix_x + 1]
1187 += tmp;
1188
1189 pix_xmax = x1 >> _SUBPIXEL_LG_POSITIONS_X;
1190
1191 tmp = (x1 & _SUBPIXEL_MASK_X);
1192 _alpha[pix_xmax ]
1193 -= (_SUBPIXEL_POSITIONS_X - tmp);
1194 _alpha[pix_xmax + 1]
1195 -= tmp;
1196
1197 if (useBlkFlags) {
1198 // flag used blocks:
1199 // note: block processing handles extra pixel:
1200 _blkFlags[pix_x >> _BLK_SIZE_LG] = 1;
1201 _blkFlags[pix_xmax >> _BLK_SIZE_LG] = 1;
1202 }
1203 }
1204 }
1205 }
1206
1207 sum += crorientation;
1208 prev = curx;
1209 }
1210 } else {
1211 // Non-zero winding rule: optimize that case (default)
1212 // and avoid processing intermediate crossings
1213 for (i = 1, sum = 0;; i++) {
1214 sum += crorientation;
1215
1216 if (sum != 0) {
1217 // prev = min(curx)
1218 if (prev > curx) {
1219 prev = curx;
1220 }
1221 } else {
1229 x1 = bboxx1;
1230 // skip right side (fast exit loop):
1231 i = numCrossings;
1232 }
1233
1234 if (x0 < x1) {
1235 x0 -= bboxx0; // turn x0, x1 from coords to indices
1236 x1 -= bboxx0; // in the alpha array.
1237
1238 pix_x = x0 >> _SUBPIXEL_LG_POSITIONS_X;
1239 pix_xmaxm1 = (x1 - 1) >> _SUBPIXEL_LG_POSITIONS_X;
1240
1241 if (pix_x == pix_xmaxm1) {
1242 // Start and end in same pixel
1243 tmp = (x1 - x0); // number of subpixels
1244 _alpha[pix_x ] += tmp;
1245 _alpha[pix_x + 1] -= tmp;
1246
1247 if (useBlkFlags) {
1248 // flag used blocks:
1249 // note: block processing handles extra pixel:
1250 _blkFlags[pix_x >> _BLK_SIZE_LG] = 1;
1251 }
1252 } else {
1253 tmp = (x0 & _SUBPIXEL_MASK_X);
1254 _alpha[pix_x ]
1255 += (_SUBPIXEL_POSITIONS_X - tmp);
1256 _alpha[pix_x + 1]
1257 += tmp;
1258
1259 pix_xmax = x1 >> _SUBPIXEL_LG_POSITIONS_X;
1260
1261 tmp = (x1 & _SUBPIXEL_MASK_X);
1262 _alpha[pix_xmax ]
1263 -= (_SUBPIXEL_POSITIONS_X - tmp);
1264 _alpha[pix_xmax + 1]
1265 -= tmp;
1266
1267 if (useBlkFlags) {
1268 // flag used blocks:
1269 // note: block processing handles extra pixel:
1270 _blkFlags[pix_x >> _BLK_SIZE_LG] = 1;
1271 _blkFlags[pix_xmax >> _BLK_SIZE_LG] = 1;
1272 }
1273 }
1274 }
1275 prev = _MAX_VALUE;
1276 }
1277
1278 if (i == numCrossings) {
1279 break;
1280 }
1281
1282 curxo = _crossings[i];
1283 curx = curxo >> 1;
1284 // to turn {0, 1} into {-1, 1}, multiply by 2 and subtract 1.
1285 // last bit contains orientation (0 or 1)
1286 crorientation = ((curxo & 0x1) << 1) - 1;
1287 }
1288 }
1289 } // numCrossings > 0
1290
1291 // even if this last row had no crossings, alpha will be zeroed
|