/*
 * Copyright (c) 2013, 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
/** * 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) { 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); } }