1 /*
   2  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
   3 
   4 
   5  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   6  *
   7  * This code is free software; you can redistribute it and/or modify it
   8  * under the terms of the GNU General Public License version 2 only, as
   9  * published by the Free Software Foundation.  Oracle designates this
  10  * particular file as subject to the "Classpath" exception as provided
  11  * by Oracle in the LICENSE file that accompanied this code.
  12  *
  13  * This code is distributed in the hope that it will be useful, but WITHOUT
  14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16  * version 2 for more details (a copy is included in the LICENSE file that
  17  * accompanied this code).
  18  *
  19  * You should have received a copy of the GNU General Public License version
  20  * 2 along with this work; if not, write to the Free Software Foundation,
  21  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  22  *
  23  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  24  * or visit www.oracle.com if you need additional information or have any
  25  * questions.
  26  */
  27 
  28 /**
  29  * Bresenham line-drawing implementation decomposing line segments 
  30  * into a series of rectangles.
  31  * This is required, because xrender doesn't support line primitives directly.
  32  * The code here is an almost 1:1 port of the existing C-source contained in
  33  * sun/java2d/loop/DrawLine.c and sun/java2d/loop/LoopMacros.h
  34  */
  35 package sun.java2d.xr;
  36 
  37 public class XRDrawLine {
  38     static final int BIG_MAX = ((1 << 29) - 1);
  39     static final int BIG_MIN = (-(1 << 29));
  40 
  41     static final int OUTCODE_TOP = 1;
  42     static final int OUTCODE_BOTTOM = 2;
  43     static final int OUTCODE_LEFT = 4;
  44     static final int OUTCODE_RIGHT = 8;
  45 
  46     int x1, y1, x2, y2;
  47     int ucX1, ucY1, ucX2, ucY2;
  48 
  49     DirtyRegion region = new DirtyRegion();
  50 
  51     protected void rasterizeLine(GrowableRectArray rectBuffer, int _x1,
  52             int _y1, int _x2, int _y2, int cxmin, int cymin, int cxmax,
  53             int cymax, boolean clip, boolean overflowCheck) {
  54         float diagF;
  55         int error;
  56         int steps;
  57         int errminor, errmajor;
  58         boolean xmajor;
  59         int dx, dy, ax, ay;
  60 
  61         initCoordinates(_x1, _y1, _x2, _y2, overflowCheck);
  62 
  63         dx = x2 - x1;
  64         dy = y2 - y1;
  65         ax = Math.abs(dx);
  66         ay = Math.abs(dy);
  67         xmajor = (ax >= ay);
  68         diagF = ((float) ax) / ay;
  69 
  70         if (clip
  71                 && !clipCoordinates(cxmin, cymin, cxmax, cymax, xmajor, dx, dy,
  72                         ax, ay)) {
  73             // whole line was clipped away
  74             return;
  75         }
  76 
  77         region.setDirtyLineRegion(x1, y1, x2, y2);
  78         int xDiff = region.x2 - region.x;
  79         int yDiff = region.y2 - region.y;
  80 
  81         if (xDiff == 0 || yDiff == 0) {
  82             // horizontal / diagonal lines can be represented by a single
  83             // rectangle
  84             rectBuffer.pushRectValues(region.x, region.y, region.x2 - region.x
  85                     + 1, region.y2 - region.y + 1);
  86             return;
  87         }
  88 
  89         // Setup bresenham
  90         if (xmajor) {
  91             errmajor = ay * 2;
  92             errminor = ax * 2;
  93             ax = -ax; /* For clipping adjustment below */
  94             steps = x2 - x1;
  95         } else {
  96             errmajor = ax * 2;
  97             errminor = ay * 2;
  98             ay = -ay; /* For clipping adjustment below */
  99             steps = y2 - y1;
 100         }
 101 
 102         if ((steps = (Math.abs(steps) + 1)) == 0) {
 103             return;
 104         }
 105 
 106         error = -(errminor / 2);
 107 
 108         if (y1 != ucY1) {
 109             int ysteps = y1 - ucY1;
 110             if (ysteps < 0) {
 111                 ysteps = -ysteps;
 112             }
 113             error += ysteps * ax * 2;
 114         }
 115 
 116         if (x1 != ucX1) {
 117             int xsteps = x1 - ucX1;
 118             if (xsteps < 0) {
 119                 xsteps = -xsteps;
 120             }
 121             error += xsteps * ay * 2;
 122         }
 123         error += errmajor;
 124         errminor -= errmajor;
 125 
 126         int xStep = (dx > 0 ? 1 : -1);
 127         int yStep = (dy > 0 ? 1 : -1);
 128         int orthogonalXStep = xmajor ? xStep : 0;
 129         int orthogonalYStep = !xmajor ? yStep : 0;
 130 
 131         /*
 132          * For lines which proceed in one direction faster, we try to generate
 133          * rectangles instead of points. Otherwise we try to avoid the extra
 134          * work...
 135          */
 136         if (diagF <= 0.9 || diagF >= 1.1) {
 137             lineToRects(rectBuffer, steps, error, errmajor, errminor, xStep,
 138                     yStep, orthogonalXStep, orthogonalYStep);
 139         } else {
 140             lineToPoints(rectBuffer, steps, error, errmajor, errminor, xStep,
 141                     yStep, orthogonalXStep, orthogonalYStep);
 142         }
 143     }
 144 
 145     private void lineToPoints(GrowableRectArray rectBuffer, int steps,
 146             int error, int errmajor, int errminor, int xStep, int yStep,
 147             int orthogonalXStep, int orthogonalYStep) {
 148         int x = x1, y = y1;
 149 
 150         do {
 151             rectBuffer.pushRectValues(x, y, 1, 1);
 152 
 153             // "Traditional" Bresenham line drawing
 154             if (error < 0) {
 155                 error += errmajor;
 156                 x += orthogonalXStep;
 157                 y += orthogonalYStep;
 158             } else {
 159                 error -= errminor;
 160                 x += xStep;
 161                 y += yStep;
 162             }
 163         } while (--steps > 0);
 164     }
 165 
 166     private void lineToRects(GrowableRectArray rectBuffer, int steps,
 167             int error, int errmajor, int errminor, int xStep, int yStep,
 168             int orthogonalXStep, int orthogonalYStep) {
 169         int x = x1, y = y1;
 170         int rectX = Integer.MIN_VALUE, rectY = 0;
 171         int rectW = 0, rectH = 0;
 172 
 173         do {
 174             // Combine the resulting rectangles
 175             // for steps performed in a single direction.
 176             if (y == rectY) {
 177                 if (x == (rectX + rectW)) {
 178                     rectW++;
 179                 } else if (x == (rectX - 1)) {
 180                     rectX--;
 181                     rectW++;
 182                 }
 183             } else if (x == rectX) {
 184                 if (y == (rectY + rectH)) {
 185                     rectH++;
 186                 } else if (y == (rectY - 1)) {
 187                     rectY--;
 188                     rectH++;
 189                 }
 190             } else {
 191                 // Diagonal step: add the previous rectangle to the list,
 192                 // iff it was "real" (= not initialized before the first
 193                 // iteration)
 194                 if (rectX != Integer.MIN_VALUE) {
 195                     rectBuffer.pushRectValues(rectX, rectY, rectW, rectH);
 196                 }
 197                 rectX = x;
 198                 rectY = y;
 199                 rectW = rectH = 1;
 200             }
 201 
 202             // "Traditional" Bresenham line drawing
 203             if (error < 0) {
 204                 error += errmajor;
 205                 x += orthogonalXStep;
 206                 y += orthogonalYStep;
 207             } else {
 208                 error -= errminor;
 209                 x += xStep;
 210                 y += yStep;
 211             }
 212         } while (--steps > 0);
 213 
 214         // Add last rectangle which isn't handled by the combination-code
 215         // anymore
 216         rectBuffer.pushRectValues(rectX, rectY, rectW, rectH);
 217     }
 218 
 219     private boolean clipCoordinates(int cxmin, int cymin, int cxmax, int cymax,
 220             boolean xmajor, int dx, int dy, int ax, int ay) {
 221         int outcode1, outcode2;
 222 
 223         outcode1 = outcode(x1, y1, cxmin, cymin, cxmax, cymax);
 224         outcode2 = outcode(x2, y2, cxmin, cymin, cxmax, cymax);
 225 
 226         while ((outcode1 | outcode2) != 0) {
 227             int xsteps = 0, ysteps = 0;
 228 
 229             if ((outcode1 & outcode2) != 0) {
 230                 return false;
 231             }
 232 
 233             if (outcode1 != 0) {
 234                 if ((outcode1 & (OUTCODE_TOP | OUTCODE_BOTTOM)) != 0) {
 235                     if ((outcode1 & OUTCODE_TOP) != 0) {
 236                         y1 = cymin;
 237                     } else {
 238                         y1 = cymax;
 239                     }
 240                     ysteps = y1 - ucY1;
 241                     if (ysteps < 0) {
 242                         ysteps = -ysteps;
 243                     }
 244                     xsteps = 2 * ysteps * ax + ay;
 245                     if (xmajor) {
 246                         xsteps += ay - ax - 1;
 247                     }
 248                     xsteps = xsteps / (2 * ay);
 249                     if (dx < 0) {
 250                         xsteps = -xsteps;
 251                     }
 252                     x1 = ucX1 + (int) xsteps;
 253                 } else if ((outcode1 & (OUTCODE_LEFT | OUTCODE_RIGHT)) != 0) {
 254                     if ((outcode1 & OUTCODE_LEFT) != 0) {
 255                         x1 = cxmin;
 256                     } else {
 257                         x1 = cxmax;
 258                     }
 259                     xsteps = x1 - ucX1;
 260                     if (xsteps < 0) {
 261                         xsteps = -xsteps;
 262                     }
 263                     ysteps = 2 * xsteps * ay + ax;
 264                     if (!xmajor) {
 265                         ysteps += ax - ay - 1;
 266                     }
 267                     ysteps = ysteps / (2 * ax);
 268                     if (dy < 0) {
 269                         ysteps = -ysteps;
 270                     }
 271                     y1 = ucY1 + (int) ysteps;
 272                 }
 273                 outcode1 = outcode(x1, y1, cxmin, cymin, cxmax, cymax);
 274             } else {
 275                 if ((outcode2 & (OUTCODE_TOP | OUTCODE_BOTTOM)) != 0) {
 276                     if ((outcode2 & OUTCODE_TOP) != 0) {
 277                         y2 = cymin;
 278                     } else {
 279                         y2 = cymax;
 280                     }
 281                     ysteps = y2 - ucY2;
 282                     if (ysteps < 0) {
 283                         ysteps = -ysteps;
 284                     }
 285                     xsteps = 2 * ysteps * ax + ay;
 286                     if (xmajor) {
 287                         xsteps += ay - ax;
 288                     } else {
 289                         xsteps -= 1;
 290                     }
 291                     xsteps = xsteps / (2 * ay);
 292                     if (dx > 0) {
 293                         xsteps = -xsteps;
 294                     }
 295                     x2 = ucX2 + (int) xsteps;
 296                 } else if ((outcode2 & (OUTCODE_LEFT | OUTCODE_RIGHT)) != 0) {
 297                     if ((outcode2 & OUTCODE_LEFT) != 0) {
 298                         x2 = cxmin;
 299                     } else {
 300                         x2 = cxmax;
 301                     }
 302                     xsteps = x2 - ucX2;
 303                     if (xsteps < 0) {
 304                         xsteps = -xsteps;
 305                     }
 306                     ysteps = 2 * xsteps * ay + ax;
 307                     if (xmajor) {
 308                         ysteps -= 1;
 309                     } else {
 310                         ysteps += ax - ay;
 311                     }
 312                     ysteps = ysteps / (2 * ax);
 313                     if (dy > 0) {
 314                         ysteps = -ysteps;
 315                     }
 316                     y2 = ucY2 + (int) ysteps;
 317                 }
 318                 outcode2 = outcode(x2, y2, cxmin, cymin, cxmax, cymax);
 319             }
 320         }
 321 
 322         return true;
 323     }
 324 
 325     private void initCoordinates(int x1, int y1, int x2, int y2,
 326             boolean checkOverflow) {
 327         /*
 328          * Part of calculating the Bresenham parameters for line stepping
 329          * involves being able to store numbers that are twice the magnitude of
 330          * the biggest absolute difference in coordinates. Since we want the
 331          * stepping parameters to be stored in jints, we then need to avoid any
 332          * absolute differences more than 30 bits. Thus, we need to preprocess
 333          * the coordinates to reduce their range to 30 bits regardless of
 334          * clipping. We need to cut their range back before we do the clipping
 335          * because the Bresenham stepping values need to be calculated based on
 336          * the "unclipped" coordinates.
 337          * 
 338          * Thus, first we perform a "pre-clipping" stage to bring the
 339          * coordinates within the 30-bit range and then we proceed to the
 340          * regular clipping procedure, pretending that these were the original
 341          * coordinates all along. Since this operation occurs based on a
 342          * constant "pre-clip" rectangle of +/- 30 bits without any
 343          * consideration for the final clip, the rounding errors that occur here
 344          * will depend only on the line coordinates and be invariant with
 345          * respect to the particular device/user clip rectangles in effect at
 346          * the time. Thus, rendering a given large-range line will be consistent
 347          * under a variety of clipping conditions.
 348          */
 349         if (checkOverflow
 350                 && (OverflowsBig(x1) || OverflowsBig(y1) || OverflowsBig(x2) || OverflowsBig(y2))) {
 351             /*
 352              * Use doubles to get us into range for "Big" arithmetic.
 353              * 
 354              * The math of adjusting an endpoint for clipping can involve an
 355              * intermediate result with twice the number of bits as the original
 356              * coordinate range. Since we want to maintain as much as 30 bits of
 357              * precision in the resulting coordinates, we will get roundoff here
 358              * even using IEEE double-precision arithmetic which cannot carry 60
 359              * bits of mantissa. Since the rounding errors will be consistent
 360              * for a given set of input coordinates the potential roundoff error
 361              * should not affect the consistency of our rendering.
 362              */
 363             double x1d = x1;
 364             double y1d = y1;
 365             double x2d = x2;
 366             double y2d = y2;
 367             double dxd = x2d - x1d;
 368             double dyd = y2d - y1d;
 369 
 370             if (x1 < BIG_MIN) {
 371                 y1d = y1 + (BIG_MIN - x1) * dyd / dxd;
 372                 x1d = BIG_MIN;
 373             } else if (x1 > BIG_MAX) {
 374                 y1d = y1 - (x1 - BIG_MAX) * dyd / dxd;
 375                 x1d = BIG_MAX;
 376             }
 377             /* Use Y1d instead of _y1 for testing now as we may have modified it */
 378             if (y1d < BIG_MIN) {
 379                 x1d = x1 + (BIG_MIN - y1) * dxd / dyd;
 380                 y1d = BIG_MIN;
 381             } else if (y1d > BIG_MAX) {
 382                 x1d = x1 - (y1 - BIG_MAX) * dxd / dyd;
 383                 y1d = BIG_MAX;
 384             }
 385             if (x2 < BIG_MIN) {
 386                 y2d = y2 + (BIG_MIN - x2) * dyd / dxd;
 387                 x2d = BIG_MIN;
 388             } else if (x2 > BIG_MAX) {
 389                 y2d = y2 - (x2 - BIG_MAX) * dyd / dxd;
 390                 x2d = BIG_MAX;
 391             }
 392             /* Use Y2d instead of _y2 for testing now as we may have modified it */
 393             if (y2d < BIG_MIN) {
 394                 x2d = x2 + (BIG_MIN - y2) * dxd / dyd;
 395                 y2d = BIG_MIN;
 396             } else if (y2d > BIG_MAX) {
 397                 x2d = x2 - (y2 - BIG_MAX) * dxd / dyd;
 398                 y2d = BIG_MAX;
 399             }
 400 
 401             x1 = (int) x1d;
 402             y1 = (int) y1d;
 403             x2 = (int) x2d;
 404             y2 = (int) y2d;
 405         }
 406 
 407         this.x1 = ucX1 = x1;
 408         this.y1 = ucY1 = y1;
 409         this.x2 = ucX2 = x2;
 410         this.y2 = ucY2 = y2;
 411     }
 412 
 413     private boolean OverflowsBig(int v) {
 414         return ((v) != (((v) << 2) >> 2));
 415     }
 416 
 417     private int out(int v, int vmin, int vmax, int cmin, int cmax) {
 418         return ((v < vmin) ? cmin : ((v > vmax) ? cmax : 0));
 419     }
 420 
 421     private int outcode(int x, int y, int xmin, int ymin, int xmax, int ymax) {
 422         return out(y, ymin, ymax, OUTCODE_TOP, OUTCODE_BOTTOM)
 423                 | out(x, xmin, xmax, OUTCODE_LEFT, OUTCODE_RIGHT);
 424     }
 425 }