brep_kernel/meshing/
mesh_weld.rs

1//! Vertex welding and undirected edge keys for triangle meshes.
2//!
3//! The one tolerance weld (record item G3, 2026-11-01): `floor` cells of
4//! twice the tolerance, the 27-cell neighbourhood, a match at
5//! `distance <= tolerance`, and the LOWEST-index matching vertex as the
6//! representative, so the result does not depend on bucket or scan order.
7
8use crate::Vec3;
9use rustc_hash::FxHashMap as HashMap;
10
11/// Bits of `value` with negative zero read as positive zero, for exact
12/// (bitwise) point keys: `-0.0` and `0.0` are the same coordinate.
13pub fn canonical_bits(value: f64) -> u64 {
14    if value == 0.0 {
15        0
16    } else {
17        value.to_bits()
18    }
19}
20
21/// The weld cell of `point`: `floor(p / (2 tol))`. At a cell of `tol` a pair
22/// exactly `tol` apart can land two cells apart once the division rounds
23/// (and `round` puts ±0.5 two cells apart outright), outside the
24/// neighbourhood; at `2 tol` every match is at most one cell away (the
25/// sew.rs `EndpointGrid` reasoning).
26fn cell(point: Vec3, tolerance: f64) -> [i64; 3] {
27    let size = 2.0 * tolerance;
28    [
29        (point.x / size).floor() as i64,
30        (point.y / size).floor() as i64,
31        (point.z / size).floor() as i64,
32    ]
33}
34
35/// The index of the lowest-index vertex within `tolerance` of `point`, or
36/// `point` appended as a new vertex. `buckets` maps a cell to its vertices
37/// in insertion (= index) order.
38pub(crate) fn weld_vertex(
39    point: Vec3,
40    tolerance: f64,
41    vertices: &mut Vec<Vec3>,
42    buckets: &mut HashMap<[i64; 3], Vec<usize>>,
43) -> usize {
44    let key = cell(point, tolerance);
45    let mut matched: Option<usize> = None;
46    for dx in -1..=1 {
47        for dy in -1..=1 {
48            for dz in -1..=1 {
49                if let Some(indices) = buckets.get(&[key[0] + dx, key[1] + dy, key[2] + dz]) {
50                    // Ascending within a bucket: the first match is its lowest.
51                    if let Some(index) = indices
52                        .iter()
53                        .copied()
54                        .find(|index| vertices[*index].sub(point).length() <= tolerance)
55                    {
56                        matched = Some(matched.map_or(index, |current| current.min(index)));
57                    }
58                }
59            }
60        }
61    }
62    if let Some(index) = matched {
63        return index;
64    }
65    let index = vertices.len();
66    vertices.push(point);
67    buckets.entry(key).or_default().push(index);
68    index
69}
70
71/// A tolerance weld over points given one at a time (`weld_vertex` with
72/// its own vertex list and cells), for callers outside the kernel.
73#[derive(Clone, Debug, Default)]
74pub struct VertexWeld {
75    tolerance: f64,
76    vertices: Vec<Vec3>,
77    buckets: HashMap<[i64; 3], Vec<usize>>,
78}
79
80impl VertexWeld {
81    /// An empty weld that merges points within `tolerance` (> 0).
82    pub fn new(tolerance: f64) -> Self {
83        Self {
84            tolerance,
85            ..Self::default()
86        }
87    }
88
89    /// The index of the lowest-index welded vertex within the tolerance of
90    /// `point`, or the index `point` is appended at.
91    pub fn weld(&mut self, point: [f64; 3]) -> usize {
92        weld_vertex(
93            Vec3::new(point[0], point[1], point[2]),
94            self.tolerance,
95            &mut self.vertices,
96            &mut self.buckets,
97        )
98    }
99
100    /// The welded vertex at `index` (the first point that created it).
101    pub fn vertex(&self, index: usize) -> [f64; 3] {
102        let v = self.vertices[index];
103        [v.x, v.y, v.z]
104    }
105
106    /// The number of welded vertices.
107    pub fn len(&self) -> usize {
108        self.vertices.len()
109    }
110
111    /// Whether no point has been welded yet.
112    pub fn is_empty(&self) -> bool {
113        self.vertices.is_empty()
114    }
115}
116
117pub(crate) fn edge_key(first: usize, second: usize) -> (usize, usize) {
118    if first < second {
119        (first, second)
120    } else {
121        (second, first)
122    }
123}
124
brep_kernel/meshing/mesh_weld.rs

brep_kernel/meshing/
mesh_weld.rs
