use super::Mesh3;
use crate::geom2::CurveGroup2;
use crate::geom3::Aabb3;
use crate::geom3::mesh::edges::edge_key;
use crate::geom3::planar_map::vertex_length_weights;
use crate::{
Curve3, CurveGroup3, IndexMask, Line3, PlanarMap, Plane3, PlaneFrame, Point3, Result, Vector3,
};
use parry3d_f64::partitioning::TraversalAction;
use parry3d_f64::shape::TriMesh;
use std::collections::{HashMap, HashSet};
#[derive(Clone)]
pub struct PlanarSection {
pub curves: CurveGroup3,
pub map: PlanarMap,
}
impl PlanarSection {
pub fn to_2d(&self) -> Result<CurveGroup2> {
self.map.curve_group_to_2d(&self.curves)
}
pub fn into_parts(self) -> (CurveGroup3, PlanarMap) {
(self.curves, self.map)
}
}
fn frame_map(plane: &Plane3, frame: PlaneFrame, curves: &CurveGroup3) -> Result<PlanarMap> {
match frame {
PlaneFrame::Auto => Ok(PlanarMap::from_plane(plane)),
PlaneFrame::Oriented { origin, x } => PlanarMap::from_plane_oriented(plane, &origin, &x),
PlaneFrame::Svd => {
let mut points = Vec::new();
let mut weights = Vec::new();
for curve in curves.curves() {
points.extend_from_slice(curve.vertices());
weights.extend(vertex_length_weights(curve));
}
PlanarMap::from_plane_svd(plane, &points, Some(&weights))
}
}
}
impl Mesh3 {
pub fn section_with_plane(
&self,
plane: &Plane3,
frame: PlaneFrame,
curve_tol: Option<f64>,
faces: Option<&IndexMask>,
) -> Result<PlanarSection> {
let curve_tol = curve_tol.unwrap_or(1e-6);
let segments = self.section_segments(plane, faces)?;
let mut results = Vec::new();
for group in chain_segments(&segments) {
let mut curve_points = group.iter().map(|&i| segments[i].a).collect::<Vec<_>>();
curve_points.push(segments[group[group.len() - 1]].b);
results.push(Curve3::from_points(&curve_points, curve_tol)?);
}
if results.is_empty() {
return Err(if faces.is_some() {
"the plane does not intersect any of the selected faces".into()
} else {
Box::<dyn std::error::Error>::from("the plane does not intersect the mesh")
});
}
let curves = CurveGroup3::new(results)?;
let map = frame_map(plane, frame, &curves)?;
Ok(PlanarSection { curves, map })
}
pub(crate) fn section_segments(
&self,
plane: &Plane3,
faces: Option<&IndexMask>,
) -> Result<Vec<TriIntr>> {
if let Some(mask) = faces
&& mask.len() != self.face_count()
{
return Err(format!(
"A face mask of length {} does not match a mesh with {} faces",
mask.len(),
self.face_count()
)
.into());
}
let mut segments = Vec::new();
for face_i in candidate_faces(&self.shape, plane, faces) {
let Some(tri_n) = self.shape.triangle(face_i).normal() else {
continue;
};
let ai = self.faces()[face_i as usize][0];
let bi = self.faces()[face_i as usize][1];
let ci = self.faces()[face_i as usize][2];
let a = self.points()[ai as usize];
let b = self.points()[bi as usize];
let c = self.points()[ci as usize];
let ab = edge_intersection(&a, &b, plane);
let bc = edge_intersection(&b, &c, plane);
let ca = edge_intersection(&c, &a, plane);
let data = match (ab, bc, ca) {
(Some(ab), Some(bc), None) => {
TriIntr::new(ab, bc, edge_key(&[ai, bi]), edge_key(&[bi, ci]), face_i)
}
(None, Some(bc), Some(ca)) => {
TriIntr::new(bc, ca, edge_key(&[bi, ci]), edge_key(&[ci, ai]), face_i)
}
(Some(ab), None, Some(ca)) => {
TriIntr::new(ab, ca, edge_key(&[ai, bi]), edge_key(&[ci, ai]), face_i)
}
_ => Err("Something went wrong with the intersection calculation")?,
};
if tri_n.cross(&data.direction()).dot(&plane.normal) < 0.0 {
segments.push(data.reversed());
} else {
segments.push(data);
}
}
Ok(segments)
}
}
pub(crate) fn chain_segments(segments: &[TriIntr]) -> Vec<Vec<usize>> {
let mut edge_count = HashMap::<[u32; 2], usize>::new();
for segment in segments.iter() {
*edge_count.entry(segment.key_a).or_insert(0) += 1;
*edge_count.entry(segment.key_b).or_insert(0) += 1;
}
let terminations = edge_count
.iter()
.filter(|(_, count)| **count == 1 || **count > 2)
.map(|(&key, _)| key)
.collect::<HashSet<[u32; 2]>>();
let mut connected = Vec::new();
let mut work_bag = (0..segments.len()).collect::<Vec<_>>();
while !work_bag.is_empty() {
let mut current = vec![work_bag.pop().unwrap()];
while !terminations.contains(&segments[current[0]].key_a) {
let key_a = segments[current[0]].key_a;
let mut did_something = false;
for i in 0..work_bag.len() {
if segments[work_bag[i]].key_b == key_a {
current.insert(0, work_bag.remove(i));
did_something = true;
break;
}
}
if !did_something {
break;
}
}
while !terminations.contains(&segments[*current.last().unwrap()].key_b)
&& !is_loop(segments, ¤t)
&& !work_bag.is_empty()
{
let key_b = segments[*current.last().unwrap()].key_b;
let mut did_something = false;
for i in 0..work_bag.len() {
if segments[work_bag[i]].key_a == key_b {
current.push(work_bag.remove(i));
did_something = true;
break;
}
}
if !did_something {
break;
}
}
connected.push(current);
}
connected
}
fn is_loop(segments: &[TriIntr], working: &[usize]) -> bool {
let start = segments[working[0]].a;
let end = segments[working[working.len() - 1]].b;
start == end
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct TriIntr {
pub(crate) a: Point3,
pub(crate) b: Point3,
pub(crate) key_a: [u32; 2],
pub(crate) key_b: [u32; 2],
pub(crate) face: u32,
}
impl TriIntr {
fn new(a: Point3, b: Point3, key_a: [u32; 2], key_b: [u32; 2], face: u32) -> Self {
Self {
a,
b,
key_a,
key_b,
face,
}
}
fn reversed(&self) -> Self {
Self::new(self.b, self.a, self.key_b, self.key_a, self.face)
}
fn direction(&self) -> Vector3 {
(self.b - self.a).normalize()
}
pub(crate) fn length(&self) -> f64 {
(self.b - self.a).norm()
}
}
fn edge_intersection(a: &Point3, b: &Point3, plane: &Plane3) -> Option<Point3> {
if !intersects_edge(a, b, plane) {
return None;
}
let line = Line3::new(*a, *b - *a);
let t = line.intersect_plane(plane)?;
Some(line.at(t))
}
fn candidate_faces(shape: &TriMesh, plane: &Plane3, faces: Option<&IndexMask>) -> Vec<u32> {
let mut candidates = Vec::new();
shape.bvh().traverse(|node| {
if !aabb_plane(&node.aabb(), plane) {
return TraversalAction::Prune;
}
if let Some(index) = node.leaf_data() {
let t = shape.triangle(index);
if let Some(n) = t.normal()
&& n.cross(&plane.normal).norm_squared() > 1e-10
&& (intersects_edge(&t.a, &t.b, plane)
|| intersects_edge(&t.b, &t.c, plane)
|| intersects_edge(&t.c, &t.a, plane))
{
if let Some(mask) = faces {
if mask.get(index as usize) {
candidates.push(index);
}
} else {
candidates.push(index);
}
};
}
TraversalAction::Continue
});
candidates
}
fn intersects_edge(a: &Point3, b: &Point3, plane: &Plane3) -> bool {
let ap = plane.signed_distance_to_point(a).is_sign_positive();
let bp = plane.signed_distance_to_point(b).is_sign_positive();
ap != bp
}
fn aabb_plane(aabb: &Aabb3, plane: &Plane3) -> bool {
let mut pos = false;
let mut neg = false;
for v in aabb.vertices().iter() {
let p = plane.signed_distance_to_point(v).is_sign_positive();
pos = pos || p;
neg = neg || !p;
}
neg && pos
}
#[cfg(test)]
mod tests {
use super::*;
use crate::common::points::dist;
use crate::{Iso3, Vector3};
use approx::assert_relative_eq;
use std::f64::consts::TAU;
#[test]
fn candidates_box_has_eight() {
let mesh = Mesh3::create_box(2.0, 2.0, 2.0, false);
let plane = Plane3::new(Vector3::z_axis(), 0.0);
let candidates = candidate_faces(&mesh.shape, &plane, None);
assert_eq!(candidates.len(), 8);
}
#[test]
fn candidates_parallel_face_empty() {
let vertices = vec![
Point3::new(0.0, 0.0, 0.0),
Point3::new(1.0, 0.0, 0.0),
Point3::new(0.0, 1.0, 0.0),
];
let faces = vec![[0, 1, 2]];
let mesh = Mesh3::new(vertices, faces, false);
let plane = Plane3::new(Vector3::z_axis(), 0.0);
let candidates = candidate_faces(&mesh.shape, &plane, None);
assert!(candidates.is_empty());
}
#[test]
fn single_loop() -> Result<()> {
let mesh = Mesh3::create_box(2.0, 2.0, 2.0, false);
let section = mesh.section_with_plane(&Plane3::xy(), PlaneFrame::Auto, None, None)?;
assert_eq!(section.curves.len(), 1);
Ok(())
}
#[test]
fn a_plane_which_misses_the_mesh_is_an_error() {
let mesh = Mesh3::create_box(2.0, 2.0, 2.0, false);
let plane = Plane3::new(Vector3::z_axis(), 50.0);
let err = match mesh.section_with_plane(&plane, PlaneFrame::Auto, None, None) {
Err(e) => e.to_string(),
Ok(s) => panic!("a plane 50 units away cut {} curves", s.curves.len()),
};
assert!(
err.contains("does not intersect"),
"unexpected message: {err}"
);
}
#[test]
fn a_face_mask_which_selects_nothing_is_an_error() {
let mesh = Mesh3::create_box(2.0, 2.0, 2.0, false);
let mask = IndexMask::new(mesh.face_count(), false);
let err = match mesh.section_with_plane(&Plane3::xy(), PlaneFrame::Auto, None, Some(&mask))
{
Err(e) => e.to_string(),
Ok(s) => panic!("an empty face mask cut {} curves", s.curves.len()),
};
assert!(err.contains("selected faces"), "unexpected message: {err}");
}
#[test]
fn unit_cylinder_in_xy_plane_creates_one_circle_curve() {
let mesh = Mesh3::create_cylinder(1.0, 2.0, 1.0e-5).unwrap();
let plane = Plane3::xy();
let curves = mesh
.section_with_plane(&plane, PlaneFrame::Auto, Some(1.0e-10), None)
.unwrap()
.curves;
assert_eq!(curves.len(), 1);
let curve = &curves.curves()[0];
assert!(curve.count() >= 3);
for vertex in curve.vertices() {
assert_relative_eq!(vertex.z, 0.0, epsilon = 1.0e-12);
let radius = (vertex.x * vertex.x + vertex.y * vertex.y).sqrt();
assert_relative_eq!(radius, 1.0, epsilon = 1.0e-4);
}
assert_relative_eq!(curve.length(), TAU, epsilon = 1.0e-2);
}
#[test]
fn two_unit_cylinders_in_xy_plane_create_two_circle_curves() {
let mut mesh = Mesh3::create_cylinder(1.0, 2.0, 1.0e-5).unwrap();
mesh.transform_in_place(&Iso3::translation(-2.0, 0.0, 0.0));
let mut m1 = Mesh3::create_cylinder(1.0, 2.0, 1.0e-5).unwrap();
m1.transform_in_place(&Iso3::translation(2.0, 0.0, 0.0));
mesh.append_in_place(&m1).unwrap();
let plane = Plane3::xy();
let curves = mesh
.section_with_plane(&plane, PlaneFrame::Auto, Some(1.0e-10), None)
.unwrap()
.curves;
assert_eq!(curves.len(), 2);
for curve in curves.curves().iter() {
assert!(curve.count() >= 3);
assert_relative_eq!(curve.length(), TAU, epsilon = 1.0e-2);
let expected_center = if curve.vertices()[0].x > 0.0 {
Point3::new(2.0, 0.0, 0.0)
} else {
Point3::new(-2.0, 0.0, 0.0)
};
for vertex in curve.vertices() {
assert_relative_eq!(dist(&expected_center, vertex), 1.0, epsilon = 1.0e-4);
}
}
}
#[test]
fn a_mesh_section_projects_back_into_its_own_plane() {
let mesh = Mesh3::create_box(2.0, 4.0, 6.0, false);
let section = mesh
.section_with_plane(&Plane3::xy(), PlaneFrame::Auto, Some(1e-9), None)
.unwrap();
let flat = section.to_2d().unwrap();
assert_eq!(flat.len(), 1);
let loop_2d = &flat.curves()[0];
assert!(loop_2d.is_closed(), "a box sections into a closed loop");
assert_relative_eq!(loop_2d.length(), 12.0, epsilon = 1e-6);
let aabb = loop_2d.aabb();
assert_relative_eq!(aabb.mins.x, -1.0, epsilon = 1e-9);
assert_relative_eq!(aabb.maxs.x, 1.0, epsilon = 1e-9);
assert_relative_eq!(aabb.mins.y, -2.0, epsilon = 1e-9);
assert_relative_eq!(aabb.maxs.y, 2.0, epsilon = 1e-9);
}
#[test]
fn a_tilted_section_has_the_same_shape_as_an_upright_one() {
let mesh = Mesh3::create_box(2.0, 4.0, 6.0, false);
let upright = mesh
.section_with_plane(&Plane3::xy(), PlaneFrame::Auto, Some(1e-9), None)
.unwrap()
.to_2d()
.unwrap();
let iso = Iso3::new(Vector3::new(10.0, -5.0, 2.0), Vector3::new(0.3, -0.5, 0.2));
let moved = mesh.transform_copy(&iso);
let plane = Plane3::xy().transformed_by(&iso);
let tilted = moved
.section_with_plane(&plane, PlaneFrame::Auto, Some(1e-9), None)
.unwrap()
.to_2d()
.unwrap();
assert_eq!(tilted.len(), upright.len());
assert_relative_eq!(tilted.length(), upright.length(), epsilon = 1e-6);
}
#[test]
fn a_2d_result_lifts_back_onto_the_section() {
let mesh = Mesh3::create_box(2.0, 4.0, 6.0, false);
let iso = Iso3::new(Vector3::new(1.0, 2.0, 3.0), Vector3::new(0.3, -0.5, 0.2));
let moved = mesh.transform_copy(&iso);
let plane = Plane3::xy().transformed_by(&iso);
let section = moved
.section_with_plane(&plane, PlaneFrame::Auto, Some(1e-9), None)
.unwrap();
let flat = section.to_2d().unwrap();
let back = section.map.curve_group_to_3d(&flat).unwrap();
assert_relative_eq!(back.length(), section.curves.length(), epsilon = 1e-9);
let (_, station) = section
.curves
.at_closest_to_point(&back.curves()[0].vertices()[1]);
assert_relative_eq!(
dist(&station.point(), &back.curves()[0].vertices()[1]),
0.0,
epsilon = 1e-9
);
}
#[test]
fn an_svd_frame_centers_the_section_on_its_long_axis() {
let mesh = Mesh3::create_box(4.0, 2.0, 6.0, false);
let iso = Iso3::new(Vector3::new(10.0, -5.0, 2.0), Vector3::new(0.3, -0.5, 0.2));
let moved = mesh.transform_copy(&iso);
let plane = Plane3::xy().transformed_by(&iso);
let flat = moved
.section_with_plane(&plane, PlaneFrame::Svd, Some(1e-9), None)
.unwrap()
.to_2d()
.unwrap();
let aabb = flat.curves()[0].aabb();
assert_relative_eq!(aabb.center(), crate::Point2::origin(), epsilon = 1e-9);
assert_relative_eq!(aabb.maxs.x - aabb.mins.x, 4.0, epsilon = 1e-9);
assert_relative_eq!(aabb.maxs.y - aabb.mins.y, 2.0, epsilon = 1e-9);
}
#[test]
fn an_oriented_frame_places_the_origin_and_x_axis() {
let mesh = Mesh3::create_box(2.0, 4.0, 6.0, false);
let frame = PlaneFrame::Oriented {
origin: Point3::new(-1.0, -2.0, 5.0),
x: Vector3::new(0.0, 1.0, 0.5),
};
let flat = mesh
.section_with_plane(&Plane3::xy(), frame, Some(1e-9), None)
.unwrap()
.to_2d()
.unwrap();
let aabb = flat.curves()[0].aabb();
assert_relative_eq!(aabb.mins.x, 0.0, epsilon = 1e-9);
assert_relative_eq!(aabb.maxs.x, 4.0, epsilon = 1e-9);
assert_relative_eq!(aabb.mins.y, -2.0, epsilon = 1e-9);
assert_relative_eq!(aabb.maxs.y, 0.0, epsilon = 1e-9);
}
#[test]
fn a_frame_which_cannot_be_built_is_an_error() {
let mesh = Mesh3::create_box(2.0, 4.0, 6.0, false);
let frame = PlaneFrame::Oriented {
origin: Point3::origin(),
x: Vector3::z(),
};
assert!(
mesh.section_with_plane(&Plane3::xy(), frame, None, None)
.is_err()
);
}
}