mesh_graph/plane_slice/
mod.rs

1mod hash_grid;
2mod polygon;
3
4#[cfg(feature = "rerun")]
5use std::iter::repeat_n;
6
7use glam::{Mat4, Vec2, Vec3, Vec3Swizzles, Vec4, Vec4Swizzles};
8pub use hash_grid::*;
9pub use polygon::*;
10use slotmap::SecondaryMap;
11
12#[cfg(feature = "rerun")]
13use crate::utils::vec3_array;
14use crate::{MeshGraph, VertexId};
15
16pub fn plane_slice(
17    mesh_graph: &MeshGraph,
18    plane_normal: Vec3,
19    plane_constant: f32,
20) -> impl Iterator<Item = Polygon3> {
21    let plane_normal = plane_normal.normalize();
22
23    #[cfg(feature = "rerun")]
24    {
25        use glam::Quat;
26
27        use crate::utils::{quat_array, vec3_array};
28
29        crate::RR
30            .log(
31                "mesh",
32                &rerun::Points3D::new(mesh_graph.positions.values().map(vec3_array)),
33            )
34            .unwrap();
35
36        let pivot = plane_normal * plane_constant;
37
38        crate::RR
39            .log(
40                "slice_plane",
41                &rerun::Ellipsoids3D::from_centers_and_half_sizes(
42                    [(pivot.x, pivot.y, pivot.z)],
43                    [(10.0, 10.0, 0.0)],
44                )
45                .with_quaternions([quat_array(Quat::from_rotation_arc_colinear(
46                    Vec3::Z,
47                    plane_normal,
48                ))]),
49            )
50            .unwrap();
51
52        crate::RR
53            .log(
54                "slice_plane/normal",
55                &rerun::Arrows3D::from_vectors([vec3_array(plane_normal)])
56                    .with_origins([vec3_array(pivot)]),
57            )
58            .unwrap();
59    }
60
61    let transform = compute_transform_from_plane_into_xy(plane_normal, plane_constant);
62
63    let mut transformed_positions = SecondaryMap::new();
64    let mut min_bounds = Vec2::splat(f32::INFINITY);
65    let mut max_bounds = Vec2::splat(f32::NEG_INFINITY);
66
67    for (vertex_id, vertex) in mesh_graph.positions.iter() {
68        let transformed_vertex = transform * vertex.extend(1.0);
69
70        debug_assert!((transformed_vertex.w - 1.0).abs() < 1e-6);
71
72        let transformed = transformed_vertex.xyz();
73        let transformed_2d = transformed.xy();
74        transformed_positions.insert(vertex_id, transformed);
75
76        // Update bounding box
77        min_bounds = min_bounds.min(transformed_2d);
78        max_bounds = max_bounds.max(transformed_2d);
79    }
80
81    #[cfg(feature = "rerun")]
82    {
83        use crate::utils::vec3_array;
84
85        crate::RR
86            .log(
87                "plane_slice/points_transformed",
88                &rerun::Points3D::new(transformed_positions.values().copied().map(vec3_array)),
89            )
90            .unwrap();
91    }
92
93    let mut hash_grid = HashGrid::new(min_bounds, max_bounds);
94
95    for face in mesh_graph.faces.values() {
96        if let Some((point1, point2)) =
97            intersect_triangle_with_xy_plane(mesh_graph, &transformed_positions, face)
98        {
99            hash_grid.insert_line(point1, point2);
100        }
101    }
102
103    let transform_inv = transform.inverse();
104
105    hash_grid
106        .into_polygons()
107        .map(move |p| Polygon3::from_polygon2_with_transform(p, transform_inv))
108}
109
110fn intersect_triangle_with_xy_plane(
111    mesh_graph: &MeshGraph,
112    transformed_positions: &SecondaryMap<VertexId, Vec3>,
113    face: &crate::Face,
114) -> Option<(Vec2, Vec2)> {
115    let vertices: Vec<Vec3> = face
116        .vertices(mesh_graph)
117        .map(|v| transformed_positions[v])
118        .collect();
119
120    // Compute signed distances from each vertex to the XY plane (z=0)
121    let distances: [f32; 3] = [vertices[0].z, vertices[1].z, vertices[2].z];
122
123    // Find intersections with triangle edges
124    let mut intersection_points = Vec::new();
125
126    for i in 0..3 {
127        let j = (i + 1) % 3;
128        let d1 = distances[i];
129        let d2 = distances[j];
130
131        // Check if edge crosses the XY plane (signs are different and not both zero)
132        if (d1 > 0.0 && d2 < 0.0) || (d1 < 0.0 && d2 > 0.0) {
133            // Compute intersection point using linear interpolation
134            let t = d1 / (d1 - d2);
135            let intersection = vertices[i] + t * (vertices[j] - vertices[i]);
136            intersection_points.push(intersection);
137        } else if d1.abs() < f32::EPSILON {
138            // Vertex is exactly on the XY plane
139            intersection_points.push(vertices[i]);
140        }
141    }
142
143    // Remove duplicate points
144    intersection_points.dedup_by(|a, b| (*a - *b).length() < f32::EPSILON);
145
146    // Create line segment if we have exactly 2 intersections
147    if intersection_points.len() == 2 {
148        debug_assert!(intersection_points[0].z.abs() < 1e-6);
149        debug_assert!(intersection_points[1].z.abs() < 1e-6);
150
151        Some((intersection_points[0].xy(), intersection_points[1].xy()))
152    } else {
153        None
154    }
155}
156
157fn compute_transform_from_plane_into_xy(plane_normal: Vec3, plane_constant: f32) -> Mat4 {
158    // Create an orthonormal basis where n is the Z-axis
159    // Find a vector perpendicular to n
160    let up = if plane_normal.x.abs() < 0.9 {
161        Vec3::X
162    } else {
163        Vec3::Y
164    };
165
166    // Create two perpendicular vectors in the plane
167    let u = plane_normal.cross(up).normalize(); // First tangent vector
168    let v = u.cross(plane_normal).normalize(); // Second tangent vector
169
170    let point_on_plane = plane_constant * plane_normal;
171
172    #[cfg(feature = "rerun")]
173    crate::RR
174        .log(
175            "plane_axes",
176            &rerun::Arrows3D::from_vectors([
177                vec3_array(v),
178                vec3_array(u),
179                vec3_array(plane_normal),
180            ])
181            .with_origins(repeat_n(vec3_array(point_on_plane), 3))
182            .with_colors([(255, 0, 0), (0, 255, 0), (0, 0, 255)]),
183        )
184        .unwrap();
185
186    let rotation = Mat4::from_cols(
187        v.extend(0.0),
188        u.extend(0.0),
189        plane_normal.extend(0.0),
190        Vec4::W,
191    )
192    .transpose();
193
194    let translation = Mat4::from_translation(-point_on_plane);
195
196    rotation * translation
197}
198
199#[cfg(test)]
200mod tests {
201    use glam::Vec4;
202
203    use crate::primitives::IcoSphere;
204
205    use super::*;
206
207    #[test]
208    fn test_compute_identity_from_plane_into_xy() {
209        let plane_normal = Vec3::new(0.0, 0.0, 1.0);
210        let plane_constant = 0.0;
211
212        let transform = compute_transform_from_plane_into_xy(plane_normal, plane_constant);
213
214        assert_eq!(transform, Mat4::IDENTITY);
215    }
216
217    #[test]
218    fn test_compute_transform_from_plane_into_xy() {
219        #![allow(clippy::approx_constant)]
220
221        let plane_normal = Vec3::new(0.0, 1.0, 1.0).normalize();
222        let plane_constant = 6.3;
223
224        let transform = compute_transform_from_plane_into_xy(plane_normal, plane_constant);
225
226        assert_eq!(
227            transform,
228            Mat4 {
229                x_axis: Vec4::new(1.0, 0.0, 0.0, 0.0),
230                y_axis: Vec4::new(0.0, 0.7071068, 0.70710677, 0.0),
231                z_axis: Vec4::new(0.0, -0.7071068, 0.70710677, 0.0),
232                w_axis: Vec4::new(0.0, 0.0, -6.3, 1.0)
233            }
234        );
235    }
236
237    #[test]
238    fn test_intersect_triangle_with_xy_plane() {
239        let mesh_graph = MeshGraph::from(IcoSphere {
240            radius: 2.5,
241            subdivisions: 3,
242        });
243
244        let line = intersect_triangle_with_xy_plane(
245            &mesh_graph,
246            &mesh_graph.positions,
247            mesh_graph.faces.values().next().unwrap(),
248        );
249
250        assert!(line.is_none());
251
252        let line = intersect_triangle_with_xy_plane(
253            &mesh_graph,
254            &mesh_graph.positions,
255            mesh_graph.faces.values().nth(64).unwrap(),
256        );
257
258        assert_eq!(
259            line,
260            Some((
261                Vec2::new(-1.0083883, 2.2876086),
262                Vec2::new(-1.3143277, 2.126627)
263            ))
264        );
265    }
266
267    #[test]
268    fn test_icosphere_plane_slice() {
269        let mesh_graph = MeshGraph::from(IcoSphere {
270            radius: 2.5,
271            subdivisions: 3,
272        });
273
274        let plane_normal = Vec3::new(0.0, 0.5, 1.0).normalize();
275        let plane_constant = 1.2;
276
277        let mut polygons = plane_slice(&mesh_graph, plane_normal, plane_constant);
278
279        assert_eq!(
280            polygons.next(),
281            Some(Polygon3 {
282                vertices: [
283                    Vec3::new(2.0347278, 1.2575308, 0.71287555),
284                    Vec3::new(1.9029243, 1.5103028, 0.58648956),
285                    Vec3::new(1.8980179, 1.5179262, 0.58267784),
286                    Vec3::new(1.8750328, 1.5487651, 0.5672584),
287                    Vec3::new(1.7130562, 1.7552376, 0.46402216),
288                    Vec3::new(1.6560348, 1.8131003, 0.43509078),
289                    Vec3::new(1.4872973, 1.9698852, 0.35669833),
290                    Vec3::new(1.3088225, 2.1019301, 0.29067588),
291                    Vec3::new(1.231257, 2.1553543, 0.26396382),
292                    Vec3::new(1.159522, 2.194203, 0.2445395),
293                    Vec3::new(0.94288135, 2.3010523, 0.19111478),
294                    Vec3::new(0.7879911, 2.3584137, 0.16243404),
295                    Vec3::new(0.6283641, 2.4094386, 0.13692164),
296                    Vec3::new(0.41535905, 2.455471, 0.11390537),
297                    Vec3::new(0.3010591, 2.4739337, 0.10467416),
298                    Vec3::new(0.05938441, 2.4911098, 0.096085966),
299                    Vec3::new(-0.05938442, 2.4911098, 0.096085966),
300                    Vec3::new(-0.3010591, 2.4739337, 0.10467416),
301                    Vec3::new(-0.41535908, 2.455471, 0.11390537),
302                    Vec3::new(-0.6283641, 2.4094386, 0.13692164),
303                    Vec3::new(-0.7879911, 2.3584137, 0.16243404),
304                    Vec3::new(-0.94288135, 2.3010523, 0.19111478),
305                    Vec3::new(-1.159522, 2.194203, 0.2445395),
306                    Vec3::new(-1.231257, 2.1553543, 0.26396382),
307                    Vec3::new(-1.3088225, 2.1019301, 0.29067588),
308                    Vec3::new(-1.4872973, 1.9698852, 0.35669833),
309                    Vec3::new(-1.6560348, 1.8131003, 0.43509078),
310                    Vec3::new(-1.7130562, 1.7552376, 0.46402216),
311                    Vec3::new(-1.8750328, 1.5487651, 0.5672584),
312                    Vec3::new(-1.8980179, 1.5179262, 0.58267784),
313                    Vec3::new(-1.9029243, 1.5103028, 0.58648956),
314                    Vec3::new(-2.0347278, 1.2575308, 0.71287555),
315                    Vec3::new(-2.0585618, 1.2000002, 0.74164087),
316                    Vec3::new(-2.136093, 0.96047235, 0.8614048),
317                    Vec3::new(-2.1506572, 0.8914818, 0.8959),
318                    Vec3::new(-2.1845584, 0.65191114, 1.0156854),
319                    Vec3::new(-2.1866322, 0.5873947, 1.0479436),
320                    Vec3::new(-2.1780944, 0.3281218, 1.17758),
321                    Vec3::new(-2.1737561, 0.29807013, 1.1926059),
322                    Vec3::new(-2.142669, 0.14740404, 1.267939),
323                    Vec3::new(-2.1126394, 0.016977072, 1.3331524),
324                    Vec3::new(-2.089665, -0.044861794, 1.3640718),
325                    Vec3::new(-2.0094798, -0.23353845, 1.4584101),
326                    Vec3::new(-1.9672765, -0.31761312, 1.5004475),
327                    Vec3::new(-1.8720983, -0.46921265, 1.5762472),
328                    Vec3::new(-1.7555597, -0.6294868, 1.6563843),
329                    Vec3::new(-1.6925815, -0.70101833, 1.6921501),
330                    Vec3::new(-1.5054793, -0.8856908, 1.7844863),
331                    Vec3::new(-1.4743863, -0.9112208, 1.7972513),
332                    Vec3::new(-1.1747257, -1.1182102, 1.9007461),
333                    Vec3::new(-1.1614131, -1.1259825, 1.9046322),
334                    Vec3::new(-0.8734361, -1.259973, 1.9716275),
335                    Vec3::new(-0.8451933, -1.2710576, 1.9771698),
336                    Vec3::new(-0.55759066, -1.3547609, 2.0190215),
337                    Vec3::new(-0.48015964, -1.3725375, 2.0279098),
338                    Vec3::new(-0.2545036, -1.4035226, 2.0434022),
339                    Vec3::new(-0.09273741, -1.4171578, 2.0502198),
340                    Vec3::new(0.09273741, -1.4171578, 2.0502198),
341                    Vec3::new(0.2545036, -1.4035226, 2.0434022),
342                    Vec3::new(0.48015964, -1.3725375, 2.0279098),
343                    Vec3::new(0.55759066, -1.3547609, 2.0190215),
344                    Vec3::new(0.8451933, -1.2710576, 1.9771698),
345                    Vec3::new(0.8734361, -1.259973, 1.9716275),
346                    Vec3::new(1.1614131, -1.1259825, 1.9046322),
347                    Vec3::new(1.1747257, -1.1182102, 1.9007461),
348                    Vec3::new(1.4743863, -0.9112208, 1.7972513),
349                    Vec3::new(1.5054793, -0.8856908, 1.7844863),
350                    Vec3::new(1.6925815, -0.70101833, 1.6921501),
351                    Vec3::new(1.7555597, -0.6294868, 1.6563843),
352                    Vec3::new(1.8720983, -0.46921265, 1.5762472),
353                    Vec3::new(1.9672765, -0.31761312, 1.5004475),
354                    Vec3::new(2.0094798, -0.23353845, 1.4584101),
355                    Vec3::new(2.089665, -0.044861794, 1.3640718),
356                    Vec3::new(2.1126394, 0.016977072, 1.3331524),
357                    Vec3::new(2.142669, 0.14740404, 1.267939),
358                    Vec3::new(2.1737561, 0.29807013, 1.1926059),
359                    Vec3::new(2.1780944, 0.3281218, 1.17758),
360                    Vec3::new(2.1866322, 0.5873947, 1.0479436),
361                    Vec3::new(2.1845584, 0.65191114, 1.0156854),
362                    Vec3::new(2.1506572, 0.89148176, 0.8959001),
363                    Vec3::new(2.136093, 0.96047235, 0.8614048),
364                    Vec3::new(2.0585618, 1.2000002, 0.74164087),
365                    Vec3::new(2.0347278, 1.2575308, 0.71287555)
366                ]
367                .into()
368            })
369        );
370
371        assert!(polygons.next().is_none());
372    }
373}
mesh_graph/plane_slice/mod.rs

mesh_graph/plane_slice/
mod.rs
