epaint/
tessellator.rs

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

epaint/
tessellator.rs
