| /* |
| * Copyright (c) 2007, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package sun.java2d.pisces; |
| |
| import java.util.Arrays; |
| |
| public class Renderer implements LineSink { |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // Scan line iterator and edge crossing data. |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| private int[] crossings; |
| |
| // This is an array of indices into the edge array. It is initialized to |
| // [i * SIZEOF_STRUCT_EDGE for i in range(0, edgesSize/SIZEOF_STRUCT_EDGE)] |
| // (where range(i, j) is i,i+1,...,j-1 -- just like in python). |
| // The reason for keeping this is because we need the edges array sorted |
| // by y0, but we don't want to move all that data around, so instead we |
| // sort the indices into the edge array, and use edgeIndices to access |
| // the edges array. This is meant to simulate a pointer array (hence the name) |
| private int[] edgePtrs; |
| |
| // crossing bounds. The bounds are not necessarily tight (the scan line |
| // at minY, for example, might have no crossings). The x bounds will |
| // be accumulated as crossings are computed. |
| private int minY, maxY; |
| private int minX, maxX; |
| private int nextY; |
| |
| // indices into the edge pointer list. They indicate the "active" sublist in |
| // the edge list (the portion of the list that contains all the edges that |
| // cross the next scan line). |
| private int lo, hi; |
| |
| private static final int INIT_CROSSINGS_SIZE = 50; |
| private void ScanLineItInitialize() { |
| crossings = new int[INIT_CROSSINGS_SIZE]; |
| edgePtrs = new int[edgesSize / SIZEOF_STRUCT_EDGE]; |
| for (int i = 0; i < edgePtrs.length; i++) { |
| edgePtrs[i] = i * SIZEOF_STRUCT_EDGE; |
| } |
| |
| qsort(0, edgePtrs.length - 1); |
| |
| // We don't care if we clip some of the line off with ceil, since |
| // no scan line crossings will be eliminated (in fact, the ceil is |
| // the y of the first scan line crossing). |
| nextY = minY = Math.max(boundsMinY, (int)Math.ceil(edgeMinY)); |
| maxY = Math.min(boundsMaxY, (int)Math.ceil(edgeMaxY)); |
| |
| for (lo = 0; lo < edgePtrs.length && edges[edgePtrs[lo]+Y1] <= nextY; lo++) |
| ; |
| for (hi = lo; hi < edgePtrs.length && edges[edgePtrs[hi]+CURY] <= nextY; hi++) |
| ; // the active list is *edgePtrs[lo] (inclusive) *edgePtrs[hi] (exclusive) |
| for (int i = lo; i < hi; i++) { |
| setCurY(edgePtrs[i], nextY); |
| } |
| |
| // We accumulate X in the iterator because accumulating it in addEdge |
| // like we do with Y does not do much good: if there's an edge |
| // (0,0)->(1000,10000), and if y gets clipped to 1000, then the x |
| // bound should be 100, but the accumulator from addEdge would say 1000, |
| // so we'd still have to accumulate the X bounds as we add crossings. |
| minX = boundsMinX; |
| maxX = boundsMaxX; |
| } |
| |
| private int ScanLineItCurrentY() { |
| return nextY - 1; |
| } |
| |
| private int ScanLineItGoToNextYAndComputeCrossings() { |
| // we go through the active list and remove the ones that don't cross |
| // the nextY scanline. |
| int crossingIdx = 0; |
| for (int i = lo; i < hi; i++) { |
| if (edges[edgePtrs[i]+Y1] <= nextY) { |
| edgePtrs[i] = edgePtrs[lo++]; |
| } |
| } |
| if (hi - lo > crossings.length) { |
| int newSize = Math.max(hi - lo, crossings.length * 2); |
| crossings = Arrays.copyOf(crossings, newSize); |
| } |
| // Now every edge between lo and hi crosses nextY. Compute it's |
| // crossing and put it in the crossings array. |
| for (int i = lo; i < hi; i++) { |
| addCrossing(nextY, getCurCrossing(edgePtrs[i]), (int)edges[edgePtrs[i]+OR], crossingIdx); |
| gotoNextY(edgePtrs[i]); |
| crossingIdx++; |
| } |
| |
| nextY++; |
| // Expand active list to include new edges. |
| for (; hi < edgePtrs.length && edges[edgePtrs[hi]+CURY] <= nextY; hi++) { |
| setCurY(edgePtrs[hi], nextY); |
| } |
| |
| Arrays.sort(crossings, 0, crossingIdx); |
| return crossingIdx; |
| } |
| |
| private boolean ScanLineItHasNext() { |
| return nextY < maxY; |
| } |
| |
| private void addCrossing(int y, int x, int or, int idx) { |
| if (x < minX) { |
| minX = x; |
| } |
| if (x > maxX) { |
| maxX = x; |
| } |
| x <<= 1; |
| crossings[idx] = ((or == 1) ? (x | 0x1) : x); |
| } |
| |
| |
| // quicksort implementation for sorting the edge indices ("pointers") |
| // by increasing y0. first, last are indices into the "pointer" array |
| // It sorts the pointer array from first (inclusive) to last (inclusive) |
| private void qsort(int first, int last) { |
| if (last > first) { |
| int p = partition(first, last); |
| if (first < p - 1) { |
| qsort(first, p - 1); |
| } |
| if (p < last) { |
| qsort(p, last); |
| } |
| } |
| } |
| |
| // i, j are indices into edgePtrs. |
| private int partition(int i, int j) { |
| int pivotVal = edgePtrs[i]; |
| while (i <= j) { |
| // edges[edgePtrs[i]+1] is equivalent to (*(edgePtrs[i])).y0 in C |
| while (edges[edgePtrs[i]+CURY] < edges[pivotVal+CURY]) { i++; } |
| while (edges[edgePtrs[j]+CURY] > edges[pivotVal+CURY]) { j--; } |
| if (i <= j) { |
| int tmp = edgePtrs[i]; |
| edgePtrs[i] = edgePtrs[j]; |
| edgePtrs[j] = tmp; |
| i++; |
| j--; |
| } |
| } |
| return i; |
| } |
| |
| //============================================================================ |
| |
| |
| ////////////////////////////////////////////////////////////////////////////// |
| // EDGE LIST |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| private static final int INIT_NUM_EDGES = 1000; |
| private static final int SIZEOF_STRUCT_EDGE = 5; |
| |
| // The following array is a poor man's struct array: |
| // it simulates a struct array by having |
| // edges[SIZEOF_STRUCT_EDGE * i + j] be the jth field in the ith element |
| // of an array of edge structs. |
| private float[] edges; |
| private int edgesSize; // size of the edge list. |
| private static final int Y1 = 0; |
| private static final int SLOPE = 1; |
| private static final int OR = 2; // the orientation. This can be -1 or 1. |
| // -1 means up, 1 means down. |
| private static final int CURY = 3; // j = 5 corresponds to the "current Y". |
| // Each edge keeps track of the last scanline |
| // crossing it computed, and this is the y coord of |
| // that scanline. |
| private static final int CURX = 4; //the x coord of the current crossing. |
| |
| // Note that while the array is declared as a float[] not all of it's |
| // elements should be floats. currentY and Orientation should be ints (or int and |
| // byte respectively), but they all need to be the same type. This isn't |
| // really a problem because floats can represent exactly all 23 bit integers, |
| // which should be more than enough. |
| // Note, also, that we only need x1 for slope computation, so we don't need |
| // to store it. x0, y0 don't need to be stored either. They can be put into |
| // curx, cury, and it's ok if they're lost when curx and cury are changed. |
| // We take this undeniably ugly and error prone approach (instead of simply |
| // making an Edge class) for performance reasons. Also, it would probably be nicer |
| // to have one array for each field, but that would defeat the purpose because |
| // it would make poor use of the processor cache, since we tend to access |
| // all the fields for one edge at a time. |
| |
| private float edgeMinY; |
| private float edgeMaxY; |
| |
| |
| private void addEdge(float x0, float y0, float x1, float y1) { |
| float or = (y0 < y1) ? 1f : -1f; // orientation: 1 = UP; -1 = DOWN |
| if (or == -1) { |
| float tmp = y0; |
| y0 = y1; |
| y1 = tmp; |
| tmp = x0; |
| x0 = x1; |
| x1 = tmp; |
| } |
| // skip edges that don't cross a scanline |
| if (Math.ceil(y0) >= Math.ceil(y1)) { |
| return; |
| } |
| |
| int newSize = edgesSize + SIZEOF_STRUCT_EDGE; |
| if (edges.length < newSize) { |
| edges = Arrays.copyOf(edges, newSize * 2); |
| } |
| edges[edgesSize+CURX] = x0; |
| edges[edgesSize+CURY] = y0; |
| edges[edgesSize+Y1] = y1; |
| edges[edgesSize+SLOPE] = (x1 - x0) / (y1 - y0); |
| edges[edgesSize+OR] = or; |
| // the crossing values can't be initialized meaningfully yet. This |
| // will have to wait until setCurY is called |
| edgesSize += SIZEOF_STRUCT_EDGE; |
| |
| // Accumulate edgeMinY and edgeMaxY |
| if (y0 < edgeMinY) { edgeMinY = y0; } |
| if (y1 > edgeMaxY) { edgeMaxY = y1; } |
| } |
| |
| // As far as the following methods care, this edges extends to infinity. |
| // They can compute the x intersect of any horizontal line. |
| // precondition: idx is the index to the start of the desired edge. |
| // So, if the ith edge is wanted, idx should be SIZEOF_STRUCT_EDGE * i |
| private void setCurY(int idx, int y) { |
| // compute the x crossing of edge at idx and horizontal line y |
| // currentXCrossing = (y - y0)*slope + x0 |
| edges[idx + CURX] = (y - edges[idx + CURY]) * edges[idx + SLOPE] + edges[idx+CURX]; |
| edges[idx + CURY] = (float)y; |
| } |
| |
| private void gotoNextY(int idx) { |
| edges[idx + CURY] += 1f; // i.e. curY += 1 |
| edges[idx + CURX] += edges[idx + SLOPE]; // i.e. curXCrossing += slope |
| } |
| |
| private int getCurCrossing(int idx) { |
| return (int)edges[idx + CURX]; |
| } |
| //==================================================================================== |
| |
| public static final int WIND_EVEN_ODD = 0; |
| public static final int WIND_NON_ZERO = 1; |
| |
| // Antialiasing |
| final private int SUBPIXEL_LG_POSITIONS_X; |
| final private int SUBPIXEL_LG_POSITIONS_Y; |
| final private int SUBPIXEL_POSITIONS_X; |
| final private int SUBPIXEL_POSITIONS_Y; |
| final private int SUBPIXEL_MASK_X; |
| final private int SUBPIXEL_MASK_Y; |
| final int MAX_AA_ALPHA; |
| |
| // Cache to store RLE-encoded coverage mask of the current primitive |
| final PiscesCache cache; |
| |
| // Bounds of the drawing region, at subpixel precision. |
| final private int boundsMinX, boundsMinY, boundsMaxX, boundsMaxY; |
| |
| // Pixel bounding box for current primitive |
| private int pix_bboxX0, pix_bboxY0, pix_bboxX1, pix_bboxY1; |
| |
| // Current winding rule |
| final private int windingRule; |
| |
| // Current drawing position, i.e., final point of last segment |
| private float x0, y0; |
| |
| // Position of most recent 'moveTo' command |
| private float pix_sx0, pix_sy0; |
| |
| public Renderer(int subpixelLgPositionsX, int subpixelLgPositionsY, |
| int pix_boundsX, int pix_boundsY, |
| int pix_boundsWidth, int pix_boundsHeight, |
| int windingRule, |
| PiscesCache cache) { |
| this.SUBPIXEL_LG_POSITIONS_X = subpixelLgPositionsX; |
| this.SUBPIXEL_LG_POSITIONS_Y = subpixelLgPositionsY; |
| this.SUBPIXEL_MASK_X = (1 << (SUBPIXEL_LG_POSITIONS_X)) - 1; |
| this.SUBPIXEL_MASK_Y = (1 << (SUBPIXEL_LG_POSITIONS_Y)) - 1; |
| this.SUBPIXEL_POSITIONS_X = 1 << (SUBPIXEL_LG_POSITIONS_X); |
| this.SUBPIXEL_POSITIONS_Y = 1 << (SUBPIXEL_LG_POSITIONS_Y); |
| this.MAX_AA_ALPHA = (SUBPIXEL_POSITIONS_X * SUBPIXEL_POSITIONS_Y); |
| |
| this.edges = new float[SIZEOF_STRUCT_EDGE * INIT_NUM_EDGES]; |
| edgeMinY = Float.POSITIVE_INFINITY; |
| edgeMaxY = Float.NEGATIVE_INFINITY; |
| edgesSize = 0; |
| |
| this.windingRule = windingRule; |
| this.cache = cache; |
| |
| this.boundsMinX = pix_boundsX * SUBPIXEL_POSITIONS_X; |
| this.boundsMinY = pix_boundsY * SUBPIXEL_POSITIONS_Y; |
| this.boundsMaxX = (pix_boundsX + pix_boundsWidth) * SUBPIXEL_POSITIONS_X; |
| this.boundsMaxY = (pix_boundsY + pix_boundsHeight) * SUBPIXEL_POSITIONS_Y; |
| |
| this.pix_bboxX0 = pix_boundsX; |
| this.pix_bboxY0 = pix_boundsY; |
| this.pix_bboxX1 = pix_boundsX + pix_boundsWidth; |
| this.pix_bboxY1 = pix_boundsY + pix_boundsHeight; |
| } |
| |
| private float tosubpixx(float pix_x) { |
| return pix_x * SUBPIXEL_POSITIONS_X; |
| } |
| private float tosubpixy(float pix_y) { |
| return pix_y * SUBPIXEL_POSITIONS_Y; |
| } |
| |
| public void moveTo(float pix_x0, float pix_y0) { |
| close(); |
| this.pix_sx0 = pix_x0; |
| this.pix_sy0 = pix_y0; |
| this.y0 = tosubpixy(pix_y0); |
| this.x0 = tosubpixx(pix_x0); |
| } |
| |
| public void lineJoin() { /* do nothing */ } |
| |
| public void lineTo(float pix_x1, float pix_y1) { |
| float x1 = tosubpixx(pix_x1); |
| float y1 = tosubpixy(pix_y1); |
| |
| // Ignore horizontal lines |
| if (y0 == y1) { |
| this.x0 = x1; |
| return; |
| } |
| |
| addEdge(x0, y0, x1, y1); |
| |
| this.x0 = x1; |
| this.y0 = y1; |
| } |
| |
| public void close() { |
| // lineTo expects its input in pixel coordinates. |
| lineTo(pix_sx0, pix_sy0); |
| } |
| |
| public void end() { |
| close(); |
| } |
| |
| private void _endRendering() { |
| // Mask to determine the relevant bit of the crossing sum |
| // 0x1 if EVEN_ODD, all bits if NON_ZERO |
| int mask = (windingRule == WIND_EVEN_ODD) ? 0x1 : ~0x0; |
| |
| // add 1 to better deal with the last pixel in a pixel row. |
| int width = ((boundsMaxX - boundsMinX) >> SUBPIXEL_LG_POSITIONS_X) + 1; |
| byte[] alpha = new byte[width+1]; |
| |
| // Now we iterate through the scanlines. We must tell emitRow the coord |
| // of the first non-transparent pixel, so we must keep accumulators for |
| // the first and last pixels of the section of the current pixel row |
| // that we will emit. |
| // We also need to accumulate pix_bbox*, but the iterator does it |
| // for us. We will just get the values from it once this loop is done |
| int pix_maxX = Integer.MIN_VALUE; |
| int pix_minX = Integer.MAX_VALUE; |
| |
| int y = boundsMinY; // needs to be declared here so we emit the last row properly. |
| ScanLineItInitialize(); |
| for ( ; ScanLineItHasNext(); ) { |
| int numCrossings = ScanLineItGoToNextYAndComputeCrossings(); |
| y = ScanLineItCurrentY(); |
| |
| if (numCrossings > 0) { |
| int lowx = crossings[0] >> 1; |
| int highx = crossings[numCrossings - 1] >> 1; |
| int x0 = Math.max(lowx, boundsMinX); |
| int x1 = Math.min(highx, boundsMaxX); |
| |
| pix_minX = Math.min(pix_minX, x0 >> SUBPIXEL_LG_POSITIONS_X); |
| pix_maxX = Math.max(pix_maxX, x1 >> SUBPIXEL_LG_POSITIONS_X); |
| } |
| |
| int sum = 0; |
| int prev = boundsMinX; |
| for (int i = 0; i < numCrossings; i++) { |
| int curxo = crossings[i]; |
| int curx = curxo >> 1; |
| int crorientation = ((curxo & 0x1) == 0x1) ? 1 : -1; |
| if ((sum & mask) != 0) { |
| int x0 = Math.max(prev, boundsMinX); |
| int x1 = Math.min(curx, boundsMaxX); |
| if (x0 < x1) { |
| x0 -= boundsMinX; // turn x0, x1 from coords to indeces |
| x1 -= boundsMinX; // in the alpha array. |
| |
| int pix_x = x0 >> SUBPIXEL_LG_POSITIONS_X; |
| int pix_xmaxm1 = (x1 - 1) >> SUBPIXEL_LG_POSITIONS_X; |
| |
| if (pix_x == pix_xmaxm1) { |
| // Start and end in same pixel |
| alpha[pix_x] += (x1 - x0); |
| alpha[pix_x+1] -= (x1 - x0); |
| } else { |
| int pix_xmax = x1 >> SUBPIXEL_LG_POSITIONS_X; |
| alpha[pix_x] += SUBPIXEL_POSITIONS_X - (x0 & SUBPIXEL_MASK_X); |
| alpha[pix_x+1] += (x0 & SUBPIXEL_MASK_X); |
| alpha[pix_xmax] -= SUBPIXEL_POSITIONS_X - (x1 & SUBPIXEL_MASK_X); |
| alpha[pix_xmax+1] -= (x1 & SUBPIXEL_MASK_X); |
| } |
| } |
| } |
| sum += crorientation; |
| prev = curx; |
| } |
| |
| if ((y & SUBPIXEL_MASK_Y) == SUBPIXEL_MASK_Y) { |
| emitRow(alpha, y >> SUBPIXEL_LG_POSITIONS_Y, pix_minX, pix_maxX); |
| pix_minX = Integer.MAX_VALUE; |
| pix_maxX = Integer.MIN_VALUE; |
| } |
| } |
| |
| // Emit final row |
| if (pix_maxX >= pix_minX) { |
| emitRow(alpha, y >> SUBPIXEL_LG_POSITIONS_Y, pix_minX, pix_maxX); |
| } |
| pix_bboxX0 = minX >> SUBPIXEL_LG_POSITIONS_X; |
| pix_bboxX1 = maxX >> SUBPIXEL_LG_POSITIONS_X; |
| pix_bboxY0 = minY >> SUBPIXEL_LG_POSITIONS_Y; |
| pix_bboxY1 = maxY >> SUBPIXEL_LG_POSITIONS_Y; |
| } |
| |
| |
| public void endRendering() { |
| // Set up the cache to accumulate the bounding box |
| if (cache != null) { |
| cache.bboxX0 = Integer.MAX_VALUE; |
| cache.bboxY0 = Integer.MAX_VALUE; |
| cache.bboxX1 = Integer.MIN_VALUE; |
| cache.bboxY1 = Integer.MIN_VALUE; |
| } |
| |
| _endRendering(); |
| } |
| |
| public void getBoundingBox(int[] pix_bbox) { |
| pix_bbox[0] = pix_bboxX0; |
| pix_bbox[1] = pix_bboxY0; |
| pix_bbox[2] = pix_bboxX1 - pix_bboxX0; |
| pix_bbox[3] = pix_bboxY1 - pix_bboxY0; |
| } |
| |
| private void emitRow(byte[] alphaRow, int pix_y, int pix_from, int pix_to) { |
| // Copy rowAA data into the cache if one is present |
| if (cache != null) { |
| if (pix_to >= pix_from) { |
| cache.startRow(pix_y, pix_from, pix_to); |
| |
| // Perform run-length encoding and store results in the cache |
| int from = pix_from - (boundsMinX >> SUBPIXEL_LG_POSITIONS_X); |
| int to = pix_to - (boundsMinX >> SUBPIXEL_LG_POSITIONS_X); |
| |
| int runLen = 1; |
| byte startVal = alphaRow[from]; |
| for (int i = from + 1; i <= to; i++) { |
| byte nextVal = (byte)(startVal + alphaRow[i]); |
| if (nextVal == startVal && runLen < 255) { |
| runLen++; |
| } else { |
| cache.addRLERun(startVal, runLen); |
| runLen = 1; |
| startVal = nextVal; |
| } |
| } |
| cache.addRLERun(startVal, runLen); |
| cache.addRLERun((byte)0, 0); |
| } |
| } |
| java.util.Arrays.fill(alphaRow, (byte)0); |
| } |
| } |
