use super::{Mesh3, MeshData3, MeshSurfPoint};
use crate::common::IndexMask;
use crate::common::barycentric::{barycentric_grid, barycentric_point};
use crate::common::points::dist;
use crate::common::poisson_disk::sample_poisson_disk_all;
use crate::geom3::point_cloud::PointCloud3;
use crate::{Point3, Result, SurfacePoint3};
use parry3d_f64::shape::Triangle;
impl MeshData3 {
pub fn sample_surface_dense(
&self,
max_spacing: f64,
face_mask: Option<&IndexMask>,
) -> Result<Vec<MeshSurfPoint>> {
compute_dense_surface_points(self.points(), self.faces(), max_spacing, face_mask)
}
pub fn sample_surface_poisson(
&self,
radius: f64,
face_mask: Option<&IndexMask>,
) -> Result<Vec<MeshSurfPoint>> {
compute_poisson_surface_points(self.points(), self.faces(), radius, face_mask)
}
pub fn sample_dense(
&self,
max_spacing: f64,
face_mask: Option<&IndexMask>,
) -> Result<PointCloud3> {
Ok(to_cloud(
&self.sample_surface_dense(max_spacing, face_mask)?,
))
}
pub fn sample_poisson(
&self,
radius: f64,
face_mask: Option<&IndexMask>,
) -> Result<PointCloud3> {
Ok(to_cloud(&self.sample_surface_poisson(radius, face_mask)?))
}
pub fn sample_uniform(&self, n: usize) -> PointCloud3 {
to_cloud(&compute_uniform_surface_points(
self.points(),
self.faces(),
n,
))
}
}
impl Mesh3 {
pub fn sample_surface_dense(
&self,
max_spacing: f64,
face_mask: Option<&IndexMask>,
) -> Result<Vec<MeshSurfPoint>> {
compute_dense_surface_points(self.points(), self.faces(), max_spacing, face_mask)
}
pub fn sample_surface_poisson(
&self,
radius: f64,
face_mask: Option<&IndexMask>,
) -> Result<Vec<MeshSurfPoint>> {
compute_poisson_surface_points(self.points(), self.faces(), radius, face_mask)
}
pub fn sample_dense(
&self,
max_spacing: f64,
face_mask: Option<&IndexMask>,
) -> Result<PointCloud3> {
Ok(to_cloud(
&self.sample_surface_dense(max_spacing, face_mask)?,
))
}
pub fn sample_poisson(
&self,
radius: f64,
face_mask: Option<&IndexMask>,
) -> Result<PointCloud3> {
Ok(to_cloud(&self.sample_surface_poisson(radius, face_mask)?))
}
pub fn sample_uniform(&self, n: usize) -> PointCloud3 {
to_cloud(&compute_uniform_surface_points(
self.points(),
self.faces(),
n,
))
}
}
pub fn compute_dense_surface_points(
points: &[Point3],
faces: &[[u32; 3]],
max_spacing: f64,
face_mask: Option<&IndexMask>,
) -> Result<Vec<MeshSurfPoint>> {
validate(faces, max_spacing, "Maximum spacing", face_mask)?;
let mut sampled = Vec::with_capacity(faces.len());
for (face_i, vert) in faces.iter().enumerate() {
if let Some(face_mask) = face_mask
&& !face_mask.get(face_i)
{
continue;
}
let tri = triangle(points, vert);
let Some(normal) = tri.normal() else {
continue;
};
let face_index = face_i as u32;
let mut push = |bc: [f64; 3]| {
let at = barycentric_point(&tri.a, &tri.b, &tri.c, bc);
let sp = SurfacePoint3::new(at, normal);
sampled.push(MeshSurfPoint { face_index, bc, sp });
};
if dist(&tri.a, &tri.b) < max_spacing
&& dist(&tri.a, &tri.c) < max_spacing
&& dist(&tri.b, &tri.c) < max_spacing
{
push([1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0]);
} else {
for bc in barycentric_grid(&tri.a, &tri.b, &tri.c, max_spacing) {
push(bc);
}
}
}
Ok(sampled)
}
pub fn compute_poisson_surface_points(
points: &[Point3],
faces: &[[u32; 3]],
radius: f64,
face_mask: Option<&IndexMask>,
) -> Result<Vec<MeshSurfPoint>> {
validate(faces, radius, "Radius", face_mask)?;
let starting = compute_dense_surface_points(points, faces, radius * 0.5, face_mask)?;
let mask = sample_poisson_disk_all(&starting, radius);
Ok(mask.iter_true().map(|i| starting[i]).collect())
}
pub fn compute_uniform_surface_points(
points: &[Point3],
faces: &[[u32; 3]],
n: usize,
) -> Vec<MeshSurfPoint> {
let mut candidates = Vec::with_capacity(faces.len());
let mut total_area = 0.0;
for (face_i, vert) in faces.iter().enumerate() {
let tri = triangle(points, vert);
let area = tri.area();
if let Some(normal) = tri.normal()
&& area > 0.0
{
total_area += area;
candidates.push((face_i as u32, total_area, tri, normal));
}
}
if candidates.is_empty() {
return Vec::new();
}
let mut result = Vec::with_capacity(n);
for _ in 0..n {
let r = rand::random::<f64>() * total_area;
let i = candidates
.partition_point(|(_, cumulative, _, _)| *cumulative <= r)
.min(candidates.len() - 1);
let (face_index, _, tri, normal) = &candidates[i];
let r1 = rand::random::<f64>();
let r2 = rand::random::<f64>();
let s = r1.sqrt();
let bc = [1.0 - s, s * (1.0 - r2), s * r2];
let at = barycentric_point(&tri.a, &tri.b, &tri.c, bc);
result.push(MeshSurfPoint {
face_index: *face_index,
bc,
sp: SurfacePoint3::new(at, *normal),
});
}
result
}
fn validate(
faces: &[[u32; 3]],
spacing: f64,
label: &str,
face_mask: Option<&IndexMask>,
) -> Result<()> {
if !spacing.is_finite() || spacing <= 0.0 {
return Err(format!("{label} must be finite and positive, got {spacing}").into());
}
if let Some(mask) = face_mask
&& mask.len() != faces.len()
{
return Err(format!(
"A face mask of length {} does not match a mesh with {} faces",
mask.len(),
faces.len()
)
.into());
}
Ok(())
}
fn triangle(points: &[Point3], vert: &[u32; 3]) -> Triangle {
Triangle::new(
points[vert[0] as usize],
points[vert[1] as usize],
points[vert[2] as usize],
)
}
fn to_cloud(samples: &[MeshSurfPoint]) -> PointCloud3 {
let sps: Vec<SurfacePoint3> = samples.iter().map(|m| m.sp).collect();
PointCloud3::from_surface_points(&sps)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::KdTree3;
use crate::common::kd_tree::*;
#[test]
fn check_kiddo_bug() {
let mesh = Mesh3::create_sphere(100.0, 0.011).unwrap();
let r = 5.0;
let sampled = mesh.sample_poisson(r, None).unwrap();
let tree = KdTree3::try_new(sampled.points()).expect("Tree construction failed");
for p in sampled.points() {
let neighbors = tree.within(p, r);
assert_eq!(neighbors.len(), 1, "Missed duplicate");
}
}
#[test]
fn a_nonsense_spacing_is_rejected() {
let mesh = Mesh3::create_box(1.0, 1.0, 1.0, true);
for bad in [0.0, -1.0, f64::NAN, f64::INFINITY] {
assert!(mesh.sample_dense(bad, None).is_err(), "{bad} was accepted");
assert!(
mesh.sample_poisson(bad, None).is_err(),
"{bad} was accepted"
);
}
}
#[test]
fn a_mask_of_the_wrong_length_is_rejected() {
let mesh = Mesh3::create_box(1.0, 1.0, 1.0, true);
for len in [mesh.faces().len() - 1, mesh.faces().len() + 1] {
let wrong = IndexMask::new(len, true);
assert!(mesh.sample_dense(0.25, Some(&wrong)).is_err());
assert!(mesh.sample_poisson(0.25, Some(&wrong)).is_err());
}
}
#[test]
fn sample_poisson_index_mask_restricts_to_masked_faces() {
let mesh = Mesh3::create_sphere(100.0, 1.1).unwrap();
let n_faces = mesh.faces().len();
let masked_indices: Vec<usize> = (0..n_faces / 2).collect();
let mask = IndexMask::try_from_indices(&masked_indices, n_faces).unwrap();
let sampled = mesh.sample_surface_poisson(5.0, Some(&mask)).unwrap();
assert!(!sampled.is_empty(), "Expected at least one sample");
for mp in &sampled {
assert!(
mask.get(mp.face_index as usize),
"face_index {} is not in the mask",
mp.face_index
);
}
}
#[test]
fn both_containers_sample_identically() {
let data = MeshData3::create_sphere(20.0, 0.5).unwrap();
let mesh = Mesh3::from_data(data.clone(), false).unwrap();
let from_data = data.sample_surface_dense(2.0, None).unwrap();
let from_mesh = mesh.sample_surface_dense(2.0, None).unwrap();
assert_eq!(from_data.len(), from_mesh.len());
for (a, b) in from_data.iter().zip(&from_mesh) {
assert_eq!(a.face_index, b.face_index);
assert_eq!(a.bc, b.bc);
assert_eq!(a.sp.point, b.sp.point);
assert_eq!(a.sp.normal, b.sp.normal);
}
let from_data = data.sample_poisson(3.0, None).unwrap();
let from_mesh = mesh.sample_poisson(3.0, None).unwrap();
assert_eq!(from_data.points(), from_mesh.points());
assert_eq!(from_data.point_normals(), from_mesh.point_normals());
}
#[test]
fn the_cloud_tier_carries_the_surface_tier_positions_and_normals() {
let mesh = Mesh3::create_box(10.0, 6.0, 4.0, false);
let surface = mesh.sample_surface_dense(1.0, None).unwrap();
let cloud = mesh.sample_dense(1.0, None).unwrap();
assert_eq!(cloud.point_count(), surface.len());
let normals = cloud.point_normals().expect("the sample carries normals");
for (i, mp) in surface.iter().enumerate() {
assert_eq!(cloud.points()[i], mp.sp.point);
assert_eq!(normals[i], mp.sp.normal);
}
assert!(cloud.point_colors().is_none());
assert!(cloud.point_stdev().is_none());
}
#[test]
fn dense_sampling_skips_degenerate_faces() {
let points = vec![
Point3::new(0.0, 0.0, 0.0),
Point3::new(1.0, 0.0, 0.0),
Point3::new(1.0, 1.0, 0.0),
Point3::new(2.0, 0.0, 0.0),
];
let faces = vec![[0, 1, 2], [0, 1, 3]];
let sampled = compute_dense_surface_points(&points, &faces, 0.25, None).unwrap();
assert!(!sampled.is_empty());
assert!(sampled.iter().all(|mp| mp.face_index == 0));
let sampled = compute_uniform_surface_points(&points, &faces, 50);
assert_eq!(sampled.len(), 50);
assert!(sampled.iter().all(|mp| mp.face_index == 0));
let only_degenerate = compute_uniform_surface_points(&points, &faces[1..], 10);
assert!(only_degenerate.is_empty());
}
#[test]
fn uniform_samples_lie_on_the_surface_with_the_face_normal() {
let mesh = Mesh3::create_box(10.0, 6.0, 4.0, false);
let cloud = mesh.sample_uniform(500);
assert_eq!(cloud.point_count(), 500);
let normals = cloud.point_normals().unwrap();
for (p, n) in cloud.points().iter().zip(normals) {
let closest = mesh.surface_closest_to(p);
assert!(dist(p, &closest.sp.point) < 1e-9);
assert!((closest.sp.normal.dot(n) - 1.0).abs() < 1e-9);
}
}
}