2 * Copyright © 2016 Keith Packard <keithp@keithp.com>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
16 #include <ao_draw_int.h>
18 #define ao_mask(x,w) (ao_right(AO_ALLONES,(x) & AO_MASK) & \
19 ao_left(AO_ALLONES,(FB_UNIT - ((x)+(w))) & AO_MASK))
22 /* out of clip region codes */
24 #define OUT_RIGHT 0x04
25 #define OUT_ABOVE 0x02
26 #define OUT_BELOW 0x01
28 /* major axis for bresenham's line */
33 * Line clipping. Clip to the box, bringing the coordinates forward while
34 * preserving the actual slope and error
37 * X major line, clip X:
43 * adjust_y = (e + -e3-1) / -e3;
45 * e -= adjust_y / -e3;
47 * X major line, clip Y:
52 * e -= adjust_y / -e3;
62 ao_bres(const struct ao_bitmap *dst_bitmap,
75 int16_t stride = dst_bitmap->stride;
76 uint32_t *dst = dst_bitmap->base;
81 mask0 = ao_right(1, AO_UNIT - 1);
83 dst = dst + y1 * stride + (x1 >> AO_SHIFT);
84 mask = ao_right(1, x1 & AO_MASK);
93 if (x1 < 0 || dst_bitmap->width <= x1) {
94 printf("bad line x %d\n", x1);
97 if (y1 < 0 || dst_bitmap->height <= y1) {
98 printf("bad line y %d\n", y1);
102 *dst = ao_do_mask_rrop(*dst, and, xor, mask);
104 if (axis == X_AXIS) {
109 mask = ao_left(mask, 1);
111 mask = ao_right(mask, 1);
135 mask = ao_left(mask, 1);
137 mask = ao_right(mask, 1);
159 /* line clipping box */
165 /* -b <= a, so we need to make a bigger */
167 div_ceil(int32_t a, int16_t b) {
168 return (int16_t) ((a + b + b - 1) / b - 1);
172 div_floor_plus_one(int32_t a, int16_t b) {
173 return (int16_t) ((a + b) / b);
177 ao_clip_line(struct ao_cc *c, struct ao_cbox *b)
179 int32_t adjust_major = 0, adjust_minor = 0;
181 /* Clip major axis */
182 if (c->major < b->maj1) {
183 if (c->sign_major <= 0)
185 adjust_major = b->maj1 - c->major;
186 } else if (c->major >= b->maj2) {
187 if (c->sign_major >= 0)
189 adjust_major = c->major - (b->maj2-1);
192 /* Clip minor axis */
193 if (c->minor < b->min1) {
194 if (c->sign_minor <= 0)
196 adjust_minor = b->min1 - c->minor;
197 } else if (c->minor >= b->min2) {
198 if (c->sign_minor >= 0)
200 adjust_minor = c->minor - (b->min2-1);
203 /* If unclipped, we're done */
204 if (adjust_major == 0 && adjust_minor == 0)
207 /* See how much minor adjustment would happen during
208 * a major clip. This is a bit tricky because line drawing
209 * isn't symmetrical when the line passes exactly between
210 * two pixels, we have to pick which one gets drawn
216 adj_min = div_ceil(c->e + adjust_major * c->e1, -c->e3);
218 adj_min = div_floor_plus_one(c->e + adjust_major * c->e1, -c->e3);
220 if (adj_min < adjust_minor) {
223 adjust_major = div_ceil(c->e - adjust_minor * c->e3, c->e1);
225 adjust_major = div_floor_plus_one(c->e - adjust_minor * c->e3, c->e1);
228 adjust_minor = adj_min;
231 c->e = (int16_t) (c->e + adjust_major * c->e1 + adjust_minor * c->e3);
233 c->major = (int16_t) (c->major + c->sign_major * adjust_major);
234 c->minor = (int16_t) (c->minor + c->sign_minor * adjust_minor);
236 c->first = true; /* signal to extend len */
241 ao_line(struct ao_bitmap *dst,
250 int16_t e, e1, e2, e3;
251 int16_t signdx = 1, signdy = 1;
254 struct ao_cc clip_1, clip_2;
257 if ((adx = x2 - x1) < 0) {
261 if ((ady = y2 - y1) < 0) {
269 e2 = e1 - (int16_t) (adx << 1);
276 clip_1.sign_major = signdx;
277 clip_1.sign_minor = signdy;
280 cbox.maj2 = dst->width;
282 cbox.min2 = dst->height;
286 e2 = e1 - (int16_t) (ady << 1);
293 clip_1.sign_major = signdy;
294 clip_1.sign_minor = signdx;
297 cbox.maj2 = dst->height;
299 cbox.min2 = dst->width;
306 clip_2.first = false;
307 clip_2.e = clip_1.e = e;
308 clip_2.e1 = clip_1.e1 = e1;
309 clip_2.e3 = clip_1.e3 = e3;
310 clip_2.sign_major = -clip_1.sign_major;
311 clip_2.sign_minor = -clip_1.sign_minor;
313 if (!ao_clip_line(&clip_1, &cbox))
316 if (!ao_clip_line(&clip_2, &cbox))
319 len = (int16_t) (clip_1.sign_major * (clip_2.major - clip_1.major) + clip_2.first);
336 ao_damage(dst, ao_min16(x1, x2), ao_max16(x1, x2), ao_min16(y1, y2), ao_max16(y1, y2));
344 clip_1.e, e1, e3, len,