1use sequoia_core::{Point, Rect};
2
3use crate::flatten::Contour;
4use crate::path::{FillRule, Path};
5use crate::{DEFAULT_OPTIONS, Span, union_rect};
6
7#[derive(Clone, Copy, Debug, PartialEq)]
8pub struct RasterOptions {
9 pub tolerance: f32,
10
11 pub row_height: f32,
12
13 pub merge_tol: f32,
14
15 pub aa_samples: u32,
16
17 pub analytic: bool,
18}
19
20impl Default for RasterOptions {
21 fn default() -> Self {
22 DEFAULT_OPTIONS
23 }
24}
25
26impl RasterOptions {
27 pub const SMOOTH: Self = Self {
28 tolerance: crate::TOLERANCE,
29 row_height: 1.0,
30 merge_tol: 0.35,
31 aa_samples: 4,
32 analytic: true,
33 };
34
35 pub const CRISP: Self = Self {
36 tolerance: crate::TOLERANCE,
37 row_height: 1.0,
38 merge_tol: 0.35,
39 aa_samples: 1,
40 analytic: true,
41 };
42
43 pub const BANDED: Self = Self {
44 tolerance: crate::TOLERANCE,
45 row_height: 1.0,
46 merge_tol: 0.35,
47 aa_samples: 4,
48 analytic: false,
49 };
50
51 pub fn tolerance(mut self, tolerance: f32) -> Self {
52 self.tolerance = tolerance;
53 self
54 }
55
56 pub fn row_height(mut self, row_height: f32) -> Self {
57 self.row_height = row_height;
58 self
59 }
60
61 pub fn merge_tol(mut self, merge_tol: f32) -> Self {
62 self.merge_tol = merge_tol;
63 self
64 }
65
66 pub fn aa_samples(mut self, samples: u32) -> Self {
67 self.aa_samples = samples.clamp(1, 64);
68 self
69 }
70
71 pub fn analytic(mut self, analytic: bool) -> Self {
72 self.analytic = analytic;
73 self
74 }
75
76 pub fn for_scale(mut self, scale: f32) -> Self {
77 let s = if scale.is_finite() && scale > 0.0 {
78 scale
79 } else {
80 1.0
81 };
82 self.tolerance = (crate::TOLERANCE / s).max(0.05);
83 self.row_height = (1.0 / s).max(1.0 / 8.0);
84 self.merge_tol = (0.35 / s).max(0.02);
85 self
86 }
87}
88
89#[derive(Clone, Copy, Debug, PartialEq)]
90pub struct FillStyle {
91 pub rule: FillRule,
92
93 pub opts: RasterOptions,
94}
95
96impl Default for FillStyle {
97 fn default() -> Self {
98 Self {
99 rule: FillRule::NonZero,
100 opts: RasterOptions::default(),
101 }
102 }
103}
104
105impl FillStyle {
106 pub fn new(rule: FillRule, opts: RasterOptions) -> Self {
107 Self { rule, opts }
108 }
109
110 pub fn with_rule(rule: FillRule) -> Self {
111 Self {
112 rule,
113 opts: RasterOptions::default(),
114 }
115 }
116
117 #[must_use]
118 pub fn with_opts(mut self, opts: RasterOptions) -> Self {
119 self.opts = opts;
120 self
121 }
122}
123
124#[derive(Clone, Copy)]
125struct Edge {
126 x0: f32,
127 y0: f32,
128 x1: f32,
129 y1: f32,
130
131 dir: i32,
132}
133
134#[derive(Clone, Copy, Debug)]
135struct Run {
136 x0: f32,
137 x1: f32,
138 y0: f32,
139 y1: f32,
140
141 alpha: f32,
142 claimed: bool,
143}
144
145pub fn fill_styled(path: &Path, style: FillStyle, out: &mut Vec<Span>) -> Rect {
146 fill(path, style.rule, style.opts, out)
147}
148
149pub fn fill(path: &Path, rule: FillRule, opts: RasterOptions, out: &mut Vec<Span>) -> Rect {
150 if opts.analytic {
151 if let Some(rect) = path.as_rect() {
152 if rect.is_empty() {
153 return Rect::ZERO;
154 }
155 out.push(Span::rect(rect));
156 return rect;
157 }
158 if let Some((rect, radius)) = path.as_rounded_rect() {
159 if rect.is_empty() {
160 return Rect::ZERO;
161 }
162 out.push(Span::rounded(rect, radius));
163 return rect;
164 }
165 if let Some((center, radius)) = path.as_circle() {
166 if radius <= 0.0 {
167 return Rect::ZERO;
168 }
169 let rect = Rect::from_xywh(
170 center.x - radius,
171 center.y - radius,
172 radius * 2.0,
173 radius * 2.0,
174 );
175 out.push(Span::rounded(rect, radius));
176 return rect;
177 }
178 }
179
180 let contours = path.contours(opts.tolerance);
181 fill_contours(&contours, rule, opts, out)
182}
183
184pub fn fill_contours(
185 contours: &[Contour],
186 rule: FillRule,
187 opts: RasterOptions,
188 out: &mut Vec<Span>,
189) -> Rect {
190 let edges = collect_edges(contours);
191 if edges.is_empty() {
192 return Rect::ZERO;
193 }
194
195 let cell = opts.row_height.clamp(0.05, 16.0);
196 let samples = opts.aa_samples.clamp(1, 64) as usize;
197 let merge_tol = opts.merge_tol.max(0.0);
198
199 let mut top = f32::INFINITY;
200 let mut bottom = f32::NEG_INFINITY;
201 let mut left = f32::INFINITY;
202 let mut right = f32::NEG_INFINITY;
203 for e in &edges {
204 top = top.min(e.y0.min(e.y1));
205 bottom = bottom.max(e.y0.max(e.y1));
206 left = left.min(e.x0.min(e.x1));
207 right = right.max(e.x0.max(e.x1));
208 }
209 if !top.is_finite() || !bottom.is_finite() || bottom <= top {
210 return Rect::ZERO;
211 }
212 if !left.is_finite() || !right.is_finite() || right <= left {
213 return Rect::ZERO;
214 }
215
216 let first_row = (top / cell).floor();
217 let last_row = (bottom / cell).ceil();
218 let first_col = (left / cell).floor();
219 let last_col = (right / cell).ceil();
220 let cols = (last_col - first_col).max(0.0) as usize;
221 if cols == 0 {
222 return Rect::ZERO;
223 }
224
225 let mut coverage_per_cell = vec![0.0f32; cols];
226 let mut crossings: Vec<(f32, i32)> = Vec::new();
227 let mut spans: Vec<(f32, f32)> = Vec::new();
228 let mut row_runs: Vec<(f32, f32, f32)> = Vec::new();
229 let mut emitted: Vec<Run> = Vec::new();
230 let mut runs: Vec<Run> = Vec::new();
231 let mut coverage = Rect::ZERO;
232 let inv_samples = 1.0 / samples as f32;
233
234 let mut row = first_row;
235 while row <= last_row {
236 let y0 = row * cell;
237 let y1 = y0 + cell;
238 row += 1.0;
239 coverage_per_cell.fill(0.0);
240
241 for sample in 0..samples {
242 let y = y0 + (sample as f32 + 0.5) * inv_samples * cell;
243 crossings.clear();
244 for e in &edges {
245 let (ymin, ymax) = (e.y0.min(e.y1), e.y0.max(e.y1));
246 if y < ymin || y >= ymax {
247 continue;
248 }
249 let t = (y - e.y0) / (e.y1 - e.y0);
250 crossings.push((e.x0 + (e.x1 - e.x0) * t, e.dir));
251 }
252 if crossings.len() < 2 {
253 continue;
254 }
255 crossings.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
256
257 spans.clear();
258 match rule {
259 FillRule::NonZero => {
260 let mut winding = 0;
261 let mut start = 0.0;
262 for &(x, dir) in &crossings {
263 let was = winding;
264 winding += dir;
265 if was == 0 && winding != 0 {
266 start = x;
267 } else if was != 0 && winding == 0 {
268 spans.push((start, x));
269 }
270 }
271 }
272 FillRule::EvenOdd => {
273 let mut i = 0;
274 while i + 1 < crossings.len() {
275 spans.push((crossings[i].0, crossings[i + 1].0));
276 i += 2;
277 }
278 }
279 }
280
281 for &(x0, x1) in &spans {
282 add_span_coverage(&mut coverage_per_cell, first_col, cell, x0, x1);
283 }
284 }
285
286 row_runs.clear();
287 let mut i = 0usize;
288 while i < cols {
289 let a = coverage_per_cell[i] * inv_samples;
290 if a <= 0.0 {
291 i += 1;
292 continue;
293 }
294 let alpha = quantize_alpha(a);
295 let start = i;
296 i += 1;
297 while i < cols {
298 let b = coverage_per_cell[i] * inv_samples;
299 if b <= 0.0 || quantize_alpha(b) != alpha {
300 break;
301 }
302 i += 1;
303 }
304 row_runs.push((
305 (first_col + start as f32) * cell,
306 (first_col + i as f32) * cell,
307 alpha,
308 ));
309 }
310
311 for run in runs.iter_mut() {
312 run.claimed = false;
313 }
314 for (x0, x1, alpha) in row_runs.drain(..) {
315 let mut extended = false;
316 for run in runs.iter_mut() {
317 if run.claimed || run.alpha != alpha {
318 continue;
319 }
320 if (run.x0 - x0).abs() <= merge_tol && (run.x1 - x1).abs() <= merge_tol {
321 run.x0 = run.x0.min(x0);
322 run.x1 = run.x1.max(x1);
323 run.y1 = y1;
324 run.claimed = true;
325 extended = true;
326 break;
327 }
328 }
329 if !extended {
330 runs.push(Run {
331 x0,
332 x1,
333 y0,
334 y1,
335 alpha,
336 claimed: true,
337 });
338 }
339 }
340
341 emitted.clear();
342 runs.retain_mut(|run| {
343 if run.claimed {
344 run.claimed = false;
345 true
346 } else {
347 emitted.push(*run);
348 false
349 }
350 });
351 for run in emitted.drain(..) {
352 coverage = union_rect(coverage, emit_run(run, out));
353 }
354 }
355 for run in runs.drain(..) {
356 coverage = union_rect(coverage, emit_run(run, out));
357 }
358 coverage
359}
360
361fn add_span_coverage(coverage: &mut [f32], first_col: f32, cell: f32, x0: f32, x1: f32) {
362 if x1 <= x0 {
363 return;
364 }
365 let start = ((x0 / cell).floor() - first_col).max(0.0) as usize;
366 let end = (((x1 / cell).ceil() - first_col).max(0.0) as usize).min(coverage.len());
367 for (i, cell_cov) in coverage[start..end].iter_mut().enumerate() {
368 let cell_left = (first_col + (start + i) as f32) * cell;
369 let lo = x0.max(cell_left);
370 let hi = x1.min(cell_left + cell);
371 if hi > lo {
372 *cell_cov += (hi - lo) / cell;
373 }
374 }
375}
376
377fn quantize_alpha(a: f32) -> f32 {
378 const LEVELS: f32 = 64.0;
381 if a >= 1.0 {
382 1.0
383 } else if a <= 0.0 {
384 0.0
385 } else {
386 ((a * LEVELS).round().max(1.0) / LEVELS).min(1.0)
387 }
388}
389
390fn emit_run(run: Run, out: &mut Vec<Span>) -> Rect {
391 let rect = Rect::from_xywh(
392 run.x0,
393 run.y0,
394 (run.x1 - run.x0).max(0.0),
395 (run.y1 - run.y0).max(0.0),
396 );
397 if rect.is_empty() {
398 return Rect::ZERO;
399 }
400 out.push(Span::rect(rect).with_alpha(run.alpha));
401 rect
402}
403
404fn collect_edges(contours: &[Contour]) -> Vec<Edge> {
405 let mut edges = Vec::new();
406 for contour in contours {
407 let pts = &contour.points;
408 if pts.len() < 2 {
409 continue;
410 }
411 let n = pts.len();
412 for i in 0..n {
413 let a = pts[i];
414 let b = pts[(i + 1) % n];
415 if a.y == b.y {
416 continue;
417 }
418 if a == b {
419 continue;
420 }
421 let dir = if b.y > a.y { 1 } else { -1 };
422 edges.push(Edge {
423 x0: a.x,
424 y0: a.y,
425 x1: b.x,
426 y1: b.y,
427 dir,
428 });
429 }
430 }
431 edges
432}
433
434pub(crate) fn contains(contours: &[Contour], p: Point, rule: FillRule) -> bool {
435 let edges = collect_edges(contours);
436 let mut winding = 0;
437 let mut crossings = 0;
438 for e in &edges {
439 let (ymin, ymax) = (e.y0.min(e.y1), e.y0.max(e.y1));
440 if p.y < ymin || p.y >= ymax {
441 continue;
442 }
443 let t = (p.y - e.y0) / (e.y1 - e.y0);
444 let x = e.x0 + (e.x1 - e.x0) * t;
445 if x > p.x {
446 winding += e.dir;
447 crossings += 1;
448 }
449 }
450 match rule {
451 FillRule::NonZero => winding != 0,
452 FillRule::EvenOdd => crossings % 2 == 1,
453 }
454}
455
456#[cfg(test)]
457mod tests {
458 use super::quantize_alpha;
459
460 #[test]
461 fn alpha_quantization_keeps_64_levels() {
462 assert_eq!(quantize_alpha(0.0), 0.0);
463 assert_eq!(quantize_alpha(1.0), 1.0);
464 assert!((quantize_alpha(0.51) - 33.0 / 64.0).abs() < f32::EPSILON);
465 assert!(quantize_alpha(0.01) > 0.0, "thin coverage must survive");
466 }
467}