1mod accumulate;
14mod cache;
15pub mod dense;
16mod flatten;
17
18pub use cache::{CoverageCache, coverage_key};
19
20use crate::IRect;
21use accumulate::{accumulate_line, clip_line};
22use alpha2_model::FillRule;
23use kurbo::{BezPath, Point};
24
25pub const TILE: usize = 16;
27
28pub const TILE_BYTES: usize = TILE * TILE;
30
31#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
33pub enum TileState {
34 Empty,
36 Full,
38 Partial(u32),
40}
41
42#[derive(Clone, Debug, Default, Eq, PartialEq)]
44pub struct TileCoverage {
45 pub origin: (i32, i32),
47 pub size: (u32, u32),
49 pub tiles: Vec<TileState>,
51 pub partial: Vec<[u8; TILE_BYTES]>,
53}
54
55impl TileCoverage {
56 #[must_use]
58 pub fn at(&self, x: i32, y: i32) -> u8 {
59 let tile = i32::try_from(TILE).unwrap_or(16);
60 let (tx, ty) = (
61 x.div_euclid(tile) - self.origin.0,
62 y.div_euclid(tile) - self.origin.1,
63 );
64 let (Ok(tx), Ok(ty)) = (u32::try_from(tx), u32::try_from(ty)) else {
65 return 0;
66 };
67 if tx >= self.size.0 || ty >= self.size.1 {
68 return 0;
69 }
70 match self.tiles[(ty * self.size.0 + tx) as usize] {
71 TileState::Empty => 0,
72 TileState::Full => 255,
73 TileState::Partial(index) => {
74 let (cx, cy) = (x.rem_euclid(tile), y.rem_euclid(tile));
75 self.partial[index as usize][usize::try_from(cy * tile + cx).unwrap_or(0)]
76 }
77 }
78 }
79
80 #[must_use]
82 pub fn rect(&self) -> IRect {
83 let tile = i32::try_from(TILE).unwrap_or(16);
84 let width = i32::try_from(self.size.0).unwrap_or(0);
85 let height = i32::try_from(self.size.1).unwrap_or(0);
86 IRect::new(
87 self.origin.0 * tile,
88 self.origin.1 * tile,
89 (self.origin.0 + width) * tile,
90 (self.origin.1 + height) * tile,
91 )
92 }
93
94 #[must_use]
96 pub fn heap_bytes(&self) -> usize {
97 self.tiles.len() * size_of::<TileState>() + self.partial.len() * TILE_BYTES
98 }
99
100 #[must_use]
102 pub fn counts(&self) -> (usize, usize, usize) {
103 let mut counts = (0, 0, 0);
104 for tile in &self.tiles {
105 match tile {
106 TileState::Empty => counts.0 += 1,
107 TileState::Full => counts.1 += 1,
108 TileState::Partial(_) => counts.2 += 1,
109 }
110 }
111 counts
112 }
113}
114
115#[must_use]
117pub fn tile_aligned(clip: IRect) -> IRect {
118 let tile = i32::try_from(TILE).unwrap_or(16);
119 if clip.is_empty() {
120 return IRect::default();
121 }
122 IRect::new(
123 clip.x0.div_euclid(tile) * tile,
124 clip.y0.div_euclid(tile) * tile,
125 (clip.x1 + tile - 1).div_euclid(tile) * tile,
126 (clip.y1 + tile - 1).div_euclid(tile) * tile,
127 )
128}
129
130#[allow(
133 clippy::cast_possible_truncation,
134 clippy::cast_sign_loss,
135 clippy::cast_precision_loss
136)]
137pub(crate) fn coverage_byte(rule: FillRule, winding: f32) -> u8 {
138 let coverage = match rule {
139 FillRule::Nonzero => winding.abs().min(1.0),
140 FillRule::Evenodd => {
141 let half = winding.abs() * 0.5;
142 let turn = half - (half as i32) as f32;
143 (1.0 - (2.0 * turn - 1.0).abs()).min(1.0)
144 }
145 };
146 (coverage * 255.0 + 0.5) as u8
147}
148
149#[derive(Clone, Copy)]
151enum Run {
152 Const { x0: usize, x1: usize, value: u8 },
153 Pixels { x0: usize, x1: usize, offset: usize },
154}
155
156impl Run {
157 const fn x1(self) -> usize {
158 match self {
159 Self::Const { x1, .. } | Self::Pixels { x1, .. } => x1,
160 }
161 }
162}
163
164#[derive(Debug, Default)]
166pub struct RasterScratch {
167 lines: Vec<[f64; 4]>,
168 bins: Vec<Vec<u32>>,
169 acc: Vec<f32>,
170 touched: Vec<Vec<(usize, usize)>>,
171 runs: Vec<Vec<RunSlot>>,
172 pixels: Vec<u8>,
173 cursor: Vec<usize>,
174}
175
176#[derive(Clone, Copy, Debug)]
178struct RunSlot(u8, usize, usize, usize);
179
180impl From<Run> for RunSlot {
181 fn from(run: Run) -> Self {
182 match run {
183 Run::Const { x0, x1, value } => Self(0, x0, x1, usize::from(value)),
184 Run::Pixels { x0, x1, offset } => Self(1, x0, x1, offset),
185 }
186 }
187}
188
189impl From<RunSlot> for Run {
190 #[allow(clippy::cast_possible_truncation)]
191 fn from(slot: RunSlot) -> Self {
192 if slot.0 == 0 {
193 Self::Const {
194 x0: slot.1,
195 x1: slot.2,
196 value: slot.3 as u8,
197 }
198 } else {
199 Self::Pixels {
200 x0: slot.1,
201 x1: slot.2,
202 offset: slot.3,
203 }
204 }
205 }
206}
207
208#[must_use]
214#[allow(clippy::too_many_lines)]
216pub fn rasterize(
217 path: &BezPath,
218 rule: FillRule,
219 clip: IRect,
220 scratch: &mut RasterScratch,
221) -> TileCoverage {
222 let clip = tile_aligned(clip);
223 let tile = i32::try_from(TILE).unwrap_or(16);
224 let (w, h) = (clip.width() as usize, clip.height() as usize);
225 let tiles_x = w / TILE;
226 let tiles_y = h / TILE;
227 let mut out = TileCoverage {
228 origin: (clip.x0.div_euclid(tile), clip.y0.div_euclid(tile)),
229 size: (
230 u32::try_from(tiles_x).unwrap_or(0),
231 u32::try_from(tiles_y).unwrap_or(0),
232 ),
233 tiles: Vec::with_capacity(tiles_x * tiles_y),
234 partial: Vec::new(),
235 };
236 if w == 0 || h == 0 {
237 return out;
238 }
239 flatten::flatten(
240 path,
241 Point::new(f64::from(clip.x0), f64::from(clip.y0)),
242 &mut scratch.lines,
243 );
244 #[allow(clippy::cast_precision_loss)]
245 let (wf, hf) = (w as f64, h as f64);
246 scratch.bins.resize_with(tiles_y, Vec::new);
248 for bin in &mut scratch.bins[..tiles_y] {
249 bin.clear();
250 }
251 for (index, line) in scratch.lines.iter().enumerate() {
252 let (lo, hi) = (line[1].min(line[3]).max(0.0), line[1].max(line[3]).min(hf));
253 if hi <= lo {
254 continue;
255 }
256 #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
258 let (first, last) = (
259 (lo as usize) / TILE,
260 (hi.ceil() as usize).div_ceil(TILE).min(tiles_y),
261 );
262 let index = u32::try_from(index).unwrap_or(u32::MAX);
263 for bin in &mut scratch.bins[first..last] {
264 bin.push(index);
265 }
266 }
267 let stride = w + 2;
268 scratch.acc.clear();
269 scratch.acc.resize(stride * TILE, 0.0);
270 scratch.touched.resize_with(TILE, Vec::new);
271 scratch.runs.resize_with(TILE, Vec::new);
272 scratch.cursor.resize(TILE, 0);
273 #[allow(clippy::cast_precision_loss)]
274 let wf32 = w as f32;
275 for strip in 0..tiles_y {
276 let r0 = strip * TILE;
277 let r1 = r0 + TILE;
278 for list in &mut scratch.touched[..TILE] {
279 list.clear();
280 }
281 {
282 let RasterScratch {
283 lines,
284 bins,
285 acc,
286 touched,
287 ..
288 } = &mut *scratch;
289 for &index in &bins[strip] {
290 clip_line(lines[index as usize], wf, hf, |p0, p1| {
291 accumulate_line(acc, stride, r0, (r0, r1), wf32, p0, p1, |y, first, last| {
292 touched[y - r0].push((first, last));
293 });
294 });
295 }
296 }
297 scratch.pixels.clear();
299 for r in 0..TILE {
300 let row = r * stride;
301 let RasterScratch {
302 acc,
303 touched,
304 runs,
305 pixels,
306 ..
307 } = &mut *scratch;
308 let ranges = &mut touched[r];
309 ranges.sort_unstable();
310 let runs = &mut runs[r];
311 runs.clear();
312 let (mut winding, mut cursor) = (0.0f32, 0usize);
313 let mut index = 0;
314 while index < ranges.len() {
315 let (lo, mut hi) = ranges[index];
316 index += 1;
317 while index < ranges.len() && ranges[index].0 <= hi + 1 {
318 hi = hi.max(ranges[index].1);
319 index += 1;
320 }
321 if lo > cursor && cursor < w {
322 runs.push(
323 Run::Const {
324 x0: cursor,
325 x1: lo.min(w),
326 value: coverage_byte(rule, winding),
327 }
328 .into(),
329 );
330 }
331 let offset = pixels.len();
332 for x in lo..=hi {
333 winding += acc[row + x];
334 acc[row + x] = 0.0;
335 if x < w {
336 pixels.push(coverage_byte(rule, winding));
337 }
338 }
339 if lo < w {
340 runs.push(
341 Run::Pixels {
342 x0: lo,
343 x1: (hi + 1).min(w),
344 offset,
345 }
346 .into(),
347 );
348 }
349 cursor = hi + 1;
350 }
351 if cursor < w {
352 runs.push(
353 Run::Const {
354 x0: cursor,
355 x1: w,
356 value: coverage_byte(rule, winding),
357 }
358 .into(),
359 );
360 }
361 }
362 for cursor in &mut scratch.cursor[..TILE] {
364 *cursor = 0;
365 }
366 for tx in 0..tiles_x {
367 let (cx0, cx1) = (tx * TILE, tx * TILE + TILE);
368 let (mut all_full, mut all_empty) = (true, true);
369 for r in 0..TILE {
370 let runs = &scratch.runs[r];
371 let cursor = &mut scratch.cursor[r];
372 while *cursor < runs.len() && Run::from(runs[*cursor]).x1() <= cx0 {
373 *cursor += 1;
374 }
375 match runs.get(*cursor).map(|slot| Run::from(*slot)) {
376 Some(Run::Const { x0, x1, value }) if x0 <= cx0 && x1 >= cx1 => {
377 all_full &= value == 255;
378 all_empty &= value == 0;
379 }
380 _ => {
381 all_full = false;
382 all_empty = false;
383 }
384 }
385 }
386 let state = if all_full {
387 TileState::Full
388 } else if all_empty {
389 TileState::Empty
390 } else {
391 let mut bytes = [0u8; TILE_BYTES];
392 for r in 0..TILE {
393 let runs = &scratch.runs[r];
394 let mut at = scratch.cursor[r];
395 while at < runs.len() {
396 let run = Run::from(runs[at]);
397 let (x0, x1) = match run {
398 Run::Const { x0, x1, .. } | Run::Pixels { x0, x1, .. } => (x0, x1),
399 };
400 if x0 >= cx1 {
401 break;
402 }
403 for x in x0.max(cx0)..x1.min(cx1) {
404 bytes[r * TILE + (x - cx0)] = match run {
405 Run::Const { value, .. } => value,
406 Run::Pixels { x0, offset, .. } => scratch.pixels[offset + (x - x0)],
407 };
408 }
409 at += 1;
410 }
411 }
412 if bytes.iter().all(|byte| *byte == 255) {
414 TileState::Full
415 } else if bytes.iter().all(|byte| *byte == 0) {
416 TileState::Empty
417 } else {
418 out.partial.push(bytes);
419 TileState::Partial(u32::try_from(out.partial.len() - 1).unwrap_or(u32::MAX))
420 }
421 };
422 out.tiles.push(state);
423 }
424 }
425 out
426}
427
428#[must_use]
430pub fn flattened(path: &BezPath, clip: IRect) -> Vec<[f64; 4]> {
431 let clip = tile_aligned(clip);
432 let mut lines = Vec::new();
433 flatten::flatten(
434 path,
435 Point::new(f64::from(clip.x0), f64::from(clip.y0)),
436 &mut lines,
437 );
438 lines
439}
440
441#[must_use]
443pub fn winding_at(path: &BezPath, point: Point) -> i32 {
444 let mut lines = Vec::new();
445 flatten::flatten(path, Point::ZERO, &mut lines);
446 let mut winding = 0;
447 for [x0, y0, x1, y1] in lines {
448 if (y0 <= point.y) != (y1 <= point.y) {
450 let x = x0 + (point.y - y0) * (x1 - x0) / (y1 - y0);
451 if x > point.x {
452 winding += if y1 > y0 { 1 } else { -1 };
453 }
454 }
455 }
456 winding
457}
458
459#[cfg(test)]
460mod tests;