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 = 32.0;
379 if a >= 1.0 {
380 1.0
381 } else if a <= 0.0 {
382 0.0
383 } else {
384 ((a * LEVELS).round().max(1.0) / LEVELS).min(1.0)
385 }
386}
387
388fn emit_run(run: Run, out: &mut Vec<Span>) -> Rect {
389 let rect = Rect::from_xywh(
390 run.x0,
391 run.y0,
392 (run.x1 - run.x0).max(0.0),
393 (run.y1 - run.y0).max(0.0),
394 );
395 if rect.is_empty() {
396 return Rect::ZERO;
397 }
398 out.push(Span::rect(rect).with_alpha(run.alpha));
399 rect
400}
401
402fn collect_edges(contours: &[Contour]) -> Vec<Edge> {
403 let mut edges = Vec::new();
404 for contour in contours {
405 let pts = &contour.points;
406 if pts.len() < 2 {
407 continue;
408 }
409 let n = pts.len();
410 for i in 0..n {
411 let a = pts[i];
412 let b = pts[(i + 1) % n];
413 if a.y == b.y {
414 continue;
415 }
416 if a == b {
417 continue;
418 }
419 let dir = if b.y > a.y { 1 } else { -1 };
420 edges.push(Edge {
421 x0: a.x,
422 y0: a.y,
423 x1: b.x,
424 y1: b.y,
425 dir,
426 });
427 }
428 }
429 edges
430}
431
432pub(crate) fn contains(contours: &[Contour], p: Point, rule: FillRule) -> bool {
433 let edges = collect_edges(contours);
434 let mut winding = 0;
435 let mut crossings = 0;
436 for e in &edges {
437 let (ymin, ymax) = (e.y0.min(e.y1), e.y0.max(e.y1));
438 if p.y < ymin || p.y >= ymax {
439 continue;
440 }
441 let t = (p.y - e.y0) / (e.y1 - e.y0);
442 let x = e.x0 + (e.x1 - e.x0) * t;
443 if x > p.x {
444 winding += e.dir;
445 crossings += 1;
446 }
447 }
448 match rule {
449 FillRule::NonZero => winding != 0,
450 FillRule::EvenOdd => crossings % 2 == 1,
451 }
452}