1const ONE: i64 = 65536;
3const SLOPE: [i64; 32] = [
4 181, 181, 181, 182, 182, 183, 184, 185, 187, 188, 190, 192, 194, 196, 198, 201, 203, 206, 209,
5 211, 214, 218, 221, 224, 227, 231, 235, 238, 242, 246, 250, 254,
6];
7const FILTER: [i64; 64] = [
8 168, 177, 185, 194, 202, 210, 218, 224, 231, 236, 241, 246, 249, 252, 254, 254, 254, 254, 252,
9 249, 246, 241, 236, 231, 224, 218, 210, 202, 194, 185, 177, 168, 158, 149, 140, 131, 122, 114,
10 105, 97, 89, 82, 75, 68, 62, 56, 50, 45, 40, 36, 32, 28, 25, 22, 19, 16, 14, 12, 11, 9, 8, 7,
11 5, 5,
12];
13
14fn clip(width: i64, height: i64, mut a: [i64; 2], mut b: [i64; 2]) -> (bool, [i64; 2], [i64; 2]) {
16 let right = width - 1;
17 let bottom = height - 1;
18 let code = |p: [i64; 2]| {
19 (p[0] < 0) as i32
20 + (p[0] > right) as i32 * 2
21 + (p[1] < 0) as i32 * 4
22 + (p[1] > bottom) as i32 * 8
23 };
24 let mut c1 = code(a);
25 let mut c2 = code(b);
26 if c1 & c2 == 0 && c1 | c2 != 0 {
27 if c1 & 12 != 0 {
28 let y = if c1 < 8 { 0 } else { bottom };
29 a[0] += ((y - a[1]) as f64 * (b[0] - a[0]) as f64 / (b[1] - a[1]) as f64) as i64;
30 a[1] = y;
31 c1 = (a[0] < 0) as i32 + (a[0] > right) as i32 * 2;
32 }
33 if c2 & 12 != 0 {
34 let y = if c2 < 8 { 0 } else { bottom };
35 b[0] += ((y - b[1]) as f64 * (b[0] - a[0]) as f64 / (b[1] - a[1]) as f64) as i64;
36 b[1] = y;
37 c2 = (b[0] < 0) as i32 + (b[0] > right) as i32 * 2;
38 }
39 if c1 & c2 == 0 && c1 | c2 != 0 {
40 if c1 != 0 {
41 let x = if c1 == 1 { 0 } else { right };
42 a[1] += ((x - a[0]) as f64 * (b[1] - a[1]) as f64 / (b[0] - a[0]) as f64) as i64;
43 a[0] = x;
44 c1 = 0;
45 }
46 if c2 != 0 {
47 let x = if c2 == 1 { 0 } else { right };
48 b[1] += ((x - b[0]) as f64 * (b[1] - a[1]) as f64 / (b[0] - a[0]) as f64) as i64;
49 b[0] = x;
50 c2 = 0;
51 }
52 }
53 }
54 (c1 | c2 == 0, a, b)
55}
56
57fn line8(data: &mut [u8], width: usize, height: usize, a: [i64; 2], b: [i64; 2], value: u8) {
59 let (inside, mut a, mut b) = clip(width as i64, height as i64, a, b);
60 if !inside {
61 return;
62 }
63 if a[0] > b[0] {
64 std::mem::swap(&mut a, &mut b);
65 }
66 let dx = b[0] - a[0];
67 let dy = (b[1] - a[1]).abs();
68 let sign = if b[1] >= a[1] { 1 } else { -1 };
69 let vertical = dy > dx;
70 let (major, minor) = if vertical { (dy, dx) } else { (dx, dy) };
71 let mut error = major - 2 * minor;
72 for _ in 0..=major {
73 data[a[1] as usize * width + a[0] as usize] = value;
74 let advance = error < 0;
75 error += -2 * minor + if advance { 2 * major } else { 0 };
76 a[0] += if vertical { advance as i64 } else { 1 };
77 a[1] += if vertical {
78 sign
79 } else {
80 sign * advance as i64
81 };
82 }
83}
84
85#[allow(clippy::too_many_arguments)]
87fn line_aa(
88 data: &mut [u8],
89 width: usize,
90 height: usize,
91 channels: usize,
92 a: [i64; 2],
93 b: [i64; 2],
94 value: u8,
95) {
96 let (inside, mut a, mut b) = clip((width as i64) << 16, (height as i64) << 16, a, b);
97 if !inside {
98 return;
99 }
100 let horizontal = (b[0] - a[0]).abs() > (b[1] - a[1]).abs();
101 let major = if horizontal { 0 } else { 1 };
102 let minor = 1 - major;
103 if a[major] > b[major] {
104 std::mem::swap(&mut a, &mut b);
105 }
106 let step = ((b[minor] - a[minor]) << 16) / ((b[major] - a[major]) | 1);
107 let last = b[major] + ONE;
108 let count = (last >> 16) - (a[major] >> 16);
109 let mut coordinate = a[minor] + ((step * -(a[major] & 65535)) >> 16) + 32768;
110 let mut slope = (step >> 11) & 63;
111 if step < 0 {
112 slope ^= 63;
113 }
114 slope = if slope & 32 != 0 {
115 256
116 } else {
117 SLOPE[slope as usize]
118 };
119 let i = (a[major] >> 9) & 120;
120 let j = (last >> 9) & 120;
121 let t0 = slope << 7;
122 let t1 = ((120 - i) | 4) * slope;
123 let t2 = (j | 4) * slope;
124 let ep = [
125 0,
126 (((((j - i) & 120) | 4) * slope) >> 8) & 511,
127 (t1 >> 8) & 511,
128 (((((j - i) & 120) | 4) * slope) >> 8) & 511,
129 (((((j - i) + 128) | 4) * slope) >> 8) & 511,
130 ((t1 + t0) >> 8) & 511,
131 (t2 >> 8) & 511,
132 ((t2 + t0) >> 8) & 511,
133 slope,
134 ];
135 for scount in 0..=count {
136 let axis = (a[major] >> 16) + scount;
137 let minor_axis = (coordinate >> 16) - 1;
138 let remaining = count - scount;
139 let correction = ep[((((scount >= 2) as i64 + 1) & (scount | 2)) * 3
140 + (((remaining >= 2) as i64 + 1) & (remaining | 2)))
141 as usize];
142 let dist = ((coordinate >> 11) & 31) as usize;
143 for (offset, weight) in [FILTER[dist + 32], FILTER[dist], FILTER[63 - dist]]
144 .iter()
145 .enumerate()
146 {
147 let (x, y) = if horizontal {
148 (axis, minor_axis + offset as i64)
149 } else {
150 (minor_axis + offset as i64, axis)
151 };
152 if x >= 0 && y >= 0 && x < width as i64 && y < height as i64 {
153 let alpha = ((correction * weight) >> 8) & 255;
154 for channel in 0..channels {
155 let target = &mut data[(y as usize * width + x as usize) * channels + channel];
156 let mut v = *target as i64;
157 v += ((value as i64 - v) * alpha + 127) >> 8;
158 v += ((value as i64 - v) * alpha + 127) >> 8;
159 *target = v as u8;
160 }
161 }
162 }
163 coordinate += step;
164 }
165}
166
167fn convex_aa(
169 data: &mut [u8],
170 width: usize,
171 height: usize,
172 channels: usize,
173 points: &[[i64; 2]],
174 value: u8,
175) {
176 let n = points.len();
177 if n == 0 {
178 return;
179 }
180 for i in 0..n {
181 line_aa(
182 data,
183 width,
184 height,
185 channels,
186 points[(i + n - 1) % n],
187 points[i],
188 value,
189 );
190 }
191 let mut low = 0;
192 for i in 1..n {
193 if points[i][1] < points[low][1] {
194 low = i;
195 }
196 }
197 let ymin = (points[low][1] + 32768) >> 16;
198 let xmax = (points.iter().map(|v| v[0]).max().unwrap() + 32768) >> 16;
199 let xmin = (points.iter().map(|v| v[0]).min().unwrap() + 32768) >> 16;
200 let raw_ymax = (points.iter().map(|v| v[1]).max().unwrap() + 32768) >> 16;
201 if xmax < 0 || raw_ymax < 0 || xmin >= width as i64 || ymin >= height as i64 {
202 return;
203 }
204 let ymax = ((points.iter().map(|v| v[1]).max().unwrap() + 32768) >> 16).min(height as i64 - 1);
205 let mut edge = [
206 [low as i64, 1, -ONE, 0, ymin],
207 [low as i64, n as i64 - 1, -ONE, 0, ymin],
208 ];
209 let mut remaining = n as i64;
210 for y in ymin..=ymax {
211 if y < ymax || y == ymin {
212 for item in &mut edge {
213 if y >= item[4] {
214 let mut index0 = item[0] as usize;
215 let direction = item[1] as usize;
216 let mut index = (index0 + direction) % n;
217 loop {
218 let old = remaining;
219 remaining -= 1;
220 if old <= 0 {
221 break;
222 }
223 let ty = (points[index][1] + 32768) >> 16;
224 if ty > y {
225 let xs = points[index0][0];
226 let xe = points[index][0];
227 item[4] = ty;
228 item[3] = ((xe - xs) * 2 + ty - y) / (2 * (ty - y));
229 item[2] = xs;
230 item[0] = index as i64;
231 break;
232 }
233 index0 = index;
234 index = (index + direction) % n;
235 }
236 }
237 }
238 }
239 if remaining < 0 {
240 break;
241 }
242 if y >= 0 && y < height as i64 {
243 let left = edge[0][2].min(edge[1][2]);
244 let right = edge[0][2].max(edge[1][2]);
245 let x1 = ((left + 65535) >> 16).max(0);
246 let x2 = (right >> 16).min(width as i64 - 1);
247 if x1 <= x2 {
248 data[(y as usize * width + x1 as usize) * channels
249 ..(y as usize * width + x2 as usize + 1) * channels]
250 .fill(value);
251 }
252 }
253 for item in &mut edge {
254 item[2] += item[3];
255 }
256 }
257}
258
259pub fn lines(
261 data: &[u8],
262 width: usize,
263 height: usize,
264 channels: usize,
265 lines: &[[i32; 4]],
266 value: u8,
267 thickness: usize,
268) -> Result<Vec<u8>, String> {
269 if width
270 .checked_mul(height)
271 .and_then(|v| v.checked_mul(channels))
272 != Some(data.len())
273 || thickness == 0
274 || thickness > 1024
275 {
276 return Err("invalid line image or thickness".into());
277 }
278 let mut output = data.to_vec();
279 for line in lines {
280 let mut start = [line[0] as i64, line[1] as i64];
281 let mut end = [line[2] as i64, line[3] as i64];
282 if thickness > 1
283 && [start, end]
284 .iter()
285 .any(|p| p[0] < 0 || p[1] < 0 || p[0] >= width as i64 || p[1] >= height as i64)
286 {
287 let margin = thickness as i64;
288 let (_, a, b) = clip(
289 width as i64 + margin * 2,
290 height as i64 + margin * 2,
291 [start[0] + margin, start[1] + margin],
292 [end[0] + margin, end[1] + margin],
293 );
294 start = [a[0] - margin, a[1] - margin];
295 end = [b[0] - margin, b[1] - margin];
296 }
297 let a = [start[0] << 16, start[1] << 16];
298 let b = [end[0] << 16, end[1] << 16];
299 if thickness == 1 {
300 line_aa(&mut output, width, height, channels, a, b, value);
301 continue;
302 }
303 let dx = (start[0] - end[0]) as f64;
304 let dy = (end[1] - start[1]) as f64;
305 let length = dx.hypot(dy);
306 let radius = (thickness as i64) << 15;
307 if length > 0. {
308 let factor = (radius + ((thickness & 1) as i64) * 32768) as f64 / length;
309 let px = (dy * factor).round_ties_even() as i64;
310 let py = (dx * factor).round_ties_even() as i64;
311 let points = [
312 [a[0] + px, a[1] + py],
313 [a[0] - px, a[1] - py],
314 [b[0] - px, b[1] - py],
315 [b[0] + px, b[1] + py],
316 ];
317 convex_aa(&mut output, width, height, channels, &points, value);
318 }
319 let rounded = (radius + 32768) >> 16;
320 let delta = if rounded < 3 {
321 90
322 } else if rounded < 10 {
323 30
324 } else if rounded < 15 {
325 18
326 } else {
327 5
328 };
329 for center in [a, b] {
330 let mut points = Vec::new();
331 for angle in (0..=360).step_by(delta) {
332 let radians = (angle as f64).to_radians();
333 let x = (center[0] as f64 + radius as f64 * radians.cos() as f32 as f64)
334 .round_ties_even() as i64;
335 let y = (center[1] as f64 + radius as f64 * radians.sin() as f32 as f64)
336 .round_ties_even() as i64;
337 if points.last() != Some(&[x, y]) {
338 points.push([x, y]);
339 }
340 }
341 convex_aa(&mut output, width, height, channels, &points, value);
342 }
343 }
344 Ok(output)
345}
346
347pub fn polygons(
349 width: usize,
350 height: usize,
351 polygons: &[Vec<[i32; 2]>],
352 value: u8,
353) -> Result<Vec<u8>, String> {
354 let mut output = vec![
355 0;
356 width
357 .checked_mul(height)
358 .ok_or("polygon image size overflow")?
359 ];
360 let mut edges = Vec::new();
361 for polygon in polygons {
362 for i in 0..polygon.len() {
363 let p0 = polygon[(i + polygon.len() - 1) % polygon.len()];
364 let p1 = polygon[i];
365 let a = [p0[0] as i64, p0[1] as i64];
366 let b = [p1[0] as i64, p1[1] as i64];
367 line8(&mut output, width, height, a, b, value);
368 if a[1] != b[1] {
369 let (_, c0, c1) = clip(width as i64, height as i64, a, b);
370 let (cy0, cy1) = if c0[1] != c1[1] {
371 (c0[1], c1[1])
372 } else {
373 (a[1], b[1])
374 };
375 let dx = ((c1[0] - c0[0]) << 16) / (cy1 - cy0);
376 let mut x = (c0[0] << 16) + (a[1] - cy0) * dx;
377 if a[1] > b[1] {
378 x += (b[1] - a[1]) * dx;
379 }
380 edges.push((a[1].min(b[1]), a[1].max(b[1]), x, dx));
381 }
382 }
383 }
384 let mut intersections = Vec::new();
385 for y in 0..height as i64 {
386 intersections.clear();
387 for &(y0, y1, x, dx) in &edges {
388 if y >= y0 && y < y1 {
389 intersections.push(x + (y - y0) * dx);
390 }
391 }
392 intersections.sort_unstable();
393 for pair in intersections.as_chunks::<2>().0 {
394 let left = ((pair[0] + 65535) >> 16).max(0);
395 let right = (pair[1] >> 16).min(width as i64 - 1);
396 if left <= right {
397 output[y as usize * width + left as usize..y as usize * width + right as usize + 1]
398 .fill(value);
399 }
400 }
401 }
402 Ok(output)
403}