| /* | |
| * Copyright (c) 2013, 2014, 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. | |
| */ | |
| /** | |
| * Bresenham line-drawing implementation decomposing line segments | |
| * into a series of rectangles. | |
| * This is required, because xrender doesn't support line primitives directly. | |
| * The code here is an almost 1:1 port of the existing C-source contained in | |
| * sun/java2d/loop/DrawLine.c and sun/java2d/loop/LoopMacros.h | |
| */ | |
| package sun.java2d.xr; | |
| public final class XRDrawLine { | |
| static final int BIG_MAX = ((1 << 29) - 1); | |
| static final int BIG_MIN = (-(1 << 29)); | |
| static final int OUTCODE_TOP = 1; | |
| static final int OUTCODE_BOTTOM = 2; | |
| static final int OUTCODE_LEFT = 4; | |
| static final int OUTCODE_RIGHT = 8; | |
| int x1, y1, x2, y2; | |
| int ucX1, ucY1, ucX2, ucY2; | |
| DirtyRegion region = new DirtyRegion(); | |
| protected void rasterizeLine(GrowableRectArray rectBuffer, int _x1, | |
| int _y1, int _x2, int _y2, int cxmin, int cymin, int cxmax, | |
| int cymax, boolean clip, boolean overflowCheck) { | |
| float diagF; | |
| int error; | |
| int steps; | |
| int errminor, errmajor; | |
| boolean xmajor; | |
| int dx, dy, ax, ay; | |
| initCoordinates(_x1, _y1, _x2, _y2, overflowCheck); | |
| dx = x2 - x1; | |
| dy = y2 - y1; | |
| ax = Math.abs(dx); | |
| ay = Math.abs(dy); | |
| xmajor = (ax >= ay); | |
| diagF = ((float) ax) / ay; | |
| if (clip | |
| && !clipCoordinates(cxmin, cymin, cxmax, cymax, xmajor, dx, dy, | |
| ax, ay)) { | |
| // whole line was clipped away | |
| return; | |
| } | |
| region.setDirtyLineRegion(x1, y1, x2, y2); | |
| int xDiff = region.x2 - region.x; | |
| int yDiff = region.y2 - region.y; | |
| if (xDiff == 0 || yDiff == 0) { | |
| // horizontal / diagonal lines can be represented by a single | |
| // rectangle | |
| rectBuffer.pushRectValues(region.x, region.y, region.x2 - region.x | |
| + 1, region.y2 - region.y + 1); | |
| return; | |
| } | |
| // Setup bresenham | |
| if (xmajor) { | |
| errmajor = ay * 2; | |
| errminor = ax * 2; | |
| ax = -ax; /* For clipping adjustment below */ | |
| steps = x2 - x1; | |
| } else { | |
| errmajor = ax * 2; | |
| errminor = ay * 2; | |
| ay = -ay; /* For clipping adjustment below */ | |
| steps = y2 - y1; | |
| } | |
| if ((steps = (Math.abs(steps) + 1)) == 0) { | |
| return; | |
| } | |
| error = -(errminor / 2); | |
| if (y1 != ucY1) { | |
| int ysteps = y1 - ucY1; | |
| if (ysteps < 0) { | |
| ysteps = -ysteps; | |
| } | |
| error += ysteps * ax * 2; | |
| } | |
| if (x1 != ucX1) { | |
| int xsteps = x1 - ucX1; | |
| if (xsteps < 0) { | |
| xsteps = -xsteps; | |
| } | |
| error += xsteps * ay * 2; | |
| } | |
| error += errmajor; | |
| errminor -= errmajor; | |
| int xStep = (dx > 0 ? 1 : -1); | |
| int yStep = (dy > 0 ? 1 : -1); | |
| int orthogonalXStep = xmajor ? xStep : 0; | |
| int orthogonalYStep = !xmajor ? yStep : 0; | |
| /* | |
| * For lines which proceed in one direction faster, we try to generate | |
| * rectangles instead of points. Otherwise we try to avoid the extra | |
| * work... | |
| */ | |
| if (diagF <= 0.9 || diagF >= 1.1) { | |
| lineToRects(rectBuffer, steps, error, errmajor, errminor, xStep, | |
| yStep, orthogonalXStep, orthogonalYStep); | |
| } else { | |
| lineToPoints(rectBuffer, steps, error, errmajor, errminor, xStep, | |
| yStep, orthogonalXStep, orthogonalYStep); | |
| } | |
| } | |
| private void lineToPoints(GrowableRectArray rectBuffer, int steps, | |
| int error, int errmajor, int errminor, int xStep, int yStep, | |
| int orthogonalXStep, int orthogonalYStep) { | |
| int x = x1, y = y1; | |
| do { | |
| rectBuffer.pushRectValues(x, y, 1, 1); | |
| // "Traditional" Bresenham line drawing | |
| if (error < 0) { | |
| error += errmajor; | |
| x += orthogonalXStep; | |
| y += orthogonalYStep; | |
| } else { | |
| error -= errminor; | |
| x += xStep; | |
| y += yStep; | |
| } | |
| } while (--steps > 0); | |
| } | |
| private void lineToRects(GrowableRectArray rectBuffer, int steps, | |
| int error, int errmajor, int errminor, int xStep, int yStep, | |
| int orthogonalXStep, int orthogonalYStep) { | |
| int x = x1, y = y1; | |
| int rectX = Integer.MIN_VALUE, rectY = 0; | |
| int rectW = 0, rectH = 0; | |
| do { | |
| // Combine the resulting rectangles | |
| // for steps performed in a single direction. | |
| if (y == rectY) { | |
| if (x == (rectX + rectW)) { | |
| rectW++; | |
| } else if (x == (rectX - 1)) { | |
| rectX--; | |
| rectW++; | |
| } | |
| } else if (x == rectX) { | |
| if (y == (rectY + rectH)) { | |
| rectH++; | |
| } else if (y == (rectY - 1)) { | |
| rectY--; | |
| rectH++; | |
| } | |
| } else { | |
| // Diagonal step: add the previous rectangle to the list, | |
| // iff it was "real" (= not initialized before the first | |
| // iteration) | |
| if (rectX != Integer.MIN_VALUE) { | |
| rectBuffer.pushRectValues(rectX, rectY, rectW, rectH); | |
| } | |
| rectX = x; | |
| rectY = y; | |
| rectW = rectH = 1; | |
| } | |
| // "Traditional" Bresenham line drawing | |
| if (error < 0) { | |
| error += errmajor; | |
| x += orthogonalXStep; | |
| y += orthogonalYStep; | |
| } else { | |
| error -= errminor; | |
| x += xStep; | |
| y += yStep; | |
| } | |
| } while (--steps > 0); | |
| // Add last rectangle which isn't handled by the combination-code | |
| // anymore | |
| rectBuffer.pushRectValues(rectX, rectY, rectW, rectH); | |
| } | |
| private boolean clipCoordinates(int cxmin, int cymin, int cxmax, int cymax, | |
| boolean xmajor, int dx, int dy, int ax, int ay) { | |
| int outcode1, outcode2; | |
| outcode1 = outcode(x1, y1, cxmin, cymin, cxmax, cymax); | |
| outcode2 = outcode(x2, y2, cxmin, cymin, cxmax, cymax); | |
| while ((outcode1 | outcode2) != 0) { | |
| long xsteps = 0, ysteps = 0; | |
| if ((outcode1 & outcode2) != 0) { | |
| return false; | |
| } | |
| if (outcode1 != 0) { | |
| if ((outcode1 & (OUTCODE_TOP | OUTCODE_BOTTOM)) != 0) { | |
| if ((outcode1 & OUTCODE_TOP) != 0) { | |
| y1 = cymin; | |
| } else { | |
| y1 = cymax; | |
| } | |
| ysteps = y1 - ucY1; | |
| if (ysteps < 0) { | |
| ysteps = -ysteps; | |
| } | |
| xsteps = 2 * ysteps * ax + ay; | |
| if (xmajor) { | |
| xsteps += ay - ax - 1; | |
| } | |
| xsteps = xsteps / (2 * ay); | |
| if (dx < 0) { | |
| xsteps = -xsteps; | |
| } | |
| x1 = ucX1 + (int) xsteps; | |
| } else if ((outcode1 & (OUTCODE_LEFT | OUTCODE_RIGHT)) != 0) { | |
| if ((outcode1 & OUTCODE_LEFT) != 0) { | |
| x1 = cxmin; | |
| } else { | |
| x1 = cxmax; | |
| } | |
| xsteps = x1 - ucX1; | |
| if (xsteps < 0) { | |
| xsteps = -xsteps; | |
| } | |
| ysteps = 2 * xsteps * ay + ax; | |
| if (!xmajor) { | |
| ysteps += ax - ay - 1; | |
| } | |
| ysteps = ysteps / (2 * ax); | |
| if (dy < 0) { | |
| ysteps = -ysteps; | |
| } | |
| y1 = ucY1 + (int) ysteps; | |
| } | |
| outcode1 = outcode(x1, y1, cxmin, cymin, cxmax, cymax); | |
| } else { | |
| if ((outcode2 & (OUTCODE_TOP | OUTCODE_BOTTOM)) != 0) { | |
| if ((outcode2 & OUTCODE_TOP) != 0) { | |
| y2 = cymin; | |
| } else { | |
| y2 = cymax; | |
| } | |
| ysteps = y2 - ucY2; | |
| if (ysteps < 0) { | |
| ysteps = -ysteps; | |
| } | |
| xsteps = 2 * ysteps * ax + ay; | |
| if (xmajor) { | |
| xsteps += ay - ax; | |
| } else { | |
| xsteps -= 1; | |
| } | |
| xsteps = xsteps / (2 * ay); | |
| if (dx > 0) { | |
| xsteps = -xsteps; | |
| } | |
| x2 = ucX2 + (int) xsteps; | |
| } else if ((outcode2 & (OUTCODE_LEFT | OUTCODE_RIGHT)) != 0) { | |
| if ((outcode2 & OUTCODE_LEFT) != 0) { | |
| x2 = cxmin; | |
| } else { | |
| x2 = cxmax; | |
| } | |
| xsteps = x2 - ucX2; | |
| if (xsteps < 0) { | |
| xsteps = -xsteps; | |
| } | |
| ysteps = 2 * xsteps * ay + ax; | |
| if (xmajor) { | |
| ysteps -= 1; | |
| } else { | |
| ysteps += ax - ay; | |
| } | |
| ysteps = ysteps / (2 * ax); | |
| if (dy > 0) { | |
| ysteps = -ysteps; | |
| } | |
| y2 = ucY2 + (int) ysteps; | |
| } | |
| outcode2 = outcode(x2, y2, cxmin, cymin, cxmax, cymax); | |
| } | |
| } | |
| return true; | |
| } | |
| private void initCoordinates(int x1, int y1, int x2, int y2, | |
| boolean checkOverflow) { | |
| /* | |
| * Part of calculating the Bresenham parameters for line stepping | |
| * involves being able to store numbers that are twice the magnitude of | |
| * the biggest absolute difference in coordinates. Since we want the | |
| * stepping parameters to be stored in jints, we then need to avoid any | |
| * absolute differences more than 30 bits. Thus, we need to preprocess | |
| * the coordinates to reduce their range to 30 bits regardless of | |
| * clipping. We need to cut their range back before we do the clipping | |
| * because the Bresenham stepping values need to be calculated based on | |
| * the "unclipped" coordinates. | |
| * | |
| * Thus, first we perform a "pre-clipping" stage to bring the | |
| * coordinates within the 30-bit range and then we proceed to the | |
| * regular clipping procedure, pretending that these were the original | |
| * coordinates all along. Since this operation occurs based on a | |
| * constant "pre-clip" rectangle of +/- 30 bits without any | |
| * consideration for the final clip, the rounding errors that occur here | |
| * will depend only on the line coordinates and be invariant with | |
| * respect to the particular device/user clip rectangles in effect at | |
| * the time. Thus, rendering a given large-range line will be consistent | |
| * under a variety of clipping conditions. | |
| */ | |
| if (checkOverflow | |
| && (OverflowsBig(x1) || OverflowsBig(y1) || OverflowsBig(x2) || OverflowsBig(y2))) { | |
| /* | |
| * Use doubles to get us into range for "Big" arithmetic. | |
| * | |
| * The math of adjusting an endpoint for clipping can involve an | |
| * intermediate result with twice the number of bits as the original | |
| * coordinate range. Since we want to maintain as much as 30 bits of | |
| * precision in the resulting coordinates, we will get roundoff here | |
| * even using IEEE double-precision arithmetic which cannot carry 60 | |
| * bits of mantissa. Since the rounding errors will be consistent | |
| * for a given set of input coordinates the potential roundoff error | |
| * should not affect the consistency of our rendering. | |
| */ | |
| double x1d = x1; | |
| double y1d = y1; | |
| double x2d = x2; | |
| double y2d = y2; | |
| double dxd = x2d - x1d; | |
| double dyd = y2d - y1d; | |
| if (x1 < BIG_MIN) { | |
| y1d = y1 + (BIG_MIN - x1) * dyd / dxd; | |
| x1d = BIG_MIN; | |
| } else if (x1 > BIG_MAX) { | |
| y1d = y1 - (x1 - BIG_MAX) * dyd / dxd; | |
| x1d = BIG_MAX; | |
| } | |
| /* Use Y1d instead of _y1 for testing now as we may have modified it */ | |
| if (y1d < BIG_MIN) { | |
| x1d = x1 + (BIG_MIN - y1) * dxd / dyd; | |
| y1d = BIG_MIN; | |
| } else if (y1d > BIG_MAX) { | |
| x1d = x1 - (y1 - BIG_MAX) * dxd / dyd; | |
| y1d = BIG_MAX; | |
| } | |
| if (x2 < BIG_MIN) { | |
| y2d = y2 + (BIG_MIN - x2) * dyd / dxd; | |
| x2d = BIG_MIN; | |
| } else if (x2 > BIG_MAX) { | |
| y2d = y2 - (x2 - BIG_MAX) * dyd / dxd; | |
| x2d = BIG_MAX; | |
| } | |
| /* Use Y2d instead of _y2 for testing now as we may have modified it */ | |
| if (y2d < BIG_MIN) { | |
| x2d = x2 + (BIG_MIN - y2) * dxd / dyd; | |
| y2d = BIG_MIN; | |
| } else if (y2d > BIG_MAX) { | |
| x2d = x2 - (y2 - BIG_MAX) * dxd / dyd; | |
| y2d = BIG_MAX; | |
| } | |
| x1 = (int) x1d; | |
| y1 = (int) y1d; | |
| x2 = (int) x2d; | |
| y2 = (int) y2d; | |
| } | |
| this.x1 = ucX1 = x1; | |
| this.y1 = ucY1 = y1; | |
| this.x2 = ucX2 = x2; | |
| this.y2 = ucY2 = y2; | |
| } | |
| private boolean OverflowsBig(int v) { | |
| return ((v) != (((v) << 2) >> 2)); | |
| } | |
| private int out(int v, int vmin, int vmax, int cmin, int cmax) { | |
| return ((v < vmin) ? cmin : ((v > vmax) ? cmax : 0)); | |
| } | |
| private int outcode(int x, int y, int xmin, int ymin, int xmax, int ymax) { | |
| return out(y, ymin, ymax, OUTCODE_TOP, OUTCODE_BOTTOM) | |
| | out(x, xmin, xmax, OUTCODE_LEFT, OUTCODE_RIGHT); | |
| } | |
| } |