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