1 /*
   2  * Copyright (c) 2007, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  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 DRendererNoAA implements DMarlinRenderer, 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 = 0x7Dffffff; // = 2^31 - 1
  37 
  38     private static final double POWER_2_TO_32 = 0x1.0p32;
  39 
  40     // 2048 (pixelSize) pixels (height) x 8 subpixels = 64K
  41     static final int INITIAL_BUCKET_ARRAY = INITIAL_PIXEL_DIM;
  42 
  43     // crossing capacity = edges count / 4 ~ 1024
  44     static final int INITIAL_CROSSING_COUNT = INITIAL_EDGES_COUNT >> 2;
  45 
  46     // common to all types of input path segments.
  47     // OFFSET as bytes
  48     // only integer values:
  49     public static final long OFF_CURX_OR  = 0;
  50     public static final long OFF_ERROR    = OFF_CURX_OR  + SIZE_INT;
  51     public static final long OFF_BUMP_X   = OFF_ERROR    + SIZE_INT;
  52     public static final long OFF_BUMP_ERR = OFF_BUMP_X   + SIZE_INT;
  53     public static final long OFF_NEXT     = OFF_BUMP_ERR + SIZE_INT;
  54     public static final long OFF_YMAX     = OFF_NEXT     + SIZE_INT;
  55 
  56     // size of one edge in bytes
  57     public static final int SIZEOF_EDGE_BYTES = (int)(OFF_YMAX + SIZE_INT);
  58 
  59     // curve break into lines
  60     // cubic error in subpixels to decrement step
  61     private static final double CUB_DEC_ERR_SUBPIX
  62         = 1D * (1D / 8D); // 1 pixel for typical 1x1 subpixels
  63     // cubic error in subpixels to increment step
  64     private static final double CUB_INC_ERR_SUBPIX
  65         = 0.4D * (1D / 8D); // 0.4 pixel for typical 1x1 subpixels
  66 
  67     // cubic bind length to decrement step = 8 * error in subpixels
  68     // multiply by 8 = error scale factor:
  69     public static final double CUB_DEC_BND
  70         = 8D * CUB_DEC_ERR_SUBPIX;
  71     // cubic bind length to increment step = 8 * error in subpixels
  72     public static final double CUB_INC_BND
  73         = 8D * CUB_INC_ERR_SUBPIX;
  74 
  75     // cubic countlg
  76     public static final int CUB_COUNT_LG = 2;
  77     // cubic count = 2^countlg
  78     private static final int CUB_COUNT = 1 << CUB_COUNT_LG;
  79     // cubic count^2 = 4^countlg
  80     private static final int CUB_COUNT_2 = 1 << (2 * CUB_COUNT_LG);
  81     // cubic count^3 = 8^countlg
  82     private static final int CUB_COUNT_3 = 1 << (3 * CUB_COUNT_LG);
  83     // cubic dt = 1 / count
  84     private static final double CUB_INV_COUNT = 1D / CUB_COUNT;
  85     // cubic dt^2 = 1 / count^2 = 1 / 4^countlg
  86     private static final double CUB_INV_COUNT_2 = 1D / CUB_COUNT_2;
  87     // cubic dt^3 = 1 / count^3 = 1 / 8^countlg
  88     private static final double CUB_INV_COUNT_3 = 1D / CUB_COUNT_3;
  89 
  90     // quad break into lines
  91     // quadratic error in subpixels
  92     private static final double QUAD_DEC_ERR_SUBPIX
  93         = 0.5D * (1D / 8D); // 1 pixel for typical 1x1 subpixels
  94 
  95     // quadratic bind length to decrement step = 8 * error in subpixels
  96     public static final double QUAD_DEC_BND
  97         = 8D * QUAD_DEC_ERR_SUBPIX;
  98 
  99     public static final boolean USE_SUBDIVIDE_QUAD = false;
 100     public static final int SUBDIVIDE_MAX = 30;
 101 
 102     public static final double QUAD_ERR_SUBPIX = 1D / 16D;
 103     public static final double MAX_FLAT_SQ
 104         = 4D * QUAD_ERR_SUBPIX * QUAD_ERR_SUBPIX; // x4
 105 
 106 //////////////////////////////////////////////////////////////////////////////
 107 //  SCAN LINE
 108 //////////////////////////////////////////////////////////////////////////////
 109     // crossings ie subpixel edge x coordinates
 110     private int[] crossings;
 111     // auxiliary storage for crossings (merge sort)
 112     private int[] aux_crossings;
 113 
 114     // indices into the segment pointer lists. They indicate the "active"
 115     // sublist in the segment lists (the portion of the list that contains
 116     // all the segments that cross the next scan line).
 117     private int edgeCount;
 118     private int[] edgePtrs;
 119     // auxiliary storage for edge pointers (merge sort)
 120     private int[] aux_edgePtrs;
 121 
 122     // max used for both edgePtrs and crossings (stats only)
 123     private int activeEdgeMaxUsed;
 124 
 125     // crossings ref (dirty)
 126     private final IntArrayCache.Reference crossings_ref;
 127     // edgePtrs ref (dirty)
 128     private final IntArrayCache.Reference edgePtrs_ref;
 129     // merge sort initial arrays (large enough to satisfy most usages) (1024)
 130     // aux_crossings ref (dirty)
 131     private final IntArrayCache.Reference aux_crossings_ref;
 132     // aux_edgePtrs ref (dirty)
 133     private final IntArrayCache.Reference aux_edgePtrs_ref;
 134 
 135 //////////////////////////////////////////////////////////////////////////////
 136 //  EDGE LIST
 137 //////////////////////////////////////////////////////////////////////////////
 138     private int edgeMinY = Integer.MAX_VALUE;
 139     private int edgeMaxY = Integer.MIN_VALUE;
 140     private double edgeMinX = Double.POSITIVE_INFINITY;
 141     private double edgeMaxX = Double.NEGATIVE_INFINITY;
 142 
 143     // edges [doubles|ints] stored in off-heap memory
 144     private final OffHeapArray edges;
 145 
 146     private int[] edgeBuckets;
 147     private int[] edgeBucketCounts; // 2*newedges + (1 if pruning needed)
 148     // used range for edgeBuckets / edgeBucketCounts
 149     private int buckets_minY;
 150     private int buckets_maxY;
 151 
 152     // edgeBuckets ref (clean)
 153     private final IntArrayCache.Reference edgeBuckets_ref;
 154     // edgeBucketCounts ref (clean)
 155     private final IntArrayCache.Reference edgeBucketCounts_ref;
 156 
 157     boolean useRLE = false;
 158 
 159     // Flattens using adaptive forward differencing. This only carries out
 160     // one iteration of the AFD loop. All it does is update AFD variables (i.e.
 161     // X0, Y0, D*[X|Y], COUNT; not variables used for computing scanline crossings).
 162     private void quadBreakIntoLinesAndAdd(double x0, double y0,
 163                                           final DCurve c,
 164                                           final double x2, final double y2)
 165     {
 166         int count = 1; // dt = 1 / count
 167 
 168         // maximum(ddX|Y) = norm(dbx, dby) * dt^2 (= 1)
 169         double maxDD = FloatMath.max(Math.abs(c.dbx), Math.abs(c.dby));
 170 
 171         final double _DEC_BND = QUAD_DEC_BND;
 172 
 173         while (maxDD >= _DEC_BND) {
 174             // divide step by half:
 175             maxDD /= 4D; // error divided by 2^2 = 4
 176 
 177             count <<= 1;
 178             if (DO_STATS) {
 179                 rdrCtx.stats.stat_rdr_quadBreak_dec.add(count);
 180             }
 181         }
 182 
 183         int nL = 0; // line count
 184         if (count > 1) {
 185             final double icount = 1D / count; // dt
 186             final double icount2 = icount * icount; // dt^2
 187 
 188             final double ddx = c.dbx * icount2;
 189             final double ddy = c.dby * icount2;
 190             double dx = c.bx * icount2 + c.cx * icount;
 191             double dy = c.by * icount2 + c.cy * icount;
 192 
 193             double x1, y1;
 194 
 195             while (--count > 0) {
 196                 x1 = x0 + dx;
 197                 dx += ddx;
 198                 y1 = y0 + dy;
 199                 dy += ddy;
 200 
 201                 addLine(x0, y0, x1, y1);
 202 
 203                 if (DO_STATS) { nL++; }
 204                 x0 = x1;
 205                 y0 = y1;
 206             }
 207         }
 208         addLine(x0, y0, x2, y2);
 209 
 210         if (DO_STATS) {
 211             rdrCtx.stats.stat_rdr_quadBreak.add(nL + 1);
 212         }
 213     }
 214 
 215     // x0, y0 and x3,y3 are the endpoints of the curve. We could compute these
 216     // using c.xat(0),c.yat(0) and c.xat(1),c.yat(1), but this might introduce
 217     // numerical errors, and our callers already have the exact values.
 218     // Another alternative would be to pass all the control points, and call
 219     // c.set here, but then too many numbers are passed around.
 220     private void curveBreakIntoLinesAndAdd(double x0, double y0,
 221                                            final DCurve c,
 222                                            final double x3, final double y3)
 223     {
 224         int count           = CUB_COUNT;
 225         final double icount  = CUB_INV_COUNT;   // dt
 226         final double icount2 = CUB_INV_COUNT_2; // dt^2
 227         final double icount3 = CUB_INV_COUNT_3; // dt^3
 228 
 229         // the dx and dy refer to forward differencing variables, not the last
 230         // coefficients of the "points" polynomial
 231         double dddx, dddy, ddx, ddy, dx, dy;
 232         dddx = 2D * c.dax * icount3;
 233         dddy = 2D * c.day * icount3;
 234         ddx = dddx + c.dbx * icount2;
 235         ddy = dddy + c.dby * icount2;
 236         dx = c.ax * icount3 + c.bx * icount2 + c.cx * icount;
 237         dy = c.ay * icount3 + c.by * icount2 + c.cy * icount;
 238 
 239         // we use x0, y0 to walk the line
 240         double x1 = x0, y1 = y0;
 241         int nL = 0; // line count
 242 
 243         final double _DEC_BND = CUB_DEC_BND;
 244         final double _INC_BND = CUB_INC_BND;
 245 
 246         while (count > 0) {
 247             // divide step by half:
 248             while (Math.abs(ddx) >= _DEC_BND || Math.abs(ddy) >= _DEC_BND) {
 249                 dddx /= 8D;
 250                 dddy /= 8D;
 251                 ddx = ddx/4D - dddx;
 252                 ddy = ddy/4D - dddy;
 253                 dx = (dx - ddx) / 2D;
 254                 dy = (dy - ddy) / 2D;
 255 
 256                 count <<= 1;
 257                 if (DO_STATS) {
 258                     rdrCtx.stats.stat_rdr_curveBreak_dec.add(count);
 259                 }
 260             }
 261 
 262             // double step:
 263             // TODO: why use first derivative dX|Y instead of second ddX|Y ?
 264             // both scale changes should use speed or acceleration to have the same metric.
 265 
 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) <= _INC_BND && Math.abs(dy) <= _INC_BND)
 269             {
 270                 dx = 2D * dx + ddx;
 271                 dy = 2D * dy + ddy;
 272                 ddx = 4D * (ddx + dddx);
 273                 ddy = 4D * (ddy + dddy);
 274                 dddx *= 8D;
 275                 dddy *= 8D;
 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 
 296             if (DO_STATS) { nL++; }
 297             x0 = x1;
 298             y0 = y1;
 299         }
 300         if (DO_STATS) {
 301             rdrCtx.stats.stat_rdr_curveBreak.add(nL);
 302         }
 303     }
 304 
 305     private void addLine(double x1, double y1, double x2, double y2) {
 306         if (DO_MONITORS) {
 307             rdrCtx.stats.mon_rdr_addLine.start();
 308         }
 309         if (DO_STATS) {
 310             rdrCtx.stats.stat_rdr_addLine.add(1);
 311         }
 312         int or = 1; // orientation of the line. 1 if y increases, 0 otherwise.
 313         if (y2 < y1) {
 314             or = 0;
 315             double tmp = y2;
 316             y2 = y1;
 317             y1 = tmp;
 318             tmp = x2;
 319             x2 = x1;
 320             x1 = tmp;
 321         }
 322 
 323         // convert subpixel coordinates  into pixel positions (int)
 324 
 325         // The index of the pixel that holds the next HPC is at ceil(trueY - 0.5)
 326         // Since y1 and y2 are biased by -0.5 in tosubpixy(), this is simply
 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 (inclusive) within bounds:
 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.0) { // <==> 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 
 383         // get free pointer (ie length in bytes)
 384         final int edgePtr = _edges.used;
 385 
 386         // use substraction to avoid integer overflow:
 387         if (_edges.length - edgePtr < _SIZEOF_EDGE_BYTES) {
 388             // suppose _edges.length > _SIZEOF_EDGE_BYTES
 389             // so doubling size is enough to add needed bytes
 390             // note: throw IOOB if neededSize > 2Gb:
 391             final long edgeNewSize = ArrayCacheConst.getNewLargeSize(
 392                                         _edges.length,
 393                                         edgePtr + _SIZEOF_EDGE_BYTES);
 394 
 395             if (DO_STATS) {
 396                 rdrCtx.stats.stat_rdr_edges_resizes.add(edgeNewSize);
 397             }
 398             _edges.resize(edgeNewSize);
 399         }
 400 
 401 
 402         final Unsafe _unsafe = OffHeapArray.UNSAFE;
 403         final long SIZE_INT = 4L;
 404         long addr   = _edges.address + edgePtr;
 405 
 406         // The x value must be bumped up to its position at the next HPC we will evaluate.
 407         // "firstcrossing" is the (sub)pixel number where the next crossing occurs
 408         // thus, the actual coordinate of the next HPC is "firstcrossing + 0.5"
 409         // so the Y distance we cover is "firstcrossing + 0.5 - trueY".
 410         // Note that since y1 (and y2) are already biased by -0.5 in tosubpixy(), we have
 411         // y1 = trueY - 0.5
 412         // trueY = y1 + 0.5
 413         // firstcrossing + 0.5 - trueY = firstcrossing + 0.5 - (y1 + 0.5)
 414         //                             = firstcrossing - y1
 415         // The x coordinate at that HPC is then:
 416         // x1_intercept = x1 + (firstcrossing - y1) * slope
 417         // The next VPC is then given by:
 418         // VPC index = ceil(x1_intercept - 0.5), or alternately
 419         // VPC index = floor(x1_intercept - 0.5 + 1 - epsilon)
 420         // epsilon is hard to pin down in doubleing point, but easy in fixed point, so if
 421         // we convert to fixed point then these operations get easier:
 422         // long x1_fixed = x1_intercept * 2^32;  (fixed point 32.32 format)
 423         // curx = next VPC = fixed_floor(x1_fixed - 2^31 + 2^32 - 1)
 424         //                 = fixed_floor(x1_fixed + 2^31 - 1)
 425         //                 = fixed_floor(x1_fixed + 0x7Dffffff)
 426         // and error       = fixed_fract(x1_fixed + 0x7Dffffff)
 427         final double x1_intercept = x1d + (firstCrossing - y1d) * slope;
 428 
 429         // inlined scalb(x1_intercept, 32):
 430         final long x1_fixed_biased = ((long) (POWER_2_TO_32 * x1_intercept))
 431                                      + 0x7DffffffL;
 432         // curx:
 433         // last bit corresponds to the orientation
 434         _unsafe.putInt(addr, (((int) (x1_fixed_biased >> 31L)) & ALL_BUT_LSB) | or);
 435         addr += SIZE_INT;
 436         _unsafe.putInt(addr,  ((int)  x1_fixed_biased) >>> 1);
 437         addr += SIZE_INT;
 438 
 439         // inlined scalb(slope, 32):
 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 (inclusive)
 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 
 481     // Bounds of the drawing region, at subpixel precision.
 482     private int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY;
 483 
 484     // Current winding rule
 485     private int windingRule;
 486 
 487     // Current drawing position, i.e., final point of last segment
 488     private double x0, y0;
 489 
 490     // Position of most recent 'moveTo' command
 491     private double sx0, sy0;
 492 
 493     // per-thread renderer context
 494     final DRendererContext rdrCtx;
 495     // dirty curve
 496     private final DCurve curve;
 497 
 498     // clean alpha array (zero filled)
 499     private int[] alphaLine;
 500 
 501     // alphaLine ref (clean)
 502     private final IntArrayCache.Reference alphaLine_ref;
 503 
 504     private boolean enableBlkFlags = false;
 505     private boolean prevUseBlkFlags = false;
 506 
 507     /* block flags (0|1) */
 508     private int[] blkFlags;
 509 
 510     // blkFlags ref (clean)
 511     private final IntArrayCache.Reference blkFlags_ref;
 512 
 513     DRendererNoAA(final DRendererContext rdrCtx) {
 514         this.rdrCtx = rdrCtx;
 515 
 516         this.edges = rdrCtx.newOffHeapArray(INITIAL_EDGES_CAPACITY); // 96K
 517 
 518         this.curve = rdrCtx.curve;
 519 
 520         edgeBuckets_ref      = rdrCtx.newCleanIntArrayRef(INITIAL_BUCKET_ARRAY); // 64K
 521         edgeBucketCounts_ref = rdrCtx.newCleanIntArrayRef(INITIAL_BUCKET_ARRAY); // 64K
 522 
 523         edgeBuckets      = edgeBuckets_ref.initial;
 524         edgeBucketCounts = edgeBucketCounts_ref.initial;
 525 
 526         // 2048 (pixelsize) pixel large
 527         alphaLine_ref = rdrCtx.newCleanIntArrayRef(INITIAL_AA_ARRAY); // 8K
 528         alphaLine     = alphaLine_ref.initial;
 529 
 530         crossings_ref     = rdrCtx.newDirtyIntArrayRef(INITIAL_CROSSING_COUNT); // 2K
 531         aux_crossings_ref = rdrCtx.newDirtyIntArrayRef(INITIAL_CROSSING_COUNT); // 2K
 532         edgePtrs_ref      = rdrCtx.newDirtyIntArrayRef(INITIAL_CROSSING_COUNT); // 2K
 533         aux_edgePtrs_ref  = rdrCtx.newDirtyIntArrayRef(INITIAL_CROSSING_COUNT); // 2K
 534 
 535         crossings     = crossings_ref.initial;
 536         aux_crossings = aux_crossings_ref.initial;
 537         edgePtrs      = edgePtrs_ref.initial;
 538         aux_edgePtrs  = aux_edgePtrs_ref.initial;
 539 
 540         blkFlags_ref = rdrCtx.newCleanIntArrayRef(INITIAL_ARRAY); // 1K = 1 tile line
 541         blkFlags     = blkFlags_ref.initial;
 542     }
 543 
 544     public DRendererNoAA init(final int pix_boundsX, final int pix_boundsY,
 545                   final int pix_boundsWidth, final int pix_boundsHeight,
 546                   final int windingRule)
 547     {
 548         this.windingRule = windingRule;
 549 
 550         // bounds as half-open intervals: minX <= x < maxX and minY <= y < maxY
 551         this.boundsMinX = pix_boundsX;
 552         this.boundsMaxX = pix_boundsX + pix_boundsWidth;
 553         this.boundsMinY = pix_boundsY;
 554         this.boundsMaxY = pix_boundsY + pix_boundsHeight;
 555 
 556         if (DO_LOG_BOUNDS) {
 557             MarlinUtils.logInfo("boundsXY = [" + boundsMinX + " ... "
 558                                 + boundsMaxX + "[ [" + boundsMinY + " ... "
 559                                 + boundsMaxY + "[");
 560         }
 561 
 562         // see addLine: ceil(boundsMaxY) => boundsMaxY + 1
 563         // +1 for edgeBucketCounts
 564         final int edgeBucketsLength = (boundsMaxY - boundsMinY) + 1;
 565 
 566         if (edgeBucketsLength > INITIAL_BUCKET_ARRAY) {
 567             if (DO_STATS) {
 568                 rdrCtx.stats.stat_array_renderer_edgeBuckets
 569                     .add(edgeBucketsLength);
 570                 rdrCtx.stats.stat_array_renderer_edgeBucketCounts
 571                     .add(edgeBucketsLength);
 572             }
 573             edgeBuckets = edgeBuckets_ref.getArray(edgeBucketsLength);
 574             edgeBucketCounts = edgeBucketCounts_ref.getArray(edgeBucketsLength);
 575         }
 576 
 577         edgeMinY = Integer.MAX_VALUE;
 578         edgeMaxY = Integer.MIN_VALUE;
 579         edgeMinX = Double.POSITIVE_INFINITY;
 580         edgeMaxX = Double.NEGATIVE_INFINITY;
 581 
 582         // reset used mark:
 583         edgeCount = 0;
 584         activeEdgeMaxUsed = 0;
 585         edges.used = 0;
 586 
 587         // reset bbox:
 588         bboxX0 = 0;
 589         bboxX1 = 0;
 590 
 591         return this; // fluent API
 592     }
 593 
 594     /**
 595      * Disposes this renderer and recycle it clean up before reusing this instance
 596      */
 597     public void dispose() {
 598         if (DO_STATS) {
 599             rdrCtx.stats.stat_rdr_activeEdges.add(activeEdgeMaxUsed);
 600             rdrCtx.stats.stat_rdr_edges.add(edges.used);
 601             rdrCtx.stats.stat_rdr_edges_count.add(edges.used / SIZEOF_EDGE_BYTES);
 602             rdrCtx.stats.hist_rdr_edges_count.add(edges.used / SIZEOF_EDGE_BYTES);
 603             rdrCtx.stats.totalOffHeap += edges.length;
 604         }
 605         // Return arrays:
 606         crossings = crossings_ref.putArray(crossings);
 607         aux_crossings = aux_crossings_ref.putArray(aux_crossings);
 608 
 609         edgePtrs = edgePtrs_ref.putArray(edgePtrs);
 610         aux_edgePtrs = aux_edgePtrs_ref.putArray(aux_edgePtrs);
 611 
 612         alphaLine = alphaLine_ref.putArray(alphaLine, 0, 0); // already zero filled
 613         blkFlags  = blkFlags_ref.putArray(blkFlags, 0, 0); // already zero filled
 614 
 615         if (edgeMinY != Integer.MAX_VALUE) {
 616             // if context is maked as DIRTY:
 617             if (rdrCtx.dirty) {
 618                 // may happen if an exception if thrown in the pipeline processing:
 619                 // clear completely buckets arrays:
 620                 buckets_minY = 0;
 621                 buckets_maxY = boundsMaxY - boundsMinY;
 622             }
 623             // clear only used part
 624             edgeBuckets = edgeBuckets_ref.putArray(edgeBuckets, buckets_minY,
 625                                                                 buckets_maxY);
 626             edgeBucketCounts = edgeBucketCounts_ref.putArray(edgeBucketCounts,
 627                                                              buckets_minY,
 628                                                              buckets_maxY + 1);
 629         } else {
 630             // unused arrays
 631             edgeBuckets = edgeBuckets_ref.putArray(edgeBuckets, 0, 0);
 632             edgeBucketCounts = edgeBucketCounts_ref.putArray(edgeBucketCounts, 0, 0);
 633         }
 634 
 635         // At last: resize back off-heap edges to initial size
 636         if (edges.length != INITIAL_EDGES_CAPACITY) {
 637             // note: may throw OOME:
 638             edges.resize(INITIAL_EDGES_CAPACITY);
 639         }
 640         if (DO_CLEAN_DIRTY) {
 641             // Force zero-fill dirty arrays:
 642             edges.fill(BYTE_0);
 643         }
 644         if (DO_MONITORS) {
 645             rdrCtx.stats.mon_rdr_endRendering.stop();
 646         }
 647     }
 648 
 649     private static double tosubpixx(final double pix_x) {
 650         return pix_x;
 651     }
 652 
 653     private static double tosubpixy(final double pix_y) {
 654         // shift y by -0.5 for fast ceil(y - 0.5):
 655         return pix_y - 0.5D;
 656     }
 657 
 658     @Override
 659     public void moveTo(double pix_x0, double pix_y0) {
 660         closePath();
 661         final double sx = tosubpixx(pix_x0);
 662         final double sy = tosubpixy(pix_y0);
 663         this.sx0 = sx;
 664         this.sy0 = sy;
 665         this.x0 = sx;
 666         this.y0 = sy;
 667     }
 668 
 669     @Override
 670     public void lineTo(double pix_x1, double pix_y1) {
 671         final double x1 = tosubpixx(pix_x1);
 672         final double y1 = tosubpixy(pix_y1);
 673         addLine(x0, y0, x1, y1);
 674         x0 = x1;
 675         y0 = y1;
 676     }
 677 
 678     @Override
 679     public void curveTo(double x1, double y1,
 680             double x2, double y2,
 681             double x3, double y3)
 682     {
 683         final double xe = tosubpixx(x3);
 684         final double ye = tosubpixy(y3);
 685         curve.set(x0, y0, tosubpixx(x1), tosubpixy(y1),
 686                           tosubpixx(x2), tosubpixy(y2), xe, ye);
 687         curveBreakIntoLinesAndAdd(x0, y0, curve, xe, ye);
 688         x0 = xe;
 689         y0 = ye;
 690     }
 691 
 692     @Override
 693     public void quadTo(double pix_x1, double pix_y1,
 694                        double pix_x2, double pix_y2)
 695     {
 696         final double cx1 = tosubpixx(pix_x1);
 697         final double cy1 = tosubpixy(pix_y1);
 698 
 699         final double xe = tosubpixx(pix_x2);
 700         final double ye = tosubpixy(pix_y2);
 701 
 702         if (USE_SUBDIVIDE_QUAD) {
 703             subdivideQuad(0, x0, y0, cx1, cy1, xe, ye);
 704         } else {
 705             curve.set(x0, y0, cx1, cy1, xe, ye);
 706             quadBreakIntoLinesAndAdd(x0, y0, curve, xe, ye);
 707         }
 708         x0 = xe;
 709         y0 = ye;
 710     }
 711 
 712     void subdivideQuad(final int level,
 713                        final double x0, final double y0,
 714                        final double x1, final double y1,
 715                        final double x2, final double y2)
 716     {
 717         if (level < SUBDIVIDE_MAX) {
 718 
 719             /* Test if the curve is flat enough for insertion. */
 720 
 721             // use Roger Willcocks bezier flatness criterion
 722 //            var tolerance:Number = 4*tol*tol;
 723 
 724             final double ux = 2D * x1 - x0 - x2;
 725 
 726             final double uy = 2D * y1 - y0 - y2;
 727 
 728             if (ux * ux + uy * uy > MAX_FLAT_SQ) {
 729 /*
 730             AGG
 731             double dx = x2 - x0;
 732             double dy = y2 - y0;
 733             final double dist = Math.abs( (x1 - x2) * dy - (y1 - y2) * dx);
 734             // TODO: check collinearity ?
 735 */
 736 
 737 //            if (level == 0 || dist * dist > MAX_FLAT_SQ * (dx * dx + dy * dy)) {
 738 //            if (ptSegDistSq(x0, y0, x2, y2, x1, y1) > MAX_FLAT_SQ) {
 739                 final double cx01 = (x0 + x1) / 2.0D;
 740                 final double cx12 = (x1 + x2) / 2.0D;
 741                 final double cx012 = (cx01 + cx12) / 2.0D;
 742 
 743                 final double cy01 = (y0 + y1) / 2.0D;
 744                 final double cy12 = (y1 + y2) / 2.0D;
 745                 final double cy012 = (cy01 + cy12) / 2.0D;
 746 
 747                 subdivideQuad(level + 1, x0, y0, cx01, cy01, cx012, cy012);
 748                 subdivideQuad(level + 1, cx012, cy012, cx12, cy12, x2, y2);
 749                 return;
 750             }
 751         }
 752 
 753         addLine(x0, y0, x2, y2);
 754     }
 755 
 756     public static double ptSegDistSq(double x1, double y1,
 757                                     double x2, double y2,
 758                                     double px, double py)
 759     {
 760         // Adjust vectors relative to x1,y1
 761         // x2,y2 becomes relative vector from x1,y1 to end of segment
 762         x2 -= x1;
 763         y2 -= y1;
 764         // px,py becomes relative vector from x1,y1 to test point
 765         px -= x1;
 766         py -= y1;
 767         double dotprod = px * x2 + py * y2;
 768         double projlenSq;
 769         if (dotprod <= 0D) {
 770             // px,py is on the side of x1,y1 away from x2,y2
 771             // distance to segment is length of px,py vector
 772             // "length of its (clipped) projection" is now 0.0
 773             projlenSq = 0D;
 774         } else {
 775             // switch to backwards vectors relative to x2,y2
 776             // x2,y2 are already the negative of x1,y1=>x2,y2
 777             // to get px,py to be the negative of px,py=>x2,y2
 778             // the dot product of two negated vectors is the same
 779             // as the dot product of the two normal vectors
 780             px = x2 - px;
 781             py = y2 - py;
 782             dotprod = px * x2 + py * y2;
 783             if (dotprod <= 0D) {
 784                 // px,py is on the side of x2,y2 away from x1,y1
 785                 // distance to segment is length of (backwards) px,py vector
 786                 // "length of its (clipped) projection" is now 0.0
 787                 projlenSq = 0D;
 788             } else {
 789                 // px,py is between x1,y1 and x2,y2
 790                 // dotprod is the length of the px,py vector
 791                 // projected on the x2,y2=>x1,y1 vector times the
 792                 // length of the x2,y2=>x1,y1 vector
 793                 projlenSq = dotprod * dotprod / (x2 * x2 + y2 * y2);
 794             }
 795         }
 796         // Distance to line is now the length of the relative point
 797         // vector minus the length of its projection onto the line
 798         // (which is zero if the projection falls outside the range
 799         //  of the line segment).
 800         double lenSq = px * px + py * py - projlenSq;
 801         if (lenSq < 0D) {
 802             lenSq = 0D;
 803         }
 804         return lenSq;
 805     }
 806 
 807     @Override
 808     public void closePath() {
 809         addLine(x0, y0, sx0, sy0);
 810         x0 = sx0;
 811         y0 = sy0;
 812     }
 813 
 814     @Override
 815     public void pathDone() {
 816         closePath();
 817 
 818         // call endRendering() to determine the boundaries:
 819         endRendering();
 820     }
 821 
 822     private void _endRendering(final int ymin, final int ymax,
 823                                final MarlinAlphaConsumer ac)
 824     {
 825         if (DISABLE_RENDER) {
 826             return;
 827         }
 828 
 829         // Get X bounds as true pixel boundaries to compute correct pixel coverage:
 830         final int bboxx0 = bbox_spminX;
 831         final int bboxx1 = bbox_spmaxX;
 832 
 833         final boolean windingRuleEvenOdd = (windingRule == WIND_EVEN_ODD);
 834 
 835         // Useful when processing tile line by tile line
 836         final int[] _alpha = alphaLine;
 837 
 838         // local vars (performance):
 839         final OffHeapArray _edges = edges;
 840         final int[] _edgeBuckets = edgeBuckets;
 841         final int[] _edgeBucketCounts = edgeBucketCounts;
 842 
 843         int[] _crossings = this.crossings;
 844         int[] _edgePtrs  = this.edgePtrs;
 845 
 846         // merge sort auxiliary storage:
 847         int[] _aux_crossings = this.aux_crossings;
 848         int[] _aux_edgePtrs  = this.aux_edgePtrs;
 849 
 850         // copy constants:
 851         final long _OFF_ERROR    = OFF_ERROR;
 852         final long _OFF_BUMP_X   = OFF_BUMP_X;
 853         final long _OFF_BUMP_ERR = OFF_BUMP_ERR;
 854 
 855         final long _OFF_NEXT     = OFF_NEXT;
 856         final long _OFF_YMAX     = OFF_YMAX;
 857 
 858         final int _ALL_BUT_LSB   = ALL_BUT_LSB;
 859         final int _ERR_STEP_MAX  = ERR_STEP_MAX;
 860 
 861         // unsafe I/O:
 862         final Unsafe _unsafe = OffHeapArray.UNSAFE;
 863         final long    addr0  = _edges.address;
 864         long addr;
 865 
 866         final int _MIN_VALUE = Integer.MIN_VALUE;
 867         final int _MAX_VALUE = Integer.MAX_VALUE;
 868 
 869         // Now we iterate through the scanlines. We must tell emitRow the coord
 870         // of the first non-transparent pixel, so we must keep accumulators for
 871         // the first and last pixels of the section of the current pixel row
 872         // that we will emit.
 873         // We also need to accumulate pix_bbox, but the iterator does it
 874         // for us. We will just get the values from it once this loop is done
 875         int minX = _MAX_VALUE;
 876         int maxX = _MIN_VALUE;
 877 
 878         int y = ymin;
 879         int bucket = y - boundsMinY;
 880 
 881         int numCrossings = this.edgeCount;
 882         int edgePtrsLen = _edgePtrs.length;
 883         int crossingsLen = _crossings.length;
 884         int _arrayMaxUsed = activeEdgeMaxUsed;
 885         int ptrLen = 0, newCount, ptrEnd;
 886 
 887         int bucketcount, i, j, ecur;
 888         int cross, lastCross;
 889         int x0, x1, tmp, sum, prev, curx, curxo, crorientation, err;
 890 
 891         int low, high, mid, prevNumCrossings;
 892         boolean useBinarySearch;
 893 
 894         final int[] _blkFlags = blkFlags;
 895         final int _BLK_SIZE_LG = BLOCK_SIZE_LG;
 896         final int _BLK_SIZE = BLOCK_SIZE;
 897 
 898         final boolean _enableBlkFlagsHeuristics = ENABLE_BLOCK_FLAGS_HEURISTICS && this.enableBlkFlags;
 899 
 900         // Use block flags if large pixel span and few crossings:
 901         // ie mean(distance between crossings) is high
 902         boolean useBlkFlags = this.prevUseBlkFlags;
 903 
 904         final int stroking = rdrCtx.stroking;
 905 
 906         int lastY = -1; // last emited row
 907 
 908 
 909         // Iteration on scanlines
 910         for (; y < ymax; y++, bucket++) {
 911             // --- from former ScanLineIterator.next()
 912             bucketcount = _edgeBucketCounts[bucket];
 913 
 914             // marker on previously sorted edges:
 915             prevNumCrossings = numCrossings;
 916 
 917             // bucketCount indicates new edge / edge end:
 918             if (bucketcount != 0) {
 919                 if (DO_STATS) {
 920                     rdrCtx.stats.stat_rdr_activeEdges_updates.add(numCrossings);
 921                 }
 922 
 923                 // last bit set to 1 means that edges ends
 924                 if ((bucketcount & 0x1) != 0) {
 925                     // eviction in active edge list
 926                     // cache edges[] address + offset
 927                     addr = addr0 + _OFF_YMAX;
 928 
 929                     for (i = 0, newCount = 0; i < numCrossings; i++) {
 930                         // get the pointer to the edge
 931                         ecur = _edgePtrs[i];
 932                         // random access so use unsafe:
 933                         if (_unsafe.getInt(addr + ecur) > y) {
 934                             _edgePtrs[newCount++] = ecur;
 935                         }
 936                     }
 937                     // update marker on sorted edges minus removed edges:
 938                     prevNumCrossings = numCrossings = newCount;
 939                 }
 940 
 941                 ptrLen = bucketcount >> 1; // number of new edge
 942 
 943                 if (ptrLen != 0) {
 944                     if (DO_STATS) {
 945                         rdrCtx.stats.stat_rdr_activeEdges_adds.add(ptrLen);
 946                         if (ptrLen > 10) {
 947                             rdrCtx.stats.stat_rdr_activeEdges_adds_high.add(ptrLen);
 948                         }
 949                     }
 950                     ptrEnd = numCrossings + ptrLen;
 951 
 952                     if (edgePtrsLen < ptrEnd) {
 953                         if (DO_STATS) {
 954                             rdrCtx.stats.stat_array_renderer_edgePtrs.add(ptrEnd);
 955                         }
 956                         this.edgePtrs = _edgePtrs
 957                             = edgePtrs_ref.widenArray(_edgePtrs, numCrossings,
 958                                                       ptrEnd);
 959 
 960                         edgePtrsLen = _edgePtrs.length;
 961                         // Get larger auxiliary storage:
 962                         aux_edgePtrs_ref.putArray(_aux_edgePtrs);
 963 
 964                         // use ArrayCache.getNewSize() to use the same growing
 965                         // factor than widenArray():
 966                         if (DO_STATS) {
 967                             rdrCtx.stats.stat_array_renderer_aux_edgePtrs.add(ptrEnd);
 968                         }
 969                         this.aux_edgePtrs = _aux_edgePtrs
 970                             = aux_edgePtrs_ref.getArray(
 971                                 ArrayCacheConst.getNewSize(numCrossings, ptrEnd)
 972                             );
 973                     }
 974 
 975                     // cache edges[] address + offset
 976                     addr = addr0 + _OFF_NEXT;
 977 
 978                     // add new edges to active edge list:
 979                     for (ecur = _edgeBuckets[bucket];
 980                          numCrossings < ptrEnd; numCrossings++)
 981                     {
 982                         // store the pointer to the edge
 983                         _edgePtrs[numCrossings] = ecur;
 984                         // random access so use unsafe:
 985                         ecur = _unsafe.getInt(addr + ecur);
 986                     }
 987 
 988                     if (crossingsLen < numCrossings) {
 989                         // Get larger array:
 990                         crossings_ref.putArray(_crossings);
 991 
 992                         if (DO_STATS) {
 993                             rdrCtx.stats.stat_array_renderer_crossings
 994                                 .add(numCrossings);
 995                         }
 996                         this.crossings = _crossings
 997                             = crossings_ref.getArray(numCrossings);
 998 
 999                         // Get larger auxiliary storage:
1000                         aux_crossings_ref.putArray(_aux_crossings);
1001 
1002                         if (DO_STATS) {
1003                             rdrCtx.stats.stat_array_renderer_aux_crossings
1004                                 .add(numCrossings);
1005                         }
1006                         this.aux_crossings = _aux_crossings
1007                             = aux_crossings_ref.getArray(numCrossings);
1008 
1009                         crossingsLen = _crossings.length;
1010                     }
1011                     if (DO_STATS) {
1012                         // update max used mark
1013                         if (numCrossings > _arrayMaxUsed) {
1014                             _arrayMaxUsed = numCrossings;
1015                         }
1016                     }
1017                 } // ptrLen != 0
1018             } // bucketCount != 0
1019 
1020 
1021             if (numCrossings != 0) {
1022                 /*
1023                  * thresholds to switch to optimized merge sort
1024                  * for newly added edges + final merge pass.
1025                  */
1026                 if ((ptrLen < 10) || (numCrossings < 40)) {
1027                     if (DO_STATS) {
1028                         rdrCtx.stats.hist_rdr_crossings.add(numCrossings);
1029                         rdrCtx.stats.hist_rdr_crossings_adds.add(ptrLen);
1030                     }
1031 
1032                     /*
1033                      * threshold to use binary insertion sort instead of
1034                      * straight insertion sort (to reduce minimize comparisons).
1035                      */
1036                     useBinarySearch = (numCrossings >= 20);
1037 
1038                     // if small enough:
1039                     lastCross = _MIN_VALUE;
1040 
1041                     for (i = 0; i < numCrossings; i++) {
1042                         // get the pointer to the edge
1043                         ecur = _edgePtrs[i];
1044 
1045                         /* convert subpixel coordinates  into pixel
1046                             positions (int) for coming scanline */
1047                         /* note: it is faster to always update edges even
1048                            if it is removed from AEL for coming or last scanline */
1049 
1050                         // random access so use unsafe:
1051                         addr = addr0 + ecur; // ecur + OFF_F_CURX
1052 
1053                         // get current crossing:
1054                         curx = _unsafe.getInt(addr);
1055 
1056                         // update crossing with orientation at last bit:
1057                         cross = curx;
1058 
1059                         // Increment x using DDA (fixed point):
1060                         curx += _unsafe.getInt(addr + _OFF_BUMP_X);
1061 
1062                         // Increment error:
1063                         err  =  _unsafe.getInt(addr + _OFF_ERROR)
1064                               + _unsafe.getInt(addr + _OFF_BUMP_ERR);
1065 
1066                         // Manual carry handling:
1067                         // keep sign and carry bit only and ignore last bit (preserve orientation):
1068                         _unsafe.putInt(addr,               curx - ((err >> 30) & _ALL_BUT_LSB));
1069                         _unsafe.putInt(addr + _OFF_ERROR, (err & _ERR_STEP_MAX));
1070 
1071                         if (DO_STATS) {
1072                             rdrCtx.stats.stat_rdr_crossings_updates.add(numCrossings);
1073                         }
1074 
1075                         // insertion sort of crossings:
1076                         if (cross < lastCross) {
1077                             if (DO_STATS) {
1078                                 rdrCtx.stats.stat_rdr_crossings_sorts.add(i);
1079                             }
1080 
1081                             /* use binary search for newly added edges
1082                                in crossings if arrays are large enough */
1083                             if (useBinarySearch && (i >= prevNumCrossings)) {
1084                                 if (DO_STATS) {
1085                                     rdrCtx.stats.stat_rdr_crossings_bsearch.add(i);
1086                                 }
1087                                 low = 0;
1088                                 high = i - 1;
1089 
1090                                 do {
1091                                     // note: use signed shift (not >>>) for performance
1092                                     // as indices are small enough to exceed Integer.MAX_VALUE
1093                                     mid = (low + high) >> 1;
1094 
1095                                     if (_crossings[mid] < cross) {
1096                                         low = mid + 1;
1097                                     } else {
1098                                         high = mid - 1;
1099                                     }
1100                                 } while (low <= high);
1101 
1102                                 for (j = i - 1; j >= low; j--) {
1103                                     _crossings[j + 1] = _crossings[j];
1104                                     _edgePtrs [j + 1] = _edgePtrs[j];
1105                                 }
1106                                 _crossings[low] = cross;
1107                                 _edgePtrs [low] = ecur;
1108 
1109                             } else {
1110                                 j = i - 1;
1111                                 _crossings[i] = _crossings[j];
1112                                 _edgePtrs[i] = _edgePtrs[j];
1113 
1114                                 while ((--j >= 0) && (_crossings[j] > cross)) {
1115                                     _crossings[j + 1] = _crossings[j];
1116                                     _edgePtrs [j + 1] = _edgePtrs[j];
1117                                 }
1118                                 _crossings[j + 1] = cross;
1119                                 _edgePtrs [j + 1] = ecur;
1120                             }
1121 
1122                         } else {
1123                             _crossings[i] = lastCross = cross;
1124                         }
1125                     }
1126                 } else {
1127                     if (DO_STATS) {
1128                         rdrCtx.stats.stat_rdr_crossings_msorts.add(numCrossings);
1129                         rdrCtx.stats.hist_rdr_crossings_ratio
1130                             .add((1000 * ptrLen) / numCrossings);
1131                         rdrCtx.stats.hist_rdr_crossings_msorts.add(numCrossings);
1132                         rdrCtx.stats.hist_rdr_crossings_msorts_adds.add(ptrLen);
1133                     }
1134 
1135                     // Copy sorted data in auxiliary arrays
1136                     // and perform insertion sort on almost sorted data
1137                     // (ie i < prevNumCrossings):
1138 
1139                     lastCross = _MIN_VALUE;
1140 
1141                     for (i = 0; i < numCrossings; i++) {
1142                         // get the pointer to the edge
1143                         ecur = _edgePtrs[i];
1144 
1145                         /* convert subpixel coordinates  into pixel
1146                             positions (int) for coming scanline */
1147                         /* note: it is faster to always update edges even
1148                            if it is removed from AEL for coming or last scanline */
1149 
1150                         // random access so use unsafe:
1151                         addr = addr0 + ecur; // ecur + OFF_F_CURX
1152 
1153                         // get current crossing:
1154                         curx = _unsafe.getInt(addr);
1155 
1156                         // update crossing with orientation at last bit:
1157                         cross = curx;
1158 
1159                         // Increment x using DDA (fixed point):
1160                         curx += _unsafe.getInt(addr + _OFF_BUMP_X);
1161 
1162                         // Increment error:
1163                         err  =  _unsafe.getInt(addr + _OFF_ERROR)
1164                               + _unsafe.getInt(addr + _OFF_BUMP_ERR);
1165 
1166                         // Manual carry handling:
1167                         // keep sign and carry bit only and ignore last bit (preserve orientation):
1168                         _unsafe.putInt(addr,               curx - ((err >> 30) & _ALL_BUT_LSB));
1169                         _unsafe.putInt(addr + _OFF_ERROR, (err & _ERR_STEP_MAX));
1170 
1171                         if (DO_STATS) {
1172                             rdrCtx.stats.stat_rdr_crossings_updates.add(numCrossings);
1173                         }
1174 
1175                         if (i >= prevNumCrossings) {
1176                             // simply store crossing as edgePtrs is in-place:
1177                             // will be copied and sorted efficiently by mergesort later:
1178                             _crossings[i]     = cross;
1179 
1180                         } else if (cross < lastCross) {
1181                             if (DO_STATS) {
1182                                 rdrCtx.stats.stat_rdr_crossings_sorts.add(i);
1183                             }
1184 
1185                             // (straight) insertion sort of crossings:
1186                             j = i - 1;
1187                             _aux_crossings[i] = _aux_crossings[j];
1188                             _aux_edgePtrs[i] = _aux_edgePtrs[j];
1189 
1190                             while ((--j >= 0) && (_aux_crossings[j] > cross)) {
1191                                 _aux_crossings[j + 1] = _aux_crossings[j];
1192                                 _aux_edgePtrs [j + 1] = _aux_edgePtrs[j];
1193                             }
1194                             _aux_crossings[j + 1] = cross;
1195                             _aux_edgePtrs [j + 1] = ecur;
1196 
1197                         } else {
1198                             // auxiliary storage:
1199                             _aux_crossings[i] = lastCross = cross;
1200                             _aux_edgePtrs [i] = ecur;
1201                         }
1202                     }
1203 
1204                     // use Mergesort using auxiliary arrays (sort only right part)
1205                     MergeSort.mergeSortNoCopy(_crossings,     _edgePtrs,
1206                                               _aux_crossings, _aux_edgePtrs,
1207                                               numCrossings,   prevNumCrossings);
1208                 }
1209 
1210                 // reset ptrLen
1211                 ptrLen = 0;
1212                 // --- from former ScanLineIterator.next()
1213 
1214 
1215                 /* note: bboxx0 and bboxx1 must be pixel boundaries
1216                    to have correct coverage computation */
1217 
1218                 // right shift on crossings to get the x-coordinate:
1219                 curxo = _crossings[0];
1220                 x0    = curxo >> 1;
1221                 if (x0 < minX) {
1222                     minX = x0; // subpixel coordinate
1223                 }
1224 
1225                 x1 = _crossings[numCrossings - 1] >> 1;
1226                 if (x1 > maxX) {
1227                     maxX = x1; // subpixel coordinate
1228                 }
1229 
1230 
1231                 // compute pixel coverages
1232                 prev = curx = x0;
1233                 // to turn {0, 1} into {-1, 1}, multiply by 2 and subtract 1.
1234                 // last bit contains orientation (0 or 1)
1235                 crorientation = ((curxo & 0x1) << 1) - 1;
1236 
1237                 if (windingRuleEvenOdd) {
1238                     sum = crorientation;
1239 
1240                     // Even Odd winding rule: take care of mask ie sum(orientations)
1241                     for (i = 1; i < numCrossings; i++) {
1242                         curxo = _crossings[i];
1243                         curx  =  curxo >> 1;
1244                         // to turn {0, 1} into {-1, 1}, multiply by 2 and subtract 1.
1245                         // last bit contains orientation (0 or 1)
1246                         crorientation = ((curxo & 0x1) << 1) - 1;
1247 
1248                         if ((sum & 0x1) != 0) {
1249                             // TODO: perform line clipping on left-right sides
1250                             // to avoid such bound checks:
1251                             x0 = (prev > bboxx0) ? prev : bboxx0;
1252 
1253                             if (curx < bboxx1) {
1254                                 x1 = curx;
1255                             } else {
1256                                 x1 = bboxx1;
1257                                 // skip right side (fast exit loop):
1258                                 i = numCrossings;
1259                             }
1260 
1261                             if (x0 < x1) {
1262                                 x0 -= bboxx0; // turn x0, x1 from coords to indices
1263                                 x1 -= bboxx0; // in the alpha array.
1264 
1265                                 _alpha[x0] += 1;
1266                                 _alpha[x1] -= 1;
1267 
1268                                 if (useBlkFlags) {
1269                                     // flag used blocks:
1270                                     _blkFlags[x0 >> _BLK_SIZE_LG] = 1;
1271                                     _blkFlags[x1 >> _BLK_SIZE_LG] = 1;
1272                                 }
1273                             }
1274                         }
1275 
1276                         sum += crorientation;
1277                         prev = curx;
1278                     }
1279                 } else {
1280                     // Non-zero winding rule: optimize that case (default)
1281                     // and avoid processing intermediate crossings
1282                     for (i = 1, sum = 0;; i++) {
1283                         sum += crorientation;
1284 
1285                         if (sum != 0) {
1286                             // prev = min(curx)
1287                             if (prev > curx) {
1288                                 prev = curx;
1289                             }
1290                         } else {
1291                             // TODO: perform line clipping on left-right sides
1292                             // to avoid such bound checks:
1293                             x0 = (prev > bboxx0) ? prev : bboxx0;
1294 
1295                             if (curx < bboxx1) {
1296                                 x1 = curx;
1297                             } else {
1298                                 x1 = bboxx1;
1299                                 // skip right side (fast exit loop):
1300                                 i = numCrossings;
1301                             }
1302 
1303                             if (x0 < x1) {
1304                                 x0 -= bboxx0; // turn x0, x1 from coords to indices
1305                                 x1 -= bboxx0; // in the alpha array.
1306 
1307                                 _alpha[x0] += 1;
1308                                 _alpha[x1] -= 1;
1309 
1310                                 if (useBlkFlags) {
1311                                     // flag used blocks:
1312                                     _blkFlags[x0 >> _BLK_SIZE_LG] = 1;
1313                                     _blkFlags[x1 >> _BLK_SIZE_LG] = 1;
1314                                 }
1315                             }
1316                             prev = _MAX_VALUE;
1317                         }
1318 
1319                         if (i == numCrossings) {
1320                             break;
1321                         }
1322 
1323                         curxo = _crossings[i];
1324                         curx  =  curxo >> 1;
1325                         // to turn {0, 1} into {-1, 1}, multiply by 2 and subtract 1.
1326                         // last bit contains orientation (0 or 1)
1327                         crorientation = ((curxo & 0x1) << 1) - 1;
1328                     }
1329                 }
1330             } // numCrossings > 0
1331 
1332             // even if this last row had no crossings, alpha will be zeroed
1333             // from the last emitRow call. But this doesn't matter because
1334             // maxX < minX, so no row will be emitted to the AlphaConsumer.
1335             if (true) {
1336                 lastY = y;
1337 
1338                 // convert subpixel to pixel coordinate within boundaries:
1339                 minX = FloatMath.max(minX, bboxx0);
1340                 maxX = FloatMath.min(maxX, bboxx1);
1341 
1342                 if (maxX >= minX) {
1343                     // note: alpha array will be zeroed by copyAARow()
1344                     // +1 because alpha [pix_minX; pix_maxX[
1345                     // fix range [x0; x1[
1346                     // note: if x1=bboxx1, then alpha is written up to bboxx1+1
1347                     // inclusive: alpha[bboxx1] ignored, alpha[bboxx1+1] == 0
1348                     // (normally so never cleared below)
1349                     copyAARow(_alpha, lastY, minX, maxX + 1, useBlkFlags, ac);
1350 
1351                     // speculative for next pixel row (scanline coherence):
1352                     if (_enableBlkFlagsHeuristics) {
1353                         // Use block flags if large pixel span and few crossings:
1354                         // ie mean(distance between crossings) is larger than
1355                         // 1 block size;
1356 
1357                         // fast check width:
1358                         maxX -= minX;
1359 
1360                         // if stroking: numCrossings /= 2
1361                         // => shift numCrossings by 1
1362                         // condition = (width / (numCrossings - 1)) > blockSize
1363                         useBlkFlags = (maxX > _BLK_SIZE) && (maxX >
1364                             (((numCrossings >> stroking) - 1) << _BLK_SIZE_LG));
1365 
1366                         if (DO_STATS) {
1367                             tmp = FloatMath.max(1,
1368                                     ((numCrossings >> stroking) - 1));
1369                             rdrCtx.stats.hist_tile_generator_encoding_dist
1370                                 .add(maxX / tmp);
1371                         }
1372                     }
1373                 } else {
1374                     ac.clearAlphas(lastY);
1375                 }
1376                 minX = _MAX_VALUE;
1377                 maxX = _MIN_VALUE;
1378             }
1379         } // scan line iterator
1380 
1381         // Emit final row
1382         y--;
1383 
1384         // convert subpixel to pixel coordinate within boundaries:
1385         minX = FloatMath.max(minX, bboxx0);
1386         maxX = FloatMath.min(maxX, bboxx1);
1387 
1388         if (maxX >= minX) {
1389             // note: alpha array will be zeroed by copyAARow()
1390             // +1 because alpha [pix_minX; pix_maxX[
1391             // fix range [x0; x1[
1392             // note: if x1=bboxx1, then alpha is written up to bboxx1+1
1393             // inclusive: alpha[bboxx1] ignored then cleared and
1394             // alpha[bboxx1+1] == 0 (normally so never cleared after)
1395             copyAARow(_alpha, y, minX, maxX + 1, useBlkFlags, ac);
1396         } else if (y != lastY) {
1397             ac.clearAlphas(y);
1398         }
1399 
1400         // update member:
1401         edgeCount = numCrossings;
1402         prevUseBlkFlags = useBlkFlags;
1403 
1404         if (DO_STATS) {
1405             // update max used mark
1406             activeEdgeMaxUsed = _arrayMaxUsed;
1407         }
1408     }
1409 
1410     void endRendering() {
1411         if (DO_MONITORS) {
1412             rdrCtx.stats.mon_rdr_endRendering.start();
1413         }
1414         if (edgeMinY == Integer.MAX_VALUE) {
1415             return; // undefined edges bounds
1416         }
1417 
1418         final int _boundsMinY = boundsMinY;
1419         final int _boundsMaxY = boundsMaxY;
1420 
1421         // bounds as inclusive intervals
1422         final int spminX = FloatMath.max(FloatMath.ceil_int(edgeMinX - 0.5D), boundsMinX);
1423         final int spmaxX = FloatMath.min(FloatMath.ceil_int(edgeMaxX - 0.5D), boundsMaxX - 1);
1424 
1425         // edge Min/Max Y are already rounded to subpixels within bounds:
1426         final int spminY = edgeMinY;
1427         final int spmaxY;
1428         int maxY = edgeMaxY;
1429 
1430         if (maxY <= _boundsMaxY - 1) {
1431             spmaxY = maxY;
1432         } else {
1433             spmaxY = _boundsMaxY - 1;
1434             maxY   = _boundsMaxY;
1435         }
1436         buckets_minY = spminY - _boundsMinY;
1437         buckets_maxY = maxY   - _boundsMinY;
1438 
1439         if (DO_LOG_BOUNDS) {
1440             MarlinUtils.logInfo("edgesXY = [" + edgeMinX + " ... " + edgeMaxX
1441                                 + "][" + edgeMinY + " ... " + edgeMaxY + "]");
1442             MarlinUtils.logInfo("spXY    = [" + spminX + " ... " + spmaxX
1443                                 + "][" + spminY + " ... " + spmaxY + "]");
1444         }
1445 
1446         // test clipping for shapes out of bounds
1447         if ((spminX > spmaxX) || (spminY > spmaxY)) {
1448             return;
1449         }
1450 
1451         // half open intervals
1452         // inclusive:
1453         final int pminX = spminX;
1454         // exclusive:
1455         final int pmaxX = spmaxX + 1; // +1 to ensure proper upper bound
1456         // inclusive:
1457         final int pminY = spminY;
1458         // exclusive:
1459         final int pmaxY = spmaxY + 1; // +1 to ensure proper upper bound
1460 
1461         // store BBox to answer ptg.getBBox():
1462         initConsumer(pminX, pminY, pmaxX, pmaxY);
1463 
1464         // Heuristics for using block flags:
1465         if (ENABLE_BLOCK_FLAGS) {
1466             enableBlkFlags = this.useRLE;
1467             prevUseBlkFlags = enableBlkFlags && !ENABLE_BLOCK_FLAGS_HEURISTICS;
1468 
1469             if (enableBlkFlags) {
1470                 // ensure blockFlags array is large enough:
1471                 // note: +2 to ensure enough space left at end
1472                 final int blkLen = ((pmaxX - pminX) >> BLOCK_SIZE_LG) + 2;
1473                 if (blkLen > INITIAL_ARRAY) {
1474                     blkFlags = blkFlags_ref.getArray(blkLen);
1475                 }
1476             }
1477         }
1478 
1479         // memorize the rendering bounding box:
1480         /* note: bbox_spminX and bbox_spmaxX must be pixel boundaries
1481            to have correct coverage computation */
1482         // inclusive:
1483         bbox_spminX = pminX;
1484         // exclusive:
1485         bbox_spmaxX = pmaxX;
1486         // inclusive:
1487         bbox_spminY = pminY;
1488         // exclusive:
1489         bbox_spmaxY = pmaxY;
1490 
1491         if (DO_LOG_BOUNDS) {
1492             MarlinUtils.logInfo("pXY       = [" + pminX + " ... " + pmaxX
1493                                 + "[ [" + pminY + " ... " + pmaxY + "[");
1494             MarlinUtils.logInfo("bbox_spXY = [" + bbox_spminX + " ... "
1495                                 + bbox_spmaxX + "[ [" + bbox_spminY + " ... "
1496                                 + bbox_spmaxY + "[");
1497         }
1498 
1499         // Prepare alpha line:
1500         // add 2 to better deal with the last pixel in a pixel row.
1501         final int width = (pmaxX - pminX) + 2;
1502 
1503         // Useful when processing tile line by tile line
1504         if (width > INITIAL_AA_ARRAY) {
1505             if (DO_STATS) {
1506                 rdrCtx.stats.stat_array_renderer_alphaline.add(width);
1507             }
1508             alphaLine = alphaLine_ref.getArray(width);
1509         }
1510     }
1511 
1512     void initConsumer(int minx, int miny, int maxx, int maxy)
1513     {
1514         // assert maxy >= miny && maxx >= minx;
1515         bboxX0 = minx;
1516         bboxX1 = maxx;
1517         bboxY0 = miny;
1518         bboxY1 = maxy;
1519 
1520         final int width = (maxx - minx);
1521 
1522         if (FORCE_NO_RLE) {
1523             useRLE = false;
1524         } else if (FORCE_RLE) {
1525             useRLE = true;
1526         } else {
1527             // heuristics: use both bbox area and complexity
1528             // ie number of primitives:
1529 
1530             // fast check min width:
1531             if (width <= RLE_MIN_WIDTH) {
1532                 useRLE = false;
1533             } else {
1534                 useRLE = true;
1535             }
1536         }
1537     }
1538 
1539     private int bbox_spminX, bbox_spmaxX, bbox_spminY, bbox_spmaxY;
1540 
1541     public void produceAlphas(final MarlinAlphaConsumer ac) {
1542         ac.setMaxAlpha(1);
1543 
1544         if (enableBlkFlags && !ac.supportBlockFlags()) {
1545             // consumer does not support block flag optimization:
1546             enableBlkFlags = false;
1547             prevUseBlkFlags = false;
1548         }
1549 
1550         if (DO_MONITORS) {
1551             rdrCtx.stats.mon_rdr_endRendering_Y.start();
1552         }
1553 
1554         // Process all scan lines:
1555         _endRendering(bbox_spminY, bbox_spmaxY, ac);
1556 
1557         if (DO_MONITORS) {
1558             rdrCtx.stats.mon_rdr_endRendering_Y.stop();
1559         }
1560     }
1561 
1562     void copyAARow(final int[] alphaRow,
1563                    final int pix_y, final int pix_from, final int pix_to,
1564                    final boolean useBlockFlags,
1565                    final MarlinAlphaConsumer ac)
1566     {
1567         if (DO_MONITORS) {
1568             rdrCtx.stats.mon_rdr_copyAARow.start();
1569         }
1570         if (DO_STATS) {
1571             rdrCtx.stats.stat_cache_rowAA.add(pix_to - pix_from);
1572         }
1573 
1574         if (useBlockFlags) {
1575             if (DO_STATS) {
1576                 rdrCtx.stats.hist_tile_generator_encoding.add(1);
1577             }
1578             ac.setAndClearRelativeAlphas(blkFlags, alphaRow, pix_y, pix_from, pix_to);
1579         } else {
1580             if (DO_STATS) {
1581                 rdrCtx.stats.hist_tile_generator_encoding.add(0);
1582             }
1583             ac.setAndClearRelativeAlphas(alphaRow, pix_y, pix_from, pix_to);
1584         }
1585         if (DO_MONITORS) {
1586             rdrCtx.stats.mon_rdr_copyAARow.stop();
1587         }
1588     }
1589 
1590     // output pixel bounding box:
1591     int bboxX0, bboxX1, bboxY0, bboxY1;
1592 
1593     @Override
1594     public int getOutpixMinX() {
1595         return bboxX0;
1596     }
1597 
1598     @Override
1599     public int getOutpixMaxX() {
1600         return bboxX1;
1601     }
1602 
1603     @Override
1604     public int getOutpixMinY() {
1605         return bboxY0;
1606     }
1607 
1608     @Override
1609     public int getOutpixMaxY() {
1610         return bboxY1;
1611     }
1612 }