brepkit_operations/tessellate/
mod.rs

1//! Tessellation: convert B-Rep faces to triangle meshes.
2
3#![allow(
4    clippy::many_single_char_names,
5    clippy::similar_names,
6    clippy::suboptimal_flops,
7    clippy::needless_range_loop,
8    clippy::cast_precision_loss,
9    clippy::doc_markdown,
10    clippy::cast_possible_truncation,
11    clippy::manual_let_else,
12    clippy::tuple_array_conversions,
13    clippy::imprecise_flops,
14    clippy::too_many_lines,
15    clippy::option_if_let_else,
16    clippy::bool_to_int_with_if,
17    clippy::if_same_then_else,
18    clippy::used_underscore_binding,
19    clippy::map_unwrap_or
20)]
21
22mod edge_sampling;
23mod face;
24mod mesh_ops;
25mod nonplanar;
26mod nurbs;
27mod planar;
28mod solid;
29#[cfg(test)]
30mod tests;
31
32use brepkit_math::vec::{Point3, Vec3};
33use brepkit_topology::Topology;
34use brepkit_topology::face::FaceId;
35
36// Re-export all public items.
37pub use face::{tessellate_with_uvs, tessellate_with_uvs_a};
38pub(crate) use mesh_ops::COINCIDENT_DEDUPE_GRID;
39pub use mesh_ops::{
40    EdgeLines, boundary_edge_count, is_watertight, non_manifold_edge_count, sample_solid_edges,
41    sample_solid_edges_filtered,
42};
43pub use solid::{
44    tessellate_solid, tessellate_solid_for_boolean, tessellate_solid_grouped_with_tolerance,
45    tessellate_solid_with_tolerance,
46};
47
48/// Merge-grid cell size for tolerance-based vertex deduplication.
49///
50/// Vertices within this distance are quantized to the same grid cell and share
51/// a single global vertex index. This catches near-identical vertices produced
52/// when boolean operations create separate edge entities for the same curve.
53const MERGE_GRID: f64 = 1e-7;
54
55/// Quantize a 3D point to a spatial grid cell for tolerance-based deduplication.
56///
57/// Two points whose coordinates differ by less than `grid` will (usually) map to
58/// the same `(i64, i64, i64)` key. Grid-boundary splits are possible but rare,
59/// and the subsequent CDT / weld phases handle any remaining gaps.
60pub(super) fn point_merge_key(pt: Point3, grid: f64) -> (i64, i64, i64) {
61    #[allow(clippy::cast_possible_truncation)]
62    (
63        (pt.x() / grid).round() as i64,
64        (pt.y() / grid).round() as i64,
65        (pt.z() / grid).round() as i64,
66    )
67}
68
69/// Compute the shorter arc range (<=pi) from an edge's start to end on a circle.
70///
71/// Returns `(t_start, t_end)` where the shorter arc goes from `t_start` to `t_end`.
72/// When the shorter arc is CW, `t_end < t_start` so that linear interpolation
73/// between them traces the correct (shorter) path via `circle.evaluate()`.
74pub(super) fn shorter_arc_range(
75    circle: &brepkit_math::curves::Circle3D,
76    topo: &Topology,
77    edge: &brepkit_topology::edge::Edge,
78) -> Result<(f64, f64), crate::OperationsError> {
79    let sp = topo.vertex(edge.start())?.point();
80    let ep = topo.vertex(edge.end())?.point();
81    let ts = circle.project(sp);
82    let te_raw = circle.project(ep);
83    let fwd_span = (te_raw - ts).rem_euclid(std::f64::consts::TAU);
84    if fwd_span <= std::f64::consts::PI {
85        // CCW arc is the shorter path.
86        Ok((ts, ts + fwd_span))
87    } else {
88        // CW arc is shorter: t_end < t_start so interpolation goes backward.
89        let rev_span = std::f64::consts::TAU - fwd_span;
90        Ok((ts, ts - rev_span))
91    }
92}
93
94/// A triangle mesh produced by tessellation.
95#[derive(Debug, Clone, Default)]
96pub struct TriangleMesh {
97    /// Vertex positions.
98    pub positions: Vec<Point3>,
99    /// Per-vertex normals.
100    pub normals: Vec<Vec3>,
101    /// Triangle indices (groups of 3).
102    pub indices: Vec<u32>,
103}
104
105/// A triangle mesh with per-vertex UV coordinates.
106#[derive(Debug, Clone, Default)]
107pub struct TriangleMeshUV {
108    /// The base mesh (positions, normals, indices).
109    pub mesh: TriangleMesh,
110    /// Per-vertex UV coordinates (same length as `mesh.positions`).
111    pub uvs: Vec<[f64; 2]>,
112}
113
114/// Kind of special handling needed for analytic surface tessellation.
115pub(super) enum AnalyticKind {
116    /// Standard quad grid with no degenerate handling.
117    General,
118    /// Triangle fan at v extremes (sphere poles at v_min and v_max).
119    SpherePole,
120    /// Triangle fan at v_min (cone apex at v = 0).
121    ConeApex,
122    /// Triangle fan at v_max only (sphere north pole for a hemisphere face).
123    VMaxPole,
124}
125
126/// Tessellate a face into a triangle mesh.
127///
128/// For planar faces, this performs fan triangulation from the first vertex,
129/// which produces correct results for convex polygons.
130///
131/// For NURBS faces, the surface is sampled on a uniform (u, v) grid whose
132/// density is derived from `deflection` — smaller values produce finer meshes.
133///
134/// # Errors
135///
136/// Returns an error if the face geometry cannot be tessellated.
137pub fn tessellate(
138    topo: &Topology,
139    face: FaceId,
140    deflection: f64,
141) -> Result<TriangleMesh, crate::OperationsError> {
142    tessellate_with_uvs(topo, face, deflection).map(|uv| uv.mesh)
143}
144
145/// Tessellate a face with explicit linear and angular tolerances.
146///
147/// `angular_tol` (radians) caps the per-segment tangent turn; pass `0.0` to
148/// disable the angular criterion (linear-only path).
149///
150/// # Errors
151///
152/// Returns an error if the face geometry cannot be tessellated.
153pub fn tessellate_with_tolerance(
154    topo: &Topology,
155    face: FaceId,
156    deflection: f64,
157    angular_tol: f64,
158) -> Result<TriangleMesh, crate::OperationsError> {
159    face::tessellate_with_uvs_a(topo, face, deflection, angular_tol).map(|uv| uv.mesh)
160}
161
162/// Check if a mesh is watertight (every edge shared by exactly 2 triangles).
163///
164/// Returns `true` if the mesh is a closed 2-manifold: every half-edge
165/// `(a, b)` in the mesh has a corresponding reverse half-edge `(b, a)`.
166///
167/// This is useful for validating that `tessellate_solid` produces
168/// gap-free meshes.
169#[cfg(test)]
170#[must_use]
171pub(super) fn position_based_boundary_count(mesh: &TriangleMesh) -> usize {
172    /// 1um grid -- intentionally coarser than `MERGE_GRID` (1e-7) to catch
173    /// gaps the production pipeline should have closed.
174    const DIAGNOSTIC_GRID: f64 = 1e-6;
175
176    use brepkit_math::det_hash::{DetHashMap, DetHashSet};
177
178    // Build canonical vertex ID from snapped position.
179    let mut pos_to_canonical: DetHashMap<(i64, i64, i64), u32> = DetHashMap::default();
180    let mut canonical_ids: Vec<u32> = Vec::with_capacity(mesh.positions.len());
181    let mut next_id: u32 = 0;
182
183    for pos in &mesh.positions {
184        let key = point_merge_key(*pos, DIAGNOSTIC_GRID);
185        let id = *pos_to_canonical.entry(key).or_insert_with(|| {
186            let id = next_id;
187            next_id += 1;
188            id
189        });
190        canonical_ids.push(id);
191    }
192
193    // Build half-edge set using canonical IDs.
194    let mut half_edges: DetHashSet<(u32, u32)> = DetHashSet::default();
195    for tri in mesh.indices.chunks_exact(3) {
196        let i0 = canonical_ids[tri[0] as usize];
197        let i1 = canonical_ids[tri[1] as usize];
198        let i2 = canonical_ids[tri[2] as usize];
199        half_edges.insert((i0, i1));
200        half_edges.insert((i1, i2));
201        half_edges.insert((i2, i0));
202    }
203
204    half_edges
205        .iter()
206        .filter(|&&(a, b)| !half_edges.contains(&(b, a)))
207        .count()
208}
brepkit_operations/tessellate/mod.rs

brepkit_operations/tessellate/
mod.rs
