use crate::geom3::mesh::algorithms::normals::compute_face_normal;
use crate::na::Matrix3;
use crate::{Point3, Result, UnitVec3, Vector3};
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct OffsetOpts {
pub rank_tolerance: f64,
pub max_ratio: f64,
}
impl Default for OffsetOpts {
fn default() -> Self {
Self {
rank_tolerance: 1.0e-6,
max_ratio: 10.0,
}
}
}
pub fn compute_face_offset_points(
points: &[Point3],
faces: &[[u32; 3]],
distance: f64,
opts: &OffsetOpts,
) -> Result<Vec<Point3>> {
if !distance.is_finite() {
return Err(format!("The offset distance must be finite, but it was {distance}").into());
}
if !(opts.rank_tolerance > 0.0 && opts.rank_tolerance < 1.0) {
return Err("The rank tolerance must lie strictly between 0 and 1".into());
}
if !(opts.max_ratio >= 1.0 && opts.max_ratio.is_finite()) {
return Err("The maximum displacement ratio must be finite and at least 1".into());
}
let quadrics = accumulate_quadrics(points, faces)?;
let limit = opts.max_ratio * distance.abs();
let mut out = Vec::with_capacity(points.len());
for (i, q) in quadrics.iter().enumerate() {
if !q.has_faces {
return Err(format!(
"Point {i} cannot be offset. It belongs to no face or only to degenerate faces, so \
there are no surfaces to offset it away from."
)
.into());
}
let mut u = solve_min_norm(&q.a, &(q.b * distance), opts.rank_tolerance);
let norm = u.norm();
if norm > limit && norm > 0.0 {
u *= limit / norm;
}
out.push(points[i] + u);
}
Ok(out)
}
pub fn compute_normal_displaced_points(
points: &[Point3],
normals: &[UnitVec3],
distance: f64,
) -> Result<Vec<Point3>> {
if points.len() != normals.len() {
return Err(format!(
"There are {} points but {} normals, and displacement needs one normal per point",
points.len(),
normals.len()
)
.into());
}
if !distance.is_finite() {
return Err(format!("The offset distance must be finite, but it was {distance}").into());
}
Ok(points
.iter()
.zip(normals.iter())
.map(|(p, n)| *p + n.into_inner() * distance)
.collect())
}
struct Quadric {
a: Matrix3<f64>,
b: Vector3,
has_faces: bool,
}
fn accumulate_quadrics(points: &[Point3], faces: &[[u32; 3]]) -> Result<Vec<Quadric>> {
let mut out = (0..points.len())
.map(|_| Quadric {
a: Matrix3::zeros(),
b: Vector3::zeros(),
has_faces: false,
})
.collect::<Vec<_>>();
for face in faces.iter() {
let p = [
*points
.get(face[0] as usize)
.ok_or("Face refers to a point which does not exist")?,
*points
.get(face[1] as usize)
.ok_or("Face refers to a point which does not exist")?,
*points
.get(face[2] as usize)
.ok_or("Face refers to a point which does not exist")?,
];
let Some(normal) = compute_face_normal(&p) else {
continue;
};
let n = normal.into_inner();
let outer = n * n.transpose();
for k in 0..3 {
let e1 = p[(k + 1) % 3] - p[k];
let e2 = p[(k + 2) % 3] - p[k];
let w = e1.cross(&e2).norm().atan2(e1.dot(&e2));
let q = &mut out[face[k] as usize];
q.a += outer * w;
q.b += n * w;
q.has_faces = true;
}
}
Ok(out)
}
fn solve_min_norm(a: &Matrix3<f64>, c: &Vector3, tol: f64) -> Vector3 {
let svd = a.svd(true, true);
let (Some(u), Some(v_t)) = (svd.u, svd.v_t) else {
return Vector3::zeros();
};
let largest = svd
.singular_values
.iter()
.fold(0.0_f64, |acc, s| acc.max(*s));
if largest <= 0.0 {
return Vector3::zeros();
}
let cutoff = largest * tol;
let mut result = Vector3::zeros();
for i in 0..3 {
let s = svd.singular_values[i];
if s <= cutoff {
continue;
}
let projection = u.column(i).dot(c) / s;
result += v_t.row(i).transpose() * projection;
}
result
}
#[cfg(test)]
mod tests {
use super::*;
use crate::geom3::mesh::algorithms::normals::compute_point_normals;
use approx::assert_relative_eq;
fn cube() -> (Vec<Point3>, Vec<[u32; 3]>) {
let mut points = Vec::new();
for x in [-1.0, 1.0] {
for y in [-1.0, 1.0] {
for z in [-1.0, 1.0] {
points.push(Point3::new(x, y, z));
}
}
}
let quads = [
[1, 5, 7, 3], [0, 2, 6, 4], [0, 4, 5, 1], [2, 3, 7, 6], [4, 6, 7, 5], [0, 1, 3, 2], ];
let mut faces = Vec::new();
for q in quads {
faces.push([q[0], q[1], q[2]]);
faces.push([q[0], q[2], q[3]]);
}
(points, faces)
}
fn flat_grid(n: u32) -> (Vec<Point3>, Vec<[u32; 3]>) {
let mut points = Vec::new();
for j in 0..n {
for i in 0..n {
points.push(Point3::new(i as f64, j as f64, 0.0));
}
}
let mut faces = Vec::new();
for j in 0..n - 1 {
for i in 0..n - 1 {
let a = j * n + i;
faces.push([a, a + 1, a + n + 1]);
faces.push([a, a + n + 1, a + n]);
}
}
(points, faces)
}
fn worst_plane_error(
points: &[Point3],
faces: &[[u32; 3]],
moved: &[Point3],
distance: f64,
) -> f64 {
let mut worst: f64 = 0.0;
for face in faces {
let p = face.map(|i| points[i as usize]);
let Some(n) = compute_face_normal(&p) else {
continue;
};
for i in face {
let u = moved[*i as usize] - points[*i as usize];
worst = worst.max((n.dot(&u) - distance).abs());
}
}
worst
}
#[test]
fn a_cube_corner_reaches_the_true_plane_intersection() -> Result<()> {
let (points, faces) = cube();
let d = 0.25;
let moved = compute_face_offset_points(&points, &faces, d, &OffsetOpts::default())?;
for (before, after) in points.iter().zip(moved.iter()) {
let expected = before + before.coords.map(|c| c.signum()) * d;
assert_relative_eq!(after.coords, expected.coords, epsilon = 1.0e-12);
}
for (before, after) in points.iter().zip(moved.iter()) {
assert_relative_eq!(
(after - before).norm(),
d * 3.0_f64.sqrt(),
epsilon = 1.0e-12
);
}
assert_relative_eq!(
worst_plane_error(&points, &faces, &moved, d),
0.0,
epsilon = 1.0e-12
);
Ok(())
}
#[test]
fn displacing_along_point_normals_under_offsets_a_corner() -> Result<()> {
let (points, faces) = cube();
let d = 0.25;
let normals = compute_point_normals(&points, &faces)?;
let naive = compute_normal_displaced_points(&points, &normals, d)?;
let shortfall = d - d / 3.0_f64.sqrt();
assert_relative_eq!(
worst_plane_error(&points, &faces, &naive, d),
shortfall,
epsilon = 1.0e-12
);
assert!(shortfall / d > 0.42);
Ok(())
}
#[test]
fn a_flat_sheet_offsets_along_its_normal() -> Result<()> {
let (points, faces) = flat_grid(4);
let d = 2.5;
let moved = compute_face_offset_points(&points, &faces, d, &OffsetOpts::default())?;
for (before, after) in points.iter().zip(moved.iter()) {
assert_relative_eq!(
after.coords,
before.coords + Vector3::z() * d,
epsilon = 1.0e-12
);
}
Ok(())
}
#[test]
fn a_valley_floor_offsets_along_the_bisector() -> Result<()> {
let points = vec![
Point3::new(-1.0, 0.0, 1.0),
Point3::new(-1.0, 1.0, 1.0),
Point3::new(0.0, 0.0, 0.0), Point3::new(0.0, 1.0, 0.0), Point3::new(1.0, 0.0, 1.0),
Point3::new(1.0, 1.0, 1.0),
];
let faces = vec![[0, 2, 3], [0, 3, 1], [2, 4, 5], [2, 5, 3]];
let d = 0.5;
let moved = compute_face_offset_points(&points, &faces, d, &OffsetOpts::default())?;
for i in [2, 3] {
let u = moved[i] - points[i];
assert_relative_eq!(u.x, 0.0, epsilon = 1.0e-12);
assert_relative_eq!(u.y, 0.0, epsilon = 1.0e-12);
assert_relative_eq!(u.z, d * 2.0_f64.sqrt(), epsilon = 1.0e-12);
}
assert_relative_eq!(
worst_plane_error(&points, &faces, &moved, d),
0.0,
epsilon = 1.0e-12
);
Ok(())
}
#[test]
fn a_regular_pyramid_apex_solves_exactly() -> Result<()> {
let points = vec![
Point3::new(0.0, 0.0, 1.0), Point3::new(-1.0, -1.0, 0.0),
Point3::new(1.0, -1.0, 0.0),
Point3::new(1.0, 1.0, 0.0),
Point3::new(-1.0, 1.0, 0.0),
];
let faces = vec![[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 1]];
let d = 0.3;
let moved = compute_face_offset_points(&points, &faces, d, &OffsetOpts::default())?;
let mut worst: f64 = 0.0;
for face in faces.iter() {
let p = face.map(|i| points[i as usize]);
let n = compute_face_normal(&p).unwrap();
let u = moved[0] - points[0];
worst = worst.max((n.dot(&u) - d).abs());
}
assert_relative_eq!(worst, 0.0, epsilon = 1.0e-12);
let u = moved[0] - points[0];
assert_relative_eq!(u.x, 0.0, epsilon = 1.0e-12);
assert_relative_eq!(u.y, 0.0, epsilon = 1.0e-12);
assert!(u.z > d, "the apex should travel farther than the distance");
Ok(())
}
#[test]
fn a_sphere_grows_by_the_offset_distance() -> Result<()> {
let sphere = crate::Mesh3::create_sphere(10.0, 0.024)?;
let d = 1.5;
let moved =
compute_face_offset_points(sphere.points(), sphere.faces(), d, &OffsetOpts::default())?;
let mut worst: f64 = 0.0;
for p in moved.iter() {
worst = worst.max((p.coords.norm() - 11.5).abs());
}
assert!(worst < 0.02, "worst radius error was {worst}");
Ok(())
}
#[test]
fn a_negative_distance_offsets_the_other_way() -> Result<()> {
let (points, faces) = cube();
let d = -0.25;
let moved = compute_face_offset_points(&points, &faces, d, &OffsetOpts::default())?;
for after in moved.iter() {
assert_relative_eq!(after.coords.abs().max(), 0.75, epsilon = 1.0e-12);
}
assert_relative_eq!(
worst_plane_error(&points, &faces, &moved, d),
0.0,
epsilon = 1.0e-12
);
Ok(())
}
#[test]
fn a_zero_distance_leaves_every_point_alone() -> Result<()> {
let (points, faces) = cube();
let moved = compute_face_offset_points(&points, &faces, 0.0, &OffsetOpts::default())?;
for (before, after) in points.iter().zip(moved.iter()) {
assert_relative_eq!(after.coords, before.coords, epsilon = 1.0e-15);
}
Ok(())
}
#[test]
fn scale_does_not_change_the_result() -> Result<()> {
let (big, faces) = cube();
let small: Vec<Point3> = big.iter().map(|p| *p * 1.0e-6).collect();
let a = compute_face_offset_points(&big, &faces, 0.25, &OffsetOpts::default())?;
let b = compute_face_offset_points(&small, &faces, 0.25e-6, &OffsetOpts::default())?;
for (x, y) in a.iter().zip(b.iter()) {
assert_relative_eq!(x.coords * 1.0e-6, y.coords, epsilon = 1.0e-15);
}
Ok(())
}
#[test]
fn a_point_with_no_faces_is_an_error() {
let points = 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),
Point3::new(5.0, 5.0, 5.0), ];
let faces = vec![[0, 1, 2]];
let err = compute_face_offset_points(&points, &faces, 1.0, &OffsetOpts::default())
.unwrap_err()
.to_string();
assert!(err.contains("Point 3"), "{err}");
}
#[test]
fn an_out_of_range_face_index_is_an_error() {
let (points, mut faces) = flat_grid(3);
faces.push([0, 1, 99]);
assert!(compute_face_offset_points(&points, &faces, 1.0, &OffsetOpts::default()).is_err());
}
fn needle(base_radius: f64, height: f64) -> (Vec<Point3>, Vec<[u32; 3]>) {
let r = base_radius;
let s = 3.0_f64.sqrt() / 2.0;
let points = vec![
Point3::new(0.0, 0.0, height), Point3::new(r, 0.0, 0.0),
Point3::new(-r * 0.5, r * s, 0.0),
Point3::new(-r * 0.5, -r * s, 0.0),
];
let faces = vec![[0, 1, 2], [0, 2, 3], [0, 3, 1]];
(points, faces)
}
#[test]
fn a_needle_tip_is_clamped() -> Result<()> {
let (points, faces) = needle(0.04, 1.0);
let d = 1.0;
let loose = OffsetOpts {
max_ratio: 1.0e6,
..Default::default()
};
let unclamped = compute_face_offset_points(&points, &faces, d, &loose)?;
let far = (unclamped[0] - points[0]).norm();
assert!(
(40.0..60.0).contains(&far),
"expected roughly 50x the distance, got {far}"
);
let clamped = compute_face_offset_points(&points, &faces, d, &OffsetOpts::default())?;
assert_relative_eq!(
(clamped[0] - points[0]).norm(),
OffsetOpts::default().max_ratio * d,
epsilon = 1.0e-9
);
let a = (unclamped[0] - points[0]).normalize();
let b = (clamped[0] - points[0]).normalize();
assert_relative_eq!(a, b, epsilon = 1.0e-9);
Ok(())
}
#[test]
fn an_extremely_thin_needle_falls_back_to_the_average_normal() -> Result<()> {
let (points, faces) = needle(1.0e-6, 1.0);
let d = 1.0;
let loose = OffsetOpts {
max_ratio: 1.0e12,
..Default::default()
};
let moved = compute_face_offset_points(&points, &faces, d, &loose)?;
let travel = (moved[0] - points[0]).norm();
assert!(
travel < 1.0 / OffsetOpts::default().rank_tolerance.sqrt(),
"travel of {travel} was not bounded by the rank cutoff"
);
Ok(())
}
#[test]
fn a_nearly_flat_vertex_is_treated_as_flat() -> Result<()> {
let (mut points, faces) = flat_grid(3);
points[4].z = 1.0e-9;
let d = 1.0;
let moved = compute_face_offset_points(&points, &faces, d, &OffsetOpts::default())?;
let u = moved[4] - points[4];
assert_relative_eq!(u.x, 0.0, epsilon = 1.0e-6);
assert_relative_eq!(u.y, 0.0, epsilon = 1.0e-6);
assert_relative_eq!(u.z, d, epsilon = 1.0e-4);
Ok(())
}
#[test]
fn degenerate_faces_are_skipped() -> Result<()> {
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(0.0, 1.0, 0.0),
];
let faces = vec![[0, 1, 2], [0, 2, 3], [0, 1, 1]];
let moved = compute_face_offset_points(&points, &faces, 1.0, &OffsetOpts::default())?;
for (before, after) in points.iter().zip(moved.iter()) {
assert_relative_eq!(
after.coords,
before.coords + Vector3::z(),
epsilon = 1.0e-12
);
}
Ok(())
}
#[test]
fn invalid_arguments_are_rejected() {
let (points, faces) = cube();
assert!(
compute_face_offset_points(&points, &faces, f64::NAN, &OffsetOpts::default()).is_err()
);
assert!(
compute_face_offset_points(
&points,
&faces,
1.0,
&OffsetOpts {
rank_tolerance: 0.0,
..Default::default()
}
)
.is_err()
);
assert!(
compute_face_offset_points(
&points,
&faces,
1.0,
&OffsetOpts {
max_ratio: 0.5,
..Default::default()
}
)
.is_err()
);
let normals = compute_point_normals(&points, &faces).unwrap();
assert!(compute_normal_displaced_points(&points, &normals[..4], 1.0).is_err());
}
}