surpass/
lines.rs

Help
1// Copyright 2022 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::cell::Cell;
6use std::num::NonZeroU64;
7
8use rayon::prelude::*;
9
10use crate::extend::{ExtendTuple10, ExtendTuple3};
11use crate::{AffineTransform, Layer, Path, PIXEL_WIDTH};
12
13const MIN_LEN: usize = 1_024;
14
15fn integers_between(a: f32, b: f32) -> u32 {
16    let min = a.min(b);
17    let max = a.max(b);
18
19    0.max((max.ceil() - min.floor() - 1.0) as u32)
20}
21
22fn prefix_sum(vals: &mut [u32]) -> u32 {
23    let mut sum = 0;
24    for val in vals {
25        sum += *val;
26        *val = sum;
27    }
28
29    sum
30}
31
32#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
33#[repr(transparent)]
34pub struct GeomId(NonZeroU64);
35
36impl GeomId {
37    #[cfg(test)]
38    pub fn get(self) -> u64 {
39        self.0.get() - 1
40    }
41
42    #[inline]
43    pub fn next(self) -> Self {
44        Self(
45            NonZeroU64::new(self.0.get().checked_add(1).expect("id should never reach u64::MAX"))
46                .unwrap(),
47        )
48    }
49}
50
51impl Default for GeomId {
52    #[inline]
53    fn default() -> Self {
54        Self(NonZeroU64::new(1).unwrap())
55    }
56}
57
58#[derive(Debug, Default)]
59pub struct LinesBuilder {
60    lines: Lines,
61    cached_len: Cell<usize>,
62    cached_until: Cell<usize>,
63}
64
65impl LinesBuilder {
66    #[inline]
67    pub fn new() -> Self {
68        Self::default()
69    }
70
71    // This type is only used in forma where it does not need `is_empty`.
72    #[allow(clippy::len_without_is_empty)]
73    #[inline]
74    pub fn len(&self) -> usize {
75        if self.lines.ids.len() <= self.cached_until.get() {
76            self.cached_len.get()
77        } else {
78            let new_len = self.cached_len.get()
79                + self.lines.ids[self.cached_until.get()..]
80                    .iter()
81                    .filter(|id| id.is_some())
82                    .count();
83
84            self.cached_len.set(new_len);
85            self.cached_until.set(self.lines.ids.len());
86
87            new_len
88        }
89    }
90
91    #[inline]
92    pub fn push_path(&mut self, id: GeomId, path: &Path) {
93        path.push_lines_to(&mut self.lines.x, &mut self.lines.y, id, &mut self.lines.ids);
94
95        self.lines.ids.resize(self.lines.x.len().checked_sub(1).unwrap_or_default(), Some(id));
96
97        if self.lines.ids.last().map(Option::is_some).unwrap_or_default() {
98            self.lines.ids.push(None);
99        }
100    }
101
102    #[cfg(test)]
103    pub fn push(&mut self, id: GeomId, segment: [crate::Point; 2]) {
104        let new_point_needed =
105            if let (Some(&x), Some(&y)) = (self.lines.x.last(), self.lines.y.last()) {
106                let last_point = crate::Point { x, y };
107
108                last_point != segment[0]
109            } else {
110                true
111            };
112
113        if new_point_needed {
114            self.lines.x.push(segment[0].x);
115            self.lines.y.push(segment[0].y);
116        }
117
118        self.lines.x.push(segment[1].x);
119        self.lines.y.push(segment[1].y);
120
121        if self.lines.ids.len() >= 2 {
122            match self.lines.ids[self.lines.ids.len() - 2] {
123                Some(last_id) if last_id != id => {
124                    self.lines.ids.push(Some(id));
125                    self.lines.ids.push(None);
126                }
127                _ => {
128                    self.lines.ids.pop();
129                    self.lines.ids.push(Some(id));
130                    self.lines.ids.push(None);
131                }
132            }
133        } else {
134            self.lines.ids.push(Some(id));
135            self.lines.ids.push(None);
136        }
137    }
138
139    pub fn retain<F>(&mut self, mut f: F)
140    where
141        F: FnMut(GeomId) -> bool,
142    {
143        let len = self.lines.x.len();
144        let mut del = 0;
145        let mut prev_id = None;
146
147        for i in 0..len {
148            // `None` IDs will always belong to the previous ID.
149            // Thus, if an ID is removed here, its None will be removed as well.
150
151            let id = self.lines.ids[i];
152            let should_retain = id
153                .or(prev_id)
154                .map(&mut f)
155                .expect("consecutive None values should not exist in ids");
156            prev_id = id;
157
158            if !should_retain {
159                del += 1;
160                continue;
161            }
162
163            if del > 0 {
164                self.lines.x.swap(i - del, i);
165                self.lines.y.swap(i - del, i);
166                self.lines.ids.swap(i - del, i);
167            }
168        }
169
170        if del > 0 {
171            self.lines.x.truncate(len - del);
172            self.lines.y.truncate(len - del);
173            self.lines.ids.truncate(len - del);
174        }
175    }
176
177    pub fn build<F>(mut self, layers: F) -> Lines
178    where
179        F: Fn(GeomId) -> Option<Layer> + Send + Sync,
180    {
181        let ps_layers = self.lines.x.par_windows(2).with_min_len(MIN_LEN).zip_eq(
182            self.lines.y.par_windows(2).with_min_len(MIN_LEN).zip_eq(
183                self.lines.ids[..self.lines.ids.len().checked_sub(1).unwrap_or_default()]
184                    .par_iter()
185                    .with_min_len(MIN_LEN),
186            ),
187        );
188        let par_iter = ps_layers.map(|(xs, (ys, &id))| {
189            let p0x = xs[0];
190            let p0y = ys[0];
191            let p1x = xs[1];
192            let p1y = ys[1];
193
194            if id.is_none() {
195                // Returns a length of 0 so that the line segments between two
196                // polygonal chains generate no pixel segments.
197                return Default::default();
198            }
199
200            let layer = match id.and_then(&layers) {
201                Some(layer) => layer,
202                None => return Default::default(),
203            };
204
205            if let Layer { is_enabled: false, .. } = layer {
206                return Default::default();
207            }
208
209            let order = match layer.order {
210                Some(order) => order.as_u32(),
211                None => return Default::default(),
212            };
213
214            fn transform_point(point: (f32, f32), transform: &AffineTransform) -> (f32, f32) {
215                (
216                    transform.ux.mul_add(point.0, transform.vx.mul_add(point.1, transform.tx)),
217                    transform.uy.mul_add(point.0, transform.vy.mul_add(point.1, transform.ty)),
218                )
219            }
220
221            let transform = layer.affine_transform.as_ref().map(|transform| &transform.0);
222
223            let (p0x, p0y, p1x, p1y) = if let Some(transform) = transform {
224                let (p0x, p0y) = transform_point((p0x, p0y), transform);
225                let (p1x, p1y) = transform_point((p1x, p1y), transform);
226
227                (p0x, p0y, p1x, p1y)
228            } else {
229                (p0x, p0y, p1x, p1y)
230            };
231
232            if p0y == p1y {
233                return Default::default();
234            }
235
236            let dx = p1x - p0x;
237            let dy = p1y - p0y;
238            let dx_recip = dx.recip();
239            let dy_recip = dy.recip();
240
241            let t_offset_x = if dx != 0.0 {
242                ((p0x.ceil() - p0x) * dx_recip).max((p0x.floor() - p0x) * dx_recip)
243            } else {
244                0.0
245            };
246            let t_offset_y = if dy != 0.0 {
247                ((p0y.ceil() - p0y) * dy_recip).max((p0y.floor() - p0y) * dy_recip)
248            } else {
249                0.0
250            };
251
252            let a = dx_recip.abs();
253            let b = dy_recip.abs();
254            let c = t_offset_x;
255            let d = t_offset_y;
256
257            let length = integers_between(p0x, p1x) + integers_between(p0y, p1y) + 1;
258
259            // Converting to sub-pixel space on th fly by multiplying with `PIXEL_WIDTH`.
260            (
261                order,
262                p0x * PIXEL_WIDTH as f32,
263                p0y * PIXEL_WIDTH as f32,
264                dx * PIXEL_WIDTH as f32,
265                dy * PIXEL_WIDTH as f32,
266                a,
267                b,
268                c,
269                d,
270                length,
271            )
272        });
273
274        ExtendTuple10::new((
275            &mut self.lines.orders,
276            &mut self.lines.x0,
277            &mut self.lines.y0,
278            &mut self.lines.dx,
279            &mut self.lines.dy,
280            &mut self.lines.a,
281            &mut self.lines.b,
282            &mut self.lines.c,
283            &mut self.lines.d,
284            &mut self.lines.lengths,
285        ))
286        .par_extend(par_iter);
287
288        prefix_sum(&mut self.lines.lengths);
289
290        self.lines
291    }
292
293    pub fn build_for_gpu<F>(mut self, layers: F) -> Lines
294    where
295        F: Fn(GeomId) -> Option<Layer> + Send + Sync,
296    {
297        fn transform_point(point: (f32, f32), transform: &AffineTransform) -> (f32, f32) {
298            (
299                transform.ux.mul_add(point.0, transform.vx.mul_add(point.1, transform.tx)),
300                transform.uy.mul_add(point.0, transform.vy.mul_add(point.1, transform.ty)),
301            )
302        }
303
304        if !self.lines.ids.is_empty() {
305            let point = match self.lines.ids[0].and_then(&layers) {
306                None | Some(Layer { is_enabled: false, .. } | Layer { order: None, .. }) => {
307                    Default::default()
308                }
309                Some(Layer { affine_transform: None, .. }) => [self.lines.x[0], self.lines.y[0]],
310                Some(Layer { affine_transform: Some(transform), .. }) => {
311                    let (x, y) = transform_point((self.lines.x[0], self.lines.y[0]), &transform.0);
312                    [x, y]
313                }
314            };
315            self.lines.points.push(point);
316        }
317
318        let ps_layers = self.lines.x.par_windows(2).with_min_len(MIN_LEN).zip_eq(
319            self.lines
320                .y
321                .par_windows(2)
322                .with_min_len(MIN_LEN)
323                .zip_eq(self.lines.ids.par_windows(2).with_min_len(MIN_LEN)),
324        );
325        let par_iter = ps_layers.map(|(xs, (ys, ids))| {
326            const NONE: u32 = u32::MAX;
327            let p0x = xs[0];
328            let p0y = ys[0];
329            let (p1x, p1y) = match ids[0].or(ids[1]).and_then(&layers) {
330                None | Some(Layer { is_enabled: false, .. } | Layer { order: None, .. }) => {
331                    (0.0, 0.0)
332                }
333                Some(Layer { affine_transform: None, .. }) => (xs[1], ys[1]),
334                Some(Layer { affine_transform: Some(transform), .. }) => {
335                    transform_point((xs[1], ys[1]), &transform.0)
336                }
337            };
338
339            let layer = match ids[0].and_then(&layers) {
340                Some(layer) => layer,
341                // Points at then end of line chain have to be transformed for the compute shader.
342                None => return (0, [p1x, p1y], NONE),
343            };
344
345            if let Layer { is_enabled: false, .. } = layer {
346                return (0, [p1x, p1y], NONE);
347            }
348
349            let order = match layer.order {
350                Some(order) => order.as_u32(),
351                None => return (0, [p1x, p1y], NONE),
352            };
353
354            let transform = layer.affine_transform.as_ref().map(|transform| &transform.0);
355
356            let (p0x, p0y) = if let Some(transform) = transform {
357                transform_point((p0x, p0y), transform)
358            } else {
359                (p0x, p0y)
360            };
361
362            if p0y == p1y {
363                return (0, [p1x, p1y], NONE);
364            }
365            let length = integers_between(p0x, p1x) + integers_between(p0y, p1y) + 1;
366
367            (length, [p1x, p1y], order)
368        });
369
370        ExtendTuple3::new((
371            &mut self.lines.lengths,
372            &mut self.lines.points,
373            &mut self.lines.orders,
374        ))
375        .par_extend(par_iter);
376
377        prefix_sum(&mut self.lines.lengths);
378
379        self.lines
380    }
381}
382
383// `x`, `y` and `ids` have the same size and encode polygonal chains.
384// In `ids`, `None` identifies the last element of a chain.
385//
386// `lines` and `lengths` have the same size and encode pixel segments
387// generators.
388#[derive(Debug, Default)]
389pub struct Lines {
390    pub x: Vec<f32>,
391    pub y: Vec<f32>,
392    pub ids: Vec<Option<GeomId>>,
393    pub orders: Vec<u32>,
394    pub x0: Vec<f32>,
395    pub y0: Vec<f32>,
396    pub dx: Vec<f32>,
397    pub dy: Vec<f32>,
398    pub a: Vec<f32>,
399    pub b: Vec<f32>,
400    pub c: Vec<f32>,
401    pub d: Vec<f32>,
402    pub points: Vec<[f32; 2]>,
403    pub lengths: Vec<u32>,
404}
405
406impl Lines {
407    #[inline]
408    pub fn unwrap(mut self) -> LinesBuilder {
409        self.orders.clear();
410        self.x0.clear();
411        self.y0.clear();
412        self.dx.clear();
413        self.dy.clear();
414        self.a.clear();
415        self.b.clear();
416        self.c.clear();
417        self.d.clear();
418        self.lengths.clear();
419        self.points.clear();
420
421        LinesBuilder { lines: self, ..Default::default() }
422    }
423
424    pub fn segments_count(&self) -> usize {
425        self.lengths.last().copied().unwrap_or_default() as usize
426    }
427
428    pub fn lines_count(&self) -> usize {
429        self.x.len() - 1
430    }
431}
surpass/lines.rs

surpass/
lines.rs
