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;
61 ao_bres(const struct ao_bitmap *dst_bitmap,
74 int16_t stride = dst_bitmap->stride;
75 uint32_t *dst = dst_bitmap->base;
80 mask0 = ao_right(1, AO_UNIT - 1);
82 dst = dst + y1 * stride + (x1 >> AO_SHIFT);
83 mask = ao_right(1, x1 & AO_MASK);
91 *dst = ao_do_mask_rrop(*dst, and, xor, mask);
95 mask = ao_left(mask, 1);
97 mask = ao_right(mask, 1);
112 mask = ao_left(mask, 1);
114 mask = ao_right(mask, 1);
136 /* line clipping box */
142 /* -b <= a, so we need to make a bigger */
144 div_ceil(int32_t a, int16_t b) {
145 return (a + b + b - 1) / b - 1;
149 div_floor_plus_one(int32_t a, int16_t b) {
154 ao_clip_line(struct ao_cc *c, struct ao_cbox *b)
156 int32_t adjust_major = 0, adjust_minor = 0;
158 /* Clip major axis */
159 if (c->major < b->maj1) {
160 if (c->sign_major <= 0)
162 adjust_major = b->maj1 - c->major;
163 } else if (c->major >= b->maj2) {
164 if (c->sign_major >= 0)
166 adjust_major = c->major - (b->maj2-1);
169 /* Clip minor axis */
170 if (c->minor < b->min1) {
171 if (c->sign_minor <= 0)
173 adjust_minor = b->min1 - c->minor;
174 } else if (c->minor >= b->min2) {
175 if (c->sign_minor >= 0)
177 adjust_minor = c->minor - (b->min2-1);
180 /* If unclipped, we're done */
181 if (adjust_major == 0 && adjust_minor == 0)
184 /* See how much minor adjustment would happen during
185 * a major clip. This is a bit tricky because line drawing
186 * isn't symmetrical when the line passes exactly between
187 * two pixels, we have to pick which one gets drawn
192 adj_min = div_ceil(c->e + adjust_major * c->e1, -c->e3);
194 adj_min = div_floor_plus_one(c->e + adjust_major * c->e1, -c->e3);
196 if (adj_min < adjust_minor) {
198 adjust_major = div_ceil(c->e - adjust_minor * c->e3, c->e1);
200 adjust_major = div_floor_plus_one(c->e - adjust_minor * c->e3, c->e1);
202 adjust_minor = adj_min;
205 c->e += adjust_major * c->e1 + adjust_minor * c->e3;
207 c->major += c->sign_major * adjust_major;
208 c->minor += c->sign_minor * adjust_minor;
214 ao_line(const struct ao_bitmap *dst,
223 int16_t e, e1, e2, e3;
224 int16_t signdx = 1, signdy = 1;
227 struct ao_cc clip_1, clip_2;
230 if ((adx = x2 - x1) < 0) {
234 if ((ady = y2 - y1) < 0) {
242 e2 = e1 - (adx << 1);
249 clip_1.sign_major = signdx;
250 clip_1.sign_minor = signdy;
253 cbox.maj2 = dst->width;
255 cbox.min2 = dst->height;
259 e2 = e1 - (ady << 1);
266 clip_1.sign_major = signdy;
267 clip_1.sign_minor = signdx;
270 cbox.maj2 = dst->height;
272 cbox.min2 = dst->width;
279 clip_2.first = false;
280 clip_2.e = clip_1.e = e;
281 clip_2.e1 = clip_1.e1 = e1;
282 clip_2.e3 = clip_1.e3 = e3;
283 clip_2.sign_major = -clip_1.sign_major;
284 clip_2.sign_minor = -clip_1.sign_minor;
286 if (!ao_clip_line(&clip_1, &cbox))
289 if (!ao_clip_line(&clip_2, &cbox))
292 len = clip_1.sign_major * (clip_2.major - clip_1.major) + clip_2.first;
310 clip_1.e, e1, e3, len,