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.
17 #include "ao_draw_int.h"
19 #define ao_mask(x,w) (ao_right(AO_ALLONES,(x) & AO_MASK) & \
20 ao_left(AO_ALLONES,(FB_UNIT - ((x)+(w))) & AO_MASK))
23 /* out of clip region codes */
25 #define OUT_RIGHT 0x04
26 #define OUT_ABOVE 0x02
27 #define OUT_BELOW 0x01
29 /* major axis for bresenham's line */
34 * Line clipping. Clip to the box, bringing the coordinates forward while
35 * preserving the actual slope and error
38 * X major line, clip X:
44 * adjust_y = (e + -e3-1) / -e3;
46 * e -= adjust_y / -e3;
48 * X major line, clip Y:
53 * 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);
86 dst = dst + y1 * stride + (x1 >> AO_SHIFT);
87 mask = ao_right(1, x1 & AO_MASK);
92 *dst = ao_do_mask_rrop(*dst, and, xor, mask);
96 mask = ao_left(mask, 1);
98 mask = ao_right(mask, 1);
113 mask = ao_left(mask, 1);
115 mask = ao_right(mask, 1);
137 /* line clipping box */
143 /* -b <= a, so we need to make a bigger */
145 div_ceil(int32_t a, int16_t b) {
146 return (a + b + b - 1) / b - 1;
150 div_floor_plus_one(int32_t a, int16_t b) {
155 ao_clip_line(struct ao_cc *c, struct ao_cbox *b)
157 int32_t adjust_major = 0, adjust_minor = 0;
159 /* Clip major axis */
160 if (c->major < b->maj1) {
161 if (c->sign_major <= 0)
163 adjust_major = b->maj1 - c->major;
164 } else if (c->major >= b->maj2) {
165 if (c->sign_major >= 0)
167 adjust_major = c->major - (b->maj2-1);
170 /* Clip minor axis */
171 if (c->minor < b->min1) {
172 if (c->sign_minor <= 0)
174 adjust_minor = b->min1 - c->minor;
175 } else if (c->minor >= b->min2) {
176 if (c->sign_minor >= 0)
178 adjust_minor = c->minor - (b->min2-1);
181 /* If unclipped, we're done */
182 if (adjust_major == 0 && adjust_minor == 0)
185 /* See how much minor adjustment would happen during
186 * a major clip. This is a bit tricky because line drawing
187 * isn't symmetrical when the line passes exactly between
188 * two pixels, we have to pick which one gets drawn
193 adj_min = div_ceil(c->e + adjust_major * c->e1, -c->e3);
195 adj_min = div_floor_plus_one(c->e + adjust_major * c->e1, -c->e3);
197 if (adj_min < adjust_minor) {
199 adjust_major = div_ceil(c->e - adjust_minor * c->e3, c->e1);
201 adjust_major = div_floor_plus_one(c->e - adjust_minor * c->e3, c->e1);
203 adjust_minor = adj_min;
206 c->e += adjust_major * c->e1 + adjust_minor * c->e3;
208 c->major += c->sign_major * adjust_major;
209 c->minor += c->sign_minor * adjust_minor;
215 ao_line(const struct ao_bitmap *dst,
224 int16_t e, e1, e2, e3;
225 int16_t signdx = 1, signdy = 1;
228 struct ao_cc clip_1, clip_2;
231 if ((adx = x2 - x1) < 0) {
235 if ((ady = y2 - y1) < 0) {
243 e2 = e1 - (adx << 1);
250 clip_1.sign_major = signdx;
251 clip_1.sign_minor = signdy;
254 cbox.maj2 = dst->width;
256 cbox.min2 = dst->height;
260 e2 = e1 - (ady << 1);
267 clip_1.sign_major = signdy;
268 clip_1.sign_minor = signdx;
271 cbox.maj2 = dst->height;
273 cbox.min2 = dst->width;
280 clip_2.first = false;
281 clip_2.e = clip_1.e = e;
282 clip_2.e1 = clip_1.e1 = e1;
283 clip_2.e3 = clip_1.e3 = e3;
284 clip_2.sign_major = -clip_1.sign_major;
285 clip_2.sign_minor = -clip_1.sign_minor;
287 if (!ao_clip_line(&clip_1, &cbox))
290 if (!ao_clip_line(&clip_2, &cbox))
293 len = clip_1.sign_major * (clip_2.major - clip_1.major) + clip_2.first;
311 clip_1.e, e1, e3, len,