1 /*

     2  * Copyright (c) 2007, 2015, 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 sun.java2d.marlin;

    27 

    28 import java.util.Arrays;

    29 import sun.awt.geom.PathConsumer2D;

    30 import static sun.java2d.marlin.OffHeapArray.SIZE_INT;

    31 import jdk.internal.misc.Unsafe;

    32 

    33 final class Renderer implements PathConsumer2D, MarlinConst {

    34 

    35     static final boolean DISABLE_RENDER = false;

    36 

    37     static final boolean ENABLE_BLOCK_FLAGS = MarlinProperties.isUseTileFlags();

    38     static final boolean ENABLE_BLOCK_FLAGS_HEURISTICS = MarlinProperties.isUseTileFlagsWithHeuristics();

    39 

    40     private static final int ALL_BUT_LSB = 0xfffffffe;

    41     private static final int ERR_STEP_MAX = 0x7fffffff; // = 2^31 - 1

    42 

    43     private static final double POWER_2_TO_32 = FloatMath.powerOfTwoD(32);

    44 

    45     // use float to make tosubpix methods faster (no int to float conversion)

    46     public static final float f_SUBPIXEL_POSITIONS_X

    47         = (float) SUBPIXEL_POSITIONS_X;

    48     public static final float f_SUBPIXEL_POSITIONS_Y

    49         = (float) SUBPIXEL_POSITIONS_Y;

    50     public static final int SUBPIXEL_MASK_X = SUBPIXEL_POSITIONS_X - 1;

    51     public static final int SUBPIXEL_MASK_Y = SUBPIXEL_POSITIONS_Y - 1;

    52 

    53     // number of subpixels corresponding to a tile line

    54     private static final int SUBPIXEL_TILE

    55         = TILE_SIZE << SUBPIXEL_LG_POSITIONS_Y;

    56 

    57     // 2048 (pixelSize) pixels (height) x 8 subpixels = 64K

    58     static final int INITIAL_BUCKET_ARRAY

    59         = INITIAL_PIXEL_DIM * SUBPIXEL_POSITIONS_Y;

    60 

    61     public static final int WIND_EVEN_ODD = 0;

    62     public static final int WIND_NON_ZERO = 1;

    63 

    64     // common to all types of input path segments.

    65     // OFFSET as bytes

    66     // only integer values:

    67     public static final long OFF_CURX_OR  = 0;

    68     public static final long OFF_ERROR    = OFF_CURX_OR  + SIZE_INT;

    69     public static final long OFF_BUMP_X   = OFF_ERROR    + SIZE_INT;

    70     public static final long OFF_BUMP_ERR = OFF_BUMP_X   + SIZE_INT;

    71     public static final long OFF_NEXT     = OFF_BUMP_ERR + SIZE_INT;

    72     public static final long OFF_YMAX     = OFF_NEXT     + SIZE_INT;

    73 

    74     // size of one edge in bytes

    75     public static final int SIZEOF_EDGE_BYTES = (int)(OFF_YMAX + SIZE_INT);

    76 

    77     // curve break into lines

    78     // cubic error in subpixels to decrement step

    79     private static final float CUB_DEC_ERR_SUBPIX

    80         = 2.5f * (NORM_SUBPIXELS / 8f); // 2.5 subpixel for typical 8x8 subpixels

    81     // cubic error in subpixels to increment step

    82     private static final float CUB_INC_ERR_SUBPIX

    83         = 1f * (NORM_SUBPIXELS / 8f); // 1 subpixel for typical 8x8 subpixels

    84 

    85     // cubic bind length to decrement step = 8 * error in subpixels

    86     // pisces: 20 / 8

    87     // openjfx pisces: 8 / 3.2

    88     // multiply by 8 = error scale factor:

    89     public static final float CUB_DEC_BND

    90         = 8f * CUB_DEC_ERR_SUBPIX; // 20f means 2.5 subpixel error

    91     // cubic bind length to increment step = 8 * error in subpixels

    92     public static final float CUB_INC_BND

    93         = 8f * CUB_INC_ERR_SUBPIX; // 8f means 1 subpixel error

    94 

    95     // cubic countlg

    96     public static final int CUB_COUNT_LG = 2;

    97     // cubic count = 2^countlg

    98     private static final int CUB_COUNT = 1 << CUB_COUNT_LG;

    99     // cubic count^2 = 4^countlg

   100     private static final int CUB_COUNT_2 = 1 << (2 * CUB_COUNT_LG);

   101     // cubic count^3 = 8^countlg

   102     private static final int CUB_COUNT_3 = 1 << (3 * CUB_COUNT_LG);

   103     // cubic dt = 1 / count

   104     private static final float CUB_INV_COUNT = 1f / CUB_COUNT;

   105     // cubic dt^2 = 1 / count^2 = 1 / 4^countlg

   106     private static final float CUB_INV_COUNT_2 = 1f / CUB_COUNT_2;

   107     // cubic dt^3 = 1 / count^3 = 1 / 8^countlg

   108     private static final float CUB_INV_COUNT_3 = 1f / CUB_COUNT_3;

   109 

   110     // quad break into lines

   111     // quadratic error in subpixels

   112     private static final float QUAD_DEC_ERR_SUBPIX

   113         = 1f * (NORM_SUBPIXELS / 8f); // 1 subpixel for typical 8x8 subpixels

   114 

   115     // quadratic bind length to decrement step = 8 * error in subpixels

   116     // pisces and openjfx pisces: 32

   117     public static final float QUAD_DEC_BND

   118         = 8f * QUAD_DEC_ERR_SUBPIX; // 8f means 1 subpixel error

   119 

   120 //////////////////////////////////////////////////////////////////////////////

   121 //  SCAN LINE

   122 //////////////////////////////////////////////////////////////////////////////

   123     // crossings ie subpixel edge x coordinates

   124     private int[] crossings;

   125     // auxiliary storage for crossings (merge sort)

   126     private int[] aux_crossings;

   127 

   128     // indices into the segment pointer lists. They indicate the "active"

   129     // sublist in the segment lists (the portion of the list that contains

   130     // all the segments that cross the next scan line).

   131     private int edgeCount;

   132     private int[] edgePtrs;

   133     // auxiliary storage for edge pointers (merge sort)

   134     private int[] aux_edgePtrs;

   135 

   136     // max used for both edgePtrs and crossings (stats only)

   137     private int activeEdgeMaxUsed;

   138 

   139     // per-thread initial arrays (large enough to satisfy most usages) (1024)

   140     private final int[] crossings_initial = new int[INITIAL_SMALL_ARRAY]; // 4K

   141     // +1 to avoid recycling in Helpers.widenArray()

   142     private final int[] edgePtrs_initial  = new int[INITIAL_SMALL_ARRAY + 1]; // 4K

   143     // merge sort initial arrays (large enough to satisfy most usages) (1024)

   144     private final int[] aux_crossings_initial = new int[INITIAL_SMALL_ARRAY]; // 4K

   145     // +1 to avoid recycling in Helpers.widenArray()

   146     private final int[] aux_edgePtrs_initial  = new int[INITIAL_SMALL_ARRAY + 1]; // 4K

   147 

   148 //////////////////////////////////////////////////////////////////////////////

   149 //  EDGE LIST

   150 //////////////////////////////////////////////////////////////////////////////

   151     private float edgeMinY = Float.POSITIVE_INFINITY;

   152     private float edgeMaxY = Float.NEGATIVE_INFINITY;

   153     private float edgeMinX = Float.POSITIVE_INFINITY;

   154     private float edgeMaxX = Float.NEGATIVE_INFINITY;

   155 

   156     // edges [floats|ints] stored in off-heap memory

   157     private final OffHeapArray edges;

   158 

   159     private int[] edgeBuckets;

   160     private int[] edgeBucketCounts; // 2*newedges + (1 if pruning needed)

   161     // used range for edgeBuckets / edgeBucketCounts

   162     private int buckets_minY;

   163     private int buckets_maxY;

   164     // sum of each edge delta Y (subpixels)

   165     private int edgeSumDeltaY;

   166 

   167     // +1 to avoid recycling in Helpers.widenArray()

   168     private final int[] edgeBuckets_initial

   169         = new int[INITIAL_BUCKET_ARRAY + 1]; // 64K

   170     private final int[] edgeBucketCounts_initial

   171         = new int[INITIAL_BUCKET_ARRAY + 1]; // 64K

   172 

   173     // Flattens using adaptive forward differencing. This only carries out

   174     // one iteration of the AFD loop. All it does is update AFD variables (i.e.

   175     // X0, Y0, D*[X|Y], COUNT; not variables used for computing scanline crossings).

   176     private void quadBreakIntoLinesAndAdd(float x0, float y0,

   177                                           final Curve c,

   178                                           final float x2, final float y2)

   179     {

   180         int count = 1; // dt = 1 / count

   181 

   182         // maximum(ddX|Y) = norm(dbx, dby) * dt^2 (= 1)

   183         float maxDD = FloatMath.max(Math.abs(c.dbx), Math.abs(c.dby));

   184 

   185         final float _DEC_BND = QUAD_DEC_BND;

   186 

   187         while (maxDD >= _DEC_BND) {

   188             // divide step by half:

   189             maxDD /= 4f; // error divided by 2^2 = 4

   190 

   191             count <<= 1;

   192             if (doStats) {

   193                 RendererContext.stats.stat_rdr_quadBreak_dec.add(count);

   194             }

   195         }

   196 

   197         int nL = 0; // line count

   198         if (count > 1) {

   199             final float icount = 1f / count; // dt

   200             final float icount2 = icount * icount; // dt^2

   201 

   202             final float ddx = c.dbx * icount2;

   203             final float ddy = c.dby * icount2;

   204             float dx = c.bx * icount2 + c.cx * icount;

   205             float dy = c.by * icount2 + c.cy * icount;

   206 

   207             float x1, y1;

   208 

   209             while (--count > 0) {

   210                 x1 = x0 + dx;

   211                 dx += ddx;

   212                 y1 = y0 + dy;

   213                 dy += ddy;

   214 

   215                 addLine(x0, y0, x1, y1);

   216 

   217                 if (doStats) { nL++; }

   218                 x0 = x1;

   219                 y0 = y1;

   220             }

   221         }

   222         addLine(x0, y0, x2, y2);

   223 

   224         if (doStats) {

   225             RendererContext.stats.stat_rdr_quadBreak.add(nL + 1);

   226         }

   227     }

   228 

   229     // x0, y0 and x3,y3 are the endpoints of the curve. We could compute these

   230     // using c.xat(0),c.yat(0) and c.xat(1),c.yat(1), but this might introduce

   231     // numerical errors, and our callers already have the exact values.

   232     // Another alternative would be to pass all the control points, and call

   233     // c.set here, but then too many numbers are passed around.

   234     private void curveBreakIntoLinesAndAdd(float x0, float y0,

   235                                            final Curve c,

   236                                            final float x3, final float y3)

   237     {

   238         int count           = CUB_COUNT;

   239         final float icount  = CUB_INV_COUNT;   // dt

   240         final float icount2 = CUB_INV_COUNT_2; // dt^2

   241         final float icount3 = CUB_INV_COUNT_3; // dt^3

   242 

   243         // the dx and dy refer to forward differencing variables, not the last

   244         // coefficients of the "points" polynomial

   245         float dddx, dddy, ddx, ddy, dx, dy;

   246         dddx = 2f * c.dax * icount3;

   247         dddy = 2f * c.day * icount3;

   248         ddx = dddx + c.dbx * icount2;

   249         ddy = dddy + c.dby * icount2;

   250         dx = c.ax * icount3 + c.bx * icount2 + c.cx * icount;

   251         dy = c.ay * icount3 + c.by * icount2 + c.cy * icount;

   252 

   253         // we use x0, y0 to walk the line

   254         float x1 = x0, y1 = y0;

   255         int nL = 0; // line count

   256 

   257         final float _DEC_BND = CUB_DEC_BND;

   258         final float _INC_BND = CUB_INC_BND;

   259 

   260         while (count > 0) {

   261             // divide step by half:

   262             while (Math.abs(ddx) >= _DEC_BND || Math.abs(ddy) >= _DEC_BND) {

   263                 dddx /= 8f;

   264                 dddy /= 8f;

   265                 ddx = ddx/4f - dddx;

   266                 ddy = ddy/4f - dddy;

   267                 dx = (dx - ddx) / 2f;

   268                 dy = (dy - ddy) / 2f;

   269 

   270                 count <<= 1;

   271                 if (doStats) {

   272                     RendererContext.stats.stat_rdr_curveBreak_dec.add(count);

   273                 }

   274             }

   275 

   276             // double step:

   277             // TODO: why use first derivative dX|Y instead of second ddX|Y ?

   278             // both scale changes should use speed or acceleration to have the same metric.

   279 

   280             // can only do this on even "count" values, because we must divide count by 2

   281             while (count % 2 == 0

   282                    && Math.abs(dx) <= _INC_BND && Math.abs(dy) <= _INC_BND)

   283             {

   284                 dx = 2f * dx + ddx;

   285                 dy = 2f * dy + ddy;

   286                 ddx = 4f * (ddx + dddx);

   287                 ddy = 4f * (ddy + dddy);

   288                 dddx *= 8f;

   289                 dddy *= 8f;

   290 

   291                 count >>= 1;

   292                 if (doStats) {

   293                     RendererContext.stats.stat_rdr_curveBreak_inc.add(count);

   294                 }

   295             }

   296             if (--count > 0) {

   297                 x1 += dx;

   298                 dx += ddx;

   299                 ddx += dddx;

   300                 y1 += dy;

   301                 dy += ddy;

   302                 ddy += dddy;

   303             } else {

   304                 x1 = x3;

   305                 y1 = y3;

   306             }

   307 

   308             addLine(x0, y0, x1, y1);

   309 

   310             if (doStats) { nL++; }

   311             x0 = x1;

   312             y0 = y1;

   313         }

   314         if (doStats) {

   315             RendererContext.stats.stat_rdr_curveBreak.add(nL);

   316         }

   317     }

   318 

   319     private void addLine(float x1, float y1, float x2, float y2) {

   320         if (doMonitors) {

   321             RendererContext.stats.mon_rdr_addLine.start();

   322         }

   323         if (doStats) {

   324             RendererContext.stats.stat_rdr_addLine.add(1);

   325         }

   326         int or = 1; // orientation of the line. 1 if y increases, 0 otherwise.

   327         if (y2 < y1) {

   328             or = 0;

   329             float tmp = y2;

   330             y2 = y1;

   331             y1 = tmp;

   332             tmp = x2;

   333             x2 = x1;

   334             x1 = tmp;

   335         }

   336 

   337         // convert subpixel coordinates (float) into pixel positions (int)

   338 

   339         // The index of the pixel that holds the next HPC is at ceil(trueY - 0.5)

   340         // Since y1 and y2 are biased by -0.5 in tosubpixy(), this is simply

   341         // ceil(y1) or ceil(y2)

   342         // upper integer (inclusive)

   343         final int firstCrossing = FloatMath.max(FloatMath.ceil_int(y1), boundsMinY);

   344 

   345         // note: use boundsMaxY (last Y exclusive) to compute correct coverage

   346         // upper integer (exclusive)

   347         final int lastCrossing  = FloatMath.min(FloatMath.ceil_int(y2), boundsMaxY);

   348 

   349         /* skip horizontal lines in pixel space and clip edges

   350            out of y range [boundsMinY; boundsMaxY] */

   351         if (firstCrossing >= lastCrossing) {

   352             if (doMonitors) {

   353                 RendererContext.stats.mon_rdr_addLine.stop();

   354             }

   355             if (doStats) {

   356                 RendererContext.stats.stat_rdr_addLine_skip.add(1);

   357             }

   358             return;

   359         }

   360         // edge min/max X/Y are in subpixel space (inclusive)

   361         if (y1 < edgeMinY) {

   362             edgeMinY = y1;

   363         }

   364         if (y2 > edgeMaxY) {

   365             edgeMaxY = y2;

   366         }

   367 

   368         // Use double-precision for improved accuracy:

   369         final double x1d   = x1;

   370         final double y1d   = y1;

   371         final double slope = (x2 - x1d) / (y2 - y1d);

   372 

   373         if (slope >= 0.0) { // <==> x1 < x2

   374             if (x1 < edgeMinX) {

   375                 edgeMinX = x1;

   376             }

   377             if (x2 > edgeMaxX) {

   378                 edgeMaxX = x2;

   379             }

   380         } else {

   381             if (x2 < edgeMinX) {

   382                 edgeMinX = x2;

   383             }

   384             if (x1 > edgeMaxX) {

   385                 edgeMaxX = x1;

   386             }

   387         }

   388 

   389         // local variables for performance:

   390         final int _SIZEOF_EDGE_BYTES = SIZEOF_EDGE_BYTES;

   391 

   392         final OffHeapArray _edges = edges;

   393 

   394         // get free pointer (ie length in bytes)

   395         final int edgePtr = _edges.used;

   396 

   397         // use substraction to avoid integer overflow:

   398         if (_edges.length - edgePtr < _SIZEOF_EDGE_BYTES) {

   399             // suppose _edges.length > _SIZEOF_EDGE_BYTES

   400             // so doubling size is enough to add needed bytes

   401             // note: throw IOOB if neededSize > 2Gb:

   402             final long edgeNewSize = ArrayCache.getNewLargeSize(_edges.length,

   403                                         edgePtr + _SIZEOF_EDGE_BYTES);

   404 

   405             if (doStats) {

   406                 RendererContext.stats.stat_rdr_edges_resizes.add(edgeNewSize);

   407             }

   408             _edges.resize(edgeNewSize);

   409         }

   410 

   411 

   412         final Unsafe _unsafe = OffHeapArray.unsafe;

   413         final long SIZE_INT = 4L;

   414         long addr   = _edges.address + edgePtr;

   415 

   416         // The x value must be bumped up to its position at the next HPC we will evaluate.

   417         // "firstcrossing" is the (sub)pixel number where the next crossing occurs

   418         // thus, the actual coordinate of the next HPC is "firstcrossing + 0.5"

   419         // so the Y distance we cover is "firstcrossing + 0.5 - trueY".

   420         // Note that since y1 (and y2) are already biased by -0.5 in tosubpixy(), we have

   421         // y1 = trueY - 0.5

   422         // trueY = y1 + 0.5

   423         // firstcrossing + 0.5 - trueY = firstcrossing + 0.5 - (y1 + 0.5)

   424         //                             = firstcrossing - y1

   425         // The x coordinate at that HPC is then:

   426         // x1_intercept = x1 + (firstcrossing - y1) * slope

   427         // The next VPC is then given by:

   428         // VPC index = ceil(x1_intercept - 0.5), or alternately

   429         // VPC index = floor(x1_intercept - 0.5 + 1 - epsilon)

   430         // epsilon is hard to pin down in floating point, but easy in fixed point, so if

   431         // we convert to fixed point then these operations get easier:

   432         // long x1_fixed = x1_intercept * 2^32;  (fixed point 32.32 format)

   433         // curx = next VPC = fixed_floor(x1_fixed - 2^31 + 2^32 - 1)

   434         //                 = fixed_floor(x1_fixed + 2^31 - 1)

   435         //                 = fixed_floor(x1_fixed + 0x7fffffff)

   436         // and error       = fixed_fract(x1_fixed + 0x7fffffff)

   437         final double x1_intercept = x1d + (firstCrossing - y1d) * slope;

   438 

   439         // inlined scalb(x1_intercept, 32):

   440         final long x1_fixed_biased = ((long) (POWER_2_TO_32 * x1_intercept))

   441                                      + 0x7fffffffL;

   442         // curx:

   443         // last bit corresponds to the orientation

   444         _unsafe.putInt(addr, (((int) (x1_fixed_biased >> 31L)) & ALL_BUT_LSB) | or);

   445         addr += SIZE_INT;

   446         _unsafe.putInt(addr,  ((int)  x1_fixed_biased) >>> 1);

   447         addr += SIZE_INT;

   448 

   449         // inlined scalb(slope, 32):

   450         final long slope_fixed = (long) (POWER_2_TO_32 * slope);

   451 

   452         // last bit set to 0 to keep orientation:

   453         _unsafe.putInt(addr, (((int) (slope_fixed >> 31L)) & ALL_BUT_LSB));

   454         addr += SIZE_INT;

   455         _unsafe.putInt(addr,  ((int)  slope_fixed) >>> 1);

   456         addr += SIZE_INT;

   457 

   458         final int[] _edgeBuckets      = edgeBuckets;

   459         final int[] _edgeBucketCounts = edgeBucketCounts;

   460 

   461         final int _boundsMinY = boundsMinY;

   462 

   463         // each bucket is a linked list. this method adds ptr to the

   464         // start of the "bucket"th linked list.

   465         final int bucketIdx = firstCrossing - _boundsMinY;

   466 

   467         // pointer from bucket

   468         _unsafe.putInt(addr, _edgeBuckets[bucketIdx]);

   469         addr += SIZE_INT;

   470         // y max (inclusive)

   471         _unsafe.putInt(addr,  lastCrossing);

   472 

   473         // Update buckets:

   474         // directly the edge struct "pointer"

   475         _edgeBuckets[bucketIdx]       = edgePtr;

   476         _edgeBucketCounts[bucketIdx] += 2; // 1 << 1

   477         // last bit means edge end

   478         _edgeBucketCounts[lastCrossing - _boundsMinY] |= 0x1;

   479 

   480         // update sum of delta Y (subpixels):

   481         edgeSumDeltaY += (lastCrossing - firstCrossing);

   482 

   483         // update free pointer (ie length in bytes)

   484         _edges.used += _SIZEOF_EDGE_BYTES;

   485 

   486         if (doMonitors) {

   487             RendererContext.stats.mon_rdr_addLine.stop();

   488         }

   489     }

   490 

   491 // END EDGE LIST

   492 //////////////////////////////////////////////////////////////////////////////

   493 

   494     // Cache to store RLE-encoded coverage mask of the current primitive

   495     final MarlinCache cache;

   496 

   497     // Bounds of the drawing region, at subpixel precision.

   498     private int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY;

   499 

   500     // Current winding rule

   501     private int windingRule;

   502 

   503     // Current drawing position, i.e., final point of last segment

   504     private float x0, y0;

   505 

   506     // Position of most recent 'moveTo' command

   507     private float pix_sx0, pix_sy0;

   508 

   509     // per-thread renderer context

   510     final RendererContext rdrCtx;

   511     // dirty curve

   512     private final Curve curve;

   513 

   514     Renderer(final RendererContext rdrCtx) {

   515         this.rdrCtx = rdrCtx;

   516 

   517         this.edges = new OffHeapArray(rdrCtx, INITIAL_EDGES_CAPACITY); // 96K

   518 

   519         this.curve = rdrCtx.curve;

   520 

   521         edgeBuckets = edgeBuckets_initial;

   522         edgeBucketCounts = edgeBucketCounts_initial;

   523 

   524         alphaLine  = alphaLine_initial;

   525 

   526         this.cache = rdrCtx.cache;

   527 

   528         // ScanLine:

   529         crossings     = crossings_initial;

   530         aux_crossings = aux_crossings_initial;

   531         edgePtrs      = edgePtrs_initial;

   532         aux_edgePtrs  = aux_edgePtrs_initial;

   533 

   534         edgeCount = 0;

   535         activeEdgeMaxUsed = 0;

   536     }

   537 

   538     Renderer init(final int pix_boundsX, final int pix_boundsY,

   539                   final int pix_boundsWidth, final int pix_boundsHeight,

   540                   final int windingRule) {

   541 

   542         this.windingRule = windingRule;

   543 

   544         // bounds as half-open intervals: minX <= x < maxX and minY <= y < maxY

   545         this.boundsMinX =  pix_boundsX << SUBPIXEL_LG_POSITIONS_X;

   546         this.boundsMaxX =

   547             (pix_boundsX + pix_boundsWidth) << SUBPIXEL_LG_POSITIONS_X;

   548         this.boundsMinY =  pix_boundsY << SUBPIXEL_LG_POSITIONS_Y;

   549         this.boundsMaxY =

   550             (pix_boundsY + pix_boundsHeight) << SUBPIXEL_LG_POSITIONS_Y;

   551 

   552         if (doLogBounds) {

   553             MarlinUtils.logInfo("boundsXY = [" + boundsMinX + " ... "

   554                                 + boundsMaxX + "[ [" + boundsMinY + " ... "

   555                                 + boundsMaxY + "[");

   556         }

   557 

   558         // see addLine: ceil(boundsMaxY) => boundsMaxY + 1

   559         // +1 for edgeBucketCounts

   560         final int edgeBucketsLength = (boundsMaxY - boundsMinY) + 1;

   561 

   562         if (edgeBucketsLength > INITIAL_BUCKET_ARRAY) {

   563             if (doStats) {

   564                 RendererContext.stats.stat_array_renderer_edgeBuckets

   565                     .add(edgeBucketsLength);

   566                 RendererContext.stats.stat_array_renderer_edgeBucketCounts

   567                     .add(edgeBucketsLength);

   568             }

   569             edgeBuckets = rdrCtx.getIntArray(edgeBucketsLength);

   570             edgeBucketCounts = rdrCtx.getIntArray(edgeBucketsLength);

   571         }

   572 

   573         edgeMinY = Float.POSITIVE_INFINITY;

   574         edgeMaxY = Float.NEGATIVE_INFINITY;

   575         edgeMinX = Float.POSITIVE_INFINITY;

   576         edgeMaxX = Float.NEGATIVE_INFINITY;

   577 

   578         // reset used mark:

   579         edgeCount = 0;

   580         activeEdgeMaxUsed = 0;

   581         edges.used = 0;

   582 

   583         edgeSumDeltaY = 0;

   584 

   585         return this; // fluent API

   586     }

   587 

   588     /**

   589      * Disposes this renderer and recycle it clean up before reusing this instance

   590      */

   591     void dispose() {

   592         if (doStats) {

   593             RendererContext.stats.stat_rdr_activeEdges.add(activeEdgeMaxUsed);

   594             RendererContext.stats.stat_rdr_edges.add(edges.used);

   595             RendererContext.stats.stat_rdr_edges_count

   596                 .add(edges.used / SIZEOF_EDGE_BYTES);

   597         }

   598         if (doCleanDirty) {

   599             // Force zero-fill dirty arrays:

   600             Arrays.fill(crossings,     0);

   601             Arrays.fill(aux_crossings, 0);

   602             Arrays.fill(edgePtrs,      0);

   603             Arrays.fill(aux_edgePtrs,  0);

   604         }

   605         // Return arrays:

   606         if (crossings != crossings_initial) {

   607             rdrCtx.putDirtyIntArray(crossings);

   608             crossings = crossings_initial;

   609             if (aux_crossings != aux_crossings_initial) {

   610                 rdrCtx.putDirtyIntArray(aux_crossings);

   611                 aux_crossings = aux_crossings_initial;

   612             }

   613         }

   614         if (edgePtrs != edgePtrs_initial) {

   615             rdrCtx.putDirtyIntArray(edgePtrs);

   616             edgePtrs = edgePtrs_initial;

   617             if (aux_edgePtrs != aux_edgePtrs_initial) {

   618                 rdrCtx.putDirtyIntArray(aux_edgePtrs);

   619                 aux_edgePtrs = aux_edgePtrs_initial;

   620             }

   621         }

   622         if (alphaLine != alphaLine_initial) {

   623             rdrCtx.putIntArray(alphaLine, 0, 0); // already zero filled

   624             alphaLine = alphaLine_initial;

   625         }

   626         if (blkFlags != blkFlags_initial) {

   627             rdrCtx.putIntArray(blkFlags, 0, 0); // already zero filled

   628             blkFlags = blkFlags_initial;

   629         }

   630 

   631         if (edgeMinY != Float.POSITIVE_INFINITY) {

   632             // clear used part

   633             if (edgeBuckets == edgeBuckets_initial) {

   634                 // fill only used part

   635                 IntArrayCache.fill(edgeBuckets,      buckets_minY,

   636                                                      buckets_maxY,     0);

   637                 IntArrayCache.fill(edgeBucketCounts, buckets_minY,

   638                                                      buckets_maxY + 1, 0);

   639             } else {

   640                  // clear only used part

   641                 rdrCtx.putIntArray(edgeBuckets,      buckets_minY,

   642                                                      buckets_maxY);

   643                 edgeBuckets = edgeBuckets_initial;

   644 

   645                 rdrCtx.putIntArray(edgeBucketCounts, buckets_minY,

   646                                                      buckets_maxY + 1);

   647                 edgeBucketCounts = edgeBucketCounts_initial;

   648             }

   649         } else if (edgeBuckets != edgeBuckets_initial) {

   650             // unused arrays

   651             rdrCtx.putIntArray(edgeBuckets, 0, 0);

   652             edgeBuckets = edgeBuckets_initial;

   653 

   654             rdrCtx.putIntArray(edgeBucketCounts, 0, 0);

   655             edgeBucketCounts = edgeBucketCounts_initial;

   656         }

   657 

   658         // At last: resize back off-heap edges to initial size

   659         if (edges.length != INITIAL_EDGES_CAPACITY) {

   660             // note: may throw OOME:

   661             edges.resize(INITIAL_EDGES_CAPACITY);

   662         }

   663         if (doCleanDirty) {

   664             // Force zero-fill dirty arrays:

   665             edges.fill(BYTE_0);

   666         }

   667         if (doMonitors) {

   668             RendererContext.stats.mon_rdr_endRendering.stop();

   669         }

   670     }

   671 

   672     private static float tosubpixx(final float pix_x) {

   673         return f_SUBPIXEL_POSITIONS_X * pix_x;

   674     }

   675 

   676     private static float tosubpixy(final float pix_y) {

   677         // shift y by -0.5 for fast ceil(y - 0.5):

   678         return f_SUBPIXEL_POSITIONS_Y * pix_y - 0.5f;

   679     }

   680 

   681     @Override

   682     public void moveTo(float pix_x0, float pix_y0) {

   683         closePath();

   684         this.pix_sx0 = pix_x0;

   685         this.pix_sy0 = pix_y0;

   686         this.y0 = tosubpixy(pix_y0);

   687         this.x0 = tosubpixx(pix_x0);

   688     }

   689 

   690     @Override

   691     public void lineTo(float pix_x1, float pix_y1) {

   692         float x1 = tosubpixx(pix_x1);

   693         float y1 = tosubpixy(pix_y1);

   694         addLine(x0, y0, x1, y1);

   695         x0 = x1;

   696         y0 = y1;

   697     }

   698 

   699     @Override

   700     public void curveTo(float x1, float y1,

   701             float x2, float y2,

   702             float x3, float y3)

   703     {

   704         final float xe = tosubpixx(x3);

   705         final float ye = tosubpixy(y3);

   706         curve.set(x0, y0, tosubpixx(x1), tosubpixy(y1),

   707                           tosubpixx(x2), tosubpixy(y2), xe, ye);

   708         curveBreakIntoLinesAndAdd(x0, y0, curve, xe, ye);

   709         x0 = xe;

   710         y0 = ye;

   711     }

   712 

   713     @Override

   714     public void quadTo(float x1, float y1, float x2, float y2) {

   715         final float xe = tosubpixx(x2);

   716         final float ye = tosubpixy(y2);

   717         curve.set(x0, y0, tosubpixx(x1), tosubpixy(y1), xe, ye);

   718         quadBreakIntoLinesAndAdd(x0, y0, curve, xe, ye);

   719         x0 = xe;

   720         y0 = ye;

   721     }

   722 

   723     @Override

   724     public void closePath() {

   725         // lineTo expects its input in pixel coordinates.

   726         lineTo(pix_sx0, pix_sy0);

   727     }

   728 

   729     @Override

   730     public void pathDone() {

   731         closePath();

   732     }

   733 

   734     @Override

   735     public long getNativeConsumer() {

   736         throw new InternalError("Renderer does not use a native consumer.");

   737     }

   738 

   739     // clean alpha array (zero filled)

   740     private int[] alphaLine;

   741     // 2048 (pixelsize) pixel large

   742     private final int[] alphaLine_initial = new int[INITIAL_AA_ARRAY]; // 8K

   743 

   744     private void _endRendering(final int ymin, final int ymax) {

   745         if (DISABLE_RENDER) {

   746             return;

   747         }

   748 

   749         // Get X bounds as true pixel boundaries to compute correct pixel coverage:

   750         final int bboxx0 = bbox_spminX;

   751         final int bboxx1 = bbox_spmaxX;

   752 

   753         final boolean windingRuleEvenOdd = (windingRule == WIND_EVEN_ODD);

   754 

   755         // Useful when processing tile line by tile line

   756         final int[] _alpha = alphaLine;

   757 

   758         // local vars (performance):

   759         final MarlinCache _cache = cache;

   760         final OffHeapArray _edges = edges;

   761         final int[] _edgeBuckets = edgeBuckets;

   762         final int[] _edgeBucketCounts = edgeBucketCounts;

   763 

   764         int[] _crossings = this.crossings;

   765         int[] _edgePtrs  = this.edgePtrs;

   766 

   767         // merge sort auxiliary storage:

   768         int[] _aux_crossings = this.aux_crossings;

   769         int[] _aux_edgePtrs  = this.aux_edgePtrs;

   770 

   771         // copy constants:

   772         final long _OFF_ERROR    = OFF_ERROR;

   773         final long _OFF_BUMP_X   = OFF_BUMP_X;

   774         final long _OFF_BUMP_ERR = OFF_BUMP_ERR;

   775 

   776         final long _OFF_NEXT     = OFF_NEXT;

   777         final long _OFF_YMAX     = OFF_YMAX;

   778 

   779         final int _ALL_BUT_LSB   = ALL_BUT_LSB;

   780         final int _ERR_STEP_MAX  = ERR_STEP_MAX;

   781 

   782         // unsafe I/O:

   783         final Unsafe _unsafe = OffHeapArray.unsafe;

   784         final long    addr0  = _edges.address;

   785         long addr;

   786         final int _SUBPIXEL_LG_POSITIONS_X = SUBPIXEL_LG_POSITIONS_X;

   787         final int _SUBPIXEL_LG_POSITIONS_Y = SUBPIXEL_LG_POSITIONS_Y;

   788         final int _SUBPIXEL_MASK_X = SUBPIXEL_MASK_X;

   789         final int _SUBPIXEL_MASK_Y = SUBPIXEL_MASK_Y;

   790         final int _SUBPIXEL_POSITIONS_X = SUBPIXEL_POSITIONS_X;

   791 

   792         final int _MIN_VALUE = Integer.MIN_VALUE;

   793         final int _MAX_VALUE = Integer.MAX_VALUE;

   794 

   795         // Now we iterate through the scanlines. We must tell emitRow the coord

   796         // of the first non-transparent pixel, so we must keep accumulators for

   797         // the first and last pixels of the section of the current pixel row

   798         // that we will emit.

   799         // We also need to accumulate pix_bbox, but the iterator does it

   800         // for us. We will just get the values from it once this loop is done

   801         int minX = _MAX_VALUE;

   802         int maxX = _MIN_VALUE;

   803 

   804         int y = ymin;

   805         int bucket = y - boundsMinY;

   806 

   807         int numCrossings = this.edgeCount;

   808         int edgePtrsLen = _edgePtrs.length;

   809         int crossingsLen = _crossings.length;

   810         int _arrayMaxUsed = activeEdgeMaxUsed;

   811         int ptrLen = 0, newCount, ptrEnd;

   812 

   813         int bucketcount, i, j, ecur;

   814         int cross, lastCross;

   815         int x0, x1, tmp, sum, prev, curx, curxo, crorientation, err;

   816         int pix_x, pix_xmaxm1, pix_xmax;

   817 

   818         int low, high, mid, prevNumCrossings;

   819         boolean useBinarySearch;

   820 

   821         final int[] _blkFlags = blkFlags;

   822         final int _BLK_SIZE_LG = BLOCK_SIZE_LG;

   823         final int _BLK_SIZE = BLOCK_SIZE;

   824 

   825         final boolean _enableBlkFlagsHeuristics = ENABLE_BLOCK_FLAGS_HEURISTICS && this.enableBlkFlags;

   826 

   827         // Use block flags if large pixel span and few crossings:

   828         // ie mean(distance between crossings) is high

   829         boolean useBlkFlags = this.prevUseBlkFlags;

   830 

   831         final int stroking = rdrCtx.stroking;

   832 

   833         int lastY = -1; // last emited row

   834 

   835 

   836         // Iteration on scanlines

   837         for (; y < ymax; y++, bucket++) {

   838             // --- from former ScanLineIterator.next()

   839             bucketcount = _edgeBucketCounts[bucket];

   840 

   841             // marker on previously sorted edges:

   842             prevNumCrossings = numCrossings;

   843 

   844             // bucketCount indicates new edge / edge end:

   845             if (bucketcount != 0) {

   846                 if (doStats) {

   847                     RendererContext.stats.stat_rdr_activeEdges_updates

   848                         .add(numCrossings);

   849                 }

   850 

   851                 // last bit set to 1 means that edges ends

   852                 if ((bucketcount & 0x1) != 0) {

   853                     // eviction in active edge list

   854                     // cache edges[] address + offset

   855                     addr = addr0 + _OFF_YMAX;

   856 

   857                     for (i = 0, newCount = 0; i < numCrossings; i++) {

   858                         // get the pointer to the edge

   859                         ecur = _edgePtrs[i];

   860                         // random access so use unsafe:

   861                         if (_unsafe.getInt(addr + ecur) > y) {

   862                             _edgePtrs[newCount++] = ecur;

   863                         }

   864                     }

   865                     // update marker on sorted edges minus removed edges:

   866                     prevNumCrossings = numCrossings = newCount;

   867                 }

   868 

   869                 ptrLen = bucketcount >> 1; // number of new edge

   870 

   871                 if (ptrLen != 0) {

   872                     if (doStats) {

   873                         RendererContext.stats.stat_rdr_activeEdges_adds

   874                             .add(ptrLen);

   875                         if (ptrLen > 10) {

   876                             RendererContext.stats.stat_rdr_activeEdges_adds_high

   877                                 .add(ptrLen);

   878                         }

   879                     }

   880                     ptrEnd = numCrossings + ptrLen;

   881 

   882                     if (edgePtrsLen < ptrEnd) {

   883                         if (doStats) {

   884                             RendererContext.stats.stat_array_renderer_edgePtrs

   885                                 .add(ptrEnd);

   886                         }

   887                         this.edgePtrs = _edgePtrs

   888                             = rdrCtx.widenDirtyIntArray(_edgePtrs, numCrossings,

   889                                                         ptrEnd);

   890 

   891                         edgePtrsLen = _edgePtrs.length;

   892                         // Get larger auxiliary storage:

   893                         if (_aux_edgePtrs != aux_edgePtrs_initial) {

   894                             rdrCtx.putDirtyIntArray(_aux_edgePtrs);

   895                         }

   896                         // use ArrayCache.getNewSize() to use the same growing

   897                         // factor than widenDirtyIntArray():

   898                         if (doStats) {

   899                             RendererContext.stats.stat_array_renderer_aux_edgePtrs

   900                                 .add(ptrEnd);

   901                         }

   902                         this.aux_edgePtrs = _aux_edgePtrs

   903                             = rdrCtx.getDirtyIntArray(

   904                                 ArrayCache.getNewSize(numCrossings, ptrEnd)

   905                             );

   906                     }

   907 

   908                     // cache edges[] address + offset

   909                     addr = addr0 + _OFF_NEXT;

   910 

   911                     // add new edges to active edge list:

   912                     for (ecur = _edgeBuckets[bucket];

   913                          numCrossings < ptrEnd; numCrossings++)

   914                     {

   915                         // store the pointer to the edge

   916                         _edgePtrs[numCrossings] = ecur;

   917                         // random access so use unsafe:

   918                         ecur = _unsafe.getInt(addr + ecur);

   919                     }

   920 

   921                     if (crossingsLen < numCrossings) {

   922                         // Get larger array:

   923                         if (_crossings != crossings_initial) {

   924                             rdrCtx.putDirtyIntArray(_crossings);

   925                         }

   926                         if (doStats) {

   927                             RendererContext.stats.stat_array_renderer_crossings

   928                                 .add(numCrossings);

   929                         }

   930                         this.crossings = _crossings

   931                             = rdrCtx.getDirtyIntArray(numCrossings);

   932 

   933                         // Get larger auxiliary storage:

   934                         if (_aux_crossings != aux_crossings_initial) {

   935                             rdrCtx.putDirtyIntArray(_aux_crossings);

   936                         }

   937                         if (doStats) {

   938                             RendererContext.stats.stat_array_renderer_aux_crossings

   939                                 .add(numCrossings);

   940                         }

   941                         this.aux_crossings = _aux_crossings

   942                             = rdrCtx.getDirtyIntArray(numCrossings);

   943 

   944                         crossingsLen = _crossings.length;

   945                     }

   946                     if (doStats) {

   947                         // update max used mark

   948                         if (numCrossings > _arrayMaxUsed) {

   949                             _arrayMaxUsed = numCrossings;

   950                         }

   951                     }

   952                 } // ptrLen != 0

   953             } // bucketCount != 0

   954 

   955 

   956             if (numCrossings != 0) {

   957                 /*

   958                  * thresholds to switch to optimized merge sort

   959                  * for newly added edges + final merge pass.

   960                  */

   961                 if ((ptrLen < 10) || (numCrossings < 40)) {

   962                     if (doStats) {

   963                         RendererContext.stats.hist_rdr_crossings

   964                             .add(numCrossings);

   965                         RendererContext.stats.hist_rdr_crossings_adds

   966                             .add(ptrLen);

   967                     }

   968 

   969                     /*

   970                      * threshold to use binary insertion sort instead of

   971                      * straight insertion sort (to reduce minimize comparisons).

   972                      */

   973                     useBinarySearch = (numCrossings >= 20);

   974 

   975                     // if small enough:

   976                     lastCross = _MIN_VALUE;

   977 

   978                     for (i = 0; i < numCrossings; i++) {

   979                         // get the pointer to the edge

   980                         ecur = _edgePtrs[i];

   981 

   982                         /* convert subpixel coordinates (float) into pixel

   983                             positions (int) for coming scanline */

   984                         /* note: it is faster to always update edges even

   985                            if it is removed from AEL for coming or last scanline */

   986 

   987                         // random access so use unsafe:

   988                         addr = addr0 + ecur; // ecur + OFF_F_CURX

   989 

   990                         // get current crossing:

   991                         curx = _unsafe.getInt(addr);

   992 

   993                         // update crossing with orientation at last bit:

   994                         cross = curx;

   995 

   996                         // Increment x using DDA (fixed point):

   997                         curx += _unsafe.getInt(addr + _OFF_BUMP_X);

   998 

   999                         // Increment error:

  1000                         err  =  _unsafe.getInt(addr + _OFF_ERROR)

  1001                               + _unsafe.getInt(addr + _OFF_BUMP_ERR);

  1002 

  1003                         // Manual carry handling:

  1004                         // keep sign and carry bit only and ignore last bit (preserve orientation):

  1005                         _unsafe.putInt(addr,               curx - ((err >> 30) & _ALL_BUT_LSB));

  1006                         _unsafe.putInt(addr + _OFF_ERROR, (err & _ERR_STEP_MAX));

  1007 

  1008                         if (doStats) {

  1009                             RendererContext.stats.stat_rdr_crossings_updates

  1010                                 .add(numCrossings);

  1011                         }

  1012 

  1013                         // insertion sort of crossings:

  1014                         if (cross < lastCross) {

  1015                             if (doStats) {

  1016                                 RendererContext.stats.stat_rdr_crossings_sorts

  1017                                     .add(i);

  1018                             }

  1019 

  1020                             /* use binary search for newly added edges

  1021                                in crossings if arrays are large enough */

  1022                             if (useBinarySearch && (i >= prevNumCrossings)) {

  1023                                 if (doStats) {

  1024                                     RendererContext.stats.

  1025                                         stat_rdr_crossings_bsearch.add(i);

  1026                                 }

  1027                                 low = 0;

  1028                                 high = i - 1;

  1029 

  1030                                 do {

  1031                                     // note: use signed shift (not >>>) for performance

  1032                                     // as indices are small enough to exceed Integer.MAX_VALUE

  1033                                     mid = (low + high) >> 1;

  1034 

  1035                                     if (_crossings[mid] < cross) {

  1036                                         low = mid + 1;

  1037                                     } else {

  1038                                         high = mid - 1;

  1039                                     }

  1040                                 } while (low <= high);

  1041 

  1042                                 for (j = i - 1; j >= low; j--) {

  1043                                     _crossings[j + 1] = _crossings[j];

  1044                                     _edgePtrs [j + 1] = _edgePtrs[j];

  1045                                 }

  1046                                 _crossings[low] = cross;

  1047                                 _edgePtrs [low] = ecur;

  1048 

  1049                             } else {

  1050                                 j = i - 1;

  1051                                 _crossings[i] = _crossings[j];

  1052                                 _edgePtrs[i] = _edgePtrs[j];

  1053 

  1054                                 while ((--j >= 0) && (_crossings[j] > cross)) {

  1055                                     _crossings[j + 1] = _crossings[j];

  1056                                     _edgePtrs [j + 1] = _edgePtrs[j];

  1057                                 }

  1058                                 _crossings[j + 1] = cross;

  1059                                 _edgePtrs [j + 1] = ecur;

  1060                             }

  1061 

  1062                         } else {

  1063                             _crossings[i] = lastCross = cross;

  1064                         }

  1065                     }

  1066                 } else {

  1067                     if (doStats) {

  1068                         RendererContext.stats.stat_rdr_crossings_msorts

  1069                             .add(numCrossings);

  1070                         RendererContext.stats.hist_rdr_crossings_ratio

  1071                             .add((1000 * ptrLen) / numCrossings);

  1072                         RendererContext.stats.hist_rdr_crossings_msorts

  1073                             .add(numCrossings);

  1074                         RendererContext.stats.hist_rdr_crossings_msorts_adds

  1075                             .add(ptrLen);

  1076                     }

  1077 

  1078                     // Copy sorted data in auxiliary arrays

  1079                     // and perform insertion sort on almost sorted data

  1080                     // (ie i < prevNumCrossings):

  1081 

  1082                     lastCross = _MIN_VALUE;

  1083 

  1084                     for (i = 0; i < numCrossings; i++) {

  1085                         // get the pointer to the edge

  1086                         ecur = _edgePtrs[i];

  1087 

  1088                         /* convert subpixel coordinates (float) into pixel

  1089                             positions (int) for coming scanline */

  1090                         /* note: it is faster to always update edges even

  1091                            if it is removed from AEL for coming or last scanline */

  1092 

  1093                         // random access so use unsafe:

  1094                         addr = addr0 + ecur; // ecur + OFF_F_CURX

  1095 

  1096                         // get current crossing:

  1097                         curx = _unsafe.getInt(addr);

  1098 

  1099                         // update crossing with orientation at last bit:

  1100                         cross = curx;

  1101 

  1102                         // Increment x using DDA (fixed point):

  1103                         curx += _unsafe.getInt(addr + _OFF_BUMP_X);

  1104 

  1105                         // Increment error:

  1106                         err  =  _unsafe.getInt(addr + _OFF_ERROR)

  1107                               + _unsafe.getInt(addr + _OFF_BUMP_ERR);

  1108 

  1109                         // Manual carry handling:

  1110                         // keep sign and carry bit only and ignore last bit (preserve orientation):

  1111                         _unsafe.putInt(addr,               curx - ((err >> 30) & _ALL_BUT_LSB));

  1112                         _unsafe.putInt(addr + _OFF_ERROR, (err & _ERR_STEP_MAX));

  1113 

  1114                         if (doStats) {

  1115                             RendererContext.stats.stat_rdr_crossings_updates

  1116                                 .add(numCrossings);

  1117                         }

  1118 

  1119                         if (i >= prevNumCrossings) {

  1120                             // simply store crossing as edgePtrs is in-place:

  1121                             // will be copied and sorted efficiently by mergesort later:

  1122                             _crossings[i]     = cross;

  1123 

  1124                         } else if (cross < lastCross) {

  1125                             if (doStats) {

  1126                                 RendererContext.stats.stat_rdr_crossings_sorts

  1127                                     .add(i);

  1128                             }

  1129 

  1130                             // (straight) insertion sort of crossings:

  1131                             j = i - 1;

  1132                             _aux_crossings[i] = _aux_crossings[j];

  1133                             _aux_edgePtrs[i] = _aux_edgePtrs[j];

  1134