density_mesh_core/generator/
mod.rs

1pub mod process_status;
2mod processing_change;
3
4use crate::{
5    coord::Coord,
6    generator::{process_status::ProcessStatus, processing_change::ProcessingChange},
7    map::{DensityMap, DensityMapError},
8    mesh::{
9        points_separation::PointsSeparation, settings::GenerateDensityMeshSettings, DensityMesh,
10        GenerateDensityMeshError,
11    },
12    triangle::Triangle,
13    Scalar,
14};
15#[cfg(feature = "parallel")]
16use rayon::prelude::*;
17use serde::{Deserialize, Serialize};
18use std::{
19    collections::VecDeque,
20    time::{Duration, Instant},
21};
22use triangulation::{Delaunay, Point};
23
24#[cfg(feature = "parallel")]
25macro_rules! into_iter {
26    ($v:expr) => {
27        $v.into_par_iter()
28    };
29}
30
31#[cfg(not(feature = "parallel"))]
32macro_rules! into_iter {
33    ($v:expr) => {
34        $v.into_iter()
35    };
36}
37
38/// Generate density mesh with region changes.
39/// For now it recalculates mesh from whole density map data.
40#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
41pub struct DensityMeshGenerator {
42    map: DensityMap,
43    mesh: Option<DensityMesh>,
44    /// [([points], settings)]
45    queue: VecDeque<(Vec<Coord>, GenerateDensityMeshSettings)>,
46    current: Option<ProcessingChange>,
47}
48
49impl DensityMeshGenerator {
50    /// Create new generator.
51    ///
52    /// # Arguments
53    /// * `points` - Initial points.
54    /// * `map` - Density map.
55    /// * `settings` - Settings.
56    ///
57    /// # Returns
58    /// New generator instance.
59    pub fn new(points: Vec<Coord>, map: DensityMap, settings: GenerateDensityMeshSettings) -> Self {
60        let mut queue = VecDeque::with_capacity(1);
61        queue.push_back((points, settings));
62        Self {
63            map,
64            mesh: None,
65            queue,
66            current: None,
67        }
68    }
69
70    /// Get inner density map.
71    pub fn map(&self) -> &DensityMap {
72        &self.map
73    }
74
75    /// Get inner density mesh if one is already generated.
76    pub fn mesh(&self) -> Option<&DensityMesh> {
77        self.mesh.as_ref()
78    }
79
80    pub fn into_mesh(self) -> Option<DensityMesh> {
81        self.mesh
82    }
83
84    /// Tells if there are changes left to process.
85    pub fn in_progress(&self) -> bool {
86        self.current.is_some() || !self.queue.is_empty()
87    }
88
89    /// Get processing progress.
90    ///
91    /// # Returns
92    /// `(current, limit, percentage)`
93    pub fn progress(&self) -> (usize, usize, Scalar) {
94        match &self.current {
95            Some(ProcessingChange::FindingPoints {
96                progress_current,
97                progress_limit,
98                ..
99            }) => (
100                *progress_current,
101                *progress_limit,
102                *progress_current as Scalar / *progress_limit as Scalar,
103            ),
104            Some(ProcessingChange::Triangulate { progress_limit, .. }) => {
105                (*progress_limit, *progress_limit, 1.0)
106            }
107            Some(ProcessingChange::RemoveInvisibleTriangles { progress_limit, .. }) => {
108                (*progress_limit, *progress_limit, 1.0)
109            }
110            Some(ProcessingChange::Extrude { progress_limit, .. }) => {
111                (*progress_limit, *progress_limit, 1.0)
112            }
113            _ => (0, 0, 0.0),
114        }
115    }
116
117    /// Add map change to the pending queue.
118    ///
119    /// # Arguments
120    /// * `col` - Density map destination column.
121    /// * `row` - Density map destination row.
122    /// * `width` - Source data unscaled width.
123    /// * `height` - Source data unscaled height.
124    /// * `data` - Source data buffer.
125    /// * `settings` - Density mesh generation settings applied for this change.
126    ///
127    /// # Returns
128    /// Ok if successful or density map error.
129    pub fn change_map(
130        &mut self,
131        col: usize,
132        row: usize,
133        width: usize,
134        height: usize,
135        data: Vec<u8>,
136        settings: GenerateDensityMeshSettings,
137    ) -> Result<(), DensityMapError> {
138        self.map.change(col, row, width, height, data)?;
139        self.queue.push_back((vec![], settings));
140        Ok(())
141    }
142
143    /// Process penging change.
144    ///
145    /// # Returns
146    /// Result with process status when ok, otherwise error.
147    #[allow(clippy::many_single_char_names)]
148    pub fn process(&mut self) -> Result<ProcessStatus, GenerateDensityMeshError> {
149        if let Some(current) = std::mem::replace(&mut self.current, None) {
150            match current {
151                ProcessingChange::FindingPoints {
152                    settings,
153                    mut tries,
154                    mut remaining,
155                    mut points,
156                    mut progress_current,
157                    progress_limit,
158                } => {
159                    if !points.is_empty() {
160                        remaining = into_iter!(remaining)
161                            .filter(|(p1, _, _, lpss)| {
162                                points.iter().all(|p2| (*p2 - *p1).sqr_magnitude() > *lpss)
163                            })
164                            .collect::<Vec<_>>();
165                        if remaining.is_empty() {
166                            self.current = Some(ProcessingChange::Triangulate {
167                                settings,
168                                points,
169                                progress_limit,
170                            });
171                            return Ok(ProcessStatus::InProgress);
172                        }
173                    }
174                    if let Some((point, _, _, _)) = remaining
175                        .iter()
176                        .max_by(|a, b| a.2.partial_cmp(&b.2).unwrap())
177                    {
178                        points.push(*point);
179                        tries = settings.max_iterations;
180                    } else if tries > 0 {
181                        tries -= 1;
182                        self.current = Some(ProcessingChange::FindingPoints {
183                            settings,
184                            tries,
185                            remaining,
186                            points,
187                            progress_current,
188                            progress_limit,
189                        });
190                        return Ok(ProcessStatus::InProgress);
191                    } else {
192                        self.current = Some(ProcessingChange::Triangulate {
193                            settings,
194                            points,
195                            progress_limit,
196                        });
197                        return Ok(ProcessStatus::InProgress);
198                    }
199                    progress_current = progress_limit - remaining.len();
200                    self.current = Some(ProcessingChange::FindingPoints {
201                        settings,
202                        tries,
203                        remaining,
204                        points,
205                        progress_current,
206                        progress_limit,
207                    });
208                    Ok(ProcessStatus::InProgress)
209                }
210                ProcessingChange::Triangulate {
211                    settings,
212                    points,
213                    progress_limit,
214                } => {
215                    let dpoints = points
216                        .iter()
217                        .map(|v| Point::new(v.x, v.y))
218                        .collect::<Vec<_>>();
219                    let triangulation = if let Some(triangulation) = Delaunay::new(&dpoints) {
220                        triangulation
221                    } else {
222                        return Err(GenerateDensityMeshError::FailedTriangulation);
223                    };
224                    let triangles = triangulation
225                        .dcel
226                        .vertices
227                        .chunks(3)
228                        .map(|t| Triangle {
229                            a: t[0],
230                            b: t[1],
231                            c: t[2],
232                        })
233                        .collect::<Vec<_>>();
234                    if !settings.keep_invisible_triangles {
235                        self.current = Some(ProcessingChange::RemoveInvisibleTriangles {
236                            settings,
237                            points,
238                            triangles,
239                            progress_limit,
240                        });
241                        Ok(ProcessStatus::InProgress)
242                    } else if let Some(size) = settings.extrude_size {
243                        self.current = Some(ProcessingChange::Extrude {
244                            points,
245                            triangles,
246                            size,
247                            progress_limit,
248                        });
249                        Ok(ProcessStatus::InProgress)
250                    } else {
251                        self.mesh = Some(DensityMesh { points, triangles });
252                        Ok(ProcessStatus::MeshChanged)
253                    }
254                }
255                ProcessingChange::RemoveInvisibleTriangles {
256                    settings,
257                    points,
258                    mut triangles,
259                    progress_limit,
260                } => {
261                    triangles = triangles
262                        .into_iter()
263                        .filter(|t| {
264                            Self::is_triangle_visible(
265                                points[t.a],
266                                points[t.b],
267                                points[t.c],
268                                &self.map,
269                                &settings,
270                            )
271                        })
272                        .collect::<Vec<_>>();
273                    if let Some(size) = settings.extrude_size {
274                        self.current = Some(ProcessingChange::Extrude {
275                            points,
276                            triangles,
277                            size,
278                            progress_limit,
279                        });
280                        Ok(ProcessStatus::InProgress)
281                    } else {
282                        self.mesh = Some(DensityMesh { points, triangles });
283                        Ok(ProcessStatus::MeshChanged)
284                    }
285                }
286                ProcessingChange::Extrude {
287                    mut points,
288                    mut triangles,
289                    size,
290                    ..
291                } => {
292                    let (p, t) = Self::extrude(&points, &triangles, size);
293                    points.extend(p);
294                    triangles.extend(t);
295                    self.mesh = Some(DensityMesh { points, triangles });
296                    Ok(ProcessStatus::MeshChanged)
297                }
298            }
299        } else if let Some((points, settings)) = self.queue.pop_front() {
300            let scale = self.map.scale();
301            let remaining = self
302                .map
303                .value_steepness_iter()
304                .filter_map(|(x, y, v, s)| {
305                    if v > settings.visibility_threshold && s > settings.steepness_threshold {
306                        let x = (x * scale) as Scalar;
307                        let y = (y * scale) as Scalar;
308                        let lpss = match settings.points_separation {
309                            PointsSeparation::Constant(v) => v * v,
310                            PointsSeparation::SteepnessMapping(f, t) => {
311                                let v = Self::lerp(s, t, f);
312                                v * v
313                            }
314                        };
315                        Some((Coord::new(x, y), v, s, lpss))
316                    } else {
317                        None
318                    }
319                })
320                .collect::<Vec<_>>();
321            let progress_limit = remaining.len();
322            let tries = settings.max_iterations;
323            self.current = Some(ProcessingChange::FindingPoints {
324                settings,
325                tries,
326                remaining,
327                points,
328                progress_current: 0,
329                progress_limit,
330            });
331            Ok(ProcessStatus::InProgress)
332        } else {
333            Ok(ProcessStatus::Idle)
334        }
335    }
336
337    /// Process incoming changes until none is left to do.
338    ///
339    /// # Returns
340    /// Ok or generation error.
341    pub fn process_wait(&mut self) -> Result<(), GenerateDensityMeshError> {
342        while self.process()? == ProcessStatus::InProgress {}
343        Ok(())
344    }
345
346    /// Process incoming changes until none is left to do.
347    ///
348    /// # Arguments
349    /// * `timeout` - Duration of time that processing can take.
350    ///
351    /// # Returns
352    /// Process status or generation error.
353    pub fn process_wait_timeout(
354        &mut self,
355        timeout: Duration,
356    ) -> Result<ProcessStatus, GenerateDensityMeshError> {
357        let timer = Instant::now();
358        loop {
359            let status = self.process()?;
360            if status != ProcessStatus::InProgress || timer.elapsed() > timeout {
361                return Ok(status);
362            }
363        }
364    }
365
366    /// Process incoming changes until none is left to do.
367    ///
368    /// # Arguments
369    /// * `f` - Callback triggered on every processing step. Signature: `fn(progress, limit, factor)`.
370    ///
371    /// # Returns
372    /// Ok or generation error.
373    pub fn process_wait_tracked<F>(&mut self, mut f: F) -> Result<(), GenerateDensityMeshError>
374    where
375        F: FnMut(usize, usize, Scalar),
376    {
377        let (c, l, p) = self.progress();
378        f(c, l, p);
379        while self.process()? == ProcessStatus::InProgress {
380            let (c, l, p) = self.progress();
381            f(c, l, p);
382        }
383        Ok(())
384    }
385
386    /// Process incoming changes until none is left to do.
387    ///
388    /// # Arguments
389    /// * `f` - Callback triggered on every processing step. Signature: `fn(progress, limit, factor)`.
390    /// * `timeout` - Duration of time that processing can take.
391    ///
392    /// # Returns
393    /// Process status or generation error.
394    pub fn process_wait_timeout_tracked<F>(
395        &mut self,
396        mut f: F,
397        timeout: Duration,
398    ) -> Result<ProcessStatus, GenerateDensityMeshError>
399    where
400        F: FnMut(usize, usize, Scalar),
401    {
402        let timer = Instant::now();
403        let (c, l, p) = self.progress();
404        f(c, l, p);
405        loop {
406            let status = self.process()?;
407            let (c, l, p) = self.progress();
408            f(c, l, p);
409            if status != ProcessStatus::InProgress || timer.elapsed() > timeout {
410                return Ok(status);
411            }
412        }
413    }
414
415    fn extrude(
416        points: &[Coord],
417        triangles: &[Triangle],
418        size: Scalar,
419    ) -> (Vec<Coord>, Vec<Triangle>) {
420        let edges = triangles
421            .iter()
422            .enumerate()
423            .flat_map(|(i, t)| vec![(i, t.a, t.b), (i, t.b, t.c), (i, t.c, t.a)])
424            .collect::<Vec<_>>();
425        let outline = edges
426            .iter()
427            .filter(|e1| {
428                !edges
429                    .iter()
430                    .any(|e2| e1.0 != e2.0 && Self::are_edges_connected(e1.1, e1.2, e2.1, e2.2))
431            })
432            .collect::<Vec<_>>();
433        let offsets = outline
434            .iter()
435            .map(|(_, m, n)| {
436                let i = *m;
437                let p = outline.iter().find(|(_, _, p)| p == m).unwrap().1;
438                let p = points[p];
439                let m = points[*m];
440                let n = points[*n];
441                let pm = -(m - p).normalized().right();
442                let mn = -(n - m).normalized().right();
443                (i, m + (pm + mn).normalized() * size)
444            })
445            .collect::<Vec<_>>();
446        let triangles = outline
447            .into_iter()
448            .flat_map(|(_, a, b)| {
449                let ea = offsets.iter().position(|(ea, _)| ea == a).unwrap() + points.len();
450                let eb = offsets.iter().position(|(eb, _)| eb == b).unwrap() + points.len();
451                vec![[*b, *a, ea].into(), [ea, eb, *b].into()]
452            })
453            .collect::<Vec<_>>();
454        (
455            offsets.into_iter().map(|(_, p)| p).collect::<Vec<_>>(),
456            triangles,
457        )
458    }
459
460    fn are_edges_connected(a_from: usize, a_to: usize, b_from: usize, b_to: usize) -> bool {
461        (a_from == b_from && a_to == b_to) || (a_from == b_to && a_to == b_from)
462    }
463
464    fn is_triangle_visible(
465        a: Coord,
466        b: Coord,
467        c: Coord,
468        map: &DensityMap,
469        settings: &GenerateDensityMeshSettings,
470    ) -> bool {
471        let fx = (a.x as isize).min(b.x as isize).min(c.x as isize);
472        let fy = (a.y as isize).min(b.y as isize).min(c.y as isize);
473        let tx = (a.x as isize).max(b.x as isize).max(c.x as isize);
474        let ty = (a.y as isize).max(b.y as isize).max(c.y as isize);
475        let nab = (b - a).right();
476        let nbc = (c - b).right();
477        let nca = (a - c).right();
478        let mut count = 0;
479        let mut samples = 0;
480        for y in fy..=ty {
481            for x in fx..=tx {
482                let p = Coord::new(x as _, y as _);
483                if (p - a).dot(nab) >= 0.0 && (p - b).dot(nbc) >= 0.0 && (p - c).dot(nca) >= 0.0 {
484                    samples += 1;
485                    if Self::is_point_visible((x, y), map, settings) {
486                        count += 1;
487                    }
488                }
489            }
490        }
491        count as Scalar / samples as Scalar > 0.5
492    }
493
494    #[inline]
495    fn is_point_visible(
496        pos: (isize, isize),
497        map: &DensityMap,
498        settings: &GenerateDensityMeshSettings,
499    ) -> bool {
500        map.value_at_point(pos) > settings.visibility_threshold
501    }
502
503    #[inline]
504    fn lerp(value: Scalar, from: Scalar, to: Scalar) -> Scalar {
505        from + (to - from) * value.max(0.0).min(1.0)
506    }
507}
density_mesh_core/generator/mod.rs

density_mesh_core/generator/
mod.rs
