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