#![allow(clippy::many_single_char_names)]
use super::*;
use crate::filters::NormalFilters;
use crate::Point2;
use rustc_hash::FxHashMap as HashMap;
use truck_base::entry_map::FxEntryMap as EntryMap;
use truck_topology::Vertex as TVertex;
#[cfg(not(target_arch = "wasm32"))]
use rayon::prelude::*;
type SPoint2 = spade::Point2<f64>;
type Cdt = ConstrainedDelaunayTriangulation<SPoint2>;
type MeshedShell = Shell<Point3, PolylineCurve, Option<PolygonMesh>>;
type MeshedCShell = CompressedShell<Point3, PolylineCurve, Option<PolygonMesh>>;
#[cfg(not(target_arch = "wasm32"))]
pub(super) fn shell_tessellation<'a, C, S>(shell: &Shell<Point3, C, S>, tol: f64) -> MeshedShell
where
C: PolylineableCurve + 'a,
S: MeshableSurface + 'a, {
let vmap: HashMap<_, _> = shell
.vertex_par_iter()
.map(|v| (v.id(), v.mapped(Point3::clone)))
.collect();
let eset: HashMap<_, _> = shell.edge_par_iter().map(move |e| (e.id(), e)).collect();
let edge_map: HashMap<_, _> = eset
.into_par_iter()
.map(move |(id, edge)| {
let v0 = vmap.get(&edge.absolute_front().id()).unwrap();
let v1 = vmap.get(&edge.absolute_back().id()).unwrap();
let curve = edge.get_curve();
let poly = PolylineCurve::from_curve(&curve, curve.parameter_range(), tol);
(id, Edge::debug_new(v0, v1, poly))
})
.collect();
let create_edge = |edge: &Edge<Point3, C>| -> Edge<_, _> {
let new_edge = edge_map.get(&edge.id()).unwrap();
match edge.orientation() {
true => new_edge.clone(),
false => new_edge.inverse(),
}
};
let create_boundary =
|wire: &Wire<Point3, C>| -> Wire<_, _> { wire.edge_iter().map(create_edge).collect() };
shell
.face_par_iter()
.map(move |face| {
let wires: Vec<_> = face
.absolute_boundaries()
.iter()
.map(create_boundary)
.collect();
let surface = face.get_surface();
let mut polyline = Polyline::default();
let polygon = match wires.iter().all(|wire: &Wire<_, _>| {
polyline.add_wire(&surface, wire.iter().map(Edge::oriented_curve))
}) {
true => Some(trimming_tessellation(&surface, &polyline, tol)),
false => None,
};
let mut new_face = Face::debug_new(wires, polygon);
if !face.orientation() {
new_face.invert();
}
new_face
})
.collect()
}
#[allow(dead_code)]
pub(super) fn shell_tessellation_single_thread<'a, C, S>(
shell: &Shell<Point3, C, S>,
tol: f64,
) -> MeshedShell
where
C: PolylineableCurve + 'a,
S: MeshableSurface + 'a,
{
let mut vmap = EntryMap::new(
move |v: &TVertex<Point3>| v.id(),
move |v| v.mapped(Point3::clone),
);
let mut edge_map = EntryMap::new(
move |edge: &Edge<Point3, C>| edge.id(),
move |edge| {
let vf = edge.absolute_front();
let v0 = vmap.entry_or_insert(vf).clone();
let vb = edge.absolute_back();
let v1 = vmap.entry_or_insert(vb).clone();
let curve = edge.get_curve();
let poly = PolylineCurve::from_curve(&curve, curve.parameter_range(), tol);
Edge::debug_new(&v0, &v1, poly)
},
);
shell
.face_iter()
.map(|face| {
let wires: Vec<_> = face
.absolute_boundaries()
.iter()
.map(|wire| {
wire.edge_iter()
.map(|edge| {
let new_edge = edge_map.entry_or_insert(edge);
match edge.orientation() {
true => new_edge.clone(),
false => new_edge.inverse(),
}
})
.collect()
})
.collect();
let surface = face.get_surface();
let mut polyline = Polyline::default();
let polygon = match wires.iter().all(|wire: &Wire<_, _>| {
polyline.add_wire(&surface, wire.iter().map(|edge| edge.oriented_curve()))
}) {
true => Some(trimming_tessellation(&surface, &polyline, tol)),
false => None,
};
let mut new_face = Face::debug_new(wires, polygon);
if !face.orientation() {
new_face.invert();
}
new_face
})
.collect()
}
pub(super) fn cshell_tessellation<'a, C, S>(
shell: &CompressedShell<Point3, C, S>,
tol: f64,
) -> MeshedCShell
where
C: PolylineableCurve + 'a,
S: MeshableSurface + 'a,
{
let vertices = shell.vertices.clone();
let tessellate_edge = |edge: &CompressedEdge<C>| {
let curve = &edge.curve;
CompressedEdge {
vertices: edge.vertices,
curve: PolylineCurve::from_curve(curve, curve.parameter_range(), tol),
}
};
#[cfg(not(target_arch = "wasm32"))]
let edges: Vec<_> = shell.edges.par_iter().map(tessellate_edge).collect();
#[cfg(target_arch = "wasm32")]
let edges: Vec<_> = shell.edges.iter().map(tessellate_edge).collect();
let tessellate_face = |face: &CompressedFace<S>| {
let boundaries = face.boundaries.clone();
let surface = &face.surface;
let mut polyline = Polyline::default();
let polygon = match boundaries.iter().all(|wire| {
let wire_iter = wire
.iter()
.filter_map(|edge_idx| match edge_idx.orientation {
true => Some(edges.get(edge_idx.index)?.curve.clone()),
false => Some(edges.get(edge_idx.index)?.curve.inverse()),
});
polyline.add_wire(surface, wire_iter)
}) {
true => Some(trimming_tessellation(surface, &polyline, tol)),
false => None,
};
CompressedFace {
boundaries,
orientation: face.orientation,
surface: polygon,
}
};
#[cfg(not(target_arch = "wasm32"))]
let faces = shell.faces.par_iter().map(tessellate_face).collect();
#[cfg(target_arch = "wasm32")]
let faces = shell.faces.iter().map(tessellate_face).collect();
MeshedCShell {
vertices,
edges,
faces,
}
}
#[derive(Debug, Default, Clone)]
struct Polyline {
positions: Vec<Point2>,
indices: Vec<[usize; 2]>,
}
impl Polyline {
fn add_wire<S>(&mut self, surface: &S, mut wire: impl Iterator<Item = PolylineCurve>) -> bool
where S: MeshableSurface {
let mut counter = 0;
let len = self.positions.len();
let res = wire.all(|mut poly_edge| {
poly_edge.pop();
counter += poly_edge.len();
let mut hint = None;
Vec::from(poly_edge).into_iter().all(|pt| {
hint = surface
.search_parameter(pt, hint, 100)
.or_else(|| surface.search_parameter(pt, None, 100));
hint.map(|hint| self.positions.push(hint.into())).is_some()
})
});
self.indices
.extend((0..counter).map(|i| [len + i, len + (i + 1) % counter]));
res
}
fn include(&self, c: Point2) -> bool {
let t = 2.0 * std::f64::consts::PI * HashGen::hash1(c);
let r = Vector2::new(f64::cos(t), f64::sin(t));
self.indices
.iter()
.try_fold(0_i32, move |counter, edge| {
let a = self.positions[edge[0]] - c;
let b = self.positions[edge[1]] - c;
let s0 = r[0] * a[1] - r[1] * a[0]; let s1 = r[0] * b[1] - r[1] * b[0]; let s2 = a[0] * b[1] - a[1] * b[0]; let x = s2 / (s1 - s0);
if x.so_small() && s0 * s1 < 0.0 {
None
} else if x > 0.0 && s0 <= 0.0 && s1 > 0.0 {
Some(counter + 1)
} else if x > 0.0 && s0 >= 0.0 && s1 < 0.0 {
Some(counter - 1)
} else {
Some(counter)
}
})
.map(|counter| counter > 0)
.unwrap_or(false)
}
fn insert_to(&self, triangulation: &mut Cdt) {
let poly2tri: Vec<_> = self
.positions
.iter()
.filter_map(|pt| triangulation.insert(SPoint2::from([pt.x, pt.y])).ok())
.collect();
let mut prev: Option<usize> = None;
self.indices.iter().for_each(|a| {
if let Some(p) = prev {
if triangulation.can_add_constraint(poly2tri[p], poly2tri[a[1]]) {
triangulation.add_constraint(poly2tri[p], poly2tri[a[1]]);
prev = None;
}
} else if triangulation.can_add_constraint(poly2tri[a[0]], poly2tri[a[1]]) {
triangulation.add_constraint(poly2tri[a[0]], poly2tri[a[1]]);
} else {
prev = Some(a[0]);
}
});
}
}
fn trimming_tessellation<S>(surface: &S, polyline: &Polyline, tol: f64) -> PolygonMesh
where S: MeshableSurface {
let mut triangulation = Cdt::new();
polyline.insert_to(&mut triangulation);
insert_surface(&mut triangulation, surface, polyline, tol);
let mut mesh = triangulation_into_polymesh(
triangulation.vertices(),
triangulation.inner_faces(),
surface,
polyline,
);
mesh.make_face_compatible_to_normal();
mesh
}
fn insert_surface(
triangulation: &mut Cdt,
surface: &impl MeshableSurface,
polyline: &Polyline,
tol: f64,
) {
let bdb: BoundingBox<Point2> = polyline.positions.iter().collect();
let range = ((bdb.min()[0], bdb.max()[0]), (bdb.min()[1], bdb.max()[1]));
let (udiv, vdiv) = surface.parameter_division(range, tol);
udiv.into_iter()
.flat_map(|u| vdiv.iter().map(move |v| Point2::new(u, *v)))
.filter(|pt| polyline.include(*pt))
.for_each(|pt| {
let _ = triangulation.insert(SPoint2::from([pt.x, pt.y]));
});
}
fn triangulation_into_polymesh<'a>(
vertices: VertexIterator<'a, SPoint2, (), CdtEdge<()>, ()>,
triangles: InnerFaceIterator<'a, SPoint2, (), CdtEdge<()>, ()>,
surface: &impl ParametricSurface3D,
polyline: &Polyline,
) -> PolygonMesh {
let mut positions = Vec::<Point3>::new();
let mut uv_coords = Vec::<Vector2>::new();
let mut normals = Vec::<Vector3>::new();
let vmap: HashMap<_, _> = vertices
.enumerate()
.map(|(i, v)| {
let p = *v.as_ref();
let uv = Vector2::new(p.x, p.y);
positions.push(surface.subs(uv[0], uv[1]));
uv_coords.push(uv);
normals.push(surface.normal(uv[0], uv[1]));
(v.fix(), i)
})
.collect();
let tri_faces: Vec<[StandardVertex; 3]> = triangles
.map(|tri| tri.vertices())
.filter(|tri| {
let tri = [*tri[0].as_ref(), *tri[1].as_ref(), *tri[2].as_ref()];
let c = Point2::new(
(tri[0].x + tri[1].x + tri[2].x) / 3.0,
(tri[0].y + tri[1].y + tri[2].y) / 3.0,
);
polyline.include(c)
})
.map(|tri| {
let idcs = [
vmap[&tri[0].fix()],
vmap[&tri[1].fix()],
vmap[&tri[2].fix()],
];
[
[idcs[0], idcs[0], idcs[0]].into(),
[idcs[1], idcs[1], idcs[1]].into(),
[idcs[2], idcs[2], idcs[2]].into(),
]
})
.collect();
PolygonMesh::debug_new(
StandardAttributes {
positions,
uv_coords,
normals,
},
Faces::from_tri_and_quad_faces(tri_faces, Vec::new()),
)
}
#[test]
#[ignore]
#[cfg(not(target_arch = "wasm32"))]
fn par_bench() {
use std::time::Instant;
use truck_modeling::*;
const JSON: &str = include_str!(concat!(
env!("CARGO_MANIFEST_DIR"),
"/../resources/shape/bottle.json"
));
let solid: Solid = serde_json::from_str(JSON).unwrap();
let shell = solid.into_boundaries().pop().unwrap();
let instant = Instant::now();
(0..100).for_each(|_| {
let _shell = shell_tessellation(&shell, 0.01);
});
println!("{}ms", instant.elapsed().as_millis());
let instant = Instant::now();
(0..100).for_each(|_| {
let _shell = shell_tessellation_single_thread(&shell, 0.01);
});
println!("{}ms", instant.elapsed().as_millis());
}