| /* |
| * 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 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) { |
| int 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 + 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 + 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 + 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 + 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); |
| } |
| } |