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 }