1// Copyright 2006 The Android Open Source Project
2// Copyright 2020 Yevhenii Reizner
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7use core::convert::TryFrom;
8
9use tiny_skia_path::SaturateCast;
10
11use crate::{FillRule, IntRect, LengthU32, Path, Rect};
12
13use crate::blitter::Blitter;
14use crate::edge::{Edge, LineEdge};
15use crate::edge_builder::{BasicEdgeBuilder, ShiftedIntRect};
16use crate::fixed_point::{fdot16, fdot6, FDot16};
17use crate::geom::{IntRectExt, ScreenIntRect};
18
19#[cfg(all(not(feature = "std"), feature = "no-std-float"))]
20use tiny_skia_path::NoStdFloat;
21
22pub fn fill_path(
23 path: &Path,
24 fill_rule: FillRule,
25 clip: &ScreenIntRect,
26 blitter: &mut dyn Blitter,
27) {
28 let ir = match conservative_round_to_int(&path.bounds()) {
29 Some(v) => v,
30 None => return,
31 };
32
33 let path_contained_in_clip = if let Some(bounds) = ir.to_screen_int_rect() {
34 clip.contains(&bounds)
35 } else {
36 // If bounds cannot be converted into ScreenIntRect,
37 // the path is out of clip.
38 false
39 };
40
41 // TODO: SkScanClipper
42
43 fill_path_impl(
44 path,
45 fill_rule,
46 clip,
47 ir.y(),
48 ir.bottom(),
49 0,
50 path_contained_in_clip,
51 blitter,
52 );
53}
54
55// Conservative rounding function, which effectively nudges the int-rect to be slightly larger
56// than Rect::round() might have produced. This is a safety-net for the scan-converter, which
57// inspects the returned int-rect, and may disable clipping (for speed) if it thinks all of the
58// edges will fit inside the clip's bounds. The scan-converter introduces slight numeric errors
59// due to accumulated += of the slope, so this function is used to return a conservatively large
60// int-bounds, and thus we will only disable clipping if we're sure the edges will stay in-bounds.
61fn conservative_round_to_int(src: &Rect) -> Option<IntRect> {
62 // We must use `from_ltrb`, otherwise rounding will be incorrect.
63 IntRect::from_ltrb(
64 left:round_down_to_int(src.left()),
65 top:round_down_to_int(src.top()),
66 right:round_up_to_int(src.right()),
67 bottom:round_up_to_int(src.bottom()),
68 )
69}
70
71// Bias used for conservative rounding of float rects to int rects, to nudge the irects a little
72// larger, so we don't "think" a path's bounds are inside a clip, when (due to numeric drift in
73// the scan-converter) we might walk beyond the predicted limits.
74//
75// This value has been determined trial and error: pick the smallest value (after the 0.5) that
76// fixes any problematic cases (e.g. crbug.com/844457)
77// NOTE: cubics appear to be the main reason for needing this slop. If we could (perhaps) have a
78// more accurate walker for cubics, we may be able to reduce this fudge factor.
79const CONSERVATIVE_ROUND_BIAS: f64 = 0.5 + 1.5 / fdot6::ONE as f64;
80
81// Round the value down. This is used to round the top and left of a rectangle,
82// and corresponds to the way the scan converter treats the top and left edges.
83// It has a slight bias to make the "rounded" int smaller than a normal round, to create a more
84// conservative int-bounds (larger) from a float rect.
85fn round_down_to_int(x: f32) -> i32 {
86 let mut xx: f64 = x as f64;
87 xx -= CONSERVATIVE_ROUND_BIAS;
88 i32::saturate_from(xx.ceil())
89}
90
91// Round the value up. This is used to round the right and bottom of a rectangle.
92// It has a slight bias to make the "rounded" int smaller than a normal round, to create a more
93// conservative int-bounds (larger) from a float rect.
94fn round_up_to_int(x: f32) -> i32 {
95 let mut xx: f64 = x as f64;
96 xx += CONSERVATIVE_ROUND_BIAS;
97 i32::saturate_from(xx.floor())
98}
99
100pub fn fill_path_impl(
101 path: &Path,
102 fill_rule: FillRule,
103 clip_rect: &ScreenIntRect,
104 mut start_y: i32,
105 mut stop_y: i32,
106 shift_edges_up: i32,
107 path_contained_in_clip: bool,
108 blitter: &mut dyn Blitter,
109) {
110 let shifted_clip = match ShiftedIntRect::new(clip_rect, shift_edges_up) {
111 Some(v) => v,
112 None => return,
113 };
114
115 let clip = if path_contained_in_clip {
116 None
117 } else {
118 Some(&shifted_clip)
119 };
120 let mut edges = match BasicEdgeBuilder::build_edges(path, clip, shift_edges_up) {
121 Some(v) => v,
122 None => return, // no edges to render, just return
123 };
124
125 edges.sort_by(|a, b| {
126 let mut value_a = a.as_line().first_y;
127 let mut value_b = b.as_line().first_y;
128
129 if value_a == value_b {
130 value_a = a.as_line().x;
131 value_b = b.as_line().x;
132 }
133
134 value_a.cmp(&value_b)
135 });
136
137 for i in 0..edges.len() {
138 // 0 will be set later, so start with 1.
139 edges[i].prev = Some(i as u32 + 0);
140 edges[i].next = Some(i as u32 + 2);
141 }
142
143 const EDGE_HEAD_Y: i32 = i32::MIN;
144 const EDGE_TAIL_Y: i32 = i32::MAX;
145
146 edges.insert(
147 0,
148 Edge::Line(LineEdge {
149 prev: None,
150 next: Some(1),
151 x: i32::MIN,
152 first_y: EDGE_HEAD_Y,
153 ..LineEdge::default()
154 }),
155 );
156
157 edges.push(Edge::Line(LineEdge {
158 prev: Some(edges.len() as u32 - 1),
159 next: None,
160 first_y: EDGE_TAIL_Y,
161 ..LineEdge::default()
162 }));
163
164 start_y <<= shift_edges_up;
165 stop_y <<= shift_edges_up;
166
167 let top = shifted_clip.shifted().y() as i32;
168 if !path_contained_in_clip && start_y < top {
169 start_y = top;
170 }
171
172 let bottom = shifted_clip.shifted().bottom() as i32;
173 if !path_contained_in_clip && stop_y > bottom {
174 stop_y = bottom;
175 }
176
177 let start_y = match u32::try_from(start_y) {
178 Ok(v) => v,
179 Err(_) => return,
180 };
181 let stop_y = match u32::try_from(stop_y) {
182 Ok(v) => v,
183 Err(_) => return,
184 };
185
186 // TODO: walk_simple_edges
187
188 walk_edges(
189 fill_rule,
190 start_y,
191 stop_y,
192 shifted_clip.shifted().right(),
193 &mut edges,
194 blitter,
195 );
196}
197
198// TODO: simplify!
199fn walk_edges(
200 fill_rule: FillRule,
201 start_y: u32,
202 stop_y: u32,
203 right_clip: u32,
204 edges: &mut [Edge],
205 blitter: &mut dyn Blitter,
206) {
207 let mut curr_y = start_y;
208 let winding_mask = if fill_rule == FillRule::EvenOdd {
209 1
210 } else {
211 -1
212 };
213
214 loop {
215 let mut w = 0i32;
216 let mut left = 0u32;
217 let mut prev_x = edges[0].x;
218
219 let mut curr_idx = edges[0].next.unwrap() as usize;
220 while edges[curr_idx].first_y <= curr_y as i32 {
221 debug_assert!(edges[curr_idx].last_y >= curr_y as i32);
222
223 let x = fdot16::round_to_i32(edges[curr_idx].x) as u32; // TODO: check
224
225 if (w & winding_mask) == 0 {
226 // we're starting interval
227 left = x;
228 }
229
230 w += i32::from(edges[curr_idx].winding);
231
232 if (w & winding_mask) == 0 {
233 // we finished an interval
234 if let Some(width) = LengthU32::new(x - left) {
235 blitter.blit_h(left, curr_y, width);
236 }
237 }
238
239 let next_idx = edges[curr_idx].next.unwrap();
240 let new_x;
241
242 if edges[curr_idx].last_y == curr_y as i32 {
243 // are we done with this edge?
244 match &mut edges[curr_idx] {
245 Edge::Line(_) => {
246 remove_edge(curr_idx, edges);
247 }
248 Edge::Quadratic(ref mut quad) => {
249 if quad.curve_count > 0 && quad.update() {
250 new_x = quad.line.x;
251
252 if new_x < prev_x {
253 // ripple current edge backwards until it is x-sorted
254 backward_insert_edge_based_on_x(curr_idx, edges);
255 } else {
256 prev_x = new_x;
257 }
258 } else {
259 remove_edge(curr_idx, edges);
260 }
261 }
262 Edge::Cubic(ref mut cubic) => {
263 if cubic.curve_count < 0 && cubic.update() {
264 debug_assert!(cubic.line.first_y == curr_y as i32 + 1);
265
266 new_x = cubic.line.x;
267
268 if new_x < prev_x {
269 // ripple current edge backwards until it is x-sorted
270 backward_insert_edge_based_on_x(curr_idx, edges);
271 } else {
272 prev_x = new_x;
273 }
274 } else {
275 remove_edge(curr_idx, edges);
276 }
277 }
278 }
279 } else {
280 debug_assert!(edges[curr_idx].last_y > curr_y as i32);
281 new_x = edges[curr_idx].x + edges[curr_idx].dx;
282 edges[curr_idx].x = new_x;
283
284 if new_x < prev_x {
285 // ripple current edge backwards until it is x-sorted
286 backward_insert_edge_based_on_x(curr_idx, edges);
287 } else {
288 prev_x = new_x;
289 }
290 }
291
292 curr_idx = next_idx as usize;
293 }
294
295 if (w & winding_mask) != 0 {
296 // was our right-edge culled away?
297 if let Some(width) = LengthU32::new(right_clip - left) {
298 blitter.blit_h(left, curr_y, width);
299 }
300 }
301
302 curr_y += 1;
303 if curr_y >= stop_y {
304 break;
305 }
306
307 // now current edge points to the first edge with a Yint larger than curr_y
308 insert_new_edges(curr_idx, curr_y as i32, edges);
309 }
310}
311
312fn remove_edge(curr_idx: usize, edges: &mut [Edge]) {
313 let prev: u32 = edges[curr_idx].prev.unwrap();
314 let next: u32 = edges[curr_idx].next.unwrap();
315
316 edges[prev as usize].next = Some(next);
317 edges[next as usize].prev = Some(prev);
318}
319
320fn backward_insert_edge_based_on_x(curr_idx: usize, edges: &mut [Edge]) {
321 let x: i32 = edges[curr_idx].x;
322 let mut prev_idx: usize = edges[curr_idx].prev.unwrap() as usize;
323 while prev_idx != 0 {
324 if edges[prev_idx].x > x {
325 prev_idx = edges[prev_idx].prev.unwrap() as usize;
326 } else {
327 break;
328 }
329 }
330
331 let next_idx: usize = edges[prev_idx].next.unwrap() as usize;
332 if next_idx != curr_idx {
333 remove_edge(curr_idx, edges);
334 insert_edge_after(curr_idx, after_idx:prev_idx, edges);
335 }
336}
337
338fn insert_edge_after(curr_idx: usize, after_idx: usize, edges: &mut [Edge]) {
339 edges[curr_idx].prev = Some(after_idx as u32);
340 edges[curr_idx].next = edges[after_idx].next;
341
342 let after_next_idx: usize = edges[after_idx].next.unwrap() as usize;
343 edges[after_next_idx].prev = Some(curr_idx as u32);
344 edges[after_idx].next = Some(curr_idx as u32);
345}
346
347// Start from the right side, searching backwards for the point to begin the new edge list
348// insertion, marching forwards from here. The implementation could have started from the left
349// of the prior insertion, and search to the right, or with some additional caching, binary
350// search the starting point. More work could be done to determine optimal new edge insertion.
351fn backward_insert_start(mut prev_idx: usize, x: FDot16, edges: &mut [Edge]) -> usize {
352 while let Some(prev: u32) = edges[prev_idx].prev {
353 prev_idx = prev as usize;
354 if edges[prev_idx].x <= x {
355 break;
356 }
357 }
358
359 prev_idx
360}
361
362fn insert_new_edges(mut new_idx: usize, curr_y: i32, edges: &mut [Edge]) {
363 if edges[new_idx].first_y != curr_y {
364 return;
365 }
366
367 let prev_idx = edges[new_idx].prev.unwrap() as usize;
368 if edges[prev_idx].x <= edges[new_idx].x {
369 return;
370 }
371
372 // find first x pos to insert
373 let mut start_idx = backward_insert_start(prev_idx, edges[new_idx].x, edges);
374 // insert the lot, fixing up the links as we go
375 loop {
376 let next_idx = edges[new_idx].next.unwrap() as usize;
377 let mut keep_edge = false;
378 loop {
379 let after_idx = edges[start_idx].next.unwrap() as usize;
380 if after_idx == new_idx {
381 keep_edge = true;
382 break;
383 }
384
385 if edges[after_idx].x >= edges[new_idx].x {
386 break;
387 }
388
389 start_idx = after_idx;
390 }
391
392 if !keep_edge {
393 remove_edge(new_idx, edges);
394 insert_edge_after(new_idx, start_idx, edges);
395 }
396
397 start_idx = new_idx;
398 new_idx = next_idx;
399
400 if edges[new_idx].first_y != curr_y {
401 break;
402 }
403 }
404}
405