maplibre/vector/
tessellation.rs

1//! Tessellation for lines and polygons is implemented here.
2
3use std::{cell::RefCell, collections::HashMap};
4
5use bytemuck::Pod;
6use geozero::{ColumnValue, FeatureProcessor, GeomProcessor, PropertyProcessor};
7use lyon::{
8    geom,
9    path::{path::Builder, Path},
10    tessellation::{
11        geometry_builder::MaxIndex, BuffersBuilder, FillOptions, FillRule, FillTessellator,
12        FillVertex, FillVertexConstructor, StrokeOptions, StrokeTessellator, StrokeVertex,
13        StrokeVertexConstructor, VertexBuffers,
14    },
15};
16
17use crate::render::ShaderVertex;
18
19const DEFAULT_TOLERANCE: f32 = 0.02;
20
21/// Vertex buffers index data type.
22pub type IndexDataType = u32; // Must match INDEX_FORMAT
23
24type GeoResult<T> = geozero::error::Result<T>;
25
26/// Constructor for Fill and Stroke vertices.
27pub struct VertexConstructor {}
28
29impl FillVertexConstructor<ShaderVertex> for VertexConstructor {
30    fn new_vertex(&mut self, vertex: FillVertex) -> ShaderVertex {
31        ShaderVertex::new(vertex.position().to_array(), [0.0, 0.0])
32    }
33}
34
35impl StrokeVertexConstructor<ShaderVertex> for VertexConstructor {
36    fn new_vertex(&mut self, vertex: StrokeVertex) -> ShaderVertex {
37        ShaderVertex::new(
38            vertex.position_on_path().to_array(),
39            vertex.normal().to_array(),
40        )
41    }
42}
43
44/// Vertex buffer which includes additional padding to fulfill the `wgpu::COPY_BUFFER_ALIGNMENT`.
45#[derive(Clone)]
46pub struct OverAlignedVertexBuffer<V, I> {
47    pub buffer: VertexBuffers<V, I>,
48    pub usable_indices: u32,
49}
50
51impl<V, I> OverAlignedVertexBuffer<V, I> {
52    pub fn empty() -> Self {
53        Self {
54            buffer: VertexBuffers::with_capacity(0, 0),
55            usable_indices: 0,
56        }
57    }
58
59    pub fn from_iters<IV, II>(vertices: IV, indices: II, usable_indices: u32) -> Self
60    where
61        IV: IntoIterator<Item = V>,
62        II: IntoIterator<Item = I>,
63        IV::IntoIter: ExactSizeIterator,
64        II::IntoIter: ExactSizeIterator,
65    {
66        let vertices = vertices.into_iter();
67        let indices = indices.into_iter();
68        let mut buffers = VertexBuffers::with_capacity(vertices.len(), indices.len());
69        buffers.vertices.extend(vertices);
70        buffers.indices.extend(indices);
71        Self {
72            buffer: buffers,
73            usable_indices,
74        }
75    }
76}
77
78impl<V: Pod, I: Pod> From<VertexBuffers<V, I>> for OverAlignedVertexBuffer<V, I> {
79    fn from(mut buffer: VertexBuffers<V, I>) -> Self {
80        let usable_indices = buffer.indices.len() as u32;
81        buffer.align_vertices();
82        buffer.align_indices();
83        Self {
84            buffer,
85            usable_indices,
86        }
87    }
88}
89
90trait Align<V: Pod, I: Pod> {
91    fn align_vertices(&mut self);
92    fn align_indices(&mut self);
93}
94
95impl<V: Pod, I: Pod> Align<V, I> for VertexBuffers<V, I> {
96    fn align_vertices(&mut self) {
97        let align = wgpu::COPY_BUFFER_ALIGNMENT;
98        let stride = std::mem::size_of::<V>() as wgpu::BufferAddress;
99        let unpadded_bytes = self.vertices.len() as wgpu::BufferAddress * stride;
100        let padding_bytes = (align - unpadded_bytes % align) % align;
101
102        if padding_bytes != 0 {
103            panic!(
104                "vertices are always aligned to wgpu::COPY_BUFFER_ALIGNMENT \
105                    because GpuVertexUniform is aligned"
106            )
107        }
108    }
109
110    fn align_indices(&mut self) {
111        let align = wgpu::COPY_BUFFER_ALIGNMENT;
112        let stride = std::mem::size_of::<I>() as wgpu::BufferAddress;
113        let unpadded_bytes = self.indices.len() as wgpu::BufferAddress * stride;
114        let padding_bytes = (align - unpadded_bytes % align) % align;
115        let overpad = (padding_bytes + stride - 1) / stride; // Divide by stride but round up
116
117        for _ in 0..overpad {
118            self.indices.push(I::zeroed());
119        }
120    }
121}
122
123/// Build tessellations with vectors.
124pub struct ZeroTessellator<I: std::ops::Add + From<lyon::tessellation::VertexId> + MaxIndex> {
125    path_builder: RefCell<Builder>,
126    path_open: bool,
127    is_point: bool,
128
129    pub buffer: VertexBuffers<ShaderVertex, I>,
130
131    pub feature_indices: Vec<u32>,
132    pub feature_properties: HashMap<String, String>,
133    pub feature_colors: Vec<[f32; 4]>,
134    pub fallback_color: [f32; 4],
135    pub style_property: Option<crate::style::layer::StyleProperty<csscolorparser::Color>>,
136    /// When true, polygon geometry is tessellated as strokes (outlines) instead of fills.
137    /// This is used when a line-type style layer references polygon source geometry.
138    pub is_line_layer: bool,
139    current_index: usize,
140}
141
142impl<I: std::ops::Add + From<lyon::tessellation::VertexId> + MaxIndex> Default
143    for ZeroTessellator<I>
144{
145    fn default() -> Self {
146        Self {
147            path_builder: RefCell::new(Path::builder()),
148            buffer: VertexBuffers::new(),
149            feature_indices: Vec::new(),
150            feature_properties: HashMap::new(),
151            feature_colors: Vec::new(),
152            fallback_color: [0.0, 0.0, 0.0, 1.0],
153            style_property: None,
154            is_line_layer: false,
155            current_index: 0,
156            path_open: false,
157            is_point: false,
158        }
159    }
160}
161
162impl<I: std::ops::Add + From<lyon::tessellation::VertexId> + MaxIndex> ZeroTessellator<I> {
163    /// Stores current indices to the output. That way we know which vertices correspond to which
164    /// feature in the output.
165    fn update_feature_indices(&mut self) {
166        let next_index = self.buffer.vertices.len();
167        let indices = (next_index - self.current_index) as u32;
168        self.feature_indices.push(indices);
169        self.current_index = next_index;
170    }
171
172    fn tessellate_strokes(&mut self) {
173        let path_builder = self.path_builder.replace(Path::builder());
174
175        StrokeTessellator::new()
176            .tessellate_path(
177                &path_builder.build(),
178                &StrokeOptions::tolerance(DEFAULT_TOLERANCE),
179                &mut BuffersBuilder::new(&mut self.buffer, VertexConstructor {}),
180            )
181            .unwrap(); // TODO: Remove unwrap
182    }
183
184    fn end(&mut self, close: bool) {
185        if self.path_open {
186            self.path_builder.borrow_mut().end(close);
187            self.path_open = false;
188        }
189    }
190
191    fn tessellate_fill(&mut self) {
192        let path_builder = self.path_builder.replace(Path::builder());
193
194        FillTessellator::new()
195            .tessellate_path(
196                &path_builder.build(),
197                &FillOptions::tolerance(DEFAULT_TOLERANCE).with_fill_rule(FillRule::NonZero),
198                &mut BuffersBuilder::new(&mut self.buffer, VertexConstructor {}),
199            )
200            .unwrap(); // TODO: Remove unwrap
201    }
202}
203
204impl<I: std::ops::Add + From<lyon::tessellation::VertexId> + MaxIndex> GeomProcessor
205    for ZeroTessellator<I>
206{
207    fn xy(&mut self, x: f64, y: f64, _idx: usize) -> GeoResult<()> {
208        // log::info!("xy");
209
210        if self.is_point {
211            // log::info!("point");
212        } else if !self.path_open {
213            self.path_builder
214                .borrow_mut()
215                .begin(geom::point(x as f32, y as f32));
216            self.path_open = true;
217        } else {
218            self.path_builder
219                .borrow_mut()
220                .line_to(geom::point(x as f32, y as f32));
221        }
222        Ok(())
223    }
224
225    fn point_begin(&mut self, _idx: usize) -> GeoResult<()> {
226        // log::info!("point_begin");
227        self.is_point = true;
228        Ok(())
229    }
230
231    fn point_end(&mut self, _idx: usize) -> GeoResult<()> {
232        // log::info!("point_end");
233        self.is_point = false;
234        Ok(())
235    }
236
237    fn multipoint_begin(&mut self, _size: usize, _idx: usize) -> GeoResult<()> {
238        // log::info!("multipoint_begin");
239        Ok(())
240    }
241
242    fn multipoint_end(&mut self, _idx: usize) -> GeoResult<()> {
243        // log::info!("multipoint_end");
244        Ok(())
245    }
246
247    fn linestring_begin(&mut self, _tagged: bool, _size: usize, _idx: usize) -> GeoResult<()> {
248        // log::info!("linestring_begin");
249        Ok(())
250    }
251
252    fn linestring_end(&mut self, tagged: bool, _idx: usize) -> GeoResult<()> {
253        // log::info!("linestring_end");
254
255        self.end(false);
256
257        if tagged {
258            self.tessellate_strokes();
259        }
260        Ok(())
261    }
262
263    fn multilinestring_begin(&mut self, _size: usize, _idx: usize) -> GeoResult<()> {
264        // log::info!("multilinestring_begin");
265        Ok(())
266    }
267
268    fn multilinestring_end(&mut self, _idx: usize) -> GeoResult<()> {
269        // log::info!("multilinestring_end");
270        self.tessellate_strokes();
271        Ok(())
272    }
273
274    fn polygon_begin(&mut self, _tagged: bool, _size: usize, _idx: usize) -> GeoResult<()> {
275        // log::info!("polygon_begin");
276        Ok(())
277    }
278
279    fn polygon_end(&mut self, tagged: bool, _idx: usize) -> GeoResult<()> {
280        // log::info!("polygon_end");
281
282        self.end(true);
283        if tagged {
284            if self.is_line_layer {
285                self.tessellate_strokes();
286            } else {
287                self.tessellate_fill();
288            }
289        }
290        Ok(())
291    }
292
293    fn multipolygon_begin(&mut self, _size: usize, _idx: usize) -> GeoResult<()> {
294        // log::info!("multipolygon_begin");
295        Ok(())
296    }
297
298    fn multipolygon_end(&mut self, _idx: usize) -> GeoResult<()> {
299        // log::info!("multipolygon_end");
300
301        if self.is_line_layer {
302            self.tessellate_strokes();
303        } else {
304            self.tessellate_fill();
305        }
306        Ok(())
307    }
308}
309
310impl<I: std::ops::Add + From<lyon::tessellation::VertexId> + MaxIndex> PropertyProcessor
311    for ZeroTessellator<I>
312{
313    fn property(
314        &mut self,
315        _idx: usize,
316        name: &str,
317        value: &ColumnValue,
318    ) -> geozero::error::Result<bool> {
319        self.feature_properties
320            .insert(name.to_string(), value.to_string());
321        Ok(false)
322    }
323}
324
325impl<I: std::ops::Add + From<lyon::tessellation::VertexId> + MaxIndex> FeatureProcessor
326    for ZeroTessellator<I>
327{
328    fn feature_end(&mut self, _idx: u64) -> geozero::error::Result<()> {
329        self.update_feature_indices();
330        let color = if let Some(style) = &self.style_property {
331            if let Some(c) = style.evaluate(&self.feature_properties) {
332                [c.r as f32, c.g as f32, c.b as f32, c.a as f32]
333            } else {
334                tracing::debug!(
335                    "Style evaluation failed for feature properties: {:?}, style: {:?}",
336                    self.feature_properties,
337                    style
338                );
339                self.fallback_color
340            }
341        } else {
342            self.fallback_color
343        };
344
345        self.feature_colors.push(color);
346        self.feature_properties.clear();
347        Ok(())
348    }
349}
maplibre/vector/tessellation.rs

maplibre/vector/
tessellation.rs
