epaint/
tessellator.rs

1//! Converts graphics primitives into textured triangles.
2//!
3//! This module converts lines, circles, text and more represented by [`Shape`]
4//! into textured triangles represented by [`Mesh`].
5
6#![allow(clippy::identity_op)]
7
8use crate::texture_atlas::PreparedDisc;
9use crate::{
10    color, emath, stroke, CircleShape, ClippedPrimitive, ClippedShape, Color32, CubicBezierShape,
11    EllipseShape, Mesh, PathShape, Primitive, QuadraticBezierShape, RectShape, Rounding, Shape,
12    Stroke, TextShape, TextureId, Vertex, WHITE_UV,
13};
14use emath::{pos2, remap, vec2, NumExt, Pos2, Rect, Rot2, Vec2};
15
16use self::color::ColorMode;
17use self::stroke::PathStroke;
18
19// ----------------------------------------------------------------------------
20
21#[allow(clippy::approx_constant)]
22mod precomputed_vertices {
23    // fn main() {
24    //     let n = 64;
25    //     println!("pub const CIRCLE_{}: [Vec2; {}] = [", n, n+1);
26    //     for i in 0..=n {
27    //         let a = std::f64::consts::TAU * i as f64 / n as f64;
28    //         println!("    vec2({:.06}, {:.06}),", a.cos(), a.sin());
29    //     }
30    //     println!("];")
31    // }
32
33    use emath::{vec2, Vec2};
34
35    pub const CIRCLE_8: [Vec2; 9] = [
36        vec2(1.000000, 0.000000),
37        vec2(0.707107, 0.707107),
38        vec2(0.000000, 1.000000),
39        vec2(-0.707107, 0.707107),
40        vec2(-1.000000, 0.000000),
41        vec2(-0.707107, -0.707107),
42        vec2(0.000000, -1.000000),
43        vec2(0.707107, -0.707107),
44        vec2(1.000000, 0.000000),
45    ];
46
47    pub const CIRCLE_16: [Vec2; 17] = [
48        vec2(1.000000, 0.000000),
49        vec2(0.923880, 0.382683),
50        vec2(0.707107, 0.707107),
51        vec2(0.382683, 0.923880),
52        vec2(0.000000, 1.000000),
53        vec2(-0.382684, 0.923880),
54        vec2(-0.707107, 0.707107),
55        vec2(-0.923880, 0.382683),
56        vec2(-1.000000, 0.000000),
57        vec2(-0.923880, -0.382683),
58        vec2(-0.707107, -0.707107),
59        vec2(-0.382684, -0.923880),
60        vec2(0.000000, -1.000000),
61        vec2(0.382684, -0.923879),
62        vec2(0.707107, -0.707107),
63        vec2(0.923880, -0.382683),
64        vec2(1.000000, 0.000000),
65    ];
66
67    pub const CIRCLE_32: [Vec2; 33] = [
68        vec2(1.000000, 0.000000),
69        vec2(0.980785, 0.195090),
70        vec2(0.923880, 0.382683),
71        vec2(0.831470, 0.555570),
72        vec2(0.707107, 0.707107),
73        vec2(0.555570, 0.831470),
74        vec2(0.382683, 0.923880),
75        vec2(0.195090, 0.980785),
76        vec2(0.000000, 1.000000),
77        vec2(-0.195090, 0.980785),
78        vec2(-0.382683, 0.923880),
79        vec2(-0.555570, 0.831470),
80        vec2(-0.707107, 0.707107),
81        vec2(-0.831470, 0.555570),
82        vec2(-0.923880, 0.382683),
83        vec2(-0.980785, 0.195090),
84        vec2(-1.000000, 0.000000),
85        vec2(-0.980785, -0.195090),
86        vec2(-0.923880, -0.382683),
87        vec2(-0.831470, -0.555570),
88        vec2(-0.707107, -0.707107),
89        vec2(-0.555570, -0.831470),
90        vec2(-0.382683, -0.923880),
91        vec2(-0.195090, -0.980785),
92        vec2(-0.000000, -1.000000),
93        vec2(0.195090, -0.980785),
94        vec2(0.382683, -0.923880),
95        vec2(0.555570, -0.831470),
96        vec2(0.707107, -0.707107),
97        vec2(0.831470, -0.555570),
98        vec2(0.923880, -0.382683),
99        vec2(0.980785, -0.195090),
100        vec2(1.000000, -0.000000),
101    ];
102
103    pub const CIRCLE_64: [Vec2; 65] = [
104        vec2(1.000000, 0.000000),
105        vec2(0.995185, 0.098017),
106        vec2(0.980785, 0.195090),
107        vec2(0.956940, 0.290285),
108        vec2(0.923880, 0.382683),
109        vec2(0.881921, 0.471397),
110        vec2(0.831470, 0.555570),
111        vec2(0.773010, 0.634393),
112        vec2(0.707107, 0.707107),
113        vec2(0.634393, 0.773010),
114        vec2(0.555570, 0.831470),
115        vec2(0.471397, 0.881921),
116        vec2(0.382683, 0.923880),
117        vec2(0.290285, 0.956940),
118        vec2(0.195090, 0.980785),
119        vec2(0.098017, 0.995185),
120        vec2(0.000000, 1.000000),
121        vec2(-0.098017, 0.995185),
122        vec2(-0.195090, 0.980785),
123        vec2(-0.290285, 0.956940),
124        vec2(-0.382683, 0.923880),
125        vec2(-0.471397, 0.881921),
126        vec2(-0.555570, 0.831470),
127        vec2(-0.634393, 0.773010),
128        vec2(-0.707107, 0.707107),
129        vec2(-0.773010, 0.634393),
130        vec2(-0.831470, 0.555570),
131        vec2(-0.881921, 0.471397),
132        vec2(-0.923880, 0.382683),
133        vec2(-0.956940, 0.290285),
134        vec2(-0.980785, 0.195090),
135        vec2(-0.995185, 0.098017),
136        vec2(-1.000000, 0.000000),
137        vec2(-0.995185, -0.098017),
138        vec2(-0.980785, -0.195090),
139        vec2(-0.956940, -0.290285),
140        vec2(-0.923880, -0.382683),
141        vec2(-0.881921, -0.471397),
142        vec2(-0.831470, -0.555570),
143        vec2(-0.773010, -0.634393),
144        vec2(-0.707107, -0.707107),
145        vec2(-0.634393, -0.773010),
146        vec2(-0.555570, -0.831470),
147        vec2(-0.471397, -0.881921),
148        vec2(-0.382683, -0.923880),
149        vec2(-0.290285, -0.956940),
150        vec2(-0.195090, -0.980785),
151        vec2(-0.098017, -0.995185),
152        vec2(-0.000000, -1.000000),
153        vec2(0.098017, -0.995185),
154        vec2(0.195090, -0.980785),
155        vec2(0.290285, -0.956940),
156        vec2(0.382683, -0.923880),
157        vec2(0.471397, -0.881921),
158        vec2(0.555570, -0.831470),
159        vec2(0.634393, -0.773010),
160        vec2(0.707107, -0.707107),
161        vec2(0.773010, -0.634393),
162        vec2(0.831470, -0.555570),
163        vec2(0.881921, -0.471397),
164        vec2(0.923880, -0.382683),
165        vec2(0.956940, -0.290285),
166        vec2(0.980785, -0.195090),
167        vec2(0.995185, -0.098017),
168        vec2(1.000000, -0.000000),
169    ];
170
171    pub const CIRCLE_128: [Vec2; 129] = [
172        vec2(1.000000, 0.000000),
173        vec2(0.998795, 0.049068),
174        vec2(0.995185, 0.098017),
175        vec2(0.989177, 0.146730),
176        vec2(0.980785, 0.195090),
177        vec2(0.970031, 0.242980),
178        vec2(0.956940, 0.290285),
179        vec2(0.941544, 0.336890),
180        vec2(0.923880, 0.382683),
181        vec2(0.903989, 0.427555),
182        vec2(0.881921, 0.471397),
183        vec2(0.857729, 0.514103),
184        vec2(0.831470, 0.555570),
185        vec2(0.803208, 0.595699),
186        vec2(0.773010, 0.634393),
187        vec2(0.740951, 0.671559),
188        vec2(0.707107, 0.707107),
189        vec2(0.671559, 0.740951),
190        vec2(0.634393, 0.773010),
191        vec2(0.595699, 0.803208),
192        vec2(0.555570, 0.831470),
193        vec2(0.514103, 0.857729),
194        vec2(0.471397, 0.881921),
195        vec2(0.427555, 0.903989),
196        vec2(0.382683, 0.923880),
197        vec2(0.336890, 0.941544),
198        vec2(0.290285, 0.956940),
199        vec2(0.242980, 0.970031),
200        vec2(0.195090, 0.980785),
201        vec2(0.146730, 0.989177),
202        vec2(0.098017, 0.995185),
203        vec2(0.049068, 0.998795),
204        vec2(0.000000, 1.000000),
205        vec2(-0.049068, 0.998795),
206        vec2(-0.098017, 0.995185),
207        vec2(-0.146730, 0.989177),
208        vec2(-0.195090, 0.980785),
209        vec2(-0.242980, 0.970031),
210        vec2(-0.290285, 0.956940),
211        vec2(-0.336890, 0.941544),
212        vec2(-0.382683, 0.923880),
213        vec2(-0.427555, 0.903989),
214        vec2(-0.471397, 0.881921),
215        vec2(-0.514103, 0.857729),
216        vec2(-0.555570, 0.831470),
217        vec2(-0.595699, 0.803208),
218        vec2(-0.634393, 0.773010),
219        vec2(-0.671559, 0.740951),
220        vec2(-0.707107, 0.707107),
221        vec2(-0.740951, 0.671559),
222        vec2(-0.773010, 0.634393),
223        vec2(-0.803208, 0.595699),
224        vec2(-0.831470, 0.555570),
225        vec2(-0.857729, 0.514103),
226        vec2(-0.881921, 0.471397),
227        vec2(-0.903989, 0.427555),
228        vec2(-0.923880, 0.382683),
229        vec2(-0.941544, 0.336890),
230        vec2(-0.956940, 0.290285),
231        vec2(-0.970031, 0.242980),
232        vec2(-0.980785, 0.195090),
233        vec2(-0.989177, 0.146730),
234        vec2(-0.995185, 0.098017),
235        vec2(-0.998795, 0.049068),
236        vec2(-1.000000, 0.000000),
237        vec2(-0.998795, -0.049068),
238        vec2(-0.995185, -0.098017),
239        vec2(-0.989177, -0.146730),
240        vec2(-0.980785, -0.195090),
241        vec2(-0.970031, -0.242980),
242        vec2(-0.956940, -0.290285),
243        vec2(-0.941544, -0.336890),
244        vec2(-0.923880, -0.382683),
245        vec2(-0.903989, -0.427555),
246        vec2(-0.881921, -0.471397),
247        vec2(-0.857729, -0.514103),
248        vec2(-0.831470, -0.555570),
249        vec2(-0.803208, -0.595699),
250        vec2(-0.773010, -0.634393),
251        vec2(-0.740951, -0.671559),
252        vec2(-0.707107, -0.707107),
253        vec2(-0.671559, -0.740951),
254        vec2(-0.634393, -0.773010),
255        vec2(-0.595699, -0.803208),
256        vec2(-0.555570, -0.831470),
257        vec2(-0.514103, -0.857729),
258        vec2(-0.471397, -0.881921),
259        vec2(-0.427555, -0.903989),
260        vec2(-0.382683, -0.923880),
261        vec2(-0.336890, -0.941544),
262        vec2(-0.290285, -0.956940),
263        vec2(-0.242980, -0.970031),
264        vec2(-0.195090, -0.980785),
265        vec2(-0.146730, -0.989177),
266        vec2(-0.098017, -0.995185),
267        vec2(-0.049068, -0.998795),
268        vec2(-0.000000, -1.000000),
269        vec2(0.049068, -0.998795),
270        vec2(0.098017, -0.995185),
271        vec2(0.146730, -0.989177),
272        vec2(0.195090, -0.980785),
273        vec2(0.242980, -0.970031),
274        vec2(0.290285, -0.956940),
275        vec2(0.336890, -0.941544),
276        vec2(0.382683, -0.923880),
277        vec2(0.427555, -0.903989),
278        vec2(0.471397, -0.881921),
279        vec2(0.514103, -0.857729),
280        vec2(0.555570, -0.831470),
281        vec2(0.595699, -0.803208),
282        vec2(0.634393, -0.773010),
283        vec2(0.671559, -0.740951),
284        vec2(0.707107, -0.707107),
285        vec2(0.740951, -0.671559),
286        vec2(0.773010, -0.634393),
287        vec2(0.803208, -0.595699),
288        vec2(0.831470, -0.555570),
289        vec2(0.857729, -0.514103),
290        vec2(0.881921, -0.471397),
291        vec2(0.903989, -0.427555),
292        vec2(0.923880, -0.382683),
293        vec2(0.941544, -0.336890),
294        vec2(0.956940, -0.290285),
295        vec2(0.970031, -0.242980),
296        vec2(0.980785, -0.195090),
297        vec2(0.989177, -0.146730),
298        vec2(0.995185, -0.098017),
299        vec2(0.998795, -0.049068),
300        vec2(1.000000, -0.000000),
301    ];
302}
303
304// ----------------------------------------------------------------------------
305
306#[derive(Clone, Copy, Debug, Default, PartialEq)]
307struct PathPoint {
308    pos: Pos2,
309
310    /// For filled paths the normal is used for anti-aliasing (both strokes and filled areas).
311    ///
312    /// For strokes the normal is also used for giving thickness to the path
313    /// (i.e. in what direction to expand).
314    ///
315    /// The normal could be estimated by differences between successive points,
316    /// but that would be less accurate (and in some cases slower).
317    ///
318    /// Normals are normally unit-length.
319    normal: Vec2,
320}
321
322/// A connected line (without thickness or gaps) which can be tessellated
323/// to either to a stroke (with thickness) or a filled convex area.
324/// Used as a scratch-pad during tessellation.
325#[derive(Clone, Debug, Default)]
326pub struct Path(Vec<PathPoint>);
327
328impl Path {
329    #[inline(always)]
330    pub fn clear(&mut self) {
331        self.0.clear();
332    }
333
334    #[inline(always)]
335    pub fn reserve(&mut self, additional: usize) {
336        self.0.reserve(additional);
337    }
338
339    #[inline(always)]
340    pub fn add_point(&mut self, pos: Pos2, normal: Vec2) {
341        self.0.push(PathPoint { pos, normal });
342    }
343
344    pub fn add_circle(&mut self, center: Pos2, radius: f32) {
345        use precomputed_vertices::{CIRCLE_128, CIRCLE_16, CIRCLE_32, CIRCLE_64, CIRCLE_8};
346
347        // These cutoffs are based on a high-dpi display. TODO(emilk): use pixels_per_point here?
348        // same cutoffs as in add_circle_quadrant
349
350        if radius <= 2.0 {
351            self.0.extend(CIRCLE_8.iter().map(|&n| PathPoint {
352                pos: center + radius * n,
353                normal: n,
354            }));
355        } else if radius <= 5.0 {
356            self.0.extend(CIRCLE_16.iter().map(|&n| PathPoint {
357                pos: center + radius * n,
358                normal: n,
359            }));
360        } else if radius < 18.0 {
361            self.0.extend(CIRCLE_32.iter().map(|&n| PathPoint {
362                pos: center + radius * n,
363                normal: n,
364            }));
365        } else if radius < 50.0 {
366            self.0.extend(CIRCLE_64.iter().map(|&n| PathPoint {
367                pos: center + radius * n,
368                normal: n,
369            }));
370        } else {
371            self.0.extend(CIRCLE_128.iter().map(|&n| PathPoint {
372                pos: center + radius * n,
373                normal: n,
374            }));
375        }
376    }
377
378    pub fn add_line_segment(&mut self, points: [Pos2; 2]) {
379        self.reserve(2);
380        let normal = (points[1] - points[0]).normalized().rot90();
381        self.add_point(points[0], normal);
382        self.add_point(points[1], normal);
383    }
384
385    pub fn add_open_points(&mut self, points: &[Pos2]) {
386        let n = points.len();
387        assert!(n >= 2);
388
389        if n == 2 {
390            // Common case optimization:
391            self.add_line_segment([points[0], points[1]]);
392        } else {
393            self.reserve(n);
394            self.add_point(points[0], (points[1] - points[0]).normalized().rot90());
395            let mut n0 = (points[1] - points[0]).normalized().rot90();
396            for i in 1..n - 1 {
397                let mut n1 = (points[i + 1] - points[i]).normalized().rot90();
398
399                // Handle duplicated points (but not triplicated…):
400                if n0 == Vec2::ZERO {
401                    n0 = n1;
402                } else if n1 == Vec2::ZERO {
403                    n1 = n0;
404                }
405
406                let normal = (n0 + n1) / 2.0;
407                let length_sq = normal.length_sq();
408                let right_angle_length_sq = 0.5;
409                let sharper_than_a_right_angle = length_sq < right_angle_length_sq;
410                if sharper_than_a_right_angle {
411                    // cut off the sharp corner
412                    let center_normal = normal.normalized();
413                    let n0c = (n0 + center_normal) / 2.0;
414                    let n1c = (n1 + center_normal) / 2.0;
415                    self.add_point(points[i], n0c / n0c.length_sq());
416                    self.add_point(points[i], n1c / n1c.length_sq());
417                } else {
418                    // miter join
419                    self.add_point(points[i], normal / length_sq);
420                }
421
422                n0 = n1;
423            }
424            self.add_point(
425                points[n - 1],
426                (points[n - 1] - points[n - 2]).normalized().rot90(),
427            );
428        }
429    }
430
431    pub fn add_line_loop(&mut self, points: &[Pos2]) {
432        let n = points.len();
433        assert!(n >= 2);
434        self.reserve(n);
435
436        let mut n0 = (points[0] - points[n - 1]).normalized().rot90();
437
438        for i in 0..n {
439            let next_i = if i + 1 == n { 0 } else { i + 1 };
440            let mut n1 = (points[next_i] - points[i]).normalized().rot90();
441
442            // Handle duplicated points (but not triplicated…):
443            if n0 == Vec2::ZERO {
444                n0 = n1;
445            } else if n1 == Vec2::ZERO {
446                n1 = n0;
447            }
448
449            let normal = (n0 + n1) / 2.0;
450            let length_sq = normal.length_sq();
451
452            // We can't just cut off corners for filled shapes like this,
453            // because the feather will both expand and contract the corner along the provided normals
454            // to make sure it doesn't grow, and the shrinking will make the inner points cross each other.
455            //
456            // A better approach is to shrink the vertices in by half the feather-width here
457            // and then only expand during feathering.
458            //
459            // See https://github.com/emilk/egui/issues/1226
460            const CUT_OFF_SHARP_CORNERS: bool = false;
461
462            let right_angle_length_sq = 0.5;
463            let sharper_than_a_right_angle = length_sq < right_angle_length_sq;
464            if CUT_OFF_SHARP_CORNERS && sharper_than_a_right_angle {
465                // cut off the sharp corner
466                let center_normal = normal.normalized();
467                let n0c = (n0 + center_normal) / 2.0;
468                let n1c = (n1 + center_normal) / 2.0;
469                self.add_point(points[i], n0c / n0c.length_sq());
470                self.add_point(points[i], n1c / n1c.length_sq());
471            } else {
472                // miter join
473                self.add_point(points[i], normal / length_sq);
474            }
475
476            n0 = n1;
477        }
478    }
479
480    /// Open-ended.
481    pub fn stroke_open(&mut self, feathering: f32, stroke: &PathStroke, out: &mut Mesh) {
482        stroke_path(feathering, &mut self.0, PathType::Open, stroke, out);
483    }
484
485    /// A closed path (returning to the first point).
486    pub fn stroke_closed(&mut self, feathering: f32, stroke: &PathStroke, out: &mut Mesh) {
487        stroke_path(feathering, &mut self.0, PathType::Closed, stroke, out);
488    }
489
490    pub fn stroke(
491        &mut self,
492        feathering: f32,
493        path_type: PathType,
494        stroke: &PathStroke,
495        out: &mut Mesh,
496    ) {
497        stroke_path(feathering, &mut self.0, path_type, stroke, out);
498    }
499
500    /// The path is taken to be closed (i.e. returning to the start again).
501    ///
502    /// Calling this may reverse the vertices in the path if they are wrong winding order.
503    ///
504    /// The preferred winding order is clockwise.
505    ///
506    /// The stroke colors is used for color-correct feathering.
507    pub fn fill(&mut self, feathering: f32, color: Color32, stroke: &PathStroke, out: &mut Mesh) {
508        fill_closed_path(feathering, &mut self.0, color, stroke, out);
509    }
510
511    /// Like [`Self::fill`] but with texturing.
512    ///
513    /// The `uv_from_pos` is called for each vertex position.
514    pub fn fill_with_uv(
515        &mut self,
516        feathering: f32,
517        color: Color32,
518        texture_id: TextureId,
519        uv_from_pos: impl Fn(Pos2) -> Pos2,
520        out: &mut Mesh,
521    ) {
522        fill_closed_path_with_uv(feathering, &mut self.0, color, texture_id, uv_from_pos, out);
523    }
524}
525
526pub mod path {
527    //! Helpers for constructing paths
528    use crate::shape::Rounding;
529    use emath::{pos2, Pos2, Rect};
530
531    /// overwrites existing points
532    pub fn rounded_rectangle(path: &mut Vec<Pos2>, rect: Rect, rounding: Rounding) {
533        path.clear();
534
535        let min = rect.min;
536        let max = rect.max;
537
538        let r = clamp_rounding(rounding, rect);
539
540        if r == Rounding::ZERO {
541            path.reserve(4);
542            path.push(pos2(min.x, min.y)); // left top
543            path.push(pos2(max.x, min.y)); // right top
544            path.push(pos2(max.x, max.y)); // right bottom
545            path.push(pos2(min.x, max.y)); // left bottom
546        } else {
547            // We need to avoid duplicated vertices, because that leads to visual artifacts later.
548            // Duplicated vertices can happen when one side is all rounding, with no straight edge between.
549            let eps = f32::EPSILON * rect.size().max_elem();
550
551            add_circle_quadrant(path, pos2(max.x - r.se, max.y - r.se), r.se, 0.0); // south east
552
553            if rect.width() <= r.se + r.sw + eps {
554                path.pop(); // avoid duplicated vertex
555            }
556
557            add_circle_quadrant(path, pos2(min.x + r.sw, max.y - r.sw), r.sw, 1.0); // south west
558
559            if rect.height() <= r.sw + r.nw + eps {
560                path.pop(); // avoid duplicated vertex
561            }
562
563            add_circle_quadrant(path, pos2(min.x + r.nw, min.y + r.nw), r.nw, 2.0); // north west
564
565            if rect.width() <= r.nw + r.ne + eps {
566                path.pop(); // avoid duplicated vertex
567            }
568
569            add_circle_quadrant(path, pos2(max.x - r.ne, min.y + r.ne), r.ne, 3.0); // north east
570
571            if rect.height() <= r.ne + r.se + eps {
572                path.pop(); // avoid duplicated vertex
573            }
574        }
575    }
576
577    /// Add one quadrant of a circle
578    ///
579    /// * quadrant 0: right bottom
580    /// * quadrant 1: left bottom
581    /// * quadrant 2: left top
582    /// * quadrant 3: right top
583    //
584    // Derivation:
585    //
586    // * angle 0 * TAU / 4 = right
587    //   - quadrant 0: right bottom
588    // * angle 1 * TAU / 4 = bottom
589    //   - quadrant 1: left bottom
590    // * angle 2 * TAU / 4 = left
591    //   - quadrant 2: left top
592    // * angle 3 * TAU / 4 = top
593    //   - quadrant 3: right top
594    // * angle 4 * TAU / 4 = right
595    pub fn add_circle_quadrant(path: &mut Vec<Pos2>, center: Pos2, radius: f32, quadrant: f32) {
596        use super::precomputed_vertices::{CIRCLE_128, CIRCLE_16, CIRCLE_32, CIRCLE_64, CIRCLE_8};
597
598        // These cutoffs are based on a high-dpi display. TODO(emilk): use pixels_per_point here?
599        // same cutoffs as in add_circle
600
601        if radius <= 0.0 {
602            path.push(center);
603        } else if radius <= 2.0 {
604            let offset = quadrant as usize * 2;
605            let quadrant_vertices = &CIRCLE_8[offset..=offset + 2];
606            path.extend(quadrant_vertices.iter().map(|&n| center + radius * n));
607        } else if radius <= 5.0 {
608            let offset = quadrant as usize * 4;
609            let quadrant_vertices = &CIRCLE_16[offset..=offset + 4];
610            path.extend(quadrant_vertices.iter().map(|&n| center + radius * n));
611        } else if radius < 18.0 {
612            let offset = quadrant as usize * 8;
613            let quadrant_vertices = &CIRCLE_32[offset..=offset + 8];
614            path.extend(quadrant_vertices.iter().map(|&n| center + radius * n));
615        } else if radius < 50.0 {
616            let offset = quadrant as usize * 16;
617            let quadrant_vertices = &CIRCLE_64[offset..=offset + 16];
618            path.extend(quadrant_vertices.iter().map(|&n| center + radius * n));
619        } else {
620            let offset = quadrant as usize * 32;
621            let quadrant_vertices = &CIRCLE_128[offset..=offset + 32];
622            path.extend(quadrant_vertices.iter().map(|&n| center + radius * n));
623        }
624    }
625
626    // Ensures the radius of each corner is within a valid range
627    fn clamp_rounding(rounding: Rounding, rect: Rect) -> Rounding {
628        let half_width = rect.width() * 0.5;
629        let half_height = rect.height() * 0.5;
630        let max_cr = half_width.min(half_height);
631        rounding.at_most(max_cr).at_least(0.0)
632    }
633}
634
635// ----------------------------------------------------------------------------
636
637#[derive(Clone, Copy, PartialEq, Eq)]
638pub enum PathType {
639    Open,
640    Closed,
641}
642
643/// Tessellation quality options
644#[derive(Clone, Copy, Debug, PartialEq)]
645#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
646#[cfg_attr(feature = "serde", serde(default))]
647pub struct TessellationOptions {
648    /// Use "feathering" to smooth out the edges of shapes as a form of anti-aliasing.
649    ///
650    /// Feathering works by making each edge into a thin gradient into transparency.
651    /// The size of this edge is controlled by [`Self::feathering_size_in_pixels`].
652    ///
653    /// This makes shapes appear smoother, but requires more triangles and is therefore slower.
654    ///
655    /// This setting does not affect text.
656    ///
657    /// Default: `true`.
658    pub feathering: bool,
659
660    /// The size of the feathering, in physical pixels.
661    ///
662    /// The default, and suggested, value for this is `1.0`.
663    /// If you use a larger value, edges will appear blurry.
664    pub feathering_size_in_pixels: f32,
665
666    /// If `true` (default) cull certain primitives before tessellating them.
667    /// This likely makes
668    pub coarse_tessellation_culling: bool,
669
670    /// If `true`, small filled circled will be optimized by using pre-rasterized circled
671    /// from the font atlas.
672    pub prerasterized_discs: bool,
673
674    /// If `true` (default) align text to mesh grid.
675    /// This makes the text sharper on most platforms.
676    pub round_text_to_pixels: bool,
677
678    /// Output the clip rectangles to be painted.
679    pub debug_paint_clip_rects: bool,
680
681    /// Output the text-containing rectangles.
682    pub debug_paint_text_rects: bool,
683
684    /// If true, no clipping will be done.
685    pub debug_ignore_clip_rects: bool,
686
687    /// The maximum distance between the original curve and the flattened curve.
688    pub bezier_tolerance: f32,
689
690    /// The default value will be 1.0e-5, it will be used during float compare.
691    pub epsilon: f32,
692
693    /// If `rayon` feature is activated, should we parallelize tessellation?
694    pub parallel_tessellation: bool,
695
696    /// If `true`, invalid meshes will be silently ignored.
697    /// If `false`, invalid meshes will cause a panic.
698    ///
699    /// The default is `false` to save performance.
700    pub validate_meshes: bool,
701}
702
703impl Default for TessellationOptions {
704    fn default() -> Self {
705        Self {
706            feathering: true,
707            feathering_size_in_pixels: 1.0,
708            coarse_tessellation_culling: true,
709            prerasterized_discs: true,
710            round_text_to_pixels: true,
711            debug_paint_text_rects: false,
712            debug_paint_clip_rects: false,
713            debug_ignore_clip_rects: false,
714            bezier_tolerance: 0.1,
715            epsilon: 1.0e-5,
716            parallel_tessellation: true,
717            validate_meshes: false,
718        }
719    }
720}
721
722fn cw_signed_area(path: &[PathPoint]) -> f64 {
723    if let Some(last) = path.last() {
724        let mut previous = last.pos;
725        let mut area = 0.0;
726        for p in path {
727            area += (previous.x * p.pos.y - p.pos.x * previous.y) as f64;
728            previous = p.pos;
729        }
730        area
731    } else {
732        0.0
733    }
734}
735
736/// Tessellate the given convex area into a polygon.
737///
738/// Calling this may reverse the vertices in the path if they are wrong winding order.
739///
740/// The preferred winding order is clockwise.
741///
742/// A stroke is required so that the fill's feathering can fade to the right color. You can pass `&PathStroke::NONE` if
743/// this path won't be stroked.
744fn fill_closed_path(
745    feathering: f32,
746    path: &mut [PathPoint],
747    color: Color32,
748    stroke: &PathStroke,
749    out: &mut Mesh,
750) {
751    if color == Color32::TRANSPARENT {
752        return;
753    }
754
755    // TODO(juancampa): This bounding box is computed twice per shape: once here and another when tessellating the
756    // stroke, consider hoisting that logic to the tessellator/scratchpad.
757    let bbox = Rect::from_points(&path.iter().map(|p| p.pos).collect::<Vec<Pos2>>())
758        .expand((stroke.width / 2.0) + feathering);
759
760    let stroke_color = &stroke.color;
761    let get_stroke_color: Box<dyn Fn(Pos2) -> Color32> = match stroke_color {
762        ColorMode::Solid(col) => Box::new(|_pos: Pos2| *col),
763        ColorMode::UV(fun) => Box::new(|pos: Pos2| fun(bbox, pos)),
764    };
765
766    let n = path.len() as u32;
767    if feathering > 0.0 {
768        if cw_signed_area(path) < 0.0 {
769            // Wrong winding order - fix:
770            path.reverse();
771            for point in &mut *path {
772                point.normal = -point.normal;
773            }
774        }
775
776        out.reserve_triangles(3 * n as usize);
777        out.reserve_vertices(2 * n as usize);
778        let idx_inner = out.vertices.len() as u32;
779        let idx_outer = idx_inner + 1;
780
781        // The fill:
782        for i in 2..n {
783            out.add_triangle(idx_inner + 2 * (i - 1), idx_inner, idx_inner + 2 * i);
784        }
785
786        // The feathering:
787        let mut i0 = n - 1;
788        for i1 in 0..n {
789            let p1 = &path[i1 as usize];
790            let dm = 0.5 * feathering * p1.normal;
791
792            let pos_inner = p1.pos - dm;
793            let pos_outer = p1.pos + dm;
794            let color_outer = get_stroke_color(pos_outer);
795
796            out.colored_vertex(pos_inner, color);
797            out.colored_vertex(pos_outer, color_outer);
798            out.add_triangle(idx_inner + i1 * 2, idx_inner + i0 * 2, idx_outer + 2 * i0);
799            out.add_triangle(idx_outer + i0 * 2, idx_outer + i1 * 2, idx_inner + 2 * i1);
800            i0 = i1;
801        }
802    } else {
803        out.reserve_triangles(n as usize);
804        let idx = out.vertices.len() as u32;
805        out.vertices.extend(path.iter().map(|p| Vertex {
806            pos: p.pos,
807            uv: WHITE_UV,
808            color,
809        }));
810        for i in 2..n {
811            out.add_triangle(idx, idx + i - 1, idx + i);
812        }
813    }
814}
815
816/// Like [`fill_closed_path`] but with texturing.
817///
818/// The `uv_from_pos` is called for each vertex position.
819fn fill_closed_path_with_uv(
820    feathering: f32,
821    path: &mut [PathPoint],
822    color: Color32,
823    texture_id: TextureId,
824    uv_from_pos: impl Fn(Pos2) -> Pos2,
825    out: &mut Mesh,
826) {
827    if color == Color32::TRANSPARENT {
828        return;
829    }
830
831    if out.is_empty() {
832        out.texture_id = texture_id;
833    } else {
834        assert_eq!(
835            out.texture_id, texture_id,
836            "Mixing different `texture_id` in the same "
837        );
838    }
839
840    let n = path.len() as u32;
841    if feathering > 0.0 {
842        if cw_signed_area(path) < 0.0 {
843            // Wrong winding order - fix:
844            path.reverse();
845            for point in &mut *path {
846                point.normal = -point.normal;
847            }
848        }
849
850        out.reserve_triangles(3 * n as usize);
851        out.reserve_vertices(2 * n as usize);
852        let color_outer = Color32::TRANSPARENT;
853        let idx_inner = out.vertices.len() as u32;
854        let idx_outer = idx_inner + 1;
855
856        // The fill:
857        for i in 2..n {
858            out.add_triangle(idx_inner + 2 * (i - 1), idx_inner, idx_inner + 2 * i);
859        }
860
861        // The feathering:
862        let mut i0 = n - 1;
863        for i1 in 0..n {
864            let p1 = &path[i1 as usize];
865            let dm = 0.5 * feathering * p1.normal;
866
867            let pos = p1.pos - dm;
868            out.vertices.push(Vertex {
869                pos,
870                uv: uv_from_pos(pos),
871                color,
872            });
873
874            let pos = p1.pos + dm;
875            out.vertices.push(Vertex {
876                pos,
877                uv: uv_from_pos(pos),
878                color: color_outer,
879            });
880
881            out.add_triangle(idx_inner + i1 * 2, idx_inner + i0 * 2, idx_outer + 2 * i0);
882            out.add_triangle(idx_outer + i0 * 2, idx_outer + i1 * 2, idx_inner + 2 * i1);
883            i0 = i1;
884        }
885    } else {
886        out.reserve_triangles(n as usize);
887        let idx = out.vertices.len() as u32;
888        out.vertices.extend(path.iter().map(|p| Vertex {
889            pos: p.pos,
890            uv: uv_from_pos(p.pos),
891            color,
892        }));
893        for i in 2..n {
894            out.add_triangle(idx, idx + i - 1, idx + i);
895        }
896    }
897}
898
899/// Translate a point along their normals according to the stroke kind.
900#[inline(always)]
901fn translate_stroke_point(p: &mut PathPoint, stroke: &PathStroke) {
902    match stroke.kind {
903        stroke::StrokeKind::Middle => { /* Nothingn to do */ }
904        stroke::StrokeKind::Outside => {
905            p.pos += p.normal * stroke.width * 0.5;
906        }
907        stroke::StrokeKind::Inside => {
908            p.pos -= p.normal * stroke.width * 0.5;
909        }
910    }
911}
912
913/// Tessellate the given path as a stroke with thickness.
914fn stroke_path(
915    feathering: f32,
916    path: &mut [PathPoint],
917    path_type: PathType,
918    stroke: &PathStroke,
919    out: &mut Mesh,
920) {
921    let n = path.len() as u32;
922
923    if stroke.is_empty() || n < 2 {
924        return;
925    }
926
927    let idx = out.vertices.len() as u32;
928
929    // Translate the points along their normals if the stroke is outside or inside
930    if stroke.kind != stroke::StrokeKind::Middle {
931        path.iter_mut()
932            .for_each(|p| translate_stroke_point(p, stroke));
933    }
934
935    // expand the bounding box to include the thickness of the path
936    let bbox = Rect::from_points(&path.iter().map(|p| p.pos).collect::<Vec<Pos2>>())
937        .expand((stroke.width / 2.0) + feathering);
938
939    let get_color = |col: &ColorMode, pos: Pos2| match col {
940        ColorMode::Solid(col) => *col,
941        ColorMode::UV(fun) => fun(bbox, pos),
942    };
943
944    if feathering > 0.0 {
945        let color_inner = &stroke.color;
946        let color_outer = Color32::TRANSPARENT;
947
948        let thin_line = stroke.width <= feathering;
949        if thin_line {
950            /*
951            We paint the line using three edges: outer, inner, outer.
952
953            .       o   i   o      outer, inner, outer
954            .       |---|          feathering (pixel width)
955            */
956
957            // Fade out as it gets thinner:
958            if let ColorMode::Solid(col) = color_inner {
959                let color_inner = mul_color(*col, stroke.width / feathering);
960                if color_inner == Color32::TRANSPARENT {
961                    return;
962                }
963            }
964
965            out.reserve_triangles(4 * n as usize);
966            out.reserve_vertices(3 * n as usize);
967
968            let mut i0 = n - 1;
969            for i1 in 0..n {
970                let connect_with_previous = path_type == PathType::Closed || i1 > 0;
971                let p1 = path[i1 as usize];
972                let p = p1.pos;
973                let n = p1.normal;
974                out.colored_vertex(p + n * feathering, color_outer);
975                out.colored_vertex(
976                    p,
977                    mul_color(get_color(color_inner, p), stroke.width / feathering),
978                );
979                out.colored_vertex(p - n * feathering, color_outer);
980
981                if connect_with_previous {
982                    out.add_triangle(idx + 3 * i0 + 0, idx + 3 * i0 + 1, idx + 3 * i1 + 0);
983                    out.add_triangle(idx + 3 * i0 + 1, idx + 3 * i1 + 0, idx + 3 * i1 + 1);
984
985                    out.add_triangle(idx + 3 * i0 + 1, idx + 3 * i0 + 2, idx + 3 * i1 + 1);
986                    out.add_triangle(idx + 3 * i0 + 2, idx + 3 * i1 + 1, idx + 3 * i1 + 2);
987                }
988                i0 = i1;
989            }
990        } else {
991            // thick anti-aliased line
992
993            /*
994            We paint the line using four edges: outer, inner, inner, outer
995
996            .       o   i     p    i   o   outer, inner, point, inner, outer
997            .       |---|                  feathering (pixel width)
998            .         |--------------|     width
999            .       |---------|            outer_rad
1000            .           |-----|            inner_rad
1001            */
1002
1003            let inner_rad = 0.5 * (stroke.width - feathering);
1004            let outer_rad = 0.5 * (stroke.width + feathering);
1005
1006            match path_type {
1007                PathType::Closed => {
1008                    out.reserve_triangles(6 * n as usize);
1009                    out.reserve_vertices(4 * n as usize);
1010
1011                    let mut i0 = n - 1;
1012                    for i1 in 0..n {
1013                        let p1 = path[i1 as usize];
1014                        let p = p1.pos;
1015                        let n = p1.normal;
1016                        out.colored_vertex(p + n * outer_rad, color_outer);
1017                        out.colored_vertex(
1018                            p + n * inner_rad,
1019                            get_color(color_inner, p + n * inner_rad),
1020                        );
1021                        out.colored_vertex(
1022                            p - n * inner_rad,
1023                            get_color(color_inner, p - n * inner_rad),
1024                        );
1025                        out.colored_vertex(p - n * outer_rad, color_outer);
1026
1027                        out.add_triangle(idx + 4 * i0 + 0, idx + 4 * i0 + 1, idx + 4 * i1 + 0);
1028                        out.add_triangle(idx + 4 * i0 + 1, idx + 4 * i1 + 0, idx + 4 * i1 + 1);
1029
1030                        out.add_triangle(idx + 4 * i0 + 1, idx + 4 * i0 + 2, idx + 4 * i1 + 1);
1031                        out.add_triangle(idx + 4 * i0 + 2, idx + 4 * i1 + 1, idx + 4 * i1 + 2);
1032
1033                        out.add_triangle(idx + 4 * i0 + 2, idx + 4 * i0 + 3, idx + 4 * i1 + 2);
1034                        out.add_triangle(idx + 4 * i0 + 3, idx + 4 * i1 + 2, idx + 4 * i1 + 3);
1035
1036                        i0 = i1;
1037                    }
1038                }
1039                PathType::Open => {
1040                    // Anti-alias the ends by extruding the outer edge and adding
1041                    // two more triangles to each end:
1042
1043                    //   | aa |       | aa |
1044                    //    _________________   ___
1045                    //   | \    added    / |  feathering
1046                    //   |   \ ___p___ /   |  ___
1047                    //   |    |       |    |
1048                    //   |    |  opa  |    |
1049                    //   |    |  que  |    |
1050                    //   |    |       |    |
1051
1052                    // (in the future it would be great with an option to add a circular end instead)
1053
1054                    out.reserve_triangles(6 * n as usize + 4);
1055                    out.reserve_vertices(4 * n as usize);
1056
1057                    {
1058                        let end = path[0];
1059                        let p = end.pos;
1060                        let n = end.normal;
1061                        let back_extrude = n.rot90() * feathering;
1062                        out.colored_vertex(p + n * outer_rad + back_extrude, color_outer);
1063                        out.colored_vertex(
1064                            p + n * inner_rad,
1065                            get_color(color_inner, p + n * inner_rad),
1066                        );
1067                        out.colored_vertex(
1068                            p - n * inner_rad,
1069                            get_color(color_inner, p - n * inner_rad),
1070                        );
1071                        out.colored_vertex(p - n * outer_rad + back_extrude, color_outer);
1072
1073                        out.add_triangle(idx + 0, idx + 1, idx + 2);
1074                        out.add_triangle(idx + 0, idx + 2, idx + 3);
1075                    }
1076
1077                    let mut i0 = 0;
1078                    for i1 in 1..n - 1 {
1079                        let point = path[i1 as usize];
1080                        let p = point.pos;
1081                        let n = point.normal;
1082                        out.colored_vertex(p + n * outer_rad, color_outer);
1083                        out.colored_vertex(
1084                            p + n * inner_rad,
1085                            get_color(color_inner, p + n * inner_rad),
1086                        );
1087                        out.colored_vertex(
1088                            p - n * inner_rad,
1089                            get_color(color_inner, p - n * inner_rad),
1090                        );
1091                        out.colored_vertex(p - n * outer_rad, color_outer);
1092
1093                        out.add_triangle(idx + 4 * i0 + 0, idx + 4 * i0 + 1, idx + 4 * i1 + 0);
1094                        out.add_triangle(idx + 4 * i0 + 1, idx + 4 * i1 + 0, idx + 4 * i1 + 1);
1095
1096                        out.add_triangle(idx + 4 * i0 + 1, idx + 4 * i0 + 2, idx + 4 * i1 + 1);
1097                        out.add_triangle(idx + 4 * i0 + 2, idx + 4 * i1 + 1, idx + 4 * i1 + 2);
1098
1099                        out.add_triangle(idx + 4 * i0 + 2, idx + 4 * i0 + 3, idx + 4 * i1 + 2);
1100                        out.add_triangle(idx + 4 * i0 + 3, idx + 4 * i1 + 2, idx + 4 * i1 + 3);
1101
1102                        i0 = i1;
1103                    }
1104
1105                    {
1106                        let i1 = n - 1;
1107                        let end = path[i1 as usize];
1108                        let p = end.pos;
1109                        let n = end.normal;
1110                        let back_extrude = -n.rot90() * feathering;
1111                        out.colored_vertex(p + n * outer_rad + back_extrude, color_outer);
1112                        out.colored_vertex(
1113                            p + n * inner_rad,
1114                            get_color(color_inner, p + n * inner_rad),
1115                        );
1116                        out.colored_vertex(
1117                            p - n * inner_rad,
1118                            get_color(color_inner, p - n * inner_rad),
1119                        );
1120                        out.colored_vertex(p - n * outer_rad + back_extrude, color_outer);
1121
1122                        out.add_triangle(idx + 4 * i0 + 0, idx + 4 * i0 + 1, idx + 4 * i1 + 0);
1123                        out.add_triangle(idx + 4 * i0 + 1, idx + 4 * i1 + 0, idx + 4 * i1 + 1);
1124
1125                        out.add_triangle(idx + 4 * i0 + 1, idx + 4 * i0 + 2, idx + 4 * i1 + 1);
1126                        out.add_triangle(idx + 4 * i0 + 2, idx + 4 * i1 + 1, idx + 4 * i1 + 2);
1127
1128                        out.add_triangle(idx + 4 * i0 + 2, idx + 4 * i0 + 3, idx + 4 * i1 + 2);
1129                        out.add_triangle(idx + 4 * i0 + 3, idx + 4 * i1 + 2, idx + 4 * i1 + 3);
1130
1131                        // The extension:
1132                        out.add_triangle(idx + 4 * i1 + 0, idx + 4 * i1 + 1, idx + 4 * i1 + 2);
1133                        out.add_triangle(idx + 4 * i1 + 0, idx + 4 * i1 + 2, idx + 4 * i1 + 3);
1134                    }
1135                }
1136            }
1137        }
1138    } else {
1139        // not anti-aliased:
1140        out.reserve_triangles(2 * n as usize);
1141        out.reserve_vertices(2 * n as usize);
1142
1143        let last_index = if path_type == PathType::Closed {
1144            n
1145        } else {
1146            n - 1
1147        };
1148        for i in 0..last_index {
1149            out.add_triangle(
1150                idx + (2 * i + 0) % (2 * n),
1151                idx + (2 * i + 1) % (2 * n),
1152                idx + (2 * i + 2) % (2 * n),
1153            );
1154            out.add_triangle(
1155                idx + (2 * i + 2) % (2 * n),
1156                idx + (2 * i + 1) % (2 * n),
1157                idx + (2 * i + 3) % (2 * n),
1158            );
1159        }
1160
1161        let thin_line = stroke.width <= feathering;
1162        if thin_line {
1163            // Fade out thin lines rather than making them thinner
1164            let radius = feathering / 2.0;
1165            if let ColorMode::Solid(color) = stroke.color {
1166                let color = mul_color(color, stroke.width / feathering);
1167                if color == Color32::TRANSPARENT {
1168                    return;
1169                }
1170            }
1171            for p in path {
1172                out.colored_vertex(
1173                    p.pos + radius * p.normal,
1174                    mul_color(
1175                        get_color(&stroke.color, p.pos + radius * p.normal),
1176                        stroke.width / feathering,
1177                    ),
1178                );
1179                out.colored_vertex(
1180                    p.pos - radius * p.normal,
1181                    mul_color(
1182                        get_color(&stroke.color, p.pos - radius * p.normal),
1183                        stroke.width / feathering,
1184                    ),
1185                );
1186            }
1187        } else {
1188            let radius = stroke.width / 2.0;
1189            for p in path {
1190                out.colored_vertex(
1191                    p.pos + radius * p.normal,
1192                    get_color(&stroke.color, p.pos + radius * p.normal),
1193                );
1194                out.colored_vertex(
1195                    p.pos - radius * p.normal,
1196                    get_color(&stroke.color, p.pos - radius * p.normal),
1197                );
1198            }
1199        }
1200    }
1201}
1202
1203fn mul_color(color: Color32, factor: f32) -> Color32 {
1204    // The fast gamma-space multiply also happens to be perceptually better.
1205    // Win-win!
1206    color.gamma_multiply(factor)
1207}
1208
1209// ----------------------------------------------------------------------------
1210
1211/// Converts [`Shape`]s into triangles ([`Mesh`]).
1212///
1213/// For performance reasons it is smart to reuse the same [`Tessellator`].
1214///
1215/// See also [`tessellate_shapes`], a convenient wrapper around [`Tessellator`].
1216#[derive(Clone)]
1217pub struct Tessellator {
1218    pixels_per_point: f32,
1219    options: TessellationOptions,
1220    font_tex_size: [usize; 2],
1221
1222    /// See [`crate::TextureAtlas::prepared_discs`].
1223    prepared_discs: Vec<PreparedDisc>,
1224
1225    /// size of feathering in points. normally the size of a physical pixel. 0.0 if disabled
1226    feathering: f32,
1227
1228    /// Only used for culling
1229    clip_rect: Rect,
1230
1231    scratchpad_points: Vec<Pos2>,
1232    scratchpad_path: Path,
1233}
1234
1235impl Tessellator {
1236    /// Create a new [`Tessellator`].
1237    ///
1238    /// * `pixels_per_point`: number of physical pixels to each logical point
1239    /// * `options`: tessellation quality
1240    /// * `shapes`: what to tessellate
1241    /// * `font_tex_size`: size of the font texture. Required to normalize glyph uv rectangles when tessellating text.
1242    /// * `prepared_discs`: What [`crate::TextureAtlas::prepared_discs`] returns. Can safely be set to an empty vec.
1243    pub fn new(
1244        pixels_per_point: f32,
1245        options: TessellationOptions,
1246        font_tex_size: [usize; 2],
1247        prepared_discs: Vec<PreparedDisc>,
1248    ) -> Self {
1249        let feathering = if options.feathering {
1250            let pixel_size = 1.0 / pixels_per_point;
1251            options.feathering_size_in_pixels * pixel_size
1252        } else {
1253            0.0
1254        };
1255        Self {
1256            pixels_per_point,
1257            options,
1258            font_tex_size,
1259            prepared_discs,
1260            feathering,
1261            clip_rect: Rect::EVERYTHING,
1262            scratchpad_points: Default::default(),
1263            scratchpad_path: Default::default(),
1264        }
1265    }
1266
1267    /// Set the [`Rect`] to use for culling.
1268    pub fn set_clip_rect(&mut self, clip_rect: Rect) {
1269        self.clip_rect = clip_rect;
1270    }
1271
1272    #[inline(always)]
1273    pub fn round_to_pixel(&self, point: f32) -> f32 {
1274        (point * self.pixels_per_point).round() / self.pixels_per_point
1275    }
1276
1277    #[inline(always)]
1278    pub fn round_to_pixel_center(&self, point: f32) -> f32 {
1279        ((point * self.pixels_per_point - 0.5).round() + 0.5) / self.pixels_per_point
1280    }
1281
1282    #[inline(always)]
1283    pub fn round_pos_to_pixel(&self, pos: Pos2) -> Pos2 {
1284        pos2(self.round_to_pixel(pos.x), self.round_to_pixel(pos.y))
1285    }
1286
1287    #[inline(always)]
1288    pub fn round_pos_to_pixel_center(&self, pos: Pos2) -> Pos2 {
1289        pos2(
1290            self.round_to_pixel_center(pos.x),
1291            self.round_to_pixel_center(pos.y),
1292        )
1293    }
1294
1295    /// Tessellate a clipped shape into a list of primitives.
1296    pub fn tessellate_clipped_shape(
1297        &mut self,
1298        clipped_shape: ClippedShape,
1299        out_primitives: &mut Vec<ClippedPrimitive>,
1300    ) {
1301        let ClippedShape { clip_rect, shape } = clipped_shape;
1302
1303        if !clip_rect.is_positive() {
1304            return; // skip empty clip rectangles
1305        }
1306
1307        if let Shape::Vec(shapes) = shape {
1308            for shape in shapes {
1309                self.tessellate_clipped_shape(ClippedShape { clip_rect, shape }, out_primitives);
1310            }
1311            return;
1312        }
1313
1314        if let Shape::Callback(callback) = shape {
1315            out_primitives.push(ClippedPrimitive {
1316                clip_rect,
1317                primitive: Primitive::Callback(callback),
1318            });
1319            return;
1320        }
1321
1322        let start_new_mesh = match out_primitives.last() {
1323            None => true,
1324            Some(output_clipped_primitive) => {
1325                output_clipped_primitive.clip_rect != clip_rect
1326                    || match &output_clipped_primitive.primitive {
1327                        Primitive::Mesh(output_mesh) => {
1328                            output_mesh.texture_id != shape.texture_id()
1329                        }
1330                        Primitive::Callback(_) => true,
1331                    }
1332            }
1333        };
1334
1335        if start_new_mesh {
1336            out_primitives.push(ClippedPrimitive {
1337                clip_rect,
1338                primitive: Primitive::Mesh(Mesh::default()),
1339            });
1340        }
1341
1342        let out = out_primitives.last_mut().unwrap();
1343
1344        if let Primitive::Mesh(out_mesh) = &mut out.primitive {
1345            self.clip_rect = clip_rect;
1346            self.tessellate_shape(shape, out_mesh);
1347        } else {
1348            unreachable!();
1349        }
1350    }
1351
1352    /// Tessellate a single [`Shape`] into a [`Mesh`].
1353    ///
1354    /// This call can panic the given shape is of [`Shape::Vec`] or [`Shape::Callback`].
1355    /// For that, use [`Self::tessellate_clipped_shape`] instead.
1356    /// * `shape`: the shape to tessellate.
1357    /// * `out`: triangles are appended to this.
1358    pub fn tessellate_shape(&mut self, shape: Shape, out: &mut Mesh) {
1359        match shape {
1360            Shape::Noop => {}
1361            Shape::Vec(vec) => {
1362                for shape in vec {
1363                    self.tessellate_shape(shape, out);
1364                }
1365            }
1366            Shape::Circle(circle) => {
1367                self.tessellate_circle(circle, out);
1368            }
1369            Shape::Ellipse(ellipse) => {
1370                self.tessellate_ellipse(ellipse, out);
1371            }
1372            Shape::Mesh(mesh) => {
1373                profiling::scope!("mesh");
1374
1375                if self.options.validate_meshes && !mesh.is_valid() {
1376                    debug_assert!(false, "Invalid Mesh in Shape::Mesh");
1377                    return;
1378                }
1379                // note: `append` still checks if the mesh is valid if extra asserts are enabled.
1380
1381                if self.options.coarse_tessellation_culling
1382                    && !self.clip_rect.intersects(mesh.calc_bounds())
1383                {
1384                    return;
1385                }
1386
1387                out.append(mesh);
1388            }
1389            Shape::LineSegment { points, stroke } => self.tessellate_line(points, stroke, out),
1390            Shape::Path(path_shape) => {
1391                self.tessellate_path(&path_shape, out);
1392            }
1393            Shape::Rect(rect_shape) => {
1394                self.tessellate_rect(&rect_shape, out);
1395            }
1396            Shape::Text(text_shape) => {
1397                if self.options.debug_paint_text_rects {
1398                    let rect = text_shape.galley.rect.translate(text_shape.pos.to_vec2());
1399                    self.tessellate_rect(
1400                        &RectShape::stroke(rect.expand(0.5), 2.0, (0.5, Color32::GREEN)),
1401                        out,
1402                    );
1403                }
1404                self.tessellate_text(&text_shape, out);
1405            }
1406            Shape::QuadraticBezier(quadratic_shape) => {
1407                self.tessellate_quadratic_bezier(&quadratic_shape, out);
1408            }
1409            Shape::CubicBezier(cubic_shape) => self.tessellate_cubic_bezier(&cubic_shape, out),
1410            Shape::Callback(_) => {
1411                panic!("Shape::Callback passed to Tessellator");
1412            }
1413        }
1414    }
1415
1416    /// Tessellate a single [`CircleShape`] into a [`Mesh`].
1417    ///
1418    /// * `shape`: the circle to tessellate.
1419    /// * `out`: triangles are appended to this.
1420    pub fn tessellate_circle(&mut self, shape: CircleShape, out: &mut Mesh) {
1421        let CircleShape {
1422            center,
1423            radius,
1424            mut fill,
1425            stroke,
1426        } = shape;
1427
1428        if radius <= 0.0 {
1429            return;
1430        }
1431
1432        if self.options.coarse_tessellation_culling
1433            && !self
1434                .clip_rect
1435                .expand(radius + stroke.width)
1436                .contains(center)
1437        {
1438            return;
1439        }
1440
1441        if self.options.prerasterized_discs && fill != Color32::TRANSPARENT {
1442            let radius_px = radius * self.pixels_per_point;
1443            // strike the right balance between some circles becoming too blurry, and some too sharp.
1444            let cutoff_radius = radius_px * 2.0_f32.powf(0.25);
1445
1446            // Find the right disc radius for a crisp edge:
1447            // TODO(emilk): perhaps we can do something faster than this linear search.
1448            for disc in &self.prepared_discs {
1449                if cutoff_radius <= disc.r {
1450                    let side = radius_px * disc.w / (self.pixels_per_point * disc.r);
1451                    let rect = Rect::from_center_size(center, Vec2::splat(side));
1452                    out.add_rect_with_uv(rect, disc.uv, fill);
1453
1454                    if stroke.is_empty() {
1455                        return; // we are done
1456                    } else {
1457                        // we still need to do the stroke
1458                        fill = Color32::TRANSPARENT; // don't fill again below
1459                        break;
1460                    }
1461                }
1462            }
1463        }
1464
1465        let path_stroke = PathStroke::from(stroke).outside();
1466        self.scratchpad_path.clear();
1467        self.scratchpad_path.add_circle(center, radius);
1468        self.scratchpad_path
1469            .fill(self.feathering, fill, &path_stroke, out);
1470        self.scratchpad_path
1471            .stroke_closed(self.feathering, &path_stroke, out);
1472    }
1473
1474    /// Tessellate a single [`EllipseShape`] into a [`Mesh`].
1475    ///
1476    /// * `shape`: the ellipse to tessellate.
1477    /// * `out`: triangles are appended to this.
1478    pub fn tessellate_ellipse(&mut self, shape: EllipseShape, out: &mut Mesh) {
1479        let EllipseShape {
1480            center,
1481            radius,
1482            fill,
1483            stroke,
1484        } = shape;
1485
1486        if radius.x <= 0.0 || radius.y <= 0.0 {
1487            return;
1488        }
1489
1490        if self.options.coarse_tessellation_culling
1491            && !self
1492                .clip_rect
1493                .expand2(radius + Vec2::splat(stroke.width))
1494                .contains(center)
1495        {
1496            return;
1497        }
1498
1499        // Get the max pixel radius
1500        let max_radius = (radius.max_elem() * self.pixels_per_point) as u32;
1501
1502        // Ensure there is at least 8 points in each quarter of the ellipse
1503        let num_points = u32::max(8, max_radius / 16);
1504
1505        // Create an ease ratio based the ellipses a and b
1506        let ratio = ((radius.y / radius.x) / 2.0).clamp(0.0, 1.0);
1507
1508        // Generate points between the 0 to pi/2
1509        let quarter: Vec<Vec2> = (1..num_points)
1510            .map(|i| {
1511                let percent = i as f32 / num_points as f32;
1512
1513                // Ease the percent value, concentrating points around tight bends
1514                let eased = 2.0 * (percent - percent.powf(2.0)) * ratio + percent.powf(2.0);
1515
1516                // Scale the ease to the quarter
1517                let t = eased * std::f32::consts::FRAC_PI_2;
1518                Vec2::new(radius.x * f32::cos(t), radius.y * f32::sin(t))
1519            })
1520            .collect();
1521
1522        // Build the ellipse from the 4 known vertices filling arcs between
1523        // them by mirroring the points between 0 and pi/2
1524        let mut points = Vec::new();
1525        points.push(center + Vec2::new(radius.x, 0.0));
1526        points.extend(quarter.iter().map(|p| center + *p));
1527        points.push(center + Vec2::new(0.0, radius.y));
1528        points.extend(quarter.iter().rev().map(|p| center + Vec2::new(-p.x, p.y)));
1529        points.push(center + Vec2::new(-radius.x, 0.0));
1530        points.extend(quarter.iter().map(|p| center - *p));
1531        points.push(center + Vec2::new(0.0, -radius.y));
1532        points.extend(quarter.iter().rev().map(|p| center + Vec2::new(p.x, -p.y)));
1533
1534        let path_stroke = PathStroke::from(stroke).outside();
1535        self.scratchpad_path.clear();
1536        self.scratchpad_path.add_line_loop(&points);
1537        self.scratchpad_path
1538            .fill(self.feathering, fill, &path_stroke, out);
1539        self.scratchpad_path
1540            .stroke_closed(self.feathering, &path_stroke, out);
1541    }
1542
1543    /// Tessellate a single [`Mesh`] into a [`Mesh`].
1544    ///
1545    /// * `mesh`: the mesh to tessellate.
1546    /// * `out`: triangles are appended to this.
1547    pub fn tessellate_mesh(&self, mesh: &Mesh, out: &mut Mesh) {
1548        if !mesh.is_valid() {
1549            debug_assert!(false, "Invalid Mesh in Shape::Mesh");
1550            return;
1551        }
1552
1553        if self.options.coarse_tessellation_culling
1554            && !self.clip_rect.intersects(mesh.calc_bounds())
1555        {
1556            return;
1557        }
1558
1559        out.append_ref(mesh);
1560    }
1561
1562    /// Tessellate a line segment between the two points with the given stroke into a [`Mesh`].
1563    ///
1564    /// * `shape`: the mesh to tessellate.
1565    /// * `out`: triangles are appended to this.
1566    pub fn tessellate_line(
1567        &mut self,
1568        points: [Pos2; 2],
1569        stroke: impl Into<PathStroke>,
1570        out: &mut Mesh,
1571    ) {
1572        let stroke = stroke.into();
1573        if stroke.is_empty() {
1574            return;
1575        }
1576
1577        if self.options.coarse_tessellation_culling
1578            && !self
1579                .clip_rect
1580                .intersects(Rect::from_two_pos(points[0], points[1]).expand(stroke.width))
1581        {
1582            return;
1583        }
1584
1585        self.scratchpad_path.clear();
1586        self.scratchpad_path.add_line_segment(points);
1587        self.scratchpad_path
1588            .stroke_open(self.feathering, &stroke, out);
1589    }
1590
1591    /// Tessellate a single [`PathShape`] into a [`Mesh`].
1592    ///
1593    /// * `path_shape`: the path to tessellate.
1594    /// * `out`: triangles are appended to this.
1595    pub fn tessellate_path(&mut self, path_shape: &PathShape, out: &mut Mesh) {
1596        if path_shape.points.len() < 2 {
1597            return;
1598        }
1599
1600        if self.options.coarse_tessellation_culling
1601            && !path_shape.visual_bounding_rect().intersects(self.clip_rect)
1602        {
1603            return;
1604        }
1605
1606        profiling::function_scope!();
1607
1608        let PathShape {
1609            points,
1610            closed,
1611            fill,
1612            stroke,
1613        } = path_shape;
1614
1615        self.scratchpad_path.clear();
1616        if *closed {
1617            self.scratchpad_path.add_line_loop(points);
1618        } else {
1619            self.scratchpad_path.add_open_points(points);
1620        }
1621
1622        if *fill != Color32::TRANSPARENT {
1623            debug_assert!(
1624                closed,
1625                "You asked to fill a path that is not closed. That makes no sense."
1626            );
1627            self.scratchpad_path
1628                .fill(self.feathering, *fill, stroke, out);
1629        }
1630        let typ = if *closed {
1631            PathType::Closed
1632        } else {
1633            PathType::Open
1634        };
1635        self.scratchpad_path
1636            .stroke(self.feathering, typ, stroke, out);
1637    }
1638
1639    /// Tessellate a single [`Rect`] into a [`Mesh`].
1640    ///
1641    /// * `rect`: the rectangle to tessellate.
1642    /// * `out`: triangles are appended to this.
1643    pub fn tessellate_rect(&mut self, rect: &RectShape, out: &mut Mesh) {
1644        let RectShape {
1645            mut rect,
1646            mut rounding,
1647            fill,
1648            stroke,
1649            mut blur_width,
1650            fill_texture_id,
1651            uv,
1652        } = *rect;
1653
1654        if self.options.coarse_tessellation_culling
1655            && !rect.expand(stroke.width).intersects(self.clip_rect)
1656        {
1657            return;
1658        }
1659        if rect.is_negative() {
1660            return;
1661        }
1662
1663        // It is common to (sometimes accidentally) create an infinitely sized rectangle.
1664        // Make sure we can handle that:
1665        rect.min = rect.min.at_least(pos2(-1e7, -1e7));
1666        rect.max = rect.max.at_most(pos2(1e7, 1e7));
1667
1668        let old_feathering = self.feathering;
1669
1670        if old_feathering < blur_width {
1671            // We accomplish the blur by using a larger-than-normal feathering.
1672            // Feathering is usually used to make the edges of a shape softer for anti-aliasing.
1673
1674            // The tessellator can't handle blurring/feathering larger than the smallest side of the rect.
1675            // Thats because the tessellator approximate very thin rectangles as line segments,
1676            // and these line segments don't have rounded corners.
1677            // When the feathering is small (the size of a pixel), this is usually fine,
1678            // but here we have a huge feathering to simulate blur,
1679            // so we need to avoid this optimization in the tessellator,
1680            // which is also why we add this rather big epsilon:
1681            let eps = 0.1;
1682            blur_width = blur_width
1683                .at_most(rect.size().min_elem() - eps)
1684                .at_least(0.0);
1685
1686            rounding += Rounding::same(0.5 * blur_width);
1687
1688            self.feathering = self.feathering.max(blur_width);
1689        }
1690
1691        if rect.width() < self.feathering {
1692            // Very thin - approximate by a vertical line-segment:
1693            let line = [rect.center_top(), rect.center_bottom()];
1694            if fill != Color32::TRANSPARENT {
1695                self.tessellate_line(line, Stroke::new(rect.width(), fill), out);
1696            }
1697            if !stroke.is_empty() {
1698                self.tessellate_line(line, stroke, out); // back…
1699                self.tessellate_line(line, stroke, out); // …and forth
1700            }
1701        } else if rect.height() < self.feathering {
1702            // Very thin - approximate by a horizontal line-segment:
1703            let line = [rect.left_center(), rect.right_center()];
1704            if fill != Color32::TRANSPARENT {
1705                self.tessellate_line(line, Stroke::new(rect.height(), fill), out);
1706            }
1707            if !stroke.is_empty() {
1708                self.tessellate_line(line, stroke, out); // back…
1709                self.tessellate_line(line, stroke, out); // …and forth
1710            }
1711        } else {
1712            let rect = if !stroke.is_empty() && stroke.width < self.feathering {
1713                // Very thin rectangle strokes create extreme aliasing when they move around.
1714                // We can fix that by rounding the rectangle corners to pixel centers.
1715                // TODO(#5164): maybe do this for all shapes and stroke sizes
1716                // TODO(emilk): since we use StrokeKind::Outside, we should probably round the
1717                // corners after offsetting them with half the stroke width (see `translate_stroke_point`).
1718                Rect {
1719                    min: self.round_pos_to_pixel_center(rect.min),
1720                    max: self.round_pos_to_pixel_center(rect.max),
1721                }
1722            } else {
1723                rect
1724            };
1725
1726            let path = &mut self.scratchpad_path;
1727            path.clear();
1728            path::rounded_rectangle(&mut self.scratchpad_points, rect, rounding);
1729            path.add_line_loop(&self.scratchpad_points);
1730            let path_stroke = PathStroke::from(stroke).outside();
1731            if uv.is_positive() {
1732                // Textured
1733                let uv_from_pos = |p: Pos2| {
1734                    pos2(
1735                        remap(p.x, rect.x_range(), uv.x_range()),
1736                        remap(p.y, rect.y_range(), uv.y_range()),
1737                    )
1738                };
1739                path.fill_with_uv(self.feathering, fill, fill_texture_id, uv_from_pos, out);
1740            } else {
1741                // Untextured
1742                path.fill(self.feathering, fill, &path_stroke, out);
1743            }
1744            path.stroke_closed(self.feathering, &path_stroke, out);
1745        }
1746
1747        self.feathering = old_feathering; // restore
1748    }
1749
1750    /// Tessellate a single [`TextShape`] into a [`Mesh`].
1751    /// * `text_shape`: the text to tessellate.
1752    /// * `out`: triangles are appended to this.
1753    pub fn tessellate_text(&mut self, text_shape: &TextShape, out: &mut Mesh) {
1754        let TextShape {
1755            pos: galley_pos,
1756            galley,
1757            underline,
1758            override_text_color,
1759            fallback_color,
1760            opacity_factor,
1761            angle,
1762        } = text_shape;
1763
1764        if galley.is_empty() {
1765            return;
1766        }
1767
1768        if *opacity_factor <= 0.0 {
1769            return;
1770        }
1771
1772        if galley.pixels_per_point != self.pixels_per_point {
1773            let warn = "epaint: WARNING: pixels_per_point (dpi scale) have changed between text layout and tessellation. \
1774                       You must recreate your text shapes if pixels_per_point changes.";
1775            #[cfg(feature = "log")]
1776            log::warn!("{warn}");
1777            #[cfg(not(feature = "log"))]
1778            println!("{warn}");
1779        }
1780
1781        out.vertices.reserve(galley.num_vertices);
1782        out.indices.reserve(galley.num_indices);
1783
1784        // The contents of the galley are already snapped to pixel coordinates,
1785        // but we need to make sure the galley ends up on the start of a physical pixel:
1786        let galley_pos = if self.options.round_text_to_pixels {
1787            pos2(
1788                self.round_to_pixel(galley_pos.x),
1789                self.round_to_pixel(galley_pos.y),
1790            )
1791        } else {
1792            *galley_pos
1793        };
1794
1795        let uv_normalizer = vec2(
1796            1.0 / self.font_tex_size[0] as f32,
1797            1.0 / self.font_tex_size[1] as f32,
1798        );
1799
1800        let rotator = Rot2::from_angle(*angle);
1801
1802        for row in &galley.rows {
1803            if row.visuals.mesh.is_empty() {
1804                continue;
1805            }
1806
1807            let mut row_rect = row.visuals.mesh_bounds;
1808            if *angle != 0.0 {
1809                row_rect = row_rect.rotate_bb(rotator);
1810            }
1811            row_rect = row_rect.translate(galley_pos.to_vec2());
1812
1813            if self.options.coarse_tessellation_culling && !self.clip_rect.intersects(row_rect) {
1814                // culling individual lines of text is important, since a single `Shape::Text`
1815                // can span hundreds of lines.
1816                continue;
1817            }
1818
1819            let index_offset = out.vertices.len() as u32;
1820
1821            out.indices.extend(
1822                row.visuals
1823                    .mesh
1824                    .indices
1825                    .iter()
1826                    .map(|index| index + index_offset),
1827            );
1828
1829            out.vertices.extend(
1830                row.visuals
1831                    .mesh
1832                    .vertices
1833                    .iter()
1834                    .enumerate()
1835                    .map(|(i, vertex)| {
1836                        let Vertex { pos, uv, mut color } = *vertex;
1837
1838                        if let Some(override_text_color) = override_text_color {
1839                            // Only override the glyph color (not background color, strike-through color, etc)
1840                            if row.visuals.glyph_vertex_range.contains(&i) {
1841                                color = *override_text_color;
1842                            }
1843                        } else if color == Color32::PLACEHOLDER {
1844                            color = *fallback_color;
1845                        }
1846
1847                        if *opacity_factor < 1.0 {
1848                            color = color.gamma_multiply(*opacity_factor);
1849                        }
1850
1851                        debug_assert!(color != Color32::PLACEHOLDER, "A placeholder color made it to the tessellator. You forgot to set a fallback color.");
1852
1853                        let offset = if *angle == 0.0 {
1854                            pos.to_vec2()
1855                        } else {
1856                            rotator * pos.to_vec2()
1857                        };
1858
1859                        Vertex {
1860                            pos: galley_pos + offset,
1861                            uv: (uv.to_vec2() * uv_normalizer).to_pos2(),
1862                            color,
1863                        }
1864                    }),
1865            );
1866
1867            if *underline != Stroke::NONE {
1868                self.scratchpad_path.clear();
1869                self.scratchpad_path.add_line_segment([
1870                    self.round_pos_to_pixel_center(row_rect.left_bottom()),
1871                    self.round_pos_to_pixel_center(row_rect.right_bottom()),
1872                ]);
1873                self.scratchpad_path
1874                    .stroke_open(0.0, &PathStroke::from(*underline), out);
1875            }
1876        }
1877    }
1878
1879    /// Tessellate a single [`QuadraticBezierShape`] into a [`Mesh`].
1880    ///
1881    /// * `quadratic_shape`: the shape to tessellate.
1882    /// * `out`: triangles are appended to this.
1883    pub fn tessellate_quadratic_bezier(
1884        &mut self,
1885        quadratic_shape: &QuadraticBezierShape,
1886        out: &mut Mesh,
1887    ) {
1888        let options = &self.options;
1889        let clip_rect = self.clip_rect;
1890
1891        if options.coarse_tessellation_culling
1892            && !quadratic_shape.visual_bounding_rect().intersects(clip_rect)
1893        {
1894            return;
1895        }
1896
1897        let points = quadratic_shape.flatten(Some(options.bezier_tolerance));
1898
1899        self.tessellate_bezier_complete(
1900            &points,
1901            quadratic_shape.fill,
1902            quadratic_shape.closed,
1903            &quadratic_shape.stroke,
1904            out,
1905        );
1906    }
1907
1908    /// Tessellate a single [`CubicBezierShape`] into a [`Mesh`].
1909    ///
1910    /// * `cubic_shape`: the shape to tessellate.
1911    /// * `out`: triangles are appended to this.
1912    pub fn tessellate_cubic_bezier(&mut self, cubic_shape: &CubicBezierShape, out: &mut Mesh) {
1913        let options = &self.options;
1914        let clip_rect = self.clip_rect;
1915        if options.coarse_tessellation_culling
1916            && !cubic_shape.visual_bounding_rect().intersects(clip_rect)
1917        {
1918            return;
1919        }
1920
1921        let points_vec =
1922            cubic_shape.flatten_closed(Some(options.bezier_tolerance), Some(options.epsilon));
1923
1924        for points in points_vec {
1925            self.tessellate_bezier_complete(
1926                &points,
1927                cubic_shape.fill,
1928                cubic_shape.closed,
1929                &cubic_shape.stroke,
1930                out,
1931            );
1932        }
1933    }
1934
1935    fn tessellate_bezier_complete(
1936        &mut self,
1937        points: &[Pos2],
1938        fill: Color32,
1939        closed: bool,
1940        stroke: &PathStroke,
1941        out: &mut Mesh,
1942    ) {
1943        if points.len() < 2 {
1944            return;
1945        }
1946
1947        self.scratchpad_path.clear();
1948        if closed {
1949            self.scratchpad_path.add_line_loop(points);
1950        } else {
1951            self.scratchpad_path.add_open_points(points);
1952        }
1953        if fill != Color32::TRANSPARENT {
1954            debug_assert!(
1955                closed,
1956                "You asked to fill a path that is not closed. That makes no sense."
1957            );
1958            self.scratchpad_path
1959                .fill(self.feathering, fill, stroke, out);
1960        }
1961        let typ = if closed {
1962            PathType::Closed
1963        } else {
1964            PathType::Open
1965        };
1966        self.scratchpad_path
1967            .stroke(self.feathering, typ, stroke, out);
1968    }
1969}
1970
1971#[deprecated = "Use `Tessellator::new(…).tessellate_shapes(…)` instead"]
1972pub fn tessellate_shapes(
1973    pixels_per_point: f32,
1974    options: TessellationOptions,
1975    font_tex_size: [usize; 2],
1976    prepared_discs: Vec<PreparedDisc>,
1977    shapes: Vec<ClippedShape>,
1978) -> Vec<ClippedPrimitive> {
1979    Tessellator::new(pixels_per_point, options, font_tex_size, prepared_discs)
1980        .tessellate_shapes(shapes)
1981}
1982
1983impl Tessellator {
1984    /// Turns [`Shape`]:s into sets of triangles.
1985    ///
1986    /// The given shapes will tessellated in the same order as they are given.
1987    /// They will be batched together by clip rectangle.
1988    ///
1989    /// * `pixels_per_point`: number of physical pixels to each logical point
1990    /// * `options`: tessellation quality
1991    /// * `shapes`: what to tessellate
1992    /// * `font_tex_size`: size of the font texture. Required to normalize glyph uv rectangles when tessellating text.
1993    /// * `prepared_discs`: What [`crate::TextureAtlas::prepared_discs`] returns. Can safely be set to an empty vec.
1994    ///
1995    /// The implementation uses a [`Tessellator`].
1996    ///
1997    /// ## Returns
1998    /// A list of clip rectangles with matching [`Mesh`].
1999    #[allow(unused_mut)]
2000    pub fn tessellate_shapes(&mut self, mut shapes: Vec<ClippedShape>) -> Vec<ClippedPrimitive> {
2001        profiling::function_scope!();
2002
2003        #[cfg(feature = "rayon")]
2004        if self.options.parallel_tessellation {
2005            self.parallel_tessellation_of_large_shapes(&mut shapes);
2006        }
2007
2008        let mut clipped_primitives: Vec<ClippedPrimitive> = Vec::default();
2009
2010        {
2011            profiling::scope!("tessellate");
2012            for clipped_shape in shapes {
2013                self.tessellate_clipped_shape(clipped_shape, &mut clipped_primitives);
2014            }
2015        }
2016
2017        if self.options.debug_paint_clip_rects {
2018            clipped_primitives = self.add_clip_rects(clipped_primitives);
2019        }
2020
2021        if self.options.debug_ignore_clip_rects {
2022            for clipped_primitive in &mut clipped_primitives {
2023                clipped_primitive.clip_rect = Rect::EVERYTHING;
2024            }
2025        }
2026
2027        clipped_primitives.retain(|p| {
2028            p.clip_rect.is_positive()
2029                && match &p.primitive {
2030                    Primitive::Mesh(mesh) => !mesh.is_empty(),
2031                    Primitive::Callback(_) => true,
2032                }
2033        });
2034
2035        for clipped_primitive in &clipped_primitives {
2036            if let Primitive::Mesh(mesh) = &clipped_primitive.primitive {
2037                debug_assert!(mesh.is_valid(), "Tessellator generated invalid Mesh");
2038            }
2039        }
2040
2041        clipped_primitives
2042    }
2043
2044    /// Find large shapes and throw them on the rayon thread pool,
2045    /// then replace the original shape with their tessellated meshes.
2046    #[cfg(feature = "rayon")]
2047    fn parallel_tessellation_of_large_shapes(&self, shapes: &mut [ClippedShape]) {
2048        profiling::function_scope!();
2049
2050        use rayon::prelude::*;
2051
2052        // We only parallelize large/slow stuff, because each tessellation job
2053        // will allocate a new Mesh, and so it creates a lot of extra memory fragmentation
2054        // and allocations that is only worth it for large shapes.
2055        fn should_parallelize(shape: &Shape) -> bool {
2056            match shape {
2057                Shape::Vec(shapes) => 4 < shapes.len() || shapes.iter().any(should_parallelize),
2058
2059                Shape::Path(path_shape) => 32 < path_shape.points.len(),
2060
2061                Shape::QuadraticBezier(_) | Shape::CubicBezier(_) | Shape::Ellipse(_) => true,
2062
2063                Shape::Noop
2064                | Shape::Text(_)
2065                | Shape::Circle(_)
2066                | Shape::Mesh(_)
2067                | Shape::LineSegment { .. }
2068                | Shape::Rect(_)
2069                | Shape::Callback(_) => false,
2070            }
2071        }
2072
2073        let tessellated: Vec<(usize, Mesh)> = shapes
2074            .par_iter()
2075            .enumerate()
2076            .filter(|(_, clipped_shape)| should_parallelize(&clipped_shape.shape))
2077            .map(|(index, clipped_shape)| {
2078                profiling::scope!("tessellate_big_shape");
2079                // TODO(emilk): reuse tessellator in a thread local
2080                let mut tessellator = (*self).clone();
2081                let mut mesh = Mesh::default();
2082                tessellator.tessellate_shape(clipped_shape.shape.clone(), &mut mesh);
2083                (index, mesh)
2084            })
2085            .collect();
2086
2087        profiling::scope!("distribute results", tessellated.len().to_string());
2088        for (index, mesh) in tessellated {
2089            shapes[index].shape = Shape::Mesh(mesh);
2090        }
2091    }
2092
2093    fn add_clip_rects(
2094        &mut self,
2095        clipped_primitives: Vec<ClippedPrimitive>,
2096    ) -> Vec<ClippedPrimitive> {
2097        self.clip_rect = Rect::EVERYTHING;
2098        let stroke = Stroke::new(2.0, Color32::from_rgb(150, 255, 150));
2099
2100        clipped_primitives
2101            .into_iter()
2102            .flat_map(|clipped_primitive| {
2103                let mut clip_rect_mesh = Mesh::default();
2104                self.tessellate_shape(
2105                    Shape::rect_stroke(clipped_primitive.clip_rect, 0.0, stroke),
2106                    &mut clip_rect_mesh,
2107                );
2108
2109                [
2110                    clipped_primitive,
2111                    ClippedPrimitive {
2112                        clip_rect: Rect::EVERYTHING, // whatever
2113                        primitive: Primitive::Mesh(clip_rect_mesh),
2114                    },
2115                ]
2116            })
2117            .collect()
2118    }
2119}
2120
2121#[test]
2122fn test_tessellator() {
2123    use crate::*;
2124
2125    let mut shapes = Vec::with_capacity(2);
2126
2127    let rect = Rect::from_min_max(pos2(0.0, 0.0), pos2(1.0, 1.0));
2128    let uv = Rect::from_min_max(pos2(0.0, 0.0), pos2(1.0, 1.0));
2129
2130    let mut mesh = Mesh::with_texture(TextureId::Managed(1));
2131    mesh.add_rect_with_uv(rect, uv, Color32::WHITE);
2132    shapes.push(Shape::mesh(mesh));
2133
2134    let mut mesh = Mesh::with_texture(TextureId::Managed(2));
2135    mesh.add_rect_with_uv(rect, uv, Color32::WHITE);
2136    shapes.push(Shape::mesh(mesh));
2137
2138    let shape = Shape::Vec(shapes);
2139    let clipped_shapes = vec![ClippedShape {
2140        clip_rect: rect,
2141        shape,
2142    }];
2143
2144    let font_tex_size = [1024, 1024]; // unused
2145    let prepared_discs = vec![]; // unused
2146
2147    let primitives = Tessellator::new(1.0, Default::default(), font_tex_size, prepared_discs)
2148        .tessellate_shapes(clipped_shapes);
2149
2150    assert_eq!(primitives.len(), 2);
2151}
2152
2153#[test]
2154fn path_bounding_box() {
2155    use crate::*;
2156
2157    for i in 1..=100 {
2158        let width = i as f32;
2159
2160        let rect = Rect::from_min_max(pos2(0.0, 0.0), pos2(10.0, 10.0));
2161        let expected_rect = rect.expand((width / 2.0) + 1.5);
2162
2163        let mut mesh = Mesh::default();
2164
2165        let mut path = Path::default();
2166        path.add_open_points(&[
2167            pos2(0.0, 0.0),
2168            pos2(2.0, 0.0),
2169            pos2(5.0, 5.0),
2170            pos2(0.0, 5.0),
2171            pos2(0.0, 7.0),
2172            pos2(10.0, 10.0),
2173        ]);
2174
2175        path.stroke(
2176            1.5,
2177            PathType::Closed,
2178            &PathStroke::new_uv(width, move |r, p| {
2179                assert_eq!(r, expected_rect);
2180                // see https://github.com/emilk/egui/pull/4353#discussion_r1573879940 for why .contains() isn't used here.
2181                // TL;DR rounding errors.
2182                assert!(
2183                    r.distance_to_pos(p) <= 0.55,
2184                    "passed rect {r:?} didn't contain point {p:?} (distance: {})",
2185                    r.distance_to_pos(p)
2186                );
2187                assert!(
2188                    expected_rect.distance_to_pos(p) <= 0.55,
2189                    "expected rect {expected_rect:?} didn't contain point {p:?}"
2190                );
2191                Color32::WHITE
2192            }),
2193            &mut mesh,
2194        );
2195    }
2196}